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.

Curse of the Azure Bonds – build 1.0.13

The game can now be completed.  I finished my dungeon crawl last night, with the help of the magic God’s Intervene cheat.

Here are the changes in build 1.0.13:

  • Fixed issues stopping the end-game sequence from working, so the game is now winnable
  • Fixed the crash that happened when sword of Frost Brand, or Flame Brand is readied
  • Fixed the way text wrapping happens, so the end game text is displayed the same as in the DOS version
  • Fixed the animation picture code, so end-game animations are drawn correctly
  • Fixed a small 3D view rendering problem with the far distance wall
  • Cheat settings are now saved in your user profile, so you don’t have to keep turning them on each time you start the game
  • Time now passes correctly when resting or searching and after combat
  • Altered the Area Map to now overlay the arrow icon cleanly
  • Added new cheat “Improved Area Map” that shows doors in blue, allowing for walking around a dungeon completely from the Area Map

I have been working on getting the sound sub-system ground-work done, but functioning sound is still a long way off.

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.