Sisällysluettelo

Prolog

Loo­gi­seen päät­te­lyyn ky­ke­ne­vä oh­jel­moin­ti­kieli


Heikin pohteita > Ohjelmointia, matematiikkaa, fysiikkaa … > Prolog > Prolog ohjelmointikieli (edit: 2016-2-13)

Prolog oh­jel­moin­ti­kieli

Esi­tän pari esi­merk­kiä 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.

Helmi­kuu 2016

Käy­tän näis­sä esi­mer­keis­sä gnu-prologia ja swipl-prologia, mutta tar­jol­la on monia mui­ta­kin prolog-implementaatioita.

Olen myös yrit­tä­nyt tehdä pro­lo­gil­la mu­siik­kia .


Heikin pohteita > Ohjelmointia, matematiikkaa, fysiikkaa … > Prolog > Prolog ohjelmointikieli > Lyhyt esittely (edit: 2016-2-14)

Lyhyt esit­te­ly

Tammi­kuu 2016

Seu­raa­vas­sa tu­tus­tum­me pro­lo­giin te­ke­mäl­lä päät­te­lyi­tä su­ku­lai­suus­suh­teis­ta. Su­ku­lai­suus­suh­teet on ku­vat­tu pro­lo­gil­la seu­raa­vas­ti: 

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).

pro­lo­gis­sa va­kiot kir­joi­te­taan pie­nel­lä kir­jai­mel­la ja muut­tu­jat isol­la. Isol­la kir­jai­mel­la al­ka­vat va­kiot pitää kir­joit­taa lai­naus­merk­kei­hin, esi­mer­kik­si 'Eila'. Kirjoitin kuitenkin ihmisten nimet pienellä, koska en jaksanut näpytellä lainausmerkkejä ja ne olisivat ehkä johtaneet lukijaa harhaan.

Asioi­den vä­lis­ten suh­tei­den nimet– kuten mother ja father– kirjoitetaan myös pienellä.

Päät­te­lyi­den hel­pot­ta­mi­sek­si mää­rit­te­lem­me, mil­lai­nen su­ku­lai­suus­suhde on van­hem­pi– parent. 

parent(A,B):- mother(A,B).
parent(A,B):- father(A,B).

Pro­lo­gin "ko­men­to­ja" kut­su­taan pre­di­kaa­teik­si. Prolog-ohjelmaa voi lukea kuin lo­gii­kan kie­lel­lä kir­joi­tet­tua ku­vaus­ta tosi­asiois­ta ja nii­den vä­li­sis­tä suh­teis­ta. Ylläolevan ku­vauk­sen su­ku­lai­suus­suh­tees­ta 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(heik­ki,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

heik­ki on ilkan van­hem­pi, koska on ole­mas­sa tosi­asia father(heik­ki,ilkka). Ole­tus­ar­voi­ses­ti prolog vas­taa ky­sy­myk­seen, onko ole­mas­sa X:ää, jolle pätee, että heik­ki on X:n van­hem­pi, siis isä tai äiti. Prolog il­moit­taa, että X:n ar­vol­la ilkka, re­laa­tio on tosi. Erik­seen pyy­tä­mäl­lä saam­me prolog-tulkin ker­to­maan muut­kin mah­dol­li­set X:n arvot– tässä ta­pauk­ses­sa hilk­ka. Sa­mal­la ta­val­la saam­me sel­vil­le, että hei­kin van­hem­pia ovat liisa ja matti.

Muita su­ku­lai­suus­suh­tei­ta voi­daan ku­va­ta vas­taa­vas­ti: 

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.

Esi­mer­kik­si suh­teen iso­äiti ku­vaus voi­daan lukea seu­raa­vas­ti: A on B:n iso­äiti, jos on ole­mas­sa A, B ja X siten, että A on X:n äiti ja X on B:n äiti. "," siis vas­taa lo­gii­kan "ja"-o­pe­raat­to­ria. Toi­nen vaih­to­ehto iso­äi­tiy­del­le on esi­tet­ty seu­raa­val­la ri­vil­lä. Re­laa­tios­sa si­sa­ruus 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

Pro­lo­gis­sa tieto esi­te­tään usein lis­toi­na. [kissa, koira, kana, lehma, lam­mas] 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
| ?-

Heikin pohteita > Ohjelmointia, matematiikkaa, fysiikkaa … > Prolog > Prolog ohjelmointikieli > Reititys (edit: 2016-2-13)

Rei­ti­tys

Esi­merk­ki rei­tin ha­ke­mi­ses­ta pis­tees­tä A pis­tee­seen B.

Helmi­kuu 2016

../xml/Programming/Prolog_swipl/reitit.png
Ris­teyk­set a..n ja niiden väliset tieosuudet 

Tar­kas­tel­laan kuvan mu­kais­ta "ties­töä", jossa on ris­teyk­siä a:sta n:ään ja niitä yhdistäviä tieosuuksia. Teemme ohjelman, joka hakee reitin mistä hyvänsä pisteestä mihin hyvänsä toiseen pisteeseen.

En­sik­si ku­vaam­me ties­tö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).

