2016.08.12 ICFP Contest 2016 - Origami Folding

Challenge: Folding Origami

This year the ICFP will be held in Nara, Japan. The contest was organized by members of The University of Electro-Communications. I checked out their website since that sounded like a weird school name, and see that they are also hosting "The Joint Conference of the 8th International Conference on ESP in Asia & the 3rd International Symposium on Innovative Teaching and Research in ESP in Japan". Unfortunately "ESP" here is for "English for Specific Purposes" rather than the usual usage.

Unlike other years, the contest started at 00:00 UTC, which is 8:00pm Thursday, and lasted until 8:00pm Saturday. This was a nice schedule to start with, getting to roll into the contest right after work, but it did leave me jazzed up on Sunday night after it was over.

I was joined at my house by Mike, and Jason joined us remotely from Portland. We coordinated by google hangouts, irc, and github. Near the end I turned on the github-notification hook that posted to irc upon pushes, and should have done that a lot earlier.

First we read through the problem, which was very tricky to wrap our heads around as usual, despite it's somewhat minimalistic Japanese aesthetic. We drew on the whiteboards and drew on paper and folded some paper. Apparently I'm not supposed to use scissors to do origami, who knew?

The rough idea is that we are given the shadow, or "silhouette", of a folded origami flattened to 2D. We then need to reconstruct it by starting with an unfolded paper and then trying to fold it until we get the same shadow. During the lightning round we were given 101 problems of this form. After the lightning round we could submit new problems of our own invention and solve problems submitted by other contestants. We submit our solutions as we go and acquire points based on how well we solved a problem, how big in bytes was our solution, and how easy it was to solve (based on how many others solved it). They even provided a nice leaderboard.

I talked Mike into programming in Perl 6 :) . While he and Jason worked on understanding the rules of folding and solving a few problems by hand, I whipped up a problem parser using Perl 6 Grammars, which worked perfectly. I had fortunately practiced a bit before. I built a simple caching API layer to get problems from the contest server, just shelling out to curl basically.

After that I did a very basic visualization using Imager (via Inline::Perl5), which Mike then took over and worked on. Then (and we're talking Friday or Saturday) I started working on modeling folding of an origami. And then I got stuck.

g_polygon.jpg I didn't realize it until I was taking a shower on Monday morning after the contest, but I was attempting to implement too general of a solution for part of it. The rough idea is to consider an origami as a bunch of polygons. You start off with one, and then when you fold it you end up with two, one of which you reflect along the fold line.

So I set out to chop up a polygon given a line, and unfortunately didn't think through my goal clearly enough -- I tried to split ANY polygon. That includes funky looking concave polygons that when you cut with a single line might split into a bunch of pieces. What I realized after the contest was that a single cut starting from a solid piece of paper can never end up that way -- there is no way to cut it into a funky shape! So I lost a lot of time there.

The other thing that cost time was reflection. We cast about for some off the shelf libraries, but got mad at them, so I just started to implement reflection myself. I even thought I had it working, but sometime early on Sunday I realized something was fishy. I switched to an off-the-shelf implementation via Math::Geometry::Planar and presto! Worked much better. Should have used that from the beginning.

origami_fold.jpg Meanwhile Mike was both improving the visualization, especially around setting a useful viewport for shadows that had been moved far away from the axis origins. He also went through and generated images for the existing problem, which helped us pick out good test cases. Jason kept at it too, starting to hand-generate us some problems to submit once we got past the lightning round, and hand-solving some of the problems that were provided.

After visualizations were working, Mike connected the dots between problems and the origami modeling to calculate a score, making further use of the Planar library. This gave us the final ingredient we needed for automated exploration of simple folds in origami space.

Finally, late on Sunday, we got to where I wanted to be by Saturday morning. Given a problem we could start with an unfolded square and then randomly fold, keeping the improvements. Basic hill-climbing, in other words. I consider this stumbling across the finish line ... but we made it :)


Add Comment

2016.06.28 Not Quite Righte

Idea for a programming language: make experienced programmers twitch by forcing minor and common errors to be part of the language.

/* This is a comment /*
 print "Hello, world!' /* Strings must have balanced quotes /*

    if 5 + 2 = 4:
print 'Everything is awesome!"

    for(var i; i < 1; ++) print i;

class Foo {
  private method greeting [
    print "Muahahaha'

Add Comment

2016.05.12 DCRUG React.rb

I enjoyed presenting at DCRUG tonight on React.rb, which I've been playing with for the last few weeks. Good turnout too!

2016-05-12 DCRUG React.rb from awwaiid


Add Comment

2016.04.10 DCBPW, On Being Small

Welcome to the DC-Baltimore Perl Workshop!

This workshop started innocently enough. The year was 2010 -- October. We were at the Pittsburgh Perl Workshop when Brad Lhotsky said he wanted to host a similar workshop in the DC/Baltimore region. I told him no. But then he talked me and some others into it. During 2011 we worked out some details and at the 2011 Pittsburgh Perl Workshop we announced that the first DCBPW would be held April 14, 2012! We even made fliers!

Here we are six wonderful years later. We've had a few of the organizers step back over the years, mostly due to moving away, but we picked up a few others and have a core of dedicated volunteers that put this workshop together every year. We get support from The Perl Foundation and also get support from local businesses and communities. It has gone pretty well! And yet... sometimes I've felt unhappy.

You see, I started to get fantasies of grandeur.

I imagined a hundred people showing up! Two hundred! Each year this didn't happen I was a little sad. Perl dying? Community dying? What's going on that a region with probably a thousand perl developers only have 50 show up to a really awesome and cheap conference?

And then I realized -- This isn't a conference! It's a workshop.

What we have is a true "workshop". A set of people focused on learning new things, getting introduced to new ideas, and getting some hands-on time. We have organized pre-planned presentations, but we also have a lot of hallway time and variety. Then the second day is completely hands-on time. The signal-to-noise ratio is fantastic -- each attendee gets a chance to learn from their peers both formally and informally.

So yeah. It's small. That's not a bug, it's a feature :)

Add Comment

2016.03.05 Arlington RetroRuby 2016

Today I attended, a great un-conference in Arlington. I got my toehold in the local Ruby community at the Arlington meetup, and was happy to visit with lots of familiar people. I didn't meet any new people, though that was mostly because it was easy to spend time catching up.

Next time I want to jump in a bit stronger on the new-dev track, maybe walk through some hands-on exercises or do a group activity (Randori).

My favorite, besides talking to people, was the lightning talks. These have a bit more technical depth and include some code getting projected, which I love. I gave a quick this-thing-exists talk on

In the hallway track I also got to preach a bit about Module Level Polyglot :)

Add Comment


META INFORMATION: This is the technical blog and wiki of Brock Wilcox (awwaiid). Entries focus on my current projects, interests, and sometimes life events. If you'd like you can check out the list of All Entries or the RSS Feed. I also have a LiveJournal syndication feed for LJ friends.


Blog Blog RSS Feed







Follow @awwaiid





Wiki Edits Wiki RSS Feed

... more changes