Drunkard's Journey Home

23

Drunkard's Journey Home

W tym wyzwaniu masz napisać program, który symuluje pijaka potykającego się z baru do domu.

Wkład:

Dane wejściowe będzie macierzą przyległości (reprezentującą skierowany wykres), która reprezentuje ścieżki, którymi może podążać pijak. W każdej lokalizacji pijak wybiera losowo jedną ścieżkę (każda opcja ma w przybliżeniu jednakową szansę i jest niezależna od wcześniejszych wyborów), którą należy podążać.

Załóż, że pijak zawsze zaczyna się od paska (pierwszy rząd w macierzy przylegania).

Jeśli pijak wejdzie w ślepy zaułek, można założyć, że albo udał się do domu, albo został aresztowany za publiczne zatrucie, a program powinien powrócić.

Można założyć, że wykres zawsze będzie zawierał przynajmniej jeden ślepy zaułek.

Można również założyć, że pijak zawsze będzie mógł wyjść z paska (pierwszy rząd nie będzie wszystkich zer) i że jeśli pijak utknie w miejscu, rząd będzie reprezentowany przez wszystkie zera.

Wydajność:

Wynikiem będzie ścieżka, którą pijak podjął, próbując wrócić do domu. Wartości lokalizacji mogą być zerowe lub zindeksowane.

Przykłady:

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
źródło
12
To przywraca wspomnienia studentów ... To znaczy, mówię, oczywiście, o ukierunkowanych grafach! o :-)
Arnauld
Czy możemy brać dane wejściowe jako tablicę ciągów takich jak [ '1011', '0000', '1000', '1111' ]?
Arnauld
Czy to możliwe, że bar jest ślepym zaułkiem? Innymi słowy, czy pierwszy wiersz będzie kiedyś zerem? Czy kiedykolwiek będzie rząd, który prowadzi tylko do siebie i czy będziemy musieli to wykryć jako warunek końcowy? Innymi słowy, czy kiedykolwiek będzie wiersz ize wszystkimi zerami oprócz kolumny i?
kamoroso94
5
Po prostu czekam, aż ktoś napisze odpowiedź w Taxi
Belgabad
Jak uzyskać ostatnią ścieżkę w drugim przykładzie? Z mojego zrozumienia, 0linki do 1,2,3,5, ale ostatni wyjściowa idzie od 0do4
phflack

Odpowiedzi:

7

Mathematica, 72 bajty

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

Ta funkcja przyjmuje macierz jako argument i zwraca listę i wykorzystuje indeksowanie 1.

Podstawową ideą jest zacząć

{1}//.

która wielokrotnie stosuje regułę, która następuje po liście, {1}aż przestanie się zmieniać. Reguła pasuje do wzorca

{r___,x_}:>

co oznacza „listę zawierającą zero lub więcej wywoływanych elementów, rpo których następuje element o nazwie x”. Daje to xjako ostatni element na bieżącej liście, a my zastępujemy listę

{r,x,<stuff>}

która jest oryginalną listą z <stuff>dołączonym. Chodzi o to

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

który przyjmuje #[[x]]( xth element macierzy wejściowej) jako listę wag i odwzorowuje je n++&/@#, co jest skrótem Range@Length@#(tj. {1,2,3,...}o odpowiedniej długości). Spowoduje to błąd, jeśli wszystkie odważniki są zerowe, dlatego jest zawinięte w a

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

który zwróci, ##&[]jeśli zostanie wygenerowany komunikat o błędzie. To tylko fantazyjny sposób pisania Sequence[], który działa jako element „nic” ( {1,2,Sequence[],3}ocenia na {1,2,3}) i dlatego pozostawia listę bez zmian, powodując, że //.przestaje się zamieniać.

Klamka
źródło
4

R , 72 69 66 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe jako logicalmacierz i drukuje na konsoli indeksy oparte na 1.

Giuseppe
źródło
3

Perl 5 -a0 , 53 51 bajtów

Podaj macierz wejściową jako osobne ciasne łańcuchy w STDIN

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

Wypróbuj online!

Uszkodzenia @Fw korpusie pętli, ale zostają naprawione przezredo

Ton Hospel
źródło
3

MATL , 15 bajtów

1`GyY)ft?th1ZrT

Wyjście jest oparte na 1.

Wypróbuj online! Pierwsze wejście . Drugie wejście . Trzecie wejście .

Wyjaśnienie

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
źródło
2

Python, 136 bajtów

Przy użyciu zerowego indeksowania, zakładając, że randrange został zaimportowany. Przyjmuje dane wejściowe m jako macierz przylegania

113 brak importu

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 z importem

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
źródło
3
Zalecam użycie 136 jako głównego licznika bajtów, ponieważ zgodnie z konsensusem importowane liczniki liczą się do niego.
Jonathan Frech
2

Rubinowy , 70 67 65 bajtów

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

Dzięki benj2240 za oszczędność 2 bajtów!

Wypróbuj online!

Cristian Lupascu
źródło
Możesz zaoszczędzić kilka bajtów za pomocąm[i].sum<1?:[]
benj2240
@ benj2240 Wow, nigdy nie wiedziałem, że to możliwe. Teraz zdałem sobie sprawę, że .sumzostał wprowadzony w wersji 2.4. Robiłem .reduce(0, :+)...
Cristian Lupascu
2

JavaScript (ES6), 87 bajtów

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

Wypróbuj online!


Wersja alternatywna, 81 bajtów

Pobiera dane wejściowe jako tablicę ciągów binarnych. Maksymalny obsługiwany rozmiar to 16 x 16.

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

Wypróbuj online!

Arnauld
źródło
1

Java 10, 135 bajtów

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

Wyjaśnienie:

Wypróbuj online.

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
źródło
1

Haskell , 123 118 bajtów

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

Wypróbuj online!

Cristian Lupascu
źródło
1

APL (Dyalog Unicode) , 32 34 bajty

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

Wypróbuj online!

Pobiera zagnieżdżoną tablicę binarną jako dane wejściowe. Wyświetla każdą iterację w osobnych wierszach.

Kritixi Lithos
źródło
1

Pyton ,97 94 bajty

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]

Wypróbuj online!


Zobacz tę odpowiedź, aby uzyskać więcej wyjaśnień na temat generatora liczb losowych:

id(a)**7%~-2**67
Vincent
źródło