Ku­vaam­me ties­tön jou­kol­la 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.)

Pre­di­kaa­til­la vie­rei­set ker­rom­me, että vie­rek­käi­syys on sym­met­ri­nen re­laa­tio. Muu­ten jou­tui­sim­me kir­joit­ta­maan esi­mer­kik­si sekä vali(a,b,10) että vali(b,a,10).

Käyn­nis­täm­me prolog-tulkin ja ko­kei­lem­me, toi­mii­ko mää­rit­te­lym­me. 

  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 ker­too, että a:sta pää­see b:n ja mat­kaa on kym­me­nen kilo­met­riä. Kun pyy­däm­me näh­tä­väk­si kaik­ki rat­kai­sut, tulk­ki luet­te­lee myös yh­tey­det ris­teyk­siin c ja d. Ky­se­lyyn 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 ris­teyk­seen a pää­see ris­teyk­sis­tä b, c ja d ja toi­sin­päin.

Seu­raa­vas­sa teem­me luet­te­loa ris­teyk­sis­tä, joi­den kaut­ta olem­me aja­neet. Muis­tel­laan ensin, miten lis­to­ja kä­si­tel­lään. Mer­kin­tä [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ää­rit­te­lem­me pre­di­kaa­tin reit­ti(A,Z,Reit­ti), 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).

Haem­me rei­tin re­kur­sii­vi­ses­ti: Ajam­me lä­him­pään ris­teyk­seen ja haem­me rei­tin siitä lop­puun. Jos jou­dum­me umpi­ku­jaan, pe­ruu­tam­me ha­ke­maan tois­ta vaih­to­ehtoa. Prolog hoi­taa "pe­ruut­ta­mi­sen" puo­les­tam­me, joten mei­dän ei tar­vit­se sitä oh­jel­moi­da.

Jos loppu­mat­kan alku- ja loppu­piste ovat vie­rek­käi­set, olem­me vii­mei­sen välin ajet­tuam­me pe­ril­lä maa­lis­sa. Koko­nais­matka on tähän asti kul­jet­tu 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).

Mi­kä­li prolog-tulkki ei löydä pe­ril­le yh­del­lä hy­pyl­lä, se ko­kei­lee tois­ta vaih­to­ehtoa: 

  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 jo­hon­kin A vie­rei­sis­tä ris­teyk­sis­tä B ja hae­taan reit­ti B:stä maa­liin. \+ member(B,Kul­je­tut),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]]

Teem­me vielä pre­di­kaa­tin, joka kerää kaik­ki reit­ti­vaih­to­ehdot yh­teen lis­taan ja jär­jes­tää sen mat­kan pi­tuu­den mu­kai­seen jär­jes­tyk­seen. 

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äl­lai­sen haku­al­go­rit­min voi tie­tys­ti oh­jel­moi­da jol­lain pro­lo­gia tu­tum­mal­la oh­jel­moin­ti­kie­lel­lä. Pro­lo­gil­la,kun sii­hen tot­tuu, monet moni­mut­kai­set on­gel­mat rat­kea­vat kui­ten­kin sel­keäm­min ja vä­hem­mäl­lä oh­jel­moin­nil­la.

