Archive for the ‘Math’ Category

Neil Freeman’s “Electoral College Reform” Map

Sunday, March 3rd, 2013

A few weeks ago a pretty cool map popped up on the internet: it’s a redrawing of U.S. state lines to create fifty regions with equal population. The goal is to end the disparity between popular vote and electoral college vote, and normalize the value of each person’s individual vote in both presidential and congressional elections. You should check it out here if you haven’t seen it, it’s quite fascinating: http://fakeisthenewreal.org/reform/.

There are many things I like about this map. It’s drawn based on both population distribution and commute patterns, so few people will have to cross a state line to drive to work despite the massive redrawing. The state names are whimsical but logical, based mostly on landscape features whose names we don’t usually see in common usage at least in other parts of the country. “Big Thicket” and “Firelands” look like they come from a fantasy novel, while “Shenandoah” and “Atchafalaya” are compelling for their unusual lettering and sound. I can’t help but imagine the map as describing an alternate reality United States, where history and culture are divergent just like the state boundaries. How different would history have been if there were no Mason-Dixon line? What would happen to college and professional sports if the states were so sharply divided between rural and urban?

As much as I like the map (to be fair, I’m likely to buy the poster once it’s available), there are a few ways in which it bothers my inner nerd:

1. There’s no quadripoint; no equivalent of the “4-corners” intersection between Colorado, Utah, New Mexico, and Arizona. This is disappointing since it’s one of my favorite quirks of the current U. S. layout. Quadripoints seem to me impossibly unlikely without some human intervention in border definition, which the current U.S. layout certainly had a lot of (witness the presence of so many straight lines). I suppose it’s inevitable that a programmatically-generated map is almost certain to have few such quirks, but it feels like some amount of human expression is lost in the transition.

2. It removes the elegant game mechanic of the unequal distribution of voting power between the House and Senate. The current system, where large states get over-represented in the House and small states get over-represented in the Senate, has always struck me as a clever way to create interesting discussions about how different types of legislation benefit different subsections of the population. I really like that it leads to different value systems and platform distributions between the two houses; it seems like this would likely contribute to more thoughtful legislation in the bills that can pass both houses. If we instead tried to make each state equally well-represented in both houses, the only differentiator left would be the longer term length in the Senate.

 

Dictionary update: middle-based trees

Sunday, March 14th, 2010

I’m working out a way to do queries on a dictionary based on something other than the start of the word. Here’s a rough draft of the data structure I have in mind:

Sample tree

The idea is that given a letter “s” in this example, this tree will let us answer the question: Are there words in which an ‘s’ is preceded by an ‘a’ and followed by a ‘t’?. Since the root s node has a child node a-t, the answer is Yes. We can then ask the next logical question Are there words in which “ast” is preceded by an ‘f’ and followed by nothing?. This can go on as long as needed to do smart searching of the dictionary space.

The application I have in mind for this is word puzzles. For example, when doing a cryptoquote we might see a word like this *o**os*. We can use this tree to start at one of the interior characters and figure out what possible letters could be in the adjacent unknown spots, by checking whether the nodes exist in the tree or not.

Now I need to implement this structure in a usable class, and do the creation when loading my dictionary.

Start of “Dictionary” assembly

Tuesday, March 9th, 2010

Been doing a lot of Cryptoquotes lately, which has led me to get interested in seeing whether these can be solved programmatically. It seems like there are a few bottlenecks (double letters, short words, contractions) that have only a handful of possible translations, and knowing the possibilities for these can lead to solutions very quickly.

It also feels like a computer should be able to answer questions like “What are all the words that have the pattern abCCdEE?” once we have a reasonably robust dictionary structure.

In order to start working towards this goal, I refactored the dictionary logic out of my WordBridge game into a separate assembly that I can start using to build a Cryptoquote solver. It’s good practice for multi-component programming in C# as well.

Right now it only has the ability to tell you whether a given string is a word or not (admittedly, this is the key piece of functionality). Here’s the signature:

Beginning stages of my Dictionary code

Beginning stages of my Dictionary code

