Preface:
This was my semester project for the class "Principles of Optimization" which was one of my absolute favorite classes that I took in college. It uses WordNet, which is a fantastic database for looking at relationships between English words, (it seems to be the basis of many online tools such as the Visual Thesuarus that is constantly advertised on dictionary.com, it was fun to see how the graphs I made for this project exactly matched the content of Visual Thesuarus, a website that seems to be just begging for an open-source ripoff...). To access WordNet, I used the Perl library WordNet::QueryData which seemed to work quite well. For the Integer Programming, I had a much harder time, I used the library Math::GLPK which has bugs that confused me for quite a while (I wish I remembered what they were, but I don't, all I remember is a general feeling of frustration with the library), if I were to redo this project, I'd take a different approach, maybe writing lp text files and solving with the glpk command line interface, or maybe using Python to interface with an IP solver. I used Cytoscape to generate the network graphs.
For those just here for example code for WordNet::QueryData, or Math::GLPK,
you can find it in a the perl file that you can download here. All others, Read On!
Showing posts with label perl. Show all posts
Showing posts with label perl. Show all posts
Saturday, April 12, 2014
Wednesday, May 29, 2013
The highschool math club problem that bugged me for entirely too long
There is a grid of digits and arithmetic operators, certain paths through the grid result in true mathematical statements. The challenge is to find all of the true statements in the grid.
It's really not that hard of a problem to solve by brute force. I at the time of the competition I tried writing a program to solve it (in the Blitzmax language, because that was the language I knew best at the time). But for whatever reason, I couldn't get it to work quite right.
Fast forward a few years, and it was still bugging me that I never solved that problem, so I wrote up a perl script to do it.
which can be found here:
https://bitbucket.org/seanrjohnson/tiler
Basically, it's a recursive algorithm that checks every possible path through the puzzle.
The problem can be thought of as an undirected graph. Solutions consist of sets of connected nodes, where each node in the set is passed just once in the traversal. A set of connected nodes is a solution if the values of the nodes, in order, make a valid mathematical statement. Even though the graph is not directional, the solutions are. Because, for example:
15*3 = 45, but 54 != 3*51
(at first I had written: 12*3 = 36, but 63 != 3*21... :-P )
In general, the reverse string of a true mathematical equation is usually not true. So every path, in both directions must be checked.
There are multiple ways to do this, but this algorithm does it by iterating through all of the nodes in the graph (tiles in the puzzle), and finding all possible sets of connected nodes that have that node as the starting point, and which of those sets spell correct equations.
Looking at that perl script now, I see lots of things that make me cringe: for example the regex to parse the input is not quite correct, the data structures I used are probably not the best for this problem (better to preprocess the data into lists probably), and others. Notwithstanding that it does solve the problem it was intended to solve, and since none of the tile-sets given were very large, it solves them instantaneously.
It's really not that hard of a problem to solve by brute force. I at the time of the competition I tried writing a program to solve it (in the Blitzmax language, because that was the language I knew best at the time). But for whatever reason, I couldn't get it to work quite right.
Fast forward a few years, and it was still bugging me that I never solved that problem, so I wrote up a perl script to do it.
which can be found here:
https://bitbucket.org/seanrjohnson/tiler
Basically, it's a recursive algorithm that checks every possible path through the puzzle.
The problem can be thought of as an undirected graph. Solutions consist of sets of connected nodes, where each node in the set is passed just once in the traversal. A set of connected nodes is a solution if the values of the nodes, in order, make a valid mathematical statement. Even though the graph is not directional, the solutions are. Because, for example:
15*3 = 45, but 54 != 3*51
(at first I had written: 12*3 = 36, but 63 != 3*21... :-P )
In general, the reverse string of a true mathematical equation is usually not true. So every path, in both directions must be checked.
There are multiple ways to do this, but this algorithm does it by iterating through all of the nodes in the graph (tiles in the puzzle), and finding all possible sets of connected nodes that have that node as the starting point, and which of those sets spell correct equations.
Looking at that perl script now, I see lots of things that make me cringe: for example the regex to parse the input is not quite correct, the data structures I used are probably not the best for this problem (better to preprocess the data into lists probably), and others. Notwithstanding that it does solve the problem it was intended to solve, and since none of the tile-sets given were very large, it solves them instantaneously.
Subscribe to:
Posts (Atom)