DWITE programming contest solutions

DWITE is an online programming contest primarily for Canadian high school students. Their official web site is http://dwite.org/. On this page I provide an unofficial archive of contest problems, in addition to my own solution programs in Java.

Repository

The project repository contains:

My runnable solution programs (Java code)
Problem statements (for the contest rounds I solved)
Test data files (for the rounds I solved)
JUnit test suites (to check solutions automatically)

You can browse the repository at GitHub or download a ZIP package .

Problems and solutions

Quick jump by school year:

2002–2004: Not available
2004–2005: October, November, December, January, February
2005–2006: October, November, December, January, February
2006–2007: October, November, December, January
2007–2008: October, November, December, January, February
2008–2009: October, November, December, January, February
2009–2010: October, November, December, January, March, April, June
2010–2011: October, November, December, January, February, July (cs4hs)
2011–2012: October, November, December, January, February
2012–2013: October, November, February

Important: Every solution program depends on three shared classes: DwiteAlgorithm.java, DwiteIo.java, DwiteSolution.java. You must compile these classes, in addition to the specific solution class.

Contest round	Problem	Solution	Comments
October 2004	Area of Circle	dwite200410p1.java	Trivial.
	24 Hour Clock	dwite200410p2.java	Trivial.
	The Tallest in the Class	dwite200410p3.java	Straightforward: Convert to common unit, and sort.
	CD-ROM Files	dwite200410p4.java	Easy: Knapsack problem, dynamic programming.
	Super Long Sums	dwite200410p5.java	Easy, and trivial if using bignums.
November 2004	Credit Card Check Digit	dwite200411p1.java	Easy.
	Squareland	dwite200411p2.java	Trivial.
	Factoring	dwite200411p3.java	Hard, messy: Rational zeros of polynomials.
	For Loops	dwite200411p4.java	Hard, messy: Multi-scan evaluation or Dijkstra’s shunting yard algorithm.
	Wind Chill	dwite200411p5.java	Easy.
December 2004	Prime Factorization	dwite200412p1.java	Easy: Recursion, primality testing.
	Squareland II	dwite200412p2.java	Straightforward. Can be sped up from `O`(`n`⁴) to `O`(`n`²) by dynamic programming, though.
	Reflections	dwite200412p3.java	Trivial: Trigonometry.
	Waring’s Prime Number Conjecture	dwite200412p4.java	Messy: Brute force search with help from the sieve of Eratosthenes.
	Hidden Geography	dwite200412p5.java	Easy: String processing and searching.
January 2005	DWITE Golf Tournament	dwite200501p1.java	Straightforward: Sorting.
	Minesweeper	dwite200501p2.java	Straightforward.
	Harshad Numbers	dwite200501p3.java	Easy, brute force computation.
	Zeller’s Congruence	dwite200501p4.java	Easy: Follow the given algorithm.
	Different Bases Multiplication	dwite200501p5.java	Trivial using library functions, otherwise medium.
February 2005	Bretschneider’s Formula	dwite200502p1.java	Easy.
	Snakes	dwite200502p2.java	Medium: Flood fill and neighbor count.
	Simple Continued Fractions	dwite200502p3.java	Easy.
	Matrix Chain Product	dwite200502p4.java	Hard: Matrix chain multiplication, dynamic programming.
	Tsunami Speed	dwite200502p5.java	Trivial.
October 2005	Odometers	dwite200510p1.java	Straightforward for the `O`(10ⁿ `n`) solution, where `n` is the number of digits. Mine runs in `O`(`n`²) time, which is a more complicated algorithm.
	The Game of Life	dwite200510p2.java	Straightforward.
	Sum ’Em Up	dwite200510p3.java	Easy, and the sum can be written in closed form.
	Minesweeper	dwite200510p4.java	Medium: Flood fill (recursion).
	Five Digit Divisibility	dwite200510p5.java	Medium: Brute force search through all permutations.
November 2005	Quadrilateral Centroid	dwite200511p1.java	Easy, arithmetic mean.
	Variations on the Game of Life	dwite200511p2.java	Straightforward.
	Cinquain Poetry	dwite200511p3.java	Easy.
	Stacking Blocks	dwite200511p4.java	Easy: Subset sum problem, dynamic programming.
	Base64 Encoding	dwite200511p5.java	Straightforward.
