Étant donné 2 entrées entières représentant la taille du champ, x
et y
, sortie un chemin à travers le champ.
Exemple de sortie pour 5, 4
:
#
#
# ###
### #
Le champ entier mesure 5 par 4, et il y a un chemin fait de hachages traversant le champ.
Le chemin doit toujours commencer dans le coin supérieur gauche et aller en bas à droite. Le chemin entier doit être randomisé à chaque exécution du programme. Chaque chemin valide doit être une sortie possible.
Les règles pour les chemins sont les suivantes:
Fait de hachures
Chaque hachage n'est connecté qu'à 2 autres hachages (c'est-à-dire que le chemin ne se croise pas ou ne court pas le long de lui-même)
Les espaces non hachés peuvent être remplis avec n'importe quel autre caractère, mais il doit être cohérent (c'est-à-dire tous les espaces, toutes les périodes, etc.)
Exemples:
2, 2
##
#
3, 4
##
##
#
#
5, 5
#####
#
#
#
#
6, 5
## ###
# # #
## # #
# ## #
### #
7, 9
#######
#
#### #
# # #
# # #
# # #
# ####
#
#######
Ce type de chemin est similaire à une marche aléatoire à évitement automatique, mais il ne peut pas être adjacent à lui-même contrairement à une vraie SCIE.
La continuité du chemin et le toucher du chemin sont tous deux définis sans diagonales.
Réponses:
MATLAB,
316 305 300293 octetsMerci @LuisMendo pour diverses suggestions et un tas d'octets =)
Essayez-le en ligne! (Sans garantie: Notez que quelques ajustements ont été nécessaires pour le faire fonctionner sur Octave: Tout d'abord, j'ai dû retirer le
function
mot clé et coder en dur les valeurs, deuxièmement: Les espaces ne sont pas imprimés correctement comme dans Matlab. De plus, je n'ai pas vérifiez les commandes de convolution d'Octave, qui pourraient agir différemment.)Exemple de sortie pour l'entrée
(7,10)
(peut déjà prendre un certain temps):Explication
Cela génère des chemins séquentiellement du haut à gauche vers le bas à droite avec la connectivité 4 souhaitée, puis utilise l'échantillonnage de rejet pour rejeter les chemins qui violent le critère selon lequel vous ne pouvez pas avoir de parties adjacentes.
Oh et comme toujours:
la source
Befunge, 344 octets
Essayez-le en ligne!
Comme @flawr l'a mentionné dans sa réponse MATLAB, cela peut prendre un certain temps si la taille du champ est d'une taille non triviale. En fait, il est assez facile de se retrouver dans une situation où cela ne vaut vraiment pas la peine d'attendre qu'il se termine, car il est fort probable que vous attendiez la fin des temps.
Pour comprendre pourquoi cela se produit, il est utile de visualiser le programme en cours d'exécution dans l'un des nombreux "débogueurs visuels" de Befunge. Étant donné que les données et le code sont la même chose dans Befunge, vous pourrez voir le chemin au fil du temps. Par exemple, voici une courte animation montrant à quoi pourrait ressembler une partie d'une course sur un chemin lent.
Une fois que l'algorithme décide de faire ce virage fatidique vers la gauche au bas de la limite du champ, il s'est essentiellement condamné à une vie d'errance sans but. À partir de ce moment, il doit suivre tous les chemins possibles dans cette zone clôturée avant de pouvoir reculer et essayer de tourner à droite. Et le nombre de chemins potentiels dans ces cas peut facilement devenir astronomique.
Conclusion: si cela semble prendre beaucoup de temps, c'est probablement une bonne idée d'interrompre l'exécution et de recommencer.
Explication
Il s'agit essentiellement d'un algorithme récursif, essayant tous les chemins possibles à travers le champ, puis déroulant les étapes qui ont déjà été suivies chaque fois qu'il est bloqué. Puisque Befunge n'a pas le concept de fonctions, une fonction récursive est hors de question, mais nous pouvons émuler le processus en suivant l'état sur la pile.
Cela fonctionne en remplissant la pile de coordonnées potentielles que nous pourrions vouloir suivre. Ensuite, nous tirons un ensemble de la pile et vérifions s'il est approprié (c'est-à-dire à portée et ne chevauchant pas un chemin existant). Une fois que nous avons un bon emplacement, nous écrivons un
#
dans le champ de jeu à cet endroit et ajoutons ces détails à la pile au cas où nous aurions besoin de revenir en arrière plus tard.Nous poussons ensuite quatre autres ensembles de coordonnées sur la pile (dans un ordre aléatoire) indiquant les chemins potentiels que nous pouvons emprunter à partir de ce nouvel emplacement, et sautons au début de la boucle. Si aucun des chemins potentiels n'est réalisable, nous arriverons au point de la pile où nous avons enregistré l'emplacement de celui que
#
nous avons écrit, donc nous annulerons cette étape et continuerons d'essayer les coordonnées potentielles d'une étape précédente.Voici à quoi ressemble le code avec les différents composants mis en évidence:
Lisez la largeur et la hauteur du champ et appuyez sur les coordonnées de départ avec un
0
marqueur de type pour indiquer un chemin potentiel plutôt qu'un emplacement de retour en arrière.Vérifiez les emplacements de retour en arrière (indiqués par un
1
marqueur de type) qui sont inversés avec une simplep
commande, car ils sont stockés au format exact nécessaire pour réécrire un espace dans le champ de jeu.Vérifiez si les coordonnées sont toujours à l'intérieur du champ de jeu. S'ils sont hors de portée, supprimez-les de la pile et faites une boucle pour essayer les prochaines coordonnées potentielles.
S'ils sont dans la plage, obtenez les deux valeurs suivantes de la pile, qui est l'emplacement de l'étape précédente (requise dans le test qui suit).
Vérifiez si les coordonnées vont entrer en contact avec un segment existant du chemin. L'emplacement de l'étape précédente est évidemment ignoré de cette vérification.
Si tous les tests réussissent, écrivez un
#
dans le champ de jeu et vérifiez si nous avons atteint l'emplacement de destination.Si c'est le cas, écrivez le chemin final et quittez.
Sinon, enregistrez les coordonnées dans la pile avec un
1
marqueur de type pour un retour en arrière ultérieur.Ceci est interrompu par un calcul de nombres aléatoires dont nous aurons bientôt besoin.
Poussez quatre destinations potentielles qui peuvent être atteintes à partir de l'emplacement actuel. Le nombre aléatoire détermine l'ordre dans lequel ils sont poussés et donc l'ordre dans lequel ils seront suivis.
Revenez au début de la boucle principale et traitez les valeurs suivantes sur la pile.
la source
QBasic, 259 octets
J'adore vraiment l'
GOTO
art.Stratégie de base: à chaque étape, imprimez un
#
à l'emplacement actuel et déplacez-vous dans une direction aléatoire. Un tableaua
de 0 et de 1 permet de savoir où nous en sommes. Si le mouvement est légal et nous amène au point final,GOTO 9
pour sortir de la boucle et imprimer la finale#
. Sinon, si le déménagement est légal, faites un autre pas. Sinon, effacez l'écran et recommencez (beaucoup plus golfique que de coder un algorithme de retour en arrière!).Testé sur mon ordinateur portable en QB64, cela produit généralement un résultat
9, 9
en cinq secondes ou moins. Les séries de10, 10
ont pris entre trois et 45 secondes. Théoriquement, tous les chemins légaux ont une probabilité non nulle, mais la probabilité d'un chemin avec de grandes courbes est extrêmement faible. J'ai parfois vu des chemins avec une ou deux petites courbes, cependant:Version non golfée et / ou explication détaillée disponible sur demande.
la source
R, 225 octets
Explication:
Nous générons un graphe régulier (réseau) [x * y] non orienté avec des poids aléatoires sur les bords puis nous trouvons le chemin le plus court du début à la fin. Cependant, dans le chemin généré, il peut y avoir des cellules qui ont plus de deux neigbors par exemple:
Nous devons donc appliquer l'algorithme du chemin le plus court deux fois. Dans la deuxième fois, nous avons défini tous les poids sur 1, à l'exception de ceux qui se trouvent dans le chemin trouvé actuel qui sont définis sur 0;
résultat
Non golfé:
la source
JavaScript (ES7),
333331330329324318312 octetsExpansion: les
#
s sont placés aléatoirement dans le tableau jusqu'à ce qu'un chemin soit trouvé à travers le champ à l'aide d'une recherche en largeur; le premier, et donc le plus court, un tel chemin est ensuite sorti; cela garantit que le chemin ne se croise pas. Notez que, en particulier pour les champs plus grands, il est possible de dépasser la pile du moteur JS avant de trouver un chemin. Non golfé:la source