Learning to use foldl and map

I have been working on a small line drawing project, and part of that project is indexing nested lists based on sets of indices.

Firstly I wrote a function to return the recursive nth item.  So for this data [[[1,2],[3,4]],[[5,6],[7,8]]] and the input [1,2,1] the value 3 is returned.  Here’s my original function:

point(Cube,[First|Rest]) ->
point(lists:nth(First,Cube),Rest);
point(Cube,[]) ->
Cube.

I then had a couple of functions to return point lists for each list of points look-ups.  The first line was for connected points, and the second lines to draw separate lines.  So using the same data above, and the input [[1,2,1],[2,2,2],[1,1,1]] to line would generate [3,8,1], and lists of that input to lines creates lists of results.  Brilliant I know, here’s my code:

lines(Cube,Lines) ->
    lines(Cube,lists:reverse(Lines),[]).

lines(_Cube,[], Output) ->
    Output;
lines(Cube,[First|Rest], Output) ->
    lines(Cube,Rest,[line(Cube,First)|Output]).

line(Cube,Points) ->
    line(Cube,lists:reverse(Points),[]).
line(Cube,[First|Rest],Output) ->
    line(Cube,Rest,[point(Cube,First)|Output]);

line(_Cube,[],Output) ->
    Output.

I used a wrapper function to reverse the input, to solve the list construction order.  I was quite proud of my groking tail recursion.  But couldn’t help notice line and lines are the same, but not the same.  While reading how to do the output formatting, I came across some good examples on using foldl and map.  Surprise, the examples where like my functions, so I rewrote them like this (renaming point to nth_nth):

lines(Cube,Lines) ->
    lists:map(fun(Line) -> line(Cube, Line) end, Lines).

line(Cube,Points) ->
    lists:map(fun(Point) -> nth_nth(Cube, Point) end, Points).

nth_nth(Vals,Nths) ->
    lists:foldl(fun(Nth,List) -> lists:nth(Nth,List) end, Vals, Nths).

Much better, but I started to have a nagging feeling about using anonymous functions to just call a single function.  I then found the way to refer to other functions by name, but this does not work for the map as I am binding an extra variable, but for foldl it does work as it’s arity is 2, thus nth_nth can be written as:

nth_nth(Vals,Nths) ->
    lists:foldl({list,nth}, Vals, Nths).

I thought the use of the fold function to return nested look-up results was clever. The new functions have less total lines, but each line is much denser, so may appear harder to read, but I am using standard functions so the cost to comprehend should be lower.

Memoizing with ETS

In my 3n + 1 post rickhg12hs suggested I use the erlang ets module to memoize my solution.

To time the code before and after changes I found this little gem from David King

-module(timer).
-export([timer/3]).

timer(Mod,Fun,Args) ->
    Start=erlang:now(),
    Result = apply(Mod,Fun,Args),
    Stop=erlang:now(),
    io:format("~p~n", [time_diff(Start,Stop)]),
    Result.

time_diff({A1,A2,A3}, {B1,B2,B3}) ->
    (B1 - A1) * 1000000 + (B2 - A2) + (B3 - A3) / 1000000.0 .

Using this I found that my old code for 1 -> 1,000,000 took 13.1 seconds..

I upgraded the code to use an ets ordered_set like this:

-module(ets3np1).
-export([tnpo_range/2]).tnpo_range(Min, Max) ->
    Tib = ets:new(x, [ordered_set,private]),
    Result = lists:max([tnpo(Tib, X) || X <- lists:seq(Min, Max) ]),
    ets:delete(Tib),
    Result.

tnpo(_, 1) -> 1;
tnpo(Tib, Num) ->
    tnpo( ets:lookup(Tib, Num), Tib, Num ).
tnpo([], Tib, Num) ->
    case( Num rem 2) of
        1 -> NewNum = (Num * 3) + 1;
        0 -> NewNum = Num div 2
    end,
    Val = tnpo(Tib, NewNum) + 1,
    ets:insert(Tib, { Num, Val }),
    Val;

tnpo([{_,Val}], _, _) -> Val.

which ran at the improved time off 8.8 seconds.

Initially I had forgotten to delete the ets tables so my lappy started grinding after a few iterations as it thrashed the swap.  Ah the joys of learning a feature via the API reference…

One nagging question I had was the speed of using the lists:seq and the list comprehension.  So I swapped to an explicit loop via parameter matching, which ran slightly faster.  Luckily I realised the code smell: the original could be mapped across many processors with little effort, but the latter was hard coded looping.

So here’s that bad code:

tnpo_range_b(Min, Max) ->
	Tib = ets:new(x, [ordered_set, private]),
	Result = tnpo_range_b(Tib, Min, Max, 0),
	ets:delete(Tib),
	Result.

tnpo_range_b(Tib, Num, Max, Best ) when Num =< Max ->
	Result = tnpo(Tib, Num),
	tnpo_range_b(Tib, Num + 1, Max, lists:max([Result,Best]));
tnpo_range_b(_, _, _, Best ) -> Best.

After that I then wondered what the difference between set (hash-table) and ordered_set (b-tree), so I altered my code again.

So the final results are (averaged over three runs):

