December 3rd, 2014
Lars Szuwalski wins the $10,000 Vistaprint Tech Challenge
Author: Daniel J. Barrett
Congratulations to the winner of Vistaprint’s first worldwide programming contest, the 2014 Tech Challenge! The task we put forth was to compute the smallest-sized shipping box to hold an arbitrary collection of Vistaprint products. This problem is intractable in general (NP complete) so we were on the lookout for clever ideas. The competition was strong as our judges evaluated each submission for accuracy, innovation, runtime efficiency, and quality of code and documentation.
In the end, after a close finish, our judges selected Lars Szuwalski of Denmark as the grand prize winner. Lars, who will receive $10,000 (US) for his entry, is a senior/lead developer at Nordea Bank in Copenhagen, the largest bank in Scandinavia. (He also has three children, which keeps him busy in other ways!)
We asked Lars how he came up with his solution:
Initially, I imagined an assembly process where a gravitational force was pulling in boxes towards a center, while maintaining a balance on the combined “structure.” Then I realized that large individual boxes would dominate the dimensions of the final package. So the final algorithm sort of combines those two ideas: combine the biggest two boxes, draw a bounding box around them, and then fill the empty spaces in this virtual box with smaller boxes. When you can’t fit any more boxes into the combo-box, you add it to the set and start over until you end up with one combo-box. I also added randomness to the process where some combo-boxes are unpacked and the new set repacked.
Indeed, Lars’s algorithm produced efficient solutions and ran instantaneously even for large numbers of products in a box.
Our judges also awarded some Honorable Mention prizes of $500 for four other notable entries:
• Ahsan Alam, Massachusetts, USA
• Daniel Hartmeier, Switzerland
• John Lawton, Massachusetts, USA
• Karol Wegrzycki, Poland
Congratulations to all of our winners, and thank you to all contestants who entered! We plan to run more Tech Challenges in the future, so watch www.lifeinvistaprint.com for details! (You can subscribe by RSS to the entire site or just the Tech Blog.)