How to generate a unique hash key from a vector of integers?

user_7035318 0
Viewed 438

Just for fun, I am trying to implement an A* search for a puzzle solver. I want to keep all states visited so far in an hash. The state is basically a vector of the integers from 0 to 15. (I won't give more information at the moment to not spoil the puzzle.)

(defstruct posn
  "A posn is a pair struct containing two integer for the row/col indices."
  (row 0 :type fixnum)
  (col 0 :type fixnum))

(defstruct state
  "A state contains a vector and a posn describing the position of the empty slot."
  (matrix '#(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0) :type simple-vector)
  (empty-slot (make-posn :row 3 :col 3) :type posn))

Because it seems that I have to check some 100.000s of states I thought It would be more efficient to generate some number as a hash key instead of using the state directly and need to check using equal each time.

I started with

(defun gen-hash-key (state)
  "Returns a unique(?) but simple hash key for STATE which is used for tracking
if the STATE was already visited."
  (loop
     with matrix = (state-matrix state)
     for i from 1
     for e across matrix
     summing (* i e)))

but had to learn that this does not lead to really unique hash keys. E.g. the vectors '#(14 1 4 6 15 11 7 12 9 10 3 0 13 8 5 2)) and '#(15 14 1 6 9 0 4 12 10 11 7 3 13 8 5 2)) will both lead to 940 causing the A* search to miss states and therefore spoiling my whole idea.

Before I continue in my amateurish way to tweak the calculation, I wanted to ask if someone could point me to a way to generate real unique keys in an efficient way? I lack the formal CS education to know if there is a standard way to generate such keys.

common-lisp hash
2 Answers

You don't need to create some special hash key: the language will do it for you!

In particular equalp has the behaviour you want on arrays and structures.

For arrays:

If two arrays have the same number of dimensions, the dimensions match, and the corresponding active elements are equalp. The types for which the arrays are specialized need not match; for example, a string and a general array that happens to contain the same characters are equalp. Because equalp performs element-by-element comparisons of strings and ignores the case of characters, case distinctions are ignored when equalp compares strings.

and for structures:

If two structures S1 and S2 have the same class and the value of each slot in S1 is the same under equalp as the value of the corresponding slot in S2.

And equalp is one of the available test functions for make-hash-table, which means that you can make hash-tables for which your state structures will hash correctly.

Admin1

16 integers whose values ranges from 0 to 15 can be represented by a 64 bit integer: 64 bits divided by 16 means 4 bits per number, and (expt 2 4) is 16. For example:

CL-USER> #(14 1 4 6 15 11 7 12 9 10 3 0 13 8 5 2)
#(14 1 4 6 15 11 7 12 9 10 3 0 13 8 5 2)

CL-USER> (loop
        for c across *
        for i = 1 then (* i 16)
          sum (* i c))
2705822978855101470

With the second vector:

CL-USER> #(15 14 1 6 9 0 4 12 10 11 7 3 13 8 5 2)
#(15 14 1 6 9 0 4 12 10 11 7 3 13 8 5 2)

CL-USER> (loop
        for c across *
        for i = 1 then (* i 16)
          sum (* i c))
2705880226411930095

You can also precompute all factors:

CL-USER> (coerce (loop for i = 1 then (* i 16) repeat 16 collect i) 'vector)
#(1 16 256 4096 65536 1048576 16777216 268435456 4294967296 68719476736
  1099511627776 17592186044416 281474976710656 4503599627370496
  72057594037927936 1152921504606846976)

I am not sure how much you gain from this. Note that if you spend a lot of time converting from numbers to vectors, the benefit of not hashing with equal might be outweight by the cost of computing those hashes.

user_1243190
Related