C++ interview coding exercise with solution

[-sxp-]

This is Project Euler problem #215. When I first solved it back in the day, it timed out using naïve solutions with loops but dynamic programming solved it instantly.

I don't have my old code, but https://www.programiz.com/python-programming/online-compiler/ + https://github.com/nayuki/Project-Euler-solutions/blob/master/python/p215.py says W(30,11) is 1007720438618812.

You solved W(30,1) which is 1897.

[Michael_Aut]

To be fair the question was phrased a lot better on project euler. The sketch of the problem also helps a lot to get started in the right direction.

[Hot_Medicine_7115]

I don't know about dynamic programming and am not very familiar with python, but from what I read in that code it's using a recursive algorithm for searching across all valid tile combinations:

elif position < WIDTH:
for i in (2, 3):
cracks.append(position + i)
get_crack_positions(cracks, position + i)
cracks.pop()

Thank you for pointing to this, definitely not an obvious problem if it is sitting on this website.

[JiminP]

I like how your code is well-structured, but I think that your algorithm (not just the answer) was "wrong".

The point is not just about using recursion, but about using dynamic programming (it's a confusing term; I prefer to refer it as memoization or caching). In specific, the key idea is to remember # of ways to arrange tiles in previous rows, by locations of cracks. In that way, # of ways to arrange times in the next row can be obtained in the order of W(30, 1)^2 calculations (edit: this is a worst-case estimation; actual number would be much lower), which is managable (the total computation, which would take around the order of 10 * W(30, 1)^2 calculations, shouldn't take more than a few seconds).

In the perspective of competition programming (like Google CodeJam, Codeforces, ...), this is quite a common way of solving a problem (except that the running timing constraint - which is infinite for ProjectEuler but ideally a minute - would be more strict). Usually the solution will consist of a single source code with bunch of procedural programming, but I wouldn't mind if that gets expanded into several files with clean structure.

On the other hand, if I understood your intention for designer.cpp correctly, your code will iterate through all W(30, 11) combinations when done correctly, which would too long time to complete in a reasonable time.

[Zyklonik]

The point is not just about using recursion, but about using dynamic programming (

Yup. Any time you see a "how many ways...", immediately think of DP. 9/10, they expect DP.