Wednesday, October 24, 2007

An update: results and research

I have seen the ICFP, and it is full of funky symbols. Yes, we won a prize; two of the twelve of us headed of to Freiburg-im-Breisgau; and we came second, beaten by Team Smartass of Google. Interestingly, of the four contestants in Freiburg to collect prizes, three were South African (myself and Marco from the United Coding Team, as well as Daniel Wright of Team Smartass).

A few months ago I posted an translation of Wolfram's (2, 3) Turing Machine into Fuun DNA. What I called "an open problem of Wolfram" is now closed. Today Wolfram announced that this machine has been proven universal by Alex Smith. Since there is known to be no (2, 2) UTM, Wolfram and Smith's machine is the smallest Universal Turing Machine.

Somewhat related to Wolfram and Smith, but *very* related to programmable Fuun DNA: programmable terrestial DNA — Programmed Mutagenesis Is a Universal Model of Computation by Khodor and Gifford. Perhaps Endo isn't as alien as we thought?

Wednesday, September 19, 2007

Haskelling the SACO 1

These blog entries is to record my early adventures in Haskell, to advertise the SACO, and show off the awesomeness of Literal Haskell (which means that this entire post can be pasted into a text file and compiled) by documenting my solutions to programming contest problems.


I've finally decided to learn Haskell. For about the third time.

But this time I'm actually doing it.

Since we've just hosted another successful South African Computer Olympiad[1], I decided to code some Haskell solutions. Looking through the problems, I decided on Living Dead Parrots: I didn't code a check solution before the contest, so it wouldn't be too boring, but it was easy enough that I would spend more time learning the language than figuring out the algorithm. Most importantly, it was an interactive problem[2], meaning I would be brought face-to-face with the IO monad, a fearful prospect for the novice Haskeller.

Well, it wasn't as scary as I'd feared. By no means.

In short, the problem we're solving is this: the evaluator has an array of N booleans. You can ask it for the number of true values between two indices (inclusive, base one). Less than a hundredth of the booleans are true. There is a limit on the number of queries you can make, but we ignore it, since it is always larger than the number needed by the correct algorithm.

This solution scores 100% (within the C++ time limit, when compiled with GHC), but is probably not the best Haskell ever written. I'd appreciate any advice you can give for improvements. That's why I'm posting, after all.

First, the preliminaries:


> module Main
> where
>
> import System.IO
>
> rInt :: String -> Int
> rInt = read
>
> flush :: IO ()
> flush = hFlush stdout


Next, the function to query the evaluator. We output "Q a b", and read in an integer. The answer is obviously wrapped in the IO monad.


> query :: Int -> Int -> IO Int
> query a b = do putStrLn ("Q " ++ (show a) ++ " " ++ (show b))
> flush
> answer <- getLine
> return $ rInt answer


I'm not particularly proud of this function, which wraps a value in the IO monad. If it's the right thing to do, there's a library function for it; if it's the wrong thing to do, I shouldn't do it. If you know which it is, leave a comment.


> coerceIO :: a -> IO a
> coerceIO x = do return x


Here comes the meaty part. Search takes a range, and the number of parrots (oh, yes, those booleans represent whether a parrot in a certain cage is pining for the fjords or has kicked the bucket) in that range, and determines where those parrots are.


> search :: Int -> Int -> Int -> IO [Bool]


There are three cases. The first is that the range contains no parrots.


> search start end 0 = coerceIO $ take (end-start+1) (repeat False)


The next case is that the range contains only one element, then we have found the location of a living parrot.


> search start end 1 | start == end = coerceIO [True]


The interesting case is the remaining one, where we divide the list into two, and recurse.


> search start end numParrots = let middle = (end+start) `div` 2
> in do leftNum <- query start middle
> left <- search start middle leftNum
> right <- search (middle+1) end (numParrots-leftNum)
> return (left ++ right)


