------_extPart_001_01C67360.3C89C50B
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: quoted-printable

Hi,

I've refined my solution a little bit. It's now a bit smarter at
positioning missing opening brackets. The old version would misbehave
given...

	[([B])}] -> [([B]){}]

The new version produces...

	[([B])}] -> [{([B])}]

After spotting that we had a missing opening bracket, I was trying to
scan backwards to find the last unclosed occurrence of the next expected
bracket. This was getting a bit messy, then I spotted the technique used
by Ross to add the opening position to the stack along with the bracket
type - being a Ruby newbie I didn't think of pushing a tuple onto the
stack. Slotted that technique in there, and it seems to work a charm.

Some test results below...
	
[B] -> [B] (valid=true)
[[B] -> [[B]] (valid=false)
[B]] -> [[B]] (valid=false)
[(B)] -> [(B)] (valid=true)
[(B] -> [(B)] (valid=false)
[B)] -> [(B)] (valid=false)
[([B])}] -> [{([B])}] (valid=false)
[{([B])] -> [{([B])}] (valid=false)
[(B)(B)(B)}] -> [{(B)(B)(B)}] (valid=false)
[(B){(B)(B)({B})] -> [(B){(B)(B)({B})}] (valid=false)
[(B)(B)(B)({B}})] -> [(B)(B)(B)({{B}})] (valid=false)
[(B)(B)(B)}({B})] -> [{(B)(B)(B)}({B})] (valid=false)

Regards,
Stu

