Chewing The Cud

Coupling Cribbage and Erlang into a program sounds like a fun little program to write to aid in learning Erlang while writing a program that brings a game I like in life to the virtual world. Is it the most efficient? Probably not, but you gotta start somewhere. To the code!

The first thing I wanted to do was create a method to calculate points. An ace is a 1, 2-10 are face value, and Jack, Queen, King are 11, 12, 13, respectively. Easy adjustments could be made to allow characters (A, J, Q, K) but for now, I like keeping it simple.

-module(cribbage).
 
-export([points/1]).
 
points([]) -> 0;
points(L) ->
    Hand = lists:sort(L),
    fifteens(Hand, 0) + runs(Hand, 0, 0) + pairs(Hand, 1, 0).

The above creates a module called cribbage and exports a function called points/1 which takes one parameter, a list of cards. There are three kinds of scoring in Cribbage: combinations of cards that equal 15, runs of three or more, and pairs (or sets or four of a kind). There is one other kind, but it’s not part of this portion of the game.

cardval(C) when C > 9 -> 10;
cardval(C) -> C.
 
fifteens(_L, Total) when Total > 15 -> 0;
fifteens(_Hand, Total) when Total =:= 15 -> 2;
fifteens([], _Total) -> 0;
fifteens([H | T], Total) when Total < 15 ->
    fifteens(T, Total) + fifteens(T, Total + cardval(H)).

cardval is a function that converts the value of face cards (11-J,12-Q,13-K) to 10 and leaves other cards unchanged in value. This is useful in finding all combinations of 15 in the hand. When a combo equals 15, two points are added to the score.

Runs were the trickiest of the three to get right. First, I defined a simple function to determine the points for a run of given length.

run(3) -> 3;
run(4) -> 6;
run(5) -> 12;
run(_Length) -> 0.

Some people may play with different values for runs of different lengths, so this allows for easy editing.

Runs come in two flavors: 1) A normal run, and 2) A run where one or two of the cards are doubled. To account for this, I have runs/3 and runs/4. runs/3 handles the first case, and passes control to runs/4 when a run of the second case is encountered. Another special case is when a run has two different cards doubled (e.g. 3,4,4,5,5) where the run of three is doubled and doubled again.

%% two cases for runs
%%   1. A straight run - 4,5,6,7
%%   2. A run with a double in the sequence - 4,4,5,6 or 4,5,5,6
runs([], _Curr, Len) -> run(Len);
runs([H | T], Curr, Len) when H =:= (Curr+1) -> runs(T, H, Len + 1);
runs([H | T], Curr, Len) when H =:= Curr -> runs(T, Curr, Len, {H, 2});
runs([H | T], _Curr, Len) -> run(Len) + runs(T, H, 1).
 
runs([], _Curr, Len, {_Card, Mult}) -> Mult * run(Len);
runs([H | T], Curr, Len, {Card, Mult}) when H =:= (Curr+1) ->
    runs(T, H, (Len+1), {Card, Mult});
%% needed for special cases where multiple cards are doubled up
%% like 3,4,4,5,5
runs([H | T], Curr, Len, {Card, Mult}) when H =:= Curr, H > Card -> 
    runs(T, Curr, Len, {H, (Mult*2)});
%% handles a triple carding, like 2,2,2,3,4
runs([H | T], Curr, Len, {Card, Mult}) when H =:= Curr ->
    runs(T, Curr, Len, {Card, (Mult+1)});
runs([H | T], _Curr, Len, {_Card, Mult}) ->
    (Mult * run(Len)) + runs(T, H, 1).

For pairs, I do a similar thing: define a pair(Length) function that returns the point value given a number of similar cards. But it’s all pretty straightforward.

pairs([], Pairs, _Curr) -> pair(Pairs);
pairs([H | T], Pairs, Curr) when H =:= Curr -> pairs(T, Pairs+1, Curr);
pairs([H | T], Pairs, _Curr) -> pair(Pairs) + pairs(T, 1, H).
 
pair(2) -> 2;
pair(3) -> 6;
pair(4) -> 12;
pair(_Length) -> 0.

