Prolog > Prolog ohjelmointikieli (2016-2-13)
Prolog ohjelmointikieli
Esitän pari esimerkkiä prolog-ohjelmointikielestä. Niiden perusteella et ehkä opi prolog-ohjelmointia enkä ehkä edes onnistu selittämään tyhjentävästi, miten esimerkkien ohjelmat toimivat. Tavoitteeni on kuitenkin antaa hyvä yleisvaikutelma siitä, millainen ohjelmointikieli prolog on ja antaa muutama esimerkki siitä, millaisia ongelmia sillä on kätevä ratkaista.
Helmikuu 2016
Käytän näissä esimerkeissä gnu-prologia ja swipl-prologia, mutta tarjolla on monia muitakin prolog-implementaatioita.
Olen myös yrittänyt tehdä prologilla musiikkia .
Prolog > Prolog ohjelmointikieli > Lyhyt esittely (2016-2-14)
Lyhyt esittely
Tammikuu 2016
Seuraavassa tutustumme prologiin tekemällä päättelyitä sukulaisuussuhteista. Sukulaisuussuhteet on kuvattu prologilla seuraavasti:
mother(eila,maija). mother(eila,kaisa). mother(kaisa,ritva). mother(kaisa,jukka). mother(maija,hilkka). mother(maija,ilkka). mother(liisa,heikki). mother(sofia,matti). father(frans,matti). father(matti,heikki). father(heikki,ilkka). father(heikki,hilkka).
prologissa vakiot kirjoitetaan pienellä kirjaimella ja muuttujat isolla. Isolla kirjaimella alkavat vakiot pitää kirjoittaa lainausmerkkeihin, esimerkiksi 'Eila'. Kirjoitin kuitenkin ihmisten nimet pienellä, koska en jaksanut näpytellä lainausmerkkejä ja ne olisivat ehkä johtaneet lukijaa harhaan.
Asioiden välisten suhteiden nimet– kuten mother ja father– kirjoitetaan myös pienellä.
Päättelyiden helpottamiseksi määrittelemme, millainen sukulaisuussuhde on vanhempi– parent.
parent(A,B):- mother(A,B). parent(A,B):- father(A,B).
Prologin "komentoja" kutsutaan predikaateiksi. Prolog-ohjelmaa voi lukea kuin logiikan kielellä kirjoitettua kuvausta tosiasioista ja niiden välisistä suhteista. Ylläolevan kuvauksen sukulaisuussuhteesta parent(A,B) voi lukea seuraavasti: Jos on olemassa A ja B siten, että A on B:n äiti tai A on B:n isä, niin A on B:n vanhempi. Vaihtoehdot– "tai"-operaatio– voidaan siis esittää allekkain ylläolevalla tavalla. Käynnistämme prolog-tulkin ja kokeilemme, miten määrittelymme toimii. | ?- on prolog-tulkin komentokehote, jonka perään kirjoitamme "kysymyksemme". Aluksi kerromme tulkille consult-komennolla, missä tiedostossa ongelmamme kuvaus on ja sen jälkeen kysymme, onko heikki jonkun vanhempi– | ?- parent(heikki,X).
htv> gprolog GNU Prolog 1.4.4 (64 bits) Compiled Dec 17 2015, 21:30:59 with gcc By Daniel Diaz Copyright (C) 1999-2013 Daniel Diaz | ?- consult(['suku.prolog']). compiling suku.prolog for byte code... suku.prolog compiled, 40 lines read - 3393 bytes written, 11 ms | ?- parent(heikki,X). X = ilkka ? ? Action (; for next solution, a for all solutions, RET to stop) ? a X = hilkka yes | ?- parent(X,heikki). X = liisa ? a X = matti
heikki on ilkan vanhempi, koska on olemassa tosiasia father(heikki,ilkka). Oletusarvoisesti prolog vastaa kysymykseen, onko olemassa X:ää, jolle pätee, että heikki on X:n vanhempi, siis isä tai äiti. Prolog ilmoittaa, että X:n arvolla ilkka, relaatio on tosi. Erikseen pyytämällä saamme prolog-tulkin kertomaan muutkin mahdolliset X:n arvot– tässä tapauksessa hilkka. Samalla tavalla saamme selville, että heikin vanhempia ovat liisa ja matti.
Muita sukulaisuussuhteita voidaan kuvata vastaavasti:
grand_mother(A,B):- mother(A,X), mother(X,B). grand_mother(A,B):- mother(A,X), father(X,B). sibling(A,B):- parent(X,A), parent(X,B), A \= B. cousin(A,B):- parent(X,A), parent(Z,X), parent(Z,Y), parent(Y,B), X \= Y.
Esimerkiksi suhteen isoäiti kuvaus voidaan lukea seuraavasti: A on B:n isoäiti, jos on olemassa A, B ja X siten, että A on X:n äiti ja X on B:n äiti. "," siis vastaa logiikan "ja"-operaattoria. Toinen vaihtoehto isoäitiydelle on esitetty seuraavalla rivillä. Relaatiossa sisaruus ehto A \= B varmistaa, että A ja B eivät ole sama henkilö vaan oikeasti sisaruksia. Kun koneita ohjelmoimaan tekemään loogisia päätelmiä, joku tämänkaltainen ihmiselle itsestäänselvä seikka jää helposti kertomatta. Näin yksinkertaisessa ohjelmassa virheen onneksi huomaa helposti ohjelman antamista ratkaisuista.
| ?- cousin(ilkka,C).
C = ritva ? a
C = jukka
| ?- cousin(C,ilkka).
C = ritva ? a
C = jukka
Prologissa tieto esitetään usein listoina. [kissa, koira, kana, lehma, lammas] on lista, jonka jäseninä on muutama kotieläin. Lista on järjestetty luettelo. Operaattorilla "|" voidaan erottaa listan ensimmäinen alkio listan loppuosasta.
listan_osat([Head|Tail],Head,Tail). | ?- listan_osat([kissa, kana, koira], Eka, Loput). Eka = kissa Loput = [kana,koira] yes | ?- listan_osat(Lista, kana, [koira,lammas]). Lista = [kana,koira,lammas] yes | ?- Elukat = [kissa|[kana,koira]]. Elukat = [kissa,kana,koira] yes | ?-
Prolog > Prolog ohjelmointikieli > Reititys (2016-2-13)
Reititys
Esimerkki reitin hakemisesta pisteestä A pisteeseen B.
Helmikuu 2016
Tarkastellaan kuvan mukaista "tiestöä", jossa on risteyksiä a:sta n:ään ja niitä yhdistäviä tieosuuksia. Teemme ohjelman, joka hakee reitin mistä hyvänsä pisteestä mihin hyvänsä toiseen pisteeseen.
Ensiksi kuvaamme tiestön prolog-ohjelmointikielellä:
vali(a,b,10). vali(a,c,20). vali(a,d,10). vali(b,m,50). vali(d,g,10). vali(d,h,10). vali(c,e,10). vali(c,f,30). vali(f,j,10). vali(f,i,15). vali(e,l,40). vali(e,k,25). vali(i,m,10). vali(i,k,5). vali(k,n,26). viereiset(A,B,L):- vali(A,B,L). viereiset(A,B,L):- vali(B,A,L).
Kuvaamme tiestön joukolla prolog-predikaatteja vali(A,B,L), missä A ja B ovat tiestön vierekkäisiä risteyksiä ja L niiden välinen matka. Prolog-kielessä muuttujien nimet alkavat isoilla kirjaimilla. (Prolog-ohjelmointikielen "käskyjä" kutsutaan predikaateiksi syystä, jota yritän selittää jutun lopussa.)
Predikaatilla viereiset kerromme, että vierekkäisyys on symmetrinen relaatio. Muuten joutuisimme kirjoittamaan esimerkiksi sekä vali(a,b,10) että vali(b,a,10).
Käynnistämme prolog-tulkin ja kokeilemme, toimiiko määrittelymme.
htv>gprolog GNU Prolog 1.4.4 (64 bits) Compiled Dec 17 2015, 21:30:59 with gcc By Daniel Diaz Copyright (C) 1999-2013 Daniel Diaz | ?- consult(['reititys.prolog']). compiling reititys.prolog for byte code... reititys.prolog compiled, 45 lines read - 4624 bytes written, 6 ms (4 ms) yes | ?- vali(a,B,L). B = b L = 10 ? ? Action (; for next solution, a for all solutions, RET to stop) ? a B = c L = 20 B = d L = 10 yes | ?- vali(X,a,L). no | ?-
Prolog-tulkki kertoo, että a:sta pääsee b:n ja matkaa on kymmenen kilometriä. Kun pyydämme nähtäväksi kaikki ratkaisut, tulkki luettelee myös yhteydet risteyksiin c ja d. Kyselyyn vali(X,a,L) ei löydy ratkaisua. Ikäänkuin mistään ei pääsisi risteykseen a, jos asiaa tulee kysyneeksi näin päin. Kokeillaanpa viereiset-predikaattia:
| ?- viereiset(a,X,L). L = 10 X = b ? a L = 20 X = c L = 10 X = d | ?- viereiset(X,a,L). L = 10 X = b ? a L = 20 X = c L = 10 X = d yes | ?-
Eli risteykseen a pääsee risteyksistä b, c ja d ja toisinpäin.
Seuraavassa teemme luetteloa risteyksistä, joiden kautta olemme ajaneet. Muistellaan ensin, miten listoja käsitellään. Merkintä [H|T] tarkoittaa, että listan T alkuun lisätään H:
| ?- T = [b,c,d], H = a, List = [H|T]. H = a List = [a,b,c,d] T = [b,c,d] yes | ?-
Määrittelemme predikaatin reitti(A,Z,Reitti), joka kuvaa reitin risteyksestä A risteykseen Z. Tarvitsemme apumuuttujan, johon kokoamme luettelon risteyksistä, joiden kautta olemme kulkeneet ja apumuuttujan, joka kertoo kulkemamme matkan. Seuraavalla "jipolla" kätkemme apumuuttujat "ulkopuolisilta". Laitamme alkupisteen kuljettujen risteysten luetteloon ja kuljetuksi matkaksi 0km. Prolog ymmärtää saman nimiset relaatiot eri relaatioiksi, jos niillä on eri määrä argumentteja. Olisimme voineet nimetä relaatiomme esimerkki reitti3 ja reitti5, mutta se ei ole tarpeen.
reitti(A,Z,Reitti):- reitti(A,Z,[A],0,Reitti).
Haemme reitin rekursiivisesti: Ajamme lähimpään risteykseen ja haemme reitin siitä loppuun. Jos joudumme umpikujaan, peruutamme hakemaan toista vaihtoehtoa. Prolog hoitaa "peruuttamisen" puolestamme, joten meidän ei tarvitse sitä ohjelmoida.
Jos loppumatkan alku- ja loppupiste ovat vierekkäiset, olemme viimeisen välin ajettuamme perillä maalissa. Kokonaismatka on tähän asti kuljettu matka Matka0 lisättynä viimeisen välin pituudella L. Koska =-merkki on prologissa varattu muuhun käyttöön, sijoituslauseessa käytetään operaattoria is– Matka is Matka0+L,. Kuljettujen risteysten luettelo on nurinkurisessa järjestyksessä viimeinen risteys ensimmäisenä, joten käännämme luettelon reverse-komennolla. Lopulliseksi "vastaukseksi" palautamme listan, jossa ensimmäisenä alkiona on matkan pituus ja toisena alkiona luettelo reittiin kuuluvista risteyksistä.
reitti(A,Z,Kuljetut,Matka0,[Matka,Reitti]):-
viereiset(A,Z,L),
Matka is Matka0+L,
reverse([Z|Kuljetut],Reitti).
Mikäli prolog-tulkki ei löydä perille yhdellä hypyllä, se kokeilee toista vaihtoehtoa:
reitti(A,Z,Kuljetut,Matka0,Reitti):-
viereiset(A,B,L),
\+ member(B,Kuljetut), % \+ tarkoittaa not
Matka is Matka0+L,
reitti(B,Z, [B|Kuljetut],Matka,Reitti).
Siirryttään johonkin A viereisistä risteyksistä B ja haetaan reitti B:stä maaliin. \+ member(B,Kuljetut),varmistaa, ettemme ole jo aiemmin kulkeneet B:n kautta– emme halua ajaa jäädä ajamaan ympyrää. Jos reittiä maaliin ei löydy, kokeillaan jotain muuta A:n viereisistä risteyksistä. Jos ne kaikki johtavat umpikujaan, peruteetaan kauemmas taaksepäin, sinne, mistä jouduttiin A:han. Peruuttamisista pitää huolen prolog-tulkin backtrace-toiminto.
| ?- reitti(g,j,GJ). GJ = [170,[g,d,a,b,m,i,k,e,c,f,j]] ? a GJ = [115,[g,d,a,b,m,i,f,j]] GJ = [105,[g,d,a,c,e,k,i,f,j]] GJ = [80,[g,d,a,c,f,j]]
Teemme vielä predikaatin, joka kerää kaikki reittivaihtoehdot yhteen listaan ja järjestää sen matkan pituuden mukaiseen järjestykseen.
reitit(A,Z,Reitit):-
findall(Reitti,reitti(A,Z,[A],0,Reitti),RR),
sort(RR,Reitit).
| ?- reitit(g,j,GJ). GJ = [[80,[g,d,a,c,f,j]],[105,[g,d,a,c,e,k,i,f,j]],[115,[g,d,a,b,m,i,f,j]],[170,[g,d,a,b,m,i,k,e,c,f,j]]] yes | ?- reitit(b,n,BN). BN = [[91,[b,a,c,e,k,n]],[91,[b,m,i,k,n]],[106,[b,a,c,f,i,k,n]],[166,[b,m,i,f,c,e,k,n]]]
Tällaisen hakualgoritmin voi tietysti ohjelmoida jollain prologia tutummalla ohjelmointikielellä. Prologilla,kun siihen tottuu, monet monimutkaiset ongelmat ratkeavat kuitenkin selkeämmin ja vähemmällä ohjelmoinnilla.
Hakualgoritmi näyttää houkuttelevan yksinkertaiselta. Ainakaan siinä ei ole kovin montaa riviä. Harmi kyllä tarkistettavien vaihtoehtojen määrä kasvaa paljon nopeammin kuin risteysten ja tienpätkien lukumäärä. Jos risteysten määrä kasvaa kymmenkertaiseksi, laskenta-aika ei kasva kymmenkertaiseksi vaan ehkä 3 potenssiin kymmenkertaiseksi. Jonain päivänä ehkä esittelen keinoja rajata hakua tämän tapaisissa tehtävissä. Ja ehkä minulla joskus on aikaa tehdä ohjelma, joka ei pelkästään hae reittejä pisteestä toiseen vaan myös piirtää ne.
/* Reititys */
vali(a,b,10).
vali(a,c,20).
vali(a,d,10).
vali(b,m,50).
vali(d,g,10).
vali(d,h,10).
vali(c,e,10).
vali(c,f,30).
vali(f,j,10).
vali(f,i,15).
vali(e,l,40).
vali(e,k,25).
vali(i,m,10).
vali(i,k,5).
vali(k,n,26).
viereiset(A,B,L):- vali(A,B,L).
viereiset(A,B,L):- vali(B,A,L).
reitti(A,Z,Reitti):-
reitti(A,Z,[A],0,Reitti).
reitti(A,Z,Kuljetut,Matka0,[Matka,Reitti]):-
viereiset(A,Z,L),
Matka is Matka0+L,
reverse([Z|Kuljetut],Reitti).
reitti(A,Z,Kuljetut,Matka0,Reitti):-
viereiset(A,B,L),
\+ member(B,Kuljetut), % \+ tarkoittaa not
Matka is Matka0+L,
reitti(B,Z, [B|Kuljetut],Matka,Reitti).
reitit(A,Z,Reitit):-
findall(Reitti,reitti(A,Z,[A],0,Reitti),RR),
sort(RR,Reitit).
Prolog > Prolog ohjelmointikieli > junarata.prolog (None)
junarata.prolog
Prolog > Prolog ohjelmointikieli > junarata.prolog > Junaratoja (None)
Junaratoja
% "asennettu-predikaatti on osa keskenjäänyttä yritystä tehostaa ratkaisujen hakua.
%:- dynamic(asennettu/4).
% kiskon palan pituus (siirtymä xy-koordinaatistossa), kääntymissuunta ja -kulma
kisko(suora, 220.0, 0.0).
kisko(vasen, L, Kulma):-
N = 8, % kaarrepalojen lukumäärä täydessä ympyrässä
D = 410.0, %kaarrepaloista rakennetun ympyrän halkaisija
Kulma is 2.0*pi/N,
L is D*sin(Kulma/2.0).
kisko(oikea, L, Kulma):-
N = 8, % kaarrepalojen lukumäärä täydessä ympyrässä
D = 410.0, %kaarrepaloista rakennetun ympyrän halkaisija
Kulma is -2.0*pi/N,
L is D*sin(-Kulma/2.0).
% rata-alueen rajat millimetreinä xy-koordinaatistossa.
% Tämän verran on lattialla tilaa. Rakentaminen aloitetaan pisteestä (0, 0)
alue(X, Y):-
X > -1000.0, X < 1000.0,
Y > -600.0, Y < 600.0.
% Radan piirtämisen avuksi
pikkukaarre(Kulma, L):-
N = 40,
D = 410.0,
Kulma is 2.0*pi/N,
L is D*sin(Kulma/2.0).
% Muut osat: Risteykset, sillat yms. pitäisi ottaa mukaan,
% jos haluaisi tehdä jotain käytännön kannalta mielenkiintoista.
% Nsuorat: Käytettävissä olevien suorien kiskojen lukumäärä
% Nkaarteet: Käytettävissä olevien kaarteiden lukumäärä
radat(Nsuorat, Nkaarteet):-
% retractall(asennettu/4),
% haetaan kaikki erilaiset radat
setof(Rata, rata(Nsuorat, Nkaarteet, Rata), Radat),
% seulotaan pois ne, jotka saa pyöräyttämällä jotain toista rataa
erilaiset(Radat, Eril),
nl,
length(Radat, M),
length(Eril, N),
write(['kaikki vs. erilaiset ', M, N]), nl,
kuvat(N),
piirraRadat(Eril, 1, Nsuorat, Nkaarteet).
% Ns0: käytettävissä olevien suorien kiskojen lukumäärä
% Nk0: käytettävissä olevien kaarrekiskojen lukumäärä
% Kiskot: Järjestetty luettelo käytetyistä kiskoista. Esim [suora, vasen, vasen, oikea, ...]
rata(Ns0, Nk0, [suora|Kiskot]):-
Ns0 > 0, !,
Ns is Ns0 - 1,
kisko(suora, L, Kulma),
kiskot(Kulma, L, 0.0, Ns, Nk0, Kiskot).
rata(0, Nk0, [vasen|Kiskot]):-
Nk is Nk0 - 1,
kisko(vasen, L, Kulma),
X is L*cos(Kulma),
Y is L*sin(Kulma),
kiskot(Kulma, X, Y, 0, Nk, Kiskot).
% kiskot(0.0, 0.0, 0.0, Ns, Nk, Rata).
kiskot(Kulma, X, Y, Ns, Nk, []):-
% Ollaanko origossa?
round(X) =:= 0.0,
round(Y) =:= 0.0,
Nk < 4,
Ns < 2,
% Onko tehty nolla (=kahdeksikko) tai useampi tasakierros vastapäivään?
kierrokset(Kulma),
% write([Nk, Ns, Kulma, X, Y]), nl,
% Laitetaan näytölle piste aina kun löydetään uusi ratkaisu
put_char('.'),
flush_output.
kiskot(Kulma0, X0, Y0, Ns0, Nk0, [Suunta|Kiskot]):-
Nk0 >= 0, Ns0 >= 0,
riittaakokaaret(Kulma0, Nk0),
riittaakokiskot(Nk0, Ns0, X0, Y0),
kisko(Suunta, L, DKulma),
kiskolkm(Suunta, Nk0, Ns0, Nk, Ns),
Kulma is Kulma0+DKulma,
X is X0+L*cos(Kulma),
Y is Y0+L*sin(Kulma),
alue(X, Y),
% overlap(X0, X, Y0, Y), (epäonnistunut/keskeneräinen yritys tehostaa hakua)
kiskot(Kulma, X, Y, Ns, Nk, Kiskot).
kiskolkm(suora, Nk0, Ns0, Nk0, Ns):- Ns is Ns0 - 1.
kiskolkm(oikea, Nk0, Ns0, Nk, Ns0):- Nk is Nk0 - 1.
kiskolkm(vasen, Nk0, Ns0, Nk, Ns0):- Nk is Nk0 - 1.
% Tavoite on 0 tai useampi kierros vastapäivään joten
% on turha mennä niin pitkälle myötäpäivään, että kaaret loppuvat
% kesken takaisinkääntymisen. (Vai rajaanko liikaa?)
riittaakokaaret(Kulma0, Nk0):-
Kulma0 + Nk0*pi/4.0 > -0.0001. % >=0 riittävä ehto
% Ollaanko niin kaukana, ettei ole mitään mahdollisuutta päästä alkupisteeseen.
riittaakokiskot(Nk, Ns, X, Y):-
kisko(suora, Ls, _),
kisko(vasen, Lk, _),
L is sqrt(X**2+Y**2),
Lmax is Ns*Ls + Nk*Lk,
L < 1.001*Lmax.
Keskeneräinen yritys rajata hakua. Ajatuksena oli välttää uuden kiskon asentaminen
aiemmin asennetun päälle.
Jokko ajatus tai toteutus on väärä.
overlap(X0, X, Y0, Y):-
Xr is round(X),
Yr is round(Y),
X0r is round(X0),
Y0r is round(Y0),
asennettu(X0r, Xr, Y0r, Yr), !, fail.
overlap(X0, X, Y0, Y):-
Xr is round(X),
Yr is round(Y),
X0r is round(X0),
Y0r is round(Y0),
asserta(asennettu(X0r, Xr, Y0r, Yr)).
overlap(X0, X, Y0, Y):-
Xr is round(X),
Yr is round(Y),
X0r is round(X0),
Y0r is round(Y0),
retract(asennettu(X0r, Xr, Y0r, Yr)).
kierrokset(Kulma):-
Kulma > -0.001, % Ei ole käännytty kierrostakaan negatiiviseen kiertosuuntaan
% kommentoi seuraava, jos haluat muutakin kuin kahdeksikkoja
Kulma < 0.001, % Ei ole käännytty kierrostakaan positiiviseen kiertosuuntaan
% Täyskierrokset: kulman ja 2*pi:n jakojäännös on lähellä nollaa
% Allaoleva ei ole välttämätön, jos ylläoleva ehto Kulma < 0.001 käytössä.
Jaannos is round(10.0*Kulma) rem round(20.0*pi),
Jaannos =:= 0.
% Rekursion lopetusehto: kaikki radat tarkastettu
% erilaisten ratkaisujen joukon alkuarvo on []
erilaiset([], []).
erilaiset([A1|An], Eril):-
length(A1, N), % N on radan pituus
% rotatoidaan enintään N-1 kertaa
rotate(A1, Ar, N),
% Onko rotatoitu sama, kuin joku jäljelläolevista radoista?
% ellei ole, member epäonnistuu ja ohjelma
% peruuttaa hakemaan rotatelta toista vaihtoehtoa
member(Ar, An), !,
% Jos löytyy samanlainen, tarkastellaan jäljellä olevia ratoja
erilaiset(An, Eril).
% Ellei löytynyt samanlaista, ylläoleva failaa ja
% tullaan tähän vaihtoehtoon.
% Lisätään rata A1 ratkaisujen joukkoon ja siirrytään tarkastelemaan
% jäljelläolevia
erilaiset([A1|An], [A1|Eril]):-
erilaiset(An, Eril), !.
rotate(A, B, _):- rotatelist(A, B).
rotate(A, B, N):-
N > 2,
M is N-1,
rotatelist(A, Ar),
rotate(Ar, B, M).
rotatelist([H|T], R):- append(T, [H], R).
demo:-
erilaiset([[a, a, b, b], [a, b, a, b], [a, b, b, a], [b, a, b, a]], B),
write(B), nl.
piirraRadat([], _, _, _).
piirraRadat([Rata1|Loput], M, Ns, Nk):-
piirraRata(Rata1, M, Ns, Nk), !,
N is M+1,
piirraRadat(Loput, N, Ns, Nk).
piirraRata(Rata, N, Ns, Nk):-
open('tmp.dat', write, Fil),
radanpisteet(Fil, 0, 0, 0, Rata, 5, Minx, Maxx, Miny, Maxy),
close(Fil),
% kasataan linux-komento
cmdline(Cmd, Minx, Maxx, Miny, Maxy, N, Ns, Nk),
% ja suoritetaan se. Jostain syystä popen toimii, mutta spawn ei.
popen(Cmd, write, Kuva),
close(Kuva).
% Viimeinenkin kisko käsitelty; rekursion loppu.
% Alkuarvo 0 x:n ja y:n ääriarvoille
radanpisteet(Fil, X, Y, Kulma, [], _, 0, 0, 0, 0):-
% pieni poikkiviiva kiskon loppuun
tick(Fil, X, Y, Kulma).
radanpisteet(Fil, X0, Y0, Kulma0, [suora|Loput], _, Minx, Maxx, Miny, Maxy):- !,
% pieni poikkiviiva kiskon alkuun
tick(Fil, X0, Y0, Kulma0),
kisko(suora, L, _),
X is X0 + L*cos(Kulma0),
Y is Y0 + L*sin(Kulma0),
tick(Fil, X, Y, Kulma0),
radanpisteet(Fil, X, Y, Kulma0, Loput, 5, Minx0, Maxx0, Miny0, Maxy0),
% toiminee myös: Minx = min(Minx0, X).
min_list([Minx0, X], Minx),
max_list([Maxx0, X], Maxx),
min_list([Miny0, Y], Miny),
max_list([Maxy0, Y], Maxy).
% Pikkukäännöksistä viimeinen
radanpisteet(Fil, X0, Y0, Kulma0, [vasen|Loput], 0, Minx, Maxx, Miny, Maxy):- !,
tick(Fil, X0, Y0, Kulma0),
radanpisteet(Fil, X0, Y0, Kulma0, Loput, 5, Minx, Maxx, Miny, Maxy).
% Pikkukäännös vasemmalle
radanpisteet(Fil, X0, Y0, Kulma0, [vasen|Loput], NPienetKaannokset, Minx, Maxx, Miny, Maxy):-
write(Fil, X0), write(Fil, ' '), write(Fil, Y0), nl(Fil),
pikkukaarre(DKulma, L),
Kulma is Kulma0+DKulma,
X is X0+L*cos(Kulma),
Y is Y0+L*sin(Kulma),
M is NPienetKaannokset-1,
radanpisteet(Fil, X, Y, Kulma, [vasen|Loput], M, Minx0, Maxx0, Miny0, Maxy0),
min_list([Minx0, X], Minx),
max_list([Maxx0, X], Maxx),
min_list([Miny0, Y], Miny),
max_list([Maxy0, Y], Maxy).
% Käännöksetn oikealle kuten vasemmallekin
radanpisteet(Fil, X0, Y0, Kulma0, [oikea|Loput], 0, Minx, Maxx, Miny, Maxy):- !,
tick(Fil, X0, Y0, Kulma0),
radanpisteet(Fil, X0, Y0, Kulma0, Loput, 5, Minx, Maxx, Miny, Maxy).
radanpisteet(Fil, X0, Y0, Kulma0, [oikea|Loput], NPienetKaannokset, Minx, Maxx, Miny, Maxy):- !,
write(Fil, X0), write(Fil, ' '), write(Fil, Y0), nl(Fil),
pikkukaarre(DKulma, L),
Kulma is Kulma0-DKulma,
X is X0+L*cos(Kulma),
Y is Y0+L*sin(Kulma),
M is NPienetKaannokset-1,
radanpisteet(Fil, X, Y, Kulma, [oikea|Loput], M, Minx0, Maxx0, Miny0, Maxy0),
min_list([Minx0, X], Minx),
max_list([Maxx0, X], Maxx),
min_list([Miny0, Y], Miny),
max_list([Maxy0, Y], Maxy).
tick(Fil, X, Y, Kulma):-
L is 25,
write(Fil, X), write(Fil, ' '), write(Fil, Y), nl(Fil),
X1 is X + L*sin(Kulma),
Y1 is Y - L*cos(Kulma),
write(Fil, X1), write(Fil, ' '), write(Fil, Y1), nl(Fil),
X2 is X - L*sin(Kulma),
Y2 is Y + L*cos(Kulma),
write(Fil, X2), write(Fil, ' '), write(Fil, Y2), nl(Fil),
write(Fil, X), write(Fil, ' '), write(Fil, Y), nl(Fil).
% Muodostetaan linux-komento radan piirtämistä varten
cmdline(Cmd, Minx0, Maxx0, Miny0, Maxy0, RadanNumero, Ns, Nk):-
Dx is abs(Minx0-Maxx0),
Dy is abs(Miny0-Maxy0),
Minx is 1.05*Minx0,
Miny is 1.05*Miny0,
% x- ja y-asteikon pitää olla samoja ettei kuva vääristy
D = max(Dx, Dy),
Maxx is D + Minx + 0.05*D,
Maxy is D + Miny + 0.05*D,
format_to_atom(Cmd,
'graph -h 0.8 -w 0.8 -u 0.1 -r 0.1 -T png -W 0.02 -L "max. ~d suoraa ja ~d kaarretta" --bg-color=yellowgreen -x ~f ~f -y ~f ~f tmp.dat > plotsTmp/plot~d.png',
[Ns, Nk, Minx, Maxx, Miny, Maxy, RadanNumero]).
% Apukomento
rc:- consult(['junarata.prolog', 'kuvat.prolog']).
rc1:- consult(['junarata.prolog']).
rc2:- consult(['kuvat.prolog']).
Selityksiä ylläolevaan
Lattialla on M kappaletta junaradan kaarteita ja N kappaleiden suoria kiskoja. Minkämuotoisia ratoja niistä voi rakentaa?
Huhtikuu 2016
Määritellään aluksi radan osien muoto. Meidän tarvitsee tietää suoran pituus jossain mittayksiköissä.Kaaresta meidän täytyy tietää pituus ja paljon yksi kaarre kääntää radan suuntaa. Tiedot saa helpoiten rakentamalla kaarrepaloista ympyrän ja mittaamalla sen halkaisijan radan keskipisteestä. Radan piirtämisen apuvälineeksi määrittelin vielä pikkukaarteen, eli kaarrepalan viidesosan.
Pienellä lisätyöllä ohjelmasta saisi yleispätevämmän niin, että valikoimaan olisi helppo lisätä muunkin laisia osia
Tämä viimeisin versio kelpuuttaa vain sellaiset radat, joissa kurvataan myötä- ja vastapäivään yhtä paljon, eli radat ovat jonkin tapaisia kahdeksikkoja.
# "asennettu-predikaatti on osa keskenjäänyttä yritystä tehostaa ratkaisujen hakua. # :- dynamic(asennettu/4). # kiskon palan pituus (siirtymä xy-koordinaatistossa), kääntymissuunta ja -kulma kisko(suora, 220.0, 0.0). kisko(vasen, L, Kulma):- N = 8, # kaarrepalojen lukumäärä täydessä ympyrässä D = 410.0, # kaarrepaloista rakennetun ympyrän halkaisija Kulma is 2.0*pi/N, L is D*sin(Kulma/2.0). kisko(oikea, L, Kulma):- N = 8, # kaarrepalojen lukumäärä täydessä ympyrässä D = 410.0, # kaarrepaloista rakennetun ympyrän halkaisija Kulma is -2.0*pi/N, L is D*sin(-Kulma/2.0). # rata-alueen rajat millimetreinä xy-koordinaatistossa. # Tämän verran on lattialla tilaa. Rakentaminen aloitetaan pisteestä (0, 0) alue(X, Y):- X > -1000.0, X < 1000.0, Y > -600.0, Y < 600.0. # Radan piirtämisen avuksi pikkukaarre(Kulma, L):- N = 40, D = 410.0, Kulma is 2.0*pi/N, L is D*sin(Kulma/2.0). # Muut osat: Risteykset, sillat yms. pitäisi ottaa mukaan, # jos haluaisi tehdä jotain käytännön kannalta mielenkiintoista.
Haetaan kaikki erilaiset vaihtoehtoiset radat. Ohjelma lähtee alkupisteestä (0, 0) kokeilemaan, millaisia kiskoja yhdistelemällä päästään takaisin alkupisteeseen ennen kuin käytettävissä olevat kiskot loppuvat. Ohjelma hakee kaikki erilaiset kombinaatiot. Harmi kyllä ohjelmani ensimmäinen vaihee katsoo erilaiseksi myös sellaiset vaihtoehdot, jotka saadaan pyöräyttämällä rataa.
Esimerkiksi kahdesta suorasta ja kahdeksasta kaaresta saa kaksi erilaista rataa: ympyrän tai kaksi puoliympyrää yhdistettynä kahdella suoralla. Ohjelmani mielestä seuraavat ovat erilaisia ratoja: 1) Aloitetaan suoralla, 2) aloitetaan kaarella ja lisätään sitten suora, 3) Aloitetaan kahdella kaarella ja lisätään sitten suora, 4) Aloitetaan neljällä kaarella ja laitetaan sitten suora. Todellisuudessa nämä tulevat kuviin vain eri asentoihin. Tein suodattimen, joka karsii tällaiset ratkaisut pois. Sellainen oli helppo ohjelmoida, mutta on laskennallisesti raskasta luoda valtavasti ratkaisuja ja karsia niistä sitten suurin osa pois. Turhien ratkaisujen määrä kasvanee eksponentiaalisesti käytettävissä olevien kiskojen lukumäärän funktiona.
# Nsuorat: Käytettävissä olevien suorien kiskojen lukumäärä # Nkaarteet: Käytettävissä olevien kaarteiden lukumäärä radat(Nsuorat, Nkaarteet):- # retractall(asennettu/4), # haetaan kaikki erilaiset radat setof(Rata, rata(Nsuorat, Nkaarteet, Rata), Radat), # seulotaan pois ne, jotka saa pyöräyttämällä jotain toista rataa erilaiset(Radat, Eril), nl, length(Radat, M), length(Eril, N), write(['kaikki vs. erilaiset ', M, N]), nl, kuvat(N), piirraRadat(Eril, 1, Nsuorat, Nkaarteet).
Suunnitellaan yksi kelvollinen rata. Aloitetaan origosta suuntaan 0 (=itään) ja lisätään rekursiivisesti kisko kerrallaan. Jos tarjolla on suoria kiskoja, aloitetaan sellaisella. Muuten otetaan kaarre vasempaan. Näillä valinnoilla rajoitetaan turhia saman näköisiä ratkaisuja.
# Ns0: käytettävissä olevien suorien kiskojen lukumäärä # Nk0: käytettävissä olevien kaarrekiskojen lukumäärä # Kiskot: Järjestetty luettelo käytetyistä kiskoista. Esim [suora, vasen, vasen, oikea, ...] rata(Ns0, Nk0, [suora|Kiskot]):- Ns0 > 0, !, Ns is Ns0 - 1, kisko(suora, L, Kulma), kiskot(Kulma, L, 0.0, Ns, Nk0, Kiskot). rata(0, Nk0, [vasen|Kiskot]):- Nk is Nk0 - 1, kisko(vasen, L, Kulma), X is L*cos(Kulma), Y is L*sin(Kulma), kiskot(Kulma, X, Y, 0, Nk, Kiskot). # kiskot(0.0, 0.0, 0.0, Ns, Nk, Rata).
Voimme lopettaa, jos 1) olemme palanneet origoon, 2) rintamasuuntamme on tehnyt yhden tai useamman täyden kierroksen niin, että kiskojen päät sopivat yhteen eikä 3) kiskoja ole ylen määrin jäljellä. Kaksi suoraa saa yleensä sovitettua rataan halkaisemalla sen sopivasta kohdasta. Neljä kaarretta saa lisättyä rataan vastaavaan tapaan kuin kaksi suoraa. Sen sijaan pitää hyväksyä, että yksi suora voi jäädä yli tai jopa kolme kaarretta, kun halutaan radasta umpinaiden.
Pyöristän x- ja y-koordinaatin kokonaisluvuksi ja tarkistan, olemmeko origossa. Kun käytän mittayksikkönä millimetrejä, tämä tarkoittaa, että ratojen pään pitää osua millilleen kohdalleen eli laskuissa ei saa kertyä paljoakaan virhettä. Vähempikin tarkkuus riittäisi.
Tämä on siis rekursion loppuehto. Prolog kokeilee eri vaihtoehtoja siinä järjestyksessä, kuin ne ovat koodissa, joten rekursion lopetusehdon pitää olla ensimmäisenä.
kiskot(Kulma, X, Y, Ns, Nk, []):- # Ollaanko origossa? round(X) =:= 0.0, round(Y) =:= 0.0, Nk < 4, Ns < 2, % Onko tehty nolla (=kahdeksikko) tai useampi tasakierros vastapäivään? kierrokset(Kulma), # write([Nk, Ns, Kulma, X, Y]), nl, # Laitetaan näytölle piste aina kun löydetään uusi ratkaisu put_char('.'), flush_output.
Kokeillaan lisätä kaari oikealle.
Esimerkiksi kahdeksasta kaaresta voi rakentaa ympyrän kääntymällä aina oikealle tai kääntymällä aina vasemmalle. Radat ovat toistensa peilikuvia eli käytännössä samanlaisia. Siksi kelpuutan vai radat, joissa tehdään nolla, yksi tai useampi kierros vasemmalle eli positiiviseen kiertosuuntaan eli vastapäivään. Kahdeksikko on rata, missä rintamasuunnaan muutos on loppujen lopuksi nolla.
kiskot(Kulma0, X0, Y0, Ns0, Nk0, [Suunta|Kiskot]):-
Nk0 >= 0, Ns0 >= 0,
riittaakokaaret(Kulma0, Nk0),
riittaakokiskot(Nk0, Ns0, X0, Y0),
kisko(Suunta, L, DKulma),
kiskolkm(Suunta, Nk0, Ns0, Nk, Ns),
Kulma is Kulma0+DKulma,
X is X0+L*cos(Kulma),
Y is Y0+L*sin(Kulma),
alue(X, Y),
# overlap(X0, X, Y0, Y), (epäonnistunut/keskeneräinen yritys tehostaa hakua)
kiskot(Kulma, X, Y, Ns, Nk, Kiskot).
kiskolkm(suora, Nk0, Ns0, Nk0, Ns):- Ns is Ns0 - 1.
kiskolkm(oikea, Nk0, Ns0, Nk, Ns0):- Nk is Nk0 - 1.
kiskolkm(vasen, Nk0, Ns0, Nk, Ns0):- Nk is Nk0 - 1.
# Tavoite on 0 tai useampi kierros vastapäivään joten
# on turha mennä niin pitkälle myötäpäivään, että kaaret loppuvat
# kesken takaisinkääntymisen. (Vai rajaanko liikaa?)
riittaakokaaret(Kulma0, Nk0):-
Kulma0 + Nk0*pi/4.0 > -0.0001. # >=0 riittävä ehto
# Ollaanko niin kaukana, ettei ole mitään mahdollisuutta päästä alkupisteeseen.
riittaakokiskot(Nk, Ns, X, Y):-
kisko(suora, Ls, _),
kisko(vasen, Lk, _),
L is sqrt(X**2+Y**2),
Lmax is Ns*Ls + Nk*Lk,
L < 1.001*Lmax.
Keskeneräinen yritys rajata hakua. Ajatuksena oli välttää uuden kiskon asentaminen
aiemmin asennetun päälle.
Jokko ajatus tai toteutus on väärä.
overlap(X0, X, Y0, Y):-
Xr is round(X),
Yr is round(Y),
X0r is round(X0),
Y0r is round(Y0),
asennettu(X0r, Xr, Y0r, Yr), !, fail.
overlap(X0, X, Y0, Y):-
Xr is round(X),
Yr is round(Y),
X0r is round(X0),
Y0r is round(Y0),
asserta(asennettu(X0r, Xr, Y0r, Yr)).
overlap(X0, X, Y0, Y):-
Xr is round(X),
Yr is round(Y),
X0r is round(X0),
Y0r is round(Y0),
retract(asennettu(X0r, Xr, Y0r, Yr)).
Tämä on osa sen tarkistamista, olemmeko saaneet yhden radan valmiiksi. Tarkistetaan, ollaanko tehty nolla, yksi tai useampi täysi kierros vastapäivään. Kulman pitää olla 2*π:n monikerta. Tämä toteutuu, jos kulma on suurempi kuin pieni negatiivinen luku ja jos jakojäännös kulma/π on nolla. Koska laskiessa saattaa kertyä pientä virhettä, ehto ei ehkä toteutuisi, vaikka kulma olisi melkein 2*π. Siksi kerron osoittajan ja nimittäjän kymmenellä ja pyöristän kokonaisluvuksi ennen jakojännöksen laskemista.
kierrokset(Kulma):-
Kulma > -0.001, # Ei ole käännytty kierrostakaan negatiiviseen kiertosuuntaan
# kommentoi seuraava, jos haluat muutakin kuin kahdeksikkoja
Kulma < 0.001, # Ei ole käännytty kierrostakaan positiiviseen kiertosuuntaan
# Täyskierrokset: kulman ja 2*pi:n jakojäännös on lähellä nollaa
# Allaoleva ei ole välttämätön, jos ylläoleva ehto Kulma < 0.001 käytössä.
Jaannos is round(10.0*Kulma) rem round(20.0*pi),
Jaannos =:= 0.
Karsitaan ne radat, jotka saadaan jostain toisesta pyöräyttämällä.
Rata esitetään listana. Esimerkiksi [vasen, vasen, vasen, vasen, suora, vasen, vasen, vasen, vasen, suora] on rata, jossa kaksi puoliympyrää on yhdistetty kahdella suoralla. Sen kanssa yhdenmuotoinen on rata [vasen, vasen, vasen, suora, vasen, vasen, vasen, vasen, suora, vasen]. Jälkimmäisen saamme edellisestä rotatoimalla sen, eri siirtämällä ensimmäisen alkion viimeiseksi.
Seuraavassa kutakin rataa rotatoidaan ja tarkistetaan, onko se rotatoituna saman lainen kuin joku joku muista radoista. Ellei ole, rotatoidaan uudestaan niin monta kerta, kuin radassa on kiskoja. Ellei löydy samanlaista, se saa jäädä kokoelmaan, muuten se karsitaan.
# Rekursion lopetusehto: kaikki radat tarkastettu # erilaisten ratkaisujen joukon alkuarvo on [] erilaiset([], []). erilaiset([A1|An], Eril):- length(A1, N), # N on radan pituus # rotatoidaan enintään N-1 kertaa rotate(A1, Ar, N), # Onko rotatoitu sama, kuin joku jäljelläolevista radoista? # ellei ole, member epäonnistuu ja ohjelma # peruuttaa hakemaan rotatelta toista vaihtoehtoa member(Ar, An), !, # Jos löytyy samanlainen, tarkastellaan jäljellä olevia ratoja erilaiset(An, Eril). # Ellei löytynyt samanlaista, ylläoleva failaa ja # tullaan tähän vaihtoehtoon. # Lisätään rata A1 ratkaisujen joukkoon ja siirrytään tarkastelemaan # jäljelläolevia erilaiset([A1|An], [A1|Eril]):- erilaiset(An, Eril), !. rotate(A, B, _):- rotatelist(A, B). rotate(A, B, N):- N > 2, M is N-1, rotatelist(A, Ar), rotate(Ar, B, M). rotatelist([H|T], R):- append(T, [H], R).
Pieni esimerkki prologin rekursiosta.
demo:-
erilaiset([[a, a, b, b], [a, b, a, b], [a, b, b, a], [b, a, b, a]], B),
write(B), nl.
Pyysin prolog-tulkkia kertomaan, miten se kutsuu predikaatteja rotatelist, rotate ja member suorittaessaan ylläolevaa demo predikaattia.
?- spy([rotatelist, rotate, member]).
Spypoint placed on rotatelist/2
Spypoint placed on rotate/3
Spypoint placed on member/2
The debugger will first leap -- showing spypoints (debug)
| ?- demo.
+ 4 3 Call: rotate([a, a, b, b], _176, 4) ? l
+ 5 4 Call: rotatelist([a, a, b, b], _200) ? l
+ 5 4 Exit: rotatelist([a, a, b, b], [a, b, b, a]) ? l
+ 4 3 Exit: rotate([a, a, b, b], [a, b, b, a], 4) ? l
+ 7 3 Call: member([a, b, b, a], [[a, b, a, b], [a, b, b, a], [b, a, b, a]]) ? l
+ 7 3 Exit: member([a, b, b, a], [[a, b, a, b], [a, b, b, a], [b, a, b, a]]) ? l
+ 10 4 Call: rotate([a, b, a, b], _335, 4) ? l
+ 11 5 Call: rotatelist([a, b, a, b], _359) ? l
+ 11 5 Exit: rotatelist([a, b, a, b], [b, a, b, a]) ? l
+ 10 4 Exit: rotate([a, b, a, b], [b, a, b, a], 4) ? l
+ 13 4 Call: member([b, a, b, a], [[a, b, b, a], [b, a, b, a]]) ? l
+ 13 4 Exit: member([b, a, b, a], [[a, b, b, a], [b, a, b, a]]) ? l
+ 16 5 Call: rotate([a, b, b, a], _494, 4) ? l
+ 17 6 Call: rotatelist([a, b, b, a], _518) ? l
+ 17 6 Exit: rotatelist([a, b, b, a], [b, b, a, a]) ? l
+ 16 5 Exit: rotate([a, b, b, a], [b, b, a, a], 4) ? l
+ 19 5 Call: member([b, b, a, a], [[b, a, b, a]]) ? l
+ 19 5 Fail: member([b, b, a, a], [[b, a, b, a]]) ? l
+ 16 5 Redo: rotate([a, b, b, a], [b, b, a, a], 4) ? l
+ 19 6 Call: rotatelist([a, b, b, a], _571) ? l
+ 19 6 Exit: rotatelist([a, b, b, a], [b, b, a, a]) ? l
+ 21 6 Call: rotate([b, b, a, a], _631, 3) ? l
+ 22 7 Call: rotatelist([b, b, a, a], _655) ? l
+ 22 7 Exit: rotatelist([b, b, a, a], [b, a, a, b]) ? l
+ 21 6 Exit: rotate([b, b, a, a], [b, a, a, b], 3) ? l
+ 16 5 Exit: rotate([a, b, b, a], [b, a, a, b], 4) ? l
+ 24 5 Call: member([b, a, a, b], [[b, a, b, a]]) ? l
+ 24 5 Fail: member([b, a, a, b], [[b, a, b, a]]) ? l
+ 16 5 Redo: rotate([a, b, b, a], [b, a, a, b], 4) ? l
+ 21 6 Redo: rotate([b, b, a, a], [b, a, a, b], 3) ? l
+ 24 7 Call: rotatelist([b, b, a, a], _708) ? l
+ 24 7 Exit: rotatelist([b, b, a, a], [b, a, a, b]) ? l
+ 26 7 Call: rotate([b, a, a, b], _768, 2) ? l
+ 27 8 Call: rotatelist([b, a, a, b], _792) ? l
+ 27 8 Exit: rotatelist([b, a, a, b], [a, a, b, b]) ? l
+ 26 7 Exit: rotate([b, a, a, b], [a, a, b, b], 2) ? l
+ 21 6 Exit: rotate([b, b, a, a], [a, a, b, b], 3) ? l
+ 16 5 Exit: rotate([a, b, b, a], [a, a, b, b], 4) ? l
+ 29 5 Call: member([a, a, b, b], [[b, a, b, a]]) ? l
+ 29 5 Fail: member([a, a, b, b], [[b, a, b, a]]) ? l
+ 16 5 Redo: rotate([a, b, b, a], [a, a, b, b], 4) ? l
+ 21 6 Redo: rotate([b, b, a, a], [a, a, b, b], 3) ? l
+ 26 7 Redo: rotate([b, a, a, b], [a, a, b, b], 2) ? l
+ 26 7 Fail: rotate([b, a, a, b], _756, 2) ? l
+ 21 6 Fail: rotate([b, b, a, a], _619, 3) ? l
+ 16 5 Fail: rotate([a, b, b, a], _482, 4) ? l
+ 17 6 Call: rotate([b, a, b, a], _520, 4) ? l
+ 18 7 Call: rotatelist([b, a, b, a], _544) ? l
+ 18 7 Exit: rotatelist([b, a, b, a], [a, b, a, b]) ? l
+ 17 6 Exit: rotate([b, a, b, a], [a, b, a, b], 4) ? l
+ 20 6 Call: member([a, b, a, b], []) ? l
+ 20 6 Fail: member([a, b, a, b], []) ? l
+ 17 6 Redo: rotate([b, a, b, a], [a, b, a, b], 4) ? l
+ 20 7 Call: rotatelist([b, a, b, a], _597) ? l
+ 20 7 Exit: rotatelist([b, a, b, a], [a, b, a, b]) ? l
+ 22 7 Call: rotate([a, b, a, b], _657, 3) ? l
+ 23 8 Call: rotatelist([a, b, a, b], _681) ? l
+ 23 8 Exit: rotatelist([a, b, a, b], [b, a, b, a]) ? l
+ 22 7 Exit: rotate([a, b, a, b], [b, a, b, a], 3) ? l
+ 17 6 Exit: rotate([b, a, b, a], [b, a, b, a], 4) ? l
+ 25 6 Call: member([b, a, b, a], []) ? l
+ 25 6 Fail: member([b, a, b, a], []) ? l
+ 17 6 Redo: rotate([b, a, b, a], [b, a, b, a], 4) ? l
+ 22 7 Redo: rotate([a, b, a, b], [b, a, b, a], 3) ? l
+ 25 8 Call: rotatelist([a, b, a, b], _734) ? l
+ 25 8 Exit: rotatelist([a, b, a, b], [b, a, b, a]) ? l
+ 27 8 Call: rotate([b, a, b, a], _794, 2) ? l
+ 28 9 Call: rotatelist([b, a, b, a], _818) ? l
+ 28 9 Exit: rotatelist([b, a, b, a], [a, b, a, b]) ? l
+ 27 8 Exit: rotate([b, a, b, a], [a, b, a, b], 2) ? l
+ 22 7 Exit: rotate([a, b, a, b], [a, b, a, b], 3) ? l
+ 17 6 Exit: rotate([b, a, b, a], [a, b, a, b], 4) ? l
+ 30 6 Call: member([a, b, a, b], []) ? l
+ 30 6 Fail: member([a, b, a, b], []) ? l
+ 17 6 Redo: rotate([b, a, b, a], [a, b, a, b], 4) ? l
+ 22 7 Redo: rotate([a, b, a, b], [a, b, a, b], 3) ? l
+ 27 8 Redo: rotate([b, a, b, a], [a, b, a, b], 2) ? l
+ 27 8 Fail: rotate([b, a, b, a], _782, 2) ? l
+ 22 7 Fail: rotate([a, b, a, b], _645, 3) ? l
+ 17 6 Fail: rotate([b, a, b, a], _508, 4) ? l
[[a, b, b, a], [b, a, b, a]]
(8 ms) yes
{debug}
Siirrytään piirtämään ratoja.
Prolog-kielessä !-merkki tarkoittaa, että jos ohjelma pääsee kyseisen kohdan yli, se ei enää peruuta sen yli takaisin hakemaan muita vaihtoehtoja. !-merkkiä kannattaa käyttää vain huolella harkituissa erikoistilanteissa. Tässä tapauksessa voin käyttää sitä, koska tiedän, että kunkin radan voi piirtää vain yhdellä tavalla. Hyötynä !-merkin käytöstä on, että prolog-tulkin ei tarvitse pitää muistissa !-merkin takaisia vaihtoehtoja.
piirraRadat([], _, _, _).
piirraRadat([Rata1|Loput], M, Ns, Nk):-
piirraRata(Rata1, M, Ns, Nk), !,
N is M+1,
piirraRadat(Loput, N, Ns, Nk).
Kirjoitetaan kunkin kiskon alkupisteiden koordinaatit tilapäistiedostoon. Kaarteista kirjoitetaan lisäksi neljän välipisteen koordinaatit. Kiskon liitoskohtiin piirretään vielä poikkiviiva kuvion hahmottamisen helpottamiseksi. Piirroksen skaalaamiseksi haetaan samalla x- ja y-arvojen pienimmät ja suurimmat arvot. Piirtämiseen käytän linuxin graph-komentoa, joka on tarkoitettu 2D-kuvaajien piirtämiseen.
piirraRata(Rata, N, Ns, Nk):-
open('tmp.dat', write, Fil),
radanpisteet(Fil, 0, 0, 0, Rata, 5, Minx, Maxx, Miny, Maxy),
close(Fil),
# kasataan linux-komento
cmdline(Cmd, Minx, Maxx, Miny, Maxy, N, Ns, Nk),
# ja suoritetaan se. Jostain syystä popen toimii, mutta spawn ei.
popen(Cmd, write, Kuva),
close(Kuva).
Radan pisteiden laskeminen on pitkälti radan suunnittelun toisintoa. Eroina on se, että pisteitä ei kerätä listaan vaan kirjoitetaan tiedostoon ja se, että lasketaan x.lle ja y:lle ääriarvot.
Kaarien välipisteiden laskeminen on ehkä vähän hämmentävää. Lisälaskurin avulla tehdään yhden ison sijasta viisi pientä käännöstä.
# Viimeinenkin kisko käsitelty; rekursion loppu. # Alkuarvo 0 x:n ja y:n ääriarvoille radanpisteet(Fil, X, Y, Kulma, [], _, 0, 0, 0, 0):- # pieni poikkiviiva kiskon loppuun tick(Fil, X, Y, Kulma). radanpisteet(Fil, X0, Y0, Kulma0, [suora|Loput], _, Minx, Maxx, Miny, Maxy):- !, # pieni poikkiviiva kiskon alkuun tick(Fil, X0, Y0, Kulma0), kisko(suora, L, _), X is X0 + L*cos(Kulma0), Y is Y0 + L*sin(Kulma0), tick(Fil, X, Y, Kulma0), radanpisteet(Fil, X, Y, Kulma0, Loput, 5, Minx0, Maxx0, Miny0, Maxy0), # toiminee myös: Minx = min(Minx0, X). min_list([Minx0, X], Minx), max_list([Maxx0, X], Maxx), min_list([Miny0, Y], Miny), max_list([Maxy0, Y], Maxy). # Pikkukäännöksistä viimeinen radanpisteet(Fil, X0, Y0, Kulma0, [vasen|Loput], 0, Minx, Maxx, Miny, Maxy):- !, tick(Fil, X0, Y0, Kulma0), radanpisteet(Fil, X0, Y0, Kulma0, Loput, 5, Minx, Maxx, Miny, Maxy). # Pikkukäännös vasemmalle radanpisteet(Fil, X0, Y0, Kulma0, [vasen|Loput], NPienetKaannokset, Minx, Maxx, Miny, Maxy):- write(Fil, X0), write(Fil, ' '), write(Fil, Y0), nl(Fil), pikkukaarre(DKulma, L), Kulma is Kulma0+DKulma, X is X0+L*cos(Kulma), Y is Y0+L*sin(Kulma), M is NPienetKaannokset-1, radanpisteet(Fil, X, Y, Kulma, [vasen|Loput], M, Minx0, Maxx0, Miny0, Maxy0), min_list([Minx0, X], Minx), max_list([Maxx0, X], Maxx), min_list([Miny0, Y], Miny), max_list([Maxy0, Y], Maxy). # Käännöksetn oikealle kuten vasemmallekin radanpisteet(Fil, X0, Y0, Kulma0, [oikea|Loput], 0, Minx, Maxx, Miny, Maxy):- !, tick(Fil, X0, Y0, Kulma0), radanpisteet(Fil, X0, Y0, Kulma0, Loput, 5, Minx, Maxx, Miny, Maxy). radanpisteet(Fil, X0, Y0, Kulma0, [oikea|Loput], NPienetKaannokset, Minx, Maxx, Miny, Maxy):- !, write(Fil, X0), write(Fil, ' '), write(Fil, Y0), nl(Fil), pikkukaarre(DKulma, L), Kulma is Kulma0-DKulma, X is X0+L*cos(Kulma), Y is Y0+L*sin(Kulma), M is NPienetKaannokset-1, radanpisteet(Fil, X, Y, Kulma, [oikea|Loput], M, Minx0, Maxx0, Miny0, Maxy0), min_list([Minx0, X], Minx), max_list([Maxx0, X], Maxx), min_list([Miny0, Y], Miny), max_list([Maxy0, Y], Maxy). tick(Fil, X, Y, Kulma):- L is 25, write(Fil, X), write(Fil, ' '), write(Fil, Y), nl(Fil), X1 is X + L*sin(Kulma), Y1 is Y - L*cos(Kulma), write(Fil, X1), write(Fil, ' '), write(Fil, Y1), nl(Fil), X2 is X - L*sin(Kulma), Y2 is Y + L*cos(Kulma), write(Fil, X2), write(Fil, ' '), write(Fil, Y2), nl(Fil), write(Fil, X), write(Fil, ' '), write(Fil, Y), nl(Fil). # Muodostetaan linux-komento radan piirtämistä varten cmdline(Cmd, Minx0, Maxx0, Miny0, Maxy0, RadanNumero, Ns, Nk):- Dx is abs(Minx0-Maxx0), Dy is abs(Miny0-Maxy0), Minx is 1.05*Minx0, Miny is 1.05*Miny0, # x- ja y-asteikon pitää olla samoja ettei kuva vääristy D = max(Dx, Dy), Maxx is D + Minx + 0.05*D, Maxy is D + Miny + 0.05*D, format_to_atom(Cmd, 'graph -h 0.8 -w 0.8 -u 0.1 -r 0.1 -T png -W 0.02 -L "max. ~d suoraa ja ~d kaarretta" --bg-color=yellowgreen -x ~f ~f -y ~f ~f tmp.dat > plotsTmp/plot~d.png', [Ns, Nk, Minx, Maxx, Miny, Maxy, RadanNumero]). # Apukomento rc:- consult(['junarata.prolog', 'kuvat.prolog']). rc1:- consult(['junarata.prolog']). rc2:- consult(['kuvat.prolog']).
Lataa tästä ohjelman tämän hetkinen versio: junarata_0.prolog
Fri Oct 8 09:19:17 2021