Delivery from Napkin Doon

I got my prize from Napkin Doon's Big Fun Game in the mail.  Imagine my horror as I saw that the envelope was ripped to shreds and it was inside one of USPS's "We care about your mail, honest" plastic bags.  Inside the bag, inside the shredded envelope, was a toploader that looked like it had been through hell and back, all scratched up and with ink blots on it.  I wasn't feeling too confident about my sweet Gypsy Queen inserts.

Much to my relief, the cards were in great condition.  I suspect the toploader is an old one that's been used for quite a few mailings, and the damage didn't come during this particular journey.

Thanks again, Mr. Doon!

2011 Google Code Jam: Round 1

Again, here is the most important detail first: I advanced!

As of this writing I'm sitting at 910th place in Round 1B.  Assuming no disqualifications of me or anyone else, that's where I'll stay.  As a reminder, Round 1 is split into sub-rounds A, B, and C.  Everyone can compete in 1A, and the top 1000 advance.  All but those 1000 can compete in 1B, and again, the top 1000 advance.  Finally, everyone but the already-advanced 2000 gets one final shot in 1C, and again, the top 1000 advance.  This mean there will be 3000 coders in Round 2, and I'm one of them.

As Google noted, Round 1A was brutal.  I skipped the lowest-value Problem A out of fear it wouldn't be enough to advance (As it turns out, solving it in 42:01 would have been enough).  I also felt like there were some tricky cases in it that made it harder than it should be for the points offered.  Problem B also seemed like it could wind up taking too long to run a quickly coded solution.  So, I focused in on the highest-value, Problem C.

You are playing a game with a fancy deck of cards. Each card has three bonus numbers: a card bonus c, a score bonus s, and a turn bonus t. Some of the cards start in your hand, while the rest are in a deck on the table. You start with one turn.

On each turn, you can choose any card from your hand and play it. If it has bonus numbers c, s, t, then the following happens:

• The card is discarded from your hand, and it can never be used again.
• You draw the first c cards from the deck into your hand. If the deck has fewer thanc cards in it, you draw all of them.
• Your total score increases by s.
• Your number of remaining turns increases by t.

If you do not have any cards in your hand at the start of a turn, then nothing happens on that turn. Your goal is to get as high a score as possible before running out of turns.

For example, suppose your hand and deck contain the following cards:

         +---+---+---+            +---+---+---+
   HAND: | c | s | t |      DECK: | c | s | t |
         +---+---+---+            +---+---+---+
Card #1: | 0 | 0 | 2 |   Card #4: | 1 | 1 | 0 |
Card #2: | 0 | 5 | 0 |   Card #5: | 0 | 1 | 1 |
Card #3: | 2 | 1 | 1 |   Card #6: | 2 | 2 | 0 |
         +---+---+---+            +---+---+---+

The following table shows how you can get a score of 8 from these cards. The first three columns show your hand, the number of turns left, and your score before playing each card, and the final column shows which card to play.

+---------+------------+-------+------+
| Hand    | Turns left | Score | Play |
+---------+------------+-------+------+
| 1, 2, 3 |      1     |   0   |   1  |
| 2, 3    |      2     |   0   |   3  |
| 2, 4, 5 |      2     |   1   |   2  |
| 4, 5    |      1     |   6   |   5  |
| 4       |      1     |   7   |   4  |
| 6       |      0     |   8   |   -  |
+---------+------------+-------+------+

As you can see, the card bonuses and turn bonuses allow you to chain together a long sequence of cards before you have to stop.

My first instinct turned out to be correct, but it went south from there.  I figured out the best thing to do is play any cards with a turn bonus first.  That would certainly have no negative effect on the potential final score.  From there I tried varying strategies, from playing the cards with the highest card bonus, to playing the highest score when you're down to your last turn, to a recursive brute force algorithm.  None worked for even the small input.  I ended with 0 points.

Round 1B turned out much better.  I just about jumped out of my chair when I saw Problem A.  It asked for a fairly simple RPI calculation.  I've written lots of code like this for various personal projects, such as writing an algorithm designed to be "Better than the BCS" and decide the best team in College Football and any sport.  At the 32:03 mark, I had full credit for the small and large input.  I wondered if that would be enough to advance, but I suspected it might not.  I read the next problems and took a quick break to think about which one I could do best.

Problem B looked most plausible to solve quickly, so I went for it.

Last year, several hot dog vendors were lined up along a street, and they had a tricky algorithm to spread themselves out. Unfortunately, the algorithm was very slow and they are still going. All is not lost though! The hot dog vendors have a plan: time to try a new algorithm!

The problem is that multiple vendors might be selling too close to each other, and then they will take each other's business. The vendors can move along the street at 1 meter/second. To avoid interfering with each other, they want to stand so that every pair of them is separated by a distance of at least D meters.

Remember that the street is really long, so there is no danger of running out of space to move in either direction. Given the starting positions of all hot dog vendors, you should find the minimum time they need before all the vendors are separated (each two vendors are at least D meters apart from each other).

