Les 5

Een hot nieuwtje in deze  #programmerenkunjeleren post, je hoeft niks meer te installeren maar je kunt newlisp nu gewoon in je browser, dus ook op je tablet of phone draaien, zie link ter linkerzijde. Er zitten nog wat beperkingen aan, vooral met opslag maar daar wordt aan gewerkt!

Ok, nu verder met de gewone les, de oplossing van de eerste opgave, sorteer op lengte is door ook een functie mee te geven aan de sort functie om aan te geven wat groter of kleiner is. Bijvoorbeeld de volgende (anonieme) functie:

(fn(x y) (< (length x) (length y)) true nil)

Dit is heel krachtig, je hoeft alleen een functie mee te geven aan een standaard functie om een zeer specifieke sorteer volgorde te verkrijgen. De volgende opgave was om hoe een lid van een lijst te verwijderen, oplossing:

(define (remove x lst) 
 (cond 
  ((= '() lst ) '()) 
  ((= x (first lst)) (remove x (rest lst))) 
  ((cons (first lst) (remove x (rest lst))))))

Een voorbeeld van functie die zichzelf aanroep (recursief), als je dat eenmaal snapt wil je niet anders! Even een uitleg, als lst leeg is dan return je een lege list, dit is  om de recursie uiteindelijk te laten stoppen. Anders kijk je of x gelijk is aan eerste element van lst, als dat het geval is dan ga je verder met de rest van de lijst (dus zonder x want die wil je verwijderen. Als x niet gelijk is dan bouw je een nieuwe lst (met cons) startende met het eerste element van de lijst en je roept remove weer aan met de rest van de list. Snappie ? ! Een kind kan de was doen!

De volgende stap voor onze scrabble bot is welke woorden we kunnen maken maken met de 7 letters die we uit de pot getrokken hebben,Daarvoor genereren we eerst alle mogelijke combinaties uit uit de zeven letters die we hebben, daarvoor gebruiken we onderstaand bestaand algorithme (we hoeven per slot van rekening niet alles zelf te verzinnen) :

Generate permutations of multisets ; Warren-Hanson algorithm for generating permutations of multisets.

(define (make-k-permutations k multiset) 
 (let ((pivots (unique multiset))) 
  (if (= k 1) 
   (map list pivots) 
   (let ((acc '())) 
  (dolist (p pivots) 
   (let ((sub-multiset (remove1 p multiset))) 
    (dolist (sub-perm (make-k-permutations (- k 1) sub-multiset)) 
     (push (cons p sub-perm) acc)))) acc)))) 

(define (remove1 elt lst) 
 (let ((elt-pos (find elt lst))) 
  (if elt-pos 
   (pop lst elt-pos)) 
   lst))

Dit hoef je nu nog niet allemaal te snappen, alleen even controleren of het werkt:

(make-k-permutations 2 '(1 2 3 2)) 

> ((3 2) (3 1) (2 2) (2 3) (2 1) (1 3) (1 2))

Tot de volgende keer!

Geef een reactie

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *