Drunkards Heimreise

23

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]
fəˈnəˈtɛk
quelle
12
Das bringt einige Schülererinnerungen zurück ... Ich meine, ähm, ich spreche natürlich von gerichteten Graphen! o :-)
Arnauld
Können wir Eingaben als ein Array von Zeichenfolgen wie z [ '1011', '0000', '1000', '1111' ].
Arnauld
Ist es möglich, dass die Bar eine Sackgasse ist? Mit anderen Worten, wird die erste Zeile jemals aus Nullen bestehen? Wird es auch jemals eine Reihe geben, die nur zu sich selbst führt, und müssen wir das als Endbedingung erkennen? Mit anderen Worten, wird es jemals eine Zeile imit allen Nullen außer in der Spalte geben i?
Kamoroso94
5
Ich warte nur darauf, dass jemand eine Antwort in Taxi
Belgabad
Wie kommt man im 2. Beispiel zum letzten Pfad? 01,2,3,504
Nach

Antworten:

7

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.

Türknauf
quelle
4

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.

Giuseppe
quelle
3

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

Tonne Hospel
quelle
3

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
Luis Mendo
quelle
2

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

Budd
quelle
3
Ich würde empfehlen, 136 als Hauptbytezahl zu verwenden, da gemäß Konsens Importanweisungen dazu zählen.
Jonathan Frech
2

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!

Cristian Lupascu
quelle
Sie können ein paar Bytes mit m[i].sum<1?:[]
speichern
@ benj2240 Wow, ich wusste nie, dass das möglich ist. Jetzt wurde mir klar, dass .sumes in 2.4 eingeführt wurde. Früher habe ich .reduce(0, :+)...
Cristian Lupascu
2

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!

Arnauld
quelle
1

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)
Kevin Cruijssen
quelle
1

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!

Cristian Lupascu
quelle