My solution wasn't quite optimal, so it worked for the small input, but failed for the large input.  In fact, I let my solution on the large input run much longer than the allotted 8 minutes.  After an hour, I finally stopped it, still with no solution.  My first naive solution was to move in increments of 0.5s, start with the leftmost vendor, and move everyone 0.5m to the left, as long as they would not get closer than D meters to the vendor to the left.  In that same 0.5s, I did the same thing starting from the right and looping to the left, moving everyone to the right as long as they wouldn't get too close.  I refined the solution a bit before attempting the large input, but still it took too long to run.

With my time expired on Problem B and not enough time to think out a solution on Problem C, I was down to scoreboard watching.  I saw my rank drop slowly from 561, down to 999th with 19 minutes to go.  When it hit 1009 with 18 minutes to go I knew I had to get out of the house for a bit before I went crazy.  I ran 2 quick errands and returned about 45 minutes after the end of the contest, and saw I finished in 910th place, good enough to advance.  This happens because Google gives an "optimistic" score during the competition, so anyone who submits a solution for the large input gets credit until the correctness of the solution is revealed at the end.  My large input solution for Problem A was correct, and enough other solutions were incorrect to vault me back into the top 1K.

For the 3rd consecutive year I've made the top 3000.  I'm hoping I can get one step further this year and hit the top 500 to make it to Round 3, but I'm pretty happy with how far I've gotten already.

2011 Topps Heritage - Blaster Box

7 packs, plus one extra pack?! How exciting!

Why don't they just say 8 packs? Anyone know?

 I could break this up into 8 blog posts, but frankly, no one wants that, not even me. Here's the whole box in one giant post.  I really need to get hold of a good scanner, so for now I'll spare you any sub-par scans. Note that this was purchased at Target, so I payed the 1 cent premium.  Let's hope it pays off.

Pack 1:
52. NL Batting Leaders
159. Joba Chamberlain (the Hut!)
193. Miguel Tejada
209. Andrew Romine
243. A.J. Burnett
359. Carlos Zambrano
403. Jonathan Papelbon
412. Colby Rasmus (When he hits homeruns the commentators love referring to is as a Colby Jack.  Does that cheese exist anywhere but St Louis?)
Chrome Refractor: C91 Dan Haren #140/562 - He's a former Cardinal, I'm waffling on whether it's up for trade.

