Forum: Ruby Re: Bracket Packing (#78)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
89bb4a34f0294dfcea27af4ed6c98b07?d=identicon&s=25 Stuart Holden (Guest)
on 2006-05-09 01:24
(Received via mailing list)
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




<body>

<blockquote>
<font FACE="Arial,Arial" SIZE="1"><p ALIGN="JUSTIFY">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 <a
href="http://www.barings.com/email/index.hcst">http://ww...
</p>
</font>
</blockquote>

<p>&nbsp;</p>
</body>
</html>
Ffcb418e17cac2873d611c2b8d8d891c?d=identicon&s=25 unknown (Guest)
on 2006-05-09 13:26
(Received via mailing list)
:) 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
Ffcb418e17cac2873d611c2b8d8d891c?d=identicon&s=25 unknown (Guest)
on 2006-05-09 14:20
(Received via mailing list)
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(p).gsub('x',
filler_pattern)}.join('|') )
  end

  def packings
    %w<(x) {x} [x]>
  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
This topic is locked and can not be replied to.