Project Nayuki


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

DWITE solutions repository at GitHub

My repository at GitHub has this content:

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:

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 2004Area of Circledwite200410p1.javaTrivial.
24 Hour Clockdwite200410p2.javaTrivial.
The Tallest in the Classdwite200410p3.javaStraightforward: Convert to common unit, and sort.
CD-ROM Filesdwite200410p4.javaEasy: Knapsack problem, dynamic programming.
Super Long Sumsdwite200410p5.javaEasy, and trivial if using bignums.
November 2004Credit Card Check Digitdwite200411p1.javaEasy.
Squarelanddwite200411p2.javaTrivial.
Factoringdwite200411p3.javaHard, messy: Rational zeros of polynomials.
For Loopsdwite200411p4.javaHard, messy: Multi-scan evaluation or Dijkstra’s shunting yard algorithm.
Wind Chilldwite200411p5.javaEasy.
December 2004Prime Factorizationdwite200412p1.javaEasy: Recursion, primality testing.
Squareland IIdwite200412p2.javaStraightforward. Can be sped up from O(n4) to O(n2) by dynamic programming, though.
Reflectionsdwite200412p3.javaTrivial: Trigonometry.
Waring’s Prime Number Conjecturedwite200412p4.javaMessy: Brute force search with help from the sieve of Eratosthenes.
Hidden Geographydwite200412p5.javaEasy: String processing and searching.
January 2005DWITE Golf Tournamentdwite200501p1.javaStraightforward: Sorting.
Minesweeperdwite200501p2.javaStraightforward.
Harshad Numbersdwite200501p3.javaEasy, brute force computation.
Zeller’s Congruencedwite200501p4.javaEasy: Follow the given algorithm.
Different Bases Multiplicationdwite200501p5.javaTrivial using library functions, otherwise medium.
February 2005Bretschneider’s Formuladwite200502p1.javaEasy.
Snakesdwite200502p2.javaMedium: Flood fill and neighbor count.
Simple Continued Fractionsdwite200502p3.javaEasy.
Matrix Chain Productdwite200502p4.javaHard: Matrix chain multiplication, dynamic programming.
Tsunami Speeddwite200502p5.javaTrivial.
October 2005Odometersdwite200510p1.javaStraightforward for the O(10n n) solution, where n is the number of digits. Mine runs in O(n2) time, which is a more complicated algorithm.
The Game of Lifedwite200510p2.javaStraightforward.
Sum ’Em Updwite200510p3.javaEasy, and the sum can be written in closed form.
Minesweeperdwite200510p4.javaMedium: Flood fill (recursion).
Five Digit Divisibilitydwite200510p5.javaMedium: Brute force search through all permutations.
November 2005Quadrilateral Centroiddwite200511p1.javaEasy, arithmetic mean.
Variations on the Game of Lifedwite200511p2.javaStraightforward.
Cinquain Poetrydwite200511p3.javaEasy.
Stacking Blocksdwite200511p4.javaEasy: Subset sum problem, dynamic programming.
Base64 Encodingdwite200511p5.javaStraightforward.
December 2005Semiprimesdwite200512p1.javaStraightforward.
The Mazedwite200512p2.javaMedium: Breadth-first search. Reused from DWITE 2003-10 P5.
Reducing Fractionsdwite200512p3.javaMedium: GCD algorithm.
Now I Know My ABC’sdwite200512p4.javaEasy: Histogram.
How Many Sumsdwite200512p5.javaMedium: Subset sum problem, dynamic programming.
January 2006Filling The Conedwite200601p1.javaEasy: Algebra.
Scrabbledwite200601p2.javaMessy and long.
London Knightsdwite200601p3.javaStraightforward: Sorting. It screams for the use of SQL, though.
Equivalent Amountsdwite200601p4.javaEasy: Convert to common unit, then convert from common unit.
Distance Between Townsdwite200601p5.javaMedium: Dijkstra’s algorithm.
February 2006Points on a Linedwite200602p1.javaEasy. Mine doesn’t use the division or floating-point.
Floppy Disk 3½-inch High Densitydwite200602p2.javaEasy: Knapsack problem, dynamic programming.
UPC Check Digitdwite200602p3.javaEasy.
Connect-4dwite200602p4.javaStraightforward.
Prime Palindromesdwite200602p5.javaMedium: Brute force search, sieve of Eratosthenes.
October 2006Pete’s Printing Pressdwite200610p1.javaStraightforward, but the data table to be manually input is large.
Body Mass Indexdwite200610p2.javaEasy.
Basketball Statistics IIdwite200610p3.javaStraightforward: Sorting.
Count Squaresdwite200610p4.javaStraightforward. Can be sped up from O(n5/2) to O(n3/2) using dynamic programming, where n is the number of cells.
Bad Input IIdwite200610p5.javaEasy if you have access to regexes and bignums.
November 200613375P34|<dwite200611p1.javaEasy.
Lottery Ticket Checkerdwite200611p2.javaStraightforward.
Linear Binomial Productsdwite200611p3.javaStraightforward.
Money Prizedwite200611p4.javaMedium: Dynamic programming.
Goldbach’s Weak Conjecturedwite200611p5.javaMedium: Recursion, sieve of Eratosthenes.
December 2006Jimmy’s Lost His Marblesdwite200612p1.javaEasy: Knapsack problem, dynamic programming.
Ulam Spiral Walkwaydwite200612p2.javaStraightforward.
Circular Primesdwite200612p3.javaStraightforward.
The Ubiquitous 196dwite200612p4.javaStraightforward.
Caesar’s Cipherdwite200612p5.javaEasy.
January 2007Filling The Conedwite200701p1.javaEasy: Algebra. Reused from DWITE 2006-01 P1.
Minesweeperdwite200701p2.javaStraightforward. Reused from DWITE 2005-01 P2.
Elapsed Time in Secondsdwite200701p3.javaDate calculation. It helps to use a date library.
Number Theorydwite200701p4.javaEasy if you know about the partition function, otherwise use recursion and a loop.
Dutch Solitairedwite200701p5.javaStraightforward. Know how to use data structure libraries!
October 2007Vanilla Primesdwite200710p1.javaEasy.
Cubes in a Pyramiddwite200710p2.javaTrivial.
Where’s my QWERTY?dwite200710p3.javaStraightforward.
Stacks of Blocksdwite200710p4.javaEasy: Knapsack problem, dynamic programming.
Velociraptor Mazedwite200710p5.javaMedium: Breadth-first search, movement simulation.
November 2007Not Quite Primedwite200711p1.javaEasy.
Show Me The Money!dwite200711p2.javaEasy.
Floor Plandwite200711p3.javaMedium: Flood fill / breadth-first search.
All Is Balanceddwite200711p4.javaEasy: Use a stack.
Bridges In A Graphdwite200711p5.javaMedium: Union-find.
December 2007Yet Another Primes Questiondwite200712p1.javaEasy.
There’s An Essay In My Codedwite200712p2.javaMedium: String processing with a regular expression or a state machine.
Playlistdwite200712p3.javaEasy: Knapsack problem.
The Convex Fence Companydwite200712p4.javaHard: Convex hull, gift-wrapping algorithm.
Portalsdwite200712p5.javaMedium: Breadth-first search.
January 2008Curve-shotdwite200801p1.javaTrivial, though needs a bit of math.
And the winner is...dwite200801p2.javaEasy.
Don’t follow my linksdwite200801p3.javaStraightforward: Ad hoc string manipulation.
Shortest path arounddwite200801p4.javaMedium: Breadth-first search.
It all adds updwite200801p5.javaMedium: Parsing, dynamic programming / memoization.
February 2008I heart youdwite200802p1.javaTrivial.
Number of factorsdwite200802p2.javaEasy.
Parity bitdwite200802p3.javaTrivial if you use a Hamming weight function, easy otherwise.
Train ridedwite200802p4.javaMedium: Breadth-first search.
Tetris!dwite200802p5.javaMedium: Ad hoc grid manipulation.
October 2008LaNDscAPE iidwite200810p1.javaEasy.
Simple Checksumdwite200810p2.javaEasy.
School’s a mazedwite200810p3.javaMedium: Breadth-first search.
What is this Roman Numeraldwite200810p4.javaStraightforward.
Moving Stuff in Boxesdwite200810p5.javaHard: A souped-up version of the NP-complete bin-packing problem; exponential time.
November 2008My shiny digital keydwite200811p1.javaTrivial.
My favourite digitdwite200811p2.javaTrivial.
My drink is made of cubesdwite200811p3.javaEasy: Integer factoring.
Big shiny tunesdwite200811p4.javaEasy: Knapsack problem, essentially the same as DWITE 2007-12 P3.
Water damagedwite200811p5.javaStraightforward: Grid traversal.
December 2008ASCII Rhombusdwite200812p1.javaEasy.
Wordcount++dwite200812p2.javaEasy.
Unicorns and Teaspoonsdwite200812p3.javaEasy, essentially the same as DWITE 2006-01 P4.
Time for changedwite200812p4.javaEasy: Knapsack problem.
Now in 3Ddwite200812p5.javaMedium: Breadth-first search, a slightly more complex version of DWITE 2008-01 P4.
January 2009Four player Pong with no playersdwite200901p1.javaEasy.
Tic Tac Windwite200901p2.javaStraightforward.
Secret partydwite200901p3.javaMedium: Graph traversal.
Shortest path around v2dwite200901p4.javaMedium: Breadth-first search, essentially the same as DWITE 2008-01 P4.
Blow your mind with 4th Ddwite200901p5.javaMedium: Breadth-first search.
February 2009Baby Diffdwite200902p1.javaTrivial.
Kill Dash Ninedwite200902p2.javaTrivial.
Working Directorydwite200902p3.javaStraightforward.
Wiring the Server Roomdwite200902p4.javaHard: Travelling salesman problem with a simple distance metric, with memoization.
Nash in Trafficdwite200902p5.javaHard: Expression parsing and evaluation, iterated shortest paths. Not network flow.
October 2009iProfitsdwite200910p1.javaEasy, but you have to do the math exactly.
Word Scramblerdwite200910p2.javaMedium: Permutations.
That Missing Numberdwite200910p3.javaEasy: Think about it mathematically.
My First True Letterdwite200910p4.javaEasy.
Running In Circlesdwite200910p5.javaMedium: Recursion, graph traversal.
November 2009Anglesdwite200911p1.javaEasy, as long as you learn about atan2().
Mini DWITEdwite200911p2.javaEasy.
Binary Test Stringdwite200911p3.javaStraightforward.
Breadth First Not Quite Treedwite200911p4.javaMedium: Single-source shortest paths in an unweighted graph.
Portals Reduxdwite200911p5.javaMedium: Flood fill, with portals added.
December 2009Quiz Timedwite200912p1.javaEasy.
Rounding to Fibonaccidwite200912p2.javaEasy.
Binary Test Strings 2dwite200912p3.javaStraightforward.
Spiral Outdwite200912p4.javaStraightforward because n ≤ 20, but messy in the general case.
Up To Four Coloursdwite200912p5.javaMedium: Recursion, graph coloring, chromatic number.
January 2010Social Media Overloaddwite201001p1.javaTrivial.
Verifying Distributed Workdwite201001p2.javaEasy: Histogram.
Moving at the same timedwite201001p3.javaStraightforward.
Autocompletedwite201001p4.javaStraightforward.
Ice Mazedwite201001p5.javaMedium: Minimum distance with a curious set of edges. Similar to DWITE 2010-10 P5.
March 2010ASCII bar graphsdwite201003p1.javaEasy.
Round to Second Primedwite201003p2.javaStraightforward.
Summary Diffdwite201003p3.javaStraightforward.
Kind of like OCRdwite201003p4.javaEasy: Recursion.
Weak Passwordsdwite201003p5.javaStraightforward: Brute force.
April 2010ROT13 Encryptiondwite201004p1.javaEasy.
Round to power of twodwite201004p2.javaStraightforward: Takes a bit of thinking.
Bill Amendmentsdwite201004p3.javaStraightforward: Takes a bit of code.
Time for Changedwite201004p4.javaEasy: Knapsack problem, dynamic programming.
Air Travel Planningdwite201004p5.javaStraightfoward: Shortest path algorithm; I used Bellman-Ford.
June 2010Binary Equipmentdwite201006p1.javaTrivial if you know your bitwise operators.
Sum of Primesdwite201006p2.javaEasy if you have the sieve of Eratosthenes.
Oil Spill Areadwite201006p3.javaMedium: Recursion for flood fill.
What is this Algebra?dwite201006p4.javaMedium, messy: Parsing, order of operations. I used a dumb brute-force approach to keep the code simple. Related to DWITE 2004-11 P4.
Snapper Chaindwite201006p5.javaEasy: Think about it mathematically; don’t use brute force.
October 2010Age Gatedwite201010p1.javaEasy.
Robot Vacuum Prototypedwite201010p2.javaEasy.
Power tilesdwite201010p3.javaMedium: Recursion, but it’s not easy to see the problem in this light.
Planting Treesdwite201010p4.javaMedium: Computational geometry.
Ricochet Robotdwite201010p5.javaMedium: Minimum distance with a curious set of edges. Similar to DWITE 2010-01 P5.
November 2010Pattern Matchingdwite201011p1.javaEasy.
Seating Arrangementdwite201011p2.javaMedium: A lot of code for a seemingly simple problem.
Escape and Lootdwite201011p3.javaMedium: Dynamic programming.
Fractions to Decimaldwite201011p4.javaMedium: Finite state machine (FSM) loop detection.
Cogwheelsdwite201011p5.javaMedium: Alternating flood fill.
December 2010Integers along a linedwite201012p1.javaEasy if you see the connection with GCD.
Unit rectanglesdwite201012p2.javaStraightforward.
Dominos Tilingdwite201012p3.javaHard: Dynamic programming with some subtlety.
Forest Firesdwite201012p4.javaMedium: Distance on a grid.
E-Searchingdwite201012p5.javaEasy if using regex library, hard if writing a good pattern matcher. Mine is an NFA that runs in linear time.
January 2011Future Printerdwite201101p1.javaEasy, but reason about odd and even numbers carefully.
Primal Numbersdwite201101p2.javaEasy if you have the sieve of Eratosthenes.
Binary Weightdwite201101p3.javaMedium: Next permutation of a bit string.
Mountain Hikingdwite201101p4.javaMedium: Path distance on a grid.
Sleepwalking Probabilitiesdwite201101p5.javaEasy: Dynamic programming.
February 2011Colourful Wordsdwite201102p1.javaEasy.
Safe from Rooksdwite201102p2.javaEasy: Think about it mathematically; don’t use brute force.
Balancing Actdwite201102p3.javaEasy: Knapsack problem.
New type of wordplaydwite201102p4.javaHard: Somewhat subtle dynamic programming.
Cube Worlddwite201102p5.javaMedium: Flood fill used in a specific way.
July 2011 (cs4hs)Root of a stringdwite201107p1.javaEasy.
Sum of primesdwite201107p2.javaEasy: Sieve of Eratosthenes.
Triangles in a griddwite201107p3.javaMedium: Geometry, equivalence detection.
October 2011Arab-lish Numbersdwite201110p1.javaStraightforward. Regular expressions are helpful.
Penny Gamedwite201110p2.javaEasy.
Take a Walkdwite201110p3.javaMedium: Vector geometry, projections.
C001 Numbersdwite201110p4.javaEasy for the slow algorithm. I have a fast algorithm that is rather tricky.
Tattarrattatdwite201110p5.javaMedium: Dynamic programming. Somewhat similar to the longest common subsequence (LCS) problem.
November 2011Wandering Billydwite201111p1.javaEasy.
Scratch Carddwite201111p2.javaEasy: Subsequence matching.
Anonymous Shoppingdwite201111p3.javaStraightforward.
Bear Treesdwite201111p4.javaMedium: A generalization of BFS and DFS into a kind of “best-first search”.
Portals Checkdwite201111p5.javaMedium: Union-find.
December 2011Weighted Presentsdwite201112p1.javaEasy.
Magical Pondsdwite201112p2.javaMedium: Number theory, GCD.
Combo Discountsdwite201112p3.javaMedium: Recursion/backtracking. Vaguely similar to the knapsack problem.
ABCA Mazedwite201112p4.javaStraightforward: Breadth-first search.
Tautologydwite201112p5.javaMedium: Formula parsing, brute force truth assignment.
January 2012Crossword Countdwite201201p1.javaStraightforward: Scan the grid.
Prime Timedwite201201p2.javaEasy if you have the sieve of Eratosthenes.
Breaking Bondsdwite201201p3.javaMedium: Graph connectedness and brute force search.
Lego Ladderdwite201201p4.javaMedium: Use dynamic programming on all possible game states.
Comet Vomitdwite201201p5.javaMedium: Use clever math to reduce it to linear time.
February 2012Age Gatedwite201202p1.javaReused from DWITE 2010-10 P1.
Unit rectanglesdwite201202p2.javaReused from DWITE 2010-12 P2.
Binary Weightdwite201202p3.javaReused from DWITE 2011-01 P3.
Forest Firesdwite201202p4.javaReused from DWITE 2010-12 P4.
Cube Worlddwite201202p5.javaReused from DWITE 2011-02 P5.
October 2012Candy Pilesdwite201210p1.javaTrivial.
Candybar Graphsdwite201210p2.javaTrivial.
Costume Partydwite201210p3.javaEasy.
Trick or Tree’ingdwite201210p4.javaMedium: Tree recursion.
Haunted Housedwite201210p5.javaHard: Breadth-first search, memoization, probably NP-complete because similar to travelling salesman problem, probably needs exponential time in general.
November 2012Sugar Rushdwite201211p1.javaEasy.
Word Arithmeticdwite201211p2.javaStraightforward, should use bigint.
Bitstringsdwite201211p3.javaEasy, requires bigint.
Magic Trickdwite201211p4.javaMedium: Rank-based insertion.
Car Hoppersdwite201211p5.javaMedium: Dynamic programming.
February 2013Travel Timedwite201302p1.javaTrivial.
Copycat SMSdwite201302p2.javaEasy.
Triangle Countdwite201302p3.javaMedium: Dynamic programming.
Fencing Problemsdwite201302p4.javaStraightforward: Grid neighbor manipulation, but difficult to interpret the problem statement.
Pattern Lockdwite201302p5.javaMedium: 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.