5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is there any restriction about the very last step? Since the mouse already entered each cell, any of the four directions would be ok. \$\endgroup\$ – Howard Jul 1 '12 at 15:20
  • \$\begingroup\$ @Howard: Whoops! The mouse can only go through cells once. \$\endgroup\$ – beary605 Jul 1 '12 at 16:01
  • 1
    \$\begingroup\$ So 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) \$\endgroup\$ – Howard Jul 1 '12 at 16:13
  • \$\begingroup\$ @Howard: Ok, I see what you are getting at now. The last step is unrestricted. \$\endgroup\$ – beary605 Jul 1 '12 at 16:22
  • 1
    \$\begingroup\$ I 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. \$\endgroup\$ – Ilmari Karonen Jul 2 '12 at 15:42
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I like your dot idea. I will add that into the rules \$\endgroup\$ – beary605 Jul 2 '12 at 4:08
4
\$\begingroup\$

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.<<<
>>>>^
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – beary605 Jul 2 '12 at 4:11
  • \$\begingroup\$ @beary605 w00, saved 6 characters! \$\endgroup\$ – boothby Jul 2 '12 at 4:17
  • 1
    \$\begingroup\$ You 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). \$\endgroup\$ – grc Jul 2 '12 at 5:14
  • 1
    \$\begingroup\$ Also an additional two chars by swapping up and down ('<^>v') and then X=x+a[i];Y=y+a[i-1]. \$\endgroup\$ – Howard Jul 2 '12 at 5:39
  • 1
    \$\begingroup\$ Small 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. \$\endgroup\$ – Ante Jul 2 '12 at 13:40
1
\$\begingroup\$

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

\$\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.