That’s it for now. Actual game play to come. You can get the code here.

I have been playing with some drawing code in javascript, storing coordinates and using them later on in the application. My list of coordinates is of the form [ [id1, x1, y1, width1, height1], [id2, x2, y2, width2, height2],…]. A requirement of the application is that a user can delete a set of coordinates from the list. Using prototype.js, I created a simple function to remove the nested array based on the id.

// remove an array from the list based on the id
function remove(id, list) {
    return $A(list).map(
        function(arr) {
            if ( $A(arr).first() == id ) { return ; }
            else { return arr; }
        }).compact();
}

In your favorite editor, this function can be a one-liner, but spacing helps here for clarity and formatting on the page. Onward!

So what’s happening? The first thing we do is wrap list with the $A() call to ensure we have access to the extensions prototype gives us for arrays (I’m calling the parameter a list because I’m on an Erlang kick and it has infiltrated my core!). Once extended, we call the map function to iterate through the list and apply the supplied function to each element in the list (in this case it is a list of arrays, so each element passed to the supplied function will be an array as well).

Within the supplied function, we are dealing with a single array of the form [id, x, y, width, height], so $A(arr).first() returns the id of the array. This value is compared to the value of the id parameter and if it matches, returns nothing, or ‘undefined’ in Javascript. If the ids don’t match, it returns the array unaltered. As the map function iterates through the list, a new list is created containing the results of the supplied function. So the return value of the map function call is an array. We then call the compact function on the resulting array, which removes any undefined values from the array, essentially leaving only those arrays that did not have the id passed in.

This function is fairly specialized; the requirements for the function are fairly specific. A more general function could be written but that is an exercise left to the reader.

So you want to download some files from an ftp server, but they are contained in more than one subdirectory. With a straight ftp client, you would have to recurse through all of the directories and mget each directory’s contents manually. Never fear, though, there is a little utility that can help - wget.

> wget -r ftp://user:pass@ftpsite.com/directory .

If the ftp site allows anonymous logins, you can omit the user:pass portion. This will get everything…it is left as an exercise to the reader to customize the command.

As we all know (actually, many probably don’t know) Internet Explorer has claimed many hours of developer time trying to get a feature working with the quirks of IE. One quirk that I’ve dealt with recently was the :hover pseudo-class and its implementation across various browsers. The most notable quirk is that IE only supports the :hover on anchor tags (<a>). What’s a fella to do when he wants a drop down menu that displays the sub-menu when the mouse is hovering over an li element? Write some Javascript to aid IE in rendering the drop-down effect properly.

The first draft of our menu is here. If you are unfortunate enough to be using IE, you probably won’t see the sub-menu items. So how do we negotiate this? With a little extra class, and some Javascript.

The second draft of our menu can be found here. The differences to note:

• The li:hover rule is now accompanied by a li.over as well
• The function fixHover()
• The function init()

So we added a rule that says any ul with a parent li with a class of over will also get the styling that a ul with a parent with li:hover gets; in this case - display the underlying ul. Next, we added a function (fixHover) that took an element, and retrieved all of it’s immediate children nodes. We then iterate through the list of children, basically adding two events, “mouseover” and “mouseout”, to for each element to observe. For “mouseover” events, append the classname “over” to the element; on “mouseout” events, remove the “over” classname. The essence here is that :hover is the CSS equivalent of observing the “mouseover” and “mouseout” events. The draw back to our solution is that if Javascript is turned off, the sub-menus remain hidden from the user.

NOTE: I am not a designer, so the purpose of this article is to merely illustrate the ability to apply hover-type functionality to any element on the page in IE and not showcase my ability to make things look nice.

Another feature to mention is the init function and the Event.observe() call, which calls the init function after the window has finished loading the page. This is a must because we cannot apply the “mouseover” and “mouseout” event observations until the nodes have been created in the DOM. Best to leave this until the window has loaded. Both of the functions rely on the prototype.js library to retrieve the child nodes, iterate through the nodes, and attach events to the nodes. It is possible to do this without prototype or with another library, but I leave it up to the reader to translate this code to their library of choice.

