DWITE programming contest solutions
DWITE is a online programming contest primarily for Canadian high school students. On this page I provide an unofficial archive of contest problems and my own solutions in Java. The official web site is http://dwite.ca/ .

Repository
My repository at GitHub has this content:

My DWITE solution code (Java)
Problem statements (for the contest rounds I solved)
Test data (for the rounds I solved)
JUnit test suites (to check my solutions)
You can browse the repository or download the entire package. If you see any improvements that can be made, feel free to fork the project and publish your changes!

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 Filesdwite200410p4.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 ^{4} ) to O (n ^{2} ) 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} n ) solution, where n is the number of digits. Mine runs in O (n ^{2} ) 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.
UPC Check Digitdwite200602p3.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.
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.
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.
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.
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: Alternating flood fill.
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 have the sieve of Eratosthenes .
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 starting in October 2007. 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 (starting October 2007) are licensed under Creative Commons BY-NC-SA 3.0 , and are republished (and slightly edited) with permission.

Related / browse
Sidebar
Recent

Random