Pack 2:
43. LA Dodgers
128. Joel Pineiro (former Cardinal and reason for dozens of local Joels to go by Jo-el)
153. Marco Scutaro
160. Garrett Jones
172. Dusty Baker (I like manager cards, I don't know why)
248. Chris Johnson
268. Ervin Santana
325. Alexi Ramirez
SP: 461 Russ Mitchell

Pack 3:
1. Josh Hamilton
3. David Ortiz
69. Cory Luebke
241. Josh Johnson
293. Jonathon Niese
314. Miguel Cabrera
330. Mike Napoli
346. Felix Hernandez
Chrome: C97 Ryan Doumit #0182/1962 - Definitely up for trade

Pack 4:
84. Denard Span
95. Ryan Zimmerman
182. Cody Ross
239. Brandon Beachy
272. Delmon Young
274. Will Venable
348. Eric Sogard
358. Andre Ethier
Green Parallel: 124 Brian Duensing - Up for trade

Pack 5:
7. Carlos Beltran
54. NL Home Run Leaders (with a nice Pujols scowl)
76. Freddie Freeman
118. Skip Schumaker (The reason you don't put an OF at 2B)
225. Adrian Beltre
322. Bruce Bochy
339. J.J. Hardy
405. Gio Gonzalez
SP: 444. Rafael Furcal

1 hit per pack so far, if you count SPs, which I do, cause it's my blog and I wanna.

Pack 6:
30. Chipper Jones (oh how I remember taunting him with Larrrrr-ryyyyyyyyyy)
108. Matt Kemp
194. Jordan Walden
208. Rickie Weeks
232. 2010 World Series Game #1
247. Jonathan Lucroy
269. Lance Berkman (in a Cardinals uniform no less)
300. Carl Crawford
SP: 450. Johnny Cueto (Karate Man)

Pack 7:
93. Nick Swisher (of "How I Met Your Mother" fame)
96. Jered Weaver (of causing his-own-brother-to-be-released fame)
115. Alfonso Soriano (the reason you don't put a 2B in the OF)
167. Wilson Ramos
187. Jon Lester
242. Manny Acta
298. Jason Kubel
351. Twin Terrors (Morneau-Mauer)
399. Roy Halladay
and a tenth, unnumbered card, labeled Checklist 6 of 6.  I'm having a hard time finding information about these, but I'm guessing there's, oh, I don't know, 6 or so.  It is interesting that it was the 10th card of the 9-card pack though.  I don't think I'll trade it just yet.

Pack 8:
64. Nick Markakis
68. Travis Snider
116. Gavin Floyd
120. Bronson Arroyo
131. Brett Sinkbeil
145. Dallas Braden
170. Aramis Ramirez
365. Howie Kendrick
News Flashbacks - NF-8: New York Mets join National League - up for trade.

Well there you have it.  One hit per pack if you count generously.  No relics, but that's ok, I think I'd rather have the 2 base cards right now, unless it's a Cardinal.  I'll make sure my Want list and Trade list are updated accordingly.  Make me some offers.  Please?

2011 Topps Heritage Tracker:
Base 70/425
SP 3/75

Self-Congratulatory Post

OK, not just yet.

I have been provisionally accepted to the doctoral program in Mathematics (Computer Science) at UMSL.  It's provisional because I haven't yet taken the GRE.  I've also previously completed a Masters degree with a 4.0 at the same University, so I imagine that had something to do with it.

When I first skimmed the letter that arrived Friday, I figured provisional just meant I wasn't yet rejected, pending GRE scores.  When I actually read it, I noticed the key detail: they're actually letting me register for Summer Semester!  So, suddenly I've got just under a month before classes start.

Due to my previous Masters degree, which will allow me to transfer 30 hours, I should have just 30 more credit hours to complete, including some taken for dissertation research.  Since I'm still working full time, I may go a bit slow, but I'll put my tentatively planned graduation date at May, 2014.  It should be an exciting and exhausting 3 years.

2011 Google Code Jam: Qualification Round

First, the most important detail: I Qualified!

There are 10,565 Qualifiers as of this writing, including - or should that be excluding - at least one above my rank (I started at 9912, now 9911) who has been disqualified.

I was a bit surprised when I logged in.  Google changed the format from solving one small and one large input to qualify, to needing 25 points. The first problem was worth 10 and 10, the next two were 10 and 15, and the last was 10 and 20.  This meant if I wanted to solve just one, it couldn't be the first.  It also meant if I wasn't too confident and I could only manage to solve the small version of the problem, I could pick up 2 more problems and solve their small input as well, and still advance.

I chose Problem B, as it looked fairly simple.

As a wizard, you can invoke eight elements, which are the "base" elements. Each base element is a single character from {Q, W, E, R, A, S, D, F}. When you invoke an element, it gets appended to your element list. For example: if you invoke W and then invoke A, (we'll call that "invoking WA" for short) then your element list will be [W, A]. 

We will specify pairs of base elements that combine to form non-base elements (the other 18 capital letters). For example, Q and F might combine to form T. If the two elements from a pair appear at the end of the element list, then both elements of the pair will be immediately removed, and they will be replaced by the element they form. In the example above, if the element list looks like [A, Q, F] or [A, F, Q] at any point, it will become [A, T]. 

We will specify pairs of base elements that are opposed to each other. After you invoke an element, if it isn't immediately combined to form another element, and it is opposed to something in your element list, then your whole element list will be cleared.

So basically, add a letter to a list, then see if it needs to combine with the previous letter to make a new one.  If not, loop over the whole list to see if the list needs to be cleared.  Looping over the list worried me a bit for the large input, as I would only have 8 minutes to solve it, and I've run out of time before when I wrote a quick and dirty, brute-force solution.  Luckily the Qualification Round usually isn't overly complex, so it worked out.

I also solved Problem A on paper, but I didn't have time to actually code, debug, and submit the solution.  I did go in and check my solution on Monday and found that sure enough, it worked.  I might have been pretty disappointed if the large input on problem B hadn't worked out but I had held back a problem A solution.  It runs in in O(n) time, where n is the number of button presses, so I was happy to at least have accomplished one "good" solution.

Now I get up to 3 tries to make the top 3000, next Friday, Saturday, and Sunday.  As I'm in the Central Time Zone, so I'll have to be pretty desperate to do Round 1C at 4am.

Big Fun Game

The Adventures of Napkin Doon, was kind enough to offer a "Big Fun Game" which is basically a White Elephant game, except he provided all the prizes from a divvied up box of 2011 Topps Gypsy Queen. I was lucky enough to get a slot and the #4 pick. Very little stealing has gone on, probably because no relics or crazy high-value cards have been drawn yet, and everyone's hoping. With 2 fellow bloggers left to pick, here's the lot I currently have:

Lot #6, "The Great Ones" Inserts

I chose #6 because #5 was AL Base cards, hoping for NL base cards and a Cardinal. Jim Palmer and Mel Ott were a nice surprise though.

2011 Topps Heritage

The Dimwit put 5 Topps Heritage cards in one of his Five Card Fridays, and I bit.  Once I got those 5 cards in hand, I knew I wanted to collect the set.

The theme was "AL Central".  Hope it's cool I borrowed your scan, Dimwit.

The set it honors still predates my life by 20 years, so it's not nostalgia per se, but I really like the non-glossy cards for a change sometimes.  In fact, I just checked my collection and I have a grand total of 2 cards older than 1962.

This will be a somewhat expensive set to collect relative to its popularity.  As far as I can tell the cheapest per-card price is the $20 Target and Walmart blaster boxes of 8 packs.  It'll take 6 of those to at least get 425 base cards to make 1 for 1 trades.  Of course, once I get a few inserts and SPs I'll probably want to complete some of those sets too.

I've purchased one blaster box, but I think I'll rate-limit myself by only opening a pack or two a week, and sharing the results on my blog.

Base 5/425
SP 0/75