A Fun Puzzle

Normally I enjoy puzzles in games. Yesterday while playing Pathfinder: Kingmaker, a CRPG, I was presented with a maddening puzzle. Maybe it wasn’t so maddening, I just felt an itch to solve it with a program. Also, I hadn’t gotten to do much Clojure lately, and that surely was an incentive.

This also had the feeling of an Euler problem or interview challenge.

The Puzzle

In the game, there were six candles laid out in a circle. Some candles were lit, some were not. The objective is to snuff all of the candles. As you snuff an individual candle, it toggles one or two other candles. Six candles, some button mashing, how hard could it be?

You can see the puzzle in action below. While it’s easy to produce, here is the key of effects:

If you press #1, it and #3 will toggle.

• #1 ==> #3
• #2 ==> #4, #5
• #3 ==> #1, #5
• #4 ==> #2, #6
• #5 ==> #2, #3
• #6 ==> #4

My Solution

Knowing there were only 6 candles, I knew I wouldn’t be constrained by complexity. My solution is a simple breadth-first-search style algorithm, but try to build your own!

(def data [:off :off :on :off :off :on])

(defn toggle-pos
  [data pos]
  (if (= :off (get data pos))
    (assoc data pos :on)
    (assoc data pos :off)))

(defn toggle-multi
  [data & xs]
  (reduce toggle-pos data xs))

(def ops [[0 3]
          [1 3 4]
          [2 0 4]
          [3 1 5]
          [4 1 2]
          [5 3]])


(defn success?
  [data]
  (= [:off :off :off :off :off :off] data))

(defn potentials
  [moves data]
  (map-indexed
   (fn [idx op]
     [(conj moves idx) (apply toggle-multi data op)])
   ops))

(defn solve
  [data]
  (loop [q [[[] data]]]
    (let [[[moves data] & xs] q]
      (if (success? data)
        (map inc moves)
        (recur (concat
                xs
                (potentials moves data)))))))