PPJ izpit 2011-03-30

n1.prolog

% Napišite predikat linked(Node1, Node2, Path), ki drži takrat, ko med
% vozliščema Node1 in Node2 nekega grafa obstaja pot Path. Poskrbite tudi, da
% se vaš program nekako izogne neskončnemu ciklanju. Povezave med vozlišči v
% grafu so podane s predikatom link(Node1, Node2), ki pove, da obstaja
% povezava med vozliščema Node1 in Node2. Smer povezave določa vrstni red
% vozlišč v predikatu link/2, v danem primeru je povezava od vozlišča Node1 do
% vozlišča Node2.
%
% Primer grafa in njegovega zapisa v prologu je podan spodaj.
%

link(15, 6).
link(15, 20).
link(20, 31).
link(6, 2).
link(6, 7).
link(7, 5).
link(7, 9).

% ?- linked(20, 7, Path).
%    Path = up(20, down(15, down(6, 7)))
% ?- linked(6, 9, Path).
%    Path = down(6, down(7, 9))
% ?- linked(9, 6, Path).
%    Path = up(9, up(7, 6))
%
% Primeri zahtevanega izpisa za pot so podani zgoraj. Po povezavah gremo
% »navzgor« (up) takrat, ko gremo v nasprotni smeri kot jo podaja link/2 med
% dvema vozliščema, ko gremo v pravi smeri, pa se šteje, da gremo »navzdol«
% (down).
%

linked(A, B, _Depth, Path):-
  link(A, B),
  Path = down(A, B).

linked(A, B, _Depth, Path):-
  link(B, A),
  Path = up(A, B).

linked(A, B, Depth, Path):-
  Depth > 0, !,
  NewDepth is Depth - 1,
  linked(A, X, NewDepth, SubPath1),
  linked(X, B, NewDepth, SubPath2),
  SubPath1 =.. [Dir | [ A2 | _ ]],
  Path =.. [Dir | [A2, SubPath2]].


% Test cases
:- linked(15,  6, 0, P), P = down(15, 6).
:- linked( 6, 15, 0, P), P = up(6, 15).
:- linked( 6,  9, 1, P), P = down(6, down(7, 9)).
:- linked( 9,  6, 1, P), P = up(9, up(7, 6)).
:- linked(20,  7, 2, P), P = up(20, down(15, down(6, 7))).

n2.prolog

% Podan je spodnji program.
%

count(_, [], 0).

count(X, [X|T], N):- !,
  count(X, T, NT),
  N is NT + 1.

count(X, [_Y|T], NT):-
  count(X, T, NT).


% c. Želeli bi, da program šteje število pojavitev nekega atoma (prvi
% argument) v seznamu (drugi argument). Spremenite program tako, da to deluje
% tudi, ko so v seznamu prisotne spremenljivke.
%

countNonVar(_, [], 0).

countNonVar(X, [H|T], N):- 
  countNonVar(X, T, NT),
  (
    nonvar(H), 
    X = H, !,
    N is NT + 1
  ;
    N = NT
  ).

n3.prolog

:- use_module(library(clpfd)).

magicSquare(L):-
  L = [A1, A2, A3, B1, B2, B3, C1, C2, C3],
  
  % definiramo domeno za naše spremenljivke
  L ins 1..9, % v SICStusu: domain(L, 0, 9)

  all_different(L), % sicer bi vse dobile vrednost 5

  S #= A1 + A2 + A3,
  S #= B1 + B2 + B3,
  S #= C1 + C2 + C3,
  S #= A1 + B1 + C1,
  S #= A2 + B2 + C2,
  S #= A3 + B3 + C3,
  S #= A1 + B2 + C3,
  S #= A3 + B2 + C1,

  labeling([], L). % prolog poskuša vsem spremenljivkam v L prirediti vrednsti
                   % glede na zgoraj podane omejitve

n4.prolog

% Tole je interpreter za čisti prolog v prologu:

freq( true):- !.

freq( ( Goal1, Goal2) ) :- !,
  freq( Goal1),
  freq( Goal2).

freq( Goal) :-
  clause( Goal, Body),
  freq( Body).

% Dopolnite ta interpreter tako, da bo ugotavljal kolikokrat se v uspešnem
% dokazu povezave uporabi predikat link/2 iz prve naloge; npr. ob klicu
% (dokazovanju) linked(5, 31, Path).

freqLink(true, 0):- !.

freqLink( (G1, G2), Count ) :- !,
  freqLink(G1, Count1),
  freqLink(G2, Count2),
  Count is Count1 + Count2.

freqLink(Goal, Count) :-
  clause(Goal, Body), !,
  freqLink(Body, TmpCount),
  Goal =.. [Pred | _],
  (
    Pred = link, !,
    Count is TmpCount + 1
  ;
    Count = TmpCount
  )
;
  freqLink(Body, Count).

% Za testiranje bomo uporabili link/2 iz prve naloge in predikat linkTest/1,
% ki za vsaka dva zaporedna elementa v seznamu pokliče link/2, da bomo lahko
% freqLink/2 testirali. Klic freqLink(linked(...)), kot v navodilu naloge,
% ne deluje, ker bi bilo interpreter potrebno dopolniti. Prepostavljam, da
% tega naloga ne zahteva.
:-[n1].
linkTest([_]).
linkTest([H1 | [H2 | T]]):-
  linkTest([H2 | T]),
  link(H1, H2).

% Test cases
:- freqLink(link(7, 6), N), N = 0.
:- freqLink(link(6, 7), N), N = 1.
:- freqLink(linkTest([6, 7, 5]), N), N = 2.
:- freqLink(linkTest([6, 7, 5, 3]), N), N = 2.
:- freqLink(linkTest([6, 7, 5, 3, 15, 20]), N),  N = 3.