Saturday, October 07, 2006

un-figlet

Eating a midnight dinner at Zuni with Dan and Charles.

Me: Today is Mid-Autumn Festival, the day of the year when the moon is at its roundest. You're supposed to spend it with family. It's the chinese version of Thanksgiving.



Dan: Yes, I was impressed by the moon tonight. It was very round.

Me: Are you sure it wasn't a shark?

...

Me: [to Charles] Dan was two years ahead of me at Caltech, and I participated in his Ditch Day stack.

Charles: What's that?

Dan: It's an annual tradition where seniors construct elaborate puzzle hunts. My stack's premise was that an AI was loose in the system. It communicated with you via light bulbs scattered around campus, that flashed in morse code. There was always a switch next to the light bulb, that you tap with morse code. I put a light bulb in the steam tunnel. I even had a fridge where you open the door, and the fridge light flashed morse code.

Me: In preparation for Ditch Day, seniors hid their preparation materials behind sheets that they marked "Seniors Only". Months before the event, Dan strung a 50-foot cable across the entire Dabney House courtyard. (Imagine a black cable strung across this courtyard):



with an Atari joystick hanging from it, eight feet in the air.



Charles: What was the joystick for?

Me: Nothing. It wasn't used in his Ditch Day stack at all. He put it there for months, just to build hype.

...

Dan: On the day before Ditch Day, we stayed up all night coding. Seniors had to get off campus by eight a.m., or they'd get duct-taped to a tree. [mimes rapidly encircling a tree with tape] At 7:30am, the code was still hitting asserts everywhere.

Me: [breathless]

Dan: So we said, "Crap. Re-compile without asserts."

Me: [laughing] That's your solution?

Dan: We rebuilt the thing without asserts. We ran it, and the intro segfaulted. So we skipped the intro, and went right to the first puzzle. The program worked perfectly the rest of the day.

Me: Awesome.




The evening reminded me of my favorite story involving Dan. In college, we liked to use the unix utility "figlet" to make ascii art. For example:

> figlet "hello world"
_ _ _ _ _
| |__ ___| | | ___ __ _____ _ __| | __| |
| '_ \ / _ \ | |/ _ \ \ \ /\ / / _ \| '__| |/ _` |
| | | | __/ | | (_) | \ V V / (_) | | | | (_| |
|_| |_|\___|_|_|\___/ \_/\_/ \___/|_| |_|\__,_|


In our college online chat, we discussed how one would write "un-figlet". The idea is that it would take ascii art input and extract the original words. The challenge is that letters overlap (witness the "e" and "l" in the example above), and it would have to handle the multiple fonts that figlet supports.

Twenty minutes into the conversation, Dan announced that he had written un-figlet while we were talking. We were shocked at the speed, but figured, hey, it's Dan.

"The algorithm is really slow though," he said. "You might have to wait up to a couple minutes."

We ran queries against it. Indeed it took at least a minute, sometimes two or three, but it always generated the correct answer. We were amazed. We lauded Dan for his impressive performance.

The next morning, our friend ran it again, and this time it hung for hours.

When Dan came online, we told him that his program broke. He confessed how his "un-figlet" worked. It emailed the input ascii art to him. He looked at it, and wrote the answer to a file which un-figlet polled. When un-figlet detected content in the file, it would print it out to the user's screen.

8 comments:

Anton Ng said...

Did you eat moon cake Niniane?

Happy moon cake festival btw.

I laughed so loud when I read the end of this post in the library. Dan is a clever chap isnt he.

Dan Egnor said...

For the record, my collaborators (Mike and Rudi) made the ditch-day stack software. I was the hardware guy. If I'd made it, I'm sure it wouldn't have worked at all.

Anonymous said...

Un-figlet
I have never heard of the unix utility “figlet”; however, I found the problem interesting and after 30 mins of pondering, this is the solution I came up with.

Prerequisites
Access to a computer
Able to reverse engineer the “figlet” algorithm (not difficult).

Assumptions (since I have never used the figlet utility)
No figlet character may completely overlap its adjacent character in a sequence.
Each vertical ascii line may intersect (inclusive) at most 2 figlet characters.

Algorithm
--Let I be the input character stream and L be a vertical ascii line within I
c = the current vertical ascii line number;
X = the current figlet character;
Y = the figlet character to the right of the X which do not overlap X;

Start at the first L from the left (c= 1) of the input stream and parse it through the reversed figlet generator (for all possible figlet). Once a possible match is found [the first figlet character that is a subset of ascii characters between L1 and c inclusive, in another word, each vertical ascii line within the figlet must be a subset of each corresponding L], the algorithm then searches for Y within I-X. Should the algorithm not find a match after all possible figlet, it would return to the previous step and look for another possible character. As soon as a space is found, the text obtained thus far can be saved. Repeat this process until the entire input stream has been depleted. This technique should handle all figlet fonts which satisfy the assumptions.

*note: when searching for characters of multiple font combinations, the performance could be very slow

Wa

Anonymous said...

Continued... (forgot to paste)
Hello World Example.

The algorithm would execute as follows:

Find H

Find E because it knows what HE-H looks like

Find L because it knows what EL-L looks like

Find L because it knows what LL-L ..

Find O because …

Find Space because …

……

Anonymous said...

re: un-figlet

My first thought in just about any situation is usually "has this been done before?" In this case, I don't know if it was solved when Ninane posed the question to Dan, but by 2004...

Anonymous said...

I would have thought that Dan's solution would be to brute-force combinations of inputs to figlet until figlet produced an output what was the same as the input to un-figlet. Brute-force an one-way hash, as it were.

Anonymous said...

Very funny!!

RC, The Netherlands

Anonymous said...

You are the one that wrote the morse code parser in Gmail ads aren't you?