I see a lot of submitted solutions that use the heuristic of going to whichever adjacent vertex has the most untraveled edges remaining. I'm pretty sure solutions based on this heuristic would fail for the following input set:

{
(0, 0, 0, 1),
(1, 0, 0, 0),
(1, 0, 0, 1),
(1, 0, 3, 0),
(3, 0, 4, 0),
(3, 0, 4, 1),
(4, 0, 4, 1),
}

which basically looks like this:

(0,1) (4,1)
| \ / |
| \ / |
(0,0)--(1,0)--(3,0)--(4,0)

In this case, the submitted solutions would start at (1,0) or (3,0) because they had odd degree, then would travel to (3,0) or (1,0) because that is the adjacent vertex with the highest number of untraveled edges remaining, but that is a bad move that leaves you stranded.

There is an existing test case (fifth test case in the Extra set) that looks similar, but basically has an extra vertex between (1,0) and (3,0), allowing the heuristic to work.

I'd like to recommend adding the test input as described above. I think all would have to be done is add the following lines to tests.py:

{
"input": [(0, 0, 0, 1), (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 3, 0),
(3, 0, 4, 0), (3, 0, 4, 1), (4, 0, 4, 1)],
"answer":[(0, 0, 0, 1), (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 3, 0),
(3, 0, 4, 0), (3, 0, 4, 1), (4, 0, 4, 1)],
}

Created at: 2015/07/24 21:54; Updated at: 2016/08/11 11:41