I’m a big fan of green living and when noteworthy technology comes along that enables green principles to be adopted by the masses, I’m all for it. Such is the case today, when I read, via EcoGeek, about a fuel cell being developed by researchers at Saint Louis University that runs on sugary liquids (ah ha, the double meaning of the title is revealed!). The hook from the SLU press release:

Juicing up your cell phone or iPod may take on a whole new meaning in the future. Researchers at Saint Louis University have developed a fuel cell battery that runs on virtually any sugar source - from soft drinks to tree sap - and has the potential to operate three to four times longer on a single charge than conventional lithium ion batteries, they say.

Now, I’m all for this kind of technology making it into mainstream commercial applications; my reservations come in when I see tree sap being listed as a potential source. I’m a big fan of real maple syrup and it already costs an arm and a leg. Should it be found that sap from the maple (especially the sugar maple, duh) is the best fuel source, I may have to hurt something, as the demand for these fuel cells would raise the price of syrup even more. So let’s pull for soda, which we really shouldn’t be drinking anyway, or some alternative source of sugar to be the front runner in the fuel cell’s source, and not maple tree sap.

Whatever the source, I am excited about these fuel cells. I wonder, though, at this sentence: “Like other fuel cells, the sugar battery contains enzymes that convert fuel - in this case, sugar - into electricity, leaving behind water as a main byproduct.” At first, the reaction is, “Great, water is the by-product; who doesn’t love that”. I wonder what the other byproducts are though. Hopefully not a contaminant of some kind, as that would really mar the greenness of the fuel cell. I guess the wise thing to do is to watch carefully as this technology progresses and keep a foot on the ground when listening to the hype of any “100% green” technology.

Gluttony is probably the sin I indulge in the most and, at this point in my life, I’m able to eat what I want at whatever quantity I want. This does not mean I am an undiscerning eater. Quite the contrary, I enjoy quality food and wish I was better at cooking those fancy meals. While fast food certainly kept me fed during school, now that I am out and bringing home a paycheck, I came to the decision that fast food really has nothing to offer me anymore. I ate it for the quantity to price ratio, to help keep some weight on my body for sports. Without that high demand for energy, quantity really has become a non-issue.

Another aspect of eating I feel fortunate in is that I haven’t really met a food I didn’t like. There are exceptions (like White Castle, but I have the fast-food-embargo card to play there now), but they really boil down to badly prepared food, not the food item itself. So I challenge myself when I eat to either order or make something I have not had before. This is most challenging at Thai restaurants, as I love Pad Thai; usually, those I’m eating with order it and I can get something else, knowing I’ll probably get the end of their plates when they have become full.

My cooking abilities are quite meager at this point. The hardest part for me is that I don’t like to cook for just myself. So if a certain someone could return from New Zealand, perhaps the pots and pans would get more varied use! That situation will be rectified soon, so I’ll be able to crack into that Joy of Cooking cookbook and create some tasty treats.

One aspect of cooking I hadn’t really considered before was the origin of the ingredients. Just go the the Schnucks or Shop and Save and pick up your ingredients, right? Well, not necessarily. Part of green living is working to use nature and the environment in a sustainable way, but also doing it in a way that still benefits people in other ways. It was in thinking about how to shop for food that would be raised in a “green” way that I came across an organization that is striving to promote this way of thinking. Their motto: “…counteract fast food and fast life, the disappearance of local food traditions and people’s dwindling interest in the food they eat, where it comes from, how it tastes and how our food choices affect the rest of the world.” Their name: Slow Food International.

Always in search of getting more out of my experiences, I think this organization brings quite a bit of education to the table (pun intended), teaching people about the hows, whys, whats, and whens of the foods they eat. It seems pretty obvious that supporting the local farmer’s markets and co-ops. Search Google Maps for farmer’s markets near your zipcode and you’ll probably find a few; I found 6 within 10 miles of me. Who knew? I do, now.

So here’s to making and experiencing good food, knowing that you are being responsible to yourself, your local community, and the ecosystem. It certainly makes things taste better knowing you’re contributing to those causes.