Haku­al­go­rit­mi näyt­tää hou­kut­te­le­van yksin­ker­tai­sel­ta. Ai­na­kaan siinä ei ole kovin mon­taa riviä. Harmi kyllä tar­kis­tet­ta­vien vaih­to­eh­to­jen määrä kas­vaa pal­jon no­peam­min kuin ris­teys­ten ja tien­pät­kien luku­määrä. Jos ris­teys­ten määrä kas­vaa kym­men­ker­tai­sek­si, las­ken­ta-aika ei kasva kym­men­ker­tai­sek­si vaan ehkä 3 po­tens­siin kym­men­ker­tai­sek­si. Jo­nain päi­vä­nä ehkä esit­te­len kei­no­ja ra­ja­ta hakua tämän ta­pai­sis­sa teh­tä­vis­sä. Ja ehkä mi­nul­la jos­kus on aikaa tehdä oh­jel­ma, joka ei pel­käs­tään hae reit­te­jä pis­tees­tä toi­seen vaan myös piir­tää 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).

Ylläoleva reititys-ohjelman koodi .


Heikin pohteita > Ohjelmointia, matematiikkaa, fysiikkaa … > Prolog > Prolog ohjelmointikieli > junarata.prolog (edit: )

junarata.prolog


Heikin pohteita > Ohjelmointia, matematiikkaa, fysiikkaa … > Prolog > Prolog ohjelmointikieli > junarata.prolog > Junaratoja (edit: )

Juna­ra­to­ja 

% "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']).

Se­li­tyk­siä ylläolevaan

Lat­tial­la on M kap­pa­let­ta juna­radan kaar­tei­ta ja N kap­pa­lei­den suo­ria kis­ko­ja. Minkämuotoisia ra­to­ja niis­tä voi ra­ken­taa?

Huhti­kuu 2016

Mää­ri­tel­lään aluk­si radan osien muoto. Mei­dän tar­vit­see tie­tää suo­ran pi­tuus jos­sain mittayksiköissä.Kaaresta mei­dän täy­tyy tie­tää pi­tuus ja pal­jon yksi kaar­re kään­tää radan suun­taa. Tie­dot saa hel­poi­ten ra­ken­ta­mal­la kaar­re­pa­lois­ta ym­py­rän ja mit­taa­mal­la sen hal­kai­si­jan radan keski­pis­tees­tä. Radan piir­tä­mi­sen apu­vä­li­neek­si mää­rit­te­lin vielä pikku­kaar­teen, eli kaar­re­palan vii­des­osan.

Pie­nel­lä lisä­työl­lä oh­jel­mas­ta saisi yleis­pä­te­väm­män niin, että va­li­koi­maan olisi help­po li­sä­tä muun­kin lai­sia osia

Tämä vii­mei­sin ver­sio kel­puut­taa vain sel­lai­set radat, jois­sa kur­va­taan myö­tä- ja vasta­päi­vään yhtä pal­jon, eli radat ovat jon­kin ta­pai­sia kah­dek­sik­ko­ja. 


 #  "asennettu-predikaatti on osa kes­ken­jää­nyt­tä yri­tys­tä te­hos­taa rat­kai­su­jen hakua.
 # :- dynamic(asen­net­tu/4).

 #  kis­kon palan pi­tuus (siir­ty­mä xy-koordinaatistossa), kään­ty­mis­suun­ta ja -kul­ma

kisko(suora, 220.0, 0.0).
kisko(vasen, L, Kulma):-
    N = 8, #  kaar­re­pa­lo­jen luku­määrä täy­des­sä ym­py­räs­sä
    D = 410.0, # kaar­re­pa­lois­ta ra­ken­ne­tun ym­py­rän hal­kai­si­ja
    Kulma is 2.0*pi/N,
    L is D*sin(Kulma/2.0).
kisko(oikea, L, Kulma):-
    N = 8, #  kaar­re­pa­lo­jen luku­määrä täy­des­sä ym­py­räs­sä
    D = 410.0, # kaar­re­pa­lois­ta ra­ken­ne­tun ym­py­rän hal­kai­si­ja
    Kulma is -2.0*pi/N,
    L is D*sin(-Kulma/2.0).

 #  rata-alueen rajat milli­met­rei­nä xy-koordinaatistossa.
 #  Tämän ver­ran on lat­tial­la tilaa. Ra­ken­ta­mi­nen aloi­te­taan pis­tees­tä (0, 0)
alue(X, Y):-
    X > -1000.0,  X < 1000.0,
    Y > -600.0,  Y < 600.0.

 #  Radan piir­tä­mi­sen avuk­si
pikkukaarre(Kulma, L):-
    N = 40,
    D = 410.0,
    Kulma is 2.0*pi/N,
    L is D*sin(Kulma/2.0).

 #  Muut osat: Ris­teyk­set, sil­lat yms. pi­täi­si ottaa mu­kaan,
 #    jos ha­luai­si tehdä jo­tain käy­tän­nön kan­nal­ta mie­len­kiin­tois­ta.

Hae­taan kaik­ki eri­lai­set vaih­to­eh­toi­set radat. Oh­jel­ma läh­tee alku­pis­tees­tä (0, 0) ko­kei­le­maan, mil­lai­sia kis­ko­ja yh­dis­te­le­mäl­lä pääs­tään ta­kai­sin alku­pis­tee­seen ennen kuin käy­tet­tä­vis­sä ole­vat kis­kot lop­pu­vat. Oh­jel­ma hakee kaik­ki eri­lai­set kom­bi­naa­tiot. Harmi kyllä oh­jel­ma­ni en­sim­mäi­nen vaihee kat­soo eri­lai­sek­si myös sel­lai­set vaih­to­ehdot, jotka saa­daan pyö­räyt­tä­mäl­lä rataa.

Esi­mer­kik­si kah­des­ta suo­ras­ta ja kah­dek­sas­ta kaa­res­ta saa kaksi eri­lais­ta rataa: ym­py­rän tai kaksi puoli­ym­py­rää yh­dis­tet­ty­nä kah­del­la suo­ral­la. Oh­jel­ma­ni mie­les­tä seu­raa­vat ovat eri­lai­sia ra­to­ja: 1) Aloi­te­taan suo­ral­la, 2) aloi­te­taan kaa­rel­la ja li­sä­tään sit­ten suora, 3) Aloi­te­taan kah­del­la kaa­rel­la ja li­sä­tään sit­ten suora, 4) Aloi­te­taan nel­jäl­lä kaa­rel­la ja lai­te­taan sit­ten suora. To­del­li­suu­des­sa nämä tu­le­vat ku­viin vain eri asen­toi­hin. Tein suo­dat­ti­men, joka kar­sii täl­lai­set rat­kai­sut pois. Sel­lai­nen oli help­po oh­jel­moi­da, mutta on las­ken­nal­li­ses­ti ras­kas­ta luoda val­ta­vas­ti rat­kai­su­ja ja kar­sia niis­tä sit­ten suu­rin osa pois. Tur­hien rat­kai­su­jen määrä kas­va­nee eks­po­nen­tiaa­li­ses­ti käy­tet­tä­vis­sä ole­vien kis­ko­jen luku­mää­rän funk­tio­na. 

 #  Nsuorat: Käy­tet­tä­vis­sä ole­vien suo­rien kis­ko­jen luku­määrä
 #  Nkaarteet: Käy­tet­tä­vis­sä ole­vien kaar­tei­den luku­määrä
radat(Nsuorat, Nkaarteet):-
 #    retractall(asen­net­tu/4),
    #  hae­taan kaik­ki eri­lai­set radat
    setof(Rata, rata(Nsuorat, Nkaarteet, Rata), Radat),
    #  seu­lo­taan pois ne, jotka saa pyö­räyt­tä­mäl­lä jo­tain tois­ta 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).

Suun­ni­tel­laan yksi kel­vol­li­nen rata. Aloi­te­taan ori­gos­ta suun­taan 0 (=itään) ja li­sä­tään re­kur­sii­vi­ses­ti kisko ker­ral­laan. Jos tar­jol­la on suo­ria kis­ko­ja, aloi­te­taan sel­lai­sel­la. Muu­ten ote­taan kaar­re va­sem­paan. Näil­lä va­lin­noil­la ra­joi­te­taan tur­hia saman nä­köi­siä rat­kai­su­ja. 

 #  Ns0: käy­tet­tä­vis­sä ole­vien suo­rien kis­ko­jen luku­määrä
 #  Nk0: käy­tet­tä­vis­sä ole­vien kaar­re­kis­ko­jen luku­määrä
 #  Kis­kot: Jär­jes­tet­ty luet­te­lo käy­te­tyis­tä kis­kois­ta. 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).
 #   kis­kot(0.0, 0.0, 0.0, Ns, Nk, Rata).

