Intel's Ronler Acres Plant

Silicon Forest
If the type is too small, Ctrl+ is your friend

Sunday, October 25, 2020

Cube Puzzle Solver Port-Mortem

Number of times search was blocked by level.

I modified my cube solver program to keep track of the number of times a search at each level failed. There are ten pieces to the puzzle, so we search at ten different levels, one level for each piece. The graph shows the number of times the search of all possible positions at that level did not find a single one that could hold the selected piece.

Levels 0 thru 4 don't even register above the X axis at this scale. Including them made the key confusing, there wasn't enough differentiation in the colors, so I didn't include them. Level 5 shows a flat line even though it has counts consistently above 10 billion (10^10). I included it just to give you an idea of the scale we are working with.

The program printed this data to stderr, which by default goes to the terminal screen. Copy and paste that into the text editor and then replace all instances of multiple spaces with a single tab. (Start with the longest sequence of spaces you can find and then work backwards.) The formatting is lost, but now you can copy and paste that into a spreadsheet and our formatting is restored.

I did some calculations in the spreadsheet to see how many comparison tests we avoided and came up with about 4.5 quadrillion, which is a very large number, but still nowhere near the value of 

12 * (3*96)^4 * (4*96)^5 = 6.8929848e+23

which is what I expected. So there is something wrong with my calculations somewhere.

P.S. Something weird happened when I pasted the text into the spreadsheet. I got a bunch of lines consisting of the single word #ERROR! I looked in my source code, but couldn't find it, and I just looked in the text file and it's not there either, so I think Google Sheets must have found something it didn't like (like a line of 300 periods) and complained. No problem, simple sort the file and all the ugly stuff you aren't interested in gets lumped together and can easily to erased.

P.P.S. One trick I use when dealing with large quantities of data is to insert a column along the left hand edge, a new column A if you will, and then number all of the lines with sequential numbers. You can easily do this by typing 1 in box A1, and then =A1+1 in box A2. Copy box A2, select all the rest of column A from A3 to the end paste. Now all the lines are numbered sequentially. However, you are not quite done. If you sort the sheet now, all the values in column A will be recomputed and your original order will be lost. So what you do is copy column A and the Paste Special -> Values Only back over it. Now you have an indelible original order. Sort however you like, but you can restore the original order by sorting on Column A.


No comments: