------ art_791_26491914.1125393948095 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Here is mine. Nothing special, except that I used Dijkstra algorithm from the graph library (http://raa.ruby-lang.org/project/graph/). Looking at the library source, I noticed that it doesn't use a priority queue, hence it could be easily made faster by using Brian Schröäer's. --- Paolo ------ art_791_26491914.1125393948095 Content-Type: application/octet-stream; name="chain.rb" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="chain.rb" cmVxdWlyZSAnZ3JhcGgnCgptb2R1bGUgV29yZENoYWlucwogIGV4dGVuZCBzZWxmCiAgCiAgY2xh c3MgV29yZEdyYXBoCiAgICBpbmNsdWRlIEdyYXBoCiAgICAKICAgIGRlZiBpbml0aWFsaXplKG4s IGRpY3RfZmlsZSkKICAgICAgQHNpemUgPSBuCiAgICAgIEBkaWN0ID0ge30KICAgICAgZGljdF9m aWxlLmVhY2hfbGluZSBkbyB8bGluZXwKICAgICAgICB3b3JkID0gbGluZS5jaG9tcAogICAgICAg IEBkaWN0W3dvcmRdID0gdHJ1ZSBpZiB3b3JkLnNpemUgPT0gQHNpemUKICAgICAgZW5kCiAgICBl bmQKICAgIAogICAgZGVmIHZhbGlkPyB3b3JkCiAgICAgIEBkaWN0W3dvcmRdCiAgICBlbmQKICAg IAogICAgZGVmIFtdKHcxLCB3MikKICAgICAgZGlmZiA9IGZhbHNlCiAgICAgIHcxLnNwbGl0KC8v KS5lYWNoX3dpdGhfaW5kZXggZG8gfGwsIGl8CiAgICAgICAgaWYgbCAhPSB3MltpLDFdCiAgICAg ICAgICByZXR1cm4gbmlsIGlmIGRpZmYKICAgICAgICAgIGRpZmYgPSB0cnVlCiAgICAgICAgZW5k CiAgICAgIGVuZAogICAgICAKICAgICAgaWYgZGlmZgogICAgICAgIDEKICAgICAgZW5kCiAgICBl bmQKICAgIAogICAgZGVmIGVhY2hfc3VjY2Vzc2luZ192ZXJ0ZXgod29yZCkKICAgICAgbW9kX3dv cmQgPSB3b3JkLmR1cAogICAgICB3b3JkLnNwbGl0KC8vKS5lYWNoX3dpdGhfaW5kZXggZG8gfGws IGl8CiAgICAgICAgKCdhJy4uJ3onKS5lYWNoIGRvIHxvdGhlcl9sZXR0ZXJ8CiAgICAgICAgICBu ZXh0IGlmIG90aGVyX2xldHRlciA9PSBsCiAgICAgICAgICBtb2Rfd29yZFtpLDFdID0gb3RoZXJf bGV0dGVyCiAgICAgICAgICB5aWVsZCBtb2Rfd29yZCBpZiBAZGljdFttb2Rfd29yZF0KICAgICAg ICBlbmQKICAgICAgICBtb2Rfd29yZFtpLDFdID0gbAogICAgICBlbmQKICAgIGVuZAogICAgCiAg ICBkZWYgZGlyZWN0ZWQ/CiAgICAgIGZhbHNlCiAgICBlbmQKICBlbmQKICAKICBkZWYgcHJpbnRf Y2hhaW4ocm9vdCwgdGFyZ2V0LCBkaWN0KQogICAgbiA9IHJvb3Quc2l6ZQogICAgZGllICJib3Ro IHdvcmRzIG11c3QgYmUgb2YgdGhlIHNhbWUgc2l6ZSIgaWYgbiAhPSB0YXJnZXQuc2l6ZQogICAg ICAKICAgIGcgPSBXb3JkR3JhcGgubmV3KG4sIEZpbGUubmV3KGRpY3QsICdyJykpCiAgICAKICAg IFtyb290LHRhcmdldF0uZWFjaCBkbyB8d29yZHwKICAgICAgZGllICIje3dvcmR9IGlzIG5vdCBh IGRpY3Rpb25hcnkgd29yZCIgdW5sZXNzIGcudmFsaWQ/IHdvcmQKICAgIGVuZAogICAgICAKICAg IHByZWQgPSB7fQogICAgcmVzID0gZy5kaWprc3RyYV9zaG9ydGVzdF9wYXRocyh7CiAgICAgIDpy b290ID0+IHJvb3QsCiAgICAgIDp0YXJnZXQgPT4gdGFyZ2V0LAogICAgICA6cHJlZGVjZXNzb3Ig PT4gcHJlZAogICAgfSkKICAgIAogICAgaWYgcmVzICAgIAogICAgICBwdXRzIGcucm91dGUodGFy Z2V0LCBwcmVkKQogICAgZWxzZQogICAgICBwdXRzICJubyBjaGFpbiBjb3VsZCBiZSBmb3VuZCIK ICAgIGVuZAogIGVuZAogIAogIGRlZiBkaWUobXNnKQogICAgd2FybiBtc2cKICAgIGV4aXQgMQog IGVuZAogIAogIGRlZiB1c2FnZQogICAgZGllICJVc2FnZTogcnVieSAjJDAgU1RBUlRfV09SRCBF TkRfV09SRCBbLWQgRElDVElPTkFSWV0iCiAgZW5kCiAgCiAgZGVmIHJ1bgogICAgYXJncyA9IFtd CiAgICBkaWN0ID0gJy91c3Ivc2hhcmUvZGljdC93b3JkcycKICAgIHdoaWxlIGFyZyA9IEFSR1Yu c2hpZnQKICAgICAgaWYgYXJnID09ICctZCcKICAgICAgICBkaWN0ID0gQVJHVi5zaGlmdCBvciB1 c2FnZQogICAgICBlbHNlCiAgICAgICAgYXJncyA8PCBhcmcKICAgICAgZW5kCiAgICBlbmQKICAg ICAgICAKICAgIHVzYWdlIGlmIGFyZ3Muc2l6ZSAhPSAyCiAgICBwcmludF9jaGFpbihhcmdzWzBd LCBhcmdzWzFdLCBkaWN0KQogIGVuZAplbmQKCmlmICQwID09IF9fRklMRV9fCiAgV29yZENoYWlu cy5ydW4KZW5k ------ art_791_26491914.1125393948095--