Erlang Games answers

[Matt Youell]

Last night I puttered around until I got out the answer that was in my head. It's not terribly Erlang-flavored. Really this is a Perl solution in Erlang clothing. But it works! I overheard one of the Daniels talking about a pattern matching solution. That sounds more 'Erlangy' already. Post it?

Here's mine:

-module(larray).

-include_lib("eunit/include/eunit.hrl").

-export([intersection/2]).

intersection(ListA, ListB) ->

  Numbers = lists:foldl( fun(N, Ranking) -> dict:update_counter(N, 1, Ranking) end , dict:new(), ListA ++ ListB),

  lists:usort([Unique || Unique <- dict:fetch_keys(Numbers), dict:fetch(Unique, Numbers) > 1]).

%% helper functions to create big lists of random integers

large_random_array(N, MaxValue) ->

  large_random_array(N, MaxValue, []).

large_random_array(0, _, L) ->

  L;

large_random_array(N, MaxValue, L) -> 

  large_random_array(N - 1, MaxValue, [random:uniform(MaxValue) | L]).

intersection_test_() ->

  ListA = lists:usort(large_random_array(100000, 1000000)),

  ListB = lists:usort(large_random_array(100000, 1000000)),

  Result = lists:usort(sets:to_list(sets:intersection(sets:from_list(ListA), sets:from_list(ListB)))),

  ?_assertEqual(Result, intersection(ListA,ListB)).

-- 

-/matt/-

http://youell.com/matt

[Daniel Hedlund]

On Wed, Feb 29, 2012 at 12:25, Matt Youell <ma...@newmoniclabs.com> wrote:

Last night I puttered around until I got out the answer that was in my head. It's not terribly Erlang-flavored. Really this is a Perl solution in Erlang clothing. But it works! I overheard one of the Daniels talking about a pattern matching solution. That sounds more 'Erlangy' already. Post it?

I have two solutions:

https://gist.github.com/1938130

The first one is a *naive* implementation that uses pattern matching to traverse two lists and runs in O(n^2) runtime.  This was the most straightforward method for teaching pattern matching and recursion but will time out on the larger datasets used in the intersection test.

The second solution (in the Gist comments) a more erlangy approach, taking full advantage of pattern matching and guards.  It has an O(n) runtime.

Additional improvements that could be made to the second solution:

1. the ordering could be re-arranged so that the most frequently encountered patterns are listed first.

2. could avoid rebuilding the first element of the list using something like X=[A|As] in the pattern match and then use X later when the full list is needed.

Cheers,

Daniel Hedlund

dan...@digitree.org

[Jayson Barley]

I just did a quick recursive function

-module(larray).
-include_lib("eunit/include/eunit.hrl").
-export([intersection/2]).

increment_rank(Key, Dict) ->
    dict:update_counter(Key, 1, Dict).

get_numbers([],[], Rank) ->
    Rank;
get_numbers([], [H|Rest], Rank) ->
    get_numbers([], Rest, increment_rank(H, Rank));
get_numbers([H|Rest], B, Rank) ->
    get_numbers(Rest, B, increment_rank(H, Rank)).

get_numbers(A, B) ->
    get_numbers(A, B, dict:new()).

intersection(ListA, ListB) ->
  Numbers = get_numbers(ListA, ListB),

  lists:usort([Unique || Unique <- dict:fetch_keys(Numbers), dict:fetch(Unique, Numbers) > 1]).

%% helper functions to create big lists of random integers
large_random_array(N, MaxValue) ->
  large_random_array(N, MaxValue, []).
large_random_array(0, _, L) ->
  L;
large_random_array(N, MaxValue, L) ->
  large_random_array(N - 1, MaxValue, [random:uniform(MaxValue) | L]).

intersection_test_() ->
  ListA = lists:usort(large_random_array(100000, 1000000)),
  ListB = lists:usort(large_random_array(100000, 1000000)),
  Result = lists:usort(sets:to_list(sets:intersection(sets:from_list(ListA), sets:from_list(ListB)))),
  ?_assertEqual(Result, intersection(ListA,ListB)).

[Matt Youell]

I realized that I didn't post the initial solution we'd come up with, the O(n^2) one that kept timing out beyond 30k items: 

https://gist.github.com/1955147

And yeah, it wasn't efficient for this problem but I love how concise the code is. I <3 comprehensions.

[Matt Youell]

Also, quick plug for the programming language group I mentioned the
other night: http://calagator.org/events/1250461973

[CLR]

Thanks for sharing this! Looking forward to that Thursday.

[Matt Youell]

Wednesday ;)