Right on the heals of 21-30 comes 31-40. These problems began to delve into mathematics, with a great emphasis on prime numbers and their generation. Quite interesting to work with, since prime numbers are the basis behind encryption of any non-trivial strength. Enjoy:

%% Determine whether a given integer number is prime.
%% Example: (is-prime 7) -> T
p31(2) -> true;
p31(N) when N rem 2 =:= 0 -> false;
p31(N) -> p31is_prime(N, 3, N div 2 ).

p31is_prime(_N, K, Limit) when K > Limit -> true;
p31is_prime(N, K, Limit) ->
case N rem K of
0 -> false;
_Else -> p31is_prime(N, K+2, Limit)
end.

%% Determine the greatest common divisor of two positive integer numbers.
%% Use Euclid’s algorithm.
%% Example: (gcd 36 63) -> 9
p32(A, 0) -> A;
p32(A, B) when B > A -> p32(B, A);
p32(A, B) -> p32(B, A rem B).

%% Determine whether two positive integer numbers are coprime.
%% Two numbers are coprime if their greatest common divisor equals 1.
%% Example: (coprime 35 64) -> T
p33(A, B) -> p32(A, B) =:= 1.

%% Calculate Euler’s totient function phi(m).
%% Euler’s so-called totient function phi(m) is defined as the number of positive integers r (1 < = r < m) that are coprime to m.
%% Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.
%% (totient-phi 10) -> 4
%% Find out what the value of phi(m) is if m is a prime number.
%% psuedo-code if is_prime(m), phi(m) = m-1, else compute phi(m).
%% Euler’s totient function plays an important role in one of the most widely used public key cryptography methods (RSA).
%% In this exercise you should use the most primitive method to calculate this function (there are smarter ways that we shall discuss later).
p34(1) -> 1;
p34(M) -> p34totient_phi(M, 1, []).

p34totient_phi(M, M, L) -> length(L);
p34totient_phi(M, R, L) ->
case p33(M, R) of
true -> p34totient_phi(M, R+1, [R | L]);
false -> p34totient_phi(M, R+1, L)
end.

%% Determine the prime factors of a given positive integer.
%% Construct a flat list containing the prime factors in ascending order.
%% Example: (prime-factors 315) -> (3 3 5 7)
p35(N) -> p35prime_factors(N, 2, []).

p35prime_factors(1, _C, PF) -> lists:reverse(PF);
p35prime_factors(N, 2, PF) ->
case (N rem 2) =:= 0 of
true -> p35prime_factors(N div 2, 2, [2 | PF]);
false -> p35prime_factors(N, 3, PF)
end;
p35prime_factors(N, C, PF) ->
case (N rem C) =:= 0 of
true -> p35prime_factors(N div C, C, [C | PF]);
false -> p35prime_factors(N, C+2, PF)
end.

%% Determine the prime factors of a given positive integer (2).
%% Construct a list containing the prime factors and their multiplicity.
%% Example: (prime-factors-mult 315) -> ((3 2) (5 1) (7 1))
%% Hint: The problem is similar to problem P13.
p36(N) -> p10(p35(N)).

%% Calculate Euler’s totient function phi(m) (improved).
%% See problem P34 for the definition of Euler’s totient function.
%% If the list of the prime factors of a number m is known in the form of problem P36 then the function phi(m) can be efficiently calculated as follows:
%% Let ((p1 m1) (p2 m2) (p3 m3) …) be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:
%% phi(m) = (p1 - 1) * [p1 ** (m1 - 1)] * (p2 - 1) * [p2 ** (m2 - 1)] * (p3 - 1) * [p3 ** (m3 - 1)] + …
%% Note that a ** b stands for the b’th power of a.
p37(M) -> p37phi(p36(M), 1).

p37phi([], Phi) -> Phi;
p37phi([[M, P] | L], Phi) -> p37phi(L, Phi * (P - 1) * round(math:pow( P, M-1 )) ).

