(defglobal ?*start-position* = (create$ 5 2))
(defglobal ?*winning-distance* = 13)
 
(deftemplate node
   (slot position)
   (slot g)
   (slot h)
   (slot f))
 
(deffunction distance (?x ?y)
   (return (sqrt (+ (* ?x ?x) (* ?y ?y)))))
 
(deffunction heuristic (?x ?y)
   (return (- ?*winning-distance* (distance ?x ?y))))
 
(deffunction generate-children (?node)
   (bind ?pos (fact-slot-value ?node position))
   (bind ?x (nth 1 ?pos))
   (bind ?y (nth 2 ?pos))
   (return (create$ (create$ (+ ?x 3) ?y)
                    (create$ ?x (+ ?y 3))
                    (create$ ?x (+ ?y 4)))))
 
(defrule init
   (initial-fact)
   =>
   (assert (node (position ?*start-position*)
                 (g 0)
                 (h (heuristic (nth 1 ?*start-position*) (nth 2 ?*start-position*)))
                 (f (heuristic (nth 1 ?*start-position*) (nth 2 ?*start-position*))))))
 
(defrule expand-node
   ?node <- (node (position ?pos)
                  (g ?g)
                  (h ?h)
                  (f ?f))
   =>
   (bind ?children (generate-children ?node))
   (foreach ?child ?children
      (bind ?x (nth 1 ?child))
      (bind ?y (nth 2 ?child))
      (bind ?dist (distance ?x ?y))
      (if (>= ?dist ?*winning-distance*)
         then
         (printout t "Winning position: " ?child crlf)
         (halt))
      (assert (node (position ?child)
                    (g (+ ?g 1))
                    (h (heuristic ?x ?y))
                    (f (+ (+ ?g 1) (heuristic ?x ?y))))))))
 
(defrule display-tree
   ?node <- (node (position ?pos) (g ?g) (h ?h) (f ?f))
   =>
   (printout t "Node: " ?pos ", g: " ?g ", h: " ?h ", f: " ?f crlf))
; your code goes here
 
(exit)
; empty line at the end

KGRlZmdsb2JhbCA/KnN0YXJ0LXBvc2l0aW9uKiA9IChjcmVhdGUkIDUgMikpCihkZWZnbG9iYWwgPyp3aW5uaW5nLWRpc3RhbmNlKiA9IDEzKQoKKGRlZnRlbXBsYXRlIG5vZGUKICAgKHNsb3QgcG9zaXRpb24pCiAgIChzbG90IGcpCiAgIChzbG90IGgpCiAgIChzbG90IGYpKQoKKGRlZmZ1bmN0aW9uIGRpc3RhbmNlICg/eCA/eSkKICAgKHJldHVybiAoc3FydCAoKyAoKiA/eCA/eCkgKCogP3kgP3kpKSkpKQoKKGRlZmZ1bmN0aW9uIGhldXJpc3RpYyAoP3ggP3kpCiAgIChyZXR1cm4gKC0gPyp3aW5uaW5nLWRpc3RhbmNlKiAoZGlzdGFuY2UgP3ggP3kpKSkpCgooZGVmZnVuY3Rpb24gZ2VuZXJhdGUtY2hpbGRyZW4gKD9ub2RlKQogICAoYmluZCA/cG9zIChmYWN0LXNsb3QtdmFsdWUgP25vZGUgcG9zaXRpb24pKQogICAoYmluZCA/eCAobnRoIDEgP3BvcykpCiAgIChiaW5kID95IChudGggMiA/cG9zKSkKICAgKHJldHVybiAoY3JlYXRlJCAoY3JlYXRlJCAoKyA/eCAzKSA/eSkKICAgICAgICAgICAgICAgICAgICAoY3JlYXRlJCA/eCAoKyA/eSAzKSkKICAgICAgICAgICAgICAgICAgICAoY3JlYXRlJCA/eCAoKyA/eSA0KSkpKSkKCihkZWZydWxlIGluaXQKICAgKGluaXRpYWwtZmFjdCkKICAgPT4KICAgKGFzc2VydCAobm9kZSAocG9zaXRpb24gPypzdGFydC1wb3NpdGlvbiopCiAgICAgICAgICAgICAgICAgKGcgMCkKICAgICAgICAgICAgICAgICAoaCAoaGV1cmlzdGljIChudGggMSA/KnN0YXJ0LXBvc2l0aW9uKikgKG50aCAyID8qc3RhcnQtcG9zaXRpb24qKSkpCiAgICAgICAgICAgICAgICAgKGYgKGhldXJpc3RpYyAobnRoIDEgPypzdGFydC1wb3NpdGlvbiopIChudGggMiA/KnN0YXJ0LXBvc2l0aW9uKikpKSkpKQoKKGRlZnJ1bGUgZXhwYW5kLW5vZGUKICAgP25vZGUgPC0gKG5vZGUgKHBvc2l0aW9uID9wb3MpCiAgICAgICAgICAgICAgICAgIChnID9nKQogICAgICAgICAgICAgICAgICAoaCA/aCkKICAgICAgICAgICAgICAgICAgKGYgP2YpKQogICA9PgogICAoYmluZCA/Y2hpbGRyZW4gKGdlbmVyYXRlLWNoaWxkcmVuID9ub2RlKSkKICAgKGZvcmVhY2ggP2NoaWxkID9jaGlsZHJlbgogICAgICAoYmluZCA/eCAobnRoIDEgP2NoaWxkKSkKICAgICAgKGJpbmQgP3kgKG50aCAyID9jaGlsZCkpCiAgICAgIChiaW5kID9kaXN0IChkaXN0YW5jZSA/eCA/eSkpCiAgICAgIChpZiAoPj0gP2Rpc3QgPyp3aW5uaW5nLWRpc3RhbmNlKikKICAgICAgICAgdGhlbgogICAgICAgICAocHJpbnRvdXQgdCAiV2lubmluZyBwb3NpdGlvbjogIiA/Y2hpbGQgY3JsZikKICAgICAgICAgKGhhbHQpKQogICAgICAoYXNzZXJ0IChub2RlIChwb3NpdGlvbiA/Y2hpbGQpCiAgICAgICAgICAgICAgICAgICAgKGcgKCsgP2cgMSkpCiAgICAgICAgICAgICAgICAgICAgKGggKGhldXJpc3RpYyA/eCA/eSkpCiAgICAgICAgICAgICAgICAgICAgKGYgKCsgKCsgP2cgMSkgKGhldXJpc3RpYyA/eCA/eSkpKSkpKSkpCgooZGVmcnVsZSBkaXNwbGF5LXRyZWUKICAgP25vZGUgPC0gKG5vZGUgKHBvc2l0aW9uID9wb3MpIChnID9nKSAoaCA/aCkgKGYgP2YpKQogICA9PgogICAocHJpbnRvdXQgdCAiTm9kZTogIiA/cG9zICIsIGc6ICIgP2cgIiwgaDogIiA/aCAiLCBmOiAiID9mIGNybGYpKQo7IHlvdXIgY29kZSBnb2VzIGhlcmUKCihleGl0KQo7IGVtcHR5IGxpbmUgYXQgdGhlIGVuZA==