Water pouring challenge

I'm trying to write code to solve water pouring problem in Clojure. The following code is strongly influenced by Martin Odersky's solution lectured in his coursera course, Functional Programming Principle in Scala. He first created a class Pouring with parameter capacity, which is accessible everywhere in the class. Though he made the best use of case class in his solution, I just used plain clojure map to represent the moves.

I tried to solve the problem in the same way, and end up with the following code:

```
(ns pouring)

(declare capacity init-state)

(defn empty [state glass]
(assoc state glass 0))

(defn fill [state glass]
(assoc state glass (capacity glass)))

(defn pour [state [from to]]
(let [amt (min (state from) (- (capacity to) (state to)))]
(-> state
(assoc from (- (state from) amt))
(assoc to (+ (state to) amt)))))

(defn change [state move]
(if state
(cond (:empty move) (empty state (:empty move))
(:fill move) (fill state (:fill move))
(:pour move) (pour state (:pour move)))
(change init-state move)))

(defn moves [capacity]
(let [glasses (range (count capacity))]
(lazy-cat
(map (fn [g] {:empty g}) glasses)
(map (fn [g] {:fill g}) glasses)
(for [from glasses, to glasses :when (not= from to)]
{:pour [from to]}))))

(defn extend-path [path move]
{:history (conj (:history path) move)
:end-state (change (:end-state path) move)})

(defn extend
([paths explored]
(if-let [more (for [path paths
next-path (map #(extend-path path %) (moves capacity))
:when (not (contains? explored (:end-state next-path)))]
next-path)]
(lazy-cat paths (extend more (conj explored (map #(:end-state %) more))))))
([] (extend #{{:history [], :end-state init-state}} #{init-state})))

(defn init [c]
(def capacity c)
(def init-state (vec (repeat (count c) 0))))

(defn solve [capacity target]
(init capacity)
(

Warning: The following is opinionated at times. At other times it is more opinionated.
Channeling PG

I've heard on the internet so it must be true, that Paul Graham will get right to the point when interviewing applicants to Y-Combinator with "What problem does this solve?" It's hard to understand code without understanding what it is supposed to do. And only Google and watching a video twice make me think I might. Since I still don't understand the code though, I can't tell whether it solves the problem or not.

The "water pouring problem" is a canonical toy problem in programming curricula. Wolfram Mathworld describes it as a special case of the three jugs problem. The special case is where the third jug:

capacity = +infinity
   contents = +infinity

The infinite capacity of the third jug allows it to represent a sink into which the contents of the other jugs may be emptied. The infinite contents allows the third jug to represent a faucet for filling other jugs.

The problem Ordersky presents is none of these. It is a generalized case based on a Python example from Peter Norvig's Design of Computer Programs course at Udacity. The problem Odersky is solving has an arbitrary number of jugs with finite capacity plus one jug with infinite capacity and contents. I would like to dub this the "n+1 Jugs Problem" because 1 captures the sink/faucet and n+1 hints at the notion of +infinity [at least in my little world].
Readability

A joke: I married my wife despite her adamant unwillingness to change her name. What's the big deal about being called "Donna" to match my tattoo?

Rich Hickey invented Clojure to help working programmers write good programs, not to give the world another excuse for tribal tattoos. I don't think init or def inside a function are big deals. They're very Pythonic and they couldn't make the code less readable for idiots like me.
Chiapas

I found the code opaque. "What is state?" I asked myself. I could look at the code for hours and never really figure it out. It took a half hour of concerted effort involving Google and watching a video of Martin Odersky...twice before I came up with a good answer: state is a vector of integers. In Ordersky's code this is explicit at line 6:

type State = Vector[Int]

That's just standard Scala. It's fast in the sense that many people will understand it as soon as they read it. The Clojure implementation, on the other hand, is really slow because the source code doesn't make the nature of state clear. A [more opinionated][more opinionated] approach might be:

;;;; The state is a vector of integers.
 ;;;; Each element represents a glass.
 ;;;; The value of each element represents the contents of the glass.

A more direct implementation of the Scala code might use int-array for both state and glasses. There's nothing wrong with using types to make writing correct clear performant code easier.
Recommendations

Think about how much effort Odersky invests in making his code understandable. There's thirty minutes of video. There's the hours of video that come before it in the course sequence. The coding session starts with diagrams explaining the problem. Those are habits that are worth emulating. Following what Clojurists on the internet espouse doesn't make one an expert [I am aware of the irony]. Clojure is the product of Hammock Driven Development.
Extension

I'm a big fan of Lamport's idea specification as the starting point. One of the issues with Odersky's generalized approach is that it doesn't quickly trim the search space. Consider the case with two glasses:

(def capacity  { :a 1
                  :b 100})
 (def target  50)           ; edit: early version used 99

The solution exists in the 99th layer of Odersky's onion because it requires 99 moves. With two glasses There are only six transition operations at each level of the onion:

; empty a
 ; empty b
 ; pour from a to b
 ; pour from b to a
 ; fill a
 ; fil  b

Yet the brute force search would cover:

level | paths
 ------|-------
 1     |  2
 2     |  12
 3     |  72
 4     |  432
 ...   |  ...
 99    |  3.6295479083337274E76 = (6^99)/3

At an arbitrary iteration some may lead to states already visited and Odersky's approach trims those. What it doesn't do is capture the semantics of bags to trim the search space. Consider:

(def capacity  { :a 1
                  :b 100
                  :c 1
                  :d 1
                  :e 1
                  :f 1})
 (def target  50)           ; edit: early version used 99

Many of the (Math/pow 42 99) states turn out to be equivalent and finding these equivalences would greatly reduce the search space and make for a more performant algorithm. For the purposes of Odersky's course [promoting Scala and functional programming] looking at algorithmic improvements is outside the mandate. For general code such as that under open review, it really isn't.

StackExchange Code Review Q#80320, answer score: 5