%% Compare the two methods of calculating Euler’s totient function.
%% Use the solutions of problems P34 and P37 to compare the algorithms. Take the number of logical inferences as a measure for efficiency. Try to calculate phi(10090) as an example.
p38(M) ->
{T34, V34} = timer:tc(lp, p34, [M]),
{T37, V37} = timer:tc(lp, p37, [M]),
io:fwrite(”p34 took ~p micro seconds and returned ~p.~n”, [T34, V34]),
io:fwrite(”p37 took ~p micro seconds and returned ~p.~n”, [T37, V37]).

%% A list of prime numbers.
%% Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.
p39(High) -> p39(1, High).
p39(Low, High) when Low > High -> p39(High, Low);
p39(Low, High) -> [X || X < - p39primes(lists:seq(2, High) , [1]), X >= Low, X =< High].

p39primes([], Primes) -> lists:reverse(Primes);
p39primes([1 | Sieve], Primes) ->      p39primes(Sieve, [1 | Primes]); % pops 1 off the sieve
p39primes([2 | Sieve], Primes) ->      p39primes([X || X < - Sieve, (X rem 2) > 0], [2 | Primes]); % pops 2 off the sieve and removes all multiples of 2
p39primes([Curr | Sieve], Primes) -> p39primes([X || X < - Sieve, (X rem Curr) > 0], [Curr | Primes]). % pops the next value off the sieve and removes all multiples

%% Goldbach’s conjecture.
%% Goldbach’s conjecture says that every positive even number greater than 2 is the sum of two prime numbers.
%% Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case.
%% It has been numerically confirmed up to very large numbers (much larger than we can go with our Prolog system).
%% Write a predicate to find the two prime numbers that sum up to a given even integer.
%% Example: (goldbach 28) -> (5 23)
p40(N) -> p40goldbach(N, p39(N), []).

p40goldbach(0, _Primes, Result) when length(Result) =:= 2 -> lists:reverse(Result);
p40goldbach(N, _Primes, Result) when length(Result) =:= 2, N =/= 0 -> false;
p40goldbach(_N, [], _Result) -> false;

p40goldbach(N, [P | Primes], Result) ->
Sol = p40goldbach(N-P, Primes, [P | Result]),
case is_list(Sol) of
true -> Sol;
_else -> p40goldbach(N, Primes, Result)
end.

The next installment of the 99 Lisp problems. 27 and 28 are incomplete as I have not sat down to actually work through them yet. More research is needed to do multinomial coefficients. This batch of problems posed some challenge and required a bit of research and dusting off math skills, as well as getting familiar with Erlang’s List Comprehension syntax. For your viewing pleasure:

%% Insert an element at a given position into a list.
%% Example: (insert-at ‘alfa ‘(a b c d) 2) -> (A ALFA B C D)
p21(Elem, L, Pos) -> p21insert(Elem, L, Pos, []).

p21insert(Elem, L, 1, NewL) -> lists:reverse([Elem | NewL]) ++ L;
p21insert(Elem, [H | L], Pos, NewL) -> p21insert(Elem, L, Pos-1, [H | NewL]).

%% Create a list containing all integers within a given range.
%% If first argument is smaller than second, produce a list in decreasing order.
%% Example: (range 4 9) -> (4 5 6 7 8 9)
p22(Start, End) when Start < End -> p22range_asc(End-Start, [Start]);
p22(Start, End) -> p22range_desc(Start-End, [Start]).

p22range_asc(0, L) -> lists:reverse(L);
p22range_asc(Count, [H | L]) -> p22range_asc(Count-1, [H+1, H | L]).

p22range_desc(0, L) -> lists:reverse(L);
p22range_desc(Count, [H | L]) -> p22range_desc(Count-1, [H-1, H | L]).

%% Extract a given number of randomly selected elements from a list.
%% The selected items shall be returned in a list.
%% Example: (rnd-select ‘(a b c d e f g h) 3) -> (E D A)
%% Hint: Use the built-in random number generator and the result of problem P20.
p23(L, Count) when length(L) < Count -> p23rnd_select(L, length(L), []);
p23(L, Count) -> p23rnd_select(L, Count, []).

