Archive for the ‘Geekdom’ Category

cribbage.erl

Monday, May 28th, 2007

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.

Remove nested arrays in javascript using the prototype library

Tuesday, May 22nd, 2007

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.

Recursive FTP

Wednesday, May 9th, 2007

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.

Drop down menus

Thursday, April 26th, 2007

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.

Sweet Battery

Thursday, March 29th, 2007

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.

Pi Day 2007

Tuesday, March 13th, 2007

Happy Pi Day (3-14, duh). Search pi for sequences of numbers, like your birthday, SSN, phone number, etc here. The page also has a good bit of Pi trivia.

Crazy addictive game

Sunday, February 4th, 2007

Flow in Games provides quite an adventure in gaming. It is no secret that I am not a big player of mainstream console and computer games, and games like Flow confirm that I am not missing out. The combination of visual, aural, and tactical elements creates quite a pleasant experience. I hardly noticed that I had wasted three hours playing! The rules are simple (like most fun games) – eat and evolve, kill or be killed. I think this is a great game for kids because it has a requires some anticipation and coordination skills to time attacks and stirke at the food. I know many more of my hours will be spent playing.

Futuristic interaction with computers…now!

Sunday, January 21st, 2007

Holy heck. This demo will blow you away. Makes the iPhone look silly. Minority Report-esque computer interaction is very near. View the demo here.

UPDATE: More UI eye candy!

E-99: 31-40

Sunday, January 7th, 2007

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.

E-99: 21-30

Sunday, January 7th, 2007

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).