23
\$\begingroup\$

Drunkard's Journey Home

In this challenge you are to write a program which simulates a drunkard stumbling his way home from the bar.

Input:

The input will be an adjacency matrix (representing a directed graph) which represents paths the drunkard can take. At each location, the drunkard will choose one path at random (Each option has an approximately equal chance and is independent of prior choices) to follow.

Assume that the drunkard always starts at the bar (first row in the adjacency matrix).

If the drunkard enters a dead-end it can be assumed that he has either made his way home or has been arrested for public intoxication and the program should return his path.

It can be assumed that the graph will always contain at least one dead-end.

It can also be assumed that the drunkard will always be able to exit the bar (the first row will not be all zeroes) and that if the drunkard would be stuck in a location, that the row would be represented by all zeroes.

Output:

The output will be the path the drunkard took in his attempt to make his way home. The values for the locations can be either zero or one indexed.

Examples:

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]
\$\endgroup\$
  • 12
    \$\begingroup\$ This brings back some student memories... I mean, err, I'm talking about directed graphs, of course! o:-) \$\endgroup\$ – Arnauld Mar 26 '18 at 9:41
  • \$\begingroup\$ Can we take input as an array of strings such as [ '1011', '0000', '1000', '1111' ]? \$\endgroup\$ – Arnauld Mar 26 '18 at 12:17
  • \$\begingroup\$ Is it possible for the bar to be a dead end? In other words, will the first row ever be all zeroes? Also, will there ever be a row that only leads to itself, and will we have to detect that as an end condition? In other words, will there ever be a row i with all zeros except at column i? \$\endgroup\$ – kamoroso94 Mar 26 '18 at 12:53
  • 5
    \$\begingroup\$ I'm just waiting for somebody to write an answer in Taxi \$\endgroup\$ – Belgabad Mar 26 '18 at 15:36
  • \$\begingroup\$ How do you get the last path in the 2nd example? From my understanding, 0 links to 1,2,3,5, but the last output has it going from 0 to 4 \$\endgroup\$ – phflack Mar 26 '18 at 18:54

12 Answers 12

7
\$\begingroup\$

Mathematica, 72 bytes

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

This is a function takes the matrix as an argument and returns a list, and it uses 1-indexing.

The basic idea is to start with

{1}//.

which repeatedly applies the rule that follows to the list {1} until it stops changing. The rule matches the pattern

{r___,x_}:>

which means "a list with zero or more elements called r followed by an element called x." This gives x as the last element in the current list, and we replace the list with

{r,x,<stuff>}

which is the original list with <stuff> appended. The stuff in question is

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

which takes #[[x]] (the xth element of the input matrix) as a list of weights and maps them to n++&/@#, which is short for Range@Length@# (i.e. {1,2,3,...} with the appropriate length). This will throw an error if the weights are all zero, which is why it's wrapped in a

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

which will return ##&[] if an error message is generated. This is just a fancy way of writing Sequence[], which acts as a "nothing" element ({1,2,Sequence[],3} evaluates to {1,2,3}) and therefore leaves the list unchanged, causing the //. to stop replacing.

\$\endgroup\$
4
\$\begingroup\$

R, 72 69 66 bytes

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

Try it online!

Takes input as a logical matrix, and prints the 1-based indices to the console.

\$\endgroup\$
3
\$\begingroup\$

Perl 5 -a0, 53 51 bytes

Give input matrix as separate tight strings on STDIN

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

Try it online!

Damages @F during the loop body but it gets repaired by redo

\$\endgroup\$
3
\$\begingroup\$

MATL,15 bytes

1`GyY)ft?th1ZrT

Output is 1-based.

Try it online! First input. Second input. Third input.

Explanation

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
\$\endgroup\$
2
\$\begingroup\$

Perl 6, 38 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python, 136 bytes

Using zero indexing, assuming randrange has been imported. Takes an input m as the adjacency matrix

113 no imports

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 with imports

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

\$\endgroup\$
  • 3
    \$\begingroup\$ I would recommend to use 136 as your main byte count, as per consensus import statements count towards it. \$\endgroup\$ – Jonathan Frech Mar 26 '18 at 17:45
2
\$\begingroup\$

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

Thanks to benj2240 for saving 2 bytes!

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You can save a couple bytes with m[i].sum<1?:[] \$\endgroup\$ – benj2240 Mar 26 '18 at 19:52
  • \$\begingroup\$ @benj2240 Wow, I never knew that was possible. Now I realized .sum was introduced in 2.4. I used to do .reduce(0, :+)... \$\endgroup\$ – Cristian Lupascu Mar 27 '18 at 6:29
2
\$\begingroup\$

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())()):[]]

Try it online!


Alternate version, 81 bytes

Takes input as an array of binary strings. The maximum supported size is 16x16.

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

Explanation:

Try it 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)
\$\endgroup\$
1
\$\begingroup\$

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Unicode), 32 34 bytes

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

Try it online!

Takes a nested binary array as input. Outputs each iteration on separate lines.

\$\endgroup\$
1
\$\begingroup\$

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]

Try it online!


See this answer for more explanation about the random number generator:

id(a)**7%~-2**67
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.