All that remains is main, which contains my most suspicious use of coerceIO, to bind purely functional variables in a monad: I haven't figured out how to use let in a do.

It first reads a line containing two integers: the size of the parrot array, and the number of questions. We ignore the latter. We then find the number of live parrots in the array, and begin the search. The output format is "A 0 0 0 0 1 0 1 0 1 ...".


> main :: IO ()
> main = do line <- getLine
> n <- coerceIO $ rInt $ head $ words line
> numParrots <- query 1 n
> parrots <- search 1 n numParrots
> putStrLn $ "A " ++ (unwords $ map (\x -> if x then "1" else "0") parrots)
> return ()


Notes on Haskell syntax, for non-Haskellers: f $ x is the same as f x, except that it binds more loosely. Its purpose is mostly to eliminate lots of irritating superfluous parentheses. (\x -> y) is an anonymous function mapping x to y

[1]We now run a parallel contest online: same problems, but open to anyone. You should check it out this time next year. We might also be running the contests from the training camps online (training camps happen about three times a year, starting in February). Unfortunately, Haskell is not one of the supported languages, but after the contests you can download the evaluator programs and test data to score solutions in any language.

[2]In the SACO, interactive problem solutions communicate through pipes with an evaluator, rather than reading an input file and writing an output file. This allows problems where access to the full dataset is unnecessary, and is either not allowed or too big to be read completely within the time limit.

Wednesday, August 29, 2007

Mr Turing, meet Endo

From the moment we saw what Endo's DNA was doing as we ran it, every ICFP contestant (at least, those who got that far) knew in their hearts that Fuun DNA is Turing complete. But I am a mathematician! And mathematicians need proof.

Mr Turing, I'd like you to meet Endo:

