RabbitFarm

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

Part 1

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

Solution

perl -e 'shift=~/(\d+):(\d\d\s*((am|pm)))/;if($1 < 12 && $3 eq "pm"){$h = $1 + 12}elsif($1 > 12 && $3 eq "pm"){$h = "0" . ($1 - 12)}else{$h = $1}print "$h:$2\n"' "17:15 pm"

Sample Run

perl -e 'shift=~/(\d+):(\d\d\s*((am|pm)))/;if($1 < 12 && $3 eq "pm"){$h = $1 + 12}elsif($1 > 12 && $3 eq "pm"){$h = "0" . ($1 - 12)}else{$h = $1}print "$h:$2\n"' "17:15 pm"
05:15 pm
perl -e 'shift=~/(\d+):(\d\d\s*((am|pm)))/;if($1 < 12 && $3 eq "pm"){$h = $1 + 12}elsif($1 > 12 && $3 eq "pm"){$h = "0" . ($1 - 12)}else{$h = $1}print "$h:$2\n"' "05:15 pm"
17:15 pm

Notes

Ok, so this isn;t going to win and Perl Golf competitions, that’s for sure! Frankly, this approach using regexes might not be the best for succinctly handling the bi-directionality.

For anyone that might not be familiar shift=~/(\d+):(\d\d\s*((am|pm)))/ means shift the first argument off of @ARGV (the command line arguments and then match against the regex. This is equivalent to $ARGV[0]=~/(\d+):(\d\d\s*((am|pm)))/.

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

use strict;
use warnings;

sub minimum_sum{
    my(@triangle) = @_;
    my($i, $j) = (0, 0);
    my $sum = $triangle[0]->[0]; 
    while($i < @triangle){
        unless(!exists($triangle[$i+1])){
            $j = ($triangle[$i+1]->[$j] >= $triangle[$i+1]->[$j+1]) ? $j+1 : $j; 
            $sum += $triangle[$i+1]->[$j]; 
        } 
        $i++;
    }  
    return $sum;
}

MAIN:{
    my(@TRIANGLE);
    @TRIANGLE = ([1], [2, 4], [6, 4, 9], [5, 1 , 7, 2]); 
    print minimum_sum(@TRIANGLE) . "\n"; 

    @TRIANGLE =([3], [3, 1], [5, 2, 3], [4, 3, 1, 3]); 
    print minimum_sum(@TRIANGLE) . "\n"; 
}

Sample Run

$ perl ch-2.pl 
8
7

Notes

I think this is a relatively well known greedy tactic. In order to minimize the total sum, make the minimum choice at each step.

References

Challenge 100

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