Drunkard's Journey Home 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]
Mathematica, 72 bytes

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


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_}:&gt;


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,&lt;stuff&gt;}


which is the original list with &lt;stuff&gt; appended. The stuff in question is

RandomChoice[#[[x]]-&gt;(n++&amp;/@#)]


which takes #[[x]] (the xth element of the input matrix) as a list of weights and maps them to n++&amp;/@#, 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[...,##&amp;[]]


which will return ##&amp;[] 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.