Voim­me lo­pet­taa, jos 1) olem­me pa­lan­neet ori­goon, 2) rin­ta­ma­suun­tam­me on teh­nyt yhden tai useam­man täy­den kier­rok­sen niin, että kis­ko­jen päät so­pi­vat yh­teen eikä 3) kis­ko­ja ole ylen mää­rin jäl­jel­lä. Kaksi suo­raa saa yleen­sä so­vi­tet­tua ra­taan hal­kai­se­mal­la sen so­pi­vas­ta koh­das­ta. Neljä kaar­ret­ta saa li­sät­tyä ra­taan vas­taa­vaan ta­paan kuin kaksi suo­raa. Sen si­jaan pitää hy­väk­syä, että yksi suora voi jäädä yli tai jopa kolme kaar­ret­ta, kun ha­lu­taan ra­das­ta umpinaiden.

Pyö­ris­tän x- ja y-koor­di­naa­tin koko­nais­lu­vuk­si ja tar­kis­tan, olem­me­ko ori­gos­sa. Kun käy­tän mitta­yk­sik­kö­nä milli­met­re­jä, tämä tar­koit­taa, että ra­to­jen pään pitää osua mil­lil­leen koh­dal­leen eli las­kuis­sa ei saa ker­tyä pal­joa­kaan vir­het­tä. Vä­hem­pi­kin tark­kuus riit­täi­si.

Tämä on siis rekursion loppu­ehto. Prolog ko­kei­lee eri vaih­to­eh­to­ja siinä jär­jes­tyk­ses­sä, kuin ne ovat koo­dis­sa, joten rekursion lo­pe­tus­ehdon pitää olla en­sim­mäi­se­nä. 


kiskot(Kulma, X, Y, Ns, Nk, []):-
    #  Ol­laan­ko ori­gos­sa?
    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,
    #  Lai­te­taan näy­töl­le piste aina kun löy­de­tään uusi rat­kai­su
    put_char('.'),
    flush_output.

Ko­keil­laan li­sä­tä kaari oi­keal­le.

Esi­mer­kik­si kah­dek­sas­ta kaa­res­ta voi ra­ken­taa ym­py­rän kään­ty­mäl­lä aina oi­keal­le tai kään­ty­mäl­lä aina va­sem­mal­le. Radat ovat tois­ten­sa peili­kuvia eli käy­tän­nös­sä saman­lai­sia. Siksi kel­puu­tan vai radat, jois­sa teh­dään nolla, yksi tai useam­pi kier­ros va­sem­mal­le eli po­si­tii­vi­seen kier­to­suun­taan eli vasta­päi­vään. Kah­dek­sik­ko on rata, missä rintamasuunnaan muu­tos on lop­pu­jen lo­puk­si 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ä­on­nis­tu­nut/kes­ken­eräi­nen yri­tys te­hos­taa 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.

 #  Ta­voi­te on 0 tai useam­pi kier­ros vasta­päi­vään joten
 #  on turha mennä niin pit­käl­le myötä­päi­vään, että kaa­ret lop­pu­vat
 #  kes­ken takaisinkääntymisen. (Vai ra­jaan­ko lii­kaa?)
riittaakokaaret(Kulma0, Nk0):-
Kulma0 + Nk0*pi/4.0 > -0.0001.   #  >=0 riit­tä­vä ehto

 #  Ol­laan­ko niin kau­ka­na, ettei ole mi­tään mah­dol­li­suut­ta pääs­tä alku­pis­tee­seen.
 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 tar­kis­ta­mis­ta, olem­me­ko saa­neet yhden radan val­miik­si. Tar­kis­te­taan, ol­laan­ko tehty nolla, yksi tai useam­pi täysi kier­ros vasta­päi­vään. Kul­man pitää olla 2*π:n moni­kerta. Tämä to­teu­tuu, jos kulma on suu­rem­pi kuin pieni ne­ga­tii­vi­nen luku ja jos jako­jään­nös kulma/π on nolla. Koska las­kies­sa saat­taa ker­tyä pien­tä vir­het­tä, ehto ei ehkä to­teu­tui­si, vaik­ka kulma olisi mel­kein 2*π. Siksi ker­ron osoit­ta­jan ja ni­mit­tä­jän kym­me­nel­lä ja pyö­ris­tän koko­nais­lu­vuk­si ennen jakojännöksen las­ke­mis­ta. 



