From: Stuart Holden Date: 2006-05-09T21:01:53+09:00 Subject: Re: [QUIZ] Bracket Packing (#78) ------_=_NextPart_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... =09 [B] -> [B] (valid=3Dtrue) [[B] -> [[B]] (valid=3Dfalse) [B]] -> [[B]] (valid=3Dfalse) [(B)] -> [(B)] (valid=3Dtrue) [(B] -> [(B)] (valid=3Dfalse) [B)] -> [(B)] (valid=3Dfalse) [([B])}] -> [{([B])}] (valid=3Dfalse) [{([B])] -> [{([B])}] (valid=3Dfalse) [(B)(B)(B)}] -> [{(B)(B)(B)}] (valid=3Dfalse) [(B){(B)(B)({B})] -> [(B){(B)(B)({B})}] (valid=3Dfalse) [(B)(B)(B)({B}})] -> [(B)(B)(B)({{B}})] (valid=3Dfalse) [(B)(B)(B)}({B})] -> [{(B)(B)(B)}({B})] (valid=3Dfalse) Regards, Stu -----Original Message----- From: Stuart Holden=20 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

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

------_=_NextPart_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= ------_=_NextPart_001_01C67360.3C89C50B--