IIPIFFPCPPPIICIIPIFFPCPPFIICIIPIFFPCPPPIICIICIFPIC
PIFPCPIFPICPIICFIFFFFIFCIPPFIFCCCIFIFCPFIFCFFIFIFC
PCIFIFCPFIFFIFIFFCIIPIFFPCPFCIICICICPCPFFPCPCPFICP
CPFPPCPPCIICIFPPICPPCPFFFFPCPFICPCPFPPCPPCFICPCPFI
CIICIIPIFFPCPFCIICICICPCPFFPCPCPFICPCPFPIIPIFFPCPF
ICIICIIPIFFPCPPCIICIICIFPPICPPCPFFIFPCPPCPFPIFPICP
FICPCPFICIICIIPIFFPCPFCIICICICPCPFFFICPCPFICPCPFPI
IPIFFPCPPCIICPCPPFIICIFPPICPPCPFFFCPCPFICPCPFPPCPC
PFICIFPCPPCPPFIICIIPIFFPCPFCIICICICPCPFFFICPCPFICP
CPFPIIPIFFPCPPCIICIIPIFFPCPFICIICIICIFPPICPPCPFFIF
PICPPCPFPPCPCPFICIFPCPIICIIPIFFPCPFCIICICICPCPFFFP
PCPFICPCPFPIIPIFFPCPPCIICPCPPFIICIFPPICICPCPFFFCPC
PFICPCPFPFCPCPFICIFPCPPCPPFIICIIPIFFPCPFCIICICICPC
PFFFPPCPFICPCPFPIIPIFFPCPPCIICIIPIFFPCPFICIICIICIF
PPICICPCPFFIFPICPPCPFPFCPCPFICIFPCPIICIIPIFFPCPFCI
ICICICPCPFFFFPCPFICPCPFPIIPIFFPCPPCIICPCPPFIICIFPP
ICICPCPFFFCPCPFICPCPFPFCPCPFICIFPCPPCPPFIICIIPIFFP
CPFCIICICICPCPFFFFPCPFICPCPFPIIPIFFPCPPCIICIIPIFFP
CPFICIICIICIFPPICICPCPFFIFPICPPCPFPFCPCPFICIFPCPII
CIIPIFFPCPFCIICICICPCPFFFCPCPFICPCPFPPCPPCIICIFPPI
CICPCPFFFFPCPFICPCPFPPCPPCFFPCPFICIICIIPIFFPCPFCII
CICICPCPFFFCPCPFICPCPFPIIPIFFPCPFICIICIIPIFFPCPPCI
ICIICIFPPICICPCPFFIFPCPPCPFPIFPICPFFPCPFICIICIIPIF
FPCPFCIICICPPCPFFPCPCPFICPCPFPPCPPCIICIFPPICPPCPFF
FFPCPFICPCPFPPCPPCFPPCPFICIICIIPIFFPCPFCIICICPPCPF
FPCPCPFICPCPFPIIPIFFPCPFICIICIIPIFFPCPPCIICIICIFPP
ICPPCPFFIFPCPPCPFPIFPICPFPPCPFICIICIIPIFFPCPFCIICI
CPPCPFFFICPCPFICPCPFPIIPIFFPCPPCIICPCPPFIICIFPPICP
PCPFFFCPCPFICPCPFPPCPCPFICIFPCPPCPPFIICIIPIFFPCPFC
IICICPPCPFFFICPCPFICPCPFPIIPIFFPCPPCIICIIPIFFPCPFI
CIICIICIFPPICPPCPFFIFPICPPCPFPPCPCPFICIFPCPIICIIPI
FFPCPFCIICICPPCPFFFPPCPFICPCPFPIIPIFFPCPPCIICPCPPF
IICIFPPICICPCPFFFCPCPFICPCPFPPCPCPFICIFPCPPCPPFIIC
IIPIFFPCPFCIICICPPCPFFFPPCPFICPCPFPIIPIFFPCPPCIICI
IPIFFPCPFICIICIICIFPPICICPCPFFIFPICPPCPFPPCPCPFICI
FPCPIICIIPIFFPCPFCIICICPPCPFFFFPCPFICPCPFPIIPIFFPC
PPCIICPCPPFIICIFPPICICPCPFFFCPCPFICPCPFPFCPCPFICIF
PCPPCPPFIICIIPIFFPCPFCIICICPPCPFFFFPCPFICPCPFPIIPI
FFPCPPCIICIIPIFFPCPFICIICIICIFPPICICPCPFFIFPICPPCP
FPFCPCPFICIFPCPIICIIPIFFPCPFCIICICPPCPFFFCPCPFICPC
PFPPCPPCIICIFPPICICPCPFFFFPCPFICPCPFPPCPPCFICPCPFI
CIICIIPIFFPCPFCIICICPPCPFFFCPCPFICPCPFPIIPIFFPCPFI
CIICIIPIFFPCPPCIICIICIFPPICICPCPFFIFPCPPCPFPIFPICP
FICPCPFICIICIIPIFFPCPPPIICIIPIFFPCPPFIICIIPIFFPCPP
PIICIICIFPICPIFPCPIFPICPIICFIFFF


I'm sure my (three, I think) regular readers have long ago worked out what I had up my sleeve, but this is it. Credit is due more to Cook and Wolfram than myself, and of course Endo and Turing, most of all.

I realise that Jeuring, et al. have probably had a proof of this fact for several months, but I believe I am the first to make it public.

To see this in action, configure your "build" program to output the current DNA at each iteration. The actual Turing machine data looks like this (it is surrounded front and back by the mechanics of the maching):

"PPPCI $State PPPCC $Symbol PPPCP PPPCF $LeftStack PPPFI $RightStack PPPFC"

