fragmentary ideas ䷿ intellectual what-nots ䷷ and haskell programming ䷴

Computer science is a fascinating and maddening thing. Even the most seemingly-esoteric topics turn out to be fundamental. Go out to the fringes of CS and you find yourself smack in the middle of Philosophy. You try to understand a single point and you suddenly find yourself embracing everything.

So this post comes from that infinitely-recursive rabbit hole of wikipedia topics I’ve been falling down for the last few weeks, and you can probably expect a few more like this one; I’ll try to keep focused.

We begin (as do All Good Things) with the Untyped Lambda Calculus:
Read the rest of this article »

The Problem

Problem A in the qualifying round of this year’s Google CodeJam contest was really clever. The problem used a classic made-for-TV gadget from the 80s: The Clapper™ (“snapper” in google’s version) and went like this:

The Snapper is a clever little device that, on one side, plugs its input plug into an output socket, and, on the other side, exposes an output socket for plugging in a light or other device.

When a Snapper is in the ON state and is receiving power from its input plug, then the device connected to its output socket is receiving power as well. When you snap your fingers — making a clicking sound — any Snapper receiving power at the time of the snap toggles between the ON and OFF states.

In hopes of destroying the universe by means of a singularity, I have purchased N Snapper devices and chained them together by plugging the first one into a power socket, the second one into the first one, and so on. The light is plugged into the Nth Snapper.

Initially, all the Snappers are in the OFF state, so only the first one is receiving power from the socket, and the light is off. I snap my fingers once, which toggles the first Snapper into the ON state and gives power to the second one. I snap my fingers again, which toggles both Snappers and then promptly cuts power off from the second one, leaving it in the ON state, but with no power. I snap my fingers the third time, which toggles the first Snapper again and gives power to the second one. Now both Snappers are in the ON state, and if my light is plugged into the second Snapper it will be on.

I keep doing this for hours. Will the light be on or off after I have snapped my fingers K times? The light is on if and only if it’s receiving power from the Snapper it’s plugged into.

Read the rest of this article »

I came up with what I think is an elegant use of monadic code, while working on a program to compute solutions to the Postage Stamp Problem. The problem asks:

Consider that an envelope is able to hold a limited number of postage stamps. Then, consider the set of the values of the stamps — positive integers only. Then, what is the smallest total postage which *cannot* be put onto the envelope?

The algorithm below takes a number of stamps that can fit and a total postage to apply and returns a list of all the sets of different stamp values that can be combined to form the target postage sum:

Thus the potential stamp combinations for a letter which can hold three stamps and costing 5 cents to mail would be:

*Main> sumLists 3 5
[[0,0,5],[0,1,4],[0,2,3],[1,1,3],[1,2,2]]

As you can see, the algorithm also produces ordered lists naturally!

But perhaps all we care about are unique stamp values that. If we want to adjust our goal such that the algorithm returns a list of all sets of unique stamp values sufficient to create the target postage, we need only adjust the return line:

>                  return (a : dropWhile (==a) as) 

Similarly we could drop the zeros (which mean “no stamp” in our case) from the beginnings of each set if we desired. The above code have applications to many similar problems including Subset Sum, and Knapsack as well as other partitioning problems.