-----Original Message-----
From: Stuart Holden 
Sent: 09 May 2006 00:22
To: ruby-talk ML
Subject: Re: [QUIZ] Bracket Packing (#78)

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

Regards,
Stu



<snipped/>



<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 http://www.barings.com/email/index.hcst</font></p></body>
</p>
</font>
</blockquote>

<p>&nbsp;</p>
</body>
</html>


------_extPart_001_01C67360.3C89C50B
Content-Type: application/octet-stream; name="packer.rb"
Content-Transfer-Encoding: base64
Content-Description: packer.rb
Content-Disposition: attachment; filename="packer.rb"

Y2xhc3MgUGFja2FnaW5nDQogIGF0dHJfYWNjZXNzb3IgOm9wZW5pbmcsIDpjbG9zaW5nLCA6ZGVz
Y3JpcHRpb24NCiAgDQogIGRlZiBpbml0aWFsaXplIChvLGMsZGVzYykNCiAgICBAb3BlbmluZyA9
IG8NCiAgICBAY2xvc2luZyA9IGMNCiAgICBAZGVzY3JpcHRpb24gPSBkZXNjDQogIGVuZA0KICAN
CiAgZGVmIG9wcCh2KQ0KICAgICh2PT1Ab3BlbmluZykgPyBAY2xvc2luZzogQG9wZW5pbmcNCiAg
ZW5kDQogIA0KICBkZWYgb3BlbmluZz8odikNCiAgICBAb3BlbmluZz09dg0KICBlbmQNCiAgDQog
IGRlZiBjbG9zaW5nPyh2KQ0KICAgIEBjbG9zaW5nPT12DQogIGVuZA0KICANCiAgZGVmIGNvbnNp
c3RzT2Y/KHYpDQogICAgb3BlbmluZz8odikgfHwgY2xvc2luZz8odikNCiAgZW5kDQplbmQgICAg
DQoNCg0KDQpjbGFzcyBQYWNrYWdpbmdQcmVQcm9jZXNzb3INCiAgYXR0cl9hY2Nlc3NvciA6cGFj
a2FnaW5nVHlwZXMNCiAgDQogIGRlZiBpbml0aWFsaXplKCkNCiAgICBAdHlwZXM9W10NCiAgZW5k
DQogIA0KICBkZWYgYWRkUGFja2FnaW5nKHApDQogICAgQHR5cGVzIDw8IHANCiAgZW5kDQogIA0K
ICBkZWYgb3BlbmluZz8oYykNCiAgICBAdHlwZXMuZGV0ZWN0IHsgfHB8IHAub3BlbmluZz8oYykg
fQ0KICBlbmQNCiAgDQogIGRlZiBjbG9zaW5nPyhjKQ0KICAgIEB0eXBlcy5kZXRlY3QgeyB8cHwg
cC5jbG9zaW5nPyhjKSB9DQogIGVuZA0KICANCiAgZGVmIGdldFBhY2thZ2luZ1R5cGUoYykNCiAg
ICBAdHlwZXMuZGV0ZWN0IHsgfHB8IHAuY29uc2lzdHNPZj8oYykgfQ0KICBlbmQNCiAgDQogIGRl
ZiBwcm9jZXNzTWVzc2FnZShtc2cpICAgIA0KICBtc2cuZmluYWwgPSBtc2cub3JpZ2luYWwNCiAg
b3BlblN0YWNrPVtdDQogICAgDQogICAgYU1zZz1tc2cub3JpZ2luYWwuc3BsaXQoLy8pDQogICAg
DQogICAgI1NjYW4gY2hhcmFjdGVyIGJ5IGNoYXJhY3RlciBmb3IgdW5iYWxhbmNlZCBicmFja2V0
cw0KICAgIGFNc2cuZWFjaF93aXRoX2luZGV4IGRvIHxjLGl8DQoNCiAgICAgICMgUHVzaCBvcGVu
aW5nIHBhY2thZ2luZyB0eXBlIG9udG8gdGhlIHN0YWNrIGFsb25nIHdpdGggdGhlIGluZGV4DQog
ICAgICBpZiBvcGVuaW5nPyhjKQ0KICAgICAgICB0eXBlPWdldFBhY2thZ2luZ1R5cGUoYykNCiAg
ICAgICAgb3BlblN0YWNrLnB1c2goW3R5cGUsaV0pDQogICAgICBlbmQNCiAgICAgIA0KICAgICAg
IyBFbnN1cmUgY2xvc2luZyBicmFja2V0cyBtYXRjaCB0aGUgbGFzdCBvcGVuaW5nIGJyYWNrZXQN
CiAgICAgIGlmIGNsb3Npbmc/KGMpDQogICAgICAgIA0KICAgICAgICBjdXJyZW50UGFja2FnaW5n
VGFnPWdldFBhY2thZ2luZ1R5cGUoYykNCiAgICAgICAgDQogICAgICAgIChleHBlY3RlZFBhY2th
Z2luZyxpT3BlbmluZ1Bvcyk9b3BlblN0YWNrLnBvcCAgICAgICAgDQogICAgICAgICAgICAgICAg
DQogICAgICAgIGlmIChleHBlY3RlZFBhY2thZ2luZz09bmlsKQ0KICAgICAgICAgICMgV2Ugd2Vy
ZW4ndCBleHBlY3RpbmcgYSBjbG9zZSB0YWcgaGVyZS4NCiAgICAgICAgICAjDQogICAgICAgICAg
IyAgIEVnLCB7KEIpKEIpfV0NCiAgICAgICAgICAjICAgICAgICAgICAgICAgXi0tLS0gV2UgYSBt
aXNzaW5nIGFuIG9wZW5lciBmb3IgdGhpcyANCiAgICAgICAgICAjIA0KICAgICAgICAgIA0KICAg
ICAgICAgIG1zZy5maW5hbD1jdXJyZW50UGFja2FnaW5nVGFnLm9wZW5pbmcgKyBtc2cub3JpZ2lu
YWwNCiAgICAgICAgICByZXR1cm4NCiAgICAgICAgZW5kDQogICAgICAgIA0KICAgICAgICBpZiAo
Y3VycmVudFBhY2thZ2luZ1RhZyAhPSBleHBlY3RlZFBhY2thZ2luZykNCiAgICAgICAgICAjIA0K
ICAgICAgICAgICMgV2UgaGF2ZSBydW4gaW50byB0aGUgd3JvbmcgY2xvc2luZyBwb3NpdGlvbiwN
CiAgICAgICAgICAjDQogICAgICAgICAgIyBUd28gY2FzZXM6DQogICAgICAgICAgIyAgICAgV2Ug
ZmFpbGVkIHRvIG9wZW4gdGhpcyBwb3NpdGlvbiwgZWcgOiBbQildLCBpbiB3aGljaA0KICAgICAg
ICAgICMgICAgIGNhc2Ugd2Ugd2lsbCBoYXZlIGEgbWlzbWF0Y2ggb2YgJ2N1cnJlbnQnIGJyYWNr
ZXRzDQogICAgICAgICAgIyAgICAgb3INCiAgICAgICAgICAjICAgICBUaGVyZSBoYWQgYmVlbiBh
IHN1YnNlcXVlbnQgcG9zaXRpb24gb3BlbmVkIHRoYXQgbmVlZHMgdG8NCiAgICAgICAgICAjICAg
ICBiZSBjbG9zZWQgZmlyc3QgLSBlZywgW3tCXSAtIG1pc21hdGNoIG9mIGV4cGVjdGVkIGJyYWNr
ZXRzDQogICAgICAgICAgIw0KICAgICAgICAgIA0KICAgICAgICAgIGlmIChhTXNnLnNlbGVjdCB7
IHxjfCBleHBlY3RlZFBhY2thZ2luZy5jb25zaXN0c09mPyhjKSB9Lmxlbmd0aCAlIDIgIT0gMCkN
CiAgICAgICAgICAgICMgbmVlZCB0byBpbnNlcnQgdGhlIGVuZCBicmFrZXQgb2YgdGhlIGV4cGVj
dGVkIHBhY2thZ2luZw0KICAgICAgICAgICAgbXNnLmZpbmFsPW1zZy5vcmlnaW5hbFswLi4oaS0x
KV0gKyBleHBlY3RlZFBhY2thZ2luZy5jbG9zaW5nICsgbXNnLm9yaWdpbmFsW2kuLi0xXQ0KICAg
ICAgICAgICAgcmV0dXJuDQogICAgICAgICAgZWxzZQ0KICAgICAgICAgICAgIyBJbnNlcnQgYW4g
b3BlbmluZyBicmFja2V0IHRvIG1hdGNoIHRoZSBjdXJyZW50IGNsb3NpbmcgYnJhY2tldC4NCiAg
ICAgICAgICAgICMgSW5zZXJ0aW9uIHBvaW50IGlzIGRpcmVjdGx5IGFmdGVyIHdoZXJlIHRoZSBl
eHBlY3RlZCBicmFja2V0DQogICAgICAgICAgICAjIHdhcyBvcGVuZWQgICAgICAgICAgIA0KICAg
ICAgICAgICAgICAgICAgICAgICAgICAgIA0KICAgICAgICAgICAgbXNnLmZpbmFsID0gbXNnLm9y
aWdpbmFsWzAuLihpT3BlbmluZ1BvcyldICsgY3VycmVudFBhY2thZ2luZ1RhZy5vcGVuaW5nICsg
bXNnLm9yaWdpbmFsWyhpT3BlbmluZ1BvcysxKS4uLTFdDQogICAgICAgICAgICByZXR1cm4NCiAg
ICAgICAgICBlbmQgICAgICAgICAgICAgICAgICAgDQogICAgICAgIGVuZCAgICAgICAgICAgICAg
ICANCiAgICAgIGVuZCAgICAgIA0KICAgIGVuZA0KICAgIA0KICAgIGlmIG9wZW5TdGFjay5sZW5n
dGghPTANCiAgICAgICMgU3RpbGwgaGF2ZSB1bmNsb3NlZCBvdXRlciBicmFja2V0cyAobm90IHBp
Y2tlZCB1cCBkdXJpbmcgc3RhY2sgbWF0Y2hpbmcpDQogICAgICAjIEVHLCBbe0J9DQogICAgICAo
ZXhwZWN0ZWRQYWNrYWdpbmcsaU9wZW5pbmdQb3MpID0gb3BlblN0YWNrLnBvcA0KICAgICAgbXNn
LmZpbmFsPW1zZy5vcmlnaW5hbCArIGV4cGVjdGVkUGFja2FnaW5nLmNsb3NpbmcgICAgICANCiAg
ICAgIHJldHVybg0KICAgIGVuZA0KICAgIA0KICBlbmQNCmVuZA0KDQpjbGFzcyBNZXNzYWdlDQog
IGF0dHJfcmVhZGVyICAgOm9yaWdpbmFsDQogIGF0dHJfYWNjZXNzb3IgOmZpbmFsDQogIA0KICBk
ZWYgaW5pdGlhbGl6ZShtc2cpDQogICAgQG9yaWdpbmFsID0gbXNnDQogIGVuZA0KICANCiAgZGVm
IHZhbGlkPw0KICAgIEBvcmlnaW5hbD09QGZpbmFsDQogIGVuZA0KZW5kDQoNCg0KDQojLS0tLS0t
LS0tLS0tLS0tLS0tLS0tLS0tLS0NCg0KcHBwPVBhY2thZ2luZ1ByZVByb2Nlc3Nvci5uZXcoKQ0K
DQpwcHAuYWRkUGFja2FnaW5nKFBhY2thZ2luZy5uZXcoIigiLCIpIiwiU29mdCBXcmFwcGluZyIp
KQ0KcHBwLmFkZFBhY2thZ2luZyhQYWNrYWdpbmcubmV3KCJbIiwiXSIsIkNhcmRib2FyZCBCb3gi
KSkNCnBwcC5hZGRQYWNrYWdpbmcoUGFja2FnaW5nLm5ldygieyIsIn0iLCJXb29kZW4gQm94Iikp
DQoNCg0KQVJHRi5lYWNoIGRvIHxsaW5lfA0KICBtc2c9TWVzc2FnZS5uZXcobGluZS5jaG9tcCkN
CiAgcHBwLnByb2Nlc3NNZXNzYWdlKG1zZykNCiAgcHJpbnQobXNnLmZpbmFsKQ0KICANCiAgI3By
aW50ICIje21zZy5vcmlnaW5hbH0gLT4gI3ttc2cuZmluYWx9ICh2YWxpZD0je21zZy52YWxpZD99
KVxuIg0KDQplbmQNCg0KDQo-----_extPart_001_01C67360.3C89C50B--