# Bracket Packing (#78)

**URL:** <https://www.ruby-forum.com/t/bracket-packing-78/94703>\
**Category:** Ruby\
**Created:** [May 11, 2006, 4:03pm UTC](https://www.ruby-forum.com/t/bracket-packing-78/94703 "2006-05-11T16:03:28Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [May 11, 2006, 4:03pm UTC](https://www.ruby-forum.com/t/bracket-packing-78/94703/1 "2006-05-11T16:03:28Z")

</div>

As I’m sure you have noticed by now, this was a very popular quiz. The  
problem  
gave two options for solutions and I’m glad to see that we had a fair  
number of  
both. Let’s examine a couple of checkers and one corrector.

First, we will have a look at a solution that just checks the packer  
instructions. This is an improved version of my own code, based on  
changes I  
learned from Ross B.'s solution:

```
#!/usr/local/bin/ruby -w

require "strscan"

stack = Array.new
input = StringScanner.new(ARGF.read)

until input.eos?
  if input.scan(/[\[({]/)
    stack.push(input.matched)
  elsif input.scan(/[\])}]/)
    exit(1) unless "#{stack.pop}#{input.matched}" =~ 

```

/\A(?:[]|()|{})\Z/  
else  
input.scan(/[^[](){}]+/)  
end  
end  
exit(1) unless stack.empty?

```
exit(1) if input.string =~ /\(\)|\[\]|\{\}/

puts input.string

```

You can see that I start by pulling in the StringScanner library and  
wrapping  
the input in an instance of that class. I also create a stack to help  
me with  
the checks we will talk about next.

The until loop may be the longest section of code, but it is a simple  
process.  
Here we just work through the input in chunks, which can be one of three  
things.  
If a chunk is an opening parenthesis, bracket, or brace, we push it onto  
the  
stack (in the if branch). If we find a run of  
non-parenthesis/bracket/brace  
characters (the Bs in the quiz examples), we skip right over them (the  
else  
branch). Finally, each time we meet a closing parenthesis, bracket, or  
brace,  
we pop the latest opener off of the stack and make sure we have a  
matched pair  
(the elsif branch). When we have run through all of the characters, the  
stack  
should be empty?() if we properly matched all of the packaging material.  
(Otherwise, we have an opener that was never closed.)

There’s still one other condition our stack check didn’t catch. With an  
input  
like [{(B)()}], we have an empty set of packaging that doesn’t make  
sense. I  
use one last Regexp to spot these cases.

If my expectations are not satisfied at any point, there is no need to  
finish  
the checks and the program just exit()s with a code of one indicating  
the error.  
If we make it all the way to the end, it means I am satisfied and the  
program  
will naturally exit() with the zero all-clear code, after printing the  
packing  
sequence.

The minus of this stack trick is that it didn’t cover the edge cases  
well, so I  
had to add more checks to handle them. Some found a better process to  
get  
around this, which was to “unwrap” each layer of packing. Here’s a nice  
example  
from Christian N.:

```
def unwrap(desc)
  [desc.gsub!('BB', 'B'), desc.gsub!('(B)', 'B'),
   desc.gsub!('[B]', 'B'), desc.gsub!('{B}', 'B')].nitems > 0
end

def valid?(desc)
  desc = desc.dup
  true while unwrap desc
  desc == "B"
end

packet = ARGV.first.to_s
if valid? packet
  puts packet
  exit 0
else
  exit 1
end

```

Start with the bottom third here. You can see the input packet is read  
and then  
checked by valid?(). Depending on the result, the if statement handles  
the  
printing and exit codes.

Now we can move up to valid?(). It does three things: copy the input,  
run  
unwrap() on the input until it returns false, and check to see if we are  
left  
with a single B at the end. That of course leads us to the magic  
unwrap()er.

The unwrap() method tries to perform four global substitutions. The  
first just  
combines and side by side Bs. The other three remove any packing around  
a (B),  
[B], or {B} respectively (leaving just the B). The results of all four  
substitutions are gathered into an Array and the non-nil items are  
counted.  
(gsub!() returns nil if it didn’t change anything.) If that count is  
greater  
than zero, we made a change and should loop again to check for more, so  
true is  
returned. When all four substitutions are nil, we have unwrap()ed the  
package  
as far as possible and can stop.

I thought that solution came out cleaner, with less special cases.

Now what if you wanted to go the distance and do the corrections too?  
Here’s  
the beginning of one possible solution by Kerry B.:

```
Brackets = {'(' => ')', '[' => ']', '{' => '}'}

# Adds missing close brackets (aborts on error unless @fix).
def fix_closings(str)
  closers = []
  fixed = ""
  str.split(//).each do |c|
    if Brackets.has_key?(c)
      # Add expected corresponding bracket to a stack
      closers.push(Brackets[c])
    elsif Brackets.has_value?(c)
      closer = closers.pop
      if closer
        # Append any missing closing brackets
        while closer != c
          abort unless @fix
          fixed << closer
          closer = closers.pop
        end
      else
        abort unless @fix
      end
    end
    fixed << c
  end
  # If we've hit the end of the description, make sure any leftover
  # closing brackets are added
  closers.reverse.each {|a| fixed << a}
  fixed
end

# ...

```

This method works similar to the stack solution we examined earlier.  
Here the  
closers variable holds the stack, which gets added to anytime the code  
runs into  
an opener. Then, when it is time to close a pair (because we have  
reached a  
closer or the end of the input), the stack is popped until we find the  
correct  
closer or empty the stack.

Now this will complete any opened sets, whether the input had them right  
or not.  
See if a closer is reached in the input that doesn’t match the latest  
opening,  
popping the stack until we get to it closes all outstanding pairs up to  
that  
point.

What this doesn’t yet handle is pairs that were never opened. For that,  
we need  
another trick:

```
# ...

# Reverses the description, mirroring brackets (eg "{foo]" => "[oof}").
def reverse_desc(str)
  new_str = ""
  str.split(//).each do |c|
    if Brackets.has_key?(c)
      new_str << Brackets[c]
    elsif Brackets.has_value?(c)
      new_str << Brackets.invert[c]
    else
      new_str << c
    end
  end
  new_str.reverse
end

# ...

```

This just reverses a string, with a catch: all parenthesis, brackets,  
and  
braces are flopped. If it was an opener it becomes a closer, and visa  
versa.

Now if you fix the input once, reverse and fix again, then reverse back  
to  
normal, you end up with a totally corrected input. Here’s the  
application code  
that triggers that process:

```
# ...

@fix = ARGV.shift == "-f"
desc = gets.chomp
# Add missing closing brackets, flip the description and repeat, then 

```

flip  
# it back the right way round again  
fixed = reverse\_desc(fix\_closings(reverse\_desc(fix\_closings(desc))))  
puts fixed

Very clever Kerry. Thanks for sharing.

A big thank you to all who played with this quiz. You all taught me  
clever  
approaches this week.

Next week, Ross is in charge and he’s got a great problem for you.  
After that,  
there will be one week off, then I’ll return with more material. See  
you then!