RabbitFarm

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given two decimal-coded binary numbers, $a and $b. Write a script to simulate the addition of the given binary numbers.

Solution

:-initialization(main).

sum_carry(0, 0, 1, 1, 1).  
sum_carry(1, 0, 1, 0, 0).  
sum_carry(0, 1, 1, 1, 0). 
sum_carry(0, 1, 0, 1, 1). 
sum_carry(0, 0, 0, 0, 0). 
sum_carry(1, 0, 0, 0, 1).  
sum_carry(0, 1, 1, 0, 1). 
sum_carry(1, 0, 0, 1, 0). 
sum_carry(0, 1, 1, 1).   
sum_carry(1, 0, 0, 1). 
sum_carry(0, 0, 0, 0). 
sum_carry(1, 0, 1, 0).    

add_binary(A, B, Sum):-
    number_chars(A, AChars),   
    number_chars(B, BChars),        
    reverse(AChars, ACharsReverse),  
    reverse(BChars, BCharsReverse),  
    add_binary(ACharsReverse, BCharsReverse, 0, [], Sum).  
add_binary([], [], 0, SumAccum, Sum):-
    number_chars(Sum, SumAccum).  
add_binary([], [], 1, SumAccum, Sum):-   
    number_chars(Sum, ['1'|SumAccum]).  
add_binary([H|T], [], Carry, SumAccum, Sum):-
    number_chars(D, [H]), 
    sum_carry(S, C, D, Carry), 
    number_chars(S, [N]),  
    add_binary(T, [], C, [N | SumAccum], Sum).  
add_binary([H0|T0], [H1|T1], Carry, SumAccum, Sum):-
    number_chars(D0, [H0]), 
    number_chars(D1, [H1]), 
    sum_carry(S, C, D0, D1, Carry), 
    number_chars(S, [N]),  
    add_binary(T0, T1, C, [N | SumAccum], Sum).  

main:-
    add_binary(11, 1, X0),
    write(X0), nl, 
    add_binary(101, 1, X1),
    write(X1), nl, 
    add_binary(100, 11, X2),
    write(X2), nl, 
    halt. 

Sample Run

$ gplc prolog/ch-1.p 
$ prolog/ch-1   
100
110
111

Notes

The approach here may seem just a little strange for "simulating a binary addition", but it seemed like a fun idea, given the small number of combinations, to just store all the intermediate results and then retrieve them as needed. This all seems to work ok, except that maybe going back and forth between numbers and chars is a little clunky.

Part 2

You are given 3 positive integers, $i, $j and $k. Write a script to print the $kth element in the sorted multiplication table of $i and $j.

Solution

:-initialization(main).

multiply(I, J, N):-
    between(1, I, Ith),
    between(1, J, Jth),
    N is Ith * Jth.

multiplication_table(I, J, Table):-
    bagof(N, multiply(I, J, N), Table).   

nth_from_table(I, J, K, N):-
    multiplication_table(I, J, Table),  
    msort(Table, SortedTable),   
    nth(K, SortedTable, N).  

main:-
    nth_from_table(2, 3, 4, N0),
    write(N0), nl, 
    nth_from_table(3, 3, 6, N1),
    write(N1), nl, 
    halt.   

Sample Run

$ gplc prolog/ch-2.p 
$ prolog/ch-2  
3
4

Notes

It's maybe a little confusing, to me anyway, that GNU Prolog's msort/2 does not merge duplicates but sort/2 does. Other than that I have to say that I really like this bit of Prolog. It seems very clean to me in that no recursion was required, everything is handled via Prolog itself.

References

Challenge 140