by Ross Bamford
The BigCo Bracket Company, one of the world's largest suppliers of brackets, hinges and fittings, has lately been experiencing problems in it's manufacturing division, with a large number or brackets lost or broken in transit owing to faulty packaging at the end of the line.
Investigations into the cause of the problem have led engineers to an ancient COBOL program controlling the packaging machinery. This program is responsible for selecting the type of packaging a given bracket should be shipped in, based on input from an array of sensors on the production line. It then sends a description of the package to the packager itself, which packs the bracket and sends it on to shipping. The description is a simple text string, made up of brackets with the following format:
(B) - Bracket in a soft wrapping
[B] - Bracket in a cardboard box
{B} - Bracket in a wooden box
Often, brackets have multiple layers of packaging for protection, for example:
{(B)} - Soft-wrapped bracket in a wooden box
[{B}] - Wooden-boxed bracket with cardboard outer
[{(B)}{(B)(B)}] - Wooden boxed single and double bracket packs with soft
inner wrap, in cardboard outer.
Now, the problem is that this venerable program has for some reason begun to output malformed packaging descriptions, occasionally missing off a bracket, for example:
[{(B}{(B)(B)}]
or:
{(B)}{(B)(B)}]
After a fruitless search for someone with the skills to fix this problem, the engineers changed tack and called you in to fix the problem from the outside.
What needs to be done?
======================
Basically, the plan is to insert another computer between the controller and the packer, upon which will run your program. The engineers can handle the integration with their systems - they just need you to write a slick bit of Ruby code to validate the packaging descriptions as they're passed in. You've been given two choices:
* Check the description, and return exitcode indicating it's okay (0)
or bad (1). If correct, you should also print the description to stdout.
If it's bad, the system can then force the controller to try again.
* Fix the description, if possible, and print it to stdout. The system
will then pass the fixed code to the packer.
Quiz Summary
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:
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:
[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:
# 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!
