El viaje del borracho a casa

En este desafío, debes escribir un programa que simule a un borracho tropezando camino a casa desde el bar.

Entrada:

La entrada será una matriz de adyacencia (que representa un gráfico dirigido) que representa los caminos que puede tomar el borracho. En cada ubicación, el borracho elegirá un camino al azar (cada opción tiene aproximadamente la misma probabilidad y es independiente de las elecciones anteriores) a seguir.

Suponga que el borracho siempre comienza en la barra (primera fila en la matriz de adyacencia).

Si el borracho entra en un callejón sin salida, se puede suponer que se dirigió a su casa o que fue arrestado por intoxicación pública y que el programa debería retomar su camino.

Se puede suponer que el gráfico siempre contendrá al menos un callejón sin salida.

También se puede suponer que el borracho siempre podrá salir de la barra (la primera fila no será todos ceros) y que si el borracho se atascara en una ubicación, la fila estaría representada por todos los ceros.

Salida:

La salida será el camino que tomó el borracho en su intento de regresar a casa. Los valores para las ubicaciones pueden ser cero o uno indexado.

Ejemplos:

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 bytes

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

Esta es una función que toma la matriz como argumento y devuelve una lista, y utiliza la indexación 1.

La idea básica es comenzar con

{1}//.

que aplica repetidamente la regla que sigue a la lista {1}hasta que deja de cambiar. La regla coincide con el patrón.

{r___,x_}:>

lo que significa "una lista con cero o más elementos llamados rseguidos de un elemento llamado x". Esto da xcomo último elemento en la lista actual, y reemplazamos la lista con

{r,x,<stuff>}

que es la lista original con <stuff>adjunta. Lo que está en cuestión es

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

que toma #[[x]](el xelemento th de la matriz de entrada) como una lista de pesos y los asigna n++&/@#, que es la abreviatura de Range@Length@#(es decir, {1,2,3,...}con la longitud adecuada). Esto arrojará un error si los pesos son todos cero, razón por la cual está envuelto en un

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

que volverá ##&[]si se genera un mensaje de error. Esta es solo una forma elegante de escribir Sequence[], que actúa como un elemento "nada" ( {1,2,Sequence[],3}evalúa {1,2,3}) y, por lo tanto, deja la lista sin cambios, lo que hace //.que se detenga la sustitución.

R , 72 69 66 bytes

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

Pruébalo en línea!

Toma la entrada como una logicalmatriz e imprime los índices basados ​​en 1 en la consola.

Perl 5 -a0 , 53 51 bytes

Dar matriz de entrada como cadenas apretadas separadas en STDIN

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

Pruébalo en línea!

Daños @Fdurante el cuerpo del bucle pero son reparados porredo

MATL , 15 bytes

1`GyY)ft?th1ZrT

La salida está basada en 1.

Pruébalo en línea! Primera entrada . Segunda entrada . Tercera entrada .

Explicación

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 bytes

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

Pruébalo en línea!

Python, 136 bytes

Utilizando la indexación cero, suponiendo que se haya importado randrange. Toma una entrada m como matriz de adyacencia

113 sin importaciones

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 con importaciones

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

Ruby , 70 67 65 bytes

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

^{¡Gracias a benj2240 por guardar 2 bytes!}

Pruébalo en línea!

JavaScript (ES6), 87 bytes

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

Pruébalo en línea!

Versión alternativa, 81 bytes.

Toma la entrada como una matriz de cadenas binarias. El tamaño máximo admitido es 16x16.

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

Pruébalo en línea!

Java 10, 135 bytes

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 indexado

Explicación:

Pruébalo en línea.

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 bytes

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#)

Pruébalo en línea!

APL (Dyalog Unicode) , 32 34 bytes

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

Pruébalo en línea!

Toma una matriz binaria anidada como entrada. Emite cada iteración en líneas separadas.

Pitón ,97 94 bytes

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]

Pruébalo en línea!

Consulte esta respuesta para obtener más explicaciones sobre el generador de números aleatorios:

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