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.

Mnemosyne

I've been doing some old Google Code Jam programs for fun. One paradigm that comes up repeatedly as a useful tool is Dynamic Programming (DP). In this one called "Welcome to Code Jam", for example, it is fairly obvious that the complexity of naive approaches will increase dramatically with large datasets. A DP algorithm, on the other hand, solves the problem handily in O(mn) time, where m is defined by number of characters in the problem text and n is defined the number of characters in "welcome to code jam".

So what does the difference in running time actually look like, between a naive and DP algorithm? In this case, one can conceive of visualizing the number of array accesses required for each logical step of the respective algorithms. As a start, I wrote a Python module to help with logging array accesses (in a slightly more generalized manner, with support for tracking basic interactions across a number of types using Abstract Base Classes):

https://github.com/tkuriyama/mnemosyne