--------------030201000309060301080308 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Bill Kelly wrote: > >> (Benchmark code is attached...) > > For completeness' sake, I've uploaded the benchmark script, plus > all the solutions... I had to tweak a few slightly to remove > printouts and such: > > http://tastyspleen.net/~billk/ruby/quiz/157-smallest-circle/benchmark/ Here's my code updated with the convex hull method from Philipp which doesn't change the result but gives a huge speedup in the most common cases. Lionel --------------030201000309060301080308 Content-Type: text/plain; name57_lionel_bouton.rb" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename57_lionel_bouton.rb" aW5jbHVkZSBNYXRoCgptb2R1bGUgQ29udmV4SHVsbAoKICAjIGFmdGVyIGdyYWhhbSAmIGFu ZHJldwogIGRlZiBzZWxmLmNvbnZleF9odWxsKHBvaW50cykKICAgIGxvcCA9IHBvaW50cy5z b3J0X2J5IHsgfHB8IHAueCB9CiAgICBsZWZ0ID0gbG9wLnNoaWZ0CiAgICByaWdodCA9IGxv cC5wb3AKICAgIGxvd2VyLCB1cHBlciA9IFtsZWZ0XSwgW2xlZnRdCiAgICBsb3dlcl9odWxs LCB1cHBlcl9odWxsID0gW10sIFtdCiAgICBkZXRfZnVuYyA9IGRldGVybWluYW50X2Z1bmN0 aW9uKGxlZnQsIHJpZ2h0KQogICAgdW50aWwgbG9wLmVtcHR5PwogICAgICBwID0gbG9wLnNo aWZ0CiAgICAgICggZGV0X2Z1bmMuY2FsbChwKSA8IDAgPyBsb3dlciA6IHVwcGVyICkgPDwg cAogICAgZW5kCiAgICBsb3dlciA8PCByaWdodAogICAgdW50aWwgbG93ZXIuZW1wdHk/CiAg ICAgIGxvd2VyX2h1bGwgPDwgbG93ZXIuc2hpZnQKICAgICAgd2hpbGUgKGxvd2VyX2h1bGwu c2l6ZSA+PSAzKSAmJgogICAgICAgICAgIWNvbnZleD8obG93ZXJfaHVsbC5sYXN0KDMpLCB0 cnVlKQogICAgICAgIGxhc3QgPSBsb3dlcl9odWxsLnBvcAogICAgICAgIGxvd2VyX2h1bGwu cG9wCiAgICAgICAgbG93ZXJfaHVsbCA8PCBsYXN0CiAgICAgIGVuZAogICAgZW5kCiAgICB1 cHBlciA8PCByaWdodAogICAgdW50aWwgdXBwZXIuZW1wdHk/CiAgICAgIHVwcGVyX2h1bGwg PDwgdXBwZXIuc2hpZnQKICAgICAgd2hpbGUgKHVwcGVyX2h1bGwuc2l6ZSA+PSAzKSAmJgog ICAgICAgICAgIWNvbnZleD8odXBwZXJfaHVsbC5sYXN0KDMpLCBmYWxzZSkKICAgICAgICBs YXN0ID0gdXBwZXJfaHVsbC5wb3AKICAgICAgICB1cHBlcl9odWxsLnBvcAogICAgICAgIHVw cGVyX2h1bGwgPDwgbGFzdAogICAgICBlbmQKICAgIGVuZAogICAgdXBwZXJfaHVsbC5zaGlm dAogICAgdXBwZXJfaHVsbC5wb3AKICAgIGxvd2VyX2h1bGwgKyB1cHBlcl9odWxsLnJldmVy c2UKICBlbmQKCiAgcHJpdmF0ZQoKICBkZWYgc2VsZi5kZXRlcm1pbmFudF9mdW5jdGlvbihw MCwgcDEpCiAgICBwcm9jIHsgfHB8ICgocDAueC1wMS54KSoocC55LXAxLnkpKS0oKHAueC1w MS54KSoocDAueS1wMS55KSkgfQogIGVuZAoKICBkZWYgc2VsZi5jb252ZXg/KGxpc3Rfb2Zf dGhyZWUsIGxvd2VyKQogICAgcDAsIHAxLCBwMiA9IGxpc3Rfb2ZfdGhyZWUKICAgIChkZXRl cm1pbmFudF9mdW5jdGlvbihwMCwgcDIpLmNhbGwocDEpID4gMCkgXiBsb3dlcgogIGVuZAoK ZW5kCgpjbGFzcyBQb2ludCA8IFN0cnVjdC5uZXcoOngsIDp5KQogIGRlZiBzZWxmLnJhbmRv bQogICAgUG9pbnQubmV3KHJhbmQsIHJhbmQpCiAgZW5kCgogIGRlZiBzZWxmLmdlbmVyYXRl X3NhbXBsZXMobikKICAgICgxLi5uKS5tYXAgeyBzZWxmLnJhbmRvbSB9CiAgZW5kCgogIGRl ZiB0b19zCiAgICAiKCN7eH0sICN7eX0pIgogIGVuZAplbmQKCmNsYXNzIFBvdGVudGlhbENl bnRlciA8IFN0cnVjdC5uZXcoOngsIDp5LCA6cG9pbnRzKQogIGluY2x1ZGUgTWF0aAoKICAj IFNxdWFyZSBkaXN0YW5jZSB3aXRoIGEgcG9pbnQKICBkZWYgc3F1YXJlX2Rpc3RhbmNlKHBv aW50KQogICAgKChwb2ludC54IC0geCkgKiogMikgKyAoKHBvaW50LnkgLSB5KSAqKiAyKQog IGVuZAoKICAjIE1heGltdW0gc3F1YXJlIGRpc3RhbmNlIHdpdGggbXkgcG9pbnRzCiAgIyBJ dCdzIGNhY2hlZCBiZWNhdXNlIGl0J3MgY2FsbGVkIHNldmVyYWwgdGltZXMgYW5kIGNhbiBi ZSB2ZXJ5IGNvc3RseQogIGRlZiBtYXhfc3F1YXJlX2Rpc3RhbmNlCiAgICBAc3FfZGlzdCB8 fD0gKHBvaW50cy5tYXAgeyB8cG9pbnR8IHNxdWFyZV9kaXN0YW5jZShwb2ludCkgfS5tYXgp CiAgZW5kCgogICMgQ29tcHV0ZSB0aGUgYmVzdCBtb3ZlIHdpdGggZ2l2ZW4gZGlzdGFuY2Ug KHJvKQogICMgYW5kIGFuZ2xlcyAodGhldGFzKQogICMgcmV0dXJucyBuaWwgaWYgbm9uZSBp cyBiZXR0ZXIgdGhhbiB0aGUgY3VycmVudCBwb3NpdGlvbgogIGRlZiBiZXN0X21vdmUocm8s IHRoZXRhcykKICAgIHBvdGVudGlhbF9tb3ZlcyA9IHRoZXRhcy5tYXAgeyB8dGhldGF8CiAg ICAgIG5ld194ID0geCArIChybyAqIGNvcyh0aGV0YSkpCiAgICAgIG5ld195ID0geSArIChy byAqIHNpbih0aGV0YSkpCiAgICAgIFBvdGVudGlhbENlbnRlci5uZXcobmV3X3gsbmV3X3ks cG9pbnRzKQogICAgfQogICAgY2hvb3NlX21vdmVfMShwb3RlbnRpYWxfbW92ZXMpCiAgZW5k CgogICMgRHVtYmVyLCBmYXN0ZXIKICBkZWYgY2hvb3NlX21vdmVfMShwb3RlbnRpYWxfbW92 ZXMpCiAgICBwb3RlbnRpYWxfbW92ZXMuZGV0ZWN0IHsgfG1vdmV8CiAgICAgIG1heF9zcXVh cmVfZGlzdGFuY2UgPiBtb3ZlLm1heF9zcXVhcmVfZGlzdGFuY2UKICAgIH0KICBlbmQKCiAg IyBMb29rIGZvciB0aGUgc2hvcnRlc3QgcGF0aCwgc2xvd2VyICh+MS40eCBvbiBhdmVyYWdl IHdpdGggbWFueSBwb2ludHMpCiAgZGVmIGNob29zZV9tb3ZlXzIocG90ZW50aWFsX21vdmVz KQogICAgcG90ZW50aWFsX21vdmVzLnJlamVjdCEgeyB8bW92ZXwKICAgICAgbWF4X3NxdWFy ZV9kaXN0YW5jZSA8PSBtb3ZlLm1heF9zcXVhcmVfZGlzdGFuY2UKICAgIH0KICAgIHBvdGVu dGlhbF9tb3Zlcy5taW4geyB8YzEsYzJ8CiAgICAgIGMxLm1heF9zcXVhcmVfZGlzdGFuY2Ug PD0+IGMyLm1heF9zcXVhcmVfZGlzdGFuY2UKICAgIH0KICBlbmQKCiAgIyBDaGVjayB0aGF0 IHRoZSBnaXZlbiBvZmZzZXQgaXMgYmlnIGVub3VnaCB0byBtb3ZlCiAgIyB0aGUgY3VycmVu dCBwb3NpdGlvbgogICMgKGZsb2F0aW5nIHBvaW50IHJvdW5kaW5nIGVycm9ycyBwcmV2ZW50 IGluZmluaXRlIHByZWNpc2lvbi4uLikKICBkZWYgY2FuX2JlX21vdmVkX2J5KG9mZnNldCkK ICAgICgoeCArIG9mZnNldCkgIT0geCkgfHwgKCh5ICsgb2Zmc2V0KSAhPSB5KQogIGVuZAoK ICBkZWYgdG9fcwogICAgIigje3h9LCAje3l9KSIKICBlbmQKZW5kCgpjbGFzcyBDaXJjbGUg PCBTdHJ1Y3QubmV3KDpjZW50ZXIsIDpyYWRpdXMpCiAgZGVmIHRvX3MKICAgICJ7Y2VudGVy OiN7Y2VudGVyfSwgcmFkaXVzOiN7cmFkaXVzfX0iCiAgZW5kCmVuZAoKZGVmIGNob3NlX29y aWdpbmFsX2NlbnRlcl9hbmRfbW92ZV9hbW91bnQocG9pbnRzKQogICMgU3RhcnQgd2l0aCBh IGdvb2QgcG90ZW50aWFsIChhcm91bmQgdGhlIG1pZGRsZSBvZiB0aGUgcG9pbnQgY2xvdWQp CiAgbWF4X3ggPSBwb2ludHMubWFwe3xwfCBwLnh9Lm1heAogIG1pbl94ID0gcG9pbnRzLm1h cHt8cHwgcC54fS5taW4KICB4ID0gKG1heF94ICsgbWluX3gpIC8gMgogIG1heF95ID0gcG9p bnRzLm1hcHt8cHwgcC55fS5tYXgKICBtaW5feSA9IHBvaW50cy5tYXB7fHB8IHAueX0ubWlu CiAgeSA9IChtYXhfeSArIG1pbl95KSAvIDIKICBjZW50ZXIgPSBQb3RlbnRpYWxDZW50ZXIu bmV3KHgsIHksIHBvaW50cykKICAjIFRoZSBvcmlnaW5hbCBkaXNwbGFjZW1lbnQgdmFsdWUg aXMgYmFzZWQgb24gdGhlIGZhY3QgdGhhdCBhIHRydWx5CiAgIyByYW5kb20gZGlzdHJpYnV0 aW9uIGdldHMgYSBtZWFuIHZhbHVlIHdpdGggYSBwcmVjaXNpb24gb2YgdGhpcyBvcmRlci4K ICAjIFRoZSBhY3R1YWwgY2VudGVyIGlzIHByb2JhYmx5IHJlYWNoYWJsZSB3aXRoIGEgZmV3 IG9mIHRoZXNlIHN0ZXBzCiAgbW92ZV9hbW91bnQgPSAoKG1heF95IC0gbWluX3kpICsgKG1h eF94IC0gbWluX3gpKSAvIHBvaW50cy5zaXplCiAgcmV0dXJuIFtjZW50ZXIsIG1vdmVfYW1v dW50XQplbmQKCiMgTG9vayBmb3IgdGhlIGJlc3QgY2VudGVyIGJ5IG1pbmltaXppbmcKIyBp dHMgbWF4aW11bSBkaXN0YW5jZSB3aXRoIHRoZSBnaXZlbiBwb2ludHMKIyBUaGlzIGlzIHRo ZSBzYW1lIGFzIG1pbmltaXppbmcgaXRzIHNxdWFyZQojICh0aGUgbWF4aW11bSBvZiB0aGUg c3F1YXJlIGRpc3RhbmNlcykKIyBUaGlzIGNhbiBiZSBzZWVuIGFzIGEgZGljaG90b215IG9u IGEgMi1kaW1lbnNpb25hbCBzcGFjZQpkZWYgZW5jaXJjbGUocG9pbnRzKQogIGNlbnRlciwg cm8gPSBjaG9zZV9vcmlnaW5hbF9jZW50ZXJfYW5kX21vdmVfYW1vdW50KHBvaW50cykKICAj IFdlJ2xsIG1vdmUgd2l0aCBwb2xhciBjb29yZGluYXRlcyAoZGlzdGFuY2UgKyBhbmdsZSA6 IHJvL3RoZXRhKQogICMgSG93IG1hbnkgZGlyZWN0aW9ucyBkbyB3ZSBmb2xsb3c/CiAgIyBl YWNoIG5ldyBhbmdsZSBjcmVhdGVzIGEgbmV3IChjb3N0bHkpIG1heF9zcXVhcmVfZGlzdGFu Y2UgY2FsbAogICMgc28gd2UgdGFrZSB0aGUgbWluaW11bSBuZWVkZWQgdG8gbW92ZSBhcm91 bmQgYW5kIGNsaW1iIHRoZQogICMgc3F1YXJlX2Rpc3RhbmNlIGdyYWRpZW50OiAzCiAgYW5n bGVfY291bnQgPSAzCiAgdGhldGFzID0gKDEuLmFuZ2xlX2NvdW50KS5tYXAgeyB8Y3wgKDIg KiBjICogTWF0aDo6UEkpIC8gYW5nbGVfY291bnR9CiAgaXRlciA9IDAKICAjIFRyYWNlIG91 ciBtb3ZlcwogIGNlbnRlcl9saXN0ID0gW10KCiAgbG9vcCBkbwogICAgY2VudGVyX2xpc3Qg PDwgY2VudGVyCiAgICBpdGVyICs9IDEKICAgIyBwdXRzICIje2l0ZXJ9OiAje2NlbnRlci5t YXhfc3F1YXJlX2Rpc3RhbmNlfSIKICAgICMgSXMgdGhlcmUgYSBiZXN0IG1vdmUgYXZhaWxh YmxlID8KICAgIGlmIG5ld19jZW50ZXIgPSBjZW50ZXIuYmVzdF9tb3ZlKHJvLCB0aGV0YXMp CiAgICAgIGNlbnRlciA9IG5ld19jZW50ZXIKICAgIGVsc2UKICAgICAgcm8gLz0gMgogICAg ICAjIFdlIHN0b3Agd2hlbiBybyBiZWNvbWVzIHRvbyBzbWFsbCB0byBtb3ZlIHRoZSBjZW50 ZXIKICAgICAgYnJlYWsgdW5sZXNzIGNlbnRlci5jYW5fYmVfbW92ZWRfYnkocm8pCiAgICBl bmQKICBlbmQKICMgcHV0cyAiQ2lyY2xlIGZvdW5kIGluICN7aXRlcn0gaXRlcmF0aW9ucyIK ICByZXR1cm4gWyBDaXJjbGUubmV3KGNlbnRlciwgc3FydChjZW50ZXIubWF4X3NxdWFyZV9k aXN0YW5jZSkpLAogICAgICAgICAgIGNlbnRlcl9saXN0IF0KZW5kCgppZiAkMCA9PSBfX0ZJ TEVfXwoKICAjIFVzZXMgMTAgcG9pbnRzIGJ5IGRlZmF1bHQKICBQT0lOVF9DT1VOVCA9IChB UkdWWzBdLnRvX2kgPT0gMCkgPyAxMCA6IEFSR1ZbMF0udG9faQoKICBwb2ludHMgPSBQb2lu dC5nZW5lcmF0ZV9zYW1wbGVzKFBPSU5UX0NPVU5UKQogIGh1bGwgPSBDb252ZXhIdWxsLmNv bnZleF9odWxsKHBvaW50cykKICB0ID0gVGltZS5ub3cKICBjaXJjbGUsIGNlbnRlcl9saXN0 ID0gZW5jaXJjbGUoaHVsbCkKICBwdXRzIGNpcmNsZQogIHB1dHMgIkZvdW5kIGluOiAje1Rp bWUubm93IC0gdH1zIgogIAogICMgR2VuZXJhdGUgYSBHbnVQbG90IGNvbW1hbmQgZmlsZSB0 byBzZWUgdGhlIHJlc3VsdAogIGYgPSBGaWxlLm9wZW4oJ3Bsb3Rjb21tYW5kLmNtZCcsICd3 JykKICBmLnByaW50IDw8RU9GCnNldCBwYXJhbWV0cmljCnNldCBzaXplIHNxdWFyZQpzZXQg eHJhbmdlIFstMC4yOjEuMl0Kc2V0IHlyYW5nZSBbLTAuMjoxLjJdCnNldCBtdWx0aXBsb3QK cGxvdCAiLSIKI3twb2ludHMubWFwIHsgfHB8ICIje3AueH0gI3twLnl9IiB9LmpvaW4oIlxu Iil9CmVuZApwbG90ICItIiB3aXRoIGxpbmVzCiN7Y2VudGVyX2xpc3QubWFwIHsgfHB8ICIj e3AueH0gI3twLnl9IiB9LmpvaW4oIlxuIil9CmVuZApwbG90IFswOjIqcGldIAooc2luKHQp KiN7Y2lyY2xlLnJhZGl1c30pKyN7Y2lyY2xlLmNlbnRlci54fSwoY29zKHQpKiN7Y2lyY2xl LnJhZGl1c30pKyN7Y2lyY2xlLmNlbnRlci55fQpzZXQgbm9tdWx0aXBsb3QKRU9GCiAgZi5j bG9zZQogIAogIHB1dHMgPDxFT0YKdXNlICdnbnVwbG90IC1wZXJzaXN0IHBsb3Rjb21tYW5k LmNtZCcgdG8gc2VlCnRoZSBjaXJjbGUsIHBvaW50cyBhbmQgcGF0aCB0byB0aGUgY2VudGVy CkVPRgogIAplbmQKCgo--------------030201000309060301080308--