## 816 - Abbott's Revenge

Moderator: Board moderators

Examiner
New poster
Posts: 27
Joined: Thu Feb 19, 2004 1:19 pm

### 816 - Abbott's Revenge

Code: Select all

north
north
east
east
south
west
west
south
west
north
north
east
south
east
east
south
west
south

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Did you generate it by hand? If yes, how long did you take?
I didn't try it by hand, but my program gives answer of same length as yours.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
That depends on how you define "by hand".
I did a paper&pecil version of a BFS, marking the edges while 'floodfilling' the maze. I would guess it took about 15 minutes to find a path of length 18 (nwseenwswnneseesws), 5 minutes to copy the maze and 10 to solve it.
If "by hand" means only staring at the picture, without the use of a pencil, it looks next to impossible.

I guess you could do a BFS in a real maze by leaving special 'bread crums' and do a lot of walking around (taking illegal paths while solving the maze saves considerable time).

Very nice problem!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
One remark:
The output description tells you to print 10 intersections per line, but the sample output only has 9 intersections per line!
If you print the correct intersections 9 per line you get WA (not PE). Be warned, you can spend a lot of time debugging a good working program (Although not as much as getting a good working program in the first place. Excelent problem!).

Good work writing a testset, Adrian! Must have taken some time to convert mazes into input files... and there are no errors, as far as my assert()s have checked, like arrows into oblivion.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Thanks for pointing out the sample output is wrong. I am sorry, I made a mistake when converting the pdf to html, in the pdf there were also 10 intersections per line in the sample output.
About creating testset: I converted only the Atlanta maze of figure 2, the other mazes are created randomly (but each arrow points to another point in the maze).

Examiner
New poster
Posts: 27
Joined: Thu Feb 19, 2004 1:19 pm
I did it using pencil and paper. The trick is to trace from both ends; then there are not many choices left. I was quite excited after solving, in about 10 minutes, and wanted to share my result; so I posted it on the forum. But I haven't tried the programming question yet.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
This question is definitely easier than dice maze in ACM 1999 world finals.

t_sergiu
New poster
Posts: 12
Joined: Sun Mar 02, 2008 6:18 am

### Re: 816 - Abbott’s Revenge

Does anybody know why this would generate a wrong answer. I'm absolutely sure my output is correct, however the judge may want an extra newline or something. Can anyone give me some sample test cases?
Thanks.

chousheng
New poster
Posts: 1
Joined: Thu Aug 07, 2008 6:13 pm

### Re: 816 - Abbott’s Revenge

I got wrong answers. Can anyone verify my output? Thanks

Here is my input and output:

Code: Select all

SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
MyMaze 1
3 1 N 1 1
0
MyMaze 2
3 1 N 3 1
0
MyMaze 3
3 1 N 2 1
0
MyMaze 4
2 2 W 3 2
1 1 NR *
1 2 ER *
2 1 WR *
2 2 SF *
0
MyMaze 5
2 2 N 2 3
1 1 WL *
1 2 NL *
2 1 SF *
2 2 NR *
3 1 SL *
3 2 EL *
0
Circle
2 1 N 2 1
1 1 NR *
1 2 ER *
2 2 SF *
3 1 WR *
3 2 SR *
0
Robert Abbott's Atlanta Maze
4 2 N 4 3
1 1 NR WL *
1 2 NLR WF EFR *
1 3 EFR WFR NL *
1 4 ER NL *
2 1 SFL WL NFR *
2 2 EL SFLR WFRL NFL *
2 3 EFLR SF NF WFRL *
2 4 SR ELR NF *
3 1 WR SL *
3 2 EFL SLR WR NF *
3 3 EFL SLR WL *
3 4 EL SR *
0
END

Code: Select all

SAMPLE
(3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1)
(2,2) (1,2) (1,3) (2,3) (3,3)
NOSOLUTION
No Solution Possible
MyMaze 1
No Solution Possible
MyMaze 2
No Solution Possible
MyMaze 3
(3,1) (2,1)
MyMaze 4
(2,2) (2,1) (1,1) (1,2) (2,2) (3,2)
MyMaze 5
(2,2) (1,2) (1,1) (2,1) (3,1) (3,2) (2,2) (2,3)
Circle
(2,1) (1,1) (1,2) (2,2) (3,2) (3,1) (2,1)
Robert Abbott's Atlanta Maze
(4,2) (3,2) (2,2) (1,2) (1,3) (1,4) (2,4) (2,3) (2,2) (3,2)
(3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (2,4) (3,4) (3,3) (4,3)

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 816 - Abbott’s Revenge

chousheng wrote:I got wrong answers. Can anyone verify my output? Thanks

Here is my input and output:

Code: Select all

SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
MyMaze 1
3 1 N 1 1
0
MyMaze 2
3 1 N 3 1
0
MyMaze 3
3 1 N 2 1
0
MyMaze 4
2 2 W 3 2
1 1 NR *
1 2 ER *
2 1 WR *
2 2 SF *
0
MyMaze 5
2 2 N 2 3
1 1 WL *
1 2 NL *
2 1 SF *
2 2 NR *
3 1 SL *
3 2 EL *
0
Circle
2 1 N 2 1
1 1 NR *
1 2 ER *
2 2 SF *
3 1 WR *
3 2 SR *
0
Robert Abbott's Atlanta Maze
4 2 N 4 3
1 1 NR WL *
1 2 NLR WF EFR *
1 3 EFR WFR NL *
1 4 ER NL *
2 1 SFL WL NFR *
2 2 EL SFLR WFRL NFL *
2 3 EFLR SF NF WFRL *
2 4 SR ELR NF *
3 1 WR SL *
3 2 EFL SLR WR NF *
3 3 EFL SLR WL *
3 4 EL SR *
0
END

Code: Select all

SAMPLE
(3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1)
(2,2) (1,2) (1,3) (2,3) (3,3)
NOSOLUTION
No Solution Possible
MyMaze 1
No Solution Possible
MyMaze 2
No Solution Possible
MyMaze 3
(3,1) (2,1)
MyMaze 4
(2,2) (2,1) (1,1) (1,2) (2,2) (3,2)
MyMaze 5
(2,2) (1,2) (1,1) (2,1) (3,1) (3,2) (2,2) (2,3)
Circle
(2,1) (1,1) (1,2) (2,2) (3,2) (3,1) (2,1)
Robert Abbott's Atlanta Maze
(4,2) (3,2) (2,2) (1,2) (1,3) (1,4) (2,4) (2,3) (2,2) (3,2)
(3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (2,4) (3,4) (3,3) (4,3)
My A.C. program produces the same output with yours.

But I found that the input data may lead you outside the maze and cause R.E. You can check it.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.