SuperQuest and Willamette Programming Contest

TechStart, a non-profit that I've been helping run for 6+ years now, held its annual SuperQuest Spring Conference and Willamette University - TechStart Programming Contest down in Salem, OR on Saturday March 12.

At our spring conference we trained nearly 40 Oregon and Washington K-12 teachers in various topics related to technology and computer science: Scratch programming for elementary students, robotics, video production for instruction, and discrete mathematics. The instructors for these training sessions are teachers that have a proven track record in the classroom - they exude credibility.

One of the highlights for me was seeing fellow TechStart board member Don Domes teach how to create video captures for instruction on a tight budget. He uses Khan Academy as his model.

While the teachers are being trained, over a dozen high school computer programming teams were hard at work on the state high school programming competition run by Fritz Ruehr of Willamette University. This was my fourth or fifth year attending the event, and the second time watching my own son Jacob compete as part of the Sherwood High School team. Teams work on 14 different computer science problems (in the style of the ACM programming contest, problem set from 2010) and score points for successful completion as well as bonus points for finishing problems before other teams.

Here's a sample of one of the easier problems of the day:

Bracket Balancing

Programmers know how annoying it can be when parentheses, brackets, and braces get out of balance in their code. You are working on a programmers' editor and need to write a utility which will highlight selected portions of the code in red if any of the bracketing characters within are out of balance. Your code will check the selection for "round" parentheses (), square brackets [], curly braces {} and even angle brackets <>. Furthermore, you should check a "no crossings" rule, so that different shapes of brackets don't get mixed up. For example, a string like " < () [ { ] } >" is not allowed: even though the curly braces and the square brackets come in matched pairs, they cross each other in between. Finally, your program should ignore any non-bracket characters, so that other bits of code (perhaps variable names, numbers, and keywords) can be intermixed. As output, you should write out the word "OK" (if everything balances, with no crossings) or "BAD" if something goes wrong. (If you are using a GUI, you may even highlight the code in green or red to indicate OK and BAD strings... just make sure that it's clear when your check is finished!)

Some examples:

Input: foo(bar[i].{}<<>>[baz]123)    Output:  OK
Input: oof{}[<<quux>> 17 ] ( {}      Output:  BAD
Input: [17] () 23 .. < [ > foo >     Output:  BAD

I had some free time towards the end of the contest and worked through a solution on my own using Ruby:

VALID_OPEN = "([<{"
VALID_CLOSE = ")]>}"

def open_token(char)
  return VALID_OPEN.index(char)
end

def close_token(char)
  return VALID_CLOSE.index(char)
end

def matches_open(open, close)
  VALID_OPEN.index(open) == VALID_CLOSE.index(close)
end

def bracket_balance(input)
  token_stack = []
  input.chars.each do |char|
    if open_token(char)
      token_stack.push char
    elsif close_token(char)
      return false if !matches_open(token_stack.pop, char)
    end
  end
  token_stack.length == 0
end

while expression = gets
  if bracket_balance(expression)
    puts "OK"
  else
    puts "BAD"
  end
end

I think test-driven development is a great methodology for approaching problems like this, and I plan to do some mentoring of Jacob and his team members as they approach next year's contest. Here are some samples of tests I wrote as I worked on the problem (these would look even cleaner if I used Cucumber or FIT-style scenario tables):

class TestBracketBalancing < Test::Unit::TestCase
  def test_empty_string
    assert bracket_balance('')
  end

  def test_single_paren
    assert !bracket_balance('(')
  end

  def test_double_paren
    assert bracket_balance('()')
  end

  def test_1
    assert bracket_balance('foo(bar[i].{}<<>>[baz]123)')
  end

  def test_2
    assert !bracket_balance('oof{}[<<quux>> 17 ] ( {}')
  end
end

Jacob's team had a solid teamwork model - he and one team member focused on implementation and programming and took on some of the easier problems on their own, while their senior team member worked ahead on paper in pseudo-code on some of the more challenging items. They did very well, finishing second overall and just a hair behind the winning team (both teams solved 8 of the 14 problems).