Re: Bracket Packing (#78)

stuart_holden · May 9, 2006, 1:24am

Here is my attempt. Go easy… my first quiz entry, and my first Ruby
script.

Regards,
Stu

class Packaging
attr_accessor :opening, :closing, :description

def initialize (o,c,desc)
@opening = o
@closing = c
@description = desc
end

def opp(v)
(v==@opening) ? @closing: @opening
end

def opening?(v)
@opening==v
end

def closing?(v)
@closing==v
end

def consistsOf?(v)
opening?(v) || closing?(v)
end
end

class PackagingPreProcessor
attr_accessor :packagingTypes

def initialize()
@types=[]
end

def addPackaging(p)
@types << p
end

def opening?(c)
@types.detect { |p| p.opening?(c) }
end

def closing?(c)
@types.detect { |p| p.closing?(c) }
end

def getPackagingType(c)
@types.detect { |p| p.consistsOf?(c) }
end

def processMessage(msg)
msg.final = msg.original
openStack=[]

aMsg=msg.original.split(//)

#Scan character by character for unbalanced brackets
aMsg.each_with_index do |c,i|

  # Push opening packaging type onto the stack
  if opening?(c)
    type=getPackagingType(c)
    openStack.push(type)
  end

  # Ensure closing brackets match the last opening bracket
  if closing?(c)

    currentPackagingTag=getPackagingType(c)

    expectedPackaging=openStack.pop

    if (expectedPackaging==nil)
      # We weren't expecting a close tag here.
      #
      #   Eg, {(B)(B)}]
      #               ^---- We a missing an opener for this
      #

      msg.final=currentPackagingTag.opening + msg.original
      return
    end

    if (currentPackagingTag != expectedPackaging)
      #
      # We have run into the wrong closing position,
      #
      # Two cases:
      #     We failed to open this position, eg : [B)], in which

case we will have a mismatch of ‘current’ brackets
# or
# There had been a subsequent position opened that needs
to be closed first - eg, [{B] - mismatch of expected brackets
#

      if (aMsg.select { |c| expectedPackaging.consistsOf?(c)

}.length % 2 != 0)
# need to insert the end braket of the expected packaging
msg.final=msg.original[0…(i-1)] + expectedPackaging.closing

msg.original[i…-1]
return
else
# Insert an opening bracket to match the current closing
bracket.
msg.final = msg.original[0…(i-1)] +
currentPackagingTag.opening + msg.original[i…-1]
return
end
end
end
end

if openStack.length!=0
# Still have unclosed outer brackets (not picked up during stack
matching)
# EG, [{B}
msg.final=msg.original + openStack.pop.closing
return
end

end
end

class Message
attr_reader :original
attr_accessor :final

def initialize(msg)
@original = msg
end

def valid?
@original==@final
end
end

#--------------------------

ppp=PackagingPreProcessor.new()

ppp.addPackaging(Packaging.new(“(”,“)”,“Soft Wrapping”))
ppp.addPackaging(Packaging.new(“[”,“]”,“Cardboard Box”))
ppp.addPackaging(Packaging.new(“{”,“}”,“Wooden Box”))

ARGF.each do |line|
msg=Message.new(line.chomp)
ppp.processMessage(msg)
print “\n”
print(msg.final)
print “\n”
end

This Email may contain confidential and privileged information and is intended for the use of the addressee(s) only. If you are not the intended recipient please notify the sender and delete the Email from your system. It should not be transmitted to any other person without the consent of the sender. Additional important notifications regarding Email transmissions from and to members of Baring Asset Management can be accessed at http://www.barings.com/email/index.hcst

stuart_holden · May 9, 2006, 1:26pm

This is great I enjoyed doing the quiz, and tried out a couple of
approaches: the stack based one (which seemed much more complex, and
even then didn’t cover all the cases), and this substitution on. Solving
the quiz was fun, but I picked up a lot of little things I didn’t know
along the way (either by bumping in to them, or looking at other
people’s solutions):

The pattern match variables $` and $’.
That you can use any start and end charater to deliminate a %w array
literal (or any of the related literals).
Having a test case in a script.
That the ruby command can be given params for the script itself.

Thank you community

Cheers,
Benjohn

module SubValidator
module_function

def is_valid(s)
validate(s) rescue nil
end

def validate(s)
# Replace basic brackets in (valid) packaging, with packages.
s = s.gsub(/(B)|{B}|[B]/, ‘P’)

# Until the string is reduced to a single package...
while(s!='P')
  # Replace one of more packages in (valid) packing, with a single

package.
s, old_s = s.gsub(/(P+)|{P+}|[P+]/, ‘P’), s

  raise "Couldn't find any packages to package in '#{s}'." if

s==old_s
end
true
end
end

require ‘test/unit’

class BracketTest < Test::Unit::TestCase
def test_validators
[SubValidator].each {|v| check_validator(v)}
end

def check_validator( validator )
# Simple cases that should pass.
valid_strings = %w<(B) {B} [B] ((B)) {(B)} ([{B}]) ((B)(B))
((((B)(B))(B))(B))>
valid_strings.each do |s|
assert_nothing_raised { validator.validate(s) }
end

# Simple cases that should fail.
invalid_strings = %w<() (b) [ B [B [} [B} } {{{{[B]}}} {{{{[B}}}

((B)B)> << ‘’
invalid_strings.each do |s|
assert_raises(RuntimeError) { validator.validate(s) }
end

# Try out a complex string - it should validate.
ok = "[({B}[B](B)[(B){[B][(B)]}]{B}{B})((B))]"
assert_nothing_raised{ validator.validate ok }

# Try dropping any of the chars - it should fail to vaildate.
ok.scan(/./) { assert_raises(RuntimeError) { validator.validate( $`

$’ ) } }

Try adding any of the vaild chars at any point - it should fail to

validate.
%w<B ( ) { } [ ]>.each do |c|
ok.scan(//) { assert_raises(RuntimeError) { validator.validate( $`

c + $’ ) } }
end
end

def test_is_valid
assert_not_nil( SubValidator::is_valid( ‘(B)’ ) )
assert_nil( SubValidator::is_valid( ‘’ ) )
end
end

if FILE == $0
if( ARGV[0] != ‘-t’ )
Test::Unit.run = false
exit( SubValidator::is_valid( ARGV[0] ) ? 0 : 1 )
else
ARGV.pop
end
end

stuart_holden · May 9, 2006, 2:20pm

I’ve done a little refactor because I didn’t like the inline regular
expressions.

Which makes me think that it’d be nice to have some extra methods in
Regexp that let you customise the special characters that it uses,
perhaps.

module SubValidator
module_function

def is_valid(s)
validate(s) rescue nil
end

def validate(s)
# Replace basic brackets in (valid) packaging, with packages.
s = s.gsub( packages_containing(‘B’), ‘P’ )

# Until the string is reduced to a single package...
while(s!='P')
  # Replace one of more packages in (valid) packing, with a single

package.
s, old_s = s.gsub( packages_containing(‘P+’), ‘P’ ), s

  raise "Couldn't find any packages to package in '#{s}'." if

s==old_s
end
true
end

def packages_containing(filler_pattern)
Regexp.new( packings.map {|p| Regexp.escape§.gsub(‘x’,
filler_pattern)}.join(’|’) )
end

def packings
%w<(x) {x} [x]>
end
end