Solution to Codejam 2022 1C (Letter Blocks) in Ruby

Question

The following is my solution to the Letter Blocks problem from Codejam 2022: https://codingcompetitions.withgoogle.com/codejam/round/0000000000877b42/0000000000afe6a1.

Problem

It is a rainy day, so you are indoors building towers of letter blocks. A letter block is a wooden cube that has a letter printed on one of its sides. The font used for the letters makes the blocks have a clear orientation: that is, there is only one side that can be pointed down (toward the floor) and one side that can be pointed up (toward the ceiling).

You have built multiple separate towers so far. Now you want to combine all of them into a single megatower by choosing one of your towers as the base, then picking up another tower (without changing the order of its blocks) and stacking the whole thing on top of that, and so on, until all towers have been used.

As an additional constraint for the megatower, for any two blocks that have the same letter, all blocks between them must also have that letter. That is, each letter of the alphabet that appears in the megatower needs to appear in one contiguous group (of one or more blocks).

For example, consider the following three possible megatowers. (These are separate examples, not built from the same original towers. Also note that the different block sizes are just for fun and are not part of the problem.)

Towers of ABCCC, AAA, and ACBCC.

The leftmost two megatowers are valid, since each letter appears in a contiguous group. However, the rightmost megatower is not valid, because there is a B in between two Cs.

Given the towers that you have built so far, can you stack them all up into a valid megatower?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case is described by two lines. The first line consists of a single integer N, the number of towers that are currently built. The second line consists of N strings S1,S2,…,SN representing the towers. Each of these strings consists of only uppercase letters. The i-th letter of each of these strings is the letter on the i-th block from the bottom in the represented tower.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a string representing a valid megatower as described above, or the word IMPOSSIBLE if no valid megatower can be built. (Notice that the string IMPOSSIBLE can never itself represent a valid megatower, since the two Is have other letters in between.)

Limits

Time limit: 5 seconds.
Memory limit: 1 GB. 1≤T≤100

1≤ the length of Si≤10, for all i

Test Set 1 (Visible Verdict)
2≤N≤6

Test Set 2 (Visible Verdict)

2≤N≤100

In summary, we have towers of wooden cubes, each with a letter printed on one side. Given n different towers of letter blocks, we want to stack all of them on top of each other in some order such that same letters appear in one contiguous group.

My code is a bit blunt, but it gets two green checkmarks. The triple nested loop looks bad, and I'd appreciate any ideas to simplify it, or any other feedback!

The code must work on Ruby 2.5.

require "set"

module LetterBlocks
  def self.mega_tower(towers)
    # Check if all towers are valid.
    return unless towers.all? { |tower| valid_tower?(tower) }
    # Group single-letter towers together because we need to process them first.
    towers.sort_by! { |tower| [tower.chars.to_set.size, tower[0]] }
    # Keep combining towers that share a letter.
    loop do
      repeat = false
      # Check every pair of towers.
      towers.each_with_index do |tower, i|
        next if tower.empty?
        towers.each_with_index do |other_tower, j|
          next if other_tower.empty? || i == j
          # Letters that tower and other_tower have in common.
          common_letters = tower.chars.to_set & other_tower.chars.to_set
          # Do nothing if the towers share no letters.
          next if common_letters.empty?
          # Impossible if there is more than one distinct common letter.
          return if common_letters.size > 1
          # The single common letter
          letter = common_letters.first
          if tower[-1] == letter && other_tower[0] == letter
            # Put other_tower on top of tower
            tower.concat(other_tower)
            other_tower.clear
            repeat = true
            break
          elsif tower[0] == letter && other_tower[-1] == letter
            # Put tower on top of other_tower
            tower.prepend(other_tower)
            other_tower.clear
            repeat = true
            break
          else
            return false
          end
        end
      end
      break unless repeat
    end
    # Combine remaining independent towers.
    towers.join
  end

  def self.valid_tower?(tower)
    sorted_tower = tower.each_char.sort.join
    sorted_tower.squeeze!
    tower.squeeze.size == sorted_tower.size
  end
  private_class_method :valid_tower?
end

