### 1. Index Problem

- Posted by petelomax in October
- 531 views

I am trying my hand at implementing walking distance instead of manhattan distance for the 15-puzzle.

(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 base-5 approach would give me an index space of 62,500,000,000 - way too much.

But there are, I think, only 34 sum-4 numbers (0004,0013,..1111,1120,..4000) and 20 sum-3 numbers (0003..3000).

If I use find() [4 times] on a 54-element sequence, the subsequent index space drops to just 8,503,056 - much more reasonable.

My question (finally): is there a better way to convert those sum-4 and sum-3 digits to an index 1..54? 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