F# and Functional Pearls

After encountering the language last year, I've finally gotten around to studying F# from Expert F#. So far, the language has proven much friendlier than Haskell (though it's not really a fair comparison since I'm now more aware of functional constructs).

As practice, I've started implementing some Project Euler problems in F#. I've also been working on porting some Haskell "functional pearls" from Richard Bird's excellent book Pearls of Functional Algorithm Design. The going is slow but rewarding, as it's turning out to be a great way to practice F# while also learning more about functional programming in general.

One chapter that I've worked on is the "countdown" problem, in which the goal is to use some numbers from a given list to generate an arithmetic expression that evaluates to a value as close to target as possible. For example, given a list of numbers [1, 3, 7, 10, 25, 50] and a target of 831, the solution is: 

> display(countdown1 831 [1;3;7;10;25;50]);;

(7+((1+10)*(25+50))) = 832

https://github.com/tkuriyama/functional-pearls/tree/master/countdown

Longest Subpalindrome in Linear Time

I've finally rewritten the linear time algorithm for finding the longest palindromic substring ("subpalindrome") within a given string. I originally came across this problem in Peter Norvig's class on Udacity and have worked on it quite a bit since then.

I'm not altogether satisfied with the clarity of the code -- it is quite imperative and stateful, with many indexing variables -- but I don't see a way to meaningfully refactor without changing the fundamental structure, so I'll leave that for another day.


Algorithm Description and Visualization
http://tarokuriyama.com/projects/palindrome2.php

Code
https://github.com/tkuriyama/palindrome

Blacksmith Puzzle Solved

The blacksmith puzzle from a previous blog post is now solved!

I experimented with a number of heuristics, but I wasn't able to come up with a very good way to rank next moves.

In the end, the combinatorial solution works fine -- it's just that the solution space was unnecessarily polluted by permutations of the same visited states. Modifying the hash of visited states to use sorting ensures uniqueness, and the solution now runs in a few seconds. Interestingly, the magic number of 13 chain links appears to be necessary, as the solver didn't find a solution when fed 12 chain links as a starting state.

https://gist.github.com/tkuriyama/8de2711675350645349d

Russian Railroad Puzzle

This was a fun and quick puzzle as the technique from Peter Norvig's solution to the Zebra Puzzle can be reused directly. It's very nice to be able to formulate the conditions in terms that are clear and almost like plain English.

https://gist.github.com/tkuriyama/5a0f5d886a3578a72d58

Passengers in a Railroad Compartment 

Six passengers sharing a train compartment are from Moscow, Leningrad, Tula, Kiev, Kharkov, and Odessa.

1. A and the man from Moscow are physicians 
2. E and the Leningrader are teachers. 
3. The man from Tula and C are engineers. 
4. B and F are WWII veterans, but the man from Tula has never served in the armed forces. 
5. The man from Kharkov is older than A. 
6. The man from Odessa is older than C. 
7. At Kiev, B and the man from Moscow got off. 
8. At Vinnitsa, C and the man from Kharkov got off. 

Match initials, professions, and cities. Also, are the facts both sufficient and necessary to solve the problem? 

from Boris A Kordemksy, The Moscow Puzzles: 359 Mathematical Recreations, p111.

Blacksmith Khecho's Ingenuity

Another puzzle from Dover's Moscow Puzzles. Building on similar structures and ideas to The Whims of Three Girls, it was much easier to conceive and develop a combinatorial solution for this one.

However... the solution does not terminate!

Presumably this is due to the combinatorial search space being much larger -- even with a small sub-problem with two people weighing 20 and 30 pounds and six of the 10-pound chains, the solver finds 226 solutions.

Solution # 1 of 226 

[20, 30, 10, 10, 10, 10, 10, 10] | * [] --- []  | []
[10, 10, 10, 10, 10, 20, 30] |  [10] --- [] * | []
[10, 10, 10, 10, 20, 30] |  [10] --- [10] * | []
[10, 10, 10, 20, 30] | * [10] --- [10, 10]  | []
[10, 10, 10, 30] |  [10, 20] --- [10, 10] * | []
[10, 10, 10, 30] | * [10] --- [10, 10]  | [20]
[10, 10, 10, 10, 30] | * [] --- [10, 10]  | [20]
[10, 10, 10, 10] |  [30] --- [10, 10] * | [20]
[10, 10, 10, 10] | * [] --- [10, 10]  | [20, 30]

When I use the problem inputs, the solution candidate stack hovers rises steadily to about 1000 candidates, falls to 700 or so over a minute or two, and begins to rise steadily thereafter.

The optimization is interesting to think about because it is not obvious how to evaluate the merits of different states. The only trivial optimization I've done is to permit people to jump off the balance and crash it, if the move results in a complete puzzle (not explicitly addressed in the problem statement, and a plausible interpretation).

I will come back to this later as I haven't made much progress in the past day.

The Whims of Three Girls

3 girls, each with her father, go for a stroll. They come to a small river. One boat, able to carry 2 persons at a time, is at their disposal. Crossing would be simple for everyone except the girls. None is willing to be in the boat or ashore with 1 or 2 strange fathers, unless her own father is present too. How do they all get across?

I came across the above in a book of puzzles. It's an interesting exercise in modeling a game space and generating correct state progressions. I started working on a Haskell version with a friend but the full script is still well beyond my reach. Meanwhile, my Python version works reasonably well and BFS returns what appears to be a minimum-length solution in approximately 75 ms on my 2014 MacBook Pro.  This served as yet another lesson in the importance of modularity and testing to the end of writing code that's clear and correct. More practice required...

https://github.com/tkuriyama/fording-puzzle

DNA Sequencing

A quick post before July expires...

I've been following Algorithms for DNA Sequencing on Coursera this month. As one might imagine, it's mainly about algorithms related to string / sequence matching and alignment. The "sequence assembly" problem is something I haven't come across before and is quite intriguing -- especially how it relates to the history of the human genome project.

I'm a little surprised by the course because I realize, in comparison, how good almost every other Coursera course I've taken has been. This course is about what you'd expect in a resource that's available for free: the instructor is clearly knowledgeable and interested in teaching, but the details are often vague and the explanation of algorithms are not very rigorous. It's still excellent as freeware, but I'm not sure I'd be happy if I'd paid Coursera to take the course as a "Signature Track" student.

As an aside, I found myself pulling my hair out due to a Python performance issue and a little bit of line profiling magic in iPython saved the day.

http://pynash.org/2013/03/06/timing-and-profiling.html

It turns out that calling in dict.keys() to check for key presence in a dictionary is silly as it creates a temporary list; in dict is obviously the way to go as it does what you would expect -- the hash lookup.