OZONE Asylum
Forums
Server-Side Scripting - Oh my!
LISP anyone?
This page's ID:
28064
Search
QuickChanges
Forums
FAQ
Archives
Register
Edit Post
Who can edit a post?
The poster and administrators may edit a post. The poster can only edit it for a short while after the initial post.
Your User Name:
Your Password:
Login Options:
Remember Me On This Computer
Your Text:
Insert Slimies »
Insert UBB Code »
Close
Last Tag
|
All Tags
UBB Help
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)) ) ) [/code] 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)) [/quote] 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.
Loading...
Options:
Enable Slimies
Enable Linkwords
« Backwards
—
Onwards »
Maximum Security
OZONE
DHTML/Javascript
Server-Side Scripting - Oh my!
CSS - DOM - XHTML - XML - XSL - XSLT
Stupid Basic HTML
Visual Therapy
Photoshop
Photoshop Pong, Anyone?
***WARNING*** BIG SIG APPROACHING
Photography
3D Modelling & Rendering
Multimedia/Animation
Print Graphics
Holding Pens
Philosophy and other Silliness
Outpatient Counseling
Site reviews!
Mad Scientists' Laboratory
Getting to know the Grail