Historical forummsgid131441edit, Revision 1
Original date:20171011 23:26:42 Edited by: petelomax Subject: Index Problem
I am trying my hand at implementing walking distance instead of manhattan distance for the 15puzzle.
(For the terminally curious, see the post by stannic 2/3 of the way down on this page.)
In short, you count the number of tiles in each row and column, eg:
1 2 3 0 5 6 7 8 9 10 11 12 13 14 15 4 Row 1 contains 3 tiles from row 1. Row 2 contains 4 tiles from row 2. Row 3 contains 4 tiles from row 3. Row 4 contains 1 tile from row 1 and 3 tiles from row 4.
and the (horizontal) "key" is therefore
3 0 0 0 0 4 0 0 0 0 4 0 1 0 0 3
Each line (and column, but you can completely ignore that part) will add up to 3 or 4.
A naive base5 approach would give me an index space of 62,500,000,000  way too much.
But there are, I think, only 32 sum4 numbers (0004 to 4000) and 19 sum3 numbers (0003..3000).
If I use find() [4 times] on a 51element sequence, the subsequent index space drops to just 6,765,201  much more reasonable.
My question: is there a better way to convert those sum4 and sum3 digits to an index 1..51? Or something not drastically larger (unlike the 3..500 that base 5 gives me).
I should mention that with 24,964 tables a dictionary based approach is also quite feasible, but I suspect a plain old sequence subscript would be at least 10x faster.
Pete
Not Categorized, Please Help

 diff to current revision, view current revision history, backlinks
 Last modified 2 months ago by petelomax