Saturday, November 27, 2010

How the Rose Bowl picks TCU (but Stanford plays in Pasadena)

As I write this, Stanford just beat Oregon State 38-0. Nevada beat Boise State, and Arkansas beat LSU. Everyone expects that tomorrow afternoon, Stanford will be 4th in the BCS rankings. What does this mean for what Bowl Game Stanford will show up for?

Summary: There's a scenario, that I think is somewhat likely, where: the Rose Bowl will pick TCU, thereby satisfying its contractual obligations, but on January 1st, Stanford will be playing in Pasadena. I'm sorry if this post is long, but I want to be precise so you'll believe this conclusion.

Everyone's been saying a lot. Don't trust them. Go read the rules for yourself. BCS Selection Procedures. Yeah, they're written in lawyer-ese (but it's actually bad lawyer-ese, as we'll get to). But you need to read it. Not all right now. But I'll be referring to it over the course of this argument.

People have been focusing on a few clauses. Let's recap the situation, but with talk about them:
6. If any of the 10 slots remain open after application of provisions 1 through 5, and if no team qualifies under paragraph No. 5 and an at-large team from a conference with an annual automatic berth for its champion is ranked No. 4 in the final BCS Standings, that team will become an automatic qualifier provided that no at-large team from the same conference qualifies for the national championship game.
This is what people mean when they say "Top 4 teams are guaranteed a BCS game." For example, on ESPN's (excellent) PAC-10 blog, Ted Miller says "All the Cardinal need is to push into the top 4 of the final BCS standings. That would guarantee it an automatic berth, per BCS rules." He's referring to this Paragraph 6.

So, if Paragraph 6 is all that mattered, the Rose Bowl would pick Stanford and all would be Right With The World. But then there's this:

For the games of January 2011 through 2014, the first year the Rose Bowl loses a team to the NCG and a team from the non-AQ group is an automatic qualifier, that non-AQ team will play in the Rose Bowl.
[For this paragraph, AQ group means a team in a BCS conference or Notre Dame. Yes, Notre Dame is explicitly special. Thus, non-AQ group means a team from a second-tier conference. TCU (and Boise State) fall into this group.]

Well, if Oregon wins out, the Rose Bowl will lose the Ducks to the NCG. TCU will be #3 and an Automatic Qualifier. Therefore, by this paragraph, TCU will go the Rose Bowl.

And this is where everyone's analysis has stopped.

But scroll down a little more. To the section "Team Selections Procedure", Paragraph 5. It says:

After completion of the selection process as described in Paragraph Nos. 1-4, the conferences and Notre Dame may, but are not required to, adjust the pairings [...]
At this point in the process, we are expecting that the process will have assigned:
  • Rose Bowl: TCU vs. Big-10 Champion
  • Some Other Bowl: Stanford vs. Other team
So, the Rose Bowl will have selected its non-AQ team, as required.

But, would TCU rather play in the Rose Bowl? Or would it rather play in Glendale (Fiesta), New Orleans (Sugar), or Miami (Orange) Bowl?

And even if TCU preferred to play in the Rose Bowl, the paragraph says that the deciders are not TCU, but "the conferences and Notre Dame". The Pac-10 would rather have Stanford in the Rose Bowl than in some other Bowl Game, and the other conferences are probably apathetic. If anything, most conferences would rather play TCU (I'm not sure if you've heard, but the Orthodoxy of College Football says that TCU is a joke, propelled heavenward only by a laughable schedule).

Will this happen? I don't know. Could it? Yes.

[Non-lawyer, non-pedantic readers: stop reading this blog post here.]

OK, if you've made it to this paragraph, you're either a lawyer or pedantic (or both).

Could this happen? Maybe. The problem is: the BCS procedure is self-contradictory.

The Rose Bowl Paragraph says: "that non-AQ team will play in the Rose Bowl."[emphasis mine]

But Paragraph 5 says: "the conferences and Notre Dame may [] adjust the pairings." So, which is it? WILL that team play in the Rose Bowl? Or MAY the conferences adjust the pairings? At least one of these sentences must be broken. If two clauses in a contract contradict, which survives? I'm not sure. But if it's the latter, then Stanford can go to the Rose Bowl, and the Rose Bowl won't be handicapped in the future.

Don't get me wrong. The BCS is about as stable as Element 113. The procedure is described in excruciating, legalistic degail (that, as we've seen, is ambiguous. So some lawyer somewhere is getting whipped by his partner tonight). But it survives only so long as the BCS survives. And the BCS stays awake at night, shivering and scared of the Sword of Damocles that is Anti-Trust Suits against the Nepotistic BCS. So maybe a court would say, the Rose Bowl could do this, and the Rose Bowl will decide that discretion is the better part of their valor.

