Thursday, July 26, 2012

The ability to write nested loops is not a sufficient condition of employment

But it ought to be a necessary one.

Suppose you were helping me write a TicTacToe program. I have this Java code so far:
package com.vaporware.tictactoe;

import com.vaporware.common.logging.FormattingLogger;

class Board {
  Piece cells [][];

  Board() {
    this.cells = new Piece [3][3];
  }

  boolean xWins () {
    return wins(Player.X);
  }

  boolean oWins () {
    return wins(Player.O);
  }

  boolean wins (Player player) {
    // FINISH ME!
    return false;
  }
}
Assume further that there is a getOwner() method on a Piece that returns a Player.
Can we finish the wins (Player player) method?

5 comments:

Unknown said...

What do you want it to do? Evaluate the board to look for a winner?

Joe Marshall said...

Yep. Real simple. The method xWins() should return true iff Player.X has 3 in a row.

Arcane Sentiment said...

Even in Java, there are reasonable solutions that don't have nested loops, because some of the loops (from 0..2, or across the eight possible rows) can be unrolled without hurting readability. Maybe k in a row on an m-by-n board would be a better example?

Joe Marshall said...

I'm seeing too many candidates that cannot write a reasonable solution (nested loops or otherwise) for this special case, let alone something more general.

John Cowan said...

This problem as given is underspecified. Before I read your comment, I thought wins() was intended to determine whether the current position was a winning position or not, as distinct from an already-won position. That involves understanding the basics of search. Still simple — I wrote a program to do this for a 4x4x4 board in high school — but not the same order of simplicity.

I might well not bother with a loop if I was trying to beat a clock, since there are only eight cases to test and I type fast.