Problem 208

[LarryC]

I think I have the right algorithm but I get more than 4 times what is shown for 25 arcs. I think there may be some rules regarding repeating paths but I am not sure of them so I would ask you to clarify!

For 25 arcs would an acceptable path be going round in a circle 5 times? That features twenty five arcs but is that counted as a path?

Thanks,
Lster

[stijn263]

Yes, that is counted as a path.

It's quite a difficult problem imo. I found a correct algorithm after about 50 minutes, but unfortunately it only works for up to 40 arcs. 45 arcs would take over an hour..

[ed_r]

It is supposed to be a tricky problem, so I was astonished when Doraki solved it within nine minutes!

[LarryC]

I'll keep looking. Thanks for the confirmation guys!

[LarryC]

Done! That was hard...

[stijn263]

Still working on it. Trying to find a closed form formula now, since I can't get my head around my algorithm any more..

[quilan]

It is supposed to be a tricky problem, so I was astonished when Doraki solved it within nine minutes!

Perhaps. It looked extremely difficult when I first saw it, but once the light-bulb blinked, even making an extremely naive & non-analytical method I was able to bang out an algorithm for it in about 10 minutes. I just started late in the day.

[LarryC]

I had the same experience as you then, I think. I had a lesson at my college that ended shortly after 1:35pm and so before walking home I had a quick look at the problem on a school computer. I couldn't really get my head round it until I started coding a naive algorithm (which was wrong). I realized it must be almost right so I recoded it to not be so naive... And then I noticed my error. It only took 15 more minutes...

[Zoinks]

Another clarification request..

Can you confirm whether the phrase "starting position" refers only to the location of the robot, or does it also include the orientation -- i.e. must be facing North.

I clearly haven't burned enough brain cells on this yet... PC is currently brute-forcing it, just wanted to confirm the rules for my result-checking program.

[hk]

A position is a position and says nothing about a heading.

[koenvdd]

I've almost got this program nicked, I've already got the right results for 25 and 5 arc, and I think correct for 10 arcs, but project Euler doesn't want to accept my answer for 70 arcs. Finding the answer takes only a few seconds, but big fat squat does that help me if the answer isn't correct. Could someone who's algorithm works give the answers for every multiple of 5 upto but EXCLUDING 70 (ofcourse you shouldn't give the answer away). Pleaaaase, I'm asking this with the biggest puppy eyes, because I actually should be studying but I know my mind won't lay it to rest until it is solved.
I am partly in a run before you can walk situation because I currently only solved the first 10 problems as well as problem 202 (that was my first), but I'm now so close to the solution, so please, be compassionate with my grades and give the examples so I can try and find where my algorithm goes wrong, it just compute but wrongly.

[Georg]

Could someone who's algorithm works give the answers for every multiple of 5 upto but EXCLUDING 70 (ofcourse you shouldn't give the answer away)

No, but you could send your results to me via PM.

[Georg]

Your 1st incorrect result is for 40 arcs.

[koenvdd]

Thanks, also, am I to high or to low?

[Georg]

You are to high.

[Mike]

I thought I'd solved this at last but evidently my answer for 70 arcs is wrong,
though correct for 25.

So - are identical-looking paths sometimes distinct or not? For instance,
for 10 arcs, is a clockwise circle (CW) followed by an anti-clockwise (AC)
circle, with the Northerly starting point in common, distinct from an
AC circle followed by a CW circle?

It would help if the statement of the problem included numbers of paths
for 5 and 10 arcs as well as 25 .

[harryh]

When you obtained the correct solution for 25 arcs, did you assume that
[3 CW circles followed by 2 AC circles] and [2 AC circles followed by 3 CW circles]
count as different solutions ?
That should give you the answer to what you ask...

[Mike]

Thanks. No surprises when it turned out my problem was with precision
and rounding errors, and not with logic after all.

[Mannion]

Hi I am having trouble finding the correct answer like previous posters. I got the algorithm producing the correct results for 25 arcs fairly easily and then managed to speed up the calculation for 70 arcs from several minutes ??? down to less than a second. Now I realise that my answer for 70 is not correct. I am assuming that any unique set of turns is a unique route. ie

LLLLLRRRRRLLLLLRRRRR is different from
RRRRRLLLLLRRRRRLLLLL

Any help would be greatly appreciated.

[Mannion]

OK I've nailed it. The clue was in the earlier posts. Don't worry about orientation. I think it was slightly ambiguous though. Fantastic problem nonetheless, I've learned a few new tricks deriving it all from scratch. I think I will go back to the easy problems on page 1 for a while now.