For the first part of my attempt at solving problem 26 see Problem 26 Part 1.
I could see where my current method was failing me, some of the repeating cycles had a non-repeated chunk of numbers at the start. 1/6 is a good example:
1/6 = 0.166666666.....
So I should treat this as a number with a cycle of 1 but instead no repetition is found and my cycleSize() method overflows some of its numbers and returns 0 when it flows into a number divisible by 6.
I can ignore leading numbers in a similar way to above but I have no way of telling how many numbers I should ignore before giving up. As an example:
1/6 = 0.166666...
10*1/6 = 1.66666...
(10*1/6)*(10-1) = 15
The (10-1) part tells me that there is a cycle of one number and the (10*1/6) tells me that I've ignored one number from the beginning. Here are some more complicated examples to compare:
1/24 = 0.04166666...
1000*1/24 = 41.666666...
(1000*1/24)*(10-1) = 375 (ie. ignore 3 numbers, cycle of 1)
1/420 = 0.00(238095)
100*1/420 = 0.(238095)
(100*1/420)*(1000000-1) = 238095 (ie. ignore 2 numbers, cycle of 6)
So implementable for sure but I have two different numbers to increment now and I don't know before hand which number to increment first. A depth first search of the possible solutions is not going to work (they go on to infinity) so breadth first it is!
A new and improved version of the solution is here:
And tests can be found here:
All but one of the tests pass. The failing test reports that 1/49 should have a cycle of 42 but my method says that it's 14. Some digging reveals that the answer 14 was gained when testing 1/49 with 3 ignored numbers and 14 in the cycle. Wolfram Alpha tells me that my method is simply reporting the wrong value. I think that the problem I'm having here is one of overflow again. ((10^3)*(10^14-1)) is a rather large number. To combat this I'm going to have to use BigInteger. This will slow down the arithmetic but should give all correct answers:
This passes all the tests (good news) and gives the correct answer (good news) but takes 69 seconds (bad news). I know that more efficient methods to solve this problem are out there (I've found some of them) but for tonight I think I'll leave it at that.
If there are other people reading this then let me know if you have ideas or if my explanations are lacking.
No comments:
Post a Comment