Rumah Perjalanan Drunkard

23

Rumah Perjalanan Drunkard

Dalam tantangan ini Anda harus menulis sebuah program yang mensimulasikan seorang pemabuk yang tersandung dalam perjalanan pulang dari bar.

Memasukkan:

Input akan berupa matriks kedekatan (mewakili grafik berarah) yang mewakili jalur yang dapat diambil pemabuk. Di setiap lokasi, pemabuk akan memilih satu jalur secara acak (Setiap opsi memiliki peluang yang kira-kira sama dan tidak tergantung pada pilihan sebelumnya) untuk diikuti.

Asumsikan pemabuk selalu mulai di bar (baris pertama dalam matriks adjacency).

Jika pemabuk memasuki jalan buntu, dapat diasumsikan bahwa ia telah pulang atau ditangkap karena keracunan di depan umum dan program tersebut harus mengembalikan jalannya.

Dapat diasumsikan bahwa grafik akan selalu mengandung setidaknya satu jalan buntu.

Dapat juga diasumsikan bahwa pemabuk akan selalu dapat keluar dari bar (baris pertama tidak akan menjadi nol semua) dan bahwa jika pemabuk akan terjebak di suatu lokasi, bahwa baris akan diwakili oleh semua nol.

Keluaran:

Hasilnya adalah jalan yang diambil si pemabuk dalam usahanya untuk pulang. Nilai untuk lokasi dapat berupa nol atau satu diindeks.

Contoh:

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
sumber
12
Ini membawa kembali beberapa ingatan siswa ... Maksud saya, err, saya berbicara tentang grafik yang diarahkan, tentu saja! o :-)
Arnauld
Bisakah kita mengambil input sebagai array string seperti [ '1011', '0000', '1000', '1111' ]?
Arnauld
Apakah mungkin bilah menjadi buntu? Dengan kata lain, apakah baris pertama adalah nol? Juga, akankah ada baris yang hanya mengarah ke dirinya sendiri, dan apakah kita harus mendeteksi itu sebagai kondisi akhir? Dengan kata lain, apakah akan ada barisan idengan semua nol kecuali pada kolom i?
kamoroso94
5
Saya hanya menunggu seseorang untuk menulis jawaban di Taksi
Belgabad
Bagaimana Anda mendapatkan jalur terakhir dalam contoh ke-2? Dari pemahaman saya, 0link ke 1,2,3,5, namun output terakhir telah itu pergi dari 0ke4
phflack

Jawaban:

7

Mathematica, 72 byte

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

Ini adalah fungsi mengambil matriks sebagai argumen dan mengembalikan daftar, dan menggunakan 1-indexing.

Ide dasarnya adalah memulainya

{1}//.

yang berulang kali menerapkan aturan yang mengikuti daftar {1}sampai berhenti berubah. Aturan cocok dengan polanya

{r___,x_}:>

yang berarti "daftar dengan nol atau lebih elemen yang disebut rdiikuti oleh elemen yang disebut x." Ini memberi xsebagai elemen terakhir dalam daftar saat ini, dan kami mengganti daftar dengan

{r,x,<stuff>}

yang merupakan daftar asli dengan <stuff>ditambahkan. Hal-hal yang dimaksud adalah

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

yang mengambil #[[x]]( xelemen th dari matriks input) sebagai daftar bobot dan memetakannya n++&/@#, yang merupakan kependekan dari Range@Length@#(yaitu {1,2,3,...}dengan panjang yang sesuai). Ini akan melempar kesalahan jika bobotnya semua nol, itulah sebabnya dibungkus dengan a

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

yang akan kembali ##&[]jika pesan kesalahan dihasilkan. Ini hanya cara penulisan yang mewah Sequence[], yang bertindak sebagai elemen "tidak ada" ( {1,2,Sequence[],3}dievaluasi menjadi {1,2,3}) dan karenanya membuat daftar tidak berubah, menyebabkannya //.berhenti mengganti.

Gagang pintu
sumber
4

R , 72 69 66 byte

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

Cobalah online!

Mengambil input sebagai logicalmatriks, dan mencetak indeks berbasis 1 ke konsol.

Giuseppe
sumber
3

Perl 5 -a0 , 53 51 byte

Berikan matriks input sebagai string ketat terpisah pada STDIN

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

Cobalah online!

Kerusakan @Fselama loop body tetapi akan diperbaiki olehredo

Ton Hospel
sumber
3

MATL , 15 byte

1`GyY)ft?th1ZrT

Output berbasis 1.

Cobalah online! Input pertama . Input kedua . Input ketiga .

Penjelasan

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
sumber
2

Python, 136 byte

Menggunakan nol pengindeksan, dengan asumsi randrange telah diimpor. Mengambil input m sebagai matriks adjacency

113 tidak ada impor

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 dengan impor

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
sumber
3
Saya akan merekomendasikan untuk menggunakan 136 sebagai jumlah byte utama Anda, sesuai dengan pernyataan impor konsensus diperhitungkan.
Jonathan Frech
2

Ruby , 70 67 65 byte

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

Terima kasih kepada benj2240 untuk menghemat 2 byte!

Cobalah online!

Cristian Lupascu
sumber
Anda dapat menyimpan beberapa byte denganm[i].sum<1?:[]
benj2240
@ benj2240 Wow, saya tidak pernah tahu itu mungkin. Sekarang saya sadar .sumdiperkenalkan pada 2.4. Saya biasa melakukan .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())()):[]]

Cobalah online!


Versi alternatif, 81 byte

Mengambil input sebagai array dari string biner. Ukuran maksimum yang didukung adalah 16x16.

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

Cobalah online!

Arnauld
sumber
1

Java 10, 135 byte

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

Diindeks 0

Penjelasan:

Cobalah 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
sumber
1

Haskell , 123 118 byte

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

Cobalah online!

Cristian Lupascu
sumber
1

APL (Dyalog Unicode) , 32 34 byte

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

Cobalah online!

Mengambil array biner bersarang sebagai input. Menghasilkan setiap iterasi pada jalur yang berbeda.

Kritixi Lithos
sumber
1

Python ,97 94 byte

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]

Cobalah online!


Lihat jawaban ini untuk penjelasan lebih lanjut tentang pembuat bilangan acak:

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