Home ›

code puzzles

Christian Harms's picture

Forfeit game - coding contest since 50 years

by Christian Harms on Mon, 11/08/2010 - 17:11
in

The game of forfeits is a simple game and one of the classic programming examples since 50 years. I found it in a ALGOL 60 exercise book from 1963: Count the numbers up to 100, but skip all numbers if one of the condition matches:

  • number is divisible by seven
  • number contains a seven
  • sum of digits is divisible by seven
  • sum of digits contains a seven

Develop a function which calculates all numbers based on the given conditions. The only one parameter for the function is the range and the function should return the Array of all valid numbers. Hint: You must not cheat while returning a sliced constant result array. The result of the function with max=100 is: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 18, 19, 20, 22, 23, 24, 26, 29, 30, 31, 32, 33, 36, 38, 39, 40, 41, 44, 45, 46, 48, 50, 51, 53, 54, 55, 58, 60, 62, 64, 65, 66, 69, 80, 81, 82, 83, 85, 88, 90, 92, 93, 94, 96, 99, 100]. Read more

clean code variant

Nico Heid's picture

Google Code Jam - Rotate

by Nico Heid on Sun, 08/15/2010 - 17:33
in

It's time for some basic finger exercise. The Google Code Jam Rotate is very trivial, so relax and fire up your IDE.

I was a bit lazy, so there is no reading of the input sets, just a two-dimensional array and two functions

Rotating

As the Google solution pointed out, there is actually no need to really rotate the 2dim array. Just push everything to the right, as if gravity would be to the right. That's the same as rotating everything and keeping gravity towards the bottom. But we save a few lines this way.

So here is the "gravity from the right" code

  1. public static void fakeRotate(char[][] board) {
  2.  
  3.     for (int i = 0; i < N; i++) {
  4.         for (int j = N - 1; j >= 0; j--) {
  5.             if (board[i][j] != '.') {
  6.                 // push to right
  7.                 int m = 1;
  8.                 while ((j + m) < N && board[i][j + m] == '.') {
Read more

Nico Heid's picture

Google Code Jam - Theme Park

by Nico Heid on Sat, 07/31/2010 - 12:20
in

Theme Park is another good example of a problem which can be solved with a fairly simple algorithm. The simple version will solve the small input set without a problem, but will run almost infinitely with the large dataset.

You can read the problem on the Google Code Jam site: Theme Park

simple solution

The simple solution is to put the groups in a static array, use a pointer that "wraps around" using modulo and fill the roller coaster until it's so full, that the next group does not fit in, then let it ride earning income accordingly to the seats taken.

This is a correct solution, but unfortunately a bit slow. The input set can have a roller coaster with up to 109 seats and 108 rides and groups as large as 107. Read more

Nico Heid's picture

Google Code Jam - The Snapper Chain

by Nico Heid on Sun, 06/20/2010 - 12:23
in

The Google problems are always nice, sometimes even a bit too tricky. This years entry problem was quite nice with some difficulties you could run in.

You need to read the problem first, to follow the article, so here's the link: http://code.google.com/codejam/contest/dashboard?c=433101#s=p0&a=0

If you're a hands on programmer first you might just want implement the chain without looking at the problem more extensively. So you might end up with something like this:

  1.                         // snapping
  2.                         boolean toggle = true;
  3.                         for (int j = 0; j < snaps; j++) {
  4.                                 toggle = true;
  5.                                 for (int k = 0; k < snapperCount; k++) {
  6.                                         if(toggle == false){
  7.                                                 break;
  8.                                         }
  9.                                         if (toggle == true) {
  10.                                                 snapper[k] = !snapper[k];
  11.                                         }
  12.                                         if (snapper[k] == true) {
  13.                                                 toggle = false;
  14.                                         }
  15.  
  16.                                 }
  17.                         }
  18.  
  19.                         // we need power on all snappers
  20.                         boolean power = true;
  21.                         for (int j = 0; j < snapperCount; j++) {
  22.                                 if (snapper[j] == false) {
Read more

Nico Heid's picture

Google Code Jam - Africa Qualification Round 2010

by Nico Heid on Mon, 04/26/2010 - 15:49
in

The Google Code Jam is an interesting option to work on some challenging problems.
With the first qualification round coming up at May 7th, it's time to look at the Africa qualification round, to see what to expect.

You have 24 hours to solve three rather simple problems. Solving two problems brings you into the next round.

I will present my Java solutions. The Code Jam site provides the code of every contestant.

Store Credit

read problem description
You just need two nested loops to find the matching articles. Just a finger exercise.

  1. for (int i = 0; i < items.size(); i++) {
  2.                         for (int j = i + 1; j < items.size(); j++) {
  3.  
  4.                                 // is this the right shopping?
  5.                                 int newSum = items.get(i) + items.get(j);
  6.  
  7.                                 if (newSum == credit) {
  8.                                         return "Case #" + caseNr + ": " + (i + 1) + " " + (j + 1);
  9.                                 }
  10.                         }
  11.  
  12. }
Read more

Syndicate content