December 2005	Semiprimes	dwite200512p1.java	Straightforward.
	The Maze	dwite200512p2.java	Medium: Breadth-first search. Reused from DWITE 2003-10 P5.
	Reducing Fractions	dwite200512p3.java	Medium: GCD algorithm.
	Now I Know My ABC’s	dwite200512p4.java	Easy: Histogram.
	How Many Sums	dwite200512p5.java	Medium: Subset sum problem, dynamic programming.
January 2006	Filling The Cone	dwite200601p1.java	Easy: Algebra.
	Scrabble	dwite200601p2.java	Messy and long.
	London Knights	dwite200601p3.java	Straightforward: Sorting. It screams for the use of SQL, though.
	Equivalent Amounts	dwite200601p4.java	Easy: Convert to common unit, then convert from common unit.
	Distance Between Towns	dwite200601p5.java	Medium: Dijkstra’s algorithm.
February 2006	Points on a Line	dwite200602p1.java	Easy. Mine doesn’t use the division or floating-point.
	Floppy Disk 3½-inch High Density	dwite200602p2.java	Easy: Knapsack problem, dynamic programming. Similar to DWITE 2004-10 P4.
	UPC Check Digit	dwite200602p3.java	Easy.
	Connect-4	dwite200602p4.java	Straightforward.
	Prime Palindromes	dwite200602p5.java	Medium: Brute force search, sieve of Eratosthenes.
October 2006	Pete’s Printing Press	dwite200610p1.java	Straightforward, but the data table to be manually input is large.
	Body Mass Index	dwite200610p2.java	Easy.
	Basketball Statistics II	dwite200610p3.java	Straightforward: Sorting.
	Count Squares	dwite200610p4.java	Straightforward. Can be sped up from `O`(`n`^5/2) to `O`(`n`^3/2) using dynamic programming, where `n` is the number of cells.
	Bad Input II	dwite200610p5.java	Easy if you have access to regexes and bignums.
November 2006	13375P34\|<	dwite200611p1.java	Easy.
	Lottery Ticket Checker	dwite200611p2.java	Straightforward.
	Linear Binomial Products	dwite200611p3.java	Straightforward.
	Money Prize	dwite200611p4.java	Medium: Dynamic programming.
	Goldbach’s Weak Conjecture	dwite200611p5.java	Medium: Recursion, sieve of Eratosthenes.
December 2006	Jimmy’s Lost His Marbles	dwite200612p1.java	Easy: Knapsack problem, dynamic programming. Essentially the same as DWITE 2004-10 P4.
	Ulam Spiral Walkway	dwite200612p2.java	Straightforward.
	Circular Primes	dwite200612p3.java	Straightforward.
	The Ubiquitous 196	dwite200612p4.java	Straightforward.
	Caesar’s Cipher	dwite200612p5.java	Easy.
January 2007	Filling The Cone	dwite200701p1.java	Easy: Algebra. Reused from DWITE 2006-01 P1.
	Minesweeper	dwite200701p2.java	Straightforward. Reused from DWITE 2005-01 P2.
	Elapsed Time in Seconds	dwite200701p3.java	Date calculation. It helps to use a date library.
	Number Theory	dwite200701p4.java	Easy if you know about the partition function, otherwise use recursion and a loop.
	Dutch Solitaire	dwite200701p5.java	Straightforward. Know how to use data structure libraries!
October 2007	Vanilla Primes	dwite200710p1.java	Easy.
	Cubes in a Pyramid	dwite200710p2.java	Trivial.
	Where’s my QWERTY?	dwite200710p3.java	Straightforward.
	Stacks of Blocks	dwite200710p4.java	Easy: Knapsack problem, dynamic programming.
	Velociraptor Maze	dwite200710p5.java	Medium: Breadth-first search, movement simulation.
November 2007	Not Quite Prime	dwite200711p1.java	Easy.
	Show Me The Money!	dwite200711p2.java	Easy.
	Floor Plan	dwite200711p3.java	Medium: Flood fill / breadth-first search.
	All Is Balanced	dwite200711p4.java	Easy: Use a stack.
	Bridges In A Graph	dwite200711p5.java	Medium: Union-find.
December 2007	Yet Another Primes Question	dwite200712p1.java	Easy.
	There’s An Essay In My Code	dwite200712p2.java	Medium: String processing with a regular expression or a state machine.
	Playlist	dwite200712p3.java	Easy: Knapsack problem.
	The Convex Fence Company	dwite200712p4.java	Hard: Convex hull, gift-wrapping algorithm.
	Portals	dwite200712p5.java	Medium: Breadth-first search.
