Drunkards Heimreise

In dieser Herausforderung musst du ein Programm schreiben, das einen Säufer simuliert, der von der Bar nach Hause stolpert.

Eingang:

Die Eingabe ist eine Adjazenzmatrix (die einen gerichteten Graphen darstellt), die Pfade darstellt, die der Betrunkene nehmen kann. An jedem Ort wählt der Betrunkene zufällig einen Weg (jede Option hat ungefähr die gleiche Chance und ist unabhängig von vorherigen Entscheidungen).

Angenommen, der Säufer beginnt immer an der Bar (erste Reihe in der Adjazenzmatrix).

Wenn der Betrunkene in eine Sackgasse gerät, kann davon ausgegangen werden, dass er entweder nach Hause gegangen ist oder wegen öffentlicher Vergiftung festgenommen wurde und das Programm seinen Weg zurückkehren sollte.

Es ist davon auszugehen, dass der Graph immer mindestens eine Sackgasse enthält.

Es kann auch davon ausgegangen werden, dass der Säufer den Balken immer verlassen kann (die erste Reihe besteht nicht aus Nullen) und dass, wenn der Säufer an einem Ort festsitzt, die Reihe durch Nullen dargestellt wird.

Ausgabe:

Das Ergebnis wird der Weg sein, den der Betrunkene bei seinem Versuch eingeschlagen hat, nach Hause zu kommen. Die Werte für die Speicherorte können entweder null oder eins sein.

Beispiele:

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++&/@#)],##&[]]}&

Dies ist eine Funktion, die die Matrix als Argument verwendet, eine Liste zurückgibt und die 1-Indexierung verwendet.

Die Grundidee ist, mit zu beginnen

{1}//.

Dabei wird die folgende Regel wiederholt auf die Liste angewendet, bis die {1}Änderung beendet ist. Die Regel entspricht dem Muster

{r___,x_}:>

Dies bedeutet "eine Liste mit null oder mehr aufgerufenen Elementen, rgefolgt von einem aufgerufenen Element x." Dies gibt xals letztes Element in der aktuellen Liste an, und wir ersetzen die Liste durch

{r,x,<stuff>}

Das ist die ursprüngliche Liste mit <stuff>angehängten. Das fragliche Zeug ist

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

Dieser nimmt #[[x]](das xdritte Element der Eingabematrix) als eine Liste von Gewichten und ordnet sie zu n++&/@#, was für Range@Length@#(dh {1,2,3,...}mit der entsprechenden Länge) kurz ist. Dies wird einen Fehler auslösen, wenn die Gewichte alle Null sind, weshalb es in a eingeschlossen ist

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

##&[]Diese Meldung wird zurückgegeben, wenn eine Fehlermeldung generiert wird. Dies ist nur eine ausgefallene Schreibweise Sequence[], die als "nichts" -Element fungiert (als " {1,2,Sequence[],3}wertend" {1,2,3}) und daher die Liste unverändert lässt, wodurch das //.Ersetzen beendet wird.

R , 72 69 66 Bytes

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

Probieren Sie es online!

Nimmt Eingaben als logicalMatrix und druckt die 1-basierten Indizes auf die Konsole.

Perl 5 -a0 , 53 51 Bytes

Geben Sie die Eingabematrix als separate enge Zeichenfolgen in STDIN ein

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

Probieren Sie es online!

Beschädigungen @Fwährend des Schleifenkörpers werden jedoch durch repariertredo

MATL , 15 Bytes

1`GyY)ft?th1ZrT

Die Ausgabe ist 1-basiert.

Probieren Sie es online! Erste Eingabe . Zweiter Eingang . Dritte Eingabe .

Erläuterung

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}

Probieren Sie es online!

Python, 136 Bytes

Unter der Annahme, dass randrange importiert wurde, wird die Null-Indexierung verwendet. Nimmt eine Eingabe m als Adjazenzmatrix

113 keine Importe

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 mit Importen

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]}

^{Danke an benj2240 für das Speichern von 2 Bytes!}

Probieren Sie es online!

JavaScript (ES6), 87 Byte

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

Probieren Sie es online!

Alternative Version, 81 Bytes

Übernimmt die Eingabe als Array von Binärzeichenfolgen. Die maximal unterstützte Größe beträgt 16x16.

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

Probieren Sie es online!

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-indiziert

Erläuterung:

Probieren Sie es online aus.

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

Probieren Sie es online!

APL (Dyalog Unicode) , 32 34 Bytes

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

Probieren Sie es online!

Nimmt ein verschachteltes binäres Array als Eingabe. Gibt jede Iteration in separaten Zeilen aus.

Python ,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]

Probieren Sie es online!

In dieser Antwort finden Sie weitere Erklärungen zum Zufallszahlengenerator:

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