stbrumme / euler Goto Github PK

I tried this solution for Hackerrank Project Euler Problem 218. But it fails for hidden test cases.

Hello, I like to read your solutions (in 99% of cases after I finish some Euler problem myself , although I used it once to get me a bit unstuck on general idea), to compare and learn new ways.

With #313 I see I can share the other way, hope you don't mind opening github issue for this, it's easiest way for me to contact you and open the discussion.

My approach was opening spreadsheet and drawing few sliding game boards first to find:

1. initial MxN board requires M+N-3 steps to provide empty space next to red counter (from either right or bottom)
2. 2x2 to solve with empty space next to red counter is 4 moves diagonal move (so whole 2x2 is 2+2-3+4 = 5)
3. if red counter is next to bottom right square which is empty, it takes +1 move to finish the game
4. to move red counter diagonally and restore the free space next to it it takes 6 moves (free space can be bottom or right, same orientation is restored)
5. to move red counter vertically/horizontally and restore the free space it takes 5 moves

These should be reasonably easy to verify by "eyeballing" small area of board in spreadsheet and trying to do the moves, and the rules 4. and 5. can be applied after each other due to preserving free square position, and 2. and 3. can be applied after either 4. or 5. once the bottom right corner of board is in reach.

Now I did a bit of leap of faith and claim that these rules can be applied to get optimal amount of moves (I think it's reasonably visible why this works intuitively, but I don't think I would be capable to produce math-quality proof of it).

• for any NxN (square) board this makes the total moves:
  S(n,n) = (n + n - 3) + (n - 2) * 6 + 4 using rules: 1. to move free space (does not matter if free space is right or bottom), 4. to move n-2 times diagonally into 2x2 ending position, and 2. to finish the game from 2x2
  This can be reduced to moves = 8n - 11
• for MxN board, assume N < M (rotate board if needed), the rules can be applied like this:
  S(m,n) = (m + n - 3) + (n - 1) * 6 + (m - n - 1) * 5 + 1 using rules 1., 4., 5. and 3. In 1. the free space is moved to the longer side of board, then diagonal movement is applied until red counter is at exit square row/column, then vertical/horizontal movement is applied until it is next to it, then the +1 finish game rule is used.
  This can be reduced to moves = 6m + 2n - 13

At this point I got next idea, to reverse the formulas, ie. calculate all [m,n] (or amount of them) for particular moves value, and after a while of playing with those formulas I got inverse formulas:

• for NxN square board the only N = (moves + 11) / 8, if divisible (moves % 8 == 5), otherwise no N exists
  (after reading through problem forum I was reminded the prime^2 will never hit this case, because that would require (p % 8)(p % 8) == 5 and there's no such (p % 8) to produce 5 after square, so actually there's never square board in the set of boards for p^2 moves.

• for MxN board I calculate first value X = (moves + 13) / 2 -> if not divisible by 2, there's no [M,N]
  min_m = ceil(X / 4) => int min_m = (x + 3) / 4; - to ensure n < m
  max_m = floor((X - 2) / 3) => int max_m = (x - 2) / 3; to ensure 2 <= n
  Then for each min_m ... max_m the n can be calculated as n = x - 3m, but that's not the point of the task, it is enough to count solutions: return 2 * (max_m - min_m + 1); ... 2x for both MxN and NxM boards.

Then the final code uses my primes class to generate all primes <= 1e6, and goes through them summing amounts of boards for each p^2, which takes about 0.03s on my machine to produce the final answer.

(I hope this finds you well and you could enjoy the read - at least as much as I enjoyed your blog so far. If you want to adjust your article to describe this approach, you are free to use/adjust this as you see fit, have a good time :) )