kierrokset(Kulma):-
    Kulma > -0.001,  #  Ei ole kään­nyt­ty kier­ros­ta­kaan ne­ga­tii­vi­seen kier­to­suun­taan
    #  kom­men­toi seu­raa­va, jos ha­luat muu­ta­kin kuin kah­dek­sik­ko­ja
    Kulma < 0.001,  #  Ei ole kään­nyt­ty kier­ros­ta­kaan po­si­tii­vi­seen kier­to­suun­taan
    #  Täys­kier­rok­set: kul­man ja 2*pi:n jako­jään­nös on lä­hel­lä nol­laa
    #  Allaoleva ei ole vält­tä­mä­tön, jos ylläoleva ehto Kulma < 0.001 käy­tös­sä.
    Jaannos is round(10.0*Kulma) rem round(20.0*pi),
    Jaannos =:= 0.

Kar­si­taan ne radat, jotka saa­daan jos­tain toi­ses­ta pyö­räyt­tä­mäl­lä.

Rata esi­te­tään lis­ta­na. Esi­mer­kik­si [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.

Seu­raa­vas­sa ku­ta­kin rataa rotatoidaan ja tar­kis­te­taan, onko se rotatoituna saman lai­nen kuin joku joku muis­ta ra­dois­ta. Ellei ole, rotatoidaan uu­des­taan niin monta kerta, kuin ra­das­sa on kis­ko­ja. Ellei löydy saman­lais­ta, se saa jäädä ko­koel­maan, muu­ten se kar­si­taan. 


 #  Rekursion lo­pe­tus­ehto: kaik­ki radat tar­kas­tet­tu
 #  eri­lais­ten rat­kai­su­jen jou­kon alku­arvo on []
erilaiset([], []).

erilaiset([A1|An], Eril):-
    length(A1, N), #  N on radan pi­tuus
    #  rotatoidaan enin­tään N-1 ker­taa
    rotate(A1, Ar, N),
    #  Onko rotatoitu sama, kuin joku jäljelläolevista ra­dois­ta?
    #  ellei ole, member epä­on­nis­tuu ja oh­jel­ma
    #  pe­ruut­taa ha­ke­maan rotatelta tois­ta vaih­to­ehtoa
    member(Ar, An), !,
    #  Jos löy­tyy saman­lai­nen, tar­kas­tel­laan jäl­jel­lä ole­via ra­to­ja
    erilaiset(An, Eril).

 #  Ellei löy­ty­nyt saman­lais­ta, ylläoleva failaa ja
 #  tul­laan tähän vaih­to­eh­toon.
 #  Li­sä­tään rata A1 rat­kai­su­jen jouk­koon ja siir­ry­tään tar­kas­te­le­maan
 #  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 esi­merk­ki pro­lo­gin rekursiosta. 



demo:-
    erilaiset([[a, a, b, b], [a, b, a, b], [a, b, b, a], [b, a, b, a]], B),
    write(B), nl.

Pyy­sin prolog-tulkkia ker­to­maan, miten se kut­suu pre­di­kaat­te­ja rotatelist, rotate ja member suo­rit­taes­saan ylläolevaa demo pre­di­kaat­tia. 

 ?- 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}

Siir­ry­tään piir­tä­mään ra­to­ja.

Prolog-kielessä !-merk­ki tar­koit­taa, että jos oh­jel­ma pää­see ky­sei­sen koh­dan yli, se ei enää pe­ruu­ta sen yli ta­kai­sin ha­ke­maan muita vaih­to­eh­to­ja. !-merk­kiä kan­nat­taa käyt­tää vain huo­lel­la har­ki­tuis­sa eri­kois­ti­lan­teis­sa. Tässä ta­pauk­ses­sa voin käyt­tää sitä, koska tie­dän, että kun­kin radan voi piir­tää vain yh­del­lä ta­val­la. Hyö­ty­nä !-mer­kin käy­tös­tä on, että prolog-tulkin ei tar­vit­se pitää muis­tis­sa !-mer­kin ta­kai­sia vaih­to­eh­to­ja. 



piirraRadat([], _, _, _).

piirraRadat([Rata1|Loput], M, Ns, Nk):-
    piirraRata(Rata1, M, Ns, Nk), !,
    N is M+1,
    piirraRadat(Loput, N, Ns, Nk).

