Code Jam 2019 Round 1A

I tried the 2.5-hour Round 1A Friday night and just missed the cut-off for advancing. The round started a few minutes late as the problems site was overloaded at first. When it did respond, I got the problems in a different order, with the last problem listed first. Thinking it was the first (and therefore easiest) problem, I started on it without noticing the difficulty scores. That “Alien Rhyme” involved finding pairs of words with common suffixes. There were a few gotchas to the greedy approaches, so I was lucky to work out a correct algorithm, but it took me a few tries to get a decent data structure for organizing the words by common suffixes. I ended up with a vector of maps, one per suffix length with each map itself mapping a suffix to a set of words. Amazingly, it worked.

Next I tried the Pylons problem which boiled down to finding a complete path through a graph. I couldn’t think of a good approach for the large 20×20 constraint, so I went for partial credit with a brute force solution which would work for the small 5×5 constraint. After that was submitted I noticed that the large graphs were dense enough to have many complete paths, so maybe a randomized brute force approach would work. I added a little randomization and resubmitted. It turned out I had the right idea, but I didn’t randomize it enough (only the starting points and not the node visitation order). So I still only got partial credit, but with a penalty for making a second submission.

The remaining problem was an interactive one and I had too little time left for the overhead of testing it locally, so I didn’t attempt it. I could see that the solution may require solving a Chinese Remainder problem, and I did solve it the next day. It’s nice that the site enters practice mode when the competition is over, so we can test out ideas later.

The good news is that I get to compete in Round 1B!

Google Code Jam 2019 Qualifying

This year’s Google Code Jam started yesterday with the 27-hour Qualifying Round. I managed to get all the problems correct for a score of 100/100 along with about 1000 of the 35,000+ participants. You only needed a score of 30 to advance, so many who could have done better probably stopped when they had enough points to qualify.

The problems always get harder with each round, but this year’s qualifying round seemed easier than usual. The first two problems only took a few minutes each, and I almost stopped there since I knew I already had 30 points.

