RabbitFarm

Part 1

You are given an array of positive integers @N. Write a script to return an array @M where $M[i] is the product of all elements of @N except the index $N[i].

Solution

/*
    You are given an array of positive integers @N.
    Write a script to return an array @M where $M[i] is 
    the product of all elements of @N except the index $N[i].
*/
product_a_b(A, B, P):- 
    P is A*B.
list_product([], 1).
list_product([H|T], P) :-
        foldl(product_a_b, T, H, P).

list_products(List, Products):-
    length(List, L0),
    L is L0 - 1,
    list_products(List, L, [], Products). 
list_products(_, -1, Products, Products).       
list_products(List, Index, ProductsAccum, Products):-
    nth0(Index, List, _, Remainder),
    list_product(Remainder, Product),
    NewIndex is Index - 1,
    list_products(List, NewIndex, [Product|ProductsAccum], Products).
    
main:-
    list_products([5, 2, 1, 4, 3], Products),
    write(Products),
    halt.  

Sample Run

$ swipl -s prolog/ch-1.p -g main
[24,60,120,30,40]

Notes

A problem like this really underscores the nature of lists in Prolog. That is, if you are programming in most other languages you might think of lists and arrays as interchangeable concepts for the most part. In Prolog that is very clearly not the case: lists are lists and obtaining an element at a certain position in the list is not as straightforward as simply accessing it with the usual square bracket notation. Not to say it is all that hard to do in Prolog, it’s just … different. Or, at least, requires a different mindset. People with experience in pure functional languages have this mindset of thinking of lists in terms of recursions and maps but fluency in these techniques is, sadly, less common these days.

Part 2

You are given m x n matrix of positive integers. Write a script to print spiral matrix as a list.

Solution

/*
    You are given m x n matrix of positive integers.
    Write a script to print spiral matrix as a list.
*/
write_remove_top(Matrix, UpdatedMatrix):-
    nth0(0, Matrix, Top),
    atomic_list_concat(Top, ",", TopString),
    write(TopString),
    nth0(0, Matrix, _, UpdatedMatrix).

write_remove_last([], UpdatedMatrix, UpdatedMatrix).
write_remove_last([H|T], RemainderAccum, UpdatedMatrix):-
    length(H, L),
    Last is L - 1,
    nth0(Last, H, Right),
    write(Right),
    write(","),
    nth0(Last, H, _, UpdatedRow),
    write_remove_last(T, [UpdatedRow|RemainderAccum], UpdatedMatrix).

write_remove_right(Matrix, UpdatedMatrix):-
    write_remove_last(Matrix, [], UpdatedMatrix).

write_remove_first([], UpdatedMatrix, UpdatedMatrix).
write_remove_first([H|T], RemainderAccum, UpdatedMatrix):-
    nth0(0, H, Left),
    write(Left),
    write(","),
    nth0(0, H, _, UpdatedRow),
    write_remove_first(T, [UpdatedRow|RemainderAccum], UpdatedMatrix).

write_remove_left(Matrix, UpdatedMatrix):-
    write_remove_first(Matrix, [], UpdatedMatrix).

write_remove_bottom(Matrix, UpdatedMatrix):-
    length(Matrix, L),
    Last is L - 1,
    nth0(Last, Matrix, Bottom),
    reverse(Bottom, ReverseBottom),
    atomic_list_concat(ReverseBottom, ",", BottomString),
    write(BottomString),
    nth0(Last, Matrix, _, UpdatedMatrix).
    
    
spiral(Matrix):-
    spiral(Matrix, _).
spiral(Matrix, UpdatedMatrix):-
    write_remove_top(Matrix, UpdatedMatrix),
    write(","),
    write_remove_right(UpdatedMatrix, RightRemainder),
    reverse(RightRemainder, RemainderRight),
    write_remove_bottom(RemainderRight, BottomRemainder), 
    write(","),
    reverse(BottomRemainder, RemainderBottom),
    write_remove_left(RemainderBottom, LeftRemainder), 
    spiral(LeftRemainder, _).
spiral(_, []):-
    write("\b").
    
main:-
    spiral([
        [ 1, 2, 3 ],
        [ 4, 5, 6 ],
        [ 7, 8, 9 ]
    ]), halt.  

Sample Run

$ swipl -s prolog/ch-2.p -g main
1,2,3,6,9,8,7,4,5

Notes

The spiral print works in a repeated pattern from the outside in: top row, right column, bottom row, left column. My solution puts each write/remove step of this pattern in their own predicates. A few things worth pointing out

• The matrix is a 2d list: a list with inner lists.
• For the spiral effect we need to print bottom up and right to left. In those cases I just use reverse/2 on the list being printed.
• I use a simple trick to remove a trailing comma in the final output; I print a backspace to the terminal which deletes it!
• Like Part 1 above I use nth0/4 as well as nth0/3 to directly access specific elements.