There is a mouse in a room, in the top-left corner. It can move up, down, left, or right, and the mouse cannot go through any cell in the room twice. Given this, return all the possible paths in which the mouse will visit every square.

Input: Two integers m and n, which represent the m x n room. m<9, n<9.

Output: The m x n room, with ^<>v noting the direction the path goes. Each line of the room will be seperated by a newline, and each room will be seperated by one newline. The last room the mouse enters will be noted by a dot.

v > v .
v ^ v ^
> ^ > ^

next room goes here...

Test Cases:

Input: 2 3, output:

v > v
> ^ .

> > v
. < <

v . <
> > ^

Shortest code wins.

beary605

Posted 2012-07-01T08:17:53.680

Reputation: 3 904

Is there any restriction about the very last step? Since the mouse already entered each cell, any of the four directions would be ok. – Howard – 2012-07-01T15:20:36.883

@Howard: Whoops! The mouse can only go through cells once. – beary605 – 2012-07-01T16:01:55.900

1So that means that the last step must go "outside" of the grid? Because the very last example in your test cases does not fulfill this rule. (should be v^<, >>^ then) – Howard – 2012-07-01T16:13:49.237

@Howard: Ok, I see what you are getting at now. The last step is unrestricted. – beary605 – 2012-07-01T16:22:10.703

1I edited your question to improve the example output formatting. While doing so, I also moved the dot in the last example output room, since it appeared to be misplaced. (The mouse cannot end its path in the upper left corner, since that's where it started.) Please correct me if I made any mistakes. – Ilmari Karonen – 2012-07-02T15:42:00.537

@IlmariKaronen: That's a much better output. Thanks! – beary605 – 2012-07-02T15:43:37.713

Answers

GolfScript, 146 137 characters

~:h\:w*:s(4\?,{[[0.]{\.4/\4%@[0$"<^v>"3$=]@2*)@[~2$3/+(\@3%+(\]@\}s(*[\;46]].{.0=.~0(>\0(>@~h<\w<&&&\0=~w*+*}%$s,={${1=}%h/n*n+n+}{;}if}%

The code shows a very direct implementation in GolfScript. Therefore, I suspect that there is plenty room for improvement. Be aware that the algorithm is really slow if you try it on anything larger than 3x3 or 2x4. I decided to put a . for the last position since any direction would be allowed there (the mouse already entered each cell and the last step is irrelevant).

Example:

> 2 4
>>>v
.<<<

v.<<
>>>^

v>>v
>^.<

v>v.
>^>^

Edit: Minor changes.

Howard

Posted 2012-07-01T08:17:53.680

Reputation: 23 109

I like your dot idea. I will add that into the rules – beary605 – 2012-07-02T04:08:28.047

Python, 296 269

With so many suggestions from others, I decided to make this a community solution. Tabs have been replaced with 4 spaces.

a=[-1,0,1,0];d='<^>v.'
def r(x,y):
 if G.values().count(4)<2:
    for i in n:print''.join(d[G[j,i]]for j in m)
    print
 for i in range(4):
    X=x+a[i];Y=y+a[i-1]
    if 4==G.get((X,Y)):G[x,y]=i;r(X,Y);G[X,Y]=4
m,n=map(range,input())
G=dict(((i,j),4)for i in m for j in n)
r(0,0)

Example

$ python paths.py
5,2
>>>>v
.<<<<

v>>>v
>^.<<

v>v>v
>^>^.

v>v.<
>^>>^

v.<<<
>>>>^

boothby

Posted 2012-07-01T08:17:53.680

Reputation: 9 038

By three newlines, I meant \n for the end of the first room, \n to seperate them, and... I'm not sure why there's a third. You only need one newline now. – beary605 – 2012-07-02T04:11:37.327

@beary605 w00, saved 6 characters! – boothby – 2012-07-02T04:17:22.593

1You could save a few characters with m,n=map(range,input()). It would mean you could use for i in m rather than for i in range(m). – grc – 2012-07-02T05:14:54.130

1Also an additional two chars by swapping up and down ('<^>v') and then X=x+a[i];Y=y+a[i-1]. – Howard – 2012-07-02T05:39:27.393

1Small changes: if(X,Y)in G and'.'==G[X,Y] -> if'.'==G.get((X,Y)), print''.join(...); print -> print''.join(...)+'\n' and substitute '.' with a variable. – Ante – 2012-07-02T13:40:12.307

Mathematica 347 315 chars

Very slow for all but the smallest arrays. This is because the solution is overly general, treating the paths as Hamiltonian Graphs rather than something more specific like a grid. Anyway, here's the code:

Needs["Combinatorica`"]
p=ReplacePart;
q[l_,{},s_]:=p[s,l->"."]//Grid
q[l_, d_,s_]:=q[l+d[[1,1]], Rest@d,p[s,l:>d[[1,2]]]]
f[r_,c_]:=Column[q[{1,1},Differences[#]/.{-1-> {{0,-1},"<"},1-> {{0,1},">"},c-> {{1,0},"v"},-c-> {{-1,0},"^"}},ConstantArray[0,{r,c}]]&/@Cases[HamiltonianPath[GridGraph[c,r],All],{1,__}],Spacings->{0,3}]

Example (I reformatted the output into a table):

"4 4"
f@@ImportString[%,"Table"][[1]]

result44

DavidC

Posted 2012-07-01T08:17:53.680

Reputation: 24 524

Mouse in a room

Answers

GolfScript, 146 137 characters

Python, 296 269

Mathematica 347 315 chars