The third problem, Cryptopangrams, was also easy to figure out, but the solution required doing math on 100 digit integers, which I couldn’t readily do in C++. I briefly looked around for a simple big-integer library to include but decided to relearn enough Python to use that. It felt silly googling things like whether array indices start at 0 or 1 (it’s 0 in Python), how to comment out a line (‘#’ character), and how to do integer division (‘//’ operator). I never did come across a good Python cheat sheet; instead I had to wade through various introductory teaching pages. Fortunately, there was no real time pressure and it was a simple problem.

All the problems have at least one small/easy test case and one large/hard test case. For the fourth problem, I could figure out the easy case quickly but had no idea how to solve the hard case. After re-reading the problem statement I realized the parameters were constrained enough (looking for at most 15 errors in a 1024 bit string) for me to solve. These are most fun problems to solve: when you start with no clue and keep looking at different angles until you find a solution.

The other complication for the fourth problem was that it was interactive. Instead of the usual read-problem-input/write-solution sequence, an interactive problem requires multiple queries and responses before the final solution can be determined, and that makes testing your code much trickier. Google nicely provides a testing Python script, which I eventually got working in my CLion environment. Had to use chmod to make testing_tool.py executable and had to prefix it with #!python for it to run. Then I set up a CLion target for the interactive_runner.py script which would launch the testing tool and my code and get them to talk to each other. Maybe I can remember enough of it to get through the next round when time is more constrained.

The Code Jam results list is a bit harder to navigate than it used to be. I wanted to look at other contestants’ solutions to the Cryptopangrams problems to see if any of them used C++. You can still look at submitted solutions, but when you do so you lose your place in the list, so you have to start over at the top of the list with each try. I looked at a few entries in the top 20 and none used C++ for that problem. Most used Python, some Java and one Ruby.

2017 Highlights

Just to avoid the embarrassment of going a calendar year without a blog post, here is a summary of some of my 2017 highlights. It’s not that I’ve been silent, but I’ve mostly switched to microblogging on Twitter (@xangregg) for sharing updates.

Tie-dye marathon

Some summers I keep track of a tie-dye “marathon” where I see how many days in a row I can go wearing a different tie-dye each day. This year I made it 32 days. Most of the images are on Twitter. Here are days 13 – 24.

Google Code Jam 2017

I tried both the code jam and the distributed code jam this year. In the regular code jam I made it to the round of 3000 before bombing out with a tied-for-last score. I keep forgetting the later rounds often require ready-made advanced optimization algorithms. I did better in the distributed code jam, advancing to the round of 500, which was enough to win my third code jam T-shirt. The distributed code jam is tricky since you submit code that is run on a distributed system of 100 CPUs. This year it helped that I built a test harness that used 100 threads for a better simulation of the actually process communication issues.

Packed Bars

Trying to find a decent way to show data with many categories in a skewed distribution, I created a new chart type called packed bars. Here’s an example showing costs of billion-dollar disasters before this year.

I presented packed bars in a poster at the IEEE VIS conference in Phoenix, and there are now implementations in JMP, R, Excel and D3.js. Ironically, the JMP script is the weakest implementation pending the arrival of JMP 14 in March 2018. It’s only great such data and has some learning curve, but skewed data is pretty common, especially in quality control (defect counts) and finance. I hope packed bars can become useful to others.

How old is that globe?

Bonnie gave me this old globe for my 50th birthday last year, hoping it was also about 50 years old. There’s no date on it, but the seller thought it was from the 1960s.

globe - 4a

It wasn’t until I saw this recent XKCD flow chart for dating maps that I sought to get a better estimate of the globe’s age.

thumb1

Simple as it is, I made a couple errors trying to traverse the diagram, beginning with the very first choice.

diagram closeup 1

My globe has Istanbul, but I went off on the left path, not noticing that the order of the labels was reversed from the order in the question. It didn’t take long too realize the error, but I almost didn’t catch my second error.

map closeup2

I was trying to follow the “no” branch from the Bangladesh node, and I mistakenly ended up at the United Arab Republic node. Apparently following a line is harder than I thought.

Once I had my errors fixed, the diagram dated my globe to the range 1961 to 1964. In the course of doing a little more exploring, I discovered the manufacturer of the globe, Replogle Globes, has a How Old is Your Globe? page. It’s a list of 100+ countries that have changed names since 1939.Screen Shot 2016-06-05 at 2.18.33 PMIt’s not as fun as the XKCD chart, but it’s more complete, especially in the period of my globe, though I still had to supplement it with Wikipedia to get the exact dates of the name changes.

Interestingly, the results are both precise and slightly conflicting. My globe has Zambia, which was Northern Rhodesia until October 24, 1964, and it has the United Republic of Tanganyika and Zanzibar which only existed for six months ending on October 29, 1964. That gives an amazingly precise origin window of only five days. However, the globe also denotes Malta as being a British territory even though Malta gained independence on September 21, 1964. I’m guessing the globe is from late 1964 or early 1965 with the Malta indication (and possibly Tanzania) being out of date. Regardless, 50 years is about right for the age.

globeclose - 1 (2)

The globe is in pretty good condition and has a two axes of rotation, making it easy to get a good look at Antartica, for instance.

globe antarctica

Days in a Month Formula

Curtis McEnroe posted a “tongue-in-cheek” derivation of a formula for the number of days in a month, ignoring leap years.

His result, in JavaScript:

function f(x) { return 28 + (x + Math.floor(x/8)) % 2 + 2 % x + 2 * Math.floor(1/x); }

His derivation is quite logical. I made a shorter alternative using a different technique, which I will leave for the reader to puzzle out.

function f(x){return 28+(62648012>>x>>x&3); }

 

My year with Android via Nexus 5

A year ago, I was ready for a change. I was tired of my tiny iPhone screen and the off-contract cost of AT&T cell service, so I switched to a Google Nexus 5 with a nice screen and T-Mobile with friendly and cheaper month-to-month service. But now I’m back to a iPhone and AT&T. The size problem has been fixed with the iPhone 6, though it’s still a little smaller than the Nexus 5, and my AT&T service is now employer subsidized. AT&T has also adapted to offering more T-Mobile-like plans.

Reasons I was looking to change back to iPhone/AT&T:

  • Battery life was terrible for my Nexus 5. It would barely make it 10 hours in sleep mode. I can only imagine that my cell/wifi reception was so poor that the phone was constantly waking up and looking for a better connection.
  • Poor T-Mobile coverage in this area. Too many places, I had no data coverage.
  • Android was not as convenient to sync with my Mac (iTunes/iPhoto). However, now I see iTunes and iPhoto aren’t as convenient as they used to be if you don’t opt in to the cloud sharing.
  • I missed having a hardware mute switch for the entire phone. Android has several different volume settings and muting one (like ringer volume) doesn’t mute the others (like app noise volume).

Things I will miss from Nexus/Android:

  • Convenient integration with Google Now. I get most of the functionality from the Google iOS app, but it’s not as convenient or as tightly integrated as on Android. Surprisingly often, it would tell me what I needed to know before I asked.
  • T-Mobile customer service. The fact that it was easy to cancel is a good sign in itself. Also, when we went to Toronto last summer, T-Mobile prompted me to buy a short-term international data plan (about $20), while my wife’s AT&T phone silently accumulated $100s in international roaming charges, and she thought she had cellular data turned off.
  • Openness of the app store, including being able to use Firefox and ad blockers.

One bonus of the switch-back is that my old iPhone apps carried over from before. Perhaps the downside of the open Google Play store is there is more a focus on in-app ads instead of paid apps. The ad-based Scrabble was unusable (a fullscreen ad after every move), so I’m happy to get back to my paid, ad-free Scrabble app on iOS.

One more thing: for some reason the iOS Google Maps app doesn’t show traffic as well as the Android version. These two screen captures are showing about the same thing before my morning commute, but the iOS version on the left puts the blue “your route” line over the red “slow traffic” lines, making it hard to see the traffic along your route.

Charity Solicitations Visualized

Way back in 2006, I tallied my charity solicitations, and since then the situation has gotten comically worse. So over the past year, I’ve tried to keep all the solicitations I received from various charities, some of which I haven’t contributed to in years. This time, instead of a simple table, I’ve made a couple kitchen floor charts showing the actual pieces of mail received. I probably missed a few, and phone calls are not represented.

Here are my “charts” of charities sending the most and least amount of mail in 2014.

charitymost

charityleast

Care is easily the most annoying (I even found another piece after taking the pic). I didn’t even know I had donated to Care, but they handled a donation for typhoon relief.

It’s good to see that Public Citizen and Southern Poverty Law Center are doing better. They were the top offenders in 2006, but they’re now mostly honoring my request for one solicitation per year.

Perhaps the annoyingness is exacerbated by my giving pattern, which is to give toward the end of the year. Unfortunately for me, common practice is to accept the December gift and then send an “annual renewal” just a few weeks later in January.

The worst offenders have either been dropped or switched to reduced anonymous giving, but I expect the junk mail to continue for years. And anonymous giving is expensive as far as I can tell. Network for Good adds a 5% fee and JustGive adds 4.5%. Hopefully, that includes the credit card fees, but I’m not sure. It shouldn’t been so expensive just to move money. Fidelity Charitable with a flat fee of $100 per year may be another option, especially if the credit card fee is separate for the other options.

My truly least annoying charity (annoyance == 0) is one that sent me no mailings or online annoyances: the Online Encyclopedia of Integer Sequences. Thanks to Neil Sloane and many volunteers for that excellent resource. Wikimedia was also in the no-mailings camp, but they made Wikipedia pretty annoying to use for most of December, so I’m not sure where to rank them.