Solutions for Session 2

Note that usually there exist multiple correct solutions for an exercise. Below we give one possible solution for each exercise.

Here is the call tree for the query ?- count(437,Sum).

In some of the solutions we will use the predicates even/1 and odd/1. Here are their definitions:

even(N):-
	A is mod(N,2),
	A = 0.
odd(N):-
	A is mod(N,2),
	A = 1.

The program will write 'olleh': it reverses the word. The prolog program would be this: (Note: if you try this on your computer, this will not work since we used the predicate split_string/3 which is not a built-in, so you would have to define it yourself):
```
reverse('').  % the simple case
reverse(Word):-  % the recursive case
	split_string(Word,First,Rest),
	reverse(Rest),
	write(First).
```
Note that if we would swap the last two lines in the definition of the recursive case, the program would simple write 'hello' (without reversing).

all_even(Number):-  % the simple case
	Number<10,
	even(Number).
all_even(Number):-  % the recursive case
	Number>=10,
	Digit is mod(Number,10),
	NewNumber is Number // 10,
	even(Digit),
	all_even(NewNumber).

Here is the call tree for the query ?- all_even(2496)..

count_even(Number,1):-  % a simple case
	Number<10,
	even(Number).
count_even(Number,0):-  % the other simple case
	Number<10,
	odd(Number).
count_even(Number,Count):-  % the recursive case
	Number>=10,
	Digit is mod(Number,10),
	NewNumber is Number // 10,
	DigCount is mod(Digit+1,2),  % DigCount will be 1 if Digit is even, 0 otherwise
	count_even(NewNumber,NumCount),
	Count is DigCount + NumCount.

Here is the call tree for the query ?- count_even(24,A). Here is the call tree for ?- count_even(25,A)..

```
?- funny(6).
6
3
10
5
16
8
4
2
I will quit

Yes
?- funny(7).
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
I will quit

Yes
```
When we move the two write(N), nl lines one line higher, the output is as follows.
```
?- funny(6).
6
3
3
10
5
5
16
8
4
2
I will quit

Yes
?- funny(7).
7
7
22
11
11
34
17
17
52
26
13
13
40
20
10
5
5
16
8
4
2
I will quit

Yes
```
It prints the odd numbers twice, the reason is that if funny(N) is called with N being odd, prolog jumps in the first recursive clause for funny/1 (the clause for even numbers), writes the odd number to the screen, fails on the condition even(N) and backtracks to the second recursive clause for funny/1 (the clause for odd numbers) where it writes the odd number to the screen again, ... .

doubledigit(N):-
	N>10,
	Digit is mod(N,10),
	NewN is N // 10,
	occurs_in(Digit,NewN).
doubledigit(N):-
	N>10,
	NewN is N // 10,
	doubledigit(NewN).

We have used an auxiliary predicate occurs_in/2:

occurs_in(Digit,Number):-
	Digit2 is mod(Number,10),
	Digit2 = Digit.
occurs_in(Digit,Number):-
	Number>=10,
	NewNumber is Number // 10,
	occurs_in(Digit,NewNumber).

doubledigitclose(N):-
	N>10,
	Digit is mod(N,10),
	NewN is N // 10,
	Digit2 is mod(NewN,10),
	Digit2 = Digit.
doubledigitclose(N):-
	N>10,
	NewN is N // 10,
	doubledigitclose(NewN).

Given your current knowledge of prolog, the following prolog program is probably the most straightforward way to compute fibonacci numbers:
```
fib(1,1).
fib(2,1).
fib(N,FibNumber):-
	N>2,
	Previous is N - 1,
	Previous2 is N - 2,
	fib(Previous,FibPrevious),
	fib(Previous2,FibPrevious2),
	FibNumber is FibPrevious + FibPrevious2.
```
This is a rather slow way of computing fibonacci numbers. To see why it is slow, try to draw the call tree for fib(5,N). You will see that using the above program, prolog will amongst others compute fib(3,N) twice. Now if we would for instance try fib(10,N), there will be much more computations that are done multiple times. In one of the later sessions we will go more into detail about this and we will see a more efficient solution to this problem.