January 2008	Curve-shot	dwite200801p1.java	Trivial, though needs a bit of math.
	And the winner is...	dwite200801p2.java	Easy.
	Don’t follow my links	dwite200801p3.java	Straightforward: Ad hoc string manipulation.
	Shortest path around	dwite200801p4.java	Medium: Breadth-first search.
	It all adds up	dwite200801p5.java	Medium: Parsing, dynamic programming / memoization.
February 2008	I heart you	dwite200802p1.java	Trivial.
	Number of factors	dwite200802p2.java	Easy.
	Parity bit	dwite200802p3.java	Trivial if you use a Hamming weight function, easy otherwise.
	Train ride	dwite200802p4.java	Medium: Breadth-first search.
	Tetris!	dwite200802p5.java	Medium: Ad hoc grid manipulation.
October 2008	LaNDscAPE ii	dwite200810p1.java	Easy.
	Simple Checksum	dwite200810p2.java	Easy.
	School’s a maze	dwite200810p3.java	Medium: Breadth-first search.
	What is this Roman Numeral?	dwite200810p4.java	Straightforward.
	Moving Stuff in Boxes	dwite200810p5.java	Hard: A souped-up version of the NP-complete bin-packing problem; exponential time.
November 2008	My shiny digital key	dwite200811p1.java	Trivial.
	My favourite digit	dwite200811p2.java	Trivial.
	My drink is made of cubes	dwite200811p3.java	Easy: Integer factoring.
	Big shiny tunes	dwite200811p4.java	Easy: Knapsack problem, essentially the same as DWITE 2007-12 P3.
	Water damage	dwite200811p5.java	Straightforward: Grid traversal.
December 2008	ASCII Rhombus	dwite200812p1.java	Easy.
	Wordcount++	dwite200812p2.java	Easy.
	Unicorns and Teaspoons	dwite200812p3.java	Easy, essentially the same as DWITE 2006-01 P4.
	Time for change	dwite200812p4.java	Easy: Knapsack problem. Similar to DWITE 2007-10 P4.
	Now in 3D	dwite200812p5.java	Medium: Breadth-first search, a slightly more complex version of DWITE 2008-01 P4.
January 2009	Four-player Pong with no players	dwite200901p1.java	Easy.
	Tic-Tac-Win	dwite200901p2.java	Straightforward.
	Secret party	dwite200901p3.java	Medium: Graph traversal.
	Shortest path around v2	dwite200901p4.java	Medium: Breadth-first search, essentially the same as DWITE 2008-01 P4.
	Blow your mind with 4th D	dwite200901p5.java	Medium: Breadth-first search.
February 2009	Baby Diff	dwite200902p1.java	Trivial.
	Kill Dash Nine	dwite200902p2.java	Trivial.
	Working Directory	dwite200902p3.java	Straightforward.
	Wiring the Server Room	dwite200902p4.java	Hard: Travelling salesman problem with a simple distance metric, with memoization.
	Nash in Traffic	dwite200902p5.java	Hard: Expression parsing and evaluation, iterated shortest paths. Not network flow.
October 2009	iProfits	dwite200910p1.java	Easy, but you have to do the math exactly.
	Word Scrambler	dwite200910p2.java	Medium: Permutations.
	That Missing Number	dwite200910p3.java	Easy: Think about it mathematically.
	My First True Letter	dwite200910p4.java	Easy.
	Running In Circles	dwite200910p5.java	Medium: Recursion, graph traversal.
November 2009	Angles	dwite200911p1.java	Easy, as long as you learn about `atan2()`.
	Mini DWITE	dwite200911p2.java	Easy.
	Binary Test String	dwite200911p3.java	Straightforward.
	Breadth-First Not Quite Tree	dwite200911p4.java	Medium: Single-source shortest paths in an unweighted graph.
	Portals Redux	dwite200911p5.java	Medium: Flood fill, with portals added.
December 2009	Quiz Time	dwite200912p1.java	Easy.
	Rounding to Fibonacci	dwite200912p2.java	Easy.
	Binary Test Strings 2	dwite200912p3.java	Straightforward. Similar to DWITE 2009-11 P3.
	Spiral Out	dwite200912p4.java	Straightforward because `n` ≤ 20, but messy in the general case.
	Up To Four Colours	dwite200912p5.java	Medium: Recursion, graph coloring, chromatic number.