p23rnd_select(_L, 0, RandL) -> RandL;
p23rnd_select(L, Count, RandL) ->
Rnd = random:uniform(length(L)),
V = lists:nth(Rnd, L),
p23rnd_select(p20(L, Rnd), Count-1, [V | RandL]).

%% Lotto: Draw N different random numbers from the set 1..M.
%% The selected numbers shall be returned in a list.
%% Example: (lotto-select 6 49) -> (23 1 17 33 21 37)
%% Hint: Combine the solutions of problems P22 and P23.
p24(Num, High) -> p23(p22(1, High), Num).

%% Generate a random permutation of the elements of a list.
%% Example: (rnd-permu ‘(a b c d e f)) -> (B A D C E F)
%% Hint: Use the solution of problem P23.
p25(L) -> p23(L, length(L)).

%% Generate the combinations of K distinct objects chosen from the N elements of a list
%% In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients).
%% For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.
%% Example: (combination 3 ‘(a b c d e f)) -> ((A B C) (A B D) (A B E) … )

% Not the most efficient way, but generate the power set for the list and remove all but the sub-lists of length K
powerset([]) ->
[[]];
powerset([H | T]) ->
SubPS = powerset(T),
lists:append(SubPS, lists:map(fun(E) -> [H | E] end, SubPS)).

p26(K, L) -> [X || X < - powerset(L), length(X) == K].

%% Group the elements of a set into disjoint subsets.
%% a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities and returns them in a list.
%% Example: (group3 ‘(aldo beat carla david evi flip gary hugo ida)) -> ( ( (ALDO BEAT) (CARLA DAVID EVI) (FLIP GARY HUGO IDA) ) … )
p27([]) -> [].

%% b) Generalize the above predicate in a way that we can specify a list of group sizes and the predicate will return a list of groups.
%% Example: (group ‘(aldo beat carla david evi flip gary hugo ida) ‘(2 2 5)) -> ( ( (ALDO BEAT) (CARLA DAVID) (EVI FLIP GARY HUGO IDA) ) … )
%% Note that we do not want permutations of the group members; i.e. ((ALDO BEAT) …) is the same solution as ((BEAT ALDO) …).
%% However, we make a difference between ((ALDO BEAT) (CARLA DAVID) …) and ((CARLA DAVID) (ALDO BEAT) …).
%% You may find more about this combinatorial problem in a good book on discrete mathematics under the term “multinomial coefficients”.
p28() -> [].

%% Sorting a list of lists according to length of sublists
%% a) We suppose that a list contains elements that are lists themselves. The objective is to sort the elements of this list according to their length. E.g. short lists first, longer lists later, or vice versa.
%% Example: (lsort ‘((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o))) -> ((O) (D E) (D E) (M N) (A B C) (F G H) (I J K L))
p29(L) -> p29lsort(L).

%% code taken from Erlang Programming Examples -> List Comprehensions -> QuickSort and adapted
p29lsort([]) -> [];
p29lsort([Pivot | L]) ->
p29lsort([ X || X < - L, length(X) < length(Pivot)]) ++ [Pivot | p29lsort([ X || X <- L, length(X) >= length(Pivot)])].

%% b) Again, we suppose that a list contains elements that are lists themselves. But this time the objective is to sort the elements of this list according to their length frequency;
%% i.e., in the default, where sorting is done ascendingly, lists with rare lengths are placed first, others with a more frequent length come later.
%% Example: (lfsort ‘((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o))) -> ((i j k l) (o) (a b c) (f g h) (d e) (d e) (m n))
%% Note that in the above example, the first two lists in the result have length 4 and 1, both lengths appear just once. The third and forth list have length 3 which appears twice (there are two list of this length).
%% And finally, the last three lists have length 2. This is the most frequent length.
p30(L) -> p30lfsort(L).

p30lfsort([]) -> [];
p30lfsort([H | L]) ->
Grouped = p30group(L, [[H]]),
Sorted = p29(Grouped),
p30ungroup(Sorted, []).

p30group([], Grouped) -> Grouped;
p30group([H | L], Grouped) -> p30group(L, p30insert(H, Grouped, [])).

