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 Bamford'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 Neukirchen:
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 Buckley:
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!