Écrivez un programme ou une fonction qui accepte trois entiers, une largeur w
, une hauteur h
et un nombre de pas s
. Vous allez dessiner une marche aléatoire non auto-entrecroisée s
longue sur une image 5*w
par 5*h
pixel où chaque cellule de 5 x 5 pixels est vide (beige pur) ou l'un de ces douze "tuyaux" simples:
L'image ci-dessus est agrandie pour montrer les détails. Voici les tuyaux à taille réelle:
(Les lignes grises sont juste pour séparer les types de tuyaux.)
La marche aléatoire sera un chemin de tuyau continu unique qui commence à un point d'extrémité de tuyau (l'un des quatre types de tuyaux inférieurs) et se termine à un autre point d'extrémité de tuyau.
Commencez par un vide w
par h
grille et choisir au hasard une cellule pour être le point de départ. Ensuite, choisissez au hasard l'une des quatre directions pour commencer et dessinez l'extrémité du tuyau correspondant. Cette cellule de départ marque la première étape de votre promenade et chaque fois que vous dessinez une nouvelle cellule ou écrasez une cellule existante, elle compte comme une autre étape.
Maintenant, à plusieurs reprises, choisissez au hasard d'aller à droite, à gauche ou à droite, en dessinant la cellule de tuyau appropriée si la direction choisie est valide. Revenez en arrière et choisissez à nouveau si une direction n'est pas valide jusqu'à ce que le s
chemin d'étape complet soit formé. Le chemin doit se terminer par un point d'extrémité de tuyau, qui peut se trouver n'importe où sur la grille, en fonction du parcours suivi.
Il est très important de noter que seules les deux cellules de tuyau droites peuvent être écrasées, et uniquement par la cellule de tuyau droite de l'orientation opposée, le résultat étant une cellule d'intersection. Sinon, tous les tuyaux doivent être placés dans des cellules vides.
Lorsqu'une intersection est dessinée, la partie du chemin la plus éloignée de la cellule de départ doit être dessinée en haut.
C'est à vous de décider si la grille a ou non des conditions aux limites périodiques (PBC), c'est-à-dire si une conduite sortant d'un côté de la grille sortira de l'autre côté. Sans PBC, la limite de la grille compte comme une barrière que vous pouvez rencontrer comme les autres tuyaux.
Cas spéciaux
- Lorsque la valeur
s
est 0, aucun tuyau ne doit être tracé et la sortie doit être un blanc5*w
par5*h
image (c'est-à-dire tout beige). Quand
s
est 1 un bout de tuyau simpledoit être tracé dans la cellule de départ choisie au hasard.
Autres détails
- Vous pouvez supposer que
s
c'est tout au plusw*h
donc un chemin sera toujours possible. (Bien que des chemins plus longs soient possibles en raison des intersections.) w
eth
sera toujours positif.- Tous les choix aléatoires doivent être uniformément aléatoires. Par exemple, vous ne devez pas éviter de créer des intersections quand elles sont possibles même si cela facilite le problème. Les générateurs de nombres pseudo-aléatoires sont autorisés.
- Trois couleurs visuellement distinctes peuvent être utilisées à la place du noir, du bleu et du beige.
- Vos images de sortie peuvent être agrandies de sorte qu'elles soient vraiment
5*w*k
en5*h*k
pixels oùk
est un entier positif. (Il est conseillé d'agrandir tous les exemples que vous publiez, même si vous en avezk
1.) - N'importe quel format de fichier d'image sans perte commun peut être utilisé et l'image peut être enregistrée dans un fichier, affichée ou crue sur stdout.
Le code le plus court en octets gagne.
Exemples
(Le tout agrandi de 500%.)
Si l'entrée est w=2, h=1, s=0
alors la sortie sera toujours:
Si l'entrée est w=2, h=1, s=1
alors la sortie sera l'une de ces images avec une chance égale:
Si l'entrée est w=2, h=1, s=2
alors la sortie sera
ou peut-être
si le réseau est supposé avoir du PBC.
(Notez que démarrer le chemin comme le rendrait impossible une deuxième étape.)
Voici quelques sorties possibles pour w=3, h=2, s=6
, en supposant PBC:
Voici une sortie possible pour w=3, h=3, s=9
, en supposant PBC:
Notez que le chemin n'a pas eu besoin de couvrir toutes les cellules car l'intersection compte pour deux étapes. De plus, nous pouvons en déduire que le point d'extrémité d'angle était la cellule de départ car le passage supérieur d'intersection doit avoir été tracé par la suite. Ainsi, nous pouvons déduire la séquence de choix aléatoires qui ont été faits:
start at top left, facing east
go straight
go right
go right
go right
go straight
go left
go right
end
Enfin, voici des exemples de w=4, h=5, s=20
et w=4, h=5, s=16
:
la source
You will be drawing a non-self-intersecting random walk
... est-elle auto-intersectée ou non?Réponses:
CJam, 274
Essayez-le en ligne
Utilise PBC, sorties au format PGM. Vous pouvez supprimer la
:+
fin pour obtenir une sortie visuelle plus agréable dans le navigateur.C'est très lent pour une entrée plus importante, surtout si le nombre de pas est proche de la zone.
Exemple de résultat pour l'entrée
4 3 10
(mise à l'échelle 500%):Brève explication:
L'approche générale est la suivante:
la source
QBasic,
517516 octetsw
,h
et às
partir de l'entrée utilisateur, séparé par des virgules.L'approche ici consiste à essayer une direction aléatoire à chaque étape et à recommencer depuis le début si elle entraîne un mouvement invalide. Nous dessinons les tuyaux au fur et à mesure que les directions sont décidées et utilisons
POINT
pour tester des points sur l'écran pour nos conditions de validité. Un mouvement est valide s'il ne sort pas des limites de la grille et:Comme la réponse CJam d'Aditsu , ce code est très lent et peut être incroyablement lent s'il
s
représente une fraction importante dew*h
. Sur ma configuration QB64, il fournit une réponse5,5,19
assez rapidement, mais prend plus de temps que je ne le souhaitais5,5,20
.Si vous souhaitez exécuter des exemples plus volumineux / plus denses, voici mon approche originale en utilisant une recherche en profondeur d'abord . C'est beaucoup plus efficace, au prix d'un énorme 300 octets supplémentaires.
Exemple de sortie pour les entrées
10, 10, 100
, taille réelle:Une version encore plus sophistiquée peut être trouvée dans cet essentiel . En plus d'être non golfé et complètement commenté, il augmente la sortie d'un facteur constant et permet un délai défini entre les étapes, vous permettant de regarder l'algorithme DFS au travail. Voici un exemple d'exécution:
la source