[QUIZ] Bracket Packing (#78)

[James_Edward_Gray_II]

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

···

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

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.

[Gautam_Dey1 (Gautam Dey)]

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 May 5, 2006, at 4:46 AM, Ruby Quiz wrote:

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

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

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.

[Pat_Maddox1 (Pat Maddox)]

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 5/5/06, Ruby Quiz <james@grayproductions.net> wrote:

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

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

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.

[Sander_Land]

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

[Alexandru_E_Ungur]

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 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(c)).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

[Roy_Sutton]

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

[C_Erler]

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(' '))

[Stefano_Taschini]

#!/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)]"]
   # => "[(<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.[](string)
    new(string.gsub(/B/,'<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 =\~ /^&lt;\(\[^&gt;\]\*\)&gt;/
      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 '[{(<B>}{(<B>)(<B>)}]', 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><(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

fixbrackets.rb (4.75 KB)

[Shane_Emmons1 (Shane Emmons)]

#!/usr/bin/ruby -w

# Author: Shane Emmons

···

#
# 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

--
Posted via http://www.ruby-forum.com/.

[James_Edward_Gray_II]

Here's my solution for checking outputs.

James Edward Gray II

#!/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

[Francisco_Ortiz]

Here's my ruby n00b solution, I intended to fix erroneous strings, but I may
not have the time, so i'll leave it at reporting the error.

78.balance_strings_otro.rb (945 Bytes)

[Ross_Bamford4 (Ross Bamford)]

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 Fri, 2006-05-05 at 22:18 +0900, Gautam Dey wrote:

--
Ross Bamford - rosco@roscopeco.REMOVE.co.uk

[Gautam_Dey1 (Gautam Dey)]

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 May 6, 2006, at 2:52 PM, Pat Maddox wrote:

On 5/5/06, Ruby Quiz <james@grayproductions.net> wrote:

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

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

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.

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

[Kerry_Buckley]

This is my first attempt at the Ruby Quiz, 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?(c)
     # Add expected corresponding bracket to a stack
     closers.push(Brackets[c])
   elsif Brackets.has_value?(c)
     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?(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

# 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

@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

[Pat_Maddox1 (Pat Maddox)]

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

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=(p)
    @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?(c)
        if @balance_left.include?(c)
          elements.push(c)
        elsif @balance_right.include?(c)
          if elements.last == @balance_right[c]
            elements.pop
          elsif elements.size == 0
            elements.push(c)
          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

[Ross_Bamford4 (Ross Bamford)]

Guys,

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

···

--
Ross Bamford - rosco@roscopeco.REMOVE.co.uk

[Logan_Capaldo]

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

···

On May 6, 2006, at 6:46 PM, Gautam Dey wrote:

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

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.

[Lou_Scoras]

#!/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('')

[Gautam_Dey1 (Gautam Dey)]

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

···

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

On May 6, 2006, at 6:46 PM, Gautam Dey wrote:

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

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?

[Logan_Capaldo]

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