Le voyage de l'ivrogne à la maison

Dans ce défi, vous devez écrire un programme qui simule un ivrogne trébuchant en rentrant du bar.

Contribution:

L'entrée sera une matrice d'adjacence (représentant un graphe orienté) qui représente les chemins que l'ivrogne peut emprunter. À chaque emplacement, l'ivrogne choisira un chemin au hasard (chaque option a une chance approximativement égale et est indépendante des choix antérieurs) à suivre.

Supposons que l'ivrogne commence toujours à la barre (première ligne de la matrice d'adjacence).

Si l'ivrogne entre dans une impasse, on peut supposer qu'il est soit rentré chez lui ou qu'il a été arrêté pour intoxication publique et que le programme devrait reprendre son chemin.

On peut supposer que le graphique contiendra toujours au moins une impasse.

On peut également supposer que l'ivrogne sera toujours en mesure de sortir de la barre (la première ligne ne sera pas tous des zéros) et que si l'ivrogne serait coincé dans un emplacement, que la ligne serait représentée par tous les zéros.

Sortie:

Le résultat sera le chemin emprunté par l'ivrogne pour tenter de rentrer chez lui. Les valeurs des emplacements peuvent être zéro ou un indexé.

Exemples:

Input
[1,0,1,1]
[0,0,0,0]
[1,0,0,0]
[1,1,1,1]

Possible Outputs
[0,2,0,3,2,0,0,3,1]
[0,3,0,3,1]


Input
[0,1,1,1,0,1]
[1,0,1,0,1,1]
[0,0,0,0,0,0]
[0,0,0,0,0,1]
[1,0,0,0,0,0]
[0,0,0,0,0,0]

Possible outputs
[0,1,5]
[0,5]
[0,1,4,0,2]
[0,3,5]
[0,3,0,1,4,0,5]

Deterministic path:

Input
[0,0,1,0]
[0,0,0,1]
[0,1,0,0]
[0,0,0,0]

Output
[0,2,1,3]

Mathematica, 72 octets

{1}//.{r___,x_}:>{r,x,n=1;Check[RandomChoice[#[[x]]->(n++&/@#)],##&[]]}&

Il s'agit d'une fonction qui prend la matrice comme argument et renvoie une liste, et elle utilise l'indexation 1.

L'idée de base est de commencer par

{1}//.

qui applique à plusieurs reprises la règle qui suit à la liste {1}jusqu'à ce qu'elle cesse de changer. La règle correspond au modèle

{r___,x_}:>

ce qui signifie "une liste avec zéro ou plusieurs éléments appelés rsuivis d'un élément appelé x." Cela donne xcomme dernier élément de la liste actuelle, et nous remplaçons la liste par

{r,x,<stuff>}

qui est la liste d'origine avec en <stuff>annexe. Le truc en question est

