Bracket Packing (#78)

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this quiz
    until
    48 hours have passed from the time on this message.

  2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Ross B.

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.

Have a question,

is each bracket always packaged individually?
For example : [(BB)] is this an error, should it be [(B)(B)]?

The other question is: the program always return the correct number
of B just messes up the packaging?
For example: {}B} or {}{B}? So these should be corrected to {B}, and
not {B}{B}.

Thank you,

Gautam.

On Fri, 2006-05-05 at 22:18 +0900, Gautam D. wrote:

Have a question,

is each bracket always packaged individually?
For example : [(BB)] is this an error, should it be [(B)(B)]?

Hmm… How about this: [(BB)] isn’t an error, but [(B)(B)] is better. As
long as you get a sensible (i.e. balanced) set of brackets, the packer
won’t complain but a layer of soft wrap between each bracket saves money
on returns…

The other question is: the program always return the correct number
of B just messes up the packaging?
For example: {}B} or {}{B}? So these should be corrected to {B}, and
not {B}{B}.

Yes. Adding brackets isn’t an option (they wouldn’t actually be on the
line going into the packer if you did :)).

Btw. In practice I don’t think it’s possible to correctly fix every
possible breakage, but you can always fail for those that won’t fix.

On May 6, 2006, at 2:52 PM, Pat M. wrote:

Investigations into the cause of the problem have led engineers to
made up of
[{B}] - Wooden-boxed bracket with cardboard outer

You’ve been
stdout. The system

Pat

Also do they have to have a wrapper at all? I assumed they did not
and that they did not need to have a parent wrapper.

I assumed that BB and (B)(B) were both legal.

Gautam.

On 5/5/06, Ruby Q. [email protected] wrote:

division, with a large number or brackets lost or broken in transit owing to
(B) - Bracket in a soft wrapping

After a fruitless search for someone with the skills to fix this problem, the

    * 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.

Do the brackets have to have a parent wrapper?

i.e. {(B)(B)} is of course valid
but (B)(B) isn’t.

I imagine that’s the case, I just want to make sure.

Pat

On May 6, 2006, at 6:46 PM, Gautam D. wrote:

Also do they have to have a wrapper at all? I assumed they did not
and that they did not need to have a parent wrapper.

I assumed that BB and (B)(B) were both legal.

Gautam.

Why are you even sending them to the packer then, if they aren’t
going to be packed?

Here is my solution.
It considers any input that is balanced and doesn’t contain empty
packaging (like []) valid.
For correcting it just tries every possible way of correcting a
string, until it finds a valid one.

def valid_packaging?(str)
other_br = {’}’=>’{’,’]’=>’[’,’)’=>’(’}
stack = []
pc = nil
str.split(’’).each {|c|
if other_br.values.include? c
stack << c
elsif mb = other_br[c]
return false unless stack.pop == mb && pc != mb # unbalanced, or
{} detected
end
pc = c
}
return stack.empty?
end

input = ARGV[0].to_s
pos = [input] + “{}”.split(’’).map{|c|
(0…input.length).map {|i| input[0…i] + c + input[i…-1] }
}

if corr = pos.flatten.find{|str| valid_packaging? str}
puts corr
else
exit! 1
end

On May 6, 2006, at 4:20 PM, Logan C. wrote:

Pat
Why are you even sending them to the packer then, if they aren’t
going to be packed?

This is true. I think I made the assumption as a simplification. When
I was thinking about the problem.

On Sun, 2006-05-07 at 10:35 +0900, Gautam D. wrote:

I imagine that’s the case, I just want to make sure.

Why are you even sending them to the packer then, if they aren’t
going to be packed?

This is true. I think I made the assumption as a simplification. When
I was thinking about the problem.

I don’t think an outer wrapper should be required, and both BB and
(B)(B) are technically legal, though BB is another one of those that
wouldn’t occur in correct input, for the reason Logan mentioned.

In my (increasingly detailed :)) mental image of this packing factory,
the packer automatically adds a shipping outer around each set of packed
brackets anyway - what we’re packing here are the display containers.

Here is my solution,

Though, it adds the outer packaging if one is not there. And if it
can not fix the string fails with an exit code of 1. Since, I’m a
noob to ruby it is not pretty.