January 2010	Social Media Overload	dwite201001p1.java	Trivial.
	Verifying Distributed Work	dwite201001p2.java	Easy: Histogram.
	Moving at the same time	dwite201001p3.java	Straightforward.
	Autocomplete	dwite201001p4.java	Straightforward.
	Ice Maze	dwite201001p5.java	Medium: Minimum distance with a curious set of edges. Similar to DWITE 2010-10 P5.
March 2010	ASCII bar graphs	dwite201003p1.java	Easy.
	Round to Second Prime	dwite201003p2.java	Straightforward.
	Summary Diff	dwite201003p3.java	Straightforward.
	Kind of like OCR	dwite201003p4.java	Easy: Recursion.
	Weak Passwords	dwite201003p5.java	Straightforward: Brute force.
April 2010	ROT13 Encryption	dwite201004p1.java	Easy.
	Round to power of two	dwite201004p2.java	Straightforward: Takes a bit of thinking.
	Bill Amendments	dwite201004p3.java	Straightforward: Takes a bit of code.
	Time for Change	dwite201004p4.java	Easy: Knapsack problem, dynamic programming. Reused from DWITE 2008-12 P4
	Air Travel Planning	dwite201004p5.java	Straightfoward: Shortest path algorithm; I used Bellman-Ford.
June 2010	Binary Equipment	dwite201006p1.java	Trivial if you know your bitwise operators.
	Sum of Primes	dwite201006p2.java	Easy if you have the sieve of Eratosthenes.
	Oil Spill Area	dwite201006p3.java	Medium: Recursion for flood fill.
	What is this Algebra?	dwite201006p4.java	Medium, messy: Parsing, order of operations. I used a dumb brute-force approach to keep the code simple. Related to DWITE 2004-11 P4.
	Snapper Chain	dwite201006p5.java	Easy: Think about it mathematically; don’t use brute force.
October 2010	Age Gate	dwite201010p1.java	Easy.
	Robot Vacuum Prototype	dwite201010p2.java	Easy.
	Power tiles	dwite201010p3.java	Medium: Recursion, but it’s not easy to see the problem in this light.
	Planting Trees	dwite201010p4.java	Medium: Computational geometry.
	Ricochet Robot	dwite201010p5.java	Medium: Minimum distance with a curious set of edges. Similar to DWITE 2010-01 P5.
November 2010	Pattern Matching	dwite201011p1.java	Easy.
	Seating Arrangement	dwite201011p2.java	Medium: A lot of code for a seemingly simple problem.
	Escape and Loot	dwite201011p3.java	Medium: Dynamic programming.
	Fractions to Decimal	dwite201011p4.java	Medium: Finite state machine (FSM) loop detection.
	Cogwheels	dwite201011p5.java	Medium: Bipartite graph testing.
December 2010	Integers along a line	dwite201012p1.java	Easy if you see the connection with GCD.
	Unit rectangles	dwite201012p2.java	Straightforward.
	Dominos Tiling	dwite201012p3.java	Hard: Dynamic programming with some subtlety.
	Forest Fires	dwite201012p4.java	Medium: Distance on a grid.
	E-Searching	dwite201012p5.java	Easy if using regex library, hard if writing a good pattern matcher. Mine is an NFA that runs in linear time.
January 2011	Future Printer	dwite201101p1.java	Easy, but reason about odd and even numbers carefully.
	Primal Numbers	dwite201101p2.java	Easy if you have the sieve of Eratosthenes.
	Binary Weight	dwite201101p3.java	Medium: Next permutation of a bit string.
	Mountain Hiking	dwite201101p4.java	Medium: Path distance on a grid.
	Sleepwalking Probabilities	dwite201101p5.java	Easy: Dynamic programming.
February 2011	Colourful Words	dwite201102p1.java	Easy.
	Safe from Rooks	dwite201102p2.java	Easy: Think about it mathematically; don’t use brute force.
	Balancing Act	dwite201102p3.java	Easy: Knapsack problem.
	New type of wordplay	dwite201102p4.java	Hard: Somewhat subtle dynamic programming.
	Cube World	dwite201102p5.java	Medium: Flood fill used in a specific way.