RandomChoice[#[[x]]->(n++&/@#)]

qui prend #[[x]](le xe élément de la matrice d'entrée) comme une liste de poids et les mappe n++&/@#, ce qui est court Range@Length@#(c'est- {1,2,3,...}à- dire avec la longueur appropriée). Cela générera une erreur si les poids sont tous nuls, c'est pourquoi il est enveloppé dans un

Check[...,##&[]]

qui retournera ##&[]si un message d'erreur est généré. Il s'agit simplement d'une façon sophistiquée d'écrire Sequence[], qui agit comme un élément "rien" ( {1,2,Sequence[],3}s'évalue {1,2,3}) et laisse donc la liste inchangée, ce qui provoque l' //.arrêt du remplacement.

R , 72 69 66 octets

function(m,o=1)while({print(o);any(x<-m[o,])})o=sample(which(x),1)

Essayez-le en ligne!

Prend les entrées sous forme de logicalmatrice et imprime les index basés sur 1 sur la console.

Perl 5 -a0 , 53 51 octets

Donner la matrice d'entrée sous forme de chaînes serrées séparées sur STDIN

$!/usr/bin/perl -a0
$n=!say$%;$F[$%]=~s:1:($%)=@-if 1>rand++$n:eg&&redo

Essayez-le en ligne!

Dommages @Fpendant le corps de la boucle, mais il est réparé parredo

MATL , 15 octets

1`GyY)ft?th1ZrT

La sortie est basée sur 1.

Essayez-le en ligne! Première entrée . Deuxième entrée . Troisième entrée .

Explication

1          % Push 1: initial value of current row index
`          % Do...while
  G        %   Push input matrix
  y        %   Duplicate from below: pushes copy of current row index
  Y)       %   Get that row
  f        %   Find: push (possibly empty) array of indices of non-zero entries
  t        %   Duplicate
  ?        %   If non-empty
    th     %     Attach a copy of itself. This is needed in case the array
           %     contains a single number n, because then the randsample
           %     function would incorrectly treat that as the array [1 2 ... n]
    1Zr    %     Randsample: pick 1 entry at random with uniform probability
    T      %     Push true
           %   End (implicit)
           % End (implicit). Proceed with a new iteration if the top of the
           % stack is truthy. This happens if the current row had some
           % non-zero entry, in which case true was pushed (and is now
           % consumed). If the current row was all zeros, the top of the stack
           % is an empty array that was produced by the find function, which is
           % falsy (and is also consumed now). In that case the loop is exited,
           % and then the stack contains a collection of numbers which
           % collectively describe the path
           % Implicit display

Perl 6 , 38 octets

{0,{.[$^l].grep(?*,:k).roll}...^!*.kv}

Essayez-le en ligne!

Python, 136 octets

En utilisant l'indexation zéro, en supposant que randrange a été importé. Prend une entrée m comme matrice d'adjacence

113 aucune importation

s=lambda m,c=0,p=[0],x=0:1 in m[c]and(m[c][x]and s(m,x,p+[x],randrange(len(m)))or s(m,c,p,randrange(len(m))))or p

136 avec importations

import random as r;s=lambda m,c=0,p=[0],x=0:1 in m[c]and(m[c][x]and s(m,x,p+[x],r.randrange(len(m)))or s(m,c,p,r.randrange(len(m))))or p

Rubis , 70 67 65 octets

f=->m,i=0{m[i].sum<1?[]:m[i][x=rand(m.size)]<1?f[m,i]:[x]+f[m,x]}

^{Merci à benj2240 pour avoir économisé 2 octets!}

Essayez-le en ligne!

JavaScript (ES6), 87 octets

f=(a,y=0)=>[y,.../1/.test(r=a[y])?f(a,(g=_=>r[k=Math.random()*r.length|0]?k:g())()):[]]

Essayez-le en ligne!

Version alternative, 81 octets

Prend l'entrée comme un tableau de chaînes binaires. La taille maximale prise en charge est 16x16.

f=(a,y=0)=>[y,...+(r=a[y])?f(a,(g=_=>+r[k=Math.random()*r.length|0]?k:g())()):[]]

Essayez-le en ligne!

Java 10, 135 octets

m->{var R="0 ";for(int r=0,c,t;;R+=(r=c)+" "){t=0;for(int x:m[r])t+=x;if(t<1)return R;for(t=c=m.length;m[r][c*=Math.random()]<1;)c=t;}}

0 indexé

Explication:

Essayez-le en ligne.

m->{                   // Method with integer-matrix parameter and String return-type
  var R="0 ";          //  Result-String, starting at "0 "
  for(int r=0,         //  Row-integer, starting at 0
          c,           //  Column-integer
          t;           //  Temp-integer
      ;                //  Loop indefinitely
       R+=             //    After every iteration: Append the result with:
          (r=c)+" "){  //     The current column and a delimiter-space,
                       //     And set the current row to this column at the same time
    t=0;               //   (Re-)set `t` to 0
    for(int x:m[r])    //   Loop over the values of the current row
      t+=x;            //    And add them to `t`
    if(t<1)            //   If the entire row only contained zeroes:
      return R;        //    Return the result
    for(t=c=m.length;  //   Set `t` (and `c`) to the size of the matrix
        m[r][c*=Math.random()]<1;)
                       //   Loop until we've found a 1,
                       //   picking a random column in the range [0,`c`)
      c=t;}}           //    Reset the range of `c` to `t` (the size of the matrix)

Haskell , 123 118 octets

import System.Random
i#m|sum(m!!i)<1=pure[]|1<2=do{x<-randomRIO(0,length m-1);[i#m,x#m>>=pure.(x:)]!!(m!!i!!x)}
f=(0#)

Essayez-le en ligne!

APL (Dyalog Unicode) , 32 34 octets

t←⎕
{}{s[?≢s←⍸⍵⊃t]}⍣{~0∊t⊃⍨⎕←⍵}1

Essayez-le en ligne!

Prend un tableau binaire imbriqué en entrée. Génère chaque itération sur des lignes distinctes.

Python ,97 94 octets

f=lambda a,i=0,j=0:sum(a[i])and[i]*a[i][j]+f(a[:],(i,j)[a[i][j]],id(a)**7%~-2**67%len(a))or[i]

Essayez-le en ligne!

Voir cette réponse pour plus d'explications sur le générateur de nombres aléatoires:

id(a)**7%~-2**67