%% insert Elem in to a group with the same length, or create a new group for the length of Elem
p30insert(Elem, [], PrevGroups) ->
lists:reverse([[Elem] | PrevGroups]);
p30insert(Elem, [ [GroupH | GroupT] | RestGrouped], PrevGroups) when length(GroupH) == length(Elem) ->
PrevGroups ++ [ [GroupH, Elem | GroupT] | RestGrouped];
p30insert(Elem, [ [GroupH | GroupT] | RestGrouped], PrevGroups) ->
p30insert(Elem, RestGrouped, [[GroupH | GroupT] | PrevGroups]).

%% remove length-specific groupings
p30ungroup([], Ungrouped) -> lists:reverse(Ungrouped);
p30ungroup([H | L], Ungrouped) when not is_list(H) -> [[H | L] | Ungrouped];
p30ungroup([Group | L], Ungrouped) -> p30ungroup(Group, []) ++ p30ungroup(L, Ungrouped).

Working through the 99 Lisp Problems in Erlang and just did a comparison of two different methods for computing Euler’s totient function. The results:

> lp:p39(10090).

p34 took 10864 micro seconds and returned 4032.
p37 took 72 micro seconds and returned 4032.

I’ll leave it to the reader to work the problems themselves, but it does illustrate the importance of good algorithm design in mission-critical parts of your code. Were my application’s lifeblood to be in calculating phi, and I was naive and took the p34 algorithm to solve for phi, I would be 150x slower at doing the job. I guess the moral is, always research mission-critical portions of code for optimized algorithms. A sub-moral would be to keep abreast of the latest and greatest in algorithms and math in general. I like to have a friend in grad school studying quantum mechanics to keep me informed!

The second set of 10 problems are now in the bag. Feeling the Erlang-fu! The first set can be found here.

%% Modified run-length encoding.
%% Modify the result of problem P10 in such a way that if an element has no duplicates it is simply copied into the result list.
%% Only elements with duplicates are transferred as (N E) lists.
%% Example: (encode-modified ‘(a a a a b c c a a d e e e e)) -> ((4 A) B (2 C) (2 A) D (4 E))
p11([]) -> [];
p11(L) -> p11encode(p09(L), []).

p11encode([], Encoded) -> lists:reverse(Encoded);
p11encode([[Elem | SubL] | L], Encoded) ->
case length(SubL) of
0 -> p11encode(L, [Elem | Encoded]);
_Else -> p11encode(L, [[length(SubL)+1, Elem] | Encoded])
end.

%% Decode a run-length encoded list.
%% Given a run-length code list generated as specified in problem P11. Construct its uncompressed version.
p12([]) -> [];
p12(L) -> p12decode(L, []).

p12decode([], Decoded) -> lists:reverse(Decoded);
p12decode([[N, Elem] | L], Decoded) -> p12decode(L, lists:duplicate(N, Elem) ++ Decoded);
p12decode([Elem | L], Decoded) -> p12decode(L, [Elem | Decoded]).

%% Run-length encoding of a list (direct solution).
%% Implement the so-called run-length encoding data compression method directly.
%% I.e. don’t explicitly create the sublists containing the duplicates, as in problem P09, but only count them.
%% As in problem P11, simplify the result list by replacing the singleton lists (1 X) by X.
%% Example: (encode-direct ‘(a a a a b c c a a d e e e e)) -> ((4 A) B (2 C) (2 A) D (4 E))
p13([]) -> [];
p13([H | L]) -> p13encode(L, H, 1, []).

%% p13encode(The Remaining List,
%% The Current Element,
%% The Number Of Repetitions Thus Far,
%% The Encoded List Thus Far)
p13encode([], Curr, Rep, Encoded) ->
case Rep of
1 -> lists:reverse([Curr | Encoded]);
_Else -> lists:reverse([[Rep, Curr] | Encoded])
end;
p13encode([H | L], Curr, Rep, Encoded) ->
case H of
Curr -> p13encode(L, Curr, Rep+1, Encoded);
_Else ->
case Rep of
1 -> p13encode(L, H, 1, [Curr | Encoded]);
_Other -> p13encode(L, H, 1, [[Rep, Curr] | Encoded])
end
end.

