(defstruct estado
  ml cl ; misioneros y caníbales en la izquierda
  mr cr ; misioneros y caníbales en la derecha
  side ; 0 = bote a la izquierda, 1 = derecha
  camino) ; lista de pasos
 
(defun estado-valido-p (st)
  (let ((ml (estado-ml st))
        (cl (estado-cl st))
        (mr (estado-mr st))
        (cr (estado-cr st)))
    (and (>= ml 0) (<= ml 3)
         (>= cl 0) (<= cl 3)
         (>= mr 0) (<= mr 3)
         (>= cr 0) (<= cr 3)
         (or (= ml 0) (>= ml cl))
         (or (= mr 0) (>= mr cr)))))
 
(defun mover (st m c)
  (let* ((ml (estado-ml st))
         (cl (estado-cl st))
         (mr (estado-mr st))
         (cr (estado-cr st))
         (side (estado-side st)))
    (cond
      ((= side 0)
       (make-estado :ml (- ml m) :cl (- cl c)
                    :mr (+ mr m) :cr (+ cr c)
                    :side 1
                    :camino (append (estado-camino st)
                                    (list (format nil "~dM~dC ->" m c)))))
      (t
       (make-estado :ml (+ ml m) :cl (+ cl c)
                    :mr (- mr m) :cr (- cr c)
                    :side 0
                    :camino (append (estado-camino st)
                                    (list (format nil "~dM~dC <-" m c))))))))
 
(defun iguales (a b)
  (and (= (estado-ml a) (estado-ml b))
       (= (estado-cl a) (estado-cl b))
       (= (estado-mr a) (estado-mr b))
       (= (estado-cr a) (estado-cr b))
       (= (estado-side a) (estado-side b))))
 
(defun repetido-p (nuevo camino)
  (some (lambda (e) (iguales e nuevo)) camino))
 