if __FILE__ == $PROGRAM_NAME
  test_count = gets.to_i
  1.upto(test_count).each do |test_num|
    _n = gets.to_i
    towers = gets.split(" ")
    mt = LetterBlocks.mega_tower(towers) || "IMPOSSIBLE"
    puts "Case ##{test_num}: #{mt}"
  end
end

Example output:

$ cat tests.txt
6
5
CODE JAM MIC EEL ZZZZZ
6
CODE JAM MIC EEL ZZZZZ EEK
2
OY YO
2
HASH CODE
6
A AA BB A BA BB
2
CAT TAX
$ ruby solution.rb < tests.txt
Case #1: ZZZZZJAMMICCODEEEL
Case #2: IMPOSSIBLE
Case #3: IMPOSSIBLE
Case #4: IMPOSSIBLE
Case #5: BBBBBAAAAA
Case #6: IMPOSSIBLE

Answer 1

The valid_tower? predicate is very nice.

tiny nit:

    sorted_tower.squeeze!
    tower.squeeze.size == sorted_tower.size

Go for parallel construction, replacing those lines with:

    tower.squeeze.size == sorted_tower.squeeze.size

(I suspect the .squeeze! line may be a leftover artifact of print() debugging.)

---

Hmm, this is an interesting "discard the value" idiom:

    _n = gets.to_i

where we never use _n again. In python the convention is to assign such a value to _, as in the contrived example for _, item in enumerate(items):. Oh, I see! It's a rubocop thing. And this usage is preferred as it clearly indicates Author's Intent. Kudos!

---

I am reading mega_tower(). It is a bit on the long side. Also, style nit, assuming that each comment is helpful I would find it easier to read if you introduce a blank line before comments.

Maybe you wrote "Check if all towers are valid." before writing any code? In which case, good. But as it stands now, your code is perfectly clear, it is lovely, and the redundant comment is merely a distraction. Consider deleting it, and similarly redundant comments.

Why am I so hard on comments? Because "comments lie!". That is, maintainers often adjust code without adjusting related comment, and then it's just sitting around waiting to deceive someone. We put the "what" in the code, and the "why" in the comments.

Also, each time you see a "produce X" comment in English, consider turning that into a def self.produce_x() helper. The helper can optionally have a comment or RDoc comment on it if you feel there's more to say.

---

This is a lovely line of code

    towers.sort_by! { |tower| [tower.chars.to_set.size, tower[0]] }

accompanied by a helpful comment. It would have benefited from having an associated unit test that shows example input / output.

I wonder if having another sorted copy, where tower[-1] was tie breaker instead of tower[0], could help us match up compatible towers more quickly?

---

I'm afraid I'm not grasping the loop do idiom. This appears to be a while repeat loop.

The nested loops should definitely be a predicate helper().

---

It took me a while to understand this function's signature.

It returns several types, and I try to write functions that return a single stable type.

Another way to put it is the function returns either falsey or a valid megatower. I would have preferred that it return either an empty string or a valid string.

It starts with return unless ... all valid, meaning we return nil. Same thing for common letters, as in the "OY YO" case. And then we see this:

            repeat = true
            break
          else
            return false

We're maintaining a boolean, and we return a boolean. Leading me to believe that the function signature was about some feasibility predicate. And then it finishes with returning a valid string.

It can be OK, and occasionally useful, to return diverse types. But do it seldom, have a good reason for it. Typically it makes things harder for the caller, especially when there's multiple call sites, since now we need to handle the various cases.

In this particular bit of code, using both nil and false to represent the identical return value caused some minor confusion.

---

You complained that the pairwise matching might be improved. Suppose you wanted to take another stab at solving this. Here's what I would suggest.

Write a helper that will .select the compatible towers. Return them to the caller, who will then worry about the appropriate way to mutate towers. Consider making the helper responsible for swapping towers into a consistent order.

Such a change won't improve running time. It is strictly for separating concerns when you choose a way to organize the code.

I notice that towers.product(towers) offers Cartesian cross product, but since you need indices it probably won't help this code.

---

Overall?

This code achieves its goals and is mostly maintainable by others.

Keep a careful eye on several items as you are writing new code:

1. Write short functions, with liberal use of tiny helpers.
2. Avoid writing words in a comment, when you could form a helper name with those words. Do write a comment to introduce most methods and classes.
3. Offer the caller a single return type, or carefully document it.