%% Duplicate the elements of a list.
%% Example: (dupli ‘(a b c c d)) -> (A A B B C C C C D D)
p14([]) -> [];
p14([H | L]) -> p14duplicate(L, [H, H]).

p14duplicate([], Cloned) -> lists:reverse(Cloned);
p14duplicate([H | L], Cloned) -> p14duplicate(L, [H, H | Cloned]).

%% Replicate the elements of a list a given number of times.
%% Example: (repli ‘(a b c) 3) -> (A A A B B B C C C)
p15([], _Num) -> [];
p15([H | L], Reps) -> p15replicate(L, Reps, [lists:duplicate(Reps, H)]).

p15replicate([], _Reps, Replicated) -> lists:append(lists:reverse(Replicated));
p15replicate([H | L], Reps, Replicated) -> p15replicate(L, Reps, [lists:duplicate(Reps, H) | Replicated]).

%% Drop every N’th element from a list.
%% Example: (drop ‘(a b c d e f g h i k) 3) -> (A B D E G H K)
p16([], _Nth) -> [];
p16([H | L], Nth) -> p16drop(L, Nth, Nth-1, [H]).

p16drop([], _Nth, _Curr, Dropped) -> lists:reverse(Dropped);
p16drop([_H | L], Nth, Curr, Dropped) when Curr == 1 -> p16drop(L, Nth, Nth, Dropped);
p16drop([H | L], Nth, Curr, Dropped) -> p16drop(L, Nth, Curr-1, [H | Dropped]).

%% Split a list into two parts; the length of the first part is given.
%% Do not use any predefined predicates.
%% Example: (split ‘(a b c d e f g h i k) 3) -> ( (A B C) (D E F G H I K))
p17([], _SplitPoint) -> [];
p17(L, SplitPoint) -> p17split(L, SplitPoint, []).

p17split([], _SplitPoint, List) -> lists:reverse(List);
p17split(L, SplitPoint, Head) when SplitPoint == 0 -> [lists:reverse(Head) | [L]];
p17split([H | L], SplitPoint, Head) -> p17split(L, SplitPoint-1, [H | Head]).

%% Extract a slice from a list.
%% Given two indices, I and K, the slice is the list containing the elements
%% between the I’th and K’th element of the original list (both limits included).
%%Start counting the elements with 1.
%% Example: (slice ‘(a b c d e f g h i k) 3 7) -> (C D E F G)
p18([], _Start, _End) -> [];
p18(L, Start, End) -> p18slice(L, Start, End-Start, []).

p18slice([], _Start, _Count, Sliced) -> lists:reverse(Sliced);
p18slice([H | _L], 1, 0, Sliced) -> lists:reverse([H | Sliced]);
p18slice([H | L], 1, Count, Sliced) -> p18slice(L, 1, Count-1, [H | Sliced]);
p18slice([_H | L], Start, Count, Sliced) -> p18slice(L, Start-1, Count, Sliced).

%% Rotate a list N places to the left.
%% Examples: (rotate ‘(a b c d e f g h) 3) -> (D E F G H A B C)
%% (rotate ‘(a b c d e f g h) -2) -> (G H A B C D E F)
%% Hint: Use the predefined functions length and append, as well as the result of problem P17.
p19([], _Rotate) -> [];
p19(L, Rotate) ->
case Rotate of
Point when Rotate > 0 -> Point;
_LT0 -> Point = length(L) + Rotate
end,
[F, B] = lp:p17(L, Point),
B ++ F.

%% Remove the K’th element from a list.
%% Example: (remove-at ‘(a b c d) 2) -> (A C D)
p20([], _Point) -> [];
p20(L, Point) -> p20remove(L, Point, []).

p20remove([], _Point, BeforePoint) -> lists:reverse(BeforePoint);
p20remove([_H | L], 1, BeforePoint) -> lists:reverse(BeforePoint) ++ L;
p20remove([H | L], Point, BeforePoint) -> p20remove(L, Point-1, [H | BeforePoint]).