Project Nayuki

DWITE programming contest solutions

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


DWITE solutions repository at GitHub

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:

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

Contest round Problem Solution Comments
Area 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.
Credit Card Check Digitdwite200411p1.javaEasy.
Factoringdwite200411p3.javaHard, messy: Rational zeros of polynomials.
For Loopsdwite200411p4.javaHard, messy: Multi-scan evaluation or Dijkstra’s shunting yard algorithm.
Wind Chilldwite200411p5.javaEasy.
Prime 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.
DWITE Golf Tournamentdwite200501p1.javaStraightforward: Sorting.
Harshad Numbersdwite200501p3.javaEasy, brute force computation.
Zeller’s Congruencedwite200501p4.javaEasy: Follow the given algorithm.
Different Bases Multiplicationdwite200501p5.javaTrivial using library functions, otherwise medium.
Bretschneider’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.
Odometersdwite200510p1.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.
Quadrilateral 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.
The Mazedwite200512p2.javaMedium: Breadth-first search. Reused from DWITE P5.
Reducing Fractionsdwite200512p3.javaMedium: GCD algorithm.
Now I Know My ABC’sdwite200512p4.javaEasy: Histogram.
How Many Sumsdwite200512p5.javaMedium: Subset sum problem, dynamic programming.
Filling 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.
Points on a Linedwite200602p1.javaEasy. Mine doesn’t use the division or floating-point.
Floppy Disk 3½-inch High Densitydwite200602p2.javaEasy: Knapsack problem, dynamic programming. Similar to DWITE P4.
UPC Check Digitdwite200602p3.javaEasy.
Prime Palindromesdwite200602p5.javaMedium: Brute force search, sieve of Eratosthenes.
Pete’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.
Lottery Ticket Checkerdwite200611p2.javaStraightforward.
Linear Binomial Productsdwite200611p3.javaStraightforward.
Money Prizedwite200611p4.javaMedium: Dynamic programming.
Goldbach’s Weak Conjecturedwite200611p5.javaMedium: Recursion, sieve of Eratosthenes.
Jimmy’s Lost His Marblesdwite200612p1.javaEasy: Knapsack problem, dynamic programming. Essentially the same as DWITE P4.
Ulam Spiral Walkwaydwite200612p2.javaStraightforward.
Circular Primesdwite200612p3.javaStraightforward.
The Ubiquitous 196dwite200612p4.javaStraightforward.
Caesar’s Cipherdwite200612p5.javaEasy.
Filling The Conedwite200701p1.javaEasy: Algebra. Reused from DWITE P1.
Minesweeperdwite200701p2.javaStraightforward. Reused from DWITE 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!
Vanilla 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.
Not 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.
Yet 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.
Curve-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.
I 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.
LaNDscAPE iidwite200810p1.javaEasy.
Simple Checksumdwite200810p2.javaEasy.
School’s a mazedwite200810p3.javaMedium: Breadth-first search.
What is this Roman Numeral?dwite200810p4.javaStraightforward.
Moving Stuff in Boxesdwite200810p5.javaHard: A souped-up version of the NP-complete bin-packing problem; exponential time.
My 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 P3.
Water damagedwite200811p5.javaStraightforward: Grid traversal.
ASCII Rhombusdwite200812p1.javaEasy.
Unicorns and Teaspoonsdwite200812p3.javaEasy, essentially the same as DWITE P4.
Time for changedwite200812p4.javaEasy: Knapsack problem. Similar to DWITE P4.
Now in 3Ddwite200812p5.javaMedium: Breadth-first search, a slightly more complex version of DWITE P4.
Four-player Pong with no playersdwite200901p1.javaEasy.
Secret partydwite200901p3.javaMedium: Graph traversal.
Shortest path around v2dwite200901p4.javaMedium: Breadth-first search, essentially the same as DWITE P4.
Blow your mind with 4th Ddwite200901p5.javaMedium: Breadth-first search.
Baby 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.
iProfitsdwite200910p1.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.
Anglesdwite200911p1.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.
Quiz Timedwite200912p1.javaEasy.
Rounding to Fibonaccidwite200912p2.javaEasy.
Binary Test Strings 2dwite200912p3.javaStraightforward. Similar to DWITE P3.
Spiral Outdwite200912p4.javaStraightforward because n ≤ 20, but messy in the general case.
Up To Four Coloursdwite200912p5.javaMedium: Recursion, graph coloring, chromatic number.
Social Media Overloaddwite201001p1.javaTrivial.
Verifying Distributed Workdwite201001p2.javaEasy: Histogram.
Moving at the same timedwite201001p3.javaStraightforward.
Ice Mazedwite201001p5.javaMedium: Minimum distance with a curious set of edges. Similar to DWITE P5.
ASCII bar graphsdwite201003p1.javaEasy.
Round to Second Primedwite201003p2.javaStraightforward.
Summary Diffdwite201003p3.javaStraightforward.
Kind of like OCRdwite201003p4.javaEasy: Recursion.
Weak Passwordsdwite201003p5.javaStraightforward: Brute force.
ROT13 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. Reused from DWITE P4
Air Travel Planningdwite201004p5.javaStraightfoward: Shortest path algorithm; I used Bellman–Ford.
Binary 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 P4.
Snapper Chaindwite201006p5.javaEasy: Think about it mathematically; don’t use brute force.
Age 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 P5.
Pattern 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: Bipartite graph testing.
Integers 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.
Future 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.
Colourful 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.
(cs4hs)Root of a stringdwite201107p1.javaEasy.
Sum of primesdwite201107p2.javaEasy: Sieve of Eratosthenes.
Triangles in a griddwite201107p3.javaMedium: Geometry, equivalence detection.
Arab-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.
Wandering 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.
Weighted 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.
Crossword Countdwite201201p1.javaStraightforward: Scan the grid.
Prime Timedwite201201p2.javaEasy if you understand properties of integer factorization.
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.
Age Gatedwite201202p1.javaReused from DWITE P1.
Unit rectanglesdwite201202p2.javaReused from DWITE P2.
Binary Weightdwite201202p3.javaReused from DWITE P3.
Forest Firesdwite201202p4.javaReused from DWITE P4.
Cube Worlddwite201202p5.javaReused from DWITE P5.
Candy 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.
Sugar Rushdwite201211p1.javaEasy.
Word Arithmeticdwite201211p2.javaStraightforward, should use bigint.
Bitstringsdwite201211p3.javaEasy, requires bigint.
Magic Trickdwite201211p4.javaMedium: Rank-based insertion.
Car Hoppersdwite201211p5.javaMedium: Dynamic programming.
Travel 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.


Trivia: DWITE stands for Do While If Then Else.

DWITE has two incarnations. The first incarnation was by Will Sentjens (I think), from to . The second incarnation is by Hacker Dan and from to . 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 ( to ) are licensed under Creative Commons BY-NC-SA 3.0, and are republished (and slightly edited) with permission.