[Haskell-begin] Morphing Endo (ICFP Contest 2007)

[Benjamin L.Russell]

For everybody's reference, here is summary information of the exercise
(each quoted paragraph starts with a double-quote, and the entire
section ends with a single double-quote):

The 10th ICFP Programming Contest: July 20 - 23, 2007, organized by
Utrecht
http://save-endo.cs.uu.nl/

Problem ("Task") Description:
http://save-endo.cs.uu.nl/Endo.pdf

Background of Problem (from "[Chapter] 1  Background" of the
above-mentioned "Problem ('Task') Description":

"Department of Information and Computing Sciences
Utrecht University

"Tenth Interstellar Contest on Fuun Programming

"Morph Endo!

"Task Description

"Endo is an alien life form, belonging to the species of the Fuun.
Endo needs your help!  Earth’s environmental conditions can be harsh
for a life form not properly adapted. Endo had the bad luck of being
dropped on Earth by an Interstellar Garbage Collector. Both the life
form and its faithful space ship Arrow were severely hurt in the
crash, and even worse, after leaving the damaged space craft Endo was
hit by a cargo container that was also dropped by the Garbage
Collector.

"Endo is now in serious trouble. It cannot survive on planet Earth in
its present form, and Arrow is running low on power. According to
Arrow, who was the one to have contacted us, the only hope for Endo is
to change its DNA and thereby adapt it to the conditions of our
planet. To this end, Arrow has been able to come up with a form in
which Endo will survive. Unfortunately, given its current condition,
Arrow lacks the resources for coming up with proper DNA modifications
itself.

"Your task is therefore to help us find such a DNA sequence within 72
hours. Shortly thereafter, Arrow’s power will run out for good, and
since only Arrow can perform the genetic modification on Endo, this
would mean Endo’s definite end.

"Admittedly, we are partially responsible for the current state of
urgency. It took us a long time before realizing the nature of
Arrow’s emergency message and decoding the information that was
provided to us. We are sorry but nevertheless hope that you, the ICFP
programming contest audience, have the proper expertise to solve this
problem within the harsh time constraints.

"Fortunately, there’s also good news. When we weren’t yet aware of
the complete story of Endo and its struggle for life, we have been
working on decoding the specification of Fuun DNA. We now know that
Fuun DNA works significantly different from human DNA, and that the
process of DNA resequencing can be properly described as an algorithm.
The main purpose of this document is to describe this algorithm."

To solve the above task, you are given the following tools:

    *  Endo's DNA string (MD5 hash c496125ef1d22a61cb86aeb1a02c4092)
        http://save-endo.cs.uu.nl/endo.zip

    * the source picture
       http://save-endo.cs.uu.nl/source.png

    * the target picture
       http://save-endo.cs.uu.nl/target.png

The actual description of the problem is 20 pages long, which is too
long to quote here.

Correct me if I'm wrong, but because the prefix should not be too
long, and chemical process of modifying Endo with the prefix should
not consume too much energy, this appears to be an example of
constraint programming.  Since constraint programming can often be
carried out by constraint logic programming, I might suggest a logic
programming approach for this problem.

According to "Applications and libraries/Compilers and interpreters -
HaskellWiki"
(http://haskell.org/haskellwiki/Applications_and_libraries/Compilers_and_interpreters),
CHR (Constraint Handling Rules) is "A concurrent committed-choice
constraint logic programming language, implemented using GHC's
software transactional memory."  The URL listed for the associated PS
file is http://www.comp.nus.edu.sg/~sulzmann/manuscript/chr-stm.ps,
but when I click on the link, I get a "403 Forbidden" error.

However, I was able to find the following associated Web site with
Google:

Constraint Handling Rules (CHR)
http://www.cs.kuleuven.ac.be/~dtai/projects/CHR/

-- Benjamin L. Russell

On Wed, 23 Jul 2008 22:11:10 -0300, "Rafael Gustavo da Cunha Pereira
Pinto" <rafaelgcpp at gmail.com> wrote:

>        Did any of you tried to do a Haskell implementation of the ICFPC
>2007 problem?
>
>        I was thinking of using it as a learning exercise, but I am afraid
>of the stack. My approach is:
>
>1) use Data.ByteString.Lazy.Char8 to read the contents of the DNA file
>2) create a recursive function process::ByteString -> a that will call
>itself.
>
>       I have a few problems:
>
>a) the DNA is 8MB long. How can I ensure the stack will hold a recursive
>call?
>b) there is an "abnormal ending" function called finish that is called
>anywhere in the code. Is it a good approach to return Empty to end
>processing?
>c) should I go "monadic", keeping the dna on a state monad?
>
>
>    Thanks