Warning: ob_start(): non-static method wpGoogleAnalytics::get_links() should not be called statically in /home/w01fe/w01fe.com/wordpress/wp-content/plugins/wp-google-analytics/wp-google-analytics.php on line 259
A Blog. » 2009 » January

Archive for January, 2009

The hardest eight-puzzle instances take 31 moves to solve

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.

Comments (6)

Efficiency of Clojure’s built-in set operations

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.

Comments

Computing java.util.List hashCode()s back-to-front

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.

Comments