Input 1 -> 1,000,000
Original:  13.1 seconds
Ordered_Set:  8.8 seconds
Bad-Code: 8.7 seconds
Set:  8.9 seconds

Input 1 -> 2,000,000
Original:  27.8 seconds
Ordered_Set:  18.6 seconds
Bad-Code: 18.2 seconds
Set:  18.8 seconds

Of funny coincidence, the day after doing the coding, I read the ets section in Programing Erlang, which turns out to cover the topic nicely.

The Trip – 110103 in Erlang

The third of my Programming Challenges solutions is for The Trip 110103

This problem is great for making you think.  Key points are; you cannot have half cents, and you have to find the minimum money needed to balance costs to within one cent.

Here is my solution in Erlang:

-module(thetrip).
-export([thetrip/1, test/0]).

average([H|T], Sum, Len) ->
    average(T, Sum+H, Len+1);
average([], Sum, Len) ->
    [Sum div Len , (Sum rem Len) > 0].

diff([H|T], Sum, Avg, Odd) when H > Avg, Odd ->
    diff(T, Sum + H - Avg - 1, Avg, Odd);
diff([H|T], Sum, Avg, Odd) when H > Avg ->
    diff(T, Sum + H - Avg, Avg, Odd);
diff([_|T], Sum, Avg, Odd) ->
    diff(T, Sum, Avg, Odd);
diff([], Sum, _, _ ) ->
    Sum.

thetrip(List) ->
    Scaledup = [ trunc( X * 100 ) || X <- List],
    [Avg, Odd] = average(Scaledup, 0, 0),
    Diff = diff(Scaledup, 0, Avg, Odd ) / 100,
    io:format("$~.2f~n",[Diff]),
    Diff.

test() ->
    10.00 = thetrip([10.00, 20.00, 30.00]),
    11.99 = thetrip([15.00, 15.01, 3.00, 3.01]),
    14.39 = thetrip([15.00, 15.01, 3.00, 3.01, 3.01]),
    19.57 = thetrip([15.00, 15.01, 3.00, 3.01, 3.02, 3.03, 3.04, 3.05, 3.06, 3.07, 3.08]),
    true.

I really enjoyed getting my head around guard sequences and using local variables to space the code out.

3n + 1 in Erlang

This is my second Programming Challenges solution written in Erlang. First here.

This time I chose the first problem 3n + 1 #110101.

It is a little bit of a cheat doing it in Erlang, as the major point of the original problem is knowing the limits of your data types, and thus C’s int type is not large enough to manage the problem. I am not even sure is a int64 is large enough or if you need to drop down to your own large number type. Ether way,  Erlang does not suffer from this problem with it’s dynamic size number type.

So here is my solution:

-module(threenplusone).
-export([three_n_plus_one_range/2,test/0]).

three_n_plus_one_range(Min, Max) ->
    lists:max([threenplusone(X) || X <- lists:seq(Min, Max) ]).

threenplusone(Num) ->
    threenplusone(Num, 1).

threenplusone(1, Count) -> Count;
threenplusone(Num, Count) ->
    case (Num rem 2) of
        1 -> threenplusone( (Num * 3) + 1, Count + 1);
        0 -> threenplusone( Num div 2, Count + 1)
    end.

test() ->
    20 = three_n_plus_one_range(1,10),
    125 = three_n_plus_one_range(100, 200),
    89 = three_n_plus_one_range(201, 210),
    174 = three_n_plus_one_range(900,1000),
    true.

The problem states that numbers up to 1,000,000 are known to converge to 1, so I ran the problem from 1 -> 1,000,000 and the largest number of steps is 525. This took around 10 seconds on my MacBook which I feel is performant enough.

I quite like using the lists:seq generator and the list comprehension together, but I wonder if there is a better way to-do number generation and function calling in a single line.

Reverse And Add 110502 in Erlang

Carrying on from Cedric’s Challenge (C#, Erlang) I decided to do some of the Programming Challenges problems in Erlang, because the problems are small, but fun.

My first is Reverse And Add #110502 and here is my solution:

-module(revandadd).
-export([rev_and_add/1, test/0]).%% number to list
ntl(Num) ->
    ntl(Num, []).
ntl(0, List) ->
    List;

ntl(Num, List) ->
    ntl(Num div 10, [Num rem 10]++List).

%% list to number
ltn(List) ->
    ltn(List, 0).

ltn([], Num) ->
    Num;
ltn([H|T], Num) ->
    ltn(T, (Num*10)+H).

%% is palindrome
is_pal(Num) ->
    ntl(Num) == lists:reverse(ntl(Num)).

rev_and_add(Num) ->
    rev_and_add(Num, 1).

rev_and_add(Num, Count) ->
    Pal = ltn(lists:reverse(ntl(Num))) + Num,
    case is_pal(Pal) of
    true ->
        [Count,Pal];
    false ->
        rev_and_add(Pal, Count+1)
    end.

test() ->
 [4,9339] = rev_and_add(195),
 [5,45254] = rev_and_add(265),
 [3,6666] = rev_and_add(750),
 true.

I’m not too happy with the number-to-list functions as I’m sure there should be a built in way to-do this already, which Joe implies therefore there probably is.