Java solver that's a contender for finding N=17

[hidny]

I knew a trick from my futile attempt to solve the challenge in Matt Parker's net folding video. (i.e. 'Can the Same Net Fold into Two Shapes?')
With that trick, I was able to find f(13) = 138457022 in less than 90 minutes. What's nice is that it doesn't have a big memory footprint and it could be distributed between multiple CPUs if needed. As of July 15th, I think the program can solve f(17) in about 8^4 * 90 minutes = 256 days... so maybe under a year? Currently, I'm planning on making it go slightly faster, and then documenting it, and then parallelizing it.

Here's the code:
https://github.com/hidny/MikeTsCubeCode/blob/main/src/NumPolyShapeSolve/DFSPolyCubeCounter.java

[dzamlo]

How do you store the already found polycubes to check if a polycubes is new ?
In my implementation (https://gitlab.com/dzamlo/polycubes), this is the issue, it consumes too much ram and is killed for n=14.

Regarding the speed, on my laptop with 16 threads, I can compute N=13 in less than 19 minutes, but my implementation is already multithreaded.

I also, f(13) = 138462649 not 138457022. See https://oeis.org/A000162 for value up to N=14.

[hidny]

Hi dzamlo,

The key is that I don't store the already found polycubes.

For every polycube I find, I have a function that does a 'race' to figure out if the cube and rotation we're using as a starting point for the polycube results is the 'first' time the polycube would be explored. That may sound impossible, but if you only develop the polycubes in a specific order (like in the order of a deterministic breath-first search), and not randomly,
there's 'only' 24*N different competitors every time you run the 'race'. (24 is the # of symmetries and N is the number of cubes that could act as a starting point.)

The space usage is small ( O(n^3) ) (or lower if I really wanted it be), but the time taken is still exponential.
The time it takes is something like O( A(n) * n * log(n) )

where 'A(n)' is the number of answers which seem to increase exponentially, and n is the number of cubes.

I think I could do some simple changes to squeeze out a bit more performance. I'll make those changes and I'll make more formal documentation as soon as I have time.

Also, thanks for pointing out the error. I think the algorithm is correct and I just copied the number of solutions from the last heartbeat message... :(
I'll rerun to make sure it's the case. I'm sorry about that.

[hidny]

Thanks for reaching out by the way. And if were keeping score, N=13 took me around 28 minutes with the latest optimizations, but I just used a single CPU. Later on, I'll get my algo to be distributed to multiple machines, and get a speed boost that scales with the number of machines.

[dzamlo]

Well done for your work! I think you will flat out beat my implementation when you implement parallel processing.

[dzamlo]

I ported your implementation to rust: https://gitlab.com/dzamlo/polycubes2

It is slightly faster than your implementation (1m24 vs 2m55 for n=12 on my machine)

There is still some not very idiomatic code I need to fix.

[hidny]

I'm impressed! That was fast and the code looks great! Thank you for doing that! I noticed a few changes that I liked. For example, you were sane had the coordinates be x, y, and z, and used vectors instead of only using arrays. I hope that the activity of porting it over taught you what it does and why it does it.
There's two things I wanted to point out though:

1. The reason getNeighbourIndex(Coord3D point, boolean cubesUsed[][][]) looks like this:
   `32 * (cubesUsed[point.a + nudgeBasedOnRotation[0][0]][point.b + nudgeBasedOnRotation[1][0]][point.c + nudgeBasedOnRotation[2][0]] ? 1 : 0)

• 16 * (cubesUsed[point.a + nudgeBasedOnRotation[0][1]][point.b + nudgeBasedOnRotation[1][1]][point.c + nudgeBasedOnRotation[2][1]] ? 1 : 0)...`
  is because I was trying to tell the compiler that it should NOT do branching here. I was told that branching is an expensive operation and the getNeighbourIndex() function gets called a lot of times. Maybe you could try to ask Rust to do arithmetic instead of branching there? (I'm not 100% sure if it will make a difference) You motivated me to try making cubesUsed[][][] a multidimensional int array and check if that's faster. EDIT: The experiment didn't work out for me :(

2. I'm not quite done with the code yet. I'm currently planning on making something that will allow a program to start from any polycube shape at depth 4 (or some small depth d). That way, I could potentially have multiple programs running at the same time, and search different areas of the search space at the same time. But even if I don't add the depth 4 start code, your code seems to be fast enough to find N=17 in under a month... so we're getting there.

[dzamlo]

For you point 1., I tried multiple ways of rewriting it, in ways that should avoid branching, but didn't see a diff in performance. After profiling, I didn't see this function as a hot spot.

[hidny]

Good to know. Sorry to bother you about that.

[hidny]

Apparently, there's more discussions in the open cubes repo. I didn't know that until now.

[dzamlo]

I wasn't aware either, will check it out