50 States Problem
The 50 states problem is fairly simple. Given a list of the 50 states of the U.S.A.:
Take the names of two U.S. States, mix them all together, then rearrange the letters to form the names of two other U.S. States. What states are these?
For the keen reader, a PHP-style array of the state is:
$states = array("alabama","alaska","arizona","arkansas","california","colorado", "connecticut","delaware","florida","georgia","hawaii","idaho", "illinois","indiana","iowa","kansas","kentucky","louisiana", "maine","maryland","massachusetts","michigan","minnesota", "mississippi","missouri","montana","nebraska","nevada", "newhampshire","newjersey","newmexico","newyork","northcarolina", "northdakota","ohio","oklahoma","oregon","pennsylvania","rhodeisland", "southcarolina","southdakota","tennessee","texas","utah","vermont", "virginia","washington","westvirginia","wisconsin","wyoming");
Files
Reverse Polish Notation in JFlex
JFlex is a popular lexical analyzer generator implemented in Java. Whilst JFlex is often found in tandem with a LALR parser generator (such as CUP) it can be used to build standalone applications, such as a Reverse Polish Notation calculator.
Reverse Polish Notation is a method of specifying calculations without the order of operations being explicitly specified. In in-fix notation an expression such as 1+2*3 could be ambiguous. If the expression is lead from left-to-right the result would be 9, but the prescribed order of operations defines the answer to be 7. Using this common style requires the order of operation to be known.
Reverse Polish Notation is much simpler to process because the order of operations is defined by the structure of the expression: 1 2 3 * +. The solution is (2*3) + 1 = 7. A calculator can be easily implemented using a stack:
- PUSH 1
- PUSH 2
- PUSH 3
- temp = POP * POP
- PUSH temp(6)
- temp = POP + POP
- PUSH temp(7)
The result can them be popped from the top of the stack.
The JFlex tool can be used to rapidly build this functionality, using a few patterns to match numbers and mathematical operators. The result is a little under 30 lines of definition.
Files
Building and Usage Instructions
You must have both JFlex and javac installed, I shall assume they are on the current path. I shall also assume that RPN.flex is in the current working directory.
- jflex RPN.flex
- javac RPN.javac
To run, the RPN must be in a plaintext file. The can contain any number of valid expressions in RPN, they should be terminated by any non-numeric or operator character (the equals sign would do).
- java RPN input.txt
If the expression is not valid a warning message will be displayed.
Translating Times - a quick one liner
I found this programming challenge on a mailing list:
Given a string that could contain arithmetic expressions, with the addition that numeric constants could be potentially expressed as times, e.g 1:36 for 96 seconds, or 2:10:08 for 2 hours 10 minutes and 8 seconds, also decimal fractions after seconds are allowed, e.g 3:45.6 or 3:40:50.67, replace all the time values with their equivalent number of seconds.
There were a few solutions in Perl, PHP and Python. They were all huge – including one monster state machine in 200 lines of C! Mine is a little more concise – a single statement of PHP:
print preg_replace_callback("|(\d{1,2}):(\d{1,2}):{0,1}(\d{1,2}){0,1}\.{0,1}(\d+){0,1}|si", create_function('$matches', 'return $matches[3] ? $matches[1] * 3600 + $matches[2] * 60 + $matches[3] + $matches[4] / 10 : $matches[1] * 60 + $matches[2] + $matches[4] / 10;'), $subject);
Problem Solved!
It's a Small World: Solution
My solution to this puzzle consists of 57 lines of PHP, and can be downloaded in the ‘Files’ section below. It is designed to run under the PHP CLI environment. It accepts a single argument as input, which is the path of a file containing the latitude/longitude definitions.
The program works exactly to specification, returning a list of each friend and the three others closest to them in O(n^2) time. In addition, the program allows the number of friends returned to be modified through a constant.
Parsing the Input File
The input file has a relatively simple structure, and is simple to parse using a regular expression. The excellent tool by Grant Skinner makes it simple to build and test the expression in real time. The somewhat trivial expression is:
|([1-9][0-9]*)\s+(-{0,1}\d+.\d+)\s+(-{0,1}\d+.\d+)|si
The PHP function preg_match_all rapidly builds an array of with all the data sorted into an accessible format.
Finding the Nearest Neighbour
Since we can assume the world is flat (incidentally Flatland by Edwin A. Abbott is a good read), finding the distance between two neighbours is a simple case of Pythagorus’ Theorem. This can be implemented in a single line of PHP:
pow(pow($latA-$latB, 2) + pow($lonA-$lonB, 2), 0.5);
Iterating over every friend in the input gives a O(n) means of finding the nearest neighbour in the function:
find_closest($k, $sourceData, $excluding=array())
The optional array $excluding gives a means to find the second nearest, by eliminating possible points.
Extending to the Spherical World
It would be simple to extend this model to the spherical world by replacing the distance calculation formula. Using the Great Circle Formula instead. coming soon
Wrapping it Up
Since the program is allowed O(n^2) running time, it is possible to iterate through each friend listed, calculate the nearest neighbours and output.
Files and Downloads
Other Solutions
coming soon
Comment [2]
It's a Small World
As a popular engineer, you know many people in your home city. While traveling around town, visiting your friends, you realize it would be really handy to have a program that tells you which of your friends are closest based upon which friend you are currently visiting.
This sandbox project is a solution to the Facebook developer puzzle It’s a Small World and all text on this page is taken from the challenge specification.
Being an engineer who is interested in writing software that is useful to everyone, you decide to write a general solution to your quandary. Each of your friends lives at a unique latitude and longitude. For the purposes of this program, the world is flat, and the latitude and longitude are for all intents and purposes Cartesian coordinates on a flat plane. For example, in our flat world, lat 45, long -179 is not as close to lat 45, long 179 when compared to lat 45, long 170.
Write a program that takes a single argument on the command line. This argument must be a file name which contains the input data. Your program should output the nearest three other friends for each friend in the list. You are virtually a celebrity and your friend list can be astoundingly huge; your program must have a running time of faster than O(n^2) and be robust and resource efficient.
Input Specifications
The input file consists of multiple lines, all of which follow the same format. Each line has three values separated by an amount of white space. The first value is the unique id number of that friend, expressed as an integer. The second value is the latitude of that friend, expressed as a float or integer. The third and last value is the longitude of that friend, expressed as a float or integer. Every friend lives at a unique combination of latitude and longitude (e.g. no two friends will ever share the exact same values). Each line ends with a single new line, except for the last line of the file, which may or may not have a terminating new line.
Example input file:
1 0.0 0.0 2 10.1 -10.1 3 -12.2 12.2 4 38.3 38.3 5 79.99 179.99
You are guaranteed that your program will run against an input file that is well formed, and has at least four lines. You are also guaranteed that your list of friends have unique distances between one another; no two distinct pairs of friends will have the same distance between them.
Output Specifications
In the order presented in the input file, output the nearest three friends for each friend. Each line of output should start with the integer id of the friend followed by a single space character, and then the list of three nearest other friend ids followed by a single new line. Even the last line of the output should terminate in a new line. This list should be comma-delimited, with no spaces. The list must be in order of proximity, with the closest of the three being first, and the farthest of the three being last.
Example output:
1 2,3,4 2 1,3,4 3 1,2,4 4 1,2,3 5 4,3,1
Solution
My solution to this is outlined on the next page.