Skip to main content
Code Review

Return to Question

Tweeted twitter.com/StackCodeReview/status/1622656376970379264
Added the quoted problem statement.
Source Link
pacmaninbw ♦
pacmaninbw ♦
  • 24.8k
  • 11
  • 46
  • 109

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

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

Source Link
Panic
Panic
  • 287
  • 1
  • 4

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

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

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