January 27, 2009 at 5:36 pm
· Filed under Uncategorized

I’m sure this information is available elsewhere, but I couldn’t find it with a quick google search — the two hardest 8-puzzle instances are:

8 6 7
2 5 4
3 . 1
6 4 7
8 5 .
3 2 1

Both require at least 31 moves to solve. All other instances can be solved in 30 moves or less. (Found using breadth-first graph search, starting at the goal state). Somewhat interestingly, they are not obviously symmetric, but differ only in the locations of the even pieces.

Permalink

January 20, 2009 at 4:01 pm
· Filed under Clojure

If you’re using Clojure’s built-in set operations, clojure.set/union/intersection/difference, you should be aware that their speed currently depends (sometimes dramatically) on the order of the arguments given. And, since clojure.set/difference is not commutative, it is simply needlessly slow if the second set is larger than the first.

… [truncated] …

**Update **: This post is no longer relevant, since my faster (+ multi-argument) versions are now included in clojure.set.

Permalink

January 7, 2009 at 2:03 pm
· Filed under Clojure, Java

For some applications, it could be desirable to compute java.util.List hashCode()s backwards, recursively from back to front, rather than front-to-back as defined in the API [1]. For instance, in Clojure this would enable computing the hash values for all of the rests of a seq for free while computing its hash value. This requires just a tiny bit of math and understanding of modular arithmetic. Clojure code showing how this can be done follows.

[1] http://java.sun.com/j2se/1.4.2/docs/api/java/util/List.html#hashCode()

(defn forward-hash "How hashCode() is defined in java.util.List" [s]
(loop [s (seq s) h (int 1)]
(if s
(recur (rest s) (int (unchecked-add (unchecked-multiply h 31) (hash (first s)))))
h)))
(def int-pow
(memoize
(fn [x n]
(let [x (int x) n (int n)]
(cond (zero? n) 1
(even? n) (let [h (int-pow x (/ n 2))] (unchecked-multiply h h))
:else (unchecked-multiply x (int-pow x (dec n))))))))
(defn backward-hash "Compute the same value as forward-hash, but back-to-front." [s]
(let [s (seq s) p (int-pow 31 (count (rest s)))]
(if s
(unchecked-add (unchecked-multiply 30 p)
(unchecked-add (int (backward-hash (rest s)))
(unchecked-multiply (int (hash (first s))) p)))
1)))
user> (map #(% (vec (range 1000))) [forward-hash backward-hash #(.hashCode %)])
(133786869 133786869 133786869)

**Update:** I posted this on the Clojure issue page here. Note a small caveat there: it is not allowed by Java that (.equals [] (seq [])), so Clojure collections and seqs cannot be comparable in general. However, everything carries through for non-empty seqs and collections.

Permalink