The wolf, the goat, and the cabbage

turtles-own [
  speed   ;; agent speed in cells per tick
  goal    ;; goal list
  carrier ;; agent carrying this agent (or "nobody")
]

globals [
  wolf
  goat
  cabbage
  man
  boat
  verbose? ;; if true, agents print what they are doing 
  bank     ;; location of river bank (+ or -)
]

to setup
  clear-all
  set bank 13
  set verbose? true
  ask patches with [ pxcor <= (- bank) or pxcor >= bank ] [set pcolor green ]
  ask patches with [ pxcor > (- bank) and pxcor < bank ] [set pcolor blue ]
  
  crt 5 [ setxy (bank + 3) 0
    set speed 0.01
    set size 3
    set carrier nobody
    set goal [ ] ]
  
  set wolf (turtle 0)
  set goat (turtle 1)
  set cabbage (turtle 2)
  set man (turtle 3)
  set boat (turtle 4)
  
  let labels [ "wolf" "goat" "cabbage" "man" "boat" ]
  ask turtles [ set label (item who labels) ]
  
  ask man [ set shape "person"
    set size 4
    set goal wgc-plan
    set color red ]

  ask cabbage [ set shape "plant"
    set carrier man
    set color 53 ]

  ask boat [ set size 5
    set xcor (bank - 1)
    set speed (speed * 2)
    set color brown ]

  ask goat [ set shape "cow"
    set goal (list "eat" cabbage)
    set carrier man
    set color white ]

  ask wolf [ set shape "wolf"
    set goal (list "eat" goat)
    set carrier man
    set color black ]
  
  reset-ticks
end 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; NetLogo code for obeying instructions ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to obey
  if (carrier != nobody) [
    move-to carrier
  ]
  if (goal != []) [
    let kind (item 0 goal)

    if-else (kind = "goto") [ if (obey-goto (item 1 goal) (item 2 goal)) [ drop3-goal ] ] [

    if-else (kind = "meet") [ if (obey-meet (item 1 goal)) [ drop2-goal ] ] [

    if-else (kind = "eat") [ if (obey-eat (item 1 goal)) [ drop2-goal ] ] [

    if-else (kind = "pickup") [ obey-pickup (item 1 goal)
                                drop2-goal ] [

    if-else (kind = "wait") [ if (runresult (item 1 goal)) [ drop2-goal ] ] [

    if-else (kind = "drop") [ obey-drop (item 1 goal)
                              drop2-goal ] [

    if-else (kind = "instruct") [ obey-instruct (item 1 goal) (item 2 goal)
                                  drop3-goal ] [

    if-else (kind = "go-left") [ obey-go-left ] [

    if-else (kind = "go-right") [ obey-go-right ] [

    if-else (kind = "embark") [ obey-embark
                                drop-goal ] [

    if-else (kind = "disembark") [ obey-disembark
                                   drop-goal ] [

    obey-unknown kind ] ] ] ] ] ] ] ] ] ] ] ]
end 

to drop-goal
  set goal (bf goal)
end 

to drop2-goal
  set goal (bf (bf goal))
end 

to drop3-goal
  set goal (bf (bf (bf goal)))
end 

to obey-unknown [ g ]
  show (list "unknown goal" g)
  drop-goal
end 

to-report at-left
  report xcor = (1 - bank)
end 

to-report at-right
  report xcor = (bank - 1)
end 

to obey-go-left
  if (verbose?) [ show (list "going left") ]
  let g (list "goto" (1 - bank) 0)
  set goal (sentence (list "meet" boat "embark" "instruct" boat g "wait" (task at-left) "disembark" "goto" (- (bank + 3)) 0) (bf goal))
end 

to obey-go-right
  if (verbose?) [ show (list "going right") ]
  let g (list "goto" (bank - 1) 0)
  set goal (sentence (list "meet" boat "embark" "instruct" boat g "wait" (task at-right) "disembark" "goto" (bank + 3) 0) (bf goal))
end 

to obey-disembark
  if (verbose?) [ show (list "disembarking") ]
  set carrier nobody
end 

to obey-embark
  if (verbose?) [ show (list "embarking") ]
  set carrier boat
end 

to obey-pickup [ him ]
  ask him [ set carrier myself ]
  if (verbose?) [ show (list "picking up" ([label] of him)) ]
end 

to obey-drop [ him ]
  if-else ([ carrier ] of him = self)
    [ ask him [ set carrier nobody ]
      if (verbose?) [ show (list "dropping" ([label] of him)) ] ]
    [ show (list "CANNOT DROP" ([label] of him)) ]
end 

to obey-instruct [ him g ]
  if-else (g = [])
    [ ask him [ set goal [] ] ]
    [ ask him [ set goal (sentence goal g) ] ]
  if (verbose?) [ show (list "instructing" ([label] of him) "to" g) ]
end 

