Folding a paper crane - a solution to the ICFP 2016 programming contest - part 1
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 :
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:
Now, let’s encode the problem specification semantics in some types :
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).
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, Monad
s are indeed Applicative
s, 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 Point
s and Segment
s based on those.
Next, we’ll need some parsing logic for the various sections of the specification file:
Notice how easily we can compose elementary parsers into more complex ones. The parseProblem0
function reflects the problem specification structure 1:1. Neat!
or, equivalently,
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.
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
.
From parsing to plotting
First, some helper functions to convert between our Problem
record fields and the diagrams
types:
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.
The two functions above subsume summarize all the conversion work between Lib
and diagrams
.
Diagrams are Monoid
s
Diagrams are instances of Monoid
, so mappend
ing them will yield another Diagram. NB: mconcat :: Monoid a => [a] -> a
is equivalent to mappend
ing 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):
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.
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 !