namespace DictionaryClasses
{
public class Dictionary
{
//The dictionary itself contains the root node of the dictionary nodes tree – this node points to all other nodes
private DictionaryClasses.DictionaryNode dictionaryRoot = new DictionaryClasses.DictionaryNode();
/// <summary>
/// Create the dictionary data structure on program load
/// </summary>
public bool Initialize(string RelativePath)
{
//file input setup
FileStream input;
try { input = File.OpenRead(RelativePath); }
catch (FileNotFoundException) { return false; }
BinaryReader reader;
reader = new BinaryReader(input);
//looping constants
char currentChar;
//string currentString;
bool endWord = false;
bool endFile = false;
//dictionary itself
DictionaryClasses.DictionaryNode currentNode;
DictionaryClasses.DictionaryNode childNode;
currentNode = dictionaryRoot;
childNode = new DictionaryClasses.DictionaryNode();
//loop over the words
do
{
//reset the word-level vars
endWord = false;
//mark the current word as valid (add terminator)
currentNode.IsTerminator = true;
//move the node marker back to the top
currentNode = dictionaryRoot;
//loop over the chars in the word
do
{
currentChar = reader.ReadChar();
if (currentChar == ‘\r’)
{
endWord = true;
}
else if (Utils.IsAlphabetLetter(currentChar))
{
//add to dictionary, if not already there
if (!(currentNode.ChildExists(currentChar)))
{
currentNode.AddChild(currentChar);
}
currentNode = currentNode.GetChild(currentChar);
}
} while (endWord != true);
//clear out the \n as well, and see if we’ve hit the end
currentChar = reader.ReadChar();
if (reader.PeekChar() == -1)
{
endFile = true;
}
} while (endFile != true);
//we exited gracefully, so return true
return true;
}
/// <summary>
/// True if the string is a word in our dictionary
/// </summary>
/// <param name=”testString”></param>
/// <returns></returns>
public bool IsWord(string testString)
{
char testChar;
DictionaryClasses.DictionaryNode currentNode;
currentNode = dictionaryRoot;
if (currentNode == null) { return false; }
for (int i = 0; i < testString.Length; i++)
{
testChar = System.Convert.ToChar(testString.Substring(i, 1));
if (!(Utils.IsAlphabetLetter(testChar)))
{
return false;
}
else if (!(currentNode.ChildExists(testChar)))
{
return false;
}
else
{
currentNode = currentNode.GetChild(testChar);
}
}
//now that we’re at the end, see whether this is a valid terminator
if (currentNode.IsTerminator)
{
return true;
}
else
{
return false;
}
}
/// <summary>
/// True if the string is the stem of a word in our dictionary
/// </summary>
/// <param name=”testString”></param>
/// <returns></returns>
public bool IsWordStem(string testString)
{
char testChar;
DictionaryClasses.DictionaryNode currentNode;
currentNode = dictionaryRoot;
if (currentNode == null) { return false; }
for (int i = 0; i < testString.Length; i++)
{
testChar = System.Convert.ToChar(testString.Substring(i, 1));
if (!(Utils.IsAlphabetLetter(testChar)))
{
return false;
}
else if (!(currentNode.ChildExists(testChar)))
{
return false;
}
else
{
currentNode = currentNode.GetChild(testChar);
}
}
//return if we got this far – don’t care about terminator check
return true;
}
}
}If

If you’re doing any programming in .NET or COM, you can grab it from here: http://www.letxbe.com/Dictionary.dll . Note that you’ll need to have your own .txt file to read from (passed in Initialize). There are lots of them out there and I haven’t figured out which one is best yet.

The River

Friday, December 11th, 2009

Have you ever seen the subtitle of this blog and wondered what it’s about?

The first part is a pretty well-known riddle:

A traveler has a wolf, a sheep, and a cabbage. He needs to get across a river in a boat, but the boat is very tiny and can only carry him and one other item or animal. So in order to get across, he needs to take one thing across at a time. The catch is that the wolf will eat the sheep if left alone with it, and the sheep will eat the cabbage if left alone with it. What are the steps he needs to take to get across? You can find a pretty good summary here, and some discussion here.

The last item in my list, a native with blue eyes, is a much more obscure (and more rewarding) logic puzzle. I’ll post more about it later.

Project Euler

Sunday, June 28th, 2009

For the last couple years I’ve been working on a challenge called “Project Euler”. It’s a combination of math and programming, where you answer increasingly difficult math questions and compete with other people in the project.

It’s a nice way to keep in practice in a structured way. I’ve used Java and C# for various puzzles, as well as trying to get into Python for a bit. I think I’m settling on C# as my language of choice, because the IDE is definitely superior.

One of the biggest limitations of using programming to solve these problems is limitations on number size. In order to avoid making the puzzles trivial, the folks at Project Euler often force you to deal with extremely large numbers that won’t fit inside the standard 8/16/32-bit variables.

To get around this, I’m starting to implement a suggestion of Sam’s: create my own number class that can hold numbers of arbitrary size.

Here’s my first success with the “EulerNumber” class:

increment

It adds any two numbers together – provided the numbers have fewer than 2.147 billion digits.