to-report obey-goto [ x y ]  ;; obey "goto x y" command; report true when achieved
  let d (distancexy x y)
  if-else (d = 0)
    [ if (verbose?) [ show (list "already at" x y) ]
      report true ]
    
    [ facexy x y
      if-else (d <= speed)
        [ setxy x y
          if (verbose?) [ show (list "have reached" x y) ]
          report true ]
      
        [ fd speed
          report false ] ]
end 

to-report obey-meet [ him ]  ;; obey "meet agent" command; report true when achieved
  if-else (him = self)
    [ if (verbose?) [ show (list "i am" him) ]
      report true ]
    
    [ face him
      let d (distance him)
      
      if-else (d <= speed)
        [ move-to him
          if (verbose?) [ show (list "have met" ([label] of him)) ]
          report true ]
        
        [ fd speed
          report false ] ]
end  

to-report obey-eat [ him ]  ;; obey "eat agent" command; report true when achieved
  if-else (carrier != nobody or distance him > 2 or ([ carrier ] of him) != nobody)
    [ report false ]
    
    [ face him
      let d (distance him)
      
      if-else (d <= speed)
        [ move-to him
          show (list "eating" ([label] of him))
          ask him [ die ]
          report true ]
        
        [ fd speed
          report false ] ]
end  

to go
  if (count (turtles with [ goal != []]) = 0) [ stop ]
  ask turtles [ obey ]
  tick
end 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; NetLogo code for planning ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; state format is [ w g c m ]
;; w = wolf, -1 for free on left, +1 for free on right, 0 for being carried
;; g = goat, c = cabbage, similarly
;; m = man, -1 for on left, +1 for on right

to-report wgc-plan ;; top-level reporter to return the full plan
  let init-state [0 0 0 1]
  let p (planner init-state [] [] [])
  ;; add final entries to erase wolf and goat plans after the problem has been solved
  set p (sentence p (list "instruct" wolf [] "instruct" goat []))
  show (fput "THE PLAN IS:" p)
  report p
end 

to-report best-of [ x y ] ;; find the best of two solutions
  if-else (length x < length y and x != [])
    [ report x ]
    [ report y]
end 

to-report acceptable [ state ] ;; everybody is on the left (possibly being carried)
  report ((item 0 state <= 0) and (item 1 state <= 0) and
          (item 2 state <= 0) and (item 3 state = -1))
end 

to-report bad [ state ] ;; wolf and goat loose together, or goat and cabbage loose together
  report ((item 0 state = -1 and item 1 state = -1) or
          (item 0 state = 1 and item 1 state = 1) or
          (item 1 state = -1 and item 2 state = -1) or
          (item 1 state = 1 and item 2 state = 1))
end 

to-report count-zeros [ x y z ] ;; count-zeros is used to count how much the man is carrying
  let n 0
  if (x = 0) [ set n (n + 1) ]
  if (y = 0) [ set n (n + 1) ]
  if (z = 0) [ set n (n + 1) ]
  report n
end 

to-report planner [ state history partial-solution best-so-far ] ;; the planner itself
  if-else ((bad state) or (member? state history) or 
           (length best-so-far <= length partial-solution and best-so-far != []))
    [ report best-so-far ]
    
    [ if-else (acceptable state)
        [ report best-of best-so-far partial-solution ]
        
        [ let h (lput state history)
          let b best-so-far
          let w (item 0 state)
          let g (item 1 state)
          let c (item 2 state)
          let m (item 3 state)
          
          ;; Can drop carried items on the current bank
          ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
          if (item 0 state = 0)
            [ let s (list m g c m)
              let new-partial (sentence partial-solution (list "drop" wolf))
              set b (planner s h new-partial b) ]
          if (item 1 state = 0)
            [ let s (list w m c m)
              let new-partial (sentence partial-solution (list "drop" goat))
              set b (planner s h new-partial b) ]
          if (item 2 state = 0)
            [ let s (list w g m m)
              let new-partial (sentence partial-solution (list "drop" cabbage))
              set b (planner s h new-partial b) ]
          
          ;; Can pick up items on the current bank
          ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
          if (item 0 state = m)
            [ let s (list 0 g c m)
              let new-partial (sentence partial-solution (list "pickup" wolf))
              set b (planner s h new-partial b) ]
          if (item 1 state = m)
            [ let s (list w 0 c m)
              let new-partial (sentence partial-solution (list "pickup" goat))
              set b (planner s h new-partial b) ]
          if (item 2 state = m)
            [ let s (list w g 0 m)
              let new-partial (sentence partial-solution (list "pickup" cabbage))
              set b (planner s h new-partial b) ]
          
          ;; Can go left or right if at most one item is being carried
          ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
          if ((m = 1) and (count-zeros w g c <= 1))
            [ let s (list w g c -1)
              let new-partial (sentence partial-solution [ "go-left" ])
              set b (planner s h new-partial b) ]
          if ((m = -1) and (count-zeros w g c <= 1))
            [ let s (list w g c 1)
              let new-partial (sentence partial-solution [ "go-right" ])
              set b (planner s h new-partial b) ]

          report b
        ]
    ]
end