(defparameter *viajes*
  '((2 0) (0 2) (1 1) (1 0) (0 1)))
 
(defun resolver (estado final camino)
  (when (iguales estado final)
    ;; Quitamos el push para no alterar la lista original y usamos list para mostrar
    (mostrar-solucion (reverse (cons estado camino)))
    (return-from resolver))
 
  (dolist (v *viajes*)
    (let ((m (first v))
          (c (second v)))
      (let ((nuevo (mover estado m c)))
        (when (and (estado-valido-p nuevo)
                   (not (repetido-p nuevo camino)))
          (resolver nuevo final (cons estado camino)))))))
 
(defun personas (m c)
  (concatenate 'string
                (make-string m :initial-element #\M)
                (make-string c :initial-element #\C)))
 
(defun lado-a-string (m c)
  (format nil "[~3a]" (personas m c)))
 
(defun mostrar-paso (anterior actual)
  (let ((ml (estado-ml anterior))
        (cl (estado-cl anterior))
        (mr (estado-mr anterior))
        (cr (estado-cr anterior))
        (side (estado-side anterior))
        (ml2 (estado-ml actual))
        (cl2 (estado-cl actual))
        (mr2 (estado-mr actual))
        (cr2 (estado-cr actual))
        (side2 (estado-side actual)))
 
    (let* ((dm (- ml ml2))
           (dc (- cl cl2))
           (m (abs dm))
           (c (abs dc))
           (cruce (personas m c)))
      (format t "~%Paso ~a (antes de cruzar):~%" (+ 1 (length (estado-camino anterior))))
      ;; CORRECCIÓN AQUÍ: Reemplazamos [] por (lado-a-string mr cr)
      (if (= side 0)
          (format t "~a B ~~~~~~ ~a~%" (lado-a-string ml cl) (lado-a-string mr cr))
          (format t "~a ~~~~~~ B ~a~%" (lado-a-string ml cl) (lado-a-string mr cr)))
 
      (format t "Cruzando con: ~a~%" cruce)
 
      (format t "Paso ~a (después de cruzar):~%" (+ 1 (length (estado-camino anterior))))
      ;; CORRECCIÓN AQUÍ: Reemplazamos [] por (lado-a-string mr2 cr2)
      (if (= side2 0)
          (format t "~a B ~~~~~~ ~a~%" (lado-a-string ml2 cl2) (lado-a-string mr2 cr2))
          (format t "~a ~~~~~~ B ~a~%" (lado-a-string ml2 cl2) (lado-a-string mr2 cr2))))))
 
(defun mostrar-solucion (camino)
  (format t "~%====================================~%") ;traviesos
  (format t "Solución en ~d pasos~%" (1- (length camino)))
  (loop for (a b) on camino while b do
        (mostrar-paso a b))
  (format t "~%====================================~%"))
 
(defun main ()
  (let ((inicio (make-estado :ml 3 :cl 3 :mr 0 :cr 0 :side 0 :camino '()))
        (fin (make-estado :ml 0 :cl 0 :mr 3 :cr 3 :side 1 :camino '())))
    (resolver inicio fin '())))
 
(main)

KGRlZnN0cnVjdCBlc3RhZG8KICBtbCBjbCA7IG1pc2lvbmVyb3MgeSBjYW7DrWJhbGVzIGVuIGxhIGl6cXVpZXJkYQogIG1yIGNyIDsgbWlzaW9uZXJvcyB5IGNhbsOtYmFsZXMgZW4gbGEgZGVyZWNoYQogIHNpZGUgOyAwID0gYm90ZSBhIGxhIGl6cXVpZXJkYSwgMSA9IGRlcmVjaGEKICBjYW1pbm8pIDsgbGlzdGEgZGUgcGFzb3MKIAooZGVmdW4gZXN0YWRvLXZhbGlkby1wIChzdCkKICAobGV0ICgobWwgKGVzdGFkby1tbCBzdCkpCiAgICAgICAgKGNsIChlc3RhZG8tY2wgc3QpKQogICAgICAgIChtciAoZXN0YWRvLW1yIHN0KSkKICAgICAgICAoY3IgKGVzdGFkby1jciBzdCkpKQogICAgKGFuZCAoPj0gbWwgMCkgKDw9IG1sIDMpCiAgICAgICAgICg+PSBjbCAwKSAoPD0gY2wgMykKICAgICAgICAgKD49IG1yIDApICg8PSBtciAzKQogICAgICAgICAoPj0gY3IgMCkgKDw9IGNyIDMpCiAgICAgICAgIChvciAoPSBtbCAwKSAoPj0gbWwgY2wpKQogICAgICAgICAob3IgKD0gbXIgMCkgKD49IG1yIGNyKSkpKSkKIAooZGVmdW4gbW92ZXIgKHN0IG0gYykKICAobGV0KiAoKG1sIChlc3RhZG8tbWwgc3QpKQogICAgICAgICAoY2wgKGVzdGFkby1jbCBzdCkpCiAgICAgICAgIChtciAoZXN0YWRvLW1yIHN0KSkKICAgICAgICAgKGNyIChlc3RhZG8tY3Igc3QpKQogICAgICAgICAoc2lkZSAoZXN0YWRvLXNpZGUgc3QpKSkKICAgIChjb25kCiAgICAgICgoPSBzaWRlIDApCiAgICAgICAobWFrZS1lc3RhZG8gOm1sICgtIG1sIG0pIDpjbCAoLSBjbCBjKQogICAgICAgICAgICAgICAgICAgIDptciAoKyBtciBtKSA6Y3IgKCsgY3IgYykKICAgICAgICAgICAgICAgICAgICA6c2lkZSAxCiAgICAgICAgICAgICAgICAgICAgOmNhbWlubyAoYXBwZW5kIChlc3RhZG8tY2FtaW5vIHN0KQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAobGlzdCAoZm9ybWF0IG5pbCAifmRNfmRDIC0+IiBtIGMpKSkpKQogICAgICAodAogICAgICAgKG1ha2UtZXN0YWRvIDptbCAoKyBtbCBtKSA6Y2wgKCsgY2wgYykKICAgICAgICAgICAgICAgICAgICA6bXIgKC0gbXIgbSkgOmNyICgtIGNyIGMpCiAgICAgICAgICAgICAgICAgICAgOnNpZGUgMAogICAgICAgICAgICAgICAgICAgIDpjYW1pbm8gKGFwcGVuZCAoZXN0YWRvLWNhbWlubyBzdCkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKGxpc3QgKGZvcm1hdCBuaWwgIn5kTX5kQyA8LSIgbSBjKSkpKSkpKSkKIAooZGVmdW4gaWd1YWxlcyAoYSBiKQogIChhbmQgKD0gKGVzdGFkby1tbCBhKSAoZXN0YWRvLW1sIGIpKQogICAgICAgKD0gKGVzdGFkby1jbCBhKSAoZXN0YWRvLWNsIGIpKQogICAgICAgKD0gKGVzdGFkby1tciBhKSAoZXN0YWRvLW1yIGIpKQogICAgICAgKD0gKGVzdGFkby1jciBhKSAoZXN0YWRvLWNyIGIpKQogICAgICAgKD0gKGVzdGFkby1zaWRlIGEpIChlc3RhZG8tc2lkZSBiKSkpKQogCihkZWZ1biByZXBldGlkby1wIChudWV2byBjYW1pbm8pCiAgKHNvbWUgKGxhbWJkYSAoZSkgKGlndWFsZXMgZSBudWV2bykpIGNhbWlubykpCiAKKGRlZnBhcmFtZXRlciAqdmlhamVzKgogICcoKDIgMCkgKDAgMikgKDEgMSkgKDEgMCkgKDAgMSkpKQogCihkZWZ1biByZXNvbHZlciAoZXN0YWRvIGZpbmFsIGNhbWlubykKICAod2hlbiAoaWd1YWxlcyBlc3RhZG8gZmluYWwpCiAgICA7OyBRdWl0YW1vcyBlbCBwdXNoIHBhcmEgbm8gYWx0ZXJhciBsYSBsaXN0YSBvcmlnaW5hbCB5IHVzYW1vcyBsaXN0IHBhcmEgbW9zdHJhcgogICAgKG1vc3RyYXItc29sdWNpb24gKHJldmVyc2UgKGNvbnMgZXN0YWRvIGNhbWlubykpKQogICAgKHJldHVybi1mcm9tIHJlc29sdmVyKSkKIAogIChkb2xpc3QgKHYgKnZpYWplcyopCiAgICAobGV0ICgobSAoZmlyc3QgdikpCiAgICAgICAgICAoYyAoc2Vjb25kIHYpKSkKICAgICAgKGxldCAoKG51ZXZvIChtb3ZlciBlc3RhZG8gbSBjKSkpCiAgICAgICAgKHdoZW4gKGFuZCAoZXN0YWRvLXZhbGlkby1wIG51ZXZvKQogICAgICAgICAgICAgICAgICAgKG5vdCAocmVwZXRpZG8tcCBudWV2byBjYW1pbm8pKSkKICAgICAgICAgIChyZXNvbHZlciBudWV2byBmaW5hbCAoY29ucyBlc3RhZG8gY2FtaW5vKSkpKSkpKQogCihkZWZ1biBwZXJzb25hcyAobSBjKQogIChjb25jYXRlbmF0ZSAnc3RyaW5nCiAgICAgICAgICAgICAgICAobWFrZS1zdHJpbmcgbSA6aW5pdGlhbC1lbGVtZW50ICNcTSkKICAgICAgICAgICAgICAgIChtYWtlLXN0cmluZyBjIDppbml0aWFsLWVsZW1lbnQgI1xDKSkpCiAKKGRlZnVuIGxhZG8tYS1zdHJpbmcgKG0gYykKICAoZm9ybWF0IG5pbCAiW34zYV0iIChwZXJzb25hcyBtIGMpKSkKIAooZGVmdW4gbW9zdHJhci1wYXNvIChhbnRlcmlvciBhY3R1YWwpCiAgKGxldCAoKG1sIChlc3RhZG8tbWwgYW50ZXJpb3IpKQogICAgICAgIChjbCAoZXN0YWRvLWNsIGFudGVyaW9yKSkKICAgICAgICAobXIgKGVzdGFkby1tciBhbnRlcmlvcikpCiAgICAgICAgKGNyIChlc3RhZG8tY3IgYW50ZXJpb3IpKQogICAgICAgIChzaWRlIChlc3RhZG8tc2lkZSBhbnRlcmlvcikpCiAgICAgICAgKG1sMiAoZXN0YWRvLW1sIGFjdHVhbCkpCiAgICAgICAgKGNsMiAoZXN0YWRvLWNsIGFjdHVhbCkpCiAgICAgICAgKG1yMiAoZXN0YWRvLW1yIGFjdHVhbCkpCiAgICAgICAgKGNyMiAoZXN0YWRvLWNyIGFjdHVhbCkpCiAgICAgICAgKHNpZGUyIChlc3RhZG8tc2lkZSBhY3R1YWwpKSkKIAogICAgKGxldCogKChkbSAoLSBtbCBtbDIpKQogICAgICAgICAgIChkYyAoLSBjbCBjbDIpKQogICAgICAgICAgIChtIChhYnMgZG0pKQogICAgICAgICAgIChjIChhYnMgZGMpKQogICAgICAgICAgIChjcnVjZSAocGVyc29uYXMgbSBjKSkpCiAgICAgIChmb3JtYXQgdCAifiVQYXNvIH5hIChhbnRlcyBkZSBjcnV6YXIpOn4lIiAoKyAxIChsZW5ndGggKGVzdGFkby1jYW1pbm8gYW50ZXJpb3IpKSkpCiAgICAgIDs7IENPUlJFQ0NJw5NOIEFRVcONOiBSZWVtcGxhemFtb3MgW10gcG9yIChsYWRvLWEtc3RyaW5nIG1yIGNyKQogICAgICAoaWYgKD0gc2lkZSAwKQogICAgICAgICAgKGZvcm1hdCB0ICJ+YSBCIH5+fn5+fiB+YX4lIiAobGFkby1hLXN0cmluZyBtbCBjbCkgKGxhZG8tYS1zdHJpbmcgbXIgY3IpKQogICAgICAgICAgKGZvcm1hdCB0ICJ+YSB+fn5+fn4gQiB+YX4lIiAobGFkby1hLXN0cmluZyBtbCBjbCkgKGxhZG8tYS1zdHJpbmcgbXIgY3IpKSkKICAgICAgCiAgICAgIChmb3JtYXQgdCAiQ3J1emFuZG8gY29uOiB+YX4lIiBjcnVjZSkKICAgICAgCiAgICAgIChmb3JtYXQgdCAiUGFzbyB+YSAoZGVzcHXDqXMgZGUgY3J1emFyKTp+JSIgKCsgMSAobGVuZ3RoIChlc3RhZG8tY2FtaW5vIGFudGVyaW9yKSkpKQogICAgICA7OyBDT1JSRUNDScOTTiBBUVXDjTogUmVlbXBsYXphbW9zIFtdIHBvciAobGFkby1hLXN0cmluZyBtcjIgY3IyKQogICAgICAoaWYgKD0gc2lkZTIgMCkKICAgICAgICAgIChmb3JtYXQgdCAifmEgQiB+fn5+fn4gfmF+JSIgKGxhZG8tYS1zdHJpbmcgbWwyIGNsMikgKGxhZG8tYS1zdHJpbmcgbXIyIGNyMikpCiAgICAgICAgICAoZm9ybWF0IHQgIn5hIH5+fn5+fiBCIH5hfiUiIChsYWRvLWEtc3RyaW5nIG1sMiBjbDIpIChsYWRvLWEtc3RyaW5nIG1yMiBjcjIpKSkpKSkKIAooZGVmdW4gbW9zdHJhci1zb2x1Y2lvbiAoY2FtaW5vKQogIChmb3JtYXQgdCAifiU9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT1+JSIpIDt0cmF2aWVzb3MKICAoZm9ybWF0IHQgIlNvbHVjacOzbiBlbiB+ZCBwYXNvc34lIiAoMS0gKGxlbmd0aCBjYW1pbm8pKSkKICAobG9vcCBmb3IgKGEgYikgb24gY2FtaW5vIHdoaWxlIGIgZG8KICAgICAgICAobW9zdHJhci1wYXNvIGEgYikpCiAgKGZvcm1hdCB0ICJ+JT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PX4lIikpCiAKKGRlZnVuIG1haW4gKCkKICAobGV0ICgoaW5pY2lvIChtYWtlLWVzdGFkbyA6bWwgMyA6Y2wgMyA6bXIgMCA6Y3IgMCA6c2lkZSAwIDpjYW1pbm8gJygpKSkKICAgICAgICAoZmluIChtYWtlLWVzdGFkbyA6bWwgMCA6Y2wgMCA6bXIgMyA6Y3IgMyA6c2lkZSAxIDpjYW1pbm8gJygpKSkpCiAgICAocmVzb2x2ZXIgaW5pY2lvIGZpbiAnKCkpKSkKCihtYWluKQ==