George V. Reilly

HouseCanary PyCon2016 Progamming Challenge

Yesterday, while at PyCon, I whipped up a quick, brute-force answer to the House­Ca­nary PyCon2016 Progamming Challenge in a few minutes. That was sufficient to pass the first two test cases and win me a very pretty House­Ca­nary t-shirt.

The answer ran in O(n⁴) time, so it failed miserably on the larger problem sets in the third and fourth cases. I mulled it over and came up with an O(n²) solution that runs in reasonable time on the larger problem sets. On the second test case, input1.txt, runtime drops from 5.2s to 0.2s.

I submitted my new answer. I’ll learn on Monday if I won the speed challenge.

blog comments powered by Disqus
Review: Jimmy the Kid (audiobook) » « Review: The Queen of Ireland