But, you have to think that Larry Scott is considering how many times this week he'll be speed dialing Pasadena, right?

Monday, March 22, 2010

Finding quines by iteration

Russ Cox has an article on his blog about quines. He examines it in zip files, and mentions his favorite Unix shell quine (you'll have to read it to find out!). I sat down this weekend and implemented a cute strategy of quine-hunting: find a fixed-point of error messages. (And I should mention that I've heard this approach credited to Guy Steele. I'd appreciate any references that confirm this).

What's a quine? To quote Russ quoting Ken Thompson (in his masterful Turing Award acceptance speech): "More precisely stated, the problem is to write a source program that, when compiled and executed, will produce as output an exact copy of its source." This statement only allows valid programs in the language. The innovation of the Steele method is to squint at this definition. Instead of "compiled and executed", let's change it to "to run through a compiler/interpreter".

A traditional quine must be a valid program in the language. But when you invoke most language runtimes with an invalid program, they aren't silent. They do produce output. Often error diagnostics to help the programmer craft their gibberish into a valid program.

So what does an invalid-program quine look like? Well, we know it has to be an error message. It has to be an error message whose error is itself. Let's take python. Fire up an interpreter and enter an invalid program:


>>> a
Traceback (most recent call last):
File "", line 1, in
NameError: name 'a' is not defined

Is that error message an invalid-program quine? Let's check.

>>> Traceback (most recent call last):
File "", line 1
Traceback (most recent call last):
^
SyntaxError: invalid syntax

Nope. A NameError isn't a NameError. It's a SyntaxError.

So how will we find it? Well, we could try traditional quine-construction techniques, but this requires an in-depth knowledge of each language runtime we want to find an invalid-program quine for. And traditional quine-construction techniques are, well, hard: they require that you work backward and forward at the same time. Let's not do that.

Instead, think back to our last revelation: a NameError isn't a NameError, it's a SyntaxError. But maybe a SyntaxError is a SyntaxError (quine!). Or maybe it's a FrobError, and a FrobError is a FrobError (quine!).

And here's the advantage studying invalid-program quines: not only are they perverse, they're also easy. Take input, run it through the language runtime, compare the error message to the input. If they're different, just repeat. But if they are the same, then the language runtime evaluated the input to the error message, and we've found an invalid-program quine.

Returning to the python example: a SyntaxError isn't a SyntaxError, and it isn't a FrobError. It's an IndentationError. And an IndentationError is an IndentationError. Here, then, is our invalid-program quine for python:


>>> File "<stdin>", line 1
File "<stdin>", line 1
File "<stdin>", line 1
^
IndentationError: unexpected indent

But if you read Russ's post, you already know a python quine. So let's find some invalid-program quines in some more languages. And let's do it faster.

#! /bin/bash

languages="python;py
awk;awk
ruby;rb
gcc cc
javac java
bash sh
ksh ksh
zsh zsh
perl;pl"

# Find an error quine for a language.
# Args:
# $1: compiler for the language
# $2: file suffix
function find_quine_for_language {
COMPILER=$1
SUFFIX=$2
echo "Searching for error quine for $COMPILER"

echo "Yields falsehood when preceded by its quotation" > input.$SUFFIX
echo "" > output.$SUFFIX

found=""
for ((n=1; n <= 24; n++)) do
$COMPILER input.$SUFFIX > output.$SUFFIX 2>&1
echo -n "."

if cmp -s input.$SUFFIX output.$SUFFIX; then
found=true
break
fi

mv output.$SUFFIX input.$SUFFIX

done
echo

if [ ! -z $found ]; then
echo "Found error quine for $COMPILER after $n steps."
echo "================================"
cat input.$SUFFIX
echo "================================"
else
echo "Could not find error quine for $COMPILER after $n steps."
echo "> du -ah input.$SUFFX"
du -ah input.$SUFFIX
fi
}

for language in $languages
do
language=$(echo $language | tr ";" " ")
find_quine_for_language $language
done


First, I've listed some language runtimes and the suffix we should use for files in that language. Then I define the function that tries to find an invalid-program quine for the language. The only added sophistication from my description is a limit to the number of iterations. Why? Most runtimes on the list tell you about the first error, or the first n errors. They think that after this many errors, any more wouldn't be useful. But one of these runtimes keeps nitpicking your by-now-obviously-not-valid program. There is no fixed point. Each error message is longer than the input, and without this limit your machine grinds to a halt. (If you want to know which language leads to a 70 megabyte text file of parse errors, run the program yourself)

The moral of the story? The next time you find yourself in a quine-speed-writing competition, type gibberish and repeat.

Sunday, January 31, 2010

Why isn't the VC community talking about Shark Tank?

Shark Tank is a major-network, prime-time show about Venture Capital. So with all the great VC/entrepreneur bloggers and twitter(er)s, why isn't anyone buzzing about it?

A description: a small businessperson comes to 5 rich people (the "sharks") with their business and an offer (e.g. $48k for a 25% stake). The businessperson pitches their idea. The sharks ask questions ("how much do you sell in a day?" "how much does it cost to make this?"). The sharks make counter offers (most involve the same amount of money for at least a 51% stake). They show off their advantages ("you want me to invest because I know retail, and you're a retailer"). Isn't this the kind of transparency that we want?

Now, yes, it's a bad show. The sharks brag about the great deals they've made and how rich they are, without mentioning the fact that, say, he made his money by selling at the peak of the bubble and Mattel's acquisition of his company "has been called one of the worst acquisitions in corporate history."

But this is major network tv. We need bad shows to rally around, so that there will be less popular but better shows. For instance, Saturday Night Live. Sucks. But it takes there being an SNL for there to be a Dana Carvey show (which featured Steve Carrell and Stephen Colbert).

And yes, it's not about tech. It's about consumer retail and people making stuffed animals with cubby holes so that kids can organize their playroom by anally fisting a monkey. That's not interesting to the tech crowd. It's not really interesting to any crowd.

But this is the first show that has people present business plans, then criticize them, and giving you a glimpse into how capitalists think and operate. Shouldn't we be singing ABC's praises for giving us even this?

Thursday, January 21, 2010

Dan's advice on Resume Writing.

It's intern-hiring season, so I'm reading more resumes at work and for friends. Here are some thoughts I have.

[These are my thoughts, not necessarily my employer's. And check out Steve Yegge's tips for a longer but better-written piece.]

  • One Page.
  • Your resume fits on a page. "But I need more than one page--" No, you don't. Either you're junior enough that you can fit it on a page, or you're awesome enough that you don't even need to list every detail. (Exception: researchers. Then you're working more on a CV than a resume.) Yes, this will mean cutting down on stuff. And as you get older, it will mean cutting stuff out. Your awesome responsibilities as a lifeguard at the pool were important when you were a sophomore, not when you're a 30 year-old.
  • Each word should give someone a reason to want to hire you.
  • Go re-read your resume with that in mind.
  • Give me what I need, but not too much.
  • Yes, you need the keywords to be in there. Tell me you were a software engineer. Tell me what languages you know. But you don't need to tell me that a software engineer "designs, implements, and verifies software code to" yadda yadda.
  • Give me hooks.
  • Here's where I diverge most from Steve's advice. There are two uses of the resume. One is to get the interview. The next is to make the interview better. For the first part, you want to trim the fat. For the second, you want to leave what I call "hooks". Interesting sentences that will make your interviewer look down at your resume, then look up at you and say, "huh, this is interesting." Then, it's your time to shine. On my resume, I have hooks for small talk ("Opened for The Who"), and then hooks for what I care about ("enjoy tackling low-hanging technical fruit to bring about societal change").

    My resume screener won't care about these hooks. And they probably won't even come up on a first-pass interview (where the interviewer cares more if I've ever actually seen a computer). But when I'm talking with someone who knows I can code, and wants to know if I can code the right things, this is a useful sentence. Put enough of yourself on the page so an interviewer will give you the chance to come out in person.
  • Go back, cut it down again.
  • OK, you have a resume. Now go back and fix it, cause it's probably still bad. No, seriously, 15 minutes now will get you farther faster. Basically, candidates write what they think resume readers want to see. Stop that. Write what you'd want to read.

    Steve (linked above, also here) spends a lot of time on the bad writing that pervades many resumes. Go read that. I'll wait. Back? Good. Now, take out your resume, reread each word, and cut it out unless you can convince your antagonistic alter ego that it's truly necessary.

  • Share, and look at other people's.
  • The best way to get a better resume is to ask the 5 people you most admire (in a similar job/field) to see their resumes. You'll probably go "oooh, that looks nice". Then stop and think about what makes it nice. Copy those attributes shamelessly. Then, the next time a friend asks for resume help, say, "okay, and here's mine, so you can see what I like in resumes." (This also has the side benefit of making you keep yours up-to-date)

    Monday, January 11, 2010

    For better encryption key distribution, look to Leisure Suit Larry. [a response to Bruce Schneier]

    A few months ago, there was an uproar over our Predator drones in Afghanistan broadcasting video unencrypted. Techies coast-to-coast were a-twitter with glee that the military-industrial complex can't do anything right. Bruce Schneier put them in their place by pointing out that this data comes with an expiration date. We only need it stay encrypted for a few hours/days. He suggested a whole new key exchange system for this sort of data.

    Here's my proposal: go back to the classics. I'm referring, of course, to the 1987 softcore software magnum opus Leisure Suit Larry in the Land of the Lounge Lizards. An adventure game in the vein of other Sierra On-Line franchises of the day (Kings Quest, Space Quest, Police Quest), it added one very important aspect: boobies. And to avoid the label of smut-peddlers, it added a CAPTCHA-esque ingenuity I think we'd do well to remember.

    When you wanted to play the game, you entered your age. And then, it tested you on it. So if you said you were 25, it would ask you questions about the popular music of 10 years earlier. You could claim you were 18, but if you had the pop-cultural IQ of a 10 year-old, you were still locked out.

    Predators should send out an encrypted video signal and a hint for the key. This could rest on cultural knowledge of American pop culture, or more specifically it could rely on the specific units the video was made for. You can search Wikipedia for Britney Spears's hit 1999 signal, but can you for, say, the nickname of the commanding general of the 10th Mountain Division?

    This isn't industrial grade crypto. But it's a way to give out keys for data whose security has a lifetime of hours, not decades.

    [ This is also related to the concept of a Shibboleth. I also vaguely remember, but couldn't find a story from WWII: Germans who'd learned American accent-free would be dressed up in looted American uniforms. They would have been made familiar with American military protocol. So US soldiers started asking them questions like "who won the National League Pennant in 1938." ]

    Thursday, December 31, 2009

    Why isn't Airport Utility 5.5 on the web? [Apple Fail]

    Airport Utility is software to administer Apple hardware. It's included with the hardware, and posted on the web. Except for the version I need.

    [Apologies, faithful reader(s?), but this post is a diversion from the normal flow(trickle?) of Enfranchised posts. Instead, it's for the internet reader who landed here after performing a WWW search using the engine of their choice.]

    Earlier this year, I:
    1. bought a Time Capsule (a router/WiFi base station/hard drive). Specifically, the 2009 Time Capsule update.
    2. installed Airport Utility (the software to administer the Time Capsule) from the included DVD.
    3. cleaned up my apartment and threw out the DVD, because physical media is for suckers.
    4. found my copy of Airport Utility got downgraded (perhaps during my Snow Leopard upgrade?)
    At http://support.apple.com/downloads/#airport , you can download many versions of Airport Utility. But not 5.5. The latest there is 5.4.1, which works with many Apple Wireless base stations. But not mine. So, until they do post it, my options are:
    • download a torrent of Airport Utility 5.5 (probably with viruses)
    • buy a new Time Capsule (right)
    • borrow DVD from a friend (I don't think I have any with this Time Capsule)
    • beg Apple support. (I'll update later)

    But, why? This software is useless without an expensive piece of Hardware/Apple Profit. Other versions are public for free download. What is it about Airport Utility 5.5, specifically, that it can't be released for download?

    Maybe it:
    • has secret data embedded Apple doesn't want you to see. (Unless you've paid the $300)
    • is a retail strategy to get me to buy it again. (This is so frustrating that I'm close.)
    • would cost too much bandwidth to offer for free download. (Unlike every other version of the same software).
    Or, maybe, this update to Airport Utility is just stuck in App Review.

    Saturday, December 26, 2009

    Three Ways to Fix the Airport Security Problem (aka Trains with Rockets)

    In the wake of another terror attempt, the TSA is locking down flights. Reports of the regulations include:
    • no electronics
    • no standing in the last hour of a flight
    • only one carry-on bag

    These make traveling a lot less attractive: over the past 20 years, a coast-to-coast trip has gotten less convenient. The trip now takes longer (airplanes haven't gotten faster, and I'm more constrained in what I can do).

    I see 3 ways to return to the era of luxurious and sumptuous transcontinental travel:

    1) Bring sanity to Airport Security. Yeah, this might happen. OK, next solution.

    (Oh hey, it turns out that when a problem is hard to solve, it's easier to go around it)

    2) Build faster planes. If flying New York to San Francisco took, say, 2 hours, then it's fine not to have your computer. But Concorde tried this, and, well, kind of failed.

    3) Screw you, planes. Major airlines already operate a hub-and-spoke model. You know what else uses fixed routes? Trains. You know what have more room than planes? Trains. You know what are almost as fast as planes? Trains with Rockets.

    Yes yes yes, trains are more fuel efficient than planes. Do Americans care about fuel efficiency? No. We care about convenience and awesome. Trains with Rockets have both. Heck, I'd even be fine with Trains with Jet engines. Yes, I know they'll never be as fast as planes. But you'll have more leg room. A red-eye will be doable. And you'll get to arrive/leave in city centers. C'mon Mr. President, this massive civil works project is one I can believe in.