KA Engineering

KA Engineering

We're the engineers behind Khan Academy. We're building a free, world-class education for anyone, anywhere.

Subscribe

Latest posts

Creating Query Components with Apollo

Brian Genisio on June 12

Migrating to a Mobile Monorepo for React Native

Jared Forsyth on May 29

Memcached-Backed Content Infrastructure

Ben Kraft on May 15

Profiling App Engine Memcached

Ben Kraft on May 1

App Engine Flex Language Shootout

Amos Latteier on April 17

What's New in OSS at Khan Academy

Brian Genisio on April 3

Automating App Store Screenshots

Bryan Clark on March 27

It's Okay to Break Things: Reflections on Khan Academy's Healthy Hackathon

Kimerie Green on March 6

Interning at Khan Academy: from student to intern

Shadaj Laddad on Dec 12, 2016

Prototyping with Framer

Nick Breen on Oct 3, 2016

Evolving our content infrastructure

William Chargin on Sep 19, 2016

Building a Really, Really Small Android App

Charlie Marsh on Aug 22, 2016

A Case for Time Tracking: Data Driven Time-Management

Oliver Northwood on Aug 8, 2016

Time Management at Khan Academy

Several Authors on Jul 25, 2016

Hackathons Can Be Healthy

Tom Yedwab on Jul 11, 2016

Ensuring transaction-safety in Google App Engine

Craig Silverstein on Jun 27, 2016

The User Write Lock: an Alternative to Transactions for Google App Engine

Craig Silverstein on Jun 20, 2016

Khan Academy's Engineering Principles

Ben Kamens on Jun 6, 2016

Minimizing the length of regular expressions, in practice

Craig Silverstein on May 23, 2016

Introducing SwiftTweaks

Bryan Clark on May 9, 2016

The Autonomous Dumbledore

Evy Kassirer on Apr 25, 2016

Engineering career development at Khan Academy

Ben Eater on Apr 11, 2016

Inline CSS at Khan Academy: Aphrodite

Jamie Wong on Mar 29, 2016

Starting Android at Khan Academy

Ben Komalo on Feb 29, 2016

Automating Highly Similar Translations

Kevin Barabash on Feb 15, 2016

The weekly snippet-server: open-sourced

Craig Silverstein on Feb 1, 2016

Stories from our latest intern class

2015 Interns on Dec 21, 2015

Kanbanning the LearnStorm Dev Process

Kevin Dangoor on Dec 7, 2015

Forgo JS packaging? Not so fast

Craig Silverstein on Nov 23, 2015

Switching to Slack

Benjamin Pollack on Nov 9, 2015

Receiving feedback as an intern at Khan Academy

David Wang on Oct 26, 2015

Schrödinger's deploys no more: how we update translations

Chelsea Voss on Oct 12, 2015

i18nize-templates: Internationalization After the Fact

Craig Silverstein on Sep 28, 2015

Making thumbnails fast

William Chargin on Sep 14, 2015

Copy-pasting more than just text

Sam Lau on Aug 31, 2015

No cheating allowed!!

Phillip Lemons on Aug 17, 2015

Fun with slope fields, css and react

Marcos Ojeda on Aug 5, 2015

Khan Academy: a new employee's primer

Riley Shaw on Jul 20, 2015

How wooden puzzles can destroy dev teams

John Sullivan on Jul 6, 2015

Babel in Khan Academy's i18n Toolchain

Kevin Barabash on Jun 22, 2015

tota11y - an accessibility visualization toolkit

Jordan Scales on Jun 8, 2015

Meta

How wooden puzzles can destroy dev teams

by John Sullivan on Jul 6, 2015

Last week a mysterious double-sided puzzle appeared at Khan Academy.

A picture of the mysterious puzzle

To solve the puzzle you must fit all four pieces inside the recessed area (the pieces will not entirely fill the area). We found a solution to the easy side after only a few days [1] but nobody could get close to solving the hard side. So five of us at Khan Academy began writing our own solvers.

The first question we each faced was how to best represent the positions of the pieces. Laying a triangular grid over each side was intuitive enough, but it wasn't obvious how the cells should be addressed.

Naturally we all came up with different systems [2]. I went with a system that used two perpendicular axes, with the origin at the bottom left.

An image of the triangular grid An image illustrating my coordinate system

I had a problem though. Once I manually input a piece into this coordinate system, I needed to rotate and reflect that piece into 12 different alignments. Reflection was easy, but despite my best efforts, I couldn't figure out how to rotate the pieces programmatically once they were placed into my grid.

After smashing my head against the problem for an hour and getting nowhere, I gave up [3] and manually inputted the three rotations necessary for each piece (all the other alignments could be expressed as reflections of those rotations).

Now I just had to write the logic to try every possible placement of the pieces, but I was behind.

Ben Eater had already finished his solver and it was churning away. His solver didn't do any pruning of the search space though (and took some time to check each placement), so he estimated that the solver would finish in around 2 years. I felt good about my chances of finding a solution before then.

Ben Eater's solver

To try and be a little faster I added in some logic to skip large parts of the search space where possible. This worked by laying down a piece at a time, and only trying the other ones if there were no collisions.

For example, first my program would lay down Piece A somewhere. If Piece A collided with a wall, my program would not try laying down Piece B yet, but would instead move Piece A somewhere else.

This ended up working well and soon I had a solver that could brute force the puzzle in less than a minute.

My solver

Emily Eisenberg finished her solver around the same time and we were able to confirm our results. The hard side of the puzzle was unsolvable.

Clearly there was a very evil puzzle master in our ranks.

An evil kitten

Jamie Wong readily admitted to bringing in the puzzle, but despite the staggering proof to the contrary, he was adamant that a solution existed. He said our solvers all shared a fatal flaw.

After a few hints, Emily and I did find the answer [4]. Which was good, because none of us had gotten any work done for awhile.

[1]If you want to spoil it for yourself, here is a picture of the solved easy side.
[2]Ben Eater decided to side-step the issue by drawing the shapes directly onto the screen. Cam Christensen came up with a coordinate system with two axes that formed a 60° angle and he convinced Emily Eisenberg to use the same system. Justin Helps used a vertex-based coordinate system (rather than piece-based) that made rotation and reflection easy, but collision detection super hard.
[3]Emily, however, was able to easily figure out rotation
[4]You don't really want me to give you the answer do you? That would be boring.