# Topic: LISP anyone? (Page 1 of 1)

_Mauro
Maniac (V) Inmate

From:
Insane since: Jul 2005

posted 06-09-2006 20:15

Lisp stands for list processing.
It is a functional language, different from object oriented languages. Everything in Lisp is a function, among odd characteristics, every single language construct.
Kinda like xsl.

We have an assigment, we had weeks to do it, but it turns out that it consisted in "filling the gaps" in a given AI code (heuristics to solve a given game).

Problem(s)? Nobody, not one single classmate has managed to do it. I have got as far as having a quirk in only of the functions we had to complete,
but... you know, it has this weird feel of "the teacher gave as a buggy code". Everybody is stuck on the same couple of functions, furthermore.

Some of us have a splendid infinite loop (my version, at some point, was playing the same two moves on and on and on...)
Some have stack overflows on recursive functions.
Some have had a function return the right output once, then never again.

I -never- do this but I am about to give up... I never give up usually, I am the most stubborn person in the Galaxy, but this thing has killed my enthusiasm.

Is there a LISP, or heuristics expert in the place?

-------------------------------------------------------------------

code:
```;=========================================================================
;  ALGORITHME A*
;=========================================================================

(defun a* (taquinInit taquinFinal)
(a*Interne
taquinFinal
(list (list taquinInit () (heuristique taquinInit taquinFinal) 0))
()
)
)

(defun a*Interne (taquinFinal ouverts fermes)
(do
;; variables utilisées par la boucle
(
(etatCourant 					;variable
(car ouverts) 	;valeur initiale
(car ouverts)		;incrémentation
)
)

;; condition d'arrêt et résultat
(
;;condition d'arrêt
(or (null ouverts) (equal (getTaquin etatCourant) taquinFinal))

;; résultat
(reverse (getChemin etatCourant))
)

; corps de la boucle

(let* (
;; on déclare 7 variables locales
(taquinCourant		(getTaquin etatCourant))	; le taquin de l'état courant
(gCourant					(getG etatCourant))				; le coût du chemin du l'état courant
(cheminCourant    (getChemin etatCourant))	; le chemin de l'état courant

; opérateurs : opérateurs applicables à l'état courant
(operateurs				(operateursPossibles taquinCourant))

; taquinsSuivantsEtOps contient les couples (op . taquin)
;  où taquin est le taquin obtenu en applicant l'opérateur op au taquin de l'état courant
(taquinsSuivantsEtOps   (mapcar (lambda (op) (cons op (taquinSuivant taquinCourant op))) operateurs))

(ouvertsSansEtatCourant 		(cdr ouverts))

; ouvertsEtFermes est le doublet constitué des listes ouverts et fermes
; enrichies des nouveaux états construits à l'aide des taquinsSuivants
; le taquin de l'état courant
(ouvertsEtFermes			(completerOuvertsEtFermes taquinFinal gCourant cheminCourant taquinsSuivantsEtOps ouvertsSansEtatCourant fermes))

)

(setf ouverts (car ouvertsEtFermes))
; on insère l'état courant dans la liste des états fermés
(setf fermes  (inserer taquinCourant cheminCourant (getH etatCourant) gCourant (cdr ouvertsEtFermes)))
)
)	; fin de la boucle
)

;-------------------------------------------------------------------------
;	(completerOuvertsEtFermes taquinFinal g chemin taquinsSuivantsEtOps ouverts fermes)
;  retourne le doublet contenant les nouvelles valeurs des listes ouverts et fermes
; après insertion des nouveaux états
;-------------------------------------------------------------------------
(defun completerOuvertsEtFermes (taquinFinal g chemin taquinsSuivantsEtOps ouverts fermes)
(cond
;;Condition si l'etat dans le quel on se trouve n'apartient ni à ouverts ni à fermés
(
(and (equal (taquinMembre (cdar taquinsSuivantsEtOps) ouverts) NIL) (equal (taquinMembre (cdar taquinsSuivantsEtOps)   fermes) NIL))
(list (inserer (cdar taquinsSuivantsEtOps) (append (list (caar taquinsSuivantsEtOps)) chemin) (heuristique (cdar taquinsSuivantsEtOps) taquinFinal) (getG (cdar taquinsSuivantsEtOps)) ouverts) fermes)
)
(t (list ouverts fermes))

)

)

;-------------------------------------------------------------------------
;	(insererEtOter taquinFinal taquin chemin h g listeEtats)
;  insère le nouvel état correspondant au taquin dans la liste listeEtats après avoir
; ôter l'état de cette liste contenant ce même taquin
;-------------------------------------------------------------------------
(defun insererEtOter (taquin chemin h g listeEtats)
;; A COMPLETER
(inserer taquin chemin h g (oter taquin listeEtats))
)

;-------------------------------------------------------------------------
;	(inserer taquin chemin h g listeEtats)
;  insère le nouvel état correspondant au taquin dans la liste listeEtats
;-------------------------------------------------------------------------
(defun inserer (taquin chemin h g listeEtats)
;; A COMPLETER
(cond
(
(not (equal chemin NIL))
(sort (append (list (list taquin chemin h g)) listeEtats) #'(lambda (x y) (< (+ (car x) (car(car x))) (+ (car y) (car(car y))))))
)
(t (append (list (list taquin chemin h g)) listeEtats))
)
)```

