Introduction

The annual ICFP contest ran between August 5 and August 8, 2016 and, even though I couldn’t fully commit to it due to an otherwise busy weekend, I resolved to tackling it in my spare time, using Haskell exclusively, in the course of the subsequent days. In this page I will document my solution process and tools, since the resulting application features quite a few techniques that are seldom explained together (parsing, plotting, geometric processing and combinatorial optimization).

Part 1 of this post will be concerned with representing the problem semantics, parsing with attoparsec and plotting with diagrams.

The task description can be found on the official blog, along with a few updates and the problem list (for which a free, anonymous registration is required).

The Challenge

In short: fold an origami.

The origami is defined as a list of coordinates defining the “silhouette” (contour of the folded origami) and segments joining them (folds or sheet edges, the “skeleton” of the origami). The problem is: given an origami, and starting from a square sheet, find the list of folding moves (simple, or “valley-type” folds only are considered) to approximate the given origami silhouette.

Parsing the problem specifications

The problems come as plain text files, of which the following is a typical example (Problem 26). I’ve added some comments to clarify what the sections mean :

2               -- # of silhouettes
6               -- # of points of first silhouette
1/4,0           -- list of point coordinates of first silhouette
3/8,1/8         -- ..      
3/8,1/4 
1/4,3/8
1/8,3/8
0,1/4           -- .. until here
4               -- # of points of second silhouette
1/8,1/8         -- list of point coordinates of second silhouette 
1/8,1/4         -- ..
1/4,1/4
1/4,1/8
10              -- # of segments
1/4,0 3/8,1/8   -- list of segment endpoint coordinates
1/8,1/8 1/8,3/8 -- ..
1/4,0 1/4,3/8
3/8,1/8 3/8,1/4
0,1/4 1/8,3/8
1/8,1/8 3/8,1/8
1/4,0 0,1/4
0,1/4 3/8,1/4
3/8,1/4 1/4,3/8
1/8,3/8 1/4,3/8

All coordinates are specified as integers or ratios of integers, and should be manipulated as such (which is sensible because we can operate on them without loss of numerical precision, as opposed to manipulating floats).

We immediately notice the need for some sort of conditional parsing: the first line specifies an integer n, which determines how many “Silhouette” stanzas will follow. The last section is the “Skeleton”, i.e. the complete set of segments that form the “x-ray” picture of the folded origami.

If you want to reproduce, create a new project e.g. with stack new and put the following in the Lib module.

First, the requisite boilerplate:

import Data.Attoparsec.Internal.Types (Parser)
import qualified Data.Attoparsec.ByteString as PB
import Data.Attoparsec.ByteString.Char8 (decimal, signed, scientific, digit, number, rational, char, char8, endOfLine, endOfInput, isDigit, isDigit_w8, isEndOfLine, isHorizontalSpace)
import qualified Data.ByteString as B (ByteString, readFile)

import System.FilePath

Now, let’s encode the problem specification semantics in some types :

data Fract = Fract !Int !Int
instance Eq Fract where
  f1 == f2 = ratSimp f1 == ratSimp f2

ratSimp :: Fractional a => Fract -> a
ratSimp (Fract n d) = fromIntegral n / fromIntegral d

Equality of rationals is established by reducing the fraction; the result is in general not an integer. This method is faster than relying on gcd and simplifying, it seems, but we’ll use it only here and for producing plots (not in the solver logic).

data Point = P Fract Fract deriving Eq

data Segment = S Point Point deriving (Eq, Show)

data Silhouette =
  Silhouette { numVerticesPoly :: Int,
               points :: [Point]  } deriving Eq

data Skeleton =
  Skeleton { numSegments :: Int,
             segments :: [Segment]} deriving Eq

data Problem = Problem [Silhouette] Skeleton deriving Eq

For parsing the specification, we rely on the amazing attoparsec package. I import its ByteString module in qualified form as PB to make it easier to follow.

We switch alternatively between applicative and do-based notation. Anyway, since GHC 8, Monads are indeed Applicatives, so whatever logic one writes in the latter form automatically applies to the former.

Small reminder about the operators: (<$>) :: Functor f => (a -> b) -> f a -> f b is a synonym for fmap, (<*>) :: Applicative f => f (a -> b) -> f a -> f b (read “apply”) is the function defining the Applicative class (“evaluate a function with a value if both are wrapped in a context”), whereas (*>) :: Applicative f => f a -> f b -> f b and (<*) :: Applicative f => f a -> f b -> f a can be read as “sequence”, i.e. they perform both actions that appear as their arguments and retain the second and first results, respectively.

The following declarations establish the rules for parsing signed fractional values (optionally integers, i.e. fractionals with 1 at the denominator, using the option modifier), then Points and Segments based on those.

parseFractional :: Parser B.ByteString Fract
parseFractional =
  Fract <$> signed decimal <*> PB.option 1 (char8 '/' *> decimal)

parsePoint :: Parser B.ByteString Point
parsePoint = P <$> (parseFractional <* comma) <*> parseFractional

parseSegment :: Parser B.ByteString Segment
parseSegment = S <$> (parsePoint <* space) <*> parsePoint

comma = char8 ','
space = char8 ' '

Next, we’ll need some parsing logic for the various sections of the specification file:

parseNumPolys :: Parser B.ByteString Int
parseNumPolys = decimal <* endOfLine

parseSilhouette :: Parser B.ByteString Silhouette
parseSilhouette = do
  nvp <- decimal <* endOfLine
  pp <- PB.many1 (parsePoint <* endOfLine)
  return $ Silhouette nvp pp

parseSkeleton :: Parser B.ByteString Skeleton
parseSkeleton = do
  ns <- decimal <* endOfLine
  segs <- PB.many1 (parseSegment <* endOfLine)
  return $ Skeleton ns segs

Notice how easily we can compose elementary parsers into more complex ones. The parseProblem0 function reflects the problem specification structure 1:1. Neat!

parseProblem0 :: Int -> Parser B.ByteString Problem
parseProblem0 n = do
  _ <- decimal *> endOfLine
  sils <- PB.count n parseSilhouette
  skels <- parseSkeleton <* endOfInput
  return $ Problem sils skels

or, equivalently,

parseProblem0' :: Int -> Parser B.ByteString Problem
parseProblem0' n =
  Problem <$>
     (decimal *> endOfLine *> PB.count n parseSilhouette) <*>
     (parseSkeleton <* endOfInput)

Next: the implementation of conditional parsing: there is probably a more concise way to say this, but the idea is simple: we must first parse and acquire an integer appearing at the beginning of the file, and with that decide how many times to apply the Silhouette parser (using the count :: Monad m => Int -> m a -> m [a] modifier).

If parsing succeeds (i.e. our parsers match the structure of the file), the resulting Problem datastructure will be returned (wrapped in a Right constructor).

N.B. the Monad instance of Either returns the first Left a value it encounters, in this case a String with the error message.

loadProblem :: Int -> IO (Either String Problem)
loadProblem n = do
  c <- B.readFile fname
  let r = PB.parseOnly parseNumPolys c
  case r of
    Left e -> error e
    Right numpolys -> 
      return $ PB.parseOnly (parseProblem0 numpolys) c
  where
     dir = "problems/"
     fname = dir </> show n

Drawing origami

Next, we’ll see how to plot our data; for this I’ll use the equally amazing diagrams package. It is pretty extensive however it also comes with an excellent set of tutorials.

The following goes in a Diag module that imports our Lib.

import Diagrams.Prelude hiding (P, (<>))
import Diagrams.Backend.SVG.CmdLine
import Diagrams.Backend.CmdLine

import Data.Monoid ((<>))
import System.Environment (getArgs)

import Lib hiding (p2)

From parsing to plotting

First, some helper functions to convert between our Problem record fields and the diagrams types:

pointToP2 :: Lib.Point -> P2 Double
pointToP2 (Lib.P x y) = p2 (ratSimp x, ratSimp y)

pointsToTrail :: [Lib.Point] -> Trail V2 Double
pointsToTrail =  closeTrail . trailFromVertices . map pointToP2

segmentToPath :: Lib.Segment -> Path V2 Double
segmentToPath (S x y)  = pointToP2 x ~~ pointToP2 y :: Path V2 Double

Both the Trail and Path types are instances of the internal ToPath class (which later will let us convert them to a Diagram in order to be drawn). Most importantly, a Path is not necessarily continuous, whereas a Trail is assumed to connect the dots.

We use the closeTrail function to render all the sides of the Silhouette polygon since in the dataset the last point in an array doesn’t usually coincide with the starting one.

silhouetteToDiagram :: Foldable t => t [Lib.Point] -> Diagram B
silhouetteToDiagram = strokeTrail . foldMap pointsToTrail 

skeletonToDiagram :: Foldable t => t Lib.Segment -> Diagram B
skeletonToDiagram = stroke . foldMap segmentToPath

The two functions above subsume summarize all the conversion work between Lib and diagrams.

Diagrams are Monoids

Diagrams are instances of Monoid, so mappending them will yield another Diagram. NB: mconcat :: Monoid a => [a] -> a is equivalent to mappending a list of monoidal values together into a single one.

The next function demonstrates this and also applies some graphical styles to the diagrams (line and filling colors):

diagTot :: Problem -> Diagram B
diagTot p =
  centerXY $ mconcat [
      (dashingG [0.01,0.005] 0 . lc red) skeletonToDiagram $ problemSegments p
    , (lc black # fc yellow) silhouetteToDiagram $ problemPoints p
    ]

The only IO required by this program : the Diagrams mainWith function is very versatile but here we simply use it to wrap the file loading IO, to supply the problem number from command line when the program is run.

There are many possibilities for extending the command line input with structured options processing via optparse-applicative, but we don’t need all of that complexity here.

main :: IO ()
main = mainWith loadProblemN

loadProblemN :: Int -> IO (Diagram B)
loadProblemN n = do
  r <- loadProblem n
  case r of Left e -> error e
            Right p -> return $ diagTot p

And that’s it really!

At this point we can stack build and, if the Cabal file defines an executable called viz that points to the Diag module it its main-is, calling stack exec viz -- -o viz.svg -w 600 101 will render an SVG file of the given width (600 pixels) using the problem specification # 101 (the figure at the top of the page).

This post is already long enough so I’ll close it here, though there are still a couple of kinks to iron in the data preprocessing.

Stay tuned for Part 2, with the solver logic !