; PitcherProblemSolver - CSLS v1, Chapter 14, Solving Pitcher Problems
; --------------------

; Global Data
; ------ ----

; initially empty, set to a solution node when one is found
global "solution

; the amount of water desired in a pitcher
global "desiredAmount

; sentence containing the sizes of the provided pitchers
global "pitcherSizes

; Common General Procedures
; ------ ------- ----------

; Output the number of pitchers in the current challenge
to numPitchers
  output count :pitcherSizes

; Tree Walking Stuff
; ---- ------- -----

; Two algorithms are provided which iterate through all nodes of a
; tree: depthFirst and breadthFirst.
; Each of these procedures expects two procedures to exist
; (1) processNode - invoked for every node of the tree
;                   one input, a node
; (2) childNodes - invoked to get a list of child nodes for a node
;                  one input, a node

; ...

; perform a breadthFirst traversal of a tree
; the procedure processNode is invoked for each node in the tree
; the function childNodes, which has one input :node, should output
;                          a list of the :node's children
; :node should contain the root node of the tree
to breadthFirst :node
  breadthFirstHelper (list :node)

; :queue is a list of nodes to be processed
; for every member of the queue, from first to last, the first
; node from :queue is passed to two procedures (processNode
; and childNodes) as an input.
; processNode checks to see if its input :node, a pouring data
; structure, has a pitcher with the desired amount. If so,
; global variable solution is set to the node.
; childNodes outputs a list of nodes that are children of the
; input node. These nodes are appended to :queue to be
; processed later.
to breadthFirstHelper :queue
  if empty? :queue [stop]
  processNode first :queue
  if not empty? :solution [stop]
  breadthFirstHelperHelper (childNodes first :queue)
  breadthFirstHelper butfirst :queue

; Append the new child nodes onto :queue 
to breadthFirstHelperHelper :childNodeList
  if empty? :childNodeList [stop]
  make "queue lput (first :childNodeList) :queue

; Data Structures
; ---- ----------
; A pouring is a list
;  - Its first member is a sentence with two numbers, the
;    source-destination-pair (srcDestPair) of the pouring
;  - Its butfirst members are the resultant pitcher state values,
;    the amount of water in each pitcher, a number for each pitcher  
; Output the source-destination-pair (srcDestPair) sentence
; for the input :pouring 
to getSrcDestPair :pouring
  output first :pouring

; Output a sentence of all the pitcher states (volumes) for
; the input :pouring
to getPitcherStates :pouring
  output butfirst :pouring

; Output a root node for a tree which will be built containing
; permutations (nodes) that could lead to or be a solution to
; the current pitcher pouring challenge. It consists of a list
; with an empty source-destination pair and zeros for the
; contents of pitchers.
to rootNode
  localmake "pitchersState []
  repeat numPitchers [make "pitchersState fput 0 :pitchersState]
  output fput [] :pitchersState

; Support for the tree traversal framework. Given a :node as input,
; output a list of the children of that node.
; This implementation of childNodes supports a search for a pitcher
; with (global variable) :desiredAmount of water. The list of child
; nodes output consists of all permutations of source and destination
; pairings (srcDestPairs) and the resultant pitcher states for them.
; Only child nodes (pourings) that make sense to check as a possible
; solution are included, e.g., a pouring where source = destination
; makes no sense...
; Note: childNodesHelper and childNodesHelperHelper take advantage
; of Logo's dynamic scope, e.g., :node is an input to childNodes and
; is referenced in childNodesHelperHelper

; output a list of child nodes for the given :node
to childNodes :node
  output []

; Check :node to see if one of the pitchers has the desired amount
; If found, set the global variable "solution to the node
to processNode :node
  ;print "|processNode | show :node
  if member? :desiredAmount (getPitcherStates :node) [make "solution :node]

; Print the solution as a list of pouring steps, e.g.,
;    Pour from the river to pitcher #2 (0/3 7/7)
;    Pour from pitcher #2 to pitcher #1 (3/3 4/7)
; and the pitcher with the solution
;    Pitcher #2 contains 4 units
to printSolution

; Initialization
; Get problem information from the user, the available pitcher sizes and
; the target amount of water desired in one

; Output a sentence containing sizes of available pitchers
to getPitcherSizes
  print [Enter sizes of pitchers (e.g. 2 5):\ ]
  output readlist

; Output a word, a number, that is the desired amount of water
to getDesiredAmt
  print [Enter desired amount in a pitcher:\ ]
  output readword

; ----
to main
  make "solution "null
  make "pitcherSizes getPitcherSizes
  make "desiredAmount getDesiredAmt
  breadthFirst rootNode
  ifelse empty? :solution [println [There is no solution!]] [printSolution]