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!