RabbitFarm

The examples used here are from the weekly challenge problem statement and demonstrate the working solution. Also, the challenge statements are given in a Perl context although for Prolog solutions some adjustments are made to account for the differing semantics between the two languages.

Part 1

You are given a time (12 hour / 24 hour). Write a one-liner to convert the given time from 12 hour format to 24 hour format and vice versa.

Solution

:-initialization(main).

hour_to_12(H12, H24):-
    append(H, [58|R], H24), 
    number_codes(N0, H),
    N is N0 - 12,
    number_codes(N, C0),
    flatten([C0, 58, R], C),  
    atom_codes(A, C), 
    H12 = A. 

hour_to_24(H12, H24):-
    append(H, [58|R], H12), 
    number_codes(N0, H),
    N is N0 + 12,
    number_codes(N, C0),
    flatten([C0, 58, R], C),  
    atom_codes(A, C), 
    H24 = A. 

twenty_four_hour(H12, H24):-
    nonvar(H12),
    hour_to_24(H12, H24). 
twenty_four_hour(H12, H24):-
    nonvar(H24),
    hour_to_12(H12, H24). 

main:-
    twenty_four_hour("05:15 pm", HOUR_24),
    write(HOUR_24), nl,
    twenty_four_hour(HOUR_12, "17:15 pm"),
    write(HOUR_12), nl,
    halt. 

Sample Run

$ gplc ch-1.p
$ ch-1
17:15 pm
5:15 pm

Notes

Keep in mind that any two points determine a line. Therefore to consider all possible non-trivial lines we need to review all triples of points.

In determining collinearity I calculate the area of a triangle using the triple of points. If the area is zero we know that all the points lay on the same line.

Part 2

You are given triangle array. Write a script to find the minimum path sum from top to bottom. When you are on index i on the current row then you may move to either index i or index i + 1 on the next row.

Solution

:-initialization(main).

minimum_sum(Triangle, Sum):-
    minimum_sum(Triangle, 1, 0, Sum).  
minimum_sum([H|[]], Index, PartialSum, Sum):-
    nth(Index, H, N),
    Sum is PartialSum + N.  
minimum_sum([H0, H1|T], Index, PartialSum, Sum):-
    nth(Index, H0, N0),
    PartialSum0 is PartialSum + N0,
    I0 is Index + 1, 
    nth(I0, H1, N1),
    nth(Index, H1, N2),
    N1 > N2,
    minimum_sum([H1|T], Index, PartialSum0, Sum). 
minimum_sum([H0, H1|T], Index, PartialSum, Sum):-
    nth(Index, H0, N0),
    PartialSum0 is PartialSum + N0,
    I0 is Index + 1, 
    nth(I0, H1, N1),
    nth(Index, H1, N2),
    N1 =< N2,
    minimum_sum([H1|T], I0, PartialSum0, Sum). 

main:-
    minimum_sum([[1], [2, 4], [6, 4, 9], [5, 1, 7, 2]], Sum0),  
    write(Sum0), nl, 
    minimum_sum([[3], [3, 1], [5, 2, 3], [4, 3, 1, 3]], Sum1), 
    write(Sum1), nl, 
    halt.  

Sample Run

$ gplc ch-2.p 
$ prolog/ch-2
8
7

Notes

This code is more functional than logical. Code is not written in a vacuum! The night before working this problem I was reading about Functional Programming in Java and it seems to have slightly warped my brain. Well, or at least I decided it would be fun to do things this way.

A more idiomatically Prolog solution would surely make use of Constraint Programming and just solve the more general case without the triangle restriction.

References

Challenge 100