forummsgid131441edit
Original date:20171012 09:40:13 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 only, see this page.)
In short, you count the number of tiles in each row (and column, but ignore that) vs. goal position, 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 again you can completely ignore that part) adds 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,0013,..1111,1120,..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 (finally): 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
