23
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]
12This brings back some student memories... I mean, err, I'm talking about directed graphs, of course! o:-) – Arnauld – 2018-03-26T09:41:48.363
Can we take input as an array of strings such as
[ '1011', '0000', '1000', '1111' ]
? – Arnauld – 2018-03-26T12:17:49.610Is 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 columni
? – kamoroso94 – 2018-03-26T12:53:00.6875I'm just waiting for somebody to write an answer in Taxi – Belgabad – 2018-03-26T15:36:03.360
How do you get the last path in the 2nd example? From my understanding,
0
links to1,2,3,5
, but the last output has it going from0
to4
– phflack – 2018-03-26T18:54:36.397@phflack I think I wasn't thinking very clearly when I was writing them and I wrote half 0 indexed half 1 indexed – fəˈnɛtɪk – 2018-03-26T23:15:57.823