Solution to a competive programming contest (Codejam 2011 1A)

Question

The following is my solution to the killer word problem from Codejam 2011: https://codingcompetitions.withgoogle.com/codejam/round/0000000000433198/0000000000432fe2. In summary, we're playing Hangman. Our opponent intelligently goes through a list of 26 letter in some order. There's a dictionary of valid words, and our goal is find a word that will result in most misses.

The code is correct, i.e. it gets two green checkmarks, but I'm not happy with its readability, so I'd appreciate any feedback. It must work on Ruby 2.5.

def solve(dic, abc)
  # Group the words by size and then solve every group.
  best_word(dic, abc, abc_pos: -1, groups: dic.group_by(&:size)).first
end

# Iterates over every letter in order and divides the given words into
# groups based on match patterns. Then finds the best word across all
# groups by recursively solving each one.
def best_word(dic, abc, abc_pos:, groups: nil)
  word, score = dic.first, 0
  return word, score if dic.size < 2 || abc_pos >= abc.size
  groups ||= dic.group_by { |word| match_num(word, abc[abc_pos]) }
  # Skip the current character if none of the words contains it.
  return best_word(dic, abc, abc_pos: abc_pos.succ) if groups[0]&.size == dic.size
  groups.each do |num, group|
    group_word, group_score = best_word(group, abc, abc_pos: abc_pos.succ)
    # Increment the group's score if there were no matches.
    group_score += 1 if num.zero?
    if group_score > score || (
        # Use the word position in the dictionary to break ties.
        group_score == score && (dic.index(group_word) < dic.index(word))
    )
      word = group_word
      score = group_score
    end
  end
  return word, score
end

def match_num(word, chr)
  num = 0
  offset = 0
  radix = word.size + 1
  while i = word.index(chr, offset)
    offset = i + 1
    num = num * radix + offset
  end
  num
end

def main
  t = gets.to_i
  t.times.each do |c|
    n, m = gets.split.map(&:to_i)
    dic = Array.new(n) { gets.rstrip }
    abcs = Array.new(m) { gets.rstrip }
    ans = abcs.map { |abc| solve(dic, abc) }.join(" ")
    puts "Case ##{c+1}: #{ans}"
  end
end

if __FILE__ == $PROGRAM_NAME
  main
end

Example output:

$ cat tests.txt
2
3 2
banana
caravan
pajamas
abcdefghijklmnopqrstuvwxyz
etaoisnhrdlcumwfgypbvkjxqz
4 1
potato
tomato
garlic
pepper
zyxwvutsrqponmlkjihgfedcba

$ ruby solution.rb < tests.txt
Case #1: pajamas caravan
Case #2: garlic

Answer 1

I'm just going to comment on one function for now, since it's what I have time for.

This is a "C in ruby" style approach rather than idiomatic ruby:

def match_num(word, chr)
  num = 0
  offset = 0
  radix = word.size + 1
  while i = word.index(chr, offset)
    offset = i + 1
    num = num * radix + offset
  end
  num
end

Here's a rewrite embracing the ruby built-ins:

def match_num(word, chr)
  radix = word.size + 1
  word.chars.each_index
    .select {|i| word[i] == chr}
    .reduce(0) {|m, i| m * radix + i + 1}
end

As you can see, its almost a 1-liner, and the only thing mutating that we need to keep track of is the reduction result.

Finally, if you are just looking for a way to translate a pattern of characters within a word into a unique number, you might consider treating the characters as 1 and everything else as 0 and interpreting the resulting string as a binary number:

def match_num2(word, chr)
  word.tr("^#{chr}", '0').tr(chr, '1').to_i(2)
end

Note this will give a different result from the original, so is a suggestion for a possible alternative approach rather than a straight rewrite suggestion.

Answer 2

I am reading main. I like it.

I was going to grumble about "identifiers are too terse, use the same business terms found in the spec." But then I read the spec and saw that they literally used T instead of num_test_cases. Ok.

Your source matches, good. And the flow is clear.

---

I found this line a bit obscure.

  groups ||= dic.group_by { |word| match_num(word, abc[abc_pos]) }

In the helper function, the identifier num is rather vague, and we don't have a # comment or docstring to help us out.

Unit tests that show example inputs and outputs would have gone a long way toward documenting the behavior of this crucially important element.

The helper's name is similarly obscure. Within we find radix, which is very helpful and descriptive. Elsewhere we have score, which ties to the business language of the original specification. But num?

A unit test for best_word would also have a bit of educational value.

---

group_score is an excellent identifier. Instead of score you might have chosen the more verbose best_score (or max_score), suggesting it is an accumulator. Better still, instead of naming it produce a list and then take .max

---

Overall? How might we improve this?

It kind of feels like Fortran code. There's no globals ("common") -- good. But everything comes in via parameters. And the thing I felt was most interfering with my understanding was mixing of static + dynamic. That is, abc is static, and once you've posed a challenge word to Sean the word length is static, as is the corresponding slice of dic. So one fairly natural way to model the problem would use a class that holds those static elements fixed, with calls to methods which vary the other elements like abc_pos. Clearly other decompositions are feasible, as the current code illustrates. This code recursively solves subproblems, just not the ones I envisioned as I read the spec.

So if you're looking for another approach to this kata, I would encourage you to separate things along the axis of how quickly they vary.