Kir­joi­te­taan kun­kin kis­kon alku­pis­tei­den koor­di­naa­tit tila­päis­tie­dos­toon. Kaar­teis­ta kir­joi­te­taan li­säk­si nel­jän väli­pis­teen koor­di­naa­tit. Kis­kon lii­tos­koh­tiin piir­re­tään vielä poik­ki­viiva ku­vion hah­mot­ta­mi­sen hel­pot­ta­mi­sek­si. Piir­rok­sen skaa­laa­mi­sek­si hae­taan sa­mal­la x- ja y-ar­vo­jen pie­nim­mät ja suu­rim­mat arvot. Piir­tä­mi­seen käy­tän li­nu­xin graph-komentoa, joka on tar­koi­tet­tu 2D-kuvaajien piir­tä­mi­seen. 


piirraRata(Rata, N, Ns, Nk):-
    open('tmp.dat', write, Fil),
    radanpisteet(Fil, 0, 0, 0, Rata, 5, Minx, Maxx, Miny, Maxy),
    close(Fil),
    #  ka­sa­taan linux-ko­men­to
    cmdline(Cmd, Minx, Maxx, Miny, Maxy, N, Ns, Nk),
    #  ja suo­ri­te­taan se. Jos­tain syys­tä popen toi­mii, mutta spawn ei.
    popen(Cmd, write, Kuva),
    close(Kuva).

Radan pis­tei­den las­ke­mi­nen on pit­käl­ti radan suun­nit­te­lun toi­sin­toa. Eroi­na on se, että pis­tei­tä ei ke­rä­tä lis­taan vaan kir­joi­te­taan tie­dos­toon ja se, että las­ke­taan x.lle ja y:lle ääri­arvot.

Kaa­rien väli­pis­tei­den las­ke­mi­nen on ehkä vähän häm­men­tä­vää. Lisä­las­ku­rin avul­la teh­dään yhden ison si­jas­ta viisi pien­tä kään­nös­tä. 


 #  Vii­mei­nen­kin kisko kä­si­tel­ty; rekursion loppu.
 #  Alku­arvo 0 x:n ja y:n ääri­ar­voil­le
radanpisteet(Fil, X, Y, Kulma, [], _, 0, 0, 0, 0):-
    #  pieni poik­ki­viiva kis­kon lop­puun
    tick(Fil, X, Y, Kulma).

radanpisteet(Fil, X0, Y0, Kulma0, [suora|Loput], _, Minx, Maxx, Miny, Maxy):- !,
    #  pieni poik­ki­viiva kis­kon al­kuun
    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),
    #  toi­mi­nee 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).

 #  Pikku­kään­nök­sis­tä vii­mei­nen
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).

 #  Pikku­kään­nös va­sem­mal­le
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 oi­keal­le kuten va­sem­mal­le­kin
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).

 #  Muo­dos­te­taan linux-ko­men­to radan piir­tä­mis­tä var­ten
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-as­tei­kon pitää olla sa­mo­ja ettei kuva vää­ris­ty
    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]).

 #  Apu­ko­men­to
rc:- consult(['junarata.prolog', 'kuvat.prolog']).
rc1:- consult(['junarata.prolog']).
rc2:- consult(['kuvat.prolog']).
../xml/Programming/Prolog_swipl/plots/plot16.png
rata 16  
../xml/Programming/Prolog_swipl/plots/plot15.png
rata 15  
../xml/Programming/Prolog_swipl/plots/plot14.png
rata 14  
../xml/Programming/Prolog_swipl/plots/plot13.png
rata 13  
../xml/Programming/Prolog_swipl/plots/plot12.png
rata 12  
../xml/Programming/Prolog_swipl/plots/plot11.png
rata 11  
../xml/Programming/Prolog_swipl/plots/plot10.png
rata 10  
../xml/Programming/Prolog_swipl/plots/plot9.png
rata 9  
../xml/Programming/Prolog_swipl/plots/plot8.png
rata 8  
../xml/Programming/Prolog_swipl/plots/plot7.png
rata 7  
../xml/Programming/Prolog_swipl/plots/plot6.png
rata 6  
../xml/Programming/Prolog_swipl/plots/plot5.png
rata 5  
../xml/Programming/Prolog_swipl/plots/plot4.png
rata 4  
../xml/Programming/Prolog_swipl/plots/plot3.png
rata 3  
../xml/Programming/Prolog_swipl/plots/plot2.png
rata 2  
../xml/Programming/Prolog_swipl/plots/plot1.png
rata 1  

Lataa tästä oh­jel­man tämän het­ki­nen ver­sio: juna­rata_0.prolog

Fri Oct 8 09:19:17 2021