Boy Plankton
Stuff that interests me.
Stuff that interests me.
Apr 10th
Haskell is an interesting language. Forces you to break the problem up into small pieces. Haskell is the seventh language featured in Seven Languages in Seven Weeks and the fifth problem for day 1 of Haskell has kept me stumped for a couple of days now. You are expected to write a Haskell version of the map-coloring problem from the Prolog chapter.
You are given a map of the southeast corner of the United States. You have to write a program to color the five states so that no two states that border each other are colored the same.
First you have to setup the problem.
states = [ "Tennessee", "Mississippi", "Alabama", "Georgia", "Florida" ] borders = [ [ "Mississippi", "Tennessee" ], [ "Mississippi", "Alabama" ], [ "Alabama", "Tennessee" ], [ "Alabama", "Mississippi" ], [ "Alabama", "Georgia" ], [ "Alabama", "Florida" ], [ "Georgia", "Florida" ], [ "Georgia", "Tennessee" ] ] colors = [ "red", "green", "blue" ]
This is a quick function to get a list of the states that border one of the states.
getBorders y = [ last x | x <- borders, head x == y ]
I needed a list of the colors of bordering states that had already been assigned colors.
getBorderColors y z = [ last x | x <- y, any ( == head x ) ( getBorders z ) ]
This function takes a list of colors and figures out which colors are still available for a state.
colorsLeft :: [[Char]] -> [[Char]] colorsLeft [] = colors colorsLeft (x:xs) = [ y | y <- colorsLeft xs, x /= y ]
Finally, we iterate through the list of states and assign them colors.
mapColors xs = helper [] xs where helper sol (x:xs) = helper ([ x, head ( colorsLeft ( getBorderColors sol x ))] : sol ) xs helper sol _ = sol
Load and execute …
*Main> mapColors states [["Florida","red"],["Georgia","green"],["Alabama","blue"],["Mississippi","green"],["Tennessee","red"]]
I’m certain that this solution is less than optimal. Still, it’s the first one I came up with that produced the correct answer.
Mar 21st
Charlieplexing is a multiplexing technique for driving LED’s using fewer IO pins. You can use it to control N*(N-1) LED’s where N is the number of IO pins that you are using. It works because the IO pins on a microcontroller have three available states. If the pin is set to output then it can output a 1 or 0. The third state is input, where the pin is set to high impedance and is effectively disconnected from the circuit.
This is the example circuit from the Wikipedia entry referenced above. There are three pins being used to drive six LED’s. Two pins have to be set to output, one high and one low, and one pin has to be disconnected from the circuit in order to address an LED.
Here is the example circuit on my breadboard. It’s being driven by a TI MSP430.
I found that the quickest way to make it work was to set all the pins so that they were inputs, then override the two that I needed as outputs and finally set the one pin that I wanted to output a 1.
Mar 20th
The solution for calculating the distance between any two points on a sphere is an equation called the Haversine Formula. It can be used to estimate the distance between any two points on Earth using their latitude and longitude by making the assumption that the Earth is a perfect sphere. It isn’t, but for some applications the approximation is good enough.
Here’s an example calculating the distance of two points using Python:
def min( val1, val2 ): if val1 > val2: return val2 else: return val1 def haversine( lat1, lon1, lat2, lon2 ): dlat = math.radians( lat2 - lat1 ) dlon = math.radians( lon2 - lon1 ) a = math.sin(dlat/2)**2 + math.cos(math.radians(lat1)) * math.cos(math.radians(lat2)) * math.sin(dlon/2)**2 return 2*math.asin(min(1,math.sqrt(a)))
Calculating the distance between Los Angeles and New York City in kilometers:
>>> haversine( 34.05, -118.24, 40.71, -74.00 ) * 6367 3933.5883159892405
Same example, miles this time:
>>> haversine( 34.05, -118.24, 40.71, -74.00 ) * 3956 2444.0514179446263