Here’s my solution. I tried to make the most compact solution
I could, based on my 2.5 months Ruby experience, so it may not
be too pretty :slight_smile: Any comments are highly welcomed.

If the string is valid it outputs it and returns with exit code 0
otherwise outputs nothing and returns with exit code 1

Have a nice day everyone,
Alex

CODE
OC,OK,ERR=’([{)]}’,0,1
i=ARGV[0];r=OK;s=[]
i.scan(/./) { |c|
next if (ci=OC.index©).nil?
s.push OC[ci+3].chr if ci<3
r=ERR if ci>2 and s.pop!=c
}
r=ERR unless s.empty?
puts i if r==OK
exit r

This is my first attempt at the Ruby Q., and I’m new to the
language, so please be gentle!

First, checking validity only (I’m ignoring the contents of the
packaging, if treating {foo} as valid as well as {B}):

Brackets = {’(’ => ‘)’, ‘[’ => ‘]’, ‘{’ => ‘}’}
@fix = ARGV.shift == “-f”
desc = gets.chomp
closers = []
desc.split(//).each do |c|
if Brackets.has_key?©
# Add expected corresponding bracket to a stack
closers.push(Brackets[c])
elsif Brackets.has_value?©
closer = closers.pop
if !closer || closer != c
abort
end
end
end
abort if closers.size > 0
puts desc

Now the fixing version (behaves like the first version unless you
specify the “-f” flag):

Brackets = {’(’ => ‘)’, ‘[’ => ‘]’, ‘{’ => ‘}’}

Adds missing close brackets (aborts on error unless @fail).

def fix_closings(str)
closers = []
fixed = “”
str.split(//).each do |c|
if Brackets.has_key?©
# Add expected corresponding bracket to a stack
closers.push(Brackets[c])
elsif Brackets.has_value?©
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

Reverses the description, mirroring brackets (eg “{foo]” => “[oof}”).

def reverse_desc(str)
new_str = “”
str.split(//).each do |c|
if Brackets.has_key?©
new_str << Brackets[c]
elsif Brackets.has_value?©
new_str << Brackets.invert[c]
else
new_str << c
end
end
new_str.reverse
end

@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

No doubt it could have been done in half the code, but it seems to
work, at least on the limited examples I’ve tried. I started trying
to do it with regular expressions, but as usual that made my head hurt.

Kerry

Here’s my solution, it’s pretty bad as it doesn’t fix anything, but I
was looking for an excuse to play with racc and I just did it in the
last 15-20mins or so:

% cat brackets.y
class BracketParser
rule
pack_string: packing
curly: ‘{’ pack_expr ‘}’
square: ‘[’ pack_expr ‘]’
round: ‘(’ pack_expr ‘)’
packing: curly | square | round
bs: ‘B’ | ‘B’ bs
packing_list: packing | packing packing_list
pack_expr: bs | packing_list

brackets.tab.rb is pretty massive so I’m omitting it, anyone without
racc who really wants to see it can email me off list

% cat parse_brackets.rb
require ‘brackets.tab’
class BracketParser
def parse_str(str)
list_of_tokens = str.split(//).map { |x| [x, x] }
list_of_tokens << [false, false]
yyparse(list_of_tokens, :each)
end
end

parser = BracketParser.new
ARGF.each do |line|
line = line.chomp
begin
parser.parse_str(line)
puts line
rescue Racc::ParseError
exit(1)
end
end

#!/usr/bin/env ruby

Yes, the lexer class is probably overkill, but I had it sitting around

from

another project and code reuse is a good thing =)

I originally was going to tinker with this until the output ensured

that

each braket is immediately wrapped in a box by iteself, but I think

this is

proably good enough–this works for both of the example erroneous

inputs in

the quiz description–and it’s already getting pretty long.

require ‘strscan’

class Lexer
class << self
def add_rule(regex, token_type = nil, &block)
@rules ||= []
block ||= lambda { |match, token| [token, match] }
@rules << [ regex, token_type, block ]
end

def each_rule
  @rules.each do |rule|
    yield *rule
  end
end

end

def initialize(input)
@scanner = StringScanner.new(input)
@tokens = Array.new()
@error_context_length = 20
end

attr_accessor :error_context_length

def tokens()
until @scanner.eos?
@tokens << find_match()
end
@tokens.compact
end

def find_match()
self.class.each_rule do |regex, token, block|
if (@scanner.scan(regex)) then
return block.call(@scanner.matched, token)
end
end
raise Exception,
“Parse error:\n” +
‘Can not tokenize input near "’ +
@scanner.peek(@error_context_length) + ‘"’
end
end

class BoxLexer < Lexer
add_rule(/[[({]/, :begin_box)
add_rule(/[])}]/, :end_box)
add_rule(/b/i, :bracket)
end

class Parser
@@matching_symbol = {
‘(’ => ‘)’, ‘)’ => ‘(’,
‘[’ => ‘]’, ‘]’ => ‘[’,
‘{’ => ‘}’, ‘}’ => ‘{’
}

def initialize input
@tokens = BoxLexer.new(input).tokens
@stack = []
@corrected_stream = []
end

def parse
while @tokens.size > 0
@current_token = @tokens.shift
dispatch_event
end
if (@current_token[0] != :end_box)
notify “!Wrapping all parts in wood ‘{’”
@corrected_stream.unshift [:begin_box, ‘{’]
@corrected_stream << [:end_box, ‘}’]
end
end

attr_reader :corrected_stream

private

def notify mesg
print ’ ’ * @stack.length
puts mesg
end

def dispatch_event
case @current_token[0]
when :begin_box
begin_event
when :bracket
bracket_event
when :end_box
end_event
end
end

def begin_event
value = @current_token[1]
notify “Found begin box ‘#{value}’”
@stack.push value
@corrected_stream << @current_token
end

def bracket_event
notify “Found a bracket”
if (@tokens.length < 1) then
premature_end
else
if (@tokens[0][0] != :end_box) then
notify “! Bracket must be followed by an ending box”
fix = guess_best_fix
notify “! Attempting to fix by adding end box: ‘#{fix}’”
@tokens.unshift [:end_box, fix]
end
@corrected_stream << @current_token
end
end

def end_event
value = @current_token[1]
symbol = @@matching_symbol[@stack.pop]
notify “Found end box ‘#{value}’”
if (value != symbol) then
if symbol then
notify “! Bad match: Expecting closed ‘#{symbol}’ got
‘#{value}’”
notify “! Attempting to fix by adding ‘#{symbol}’”
@tokens.unshift @current_token
@corrected_stream << [:end_box, symbol]
else
premature_end
end
else
@corrected_stream << @current_token
end
end

def guess_best_fix
fix = @@matching_symbol[@stack[-1]]
if (!fix) then
notify “! Wow, we really screwed this one up.”
notify “! Use soft packaging ‘)’ because we are cheap ;-)”
fix = ‘)’
end
fix
end

def premature_end
value = @current_token[1]
new_sym = @@matching_symbol[value]
notify “! Premature end of box: found extra ‘#{value}’”
notify “! Attempting to fix by wrapping entire payload in
‘#{new_sym}’”
@corrected_stream.unshift [:begin_box, new_sym]
@corrected_stream << [:end_box, value]
end
end

if (ARGV.length < 1) then
$stderr.puts “Usage #{FILE} box_string”
exit
end

parser = Parser.new(ARGV[0])
parser.parse
puts parser.corrected_stream.collect{|t| t.last}.join(’’)

Here are my solutions for both choices.

=== Choice one ===

Determines whether a packing diagram is acceptable.

def good_diagram? packing_diagram

Ensure there is no packaging that surrounds no items: (()B)

return false if packing_diagram =~ /()|[]|{}/

Make an unfrozen copy of the original.

packing_diagram = packing_diagram.dup

Remove the items: (((B))(B)(B)) -> ((())()())

packing_diagram = packing_diagram.delete ‘B’

Repeatedly remove matching opening-closing neighbors: ((())()()) ->

(())
-> () ->
packing_diagram.gsub! /()|[]|{}/, ‘’ while packing_diagram =~
/()|[]|{}/

If everything was removed, the diagram was good.

packing_diagram.empty?
end

packing_diagram = ARGV.join ’ ’
exit 1 unless good_diagram? packing_diagram
puts packing_diagram
exit 0

=== Choice two ===

Repairs any errors. When repairing, this errs on the side of too much

packaging. To reduce excess packaging, don’t have errors.

It’s a bit ugly, but I don’t think I let any possible breakages

through.
If I did, please let me know.
MaxCleanTime = 5

This has optional damage prevention enhancements. Uncomment the

paragraphs with an “# (option)” header if you want an option.
def clean_diagram packing_diagram, start_time=Time.now.to_i, length=0,
best_so_far=[1.0/0.0, nil], recursion_so_far=false

If we’ve already lost, quit.

return nil if length >= best_so_far.first or Time.now.to_i -
start_time >
MaxCleanTime

unless recursion_so_far
# Do nothing if nothing is being packed.
return ‘’ unless packing_diagram =~ /B/

# Make an unfrozen copy of the original.
packing_diagram = packing_diagram.dup

# Remove extraneous characters: (**Chunky bacon B ) -> (B)
packing_diagram.gsub! /[^B\(\)\[\]\{\}]/, ''

# Remove packing that surrounds no items: (()B) -> (B)
packing_diagram.gsub! /^[\)\]\}]|[\(\[\{][\)\]\}]|[\(\[\{]$/, '' 

while
packing_diagram =~ /^[)]}]|[([{][)]}]|[([{]$/

# Get the length.
length = packing_diagram.length

# Mark items as properly nested.
packing_diagram.gsub! /B/, 'Bm'

end

Mark all properly nested packaging.

while packing_diagram =~
/((([^m]m))|[([^m]m)]|{([^m]m)})([^m]|$)/
packing_diagram.gsub! /(((?:[^m]m)
))([^m]|$)/, ‘(m\1)m\2’
packing_diagram.gsub! /[((?:[^m]m))]([^m]|$)/, ‘[m\1]m\2’
packing_diagram.gsub! /{((?:[^m]m)
)}([^m]|$)/, ‘{m\1}m\2’
end

If we have improper nesting :

if packing_diagram !~ /^([^m]m)+$/
# If we have an opener with an improper closer: (B] :
if (mismatch = /([([{])(?:[^m]m)*([)]}])(?:[^m]|$)/.match
packing_diagram)
# Fix improper nestings in two different ways: by duplicating the
opening packaging and by duplicating the closing packaging.
clean_diagram(packing_diagram.dup.insert(mismatch.begin(2), { ‘(’
=>
‘)’, ‘[’ => ‘]’, ‘{’ => ‘}’ }[mismatch[1]]), start_time, length + 1,
best_so_far, true)
clean_diagram(packing_diagram.dup.insert(mismatch.begin(1) + 1, {
‘)’
=> ‘(’, ‘]’ => ‘[’, ‘}’ => ‘{’ }[mismatch[2]]), start_time, length + 1,
best_so_far, true)
packing_diagram = nil

# If we have an opener without even an improper closer or vice 

versa:
(B))(B) :
else
# If an unmarked opener falls off the right end :
if (mismatch = /([([{])(?:[^m]m)*$/.match packing_diagram)
packing_diagram << { ‘(’ => ‘)’, ‘[’ => ‘]’, ‘{’ => ‘}’
}[mismatch[1]]

  # If an unmarked opener slams into an unmarked opener :
  elsif (mismatch = /([\(\[\{])(?:[^m]m)*([\(\[\{])(?:[^m]|$)/.match

packing_diagram)
packing_diagram.insert(mismatch.begin(2), { ‘(’ => ‘)’, ‘[’ =>
‘]’,
‘{’ => ‘}’ }[mismatch[1]])

  # If an unmarked closer falls off the left end :
  elsif (mismatch = /^(?:[^m]m)*([\)\]\}])(?:[^m]|$)/.match

packing_diagram)
packing_diagram.insert(0, { ‘)’ => ‘(’, ‘]’ => ‘[’, ‘}’ => ‘{’
}[mismatch[1]])

  # If an unmarked closer slams into an unmarked closer :
  elsif (mismatch = /([\)\]\}])(?:[^m]m)*([\)\]\}])(?:[^m]|$)/.match

packing_diagram)
packing_diagram.insert(mismatch.begin(1) + 1, { ‘)’ => ‘(’, ‘]’
=>
‘[’, ‘}’ => ‘{’ }[mismatch[2]])
end

  clean_diagram packing_diagram, start_time, length + 1, 

best_so_far,
true
packing_diagram = nil
end

If we have proper nesting :

else
# Remove markings.
packing_diagram.delete! ‘m’

# (option) Ensure no items are left outside any packaging: B(BBB) ->

(B(BBB))
#~ packing_diagram.sub! /^(B.*|.*B)$/, ‘(\1)’

# (option) Ensure no item touches another item: (BBB) -> (B(B)B)
#~ packing_diagram.gsub! /BB/, 'B(B)' while packing_diagram =~ /BB/

# (option) Ensure all items are individually wrapped: ((B)B) -> 

((B)(B))
#~ packing_diagram.gsub! /(^|[B\)\]}])B/, ‘\1(B)’ while
packing_diagram
=~ /(^|[B\)\]}])B/
#~ packing_diagram.gsub! /B([B\(\[\{]|$)/, ‘(B)\1’ while
packing_diagram
=~ /B([B\(\[\{]|$)/
end

Update best_so_far.

best_so_far.replace [packing_diagram.length, packing_diagram] if
packing_diagram.length < best_so_far.first unless packing_diagram.nil?

best_so_far.last
end

Choice two

puts clean_diagram(ARGV.join(’ '))

Here’s a simple solution to the first part. This follows the assumption
laid out the machine drops one (and only one) bracket. Also assumes
input is a command line argument or comes from standard input.

desc = ARGV[0] || $stdin.gets.chomp
exit 1 if ((desc.scan(/[[]{}()]/).length % 2) == 1)
puts desc

This is the very first time I’ve participated in the ruby quiz…I was
very excited about it, and was absurdly pleased with myself when I got
a working program.

Then I saw the other solutions. My code is like 6x longer than
everyone else’s. It’s kind of depressing.

A lot of the code in my class is messy - I’d really like to learn how
to make it work better. Despite that, it provides a decent interface.
You can either just pass in the string to create an item, or do stuff
like
SoftWrap.new.wrap(Bracket.new)

It’d be really easy to implement a slick DSL with it, but I ended up
not doing so because it just didn’t really matter. The capability is
there though :slight_smile:

Anyway here’s my solution. As I said, I’d love it if anyone could
give me hints on making the implementation cleaner.

require “enumerator”

class Item
@balance_left = {}
@balance_right = {}
@descriptors = []

attr_reader :parent

def self.create(description, parent = nil)
product, remainder = split_product(description)
return nil if product.nil?
if(product.length == 1)
item = create_item(product, parent)
elsif product.length == 2
return nil
else
item = create_item(product, parent)
child = create(product[1…-1], item)
item.wrap(child) unless child.nil?
if item.empty? && !item.leaf?
return nil
end
if !remainder.empty? && item.root?
return nil
end
unless remainder.empty? || item.root?
sibling = create(remainder, item)
item.parent.wrap(sibling)
end
end
return item
end

def self.descriptor(d = nil)
unless d.nil?
@descriptor = d
Item.balance(descriptor[0].chr, descriptor[1].chr) if
@descriptor.size == 2
end
@descriptor
end

def self.regex
descriptor.length == 2 ?
“^\#{descriptor[0].chr}(.*)\#{descriptor[1].chr}$” : descriptor
end

def initialize(parent = nil)
@items = []
@parent = parent
end

def leaf?
false
end

def empty?
@items.empty?
end

def wrap(i)
i.parent = self
@items << i
self
end

def parent=§
@parent = p
end

def root?
@parent.nil?
end

def descriptor
self.class.descriptor
end

def description
unless @items.empty?
desc = [descriptor[0].chr]
@items.reverse.each { |i| desc << i.description }
desc << descriptor[1].chr
desc.flatten.join
else
descriptor
end
end

descriptor ‘’

protected

def self.split_product(description)
index = 0
elements = []
description.split(/\s*/).each_with_index do |c, index|
if @descriptors.include
if @balance_left.include
elements.push©
elsif @balance_right.include
if elements.last == @balance_right[c]
elements.pop
elsif elements.size == 0
elements.push©
end
end
break if elements.size == 0
end
end

if elements.size == 0
  return description[0..index], description[index+1..-1]
else
  return nil
end

end

def self.balance(first_char, second_char)
@balance_left[first_char] = second_char
@balance_right[second_char] = first_char
@descriptors << first_char unless @descriptors.include?(first_char)
@descriptors << second_char unless
@descriptors.include?(second_char)
end

def self.create_item(string, parent = nil)
ObjectSpace.enum_for(:each_object, class << Item; self;
end).to_a.each do |klass|
next if klass == self
r = Regexp.new(klass.regex)
return klass.new(parent) if r.match(string)
end
nil
end
end

class Bracket < Item
descriptor “B”

def wrap(i)
raise “Brackets ain’t got no flow”
end

def leaf?
true
end
end

class SoftWrap < Item
descriptor “()”
end

class WoodBox < Item
descriptor “{}”
end

class CardboardBox < Item
descriptor “[]”
end

pkg_desc = ARGV[0]
package = Item.create(pkg_desc)
exit(1) if package.nil?
puts package.description

#!/usr/bin/env ruby

=begin rdoc

In order to correct a possibly ill-formed string, the syntactic tree
is constructed starting from the leaves. Well-formed parts of the tree
are inlined in the string, marked by < and >. At the beginning, only
the leaves are marked:

Bracketing["[(B)(B)]"]

=> “[()()]”

Then, the tree is grown from the leaves:

Bracketing["[(B)(B)]"].grow_tree

=> “<[(B)(B)]>”

If the initial string is well-formed the inlined tree includes the
whole string, as in the case above. If the string is ill-formed, then
more than one tree fragmens are left:

Bracketing[’[{(B){(B)(B)}]’].grow_tree

=> “[{<(B)><{(B)(B)}>]”

Bracketing#fix_tree tries to add the missing bracket so that the
subtrees can be successfully merged:

Bracketing[’[{(B){(B)(B)}]’].grow_tree.fix_tree

=> “<[{(B)}{(B)(B)}]>”

Bracketing#balance wraps the whole thing up, returning a well-formed
string if the input string was successfully balanced and nil
otherwise.

Bracketing[’[{(B){(B)(B)}]’].balance

=> “[{(B)}{(B)(B)}]”

Invoking the program with the --test switch runs the test-suite. Else,
the first line of the input is parsed and possibly corrected. The exit
status is set in accordance with the success of the operation.

=end

Bracketing extends a string in the “bracket language” with inlined

syntax tree, enclosed in “<” and “>”

class Bracketing < String

Replace each open bracket in a string with its closed equivalent.

def close(string)
string.tr(’([{’,’)]}’)
end

Replace each closed bracket in a string with its open equivalent.

def open(string)
string.tr(’)]}’,’([{’)
end

Construct a Bracketing object with marked leaves.

def self.
new(string.gsub(/B/,’’))
end

Expand the branches from the leaves.

def grow_tree
s = self
while (z = s.
gsub(/(<((?:[^>]|><))>)/) { “<(#{$1.gsub(’><’,’’)})>”}.
gsub(/[<((?:[^>]|><)
)>]/) { “<[#{$1.gsub(’><’,’’)}]>”}.
gsub(/{<((?:[^>]|><)*)>}/) { “<{#{$1.gsub(’><’,’’)}}>”}
) != s
s = z
end
z
end

Find all possible corrections to an unbalanced Bracketing object

and select the one with lowest complexity.

def fix_tree
fixes = []
scan(/<[^>]>/) {
l,m,r = $`,$&,$’
a, b = l.gsub(/<[^>]
>/,’’), r.gsub(/<[^>]*>/,’’)
if close(a + open(b[0,1]||’’)).reverse == b
fixes << self.class.new(l + open(b[0,1]) + m + r).grow_tree
end
if a == open(close(a[-1,1]||’’) + b).reverse
fixes << self.class.new(l + m + close(a[-1,1]) + r).grow_tree
end
}
fixes.reject{|x| x[’><’]}.sort_by{|x| x.complexity}.first || self
end

The complexity is proportional to the variance of the depth over

the leaves in the syntactic tree.

def complexity
current, data = 0, []
scan(/./) {|c|
current += 1 if “{[(”[c]
current -= 1 if “}])”[c]
data << current if c==“B”
}
mean = data.inject{|a,x| a+x} / data.size().to_f
data.inject(0){|a,x| a + (x-mean) ** 2}
end

Return a balanced string or nil if self cannot be balanced.

def balance
z = grow_tree
while true
return $1 if z =~ /^<([^>]*)>$/
s = z
z = s.fix_tree
return nil if z == s
end
end

end

require ‘test/unit’

class Bracketing::Test < Test::Unit::TestCase

def test_construction
assert_equal ‘[{(}{()()}]’, Bracketing[’[{(B}{(B)(B)}]’]
end

def test_grow_tree
assert_equal ‘<{B}><(B)><[B]>’, Bracketing[’{B}(B)[B]’].grow_tree
assert_equal ‘<[{(B)}{(B)(B)}]>’,
Bracketing[’[{(B)}{(B)(B)}]’].grow_tree
assert_equal ‘<{(B)}><{(B)(B)}>]’,
Bracketing[’{(B)}{(B)(B)}]’].grow_tree
assert_equal ‘[<{(B)}>{(<(B)>}]’,
Bracketing[’[{(B)}{(B(B)}]’].grow_tree
end

def test_balance
ref = ‘[{(B)}{(B)(B)}]’
assert_equal ref, Bracketing[’[{(B)}{(B)(B)}]’].balance
assert_equal ref, Bracketing[’{(B)}{(B)(B)}]’].balance
assert_equal ref, Bracketing[’[(B)}{(B)(B)}]’].balance
assert_equal ref, Bracketing[’[{B)}{(B)(B)}]’].balance
assert_equal ref, Bracketing[’[{(B}{(B)(B)}]’].balance
assert_equal ref, Bracketing[’[{(B){(B)(B)}]’].balance
assert_equal ref, Bracketing[’[{(B)}(B)(B)}]’].balance
assert_equal ref, Bracketing[’[{(B)}{B)(B)}]’].balance
assert_equal ref, Bracketing[’[{(B)}{(B(B)}]’].balance
assert_equal ref, Bracketing[’[{(B)}{(B)B)}]’].balance
assert_equal ref, Bracketing[’[{(B)}{(B)(B}]’].balance
assert_equal ref, Bracketing[’[{(B)}{(B)(B)]’].balance
assert_equal ref, Bracketing[’[{(B)}{(B)(B)}’].balance
assert_equal nil, Bracketing[’(B)}{(B)(B)}]’].balance
end

end

Test::Unit.run = true
if FILE == $0
if ARGV[0] == ‘–test’
ARGV.pop
Test::Unit.run = false
elsif out = Bracketing[gets.chomp].balance
puts out
exit 0
else
exit 1
end
end

#!/usr/bin/ruby -w

Author: Shane E.

Bracket Packing (#78)

This is a pretty simple solution. I didn’t want to be

to complicated on the English translation, so instead

of describing the packaging, I wrote out the instructions

to manually pack the bracket(s). Thanks for a fun quiz!

class PackagingValidator

PACKAGING_DESC = { '[' => "Insert a cardboard box.\n",
                   '{' => "Insert a wooden box.\n",
                   '(' => "Insert some soft wrapping.\n",
                   ']' => "Close the cardboard box.\n",
                   '}' => "Close the wooden box.\n",
                   ')' => "Seal the soft wrapping.\n",
                   'B' => "Insert a brace.\n" }

def initialize( packaging )
    @packaging = packaging
end

def validate
    packaging_stack, brace_found = Array.new, false
    instruction_text = ''
    @packaging.split(//).each do |piece|
        case piece
        when '[', '{', '('
            brace_found = false
            packaging_stack.push(piece)
        when ']', '}', ')'
            return 1 unless brace_found
            return 1 if piece.eql?(']') and
                        not packaging_stack[-1].eql?('[')
            return 1 if piece.eql?('}') and
                        not packaging_stack[-1].eql?('{')
            return 1 if piece.eql?(')') and
                        not packaging_stack[-1].eql?('(')
            packaging_stack.pop
        when 'B'
            return 1 if packaging_stack.empty?
            brace_found = true
        else
            return 1
        end
        instruction_text << PACKAGING_DESC[piece]
    end
    return 1 unless brace_found and
                    packaging_stack.empty?
    print instruction_text.sub(/^Insert/, 'Start with')
    return 0
end

end

if $0 == FILE
print PackagingValidator.new(’[{(B)}{(B)(B)}]’).validate, “\n”
end

Guys,

Just had to say, I’m seriously impressed by all these solutions so
far :slight_smile: There appear to be more ways to approach this than I ever
imagined…