Basically, a* is the entry point, and a*Internal is the main loop.
completerOuvertsEtFermes is incomplete yet, because it relies on inserer.
inserer should append a new state on top of a sorted states list (and it does).

This is the trace log of the "completerOuvertsEtFermes" function:

quote:

;; Traçage de la fonction COMPLETEROUVERTSETFERMES.
1. Trace:
(COMPLETEROUVERTSETFERMES '(1 2 3 4 5 6 7 8 0) '0 'NIL
'((N 1 0 3 4 2 6 5 7 8) (S 1 2 3 4 7 6 5 0 8) (O 1 2 3 0 4 6 5 7 8) (E 1 2 3 4 6 0 5 7 8)) 'NIL
'NIL)
1. Trace: COMPLETEROUVERTSETFERMES ==> ((((1 0 3 4 2 6 5 7 8) (N) 8 4)) NIL)
1. Trace:
(COMPLETEROUVERTSETFERMES '(1 2 3 4 5 6 7 8 0) '4 '(N)
'((S 1 2 3 4 0 6 5 7 8) (O 0 1 3 4 2 6 5 7 8) (E 1 3 0 4 2 6 5 7 8)) 'NIL
'(((1 2 3 4 0 6 5 7 8) NIL 6 0) NIL))
1. Trace: COMPLETEROUVERTSETFERMES ==> (NIL (((1 2 3 4 0 6 5 7 8) NIL 6 0) NIL))

And it just doesn't make sense at all. The first time that function returns, everything goes right. The second trace == death of the application and wrong return value.
Nobody in the class has been able to solve this as of.. now, and it is due tomorrow at 8AM.

WarMage
Maniac (V) Mad Scientist

From: Rochester, New York, USA
Insane since: May 2000

posted 06-10-2006 02:15

I have never tried to debug something written in a different language, I might not be able to offer any help at all on this, but I will look at it later.

I am going out for a couple of hours, when I get back and if I have not drank too much I might be able to offer some assistance, but I wouldn't count on it.

Dan @ Code Town

_Mauro
Maniac (V) Inmate

From:
Insane since: Jul 2005

posted 06-10-2006 02:27

Well, 'couple of hours later, I am drunk myself.
While I do understand the a-star pathfinding algorithm in use here, while I do understand Lisp syntax to an extent (enough to know it's a pain in the behind),
the teacher really made it a nasty, nasty piece of code: he layed out tree structures as flat lists... so what he gave is what he'll get: almost all functions work
with the exception of the "crux", that's what I'll deliver.

Screw him.

And cheers to anyone enjoying a cool Friday night.