lørdag 12. desember 2015 Julekalender Common Lisp
Julekalenderen har ikke gått helt som planlagt. Virkeligheten innhentet meg, og jeg har ikke funnet tid til å kode opp og poste så mye av det jeg hadde håpet. Ikke veeeeldig overraskende, men det var jo lov å være optimistisk.
Jeg støtte også på et problem med SMS-løsningen jeg jobber med som jeg sålangt ikke har klart å løse. Jeg hadde noe som fungerte, men så noen dager senere så fungerte det ikke. Oppdaterte tredjepartsbibloteker? En av de mange Windows-oppgraderingene som skaper problemer? Jeg vet ikke, men avlusing tar tid. Og sist men ikke minst så er det ikke så motiverende å skrive så mye om et tema - Common Lisp - som svært få (forståelig nok) viser noen interesse for.
Derimot har jeg hatt det veldig gøy i desember med å løse oppgavene i Knowit sin julekalender, og det har det jo også blitt noen blogposter av: 1, 2, 3, 4 og 5.
Her følger løsningene mine på resten av lukene som har blitt åpnet...
Oppgaveteksten lød:
Gitt at vi har n par parenteser, hvor mange kombinasjoner av balanserte parenteser (dvs alle åpne parenteser er lukket) kan en lage? Eksempel: Gitt n=3, har vi følgende kombinasjoner som gir balanserte parenteser: "((()))", "(()())", "(())()", "()(())", "()()()" Altså fem ulike måter.
Hvor mange velformede kombinasjoner finnes det for n = 13?
Her valgte jeg å gjøre litt research før jeg gikk i gang, og fant raskt ut at det jeg var ute etter var å kalkulere et Catalan-nummer. Og Wikipedia var så snill å liste ut de første numrene, inkludert for n=13, så da kunne jeg besvare luken først, og så kode etterpå...
Jeg valgte å være litt fancy, og laget en funksjon som brukte continuation passing style og som faktisk genererte streng-representasjoner av alle kombinasjonene. Den er litt lang, og egner seg ikke å vise her uten en del forklaring. I stedet vil jeg vise et par andre løsninger på oppgaven, som er Common Lisp-adapsjoiner av andre sine bidrag.
Her er en oversettelse av en løsning laget av Tomas i F#. Jeg brukter en pakke som heter optima til å gi meg patter matching, som blir ganske elegant her:
(ql:quickload :optima)
(use-package :optima)
(defun gen-parens (n &optional (opened 0))
(match (cons n opened)
((cons 0 0) 0)
((cons 0 _) 1)
((cons n 0) (gen-parens (1- n) 1))
((cons n x) (+ (gen-parens n (1- x))
(gen-parens (1- n) (1+ x))))))
(print (time (gen-parens 13)))
På min maskin finner denne funksjonen løsningen på 0,031 sekunder (og 84 millioner prosessorsykler).
Jeg oversatte også en kort Java-løsning, laget av Narve:
(defun calc (l r)
(if (zerop l) 1
(+ (calc (1- l) r)
(if (<= r l) 0
(calc l (1- r))))))
(print (time (calc 13 13)))
Denne var raskere: 0,015 sekunder (og 52 millioner sykler).
Den syvende luken lød:
Finn summen av alle positive heltall mellom 0 og 1000 som er har 7 som en primtallsfaktor, der det reverserte tallet også har 7 som en primtallsfaktor. For eksempel teller 259 da en får 952 om en reverserer sifrene og begge disse tallene har 7 som en primtallsfaktor.
Oppgaveteksten kan forvirre litt, men om man skjønner at "har 7 som en primtallsfaktor" rett og slett bare betyr at tallet må være delelig på 7 så er oppgaven lett. Her er min komplette løsning, som blant annet viser frem hvor fleksibel loop-makroen i Common Lisp kan være:
(ql:quickload :cl-arrows)
(use-package :cl-arrows)
(defun parse-any-value (x)
(with-input-from-string (in x)
(read in)))
(defun any-value-to-string (x)
(format nil "~A" x))
(defun reverse-number (x)
(->> x
any-value-to-string
reverse
parse-any-value))
(loop for x from 1 to 1000
for x-reversed = (reverse-number x)
with sum = 0
when (and (zerop (mod x 7))
(zerop (mod x-reversed 7)))
do (incf sum x)
finally (format t "~&Summen er: ~A~%" sum))
Vi definerer et primtall som et MIRPTALL dersom vi fortsatt har er primtall når sifrene reverseres. Regelen gjelder imidlertid ikke dersom tallet samtidig er et palindrom (dvs likt samme hvilken ende det leses fra, som 969). Hvor mange positive heltall under 1000 er MIRPTALL?
Her kunne jeg gjenbruke reverse-number fra luke 7, og utfordringen var å lage en funksjon som testet om et tall var et primtall. Her må jeg innrømme at jeg jukset litt - jeg har tenkt grundig gjennom dette før da jeg løste lignende oppgaver i Project Euler, men denne gangen fant jeg noe på nettet som jeg pyntet litt på, og som endte opp slik:
(defun forall (L P)
(or (null L)
(and (funcall P (car L))
(forall (cdr L) P))))
(defun nums (start stop)
(let (L)
(loop (when (> start stop)
(return (reverse L)))
(setf L (cons start L))
(incf start))))
(defun prime (N)
(forall (nums 2 (floor (sqrt N)))
#'(lambda (d) (not (= (MOD N d) 0)))))
Da ble løsningen så enkel som dette:
(loop for x from 10 to 999
for x-reversed = (reverse-number x)
when (and (prime x)
(prime x-reversed)
(not (= x x-reversed)))
counting x)
Gitt et positivt heltall, finn den tilsvarende kolonnetittelen som vises fram i et Excel ark. Finn kolonnetittelen til 142453146368
Her rotet jeg mye! Jeg trodde først jeg skulle klare å løse oppgaven med noe kode jeg hadde skrevet før, og blogget om i posten Komprimere tall. Men nummereringen av kolonner er en litt spesiell måte å telle på, og jeg fikk det ikke til. Med litt Google-hjelp kom jeg opp med denne løsningen:
(defvar *BASE* 26)
(defun excelify (col)
(if (<= col *BASE*)
(string (code-char (+ col 64)))
(concatenate 'string
(excelify (quot (1- col) *BASE*))
(excelify (1+ (mod (1- col) *BASE*))))))
Basert på det jeg så i kommentartråden i julekalenderen implementerte jeg også et par andre varianter. Denne første er en oversettelse fra en løsning i Python:
(defun excelify2 (n)
(when (> n 0)
(let ((x (mod (1- n) *BASE*)))
(excelify2 (quot (- n x) *BASE*))
(format t "~A" (code-char (+ x 65))))))
Den er litt anderledes blant annet fordi den skriver ut én og én bokstav om gangen.
Og her er en direkte oversettelse av en løsning som ble presentert i Clojure:
(defun excelify3 (n &optional s)
(if (zerop n)
s
(excelify3
(quot (1- n) 26)
(concatenate 'string
(string (code-char
(+ 65 (mod (1- n) 26))))
s))))
I alle disse løsningene bruker jeg funksjonen quot for å dele, fordi deling i Common Lisp ellers ville gitt meg brøker:
(defun quot (m n)
(floor (/ m n)))
Om jeg deler for eksempel 5 på 2 i Common Lisp, får jeg 5/2 i retur. (quot 5 2) derimot gir meg to verdier tilbake, først tallet 2, og så resten 1/2 om jeg ønsker den. At brøk er en så basal datatype i Lisp er litt kult, men man må ofte passe på å unngå dem når man skal jobbe med heltall :)
Luke 10 prøvde jeg meg på, men jeg tenkte for komplisert, og endte opp med en løsning som ble for krevende. Til slutt var det Lisp som gav opp, og sa:
Heap exhausted. Game over.
Jeg hadde ikke mer tid, så jeg tok Lisp på ordet. Da jeg neste da fikk se løsningene folk hadde brukt ble jeg litt irritert, fordi jeg mente de løsningene ikke nødvendigvis hadde trengt å gi det riktige resultatet.., gitt et potensielt annet datasett. Dårlig taper?
På http://pastebin.com/raw.php?i=p1eVAM5H finner du en usortert liste med odde antall elementer. Elementene kan være romertall, binærtall eller heltall. Hva er mediantallet i denne lista?
Igjen fikk jeg bruk for flere ting jeg har laget før, som get-pastebin, split-lines, parse-any-value og quot. Hovedutfordringen var å konvertere binærtall og romertall til desimaltall. For binærtall gjorde jeg det sånn:
;; Binary input like "0b01010101"
(defun tokenize-binary (x)
(loop for bit across (subseq x 2)
collect (parse-any-value (string bit))))
(defun parse-binary (b)
(let ((tokens (tokenize-binary b)))
(reduce (lambda (x y) (+ (* x 2) y)) tokens)))
Og romertall konverterte jeg (igjen med litt Google-hjelp) slik:
(defun mapcn (chars nums string)
(loop as char across string
as i = (position char chars)
collect (and i (nth i nums))))
(defun parse-roman (R)
(loop with nums = (mapcn "IVXLCDM" '(1 5 10 50 100 500 1000) R)
as (A B) on nums if A sum (if (and B (< A B)) (- A) A)))
Jeg brukte regex til å sjekke hvilket type tall det var snakk om...
(defun binaryp (x)
(cl-ppcre:scan "^0b[01]+$" x))
(defun romanp (x)
(cl-ppcre:scan "^[IVXDCML]+$" x))
Og denne funksjonen gir desimalverdien, uavhengig av hvilket type tall vi får som input:
(defun get-relative-value (x)
(cond ((binaryp x) (parse-binary x))
((romanp x) (parse-roman x))
(t (parse-any-value x))))
For å finne median i en sortert liste:
(defun find-middle (xs)
(let ((middle-index (quot (length xs) 2)))
(nth middle-index xs)))
Og endelig lar problemet seg løse slik:
(-> "p1eVAM5H"
get-pastebin
split-lines
(sort #'< :key #'get-relative-value)
find-middle)
En kuriositet: Teknikken for å konvertere et binærtall til desimaltall i Common Lisp hentet jeg fra en blogpost på bloggen VLADNAMA - Memoirs of Vlad from Kabul. Vlad liker formler, teoremer, bevis, eksperimenter (spesielt når de eksploderer), Lisp, Fortran, Perl, skrujern, og han har åpenbart mye humor.
Så nå vet du hvem som var på bildet i starten av denne bloggposten ;)
...har jeg løst, men den løsningen kan jeg ikke legge ut helt enda, siden fristen ikke har gått ut. Kom tilbake i morgen om du vil se hva jeg kodet i senga på et hotellrom morgenen etter et bra julebord.
Og så var det bare 12 dager igjen til Julaften!