$State is either "PP" (up) or "PF" (down). $Symbol is the symbol currently "under the head"; the symbols are "CI", "CC", "CF", "CP" and "FI", from white to black (note that I read NKS online, so I don't know what the colours are in the original). $LeftStack and $RightStack are lists of symbols delimited by "PPPCP", both starting with the tape cell nearest the head.

My previous Turing machines had a similar structure, but used "markers" other than "PPPxx".

EDIT: I have changed "FIFxx" for the markers, since strings of P's behave particularly badly in the face of quoting.

I'll leave the rest to you to work out.

Now... can we write a compiler before the organisers release theirs? I'm in the middle of a whole bunch of projects and tests, as well as practising for ACM ICPC, but I'd love to contribute if somebody else is prepared to lead for a bit.

Sunday, August 26, 2007

On an open problem of Wolfram

I have something to admit. Something rather shameful. I never learnt Fuun during the contest. After all, I was a late arrival to a team with a man we call Bruce Almighty, after whom the Bruce-First Search is named. Although I had a vague understanding of the low-level details, my contributions were mostly at a higher level.

So I'm only really learning the details now, as I don my tin-foil hat and prepare for a Fuun-filled future. When I saw Jochen's ingenious 55-character junk generator, I had only an inkling of how it worked until I whipped out my spec booklet and a pencil. Jochen's string shows just how incredibly rich Fuun DNA is. And also that Jochen is a brilliant DNA hacker.

I will now, finally, progress to my point. Last week, I left you with an SHA-1 "essence" of a result. In truth, it is more of a question than a result. It is suspected by some that the following DNA sequence has a truly awe-inspiring property: that the genetic program of any being can be emulated by this sequence of Fuun genes. Is this the case? A cash prize is offered for a proof of the affirmative.

IIPIFFCFPPPIICIIPIFFCFPPFIICIIPIFFCFPPPIICIICIFPIC
PIFPCPIFPICPIICICFFFICFCIPFICFCCCCICFCPICFCFICFFII
CFFCIIPIFFCFPFCIICICPCFPFFFPCFPFICCFPFPCFPPCIICIFP
PICPCFPFFFFCFPFICCFPFPCFPPCFCCFPFICIICIIPIFFCFPFCI
ICICPCFPFFFPCFPFICCFPFPIIPIFFCFPFICIICIIPIFFCFPPCI
ICIICIFPPICPCFPFFIFPCPCFPFPIFPICPFCCFPFICIICIIPIFF
CFPFCIICICPCFPFFFCCFPFICCFPFPCFPPCIICIFPPICPCFPFFF
FCFPFICCFPFPCFPPCFPCFPFICIICIIPIFFCFPFCIICICPCFPFF
FCCFPFICCFPFPIIPIFFCFPFICIICIIPIFFCFPPCIICIICIFPPI
CPCFPFFIFPCPCFPFPIFPICPFPCFPFICIICIIPIFFCFPFCIICIC
PCFPFFFFCFPFICCFPFPIIPIFFCFPPCIICCFPPFIICIFPPICICC
FPFFFFCFPFICCFPFPFCCFPFICIFPCPCFPPFIICIIPIFFCFPFCI
ICICPCFPFFFFCFPFICCFPFPIIPIFFCFPPCIICIIPIFFCFPFICI
ICIICIFPPICICCFPFFIFPICPCFPFPFCCFPFICIFPCPIICIIPIF
FCFPFCIICICICCFPFFFPCFPFICCFPFPIIPIFFCFPPCIICCFPPF
IICIFPPICPCFPFFFFCFPFICCFPFPFFCFPFICIFPCPCFPPFIICI
IPIFFCFPFCIICICICCFPFFFPCFPFICCFPFPIIPIFFCFPPCIICI
IPIFFCFPFICIICIICIFPPICPCFPFFIFPICPCFPFPFFCFPFICIF
PCPIICIIPIFFCFPFCIICICICCFPFFFCCFPFICCFPFPIIPIFFCF
PPCIICCFPPFIICIFPPICICCFPFFFFCFPFICCFPFPFPCFPFICIF
PCPCFPPFIICIIPIFFCFPFCIICICICCFPFFFCCFPFICCFPFPIIP
IFFCFPPCIICIIPIFFCFPFICIICIICIFPPICICCFPFFIFPICPCF
PFPFPCFPFICIFPCPIICIIPIFFCFPFCIICICICCFPFFFFCFPFIC
CFPFPCFPPCIICIFPPICPCFPFFFFCFPFICCFPFPCFPPCFPCFPFI
CIICIIPIFFCFPFCIICICICCFPFFFFCFPFICCFPFPIIPIFFCFPF
ICIICIIPIFFCFPPCIICIICIFPPICPCFPFFIFPCPCFPFPIFPICP
FPCFPFICIICIIPIFFCFPPPIICIIPIFFCFPPFIICIIPIFFCFPPP
IICIICIFPICPIFPCPIFPICPIICICFFF

Thursday, August 23, 2007

Investigating Endo: Junk DNA

My friend Marco has blogged about my team's experience in the ICFP, but since the contest, I've been investigating Endo's DNA. Johann Jeuring is slowly revealing some interesting facts, but as we know, he was kidnapped by Fuun invaders, and so we can't really trust what he tells us.

I've discovered some truly remarkable properties of Fuun DNA, the proof of which this blog is wide enough to contain. Unfortunately Earth's internet has already been infiltrated by Fuun agents, as attested by their subversion of the ICFP itself.

I will, however, reveal a single DNA sequence, which may prove useful in the defense against Fuun invaders, should they further threaten our planet. When "executed" it generates large amounts of "junk DNA". JB and HM indicate that in generates on the order of 10865 acids in about 101730 iterations before destroying itself, but of course our gene simulators would take many years to confirm this.

Anyone who discovers more about this sequence or others related to it should post them on this blog, so that we may broaden our knowledge of our universe's lifeforms, and begin to coordinate anti-Fuun defense, should it be necessary.

IIPIFFCFPPPIICIIPIFFCFPPFIICIIPIFFCFPPPIICIICIFPIC
PIFPCPIFPICPIICICFFFICFCIPIICFCCCCICFCPICFCFICFFII
CFFCIIPIFFCFPFCIICICCCFPFFFFCFPFICCFPFPIIPIFFCFPPC
IICCFPPFIICIFPPICFCFPFFFFCFPFICCFPFPFCCFPFICIFPCPC
FPPFIICIIPIFFCFPFCIICICCCFPFFFFCFPFICCFPFPIIPIFFCF
PPCIICIIPIFFCFPFICIICIICIFPPICFCFPFFIFPICPCFPFPFCC
FPFICIFPCPIICIIPIFFCFPFCIICICCCFPFFFCCFPFICCFPFPCF
PPCIICIFPPPFCFPFFFFCFPFICCFPFPCFPPCFFCFPFICIICIIPI
FFCFPFCIICICCCFPFFFCCFPFICCFPFPIIPIFFCFPFICIICIIPI
FFCFPPCIICIICIFPPPFCFPFFIFPCPCFPFPIFPICPFFCFPFICII
CIIPIFFCFPFCIICICFCFPFFFFCFPFICCFPFPIIPIFFCFPPCIIC
CFPPFIICIFPPICPCFPFFFFCFPFICCFPFPFFCFPFICIFPCPCFPP
FIICIIPIFFCFPFCIICICFCFPFFFFCFPFICCFPFPIIPIFFCFPPC
IICIIPIFFCFPFICIICIICIFPPICPCFPFFIFPICPCFPFPFFCFPF
ICIFPCPIICIIPIFFCFPFCIICICFCFPFFFCCFPFICCFPFPIIPIF
FCFPPCIICCFPPFIICIFPPICICCFPFFFFCFPFICCFPFPFFCFPFI
CIFPCPCFPPFIICIIPIFFCFPFCIICICFCFPFFFCCFPFICCFPFPI
IPIFFCFPPCIICIIPIFFCFPFICIICIICIFPPICICCFPFFIFPICP
CFPFPFFCFPFICIFPCPIICIIPIFFCFPFCIICICPCFPFFFFCFPFI
CCFPFPCFPPCIICIFPPICICCFPFFFFCFPFICCFPFPCFPPCFCCFP
FICIICIIPIFFCFPFCIICICPCFPFFFFCFPFICCFPFPIIPIFFCFP
FICIICIIPIFFCFPPCIICIICIFPPICICCFPFFIFPCPCFPFPIFPI
CPFCCFPFICIICIIPIFFCFPFCIICICPCFPFFFCCFPFICCFPFPII
PIFFCFPPCIICCFPPFIICIFPPPCCFPFFFFCFPFICCFPFPFCCFPF
ICIFPCPCFPPFIICIIPIFFCFPFCIICICPCFPFFFCCFPFICCFPFP
IIPIFFCFPPCIICIIPIFFCFPFICIICIICIFPPPCCFPFFIFPICPC
FPFPFCCFPFICIFPCPIICIIPIFFCFPFCIICICICCFPFFFFCFPFI
CCFPFPCFPPCIICIFPPPCCFPFFFFCFPFICCFPFPCFPPCFFCFPFI
CIICIIPIFFCFPFCIICICICCFPFFFFCFPFICCFPFPIIPIFFCFPF
ICIICIIPIFFCFPPCIICIICIFPPPCCFPFFIFPCPCFPFPIFPICPF
FCFPFICIICIIPIFFCFPFCIICICICCFPFFFCCFPFICCFPFPCFPP
CIICIFPPICICCFPFFFFCFPFICCFPFPCFPPCFFCFPFICIICIIPI
FFCFPFCIICICICCFPFFFCCFPFICCFPFPIIPIFFCFPFICIICIIP
IFFCFPPCIICIICIFPPICICCFPFFIFPCPCFPFPIFPICPFFCFPFI
CIICIIPIFFCFPFCIICPCCFPFFFFCFPFICCFPFPIIPIFFCFPPCI
ICCFPPFIICIFPPICCCFPFFFFCFPFICCFPFPFFCFPFICIFPCPCF
PPFIICIIPIFFCFPFCIICPCCFPFFFFCFPFICCFPFPIIPIFFCFPP
CIICIIPIFFCFPFICIICIICIFPPICCCFPFFIFPICPCFPFPFFCFP
FICIFPCPIICIIPIFFCFPFCIICPCCFPFFFCCFPFICCFPFPIIPIF
FCFPPCIICCFPPFIICIFPPICPCFPFFFFCFPFICCFPFPFCCFPFIC
IFPCPCFPPFIICIIPIFFCFPFCIICPCCFPFFFCCFPFICCFPFPIIP
IFFCFPPCIICIIPIFFCFPFICIICIICIFPPICPCFPFFIFPICPCFP
FPFCCFPFICIFPCPIICIIPIFFCFPFCIICPFCFPFFFFCFPFICCFP
FPCFPPCIICIFPPICCCFPFFFFCFPFICCFPFPCFPPCFCCFPFICII
CIIPIFFCFPFCIICPFCFPFFFFCFPFICCFPFPIIPIFFCFPFICIIC
IIPIFFCFPPCIICIICIFPPICCCFPFFIFPCPCFPFPIFPICPFCCFP
FICIICIFFCFPFCPFCFPFFFCCFPFICIFFCFPPPIICIICIIPIFFC
FPPPIICIIPIFFCFPPFIICIIPIFFCFPPPIICIICIFPICPIFPCPI
FPICPIICICFFF


As a token, I leave you with this essence of my deepest result yet: 54c763a5f6b9beba26eeae2e98ba786f45b0fef8.

EDIT: Thanks to Jochen for the correction. In case you were worrying, he is not a Fuun agent: I have carefully checked his patch.