------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--