Let be the first to admit. I am an ignoramoose. I enjoy going to the Cracker Barrel for a good dinner of Chicken and Dumplings. Every time I go, I have to try the peg game that is on every table and almost every time that small little wooden triangle calls me an ignoramoose.
So since I am tired of being put down by block of wood I thought to my self... How could I algorithmically solve such a puzzle. At first thought there are 15 places for a peg to be; that means there is 32,768 possible configurations that the board can be in. That number is small enough for a computer to brute force solve the problem by arranging all the possible boards into a tree structure where the root of the tree is the board with only one peg missing and the leaves of the tree are are boards where there are no more possible moves. Each child node in the tree would be a valid "Jump" applied to its parent. The paths that start at the root of the tree and go down to a leaf that have a length of 13 (there is 14 pegs to start with because one of the holes is empty and you have to leave one peg so 14 - 1 = 13)is a valid solution to the puzzle.
Since we are not interested in all possible solutions just one that works this method would be a over kill. A slightly more efficient approach would be start with the root node and build our tree in a depth first manner until we get a branch in the tree that solves the problem. That is to say we will start with a board with only one peg missing, make a move, keep making moves until we either get stuck or solve the puzzle. If we get stuck undo the moves we made until we are at a spot where we could make another move. When we have back tracked to a spot where we had a choice, we will pick a different move then the one we picked previously. We will continue you on in this manner until the puzzle is solved. When the puzzle is solved we can just go up the tree to find the right sequence of moves that solve the puzzle.
Now comes the issue of translating this algorithm into Python code. First I want to start off by creating a class call PegBoard that will represent a configuration of the pegs. We will do this by using a 2D array of ints where 0 represents an open place, 1 represents a peg, and anything less then one and invalid spot of the board (I know i could have made a jagged array but that makes things ugly in my opnion). My class looks something like this:
class PegBoard:
def __init__(self, pegBoard=None):
if pegBoard:
self.parent=pegBoard
self.board=copy.deepcopy(pegBoard.board)
else:
self.parent=None
self.board = [[1, -8, -8, -8, -8],
[1, 1, -8, -8, -8],
[1, 1, 1, -8, -8],
[1, 1, 1, 1, -8],
[0, 1, 1, 1, 1] ]
def createPossibles(self):
. . .
#Return list of all possible boards
. . .
def printBoard(self):
. . .
. . .
def isWin(self):
score=0
for x in range (len(self.board)):
for y in range(len (self.board[x])):
if self.board[x][y]<1:
continue
score+=1
return score==1
I choose not to write out the createPossibles function because it is very long and boring but be content with that basis of the function is loop over ever peg and see if there is a jump. If there is a jump make a copy of the board, make the jump on the copied board, and append the new board to a list, after checking every peg return the list.
Now that we have our Peg Board we can use the following algorithm to solve the puzzle:
stack = [PegBoard()]
is_winner=False
while len(stack)>0 and not is_winner:
p = stack.pop();
stack.extend (p.createPossibles())
for p in stack:
if p.isWin():
print "FOUND ONE"
stack=[]
while p:
stack.append(p)
p=p.parent
stack.reverse()
for p in stack:
p.printBoard()
is_winner=True
break
if not is_winner:
print "DID NOT FIND ONE"
You maybe thinking "Where is my tree? You promised me a tree and I don't see one". You are partly right in that accusation. We are making a very witty use of a stack to simulate a tree here. We are pushing on the newest possible solutions to the top of the stack. These solutions are currently the deepest leaves on the tree. When we get stuck we remove the top element on the stack which will give us the next possible board that we can start from. If the stack becomes empty and no solution is found then there is no possible solution. This is confusing at first look if you aren't used to stacks as trees.
I will note that this is not the most efficient algorithm by a long shot. For starters its possible two different paths lead to the same dead end. We could record paths to dead ends and when we start down that patch stop then since we know there is no solution at the end of the path. Another optimization would be ignore isomorphic boards that have already been checked. I am calling two boards isomorphic if you could get one board from the other just by rotating the triangle. That is to say, the board with just the top peg missing is really the same as the board the the bottom right peg missing because you could rotate the triangle 60 degrees counter clockwise and get the same board. This puzzle lends its self to be solved by dynamic programming. (My algorithm works fine in this case because there are such few possibilities but as the board got bigger you would need to rework the algorithm to use more dynamic programming techniques).
For the history and other peg games that go far beyond the cracker barrel check out this Wikipedia page:http://en.wikipedia.org/wiki/Peg_solitaire
To try out the code you can use this simple web page here
As my quest for better home automation and move away form OS X continues, I was looking for away to script Pandora on Windows. After Googleing a few times I was unable to find an equivalent to PandoraBoy (http://code.google.com/p/pandoraboy/ scriptable Pandora Client for OS X) for Windows (not that I am complaining, I found PandoraBoy to be buggy when scripting it). I did how ever find an open source project called Open Pandora (http://openpandora.googlepages.com/) that was written in C# and had internal calls to functions like Play, Stop, Next, Like, and Dislike. (And before you ask, it doesn't have all the restrictions that PandoraBoy has, a.k.a. No bugs that I see).
So since there was no scripting interface to Open Pandora I needed to add one. Since the rest of my home automation application is written in Python, the scripting interface needed to accessible to non-.Net languages. This fact rules out the .Net IPC library. Pretty much my entire day job consists of writing WCF code but I fell like that is to heavy of a solution to address this problem. The way I decided to make Open Pandora scriptable is by adding a simple TCP listener into the code. This was when Open Pandora runs it will also listen on a TCP port that I can send command to via any program that has some kind of socket API.
The Open Pandora solution has a file called Pandora.cs that abstracts all the function that the player can do. This is where I decided to add my listener since I would have access to all the functions with out have to modify the rest of the project. Below is a list of code changes I made to the file:
1) Added a global private variable called tcpLinstener of type System.Net.Sockets.TcpListener to the class
private System.Net.Sockets.TcpListener tcpLinstener;
2) In the constructor for the Pandora object, I initialized the listener:
tcpLinstener = new System.Net.Sockets.TcpListener(System.Net.IPAddress.Any, 5654);
tcpLinstener.Start();
tcpLinstener.BeginAcceptTcpClient(new AsyncCallback(GotTcpMsg), null);
3) Now I need to create the call back event handler called GotTcpMsg. This event handler should get the tcp stream, and try and figure out what to do with it. I am also useing an enum to make things more clear:
void GotTcpMsg(IAsyncResult result)
{
System.Net.Sockets.TcpClient client = tcpLinstener.EndAcceptTcpClient(result);
tcpLinstener.BeginAcceptTcpClient(new AsyncCallback(GotTcpMsg), null);
PandoraAction action = (PandoraAction)client.GetStream().ReadByte();
client.Close();
switch (action)
{
case PandoraAction.Hate:
this.Hate();
break;
case PandoraAction.Like:
this.Like();
break;
case PandoraAction.Next:
this.NextTrack();
break;
case PandoraAction.Play:
this.PlayPause();
break;
case PandoraAction.Stop:
this.PlayPause();
break;
case PandoraAction.VolumeUp:
this.VolumeUp();
break;
case PandoraAction.VolumeDown:
this.VolumeDown();
break;
}
}
4) The PandoraAction enum looks something like:
public enum PandoraAction
{
Play=1,
Stop=2,
Next=3,
Like=4,
Hate=5,
VolumeUp=6,
VolumeDown=7
}
And that is all there is to it. If you want the complete source code or binary, go to the contact page and let me know. I am going to attempt to get with the Open Pandora people and try to get his incorporated in to the project. Below are two really short test clients just to see and example of use:
C#)
//This should toggle the playing of Pandora
static void Main(string[] args)
{
System.Net.Sockets.TcpClient client =
new System.Net.Sockets.TcpClient("localhost", 5654);
client.GetStream().WriteByte(1);
client.Close();
}
Python)
The way that I understand The Law of Big Numbers (http://en.wikipedia.org/wiki/Law_of_large_numbers) is that if have X items and you pick one of at random then put it back and pick again at random and do this Y times where Y is a very very big number then you should have picked each item about 1/X% of the time. In other words if you the lottery has 100 balls and they pick every night for forever then each ball should come up about 1/100th of them time. You may be thinking that wrong, random is random.
Picture Credit:www.dilbert.com
Well maybe random is random, but if a number never comes up its not truly random. All numbers must really come up nearly equal number of time to truly be random. So back to the lottery example, does all numbers in the lottery come up an equal number of times. Well lets look at the Georgia Lottery's Mega Millions (http://www.georgialottery.com/stc/games/megaMillions.jsp) game.
Click to enlarge
The above graph shows the frequency that each lotto ball for that past three years or so. Each graph has a horizontal line showing where each bar should come to if every ball came up an equal number of times. Just by glancing over the graph you can tell that the lottery up till now hasn't been 100% even. This makes you think that some balls are now due to come up to make every thing be truly random. So if you believe that the lottery really is a game of chance you would want to know what numbers have came up the least amount of times.
Now before we go to much farther lets consider the other side of the cone for a few minutes. What if the lottery really isn't random. There could be stuff to cause this. For example the number 8 ball must have more paint on it then the number 1 ball because it takes more paint to paint and 8 then it does a 1. This extra paint could make the number 8 ball slightly heaver the number 1 ball and thus come up slightly more often. Another possibility could be when the host of the lottery drawing turns the ball so to face the camera oil form her finger or possible food residue on her hand gets on the ball making it heaver. If this is the case the lottery isn't truly random and you should pick numbers that come up more often.
Which ever way you believe the lottery works you want as much historical data as possible to make your choice on what lottery numbers to pick. This being the case it is not helpful to make all your calculations once and pick those numbers every time; you the most up to date numbers possible because trends may change or emerge with new numbers. Below is a python script presented as a psp page that will download all of Georgia Lottery's Mega Million numbers since June 2005 (Mega Millions was around before June 2005 but on that date the changed the rules so that the highest ball that was possible was changed) till the present and calculate the 5 most winning white balls, that most winning Mega Ball, the 5 least winning white balls, and the least winning Mega Ball. The script is presented as a psp page so that you can pull the information down on your mobile phone when you are buying your lottery tickets.
View at demo of the script at http://www.jonlathem.com/python/lotto.psp. The top set is the least winning numbers and the bottom set is the most winning numbers. The last ball in each set is the money ball.
<html>
<body>
<%
from mod_python import apache
from urllib2 import urlopen
import re
MaxWhiteBall = 56
MaxMoneyBall = 46
p = re.compile (r'^"\d+/\d+/\d+","(\d\d)-(\d\d)-(\d\d)-(\d\d)-(\d\d) MB=(\d\d)"$')
f = urlopen ("http://www.georgialottery.com/serv/do/historyView?game=megaMillion&outputType=2&viewType=3&csvStartMonth=5&csvStartDay=22&csvStartYear=2005&csvEndMonth=11&csvEndDay=31&csvEndYear=2010")
WhiteBallFreqDict = {}.fromkeys(range (1, MaxWhiteBall+1), 0)
MoneyBallFreqDict = {}.fromkeys(range (1, MaxMoneyBall+1), 0)
for line in f:
m=p.match(line[:-2])
if m:
for i in range (5):
WhiteBallFreqDict[int (m.groups(1)[i])]+=1
MoneyBallFreqDict[int (m.groups(1)[5])]+=1
f.close()
MoneyBallPairs = (zip (MoneyBallFreqDict.values(), MoneyBallFreqDict.keys()))
MoneyBallPairs.sort()
WhiteBallPairs = (zip (WhiteBallFreqDict.values(), WhiteBallFreqDict.keys()))
WhiteBallPairs.sort()
req.write("Lossing: "+str(WhiteBallPairs[0][1]) + ", " + str(WhiteBallPairs[1][1]) + ", " + str(WhiteBallPairs[2][1]) + ", " +str(WhiteBallPairs[3][1]) + ", " + str(WhiteBallPairs[4][1]) + " Money Ball:" + str(MoneyBallPairs[0][1]) )
req.write("<br/>")
req.write("Winning: "+str(WhiteBallPairs[MaxWhiteBall-1][1]) + ", " + str(WhiteBallPairs[MaxWhiteBall-2][1]) + ", " + str(WhiteBallPairs[MaxWhiteBall-3][1]) + ", " + str(WhiteBallPairs[MaxWhiteBall-4][1]) + ", " + str(WhiteBallPairs[MaxWhiteBall-5][1]) + " Money Ball: " + str(MoneyBallPairs[MaxMoneyBall-1][1]))
%>
</body>
</html>