July 2011 (cs4hs)	Root of a string	dwite201107p1.java	Easy.
	Sum of primes	dwite201107p2.java	Easy: Sieve of Eratosthenes.
	Triangles in a grid	dwite201107p3.java	Medium: Geometry, equivalence detection.
October 2011	Arab-lish Numbers	dwite201110p1.java	Straightforward. Regular expressions are helpful.
	Penny Game	dwite201110p2.java	Easy.
	Take a Walk	dwite201110p3.java	Medium: Vector geometry, projections.
	C001 Numbers	dwite201110p4.java	Easy for the slow algorithm. I have a fast algorithm that is rather tricky.
	Tattarrattat	dwite201110p5.java	Medium: Dynamic programming. Somewhat similar to the longest common subsequence (LCS) problem.
November 2011	Wandering Billy	dwite201111p1.java	Easy.
	Scratch Card	dwite201111p2.java	Easy: Subsequence matching.
	Anonymous Shopping	dwite201111p3.java	Straightforward.
	Bear Trees	dwite201111p4.java	Medium: A generalization of BFS and DFS into a kind of “best-first search”.
	Portals Check	dwite201111p5.java	Medium: Union-find.
December 2011	Weighted Presents	dwite201112p1.java	Easy.
	Magical Ponds	dwite201112p2.java	Medium: Number theory, GCD.
	Combo Discounts	dwite201112p3.java	Medium: Recursion/backtracking. Vaguely similar to the knapsack problem.
	ABCA Maze	dwite201112p4.java	Straightforward: Breadth-first search.
	Tautology	dwite201112p5.java	Medium: Formula parsing, brute force truth assignment.
January 2012	Crossword Count	dwite201201p1.java	Straightforward: Scan the grid.
	Prime Time	dwite201201p2.java	Easy if you understand properties of integer factorization.
	Breaking Bonds	dwite201201p3.java	Medium: Graph connectedness and brute force search.
	LEGO Ladder	dwite201201p4.java	Medium: Use dynamic programming on all possible game states.
	Comet Vomit	dwite201201p5.java	Medium: Use clever math to reduce it to linear time.
February 2012	Age Gate	dwite201202p1.java	Reused from DWITE 2010-10 P1.
	Unit rectangles	dwite201202p2.java	Reused from DWITE 2010-12 P2.
	Binary Weight	dwite201202p3.java	Reused from DWITE 2011-01 P3.
	Forest Fires	dwite201202p4.java	Reused from DWITE 2010-12 P4.
	Cube World	dwite201202p5.java	Reused from DWITE 2011-02 P5.
October 2012	Candy Piles	dwite201210p1.java	Trivial.
	Candybar Graphs	dwite201210p2.java	Trivial.
	Costume Party	dwite201210p3.java	Easy.
	Trick or Tree’ing	dwite201210p4.java	Medium: Tree recursion.
	Haunted House	dwite201210p5.java	Hard: Breadth-first search, memoization, probably NP-complete because similar to travelling salesman problem, probably needs exponential time in general.
November 2012	Sugar Rush	dwite201211p1.java	Easy.
	Word Arithmetic	dwite201211p2.java	Straightforward, should use bigint.
	Bitstrings	dwite201211p3.java	Easy, requires bigint.
	Magic Trick	dwite201211p4.java	Medium: Rank-based insertion.
	Car Hoppers	dwite201211p5.java	Medium: Dynamic programming.
February 2013	Travel Time	dwite201302p1.java	Trivial.
	Copycat SMS	dwite201302p2.java	Easy.
	Triangle Count	dwite201302p3.java	Medium: Dynamic programming.
	Fencing Problems	dwite201302p4.java	Straightforward: Grid neighbor manipulation, but difficult to interpret the problem statement.
	Pattern Lock	dwite201302p5.java	Medium: Recursion.

Notes

Trivia: DWITE stands for Do While If Then Else.

DWITE has two incarnations. The first incarnation was by Will Sentjens (I think), from June 2002 to February 2006. The second incarnation is by Hacker Dan and CompSci.ca from October 2007 to February 2013. See the current DWITE about page for more details on the goals and history. At the moment, this collection of my solution code covers about half of the first DWITE incarnation and the entire second DWITE incarnation.

The contest problems statements (PDF and HTML files) are not made by Nayuki. The problems in the second incarnation (Oct 2007 to Feb 2013) are licensed under Creative Commons BY-NC-SA 3.0, and are republished (and slightly edited) with permission.