From 5e48424b6456b49d3a37fd75040ccf7ea5f9b31c Mon Sep 17 00:00:00 2001 From: tomsmeding Date: Sun, 23 Dec 2018 23:44:22 +0100 Subject: Day 23 This isn't fun anymore. Because I was tired of this one and didn't care anymore, I looked at what others did and was baffled to see that there were basically two groups of people: one that used Z3 or an ILP solver, and one that wrote a direct solution that only worked on their own input, by accident. So I also used Z3. It worked. It takes a minute, though. --- 2018/23_draw.html | 1050 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2018/Cargo.lock | 150 ++++++++ 2018/Cargo.toml | 1 + 2018/input/23.txt | 1000 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2018/src/day23.rs | 492 +++++++++++++++++++++++++ 2018/src/main.rs | 4 +- 6 files changed, 2696 insertions(+), 1 deletion(-) create mode 100644 2018/23_draw.html create mode 100644 2018/input/23.txt create mode 100644 2018/src/day23.rs diff --git a/2018/23_draw.html b/2018/23_draw.html new file mode 100644 index 0000000..a4335dc --- /dev/null +++ b/2018/23_draw.html @@ -0,0 +1,1050 @@ + + + + + + + + +

+ + diff --git a/2018/Cargo.lock b/2018/Cargo.lock index 1d233ab..32017f4 100644 --- a/2018/Cargo.lock +++ b/2018/Cargo.lock @@ -12,6 +12,7 @@ version = "0.1.0" dependencies = [ "argparse 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", "lazy_static 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rand 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)", "regex 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -20,11 +21,38 @@ name = "argparse" version = "0.2.2" source = "registry+https://github.com/rust-lang/crates.io-index" +[[package]] +name = "bitflags" +version = "1.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" + [[package]] name = "cfg-if" version = "0.1.6" source = "registry+https://github.com/rust-lang/crates.io-index" +[[package]] +name = "cloudabi" +version = "0.0.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "fuchsia-zircon" +version = "0.3.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)", + "fuchsia-zircon-sys 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "fuchsia-zircon-sys" +version = "0.3.3" +source = "registry+https://github.com/rust-lang/crates.io-index" + [[package]] name = "lazy_static" version = "1.2.0" @@ -45,6 +73,71 @@ dependencies = [ "version_check 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)", ] +[[package]] +name = "rand" +version = "0.6.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)", + "fuchsia-zircon 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)", + "libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_chacha 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_hc 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_isaac 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_xorshift 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_chacha" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_core" +version = "0.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "rand_hc" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_isaac" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_pcg" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_xorshift" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + [[package]] name = "regex" version = "1.1.0" @@ -65,6 +158,27 @@ dependencies = [ "ucd-util 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)", ] +[[package]] +name = "rustc_version" +version = "0.2.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "semver 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "semver" +version = "0.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "semver-parser 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "semver-parser" +version = "0.7.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + [[package]] name = "thread_local" version = "0.3.6" @@ -88,16 +202,52 @@ name = "version_check" version = "0.1.5" source = "registry+https://github.com/rust-lang/crates.io-index" +[[package]] +name = "winapi" +version = "0.3.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + [metadata] "checksum aho-corasick 0.6.9 (registry+https://github.com/rust-lang/crates.io-index)" = "1e9a933f4e58658d7b12defcf96dc5c720f20832deebe3e0a19efd3b6aaeeb9e" "checksum argparse 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "3f8ebf5827e4ac4fd5946560e6a99776ea73b596d80898f357007317a7141e47" +"checksum bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "228047a76f468627ca71776ecdebd732a3423081fcf5125585bcd7c49886ce12" "checksum cfg-if 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)" = "082bb9b28e00d3c9d39cc03e64ce4cea0f1bb9b3fde493f0cbc008472d22bdf4" +"checksum cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ddfc5b9aa5d4507acaf872de71051dfd0e309860e88966e1051e462a077aac4f" +"checksum fuchsia-zircon 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "2e9763c69ebaae630ba35f74888db465e49e259ba1bc0eda7d06f4a067615d82" +"checksum fuchsia-zircon-sys 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "3dcaa9ae7725d12cdb85b3ad99a434db70b468c09ded17e012d86b5c1010f7a7" "checksum lazy_static 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a374c89b9db55895453a74c1e38861d9deec0b01b405a82516e9d5de4820dea1" "checksum libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)" = "10923947f84a519a45c8fefb7dd1b3e8c08747993381adee176d7a82b4195311" "checksum memchr 2.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "0a3eb002f0535929f1199681417029ebea04aadc0c7a4224b46be99c7f5d6a16" +"checksum rand 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ae9d223d52ae411a33cf7e54ec6034ec165df296ccd23533d671a28252b6f66a" +"checksum rand_chacha 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "771b009e3a508cb67e8823dda454aaa5368c7bc1c16829fb77d3e980440dd34a" +"checksum rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "0905b6b7079ec73b314d4c748701f6931eb79fd97c668caa3f1899b22b32c6db" +"checksum rand_hc 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "7b40677c7be09ae76218dc623efbf7b18e34bced3f38883af07bb75630a21bc4" +"checksum rand_isaac 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ded997c9d5f13925be2a6fd7e66bf1872597f759fd9dd93513dd7e92e5a5ee08" +"checksum rand_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "086bd09a33c7044e56bb44d5bdde5a60e7f119a9e95b0775f545de759a32fe05" +"checksum rand_xorshift 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "effa3fcaa47e18db002bdde6060944b6d2f9cfd8db471c30e873448ad9187be3" "checksum regex 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "37e7cbbd370869ce2e8dff25c7018702d10b21a20ef7135316f8daecd6c25b7f" "checksum regex-syntax 0.6.4 (registry+https://github.com/rust-lang/crates.io-index)" = "4e47a2ed29da7a9e1960e1639e7a982e6edc6d49be308a3b02daf511504a16d1" +"checksum rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "138e3e0acb6c9fb258b19b67cb8abd63c00679d2851805ea151465464fe9030a" +"checksum semver 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "1d7eb9ef2c18661902cc47e535f9bc51b78acd254da71d375c2f6720d9a40403" +"checksum semver-parser 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "388a1df253eca08550bef6c72392cfe7c30914bf41df5269b68cbd6ff8f570a3" "checksum thread_local 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "c6b53e329000edc2b34dbe8545fd20e55a333362d0a321909685a19bd28c3f1b" "checksum ucd-util 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "535c204ee4d8434478593480b8f86ab45ec9aae0e83c568ca81abf0fd0e88f86" "checksum utf8-ranges 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "796f7e48bef87609f7ade7e06495a87d5cd06c7866e6a5cbfceffc558a243737" "checksum version_check 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "914b1a6776c4c929a602fafd8bc742e06365d4bcbe48c30f9cca5824f70dc9dd" +"checksum winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "92c1eb33641e276cfa214a0522acad57be5c56b10cb348b3c5117db75f3ac4b0" +"checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" +"checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" diff --git a/2018/Cargo.toml b/2018/Cargo.toml index 484f482..33eca25 100644 --- a/2018/Cargo.toml +++ b/2018/Cargo.toml @@ -8,3 +8,4 @@ edition = "2018" argparse = "0.2.2" regex = "1" lazy_static = "1.2.0" +rand = "0.6.1" diff --git a/2018/input/23.txt b/2018/input/23.txt new file mode 100644 index 0000000..f762f20 --- /dev/null +++ b/2018/input/23.txt @@ -0,0 +1,1000 @@ +pos=<136613456,-512820,-739737>, r=87427481 +pos=<-53697593,55277802,49040699>, r=86116187 +pos=<3220880,75515511,53337027>, r=50746552 +pos=<88414078,70781701,66277674>, r=98943677 +pos=<-17988814,83735639,57607927>, r=84446784 +pos=<7905695,86080636,69893638>, r=73183217 +pos=<-106237978,86340882,82036549>, r=85944614 +pos=<-39951484,51796765,70217077>, r=87079969 +pos=<-41339171,48697955,55193194>, r=73297553 +pos=<-42571382,53083825,53317409>, r=74087026 +pos=<-7368751,52027496,-9560976>, r=95138965 +pos=<-8239116,41812660,62596194>, r=54485758 +pos=<-1137951,49037154,75388024>, r=52951810 +pos=<7650881,79141366,92778865>, r=89383763 +pos=<-17148778,67167319,69069673>, r=78500152 +pos=<-34682895,65463074,55433727>, r=80694128 +pos=<92864435,72243385,52889446>, r=91467469 +pos=<23342790,57278342,66486606>, r=96631618 +pos=<16097469,22492567,11010000>, r=76930041 +pos=<-27239715,74048890,47983162>, r=79486831 +pos=<48014242,79716366,40015768>, r=62251861 +pos=<511676,64398402,63621216>, r=52622716 +pos=<-29486239,66238746,61923874>, r=82763569 +pos=<92097957,57353083,58524935>, r=81446016 +pos=<-2615864,64900611,68273820>, r=60905066 +pos=<17304995,87864295,58127670>, r=53801410 +pos=<36460810,70793722,116450849>, r=97175553 +pos=<91303570,59210855,59663955>, r=83648530 +pos=<17400055,51714900,106525287>, r=65954578 +pos=<-9201950,68270611,75924360>, r=78511311 +pos=<10184185,63093052,93307967>, r=71331241 +pos=<24739666,43259195,5573675>, r=52957566 +pos=<-18267592,52724555,76111483>, r=72218039 +pos=<-35598801,54737022,27433735>, r=89083529 +pos=<35813819,73515444,94558754>, r=77358361 +pos=<6642272,22056475,91067625>, r=87832335 +pos=<17645774,89603262,67321149>, r=64393217 +pos=<-10216980,27634811,38770566>, r=70341591 +pos=<12799318,81249393,71992414>, r=65556938 +pos=<-10218046,74437078,62070349>, r=71839923 +pos=<-1309123,20674953,59788059>, r=65885225 +pos=<-27217791,66526827,53078642>, r=71937695 +pos=<-34737368,44315647,75994929>, r=91879642 +pos=<30808903,39024070,99557972>, r=65161437 +pos=<18233335,72395211,90831029>, r=70107346 +pos=<37186749,-678419,57742780>, r=69426693 +pos=<-9615179,80576697,64086230>, r=79392664 +pos=<33935621,102484176,52277559>, r=62167524 +pos=<21730454,116532754,59523052>, r=79439730 +pos=<-44299553,51849314,52674431>, r=73937932 +pos=<98820726,52369354,56304096>, r=80964285 +pos=<-14670863,53307196,63286058>, r=56378495 +pos=<21141579,52692533,60648771>, r=77839132 +pos=<106030705,57863782,38674931>, r=99756568 +pos=<3660762,56362269,113500773>, r=91316727 +pos=<-407093,36114871,62900059>, r=52655349 +pos=<17300250,90851621,82759279>, r=81425029 +pos=<3552610,79637006,46529196>, r=55736575 +pos=<19340107,84837235,62352207>, r=52963786 +pos=<8521013,89819722,24371259>, r=83109002 +pos=<14563407,28673587,78383971>, r=60610219 +pos=<105274857,48490223,59505360>, r=90108685 +pos=<6522669,68013196,92958454>, r=79563377 +pos=<61441811,62255240,63607848>, r=60775173 +pos=<-30662880,72201886,57781685>, r=85760834 +pos=<-5704121,74191612,91679671>, r=96690023 +pos=<22440794,115302243,29587291>, r=89455675 +pos=<16846226,85850758,26219592>, r=68966703 +pos=<-11181912,74609397,43701422>, r=68271328 +pos=<112019147,48094141,55257089>, r=93000920 +pos=<-58029664,63702221,52791218>, r=99637517 +pos=<56546279,54927537,104557578>, r=89501416 +pos=<13690470,51265122,54792423>, r=53548975 +pos=<-20863525,78114651,44421611>, r=80738144 +pos=<20071309,136046599,55636529>, r=96726219 +pos=<-9825817,54458897,71973514>, r=61373140 +pos=<-13643977,45813902,94182312>, r=87475383 +pos=<4214048,57552549,55230473>, r=97407755 +pos=<-44465852,38322072,54656647>, r=86263523 +pos=<-8532222,52266115,71351598>, r=57264679 +pos=<15789835,78397136,91588786>, r=79310551 +pos=<87644233,71738261,52393733>, r=85246435 +pos=<24700943,90988926,103171122>, r=94573621 +pos=<-16261249,63121025,87229161>, r=91725871 +pos=<-52294570,67135761,48053370>, r=97558456 +pos=<18918374,81332072,97803514>, r=85331838 +pos=<11760283,82388891,26779326>, r=70030661 +pos=<19928626,82449711,96833465>, r=84469124 +pos=<-18348975,19999142,52648068>, r=76460901 +pos=<-12075601,71251550,85024678>, r=93466308 +pos=<80062151,62500897,78775775>, r=94808908 +pos=<12337661,103647294,81418622>, r=97842757 +pos=<-11115387,60112851,66531714>, r=62874491 +pos=<16906477,63764749,85558216>, r=57530991 +pos=<-4672303,54855285,1301903>, r=84407059 +pos=<-37982464,58456898,68225299>, r=89779132 +pos=<-17681001,71939994,60038525>, r=74774035 +pos=<-11837172,58467855,79274314>, r=74693725 +pos=<29729949,7390010,64977794>, r=61136429 +pos=<-12679395,87224461,58161931>, r=83180457 +pos=<-11559100,72144044,77817800>, r=86635361 +pos=<-2084469,25684278,55681143>, r=57544326 +pos=<20590016,129914590,49426051>, r=86080032 +pos=<-7571416,69794846,69085384>, r=71566033 +pos=<-34145880,48469543,51820255>, r=62959690 +pos=<-8692081,31985652,52581756>, r=54751347 +pos=<-24455978,69065733,52902609>, r=71539034 +pos=<-2667941,59922398,71227376>, r=58932198 +pos=<-38020475,72881338,61644325>, r=97660532 +pos=<-21527600,53755812,51653194>, r=52050984 +pos=<-8830611,33006975,78898650>, r=80185902 +pos=<19025250,113913931,63618165>, r=83621311 +pos=<8387089,77230233,57248610>, r=51206312 +pos=<9535513,118434510,37136580>, r=97943806 +pos=<78992433,58822717,31347868>, r=81004338 +pos=<-16906193,77442482,52709412>, r=72172536 +pos=<22311017,63448797,51701106>, r=94242941 +pos=<43179406,2818296,30763106>, r=84483777 +pos=<-363630,57933199,98730777>, r=82142085 +pos=<-3421442,71654138,81584493>, r=81774527 +pos=<105294101,47765605,48049117>, r=84365008 +pos=<-14236037,92920841,48040781>, r=85297524 +pos=<5696945,87936599,71179435>, r=78533668 +pos=<70714071,41126802,64803849>, r=68209814 +pos=<-18725349,54598292,52699640>, r=51138183 +pos=<59897823,71653281,71202033>, r=76223304 +pos=<48123775,102241419,73882598>, r=97717918 +pos=<-27257912,59427348,52360090>, r=64159728 +pos=<7347141,78617861,96938400>, r=93323519 +pos=<98970812,42594863,66538549>, r=96733304 +pos=<60136017,76634280,74781184>, r=85021510 +pos=<-38514792,65847495,52025409>, r=81502116 +pos=<-5508508,4887248,43864104>, r=83287138 +pos=<21727987,54693625,95057154>, r=53137390 +pos=<-15479704,40894383,53779209>, r=53827666 +pos=<-50001012,42594012,56389944>, r=89260340 +pos=<-49970116,64164073,53317682>, r=92566258 +pos=<-56357341,55323528,59446041>, r=96241383 +pos=<625968,53683329,98614903>, r=76786891 +pos=<21482773,117944535,70699492>, r=92275780 +pos=<16203712,73330825,69917915>, r=52159463 +pos=<13906226,70337776,30608175>, r=52004893 +pos=<-21655059,68530571,79036384>, r=94336614 +pos=<-6379112,70074314,96974691>, r=98542673 +pos=<37257281,88232345,55974220>, r=54934223 +pos=<-153042,61570334,64745296>, r=51583144 +pos=<75744358,74770786,74235757>, r=98220949 +pos=<2593526,12576425,76209878>, r=86502916 +pos=<-3213601,79186838,80823018>, r=88337919 +pos=<-9431288,52885294,66308318>, r=53739421 +pos=<39457172,77981561,77781961>, r=68690851 +pos=<3658726,45027232,78570696>, r=55347772 +pos=<19540854,59560050,33221913>, r=66437344 +pos=<-23991955,53819675,65495637>, r=68421679 +pos=<-15925338,62003166,71681923>, r=74724861 +pos=<179979,95055064,72345095>, r=92334745 +pos=<32084825,113714994,57462206>, r=76732047 +pos=<-79456713,-30995940,73253681>, r=71108738 +pos=<-5085269,56556449,63274512>, r=50030649 +pos=<-1823099,53617693,74353439>, r=54908645 +pos=<-21582671,87360226,64824893>, r=98882268 +pos=<-54047120,52572271,45012396>, r=87788501 +pos=<-621964,40254302,67623764>, r=53454465 +pos=<10705962,52178757,-10564055>, r=78218262 +pos=<-27052117,72974854,68996532>, r=94137885 +pos=<-5333720,61326896,75858050>, r=67633053 +pos=<-442860,-7927774,60719749>, r=94553540 +pos=<20190232,59561903,101548027>, r=66034633 +pos=<-7907411,40629427,68521654>, r=61262635 +pos=<-9455107,66611005,94728621>, r=95909233 +pos=<22122168,62372400,119686289>, r=85051023 +pos=<-16418814,91187751,60788730>, r=93509810 +pos=<-12210203,71963130,19080036>, r=91275101 +pos=<-16069946,54585553,55218935>, r=50988886 +pos=<73589783,36919962,51760461>, r=62248915 +pos=<10988236,47525791,7585386>, r=60430836 +pos=<10516253,63819008,75162627>, r=53580091 +pos=<54978561,77777004,81843099>, r=88068740 +pos=<843965,59034530,26718598>, r=57653476 +pos=<8390445,51933284,106893232>, r=75550828 +pos=<55468357,41898786,6292104>, r=82163240 +pos=<-15657432,59791539,54996025>, r=55559386 +pos=<21925705,56064114,98432334>, r=57685472 +pos=<2045205,54926092,91406478>, r=69401804 +pos=<18964578,82009106,68170256>, r=56329266 +pos=<-5020873,58135455,83138917>, r=71409692 +pos=<11206282,18758794,90297569>, r=85795593 +pos=<60429823,65420118,62455940>, r=61775922 +pos=<-50071054,65142864,56916609>, r=97245137 +pos=<37522973,119514287,68154460>, r=98661779 +pos=<-24546116,79951244,52341069>, r=81952965 +pos=<-42895143,51426102,49103721>, r=71398899 +pos=<19847811,70965352,88276453>, r=64508398 +pos=<31969885,74676586,119451667>, r=99568484 +pos=<43133639,79493715,70091589>, r=66189023 +pos=<3536597,70013464,59700142>, r=51291540 +pos=<-43456481,62212963,55178319>, r=85962366 +pos=<66908155,61377553,55147564>, r=56903339 +pos=<-6338837,64186892,67392177>, r=63032325 +pos=<24582754,12428156,39119902>, r=50399652 +pos=<19622738,107750729,55849974>, r=69092525 +pos=<-50422280,58990076,62168244>, r=96695006 +pos=<58134510,61311825,96239969>, r=89156504 +pos=<-30966037,57564421,54587595>, r=68232489 +pos=<12569803,83417760,58547639>, r=54510046 +pos=<16028817,91085624,85099394>, r=85270691 +pos=<26948233,79274928,118354187>, r=98047375 +pos=<-52310680,47522666,64367435>, r=94618457 +pos=<-6416427,79465208,59490450>, r=70486528 +pos=<20092186,68488461,91337971>, r=64848774 +pos=<-15142198,42300705,54605738>, r=52910257 +pos=<-27837357,69166421,45527549>, r=77657747 +pos=<-40369484,73666973,51836487>, r=90987378 +pos=<85019354,56875805,38052709>, r=78379725 +pos=<-4826865,73385493,74154124>, r=77481047 +pos=<-44327050,62980445,57928726>, r=90350601 +pos=<2268051,71674062,18320627>, r=77266756 +pos=<7560942,23918555,95582539>, r=89566155 +pos=<-40522661,58387981,55190926>, r=79216025 +pos=<17493703,92481489,21602524>, r=79566649 +pos=<-549853,30548349,59679581>, r=55144150 +pos=<-11540623,61439486,75747954>, r=73842446 +pos=<-27425143,66943956,51613022>, r=71096670 +pos=<7492358,52336684,59482404>, r=62591245 +pos=<8199261,52115157,61979910>, r=52924169 +pos=<-5227038,75473558,53223397>, r=59038494 +pos=<69304179,60217316,90678830>, r=93670829 +pos=<-27825322,58595174,52943775>, r=64478650 +pos=<-3930520,44822324,83076659>, r=67647944 +pos=<-15669371,56863526,61131713>, r=58778995 +pos=<28136546,52898534,69587237>, r=88623606 +pos=<-65393666,51826191,55613912>, r=97948204 +pos=<-15477551,51180735,42248775>, r=50591359 +pos=<40449375,72513414,96662908>, r=83095857 +pos=<-33924420,53998875,71917916>, r=84955612 +pos=<10793863,52565615,51767299>, r=98060212 +pos=<9995273,60527127,91707845>, r=67354108 +pos=<-60284471,51756689,57993530>, r=95149079 +pos=<18376558,10452573,62217674>, r=58851640 +pos=<6437033,60403963,76732508>, r=55814249 +pos=<-28335460,51550727,67141191>, r=72141764 +pos=<-20795148,56783730,53199338>, r=55892601 +pos=<12754662,84841524,53799805>, r=51001164 +pos=<9355656,37410878,81929957>, r=60626411 +pos=<70162685,52698231,62479018>, r=58810202 +pos=<3593617,1103985,61329203>, r=82094839 +pos=<-11110833,76403444,81998629>, r=94627295 +pos=<-2911501,68332204,55930359>, r=52288511 +pos=<-5611352,24754525,54946306>, r=61266149 +pos=<8852382,71155727,68890982>, r=56308709 +pos=<61447488,68409236,69588689>, r=72915436 +pos=<7800512,89666253,65758055>, r=72738393 +pos=<10592995,54945607,58732681>, r=89051922 +pos=<42798128,-12649279,56562836>, r=85829241 +pos=<11562554,75630041,86875504>, r=76057543 +pos=<77961659,71510466,54153352>, r=77095503 +pos=<31055259,54921299,-9869494>, r=70383159 +pos=<-27501669,62023219,47541351>, r=68164946 +pos=<42374475,68761335,72601978>, r=57207824 +pos=<-33321254,51983321,59677321>, r=70096300 +pos=<24068578,39736961,60654009>, r=88299248 +pos=<-19116561,56737201,34200348>, r=67834972 +pos=<22969648,52249055,100644454>, r=55038258 +pos=<-42911185,51860830,61376355>, r=81262991 +pos=<-42633368,44611772,66190367>, r=89674954 +pos=<-3829240,75255688,21232601>, r=84033808 +pos=<5934856,57988042,76585113>, r=53752725 +pos=<-32964350,68530123,57108410>, r=83717261 +pos=<43876005,92164898,87846839>, r=97357843 +pos=<-2417792,58943300,65531206>, r=52006718 +pos=<54964722,89070986,53056518>, r=70562253 +pos=<-290623,31446470,65443341>, r=59750487 +pos=<7639935,101059316,58888687>, r=77422498 +pos=<-28253746,62612782,71235848>, r=87217278 +pos=<-7422094,56693858,109005575>, r=98235920 +pos=<61189820,88854622,44952918>, r=79628549 +pos=<-16010449,60503569,67814188>, r=69442584 +pos=<31995549,99041054,92811203>, r=97317853 +pos=<14407890,68606212,88656048>, r=67968926 +pos=<3797019,93897803,59385476>, r=74600640 +pos=<89982687,70799922,58816742>, r=93069386 +pos=<-47391381,58920806,47022977>, r=85470601 +pos=<-18682541,52396968,60465510>, r=56659507 +pos=<-33603071,56312429,61658802>, r=76688781 +pos=<-1966320,58483882,29754668>, r=56877265 +pos=<-6876331,35253483,65966223>, r=63052064 +pos=<-39772638,75789985,47508955>, r=94235051 +pos=<-24980812,-1938691,-46278539>, r=50540858 +pos=<-14975005,78724644,39316097>, r=80565111 +pos=<-2885944,65589513,76516656>, r=70106553 +pos=<3541691,72547980,70693895>, r=64814600 +pos=<-44510906,63214333,63320805>, r=96160422 +pos=<185135951,79371810,69897884>, r=92278734 +pos=<-15712941,69417771,56680209>, r=66925482 +pos=<3371300,64063926,70577995>, r=56385028 +pos=<20093270,89812250,83966344>, r=78799702 +pos=<-44882626,56482809,44012736>, r=83534067 +pos=<7807097,59338218,93406346>, r=70052015 +pos=<83206185,54254511,65285920>, r=76216650 +pos=<-9128452,31764042,52408460>, r=55235957 +pos=<9273140,58063106,84328894>, r=58233459 +pos=<12730173,65723179,86216535>, r=64323934 +pos=<-5370160,21333035,52408548>, r=61908782 +pos=<-50412106,36708544,57003999>, r=96170823 +pos=<-12428116,56614507,59912876>, r=54070441 +pos=<23530187,55890018,101558624>, r=59032841 +pos=<24076853,75872593,84021081>, r=60931262 +pos=<66742911,53159306,102755650>, r=96128101 +pos=<52985633,69568131,100732548>, r=96756344 +pos=<21276856,95454549,27263024>, r=73096105 +pos=<18634979,90055348,78648309>, r=75183223 +pos=<59296178,97443382,58785611>, r=88995359 +pos=<-9151924,60937196,63129967>, r=58333507 +pos=<-131439802,11932397,63801725>, r=91099003 +pos=<-15182359,51945676,96531706>, r=88774362 +pos=<37456150,58413739,90785927>, r=60125884 +pos=<55535275,58675694,68529536>, r=56210588 +pos=<-23901453,82911425,51765843>, r=83693104 +pos=<20400242,84135488,38426476>, r=51490217 +pos=<86127079,53137259,73699744>, r=86434146 +pos=<-37504970,65330192,58356041>, r=86305590 +pos=<-36229876,54144877,76073195>, r=91562525 +pos=<7122807,47260000,60037998>, r=92003347 +pos=<14241003,60321844,84135837>, r=55331088 +pos=<-58054472,54730510,42664262>, r=96302105 +pos=<11128985,-3179856,61388093>, r=78901954 +pos=<-86171724,81676146,128118766>, r=65629454 +pos=<-32477909,54111811,66095298>, r=77799414 +pos=<16473884,29685000,94881174>, r=74185298 +pos=<-39673388,54367240,60656362>, r=79811579 +pos=<-36820899,56003364,51780853>, r=69719509 +pos=<33393407,80286458,76512600>, r=63663115 +pos=<18145724,41961673,52085548>, r=82246846 +pos=<773269,56344730,109740475>, r=90426345 +pos=<23227623,20924988,89657454>, r=70967862 +pos=<29769636,51258040,101968164>, r=56466105 +pos=<-3255302,91302711,53052997>, r=72725506 +pos=<63288029,31756890,15053302>, r=91363738 +pos=<-696254,82267064,54884033>, r=62961850 +pos=<24224162,74018463,80725407>, r=55634090 +pos=<-31583375,35116342,57915541>, r=79845595 +pos=<-20265647,61458300,53421504>, r=60260040 +pos=<-3625510,70617596,85973701>, r=85331222 +pos=<38592662,72038274,107230244>, r=91331550 +pos=<20947230,95753333,5848876>, r=95138602 +pos=<65256974,42508621,53997591>, r=50564655 +pos=<56144525,-47809394,138757109>, r=88873477 +pos=<12536114,44878759,53725314>, r=86437546 +pos=<-20301103,44075250,52762962>, r=54451813 +pos=<-461902,80465125,84487814>, r=90529307 +pos=<7130680,32413231,68883794>, r=54802893 +pos=<-50296082,60195477,45850842>, r=90822087 +pos=<-14564832,72623628,17948114>, r=95421720 +pos=<-22686155,63096629,54372268>, r=65269532 +pos=<69844001,61172133,56055801>, r=60541966 +pos=<-52847704,61819166,58790940>, r=98572688 +pos=<14547281,53614270,69916715>, r=64925594 +pos=<11858628,69801510,83476504>, r=66533825 +pos=<-19237228,57038668,55663966>, r=57054287 +pos=<-2272553,98539746,62554872>, r=88481774 +pos=<-8556006,44686979,74145414>, r=63477536 +pos=<2504323,61605769,51711818>, r=54478689 +pos=<47588454,79992799,94986516>, r=96037851 +pos=<103658947,51685093,57082700>, r=85896762 +pos=<-30259191,60236324,60596487>, r=76206463 +pos=<-16899083,75972745,75204218>, r=93190621 +pos=<-16138352,72149890,57424797>, r=70827421 +pos=<-32022269,39108198,51836967>, r=70214052 +pos=<-253386,60377315,87086253>, r=72831391 +pos=<70319029,58272431,24333949>, r=78795019 +pos=<98140448,55305455,54099422>, r=81015347 +pos=<-9894221,46215061,90692267>, r=79835086 +pos=<8135694,75227546,75981649>, r=68187909 +pos=<3050471,53586527,55188089>, r=52075619 +pos=<1872493,96006217,77781926>, r=97030112 +pos=<33059309,107988331,79210607>, r=93728745 +pos=<16673776,69427534,108363123>, r=86231293 +pos=<-55714690,52582577,37933926>, r=96544709 +pos=<593835,83505567,68365123>, r=76391300 +pos=<43486018,76414497,67060559>, r=60431122 +pos=<-103710,79781165,51942827>, r=56942322 +pos=<10133283,63186363,55221028>, r=90994744 +pos=<23438290,54031653,67704842>, r=75155252 +pos=<-67769695,52775484,52431198>, r=98090761 +pos=<-18104986,52809731,54267642>, r=50296769 +pos=<109991188,53156356,60594209>, r=97211931 +pos=<-13768977,54140486,59831889>, r=52855852 +pos=<-12489665,47714331,86555741>, r=76794067 +pos=<-26482316,33973790,58911081>, r=76882915 +pos=<-160197435,53199007,15047334>, r=72701562 +pos=<23358129,69976926,85439610>, r=57172786 +pos=<24201045,82557215,112270801>, r=95741523 +pos=<72394082,20781518,37930394>, r=88568308 +pos=<45145254,31095571,82460069>, r=70328402 +pos=<-24815015,78740100,66702713>, r=95372303 +pos=<-11180118,63194518,51850772>, r=51339974 +pos=<-30260369,77069699,58001879>, r=90446543 +pos=<12841613,54905801,60405944>, r=69102701 +pos=<69379484,75759864,80677420>, r=99286807 +pos=<-19898305,56022498,52114906>, r=53150117 +pos=<23972174,63400531,63593334>, r=88610729 +pos=<-7853869,55653210,30754191>, r=58934358 +pos=<40004815,92174613,37712106>, r=69004511 +pos=<-18970401,64246847,57001969>, r=65333603 +pos=<-55945729,46641309,41200961>, r=94633445 +pos=<10448314,60832634,-13979245>, r=90545188 +pos=<104420953,54797004,51761342>, r=84449325 +pos=<-7833268,56419777,64966118>, r=54333552 +pos=<-41600051,53218447,75060610>, r=94993621 +pos=<-23285697,51988784,62294935>, r=62683806 +pos=<-6906170,52717101,66490995>, r=51228649 +pos=<-36994277,58578684,69447528>, r=90134897 +pos=<13894089,90601100,71559173>, r=73380713 +pos=<5549488,90598003,63587583>, r=73750520 +pos=<27986859,65318406,569711>, r=67272566 +pos=<11420671,52635330,54320974>, r=70384136 +pos=<58986016,64249155,26039401>, r=71732796 +pos=<5530635,65978466,18218016>, r=68411191 +pos=<-5385393,46216210,79409449>, r=64041818 +pos=<-21799629,90568144,46789063>, r=91760239 +pos=<-36265254,58098351,59809891>, r=79287875 +pos=<-85146141,88950855,-3714880>, r=50044292 +pos=<38619326,-4038243,77668519>, r=94144770 +pos=<2694518,54614333,-4908892>, r=83010409 +pos=<5313262,51345161,59838196>, r=72136128 +pos=<14843630,-1349878,43928227>, r=69108117 +pos=<22464636,120847792,40757992>, r=83806553 +pos=<-9865777,51214858,90863194>, r=77058488 +pos=<19167267,52510615,54852693>, r=90699829 +pos=<14593457,70653650,97885859>, r=79060557 +pos=<-8818822,61716404,18373136>, r=78343826 +pos=<1060,70746123,74820827>, r=70680268 +pos=<2440131,63910700,77731744>, r=64316854 +pos=<9446148,94030616,72483361>, r=82182217 +pos=<99080786,67236493,59091021>, r=98878926 +pos=<-1302538,90260423,63215145>, r=79892689 +pos=<8394619,77120518,104185074>, r=98025497 +pos=<8809237,89970368,88703357>, r=94978937 +pos=<61696969,53031317,25103817>, r=64161515 +pos=<-17945953,52730115,54562544>, r=50352996 +pos=<5573049,75894102,57995185>, r=53430728 +pos=<1734159,18182439,88390315>, r=93936719 +pos=<16427148,60790813,57255534>, r=77938471 +pos=<-5794985,58712237,72538823>, r=62160526 +pos=<114104963,48165299,48341508>, r=92483804 +pos=<66162561,63632542,48965213>, r=55367138 +pos=<-10848319,68498736,72425408>, r=76886851 +pos=<35960404,57952302,83825949>, r=51208802 +pos=<-7537899,63784540,26119781>, r=71384092 +pos=<7597577,78226192,54364713>, r=50108075 +pos=<-4944468,85203935,56866419>, r=72129314 +pos=<-31664056,74767063,66581879>, r=98127721 +pos=<-30554637,64050408,69381798>, r=89101226 +pos=<15180605,89452073,84996875>, r=84382933 +pos=<24727280,106040899,27094989>, r=80399998 +pos=<-32937600,57802552,41091533>, r=75830264 +pos=<-24285878,55135192,45900921>, r=59701557 +pos=<99942558,60451396,53076615>, r=86940865 +pos=<-8142431,63656427,70896708>, r=67810159 +pos=<19572931,72289003,88954380>, r=66784918 +pos=<17178080,32326459,98036814>, r=73995977 +pos=<-40327597,60321955,30752519>, r=96078407 +pos=<-26708621,51303087,68660841>, r=71786962 +pos=<5298440,71150886,98998933>, r=89965866 +pos=<-26727384,52712004,60606804>, r=65160630 +pos=<-42515019,36860711,54621755>, r=85739222 +pos=<-19692936,52880476,53505130>, r=51192967 +pos=<-2862751,72059619,56687442>, r=56724369 +pos=<23309701,73678498,90297260>, r=65780546 +pos=<103591531,51292218,54785000>, r=83139488 +pos=<13334478,40067215,41788503>, r=53285143 +pos=<-19529026,52222981,57621425>, r=54488069 +pos=<-1797950,83874608,63370131>, r=74157238 +pos=<-25984963,45705100,63968004>, r=69711376 +pos=<-24664085,26439550,59809899>, r=83497673 +pos=<19736100,80301464,65388701>, r=51068468 +pos=<-25320635,61777368,77622402>, r=89834801 +pos=<-17286284,77658389,79260938>, r=99320666 +pos=<70330963,53068965,53858287>, r=50728428 +pos=<-3076230,90554067,55114683>, r=73859363 +pos=<-20974395,51855715,72542126>, r=70486673 +pos=<1092644,-4119326,69709754>, r=98199427 +pos=<15938133,59416689,58855448>, r=92943839 +pos=<-9112976,52910350,69896190>, r=57034132 +pos=<52773451,30360939,79247967>, r=75479113 +pos=<-6680030,26114817,19182073>, r=87913270 +pos=<1482965,86244061,74533437>, r=84409063 +pos=<24689402,71291292,83726812>, r=55443483 +pos=<30350862,66160075,106804338>, r=76785312 +pos=<-4063590,84853935,56872509>, r=70904417 +pos=<5856723,68860058,67443259>, r=55561024 +pos=<-7092718,83599936,62097932>, r=77904977 +pos=<-10322894,95735574,63377690>, r=94550544 +pos=<19921997,12113475,95509859>, r=88937502 +pos=<11534894,57463560,99207505>, r=70250571 +pos=<12352413,63309310,95136075>, r=71207369 +pos=<41175395,95875663,40694251>, r=70893868 +pos=<59891986,74136560,19271752>, r=89293819 +pos=<-23086309,46188709,61304958>, r=63666046 +pos=<-35534522,46755845,63454442>, r=77696176 +pos=<-17431848,55911646,61066276>, r=59524206 +pos=<19833014,98941413,53373702>, r=57596603 +pos=<-28451505,62393147,51769902>, r=67729137 +pos=<8178175,-29195966,48404389>, r=99143478 +pos=<-10800811,66052879,72255412>, r=74223622 +pos=<7592515,82345414,73497606>, r=73364887 +pos=<18762382,82447623,97073423>, r=85873084 +pos=<-10487671,31987978,73584470>, r=77547158 +pos=<-9056504,62925961,53357292>, r=50454349 +pos=<27999580,85878361,92076324>, r=79424309 +pos=<51800702,30641723,78124579>, r=73102228 +pos=<12642813,82894579,64946494>, r=60312761 +pos=<-61807304,47686811,53275056>, r=92858540 +pos=<-7276796,60434304,88907028>, r=81732530 +pos=<-29599217,39708375,83129734>, r=98483597 +pos=<-23520152,26844092,62214412>, r=84353826 +pos=<-28877325,61946397,69770777>, r=85708879 +pos=<-14608106,72848679,65361364>, r=77932548 +pos=<-36824990,70391000,43020520>, r=90376960 +pos=<44969927,68147155,35692982>, r=51961138 +pos=<19011433,65149442,-12540316>, r=84859740 +pos=<18764314,69338844,96926694>, r=72615606 +pos=<-25391985,54173991,76565456>, r=81246468 +pos=<-37132499,58605126,57299821>, r=78151951 +pos=<317469,47901411,90999015>, r=68243137 +pos=<4732566,82416141,64829451>, r=67627448 +pos=<-4438337,64068128,59428063>, r=53049034 +pos=<-7510390,65454288,58686238>, r=56765295 +pos=<13297331,71022908,83309651>, r=66149656 +pos=<-2443890,-1053307,49146976>, r=80880201 +pos=<18424959,-25894837,57469563>, r=90402436 +pos=<19134835,37687041,81457411>, r=50098606 +pos=<30727267,74338302,16287433>, r=63315163 +pos=<76426391,60025595,56674928>, r=66597034 +pos=<-37764165,64665026,63738632>, r=91282254 +pos=<73841307,45244034,7979885>, r=95503095 +pos=<8518776,102619990,65620373>, r=84836052 +pos=<33279437,-14820526,57737587>, r=79656722 +pos=<-12641079,64685181,53396171>, r=55837091 +pos=<-9951596,57691018,18966738>, r=74857701 +pos=<11705830,39289792,103172595>, r=77639987 +pos=<32755328,86575935,59301361>, r=52102968 +pos=<-56381974,51244757,51903260>, r=84644396 +pos=<10573573,67254309,71343991>, r=53139256 +pos=<23178882,99249505,53062798>, r=54247805 +pos=<-30438220,43249726,63852895>, r=76504484 +pos=<-18008082,91354098,61662797>, r=96139463 +pos=<58130621,-5410250,53763204>, r=91122775 +pos=<38376500,5309795,68536851>, r=75422199 +pos=<40568207,55819371,111949414>, r=81807094 +pos=<13385608,58751181,87916220>, r=58396316 +pos=<10652780,62923714,16913699>, r=61538816 +pos=<66584605,90471059,59953467>, r=90479328 +pos=<23828597,9229466,82674549>, r=75079685 +pos=<-2374305,51653149,81806283>, r=60948119 +pos=<15686944,101308548,58364945>, r=69100929 +pos=<12725742,68880644,106967805>, r=88237088 +pos=<17716933,53898766,92455242>, r=53751453 +pos=<-33372359,56824192,52416697>, r=67727660 +pos=<4982549,62244620,102018278>, r=84394819 +pos=<9097870,2277106,23511783>, r=91643276 +pos=<104095420,52061506,57103657>, r=86730620 +pos=<38111501,86440374,53482963>, r=51504912 +pos=<58344818,61400907,63284974>, r=56500739 +pos=<16884807,19231253,82990003>, r=72336956 +pos=<-42692945,65946169,41961384>, r=92859217 +pos=<-28034754,55487947,62126726>, r=70763811 +pos=<19274376,79870506,35147693>, r=51629912 +pos=<21320145,55312624,92060702>, r=51167634 +pos=<-36291008,37650308,58389536>, r=82493243 +pos=<-10796796,41489105,66097601>, r=60868304 +pos=<-40177150,63607920,46375716>, r=83590789 +pos=<16877383,57508433,130889109>, r=96634562 +pos=<78035795,47558838,61699900>, r=65995510 +pos=<-12157529,59079739,94459705>, r=90811614 +pos=<-14719298,67293961,58776388>, r=65904037 +pos=<23165472,48319134,141014934>, r=94993386 +pos=<14483307,55545491,83869510>, r=50046127 +pos=<-13975465,72281297,75555056>, r=86926409 +pos=<54944081,54012748,104500519>, r=86928029 +pos=<15118634,63975046,120649575>, r=94620419 +pos=<18002868,89743987,46547787>, r=51375023 +pos=<118470960,53314916,47200144>, r=99123142 +pos=<-18823495,55420905,53701803>, r=53060582 +pos=<-5467064,58554591,77050896>, r=66186932 +pos=<22160794,74878846,55706389>, r=70447601 +pos=<-27826743,71164171,56998262>, r=81103878 +pos=<-60219520,57279767,54018988>, r=96632668 +pos=<11765030,64865953,25690628>, r=53591753 +pos=<-77604253,51195582,160265663>, r=82321239 +pos=<8895376,94389845,70206097>, r=80814976 +pos=<72068955,61735419,61931626>, r=69206024 +pos=<71294850,57747925,61258998>, r=63771982 +pos=<-12500311,87983348,41185110>, r=85480069 +pos=<13165281,58734390,57751380>, r=71578498 +pos=<-16519504,56287098,41988135>, r=57000006 +pos=<15702065,59567300,125776377>, r=94756321 +pos=<104067037,56353806,59893063>, r=93783989 +pos=<-2443051,34066815,59811244>, r=53650485 +pos=<78659016,53301646,58395591>, r=63826456 +pos=<-5395135,51489915,53108186>, r=54457449 +pos=<43783348,70786755,68608325>, r=56648600 +pos=<15861882,75526752,70870247>, r=55649551 +pos=<-21433110,60201366,71144216>, r=77893311 +pos=<16927373,30534856,57344675>, r=79447115 +pos=<-23582240,51182170,53671182>, r=53550212 +pos=<48377124,87322307,57807776>, r=66977272 +pos=<-24658235,34774969,55408108>, r=70754558 +pos=<-57025118,51608427,56368656>, r=90116625 +pos=<-40956808,54872377,58233637>, r=79177201 +pos=<-7940696,64406847,65491844>, r=62954392 +pos=<18514021,116278681,67137430>, r=90016641 +pos=<43358506,27845033,68486380>, r=57818557 +pos=<1110894,83500413,68255453>, r=75759354 +pos=<-37948234,63772147,53141588>, r=79976703 +pos=<13559648,85475298,69747661>, r=66777842 +pos=<52847535,100951259,70145575>, r=97414722 +pos=<-21363508,51195381,52333138>, r=50006604 +pos=<42775136,24331657,88882389>, r=81144757 +pos=<-1933203,45916056,85330850>, r=66811316 +pos=<-57987412,55995732,52031150>, r=91128682 +pos=<-42000373,57698338,58535687>, r=83348916 +pos=<-22415966,68748566,55301911>, r=71580898 +pos=<63130941,60546452,58913823>, r=56061251 +pos=<-25360,94955513,32263639>, r=88899014 +pos=<16041791,46748455,54886958>, r=52853925 +pos=<21841806,63659499,51701479>, r=64043047 +pos=<1507336,30781882,86426870>, r=79600758 +pos=<-61462214,51930278,59048201>, r=97555074 +pos=<5596619,62910768,103402603>, r=85831362 +pos=<-17947167,60351558,52786859>, r=56199984 +pos=<8310608,110445624,30715607>, r=97601075 +pos=<57809969,62546762,83913036>, r=77739845 +pos=<-4243002,78023652,59272973>, r=66654140 +pos=<-38346139,46279251,81595137>, r=99125137 +pos=<-39505659,59077659,30772250>, r=93992534 +pos=<70748692,61615798,69299886>, r=75134429 +pos=<-8927983,72196971,41805506>, r=65500828 +pos=<18230519,71253951,55091105>, r=51783470 +pos=<-82741,89299947,70860177>, r=85357733 +pos=<19408526,70959236,391121>, r=77341247 +pos=<-118838868,96481794,83622656>, r=81565538 +pos=<7699857,77112966,58676603>, r=53204091 +pos=<-5285832,98989634,54909145>, r=84299424 +pos=<-9949091,79675756,62952022>, r=77691300 +pos=<6548040,71704033,79332787>, r=69603175 +pos=<41519552,70838659,77663756>, r=63492002 +pos=<24672816,51183711,105057962>, r=56683540 +pos=<26979282,57437475,67725517>, r=91990453 +pos=<-146316585,60113902,86014018>, r=74912650 +pos=<72430683,58332575,69349806>, r=73583276 +pos=<20029551,67957881,114673401>, r=87716194 +pos=<-12896053,72374875,79141839>, r=89527418 +pos=<10238771,77142540,70645372>, r=62663967 +pos=<-3216297,27169332,60070123>, r=61580077 +pos=<-23930209,54633761,66648944>, r=70327317 +pos=<-18679703,21196655,30842395>, r=93170631 +pos=<44655563,9533925,46538296>, r=63469153 +pos=<-59378193,54454082,43217955>, r=96795689 +pos=<24496603,92577304,64368811>, r=57563942 +pos=<-27053938,59501992,52024839>, r=63695171 +pos=<-9529140,74055507,52153025>, r=60852050 +pos=<44555529,104038871,53349626>, r=75414106 +pos=<-14679818,88223002,52168606>, r=80185804 +pos=<4552719,62659754,92650998>, r=75872423 +pos=<-19881238,63944538,24064643>, r=85942719 +pos=<16076790,55601668,101552666>, r=66191930 +pos=<21912528,118540961,52911368>, r=74654179 +pos=<-42123089,64929314,59158052>, r=91325104 +pos=<10936357,81890391,20134023>, r=77001665 +pos=<10351597,9179596,62138956>, r=68070751 +pos=<92774311,53165517,56634384>, r=76044462 +pos=<14950682,78188149,16646479>, r=72772458 +pos=<-36369450,41148166,38468120>, r=83283873 +pos=<78960321,78942802,53919616>, r=85293057 +pos=<-158664912,45952974,29905855>, r=62185933 +pos=<114294274,47756105,53682861>, r=94039744 +pos=<20046552,73002532,57617045>, r=54110780 +pos=<-29832468,53561561,86264939>, r=94773352 +pos=<5152614,124285693,53684633>, r=97932108 +pos=<31373573,67528454,85096814>, r=57468866 +pos=<-34521748,54572314,66408185>, r=80616625 +pos=<21670677,109269914,16882176>, r=96898951 +pos=<-13862893,59818682,65331199>, r=64127296 +pos=<17318835,71965542,106868073>, r=86629159 +pos=<78142676,48758577,56205332>, r=59408131 +pos=<-23340878,51182474,58635784>, r=58273523 +pos=<-26740311,87129579,52453722>, r=91438117 +pos=<4303903,69818029,63437040>, r=54065753 +pos=<3266332,71031490,81452081>, r=74331764 +pos=<13702746,18039813,44354215>, r=50433215 +pos=<-3482754,38377262,76574157>, r=67142882 +pos=<-9228255,63064015,42837554>, r=55636176 +pos=<-50838633,55818579,60038300>, r=91809905 +pos=<12044855,110909031,26804479>, r=98241104 +pos=<3069579,54401690,81614434>, r=58061261 +pos=<-55632341,51473141,61974878>, r=94194739 +pos=<47405039,61876630,72051227>, r=54803065 +pos=<-54699622,62927561,51595043>, r=94336968 +pos=<-5193725,62373908,96721874>, r=89403908 +pos=<39277912,51487063,98292773>, r=62527889 +pos=<28453914,55902735,104745928>, r=62572701 +pos=<70028230,51756434,45557821>, r=50764114 +pos=<6794251,79565242,72837497>, r=70723039 +pos=<-13346572,55208620,19942682>, r=74793897 +pos=<-26551619,52981805,64542889>, r=69190740 +pos=<-43505598,52177986,74471561>, r=95270055 +pos=<-36730243,57166097,70373519>, r=89384321 +pos=<67837280,44038045,5154880>, r=93530016 +pos=<24819569,59550660,112300422>, r=72145934 +pos=<22889616,60439671,109383201>, r=72047709 +pos=<16010141,59272902,95102320>, r=63479459 +pos=<45785695,3672162,40921594>, r=76077574 +pos=<52634264,230093674,55591446>, r=92328001 +pos=<-1093816,65699672,61755421>, r=53663391 +pos=<-2927319,46551949,115336543>, r=97175126 +pos=<9846871,97494787,27660769>, r=86168853 +pos=<14575046,54156478,106441784>, r=71137652 +pos=<3693372,64829888,65085318>, r=51336253 +pos=<-14475986,58191102,40490687>, r=58358086 +pos=<-32625219,54193671,54687567>, r=66620839 +pos=<19841368,112790310,53953991>, r=72017337 +pos=<-36529548,56646542,73106232>, r=91396775 +pos=<21383461,52564742,65263630>, r=69168248 +pos=<-25544951,69296904,55993281>, r=75949615 +pos=<5520910,41049609,87926413>, r=66818890 +pos=<78361286,55145660,70961730>, r=77938767 +pos=<-12502650,52118530,26315830>, r=64486867 +pos=<-8502681,43100643,60553969>, r=51419015 +pos=<30788480,91079544,72453023>, r=67791399 +pos=<-41582270,52471539,51548548>, r=70716745 +pos=<22495328,56368486,39214022>, r=54868649 +pos=<629350,38620684,-5628651>, r=92908951 +pos=<54092772,69401105,92313004>, r=89276951 +pos=<-5909105,43864786,12211016>, r=76363299 +pos=<3912827,52322153,79041627>, r=52565376 +pos=<-58023857,53967358,52040730>, r=89146355 +pos=<-31872996,52197859,61603944>, r=70789344 +pos=<15997340,97237977,68995404>, r=75350443 +pos=<-47277488,55104503,30071304>, r=98492088 +pos=<-8126606,68416175,57612004>, r=59269187 +pos=<-41526057,70666640,40848412>, r=97525664 +pos=<73462661,56792015,64535899>, r=68260624 +pos=<17561494,61650408,18024697>, r=52245702 +pos=<18999409,83239866,79157013>, r=68511878 +pos=<-17147426,82949543,58049486>, r=83260838 +pos=<-18999109,63366752,88314976>, r=95795304 +pos=<22782196,90426553,59952512>, r=52711323 +pos=<3870299,63602471,24263373>, r=61650297 +pos=<-28961118,57302888,47585264>, r=64860112 +pos=<-54015783,52509914,54351945>, r=85992387 +pos=<-31431674,55933418,55746724>, r=68226308 +pos=<6227367,990142,64669121>, r=82914608 +pos=<5035135,38115972,99202791>, r=81514672 +pos=<-33418983,63482456,38640418>, r=84442392 +pos=<-10795967,62940846,61879242>, r=60730704 +pos=<109337482,53196724,58133710>, r=94138173 +pos=<24242369,44107239,101663495>, r=58776882 +pos=<13836970,62942011,18092686>, r=57193751 +pos=<22307447,72298904,83902781>, r=59008632 +pos=<61542152,47395133,73538238>, r=61503948 +pos=<-24075040,59046188,54656470>, r=62892239 +pos=<2709891,16928362,83441813>, r=89266699 +pos=<18108186,51788474,56989142>, r=80851857 +pos=<8783157,59841041,97619446>, r=73792049 +pos=<-11464337,-1808695,45620039>, r=94183197 +pos=<-27362762,61729073,63812346>, r=78018926 +pos=<-16479685,60701430,70404170>, r=72700118 +pos=<18072359,95490781,46478814>, r=57121005 +pos=<22305099,61060570,52457431>, r=91124722 +pos=<-3144103,35052829,41802786>, r=52818565 +pos=<14700849,76137475,4759707>, r=82858288 +pos=<24087216,72433922,86093140>, r=59554341 +pos=<78515636,57323047,62505044>, r=71813766 +pos=<-24840821,74681746,64511653>, r=89148740 +pos=<-23826296,65180883,55787778>, r=69909354 +pos=<75346962,35126022,80923207>, r=94962783 +pos=<17008079,55328336,57579351>, r=53041203 +pos=<-7356211,68676554,73449531>, r=74596693 +pos=<-17162496,73932992,66248811>, r=82458915 +pos=<-136511398,24674918,81631631>, r=52044146 +pos=<17677665,60697644,59711178>, r=87163127 +pos=<-23195799,53013298,81013306>, r=82336819 +pos=<-11747126,98444482,59328815>, r=94634945 +pos=<5844912,56397886,77450074>, r=53117462 +pos=<-34509639,55837799,78666373>, r=94128480 +pos=<5904302,91792190,56962332>, r=67964633 +pos=<-17032381,59374519,60271759>, r=61793041 +pos=<126401,73284278,37689172>, r=61650102 +pos=<13058035,58217638,117787893>, r=88061922 +pos=<13828494,55793337,5715352>, r=62430875 +pos=<-38076711,68063369,58208411>, r=89462874 +pos=<11310783,64077677,47800713>, r=90266880 +pos=<71295692,59864191,53931657>, r=58561571 +pos=<-28401409,54456913,64786142>, r=72758897 +pos=<7099165,104942769,74968888>, r=97926943 +pos=<-13995801,56919587,69332174>, r=65361965 +pos=<-26207717,59423657,75475224>, r=86221043 +pos=<6284415,23177140,26461281>, r=70607154 +pos=<215192914,61945607,54981371>, r=57239098 +pos=<570884,53692018,83080045>, r=61315597 +pos=<82035008,70009886,45451263>, r=81130714 +pos=<56491702,68916341,58674725>, r=57552984 +pos=<41387757,67423761,76216212>, r=58497788 +pos=<-13813748,54323195,39213241>, r=55105070 +pos=<-6283377,38226161,58990807>, r=52511441 +pos=<-26649360,45588196,46247152>, r=61344017 +pos=<-14376863,65982584,89020987>, r=94494818 +pos=<-3323474,29138548,66137005>, r=65784968 +pos=<58981819,73400065,67082387>, r=72934311 +pos=<-24602073,59590457,54064654>, r=63371721 +pos=<36151757,93220459,79425935>, r=82268360 +pos=<87119215,67120469,66106290>, r=93816049 +pos=<-48564056,44611797,43001926>, r=87480464 +pos=<-184831138,45972224,52522771>, r=50154575 +pos=<-15029762,39315381,53334088>, r=54511484 +pos=<-63442720,56809824,159032480>, r=72599634 +pos=<60777021,86337479,55149072>, r=75733594 +pos=<92444973,55329391,26343979>, r=95967763 +pos=<-21559036,59753239,49501583>, r=57992092 +pos=<9746816,62098999,110099681>, r=87566354 +pos=<10180395,73435400,84209682>, r=72579076 +pos=<9869506,63811097,-18666569>, r=98789533 +pos=<-13838113,59406279,58751626>, r=57110750 +pos=<64073559,55987760,56938593>, r=50470036 +pos=<122002455,-29528127,89467426>, r=76860378 +pos=<933085,106082663,68426376>, r=98690342 +pos=<-2675758,105102702,49288669>, r=84671159 +pos=<21148930,85952702,88820154>, r=78738465 +pos=<-20327181,54015158,64694298>, r=64151435 +pos=<1808162,74371192,54758455>, r=52436239 +pos=<42135947,69930651,489911>, r=86113750 +pos=<-12374999,90510715,64743102>, r=92743325 +pos=<-4294480,65880302,57264170>, r=52553487 +pos=<-11380714,79284188,78361214>, r=94140720 +pos=<-18741699,56843996,93948119>, r=94648195 +pos=<-15112925,57666102,84178102>, r=82071526 +pos=<48905117,61145192,67255382>, r=50775815 +pos=<22577383,65607571,119314309>, r=87458960 +pos=<15014461,96714632,60980637>, r=67795269 +pos=<47428343,39689983,86775385>, r=68333041 +pos=<-28078465,61095714,45936858>, r=69419061 +pos=<-23524262,42214714,78362442>, r=85135301 +pos=<11059849,57287793,87820074>, r=59162425 +pos=<3565314,29345958,18633562>, r=74985191 +pos=<66387470,53690251,35786796>, r=58828200 +pos=<3116731,79442759,52841036>, r=54281677 +pos=<-19604720,61128015,61910900>, r=67758297 +pos=<57308392,70794674,32711619>, r=69928478 +pos=<12845664,78795191,27148691>, r=64982288 +pos=<80886361,60430853,61195181>, r=75982584 +pos=<23065226,55203444,121115562>, r=78368206 +pos=<-1767172,87142211,34592050>, r=80499249 +pos=<13751120,55697434,59007891>, r=91399024 +pos=<-21912028,56562619,52196254>, r=55785461 +pos=<24434582,75675617,15708816>, r=61713746 +pos=<-752271,77413609,96554782>, r=99835052 +pos=<17710144,89394902,70841612>, r=67640873 +pos=<-29164492,60989567,53774351>, r=69042803 +pos=<65721828,57739878,71302517>, r=68234456 +pos=<51294874,74255591,89905897>, r=88926704 +pos=<122447102,164387501,54549178>, r=86167801 +pos=<-2233409,26924269,59265799>, r=60037952 +pos=<3711632,67371720,79918709>, r=68693447 +pos=<-39313716,47720889,55898562>, r=72954666 +pos=<-29988637,48099743,66238336>, r=73590241 +pos=<7092311,93600756,55598390>, r=67221312 +pos=<94926391,52295037,52035414>, r=72727059 +pos=<58322954,64494143,14681677>, r=82672475 +pos=<-30606897,52115517,55916025>, r=63752817 +pos=<33683678,52234183,65402997>, r=77026018 +pos=<2893581,30919431,63800326>, r=55450312 +pos=<-10073625,68787754,42712060>, r=62330691 +pos=<-13226028,58548045,37442239>, r=60513212 +pos=<13341702,123874963,58254419>, r=93902154 +pos=<682234,97911898,48242929>, r=75168144 +pos=<18722317,56674681,90606505>, r=53673250 +pos=<90077460,56726877,60520864>, r=80795256 +pos=<11265077,100200311,67941274>, r=81990966 +pos=<10217162,21958720,59276183>, r=52563693 +pos=<82134787,48069587,56864579>, r=64748411 +pos=<20010404,57114507,56739832>, r=95448884 +pos=<298850,62853941,18970195>, r=69766264 +pos=<-34773033,48567904,55236028>, r=66904149 +pos=<3075957,26623236,63055783>, r=58819651 +pos=<16457975,57122257,70087795>, r=86513850 +pos=<90103819,53683092,69699596>, r=86956610 +pos=<-17689799,58550974,60782619>, r=62138075 +pos=<9338392,37129212,14441408>, r=65620968 +pos=<10278172,104026582,58505957>, r=77369117 +pos=<-36648669,53313763,57070182>, r=72147006 +pos=<3644850,75873038,60944199>, r=58286859 +pos=<-55768152,64438408,48348049>, r=98040163 +pos=<23966354,61323517,66723852>, r=63170986 +pos=<83907332,75993772,60160048>, r=93531174 +pos=<-49160977,51421296,51777959>, r=77474735 +pos=<-19554495,83185945,68889433>, r=96744324 +pos=<4083844,61211766,78812607>, r=61054908 +pos=<-28740891,76035877,59783586>, r=89674749 +pos=<1477390,92187674,62374371>, r=78199589 +pos=<27555445,100617770,28346459>, r=74363771 +pos=<61157488,92524005,67778649>, r=94930233 +pos=<44509108,57672466,-14457614>, r=91176410 +pos=<-49301441,57583231,64690420>, r=96689478 +pos=<6254148,63730492,98438208>, r=81029012 +pos=<-65249177,51697848,46584216>, r=96544404 +pos=<-18251430,74523624,66136947>, r=84026579 +pos=<-38032746,59650424,49516347>, r=74348754 +pos=<1025165,71664650,57908627>, r=53662668 +pos=<-47108245,52145065,40842431>, r=84592249 +pos=<-48768564,66546374,54932017>, r=95361722 +pos=<-21610139,44024485,61168243>, r=64217401 +pos=<10087091,107246375,62170269>, r=84443931 +pos=<51033289,57777223,79683838>, r=61964875 +pos=<-1515410,54504740,89312112>, r=70446642 +pos=<6955077,59969833,119903931>, r=98033598 +pos=<-22531794,48719765,58184485>, r=57459504 +pos=<-5094294,59314583,76395596>, r=65919004 +pos=<76187323,83948474,38225082>, r=96447759 +pos=<-21294072,54806425,61700229>, r=62915134 +pos=<22543466,42317235,91615254>, r=52217555 +pos=<28314112,89701628,91872856>, r=83358628 +pos=<-4228579,64941150,75051735>, r=69335866 +pos=<50966330,77605764,84252544>, r=86294744 +pos=<-6737743,107415917,54338071>, r=93606463 +pos=<23145972,65757098,91211071>, r=58936588 +pos=<19007479,87503572,82855617>, r=76466297 +pos=<-14765231,68331156,77316912>, r=85528263 +pos=<-949424,70946763,65236949>, r=62247745 +pos=<-32803143,52738611,60060225>, r=70716401 +pos=<66822816,56906431,65665714>, r=62865107 +pos=<9680974,91968172,80327678>, r=87729365 +pos=<8343767,56768063,52291322>, r=57842575 +pos=<38074555,75932657,94592379>, r=82069623 +pos=<-19059954,72759195,75265940>, r=92199655 +pos=<17867950,85793108,72307124>, r=65346674 +pos=<4765057,109187888,51558662>, r=81095880 +pos=<-18597182,56282648,71097542>, r=71091807 +pos=<-53544594,48732733,55083403>, r=85358259 +pos=<-14162311,76553349,71226487>, r=87056545 +pos=<-47205943,48535879,60516002>, r=84649054 +pos=<-51865413,61371035,54334719>, r=92685802 +pos=<-10560072,67389213,73620186>, r=76683871 +pos=<18319316,72506183,-3063602>, r=83431987 +pos=<-3588999,72423545,64377299>, r=65504222 +pos=<11888209,56845438,49310444>, r=80146809 +pos=<21726851,54782153,26405131>, r=94721944 +pos=<-21291084,56654299,74535249>, r=77595146 +pos=<936181,103600381,67588131>, r=95367106 +pos=<-13782512,64133232,74692014>, r=77722142 +pos=<-36410139,62335051,70838270>, r=94697845 +pos=<-13219359,55905482,102146596>, r=96385842 +pos=<7982302,72795551,71059219>, r=60987001 +pos=<14814723,60392314,88790377>, r=59482349 +pos=<-46730374,59535255,39966466>, r=92480718 +pos=<-12683668,63360272,34527358>, r=67698165 +pos=<34918460,61167889,51688378>, r=99658139 +pos=<65522795,5172637,52395633>, r=86564425 +pos=<21631208,32413943,104746960>, r=76164801 +pos=<-11979634,65490331,75294207>, r=77878552 +pos=<6957102,71949660,103009238>, r=93116178 +pos=<16501855,87396298,22166944>, r=74908909 +pos=<-3903540,38079649,95576440>, r=86863330 +pos=<20206463,69766028,75938015>, r=50611973 +pos=<4305930,14987890,73560026>, r=79729291 +pos=<-7564317,16601205,60800573>, r=77226681 +pos=<78960025,77022559,51882781>, r=81335395 +pos=<-2691592,55376094,83330088>, r=66512406 +pos=<-47250869,37081123,43153632>, r=93546119 +pos=<8536338,15031904,58255252>, r=60150014 +pos=<60376108,86278760,75828759>, r=95953668 +pos=<-6882477,55533881,67317545>, r=54848322 +pos=<9678384,78681532,76529906>, r=70647662 +pos=<10075511,91722489,53804756>, r=60566307 +pos=<21285284,59022109,91758839>, r=54610451 +pos=<-37992414,58278309,25526337>, r=96925765 +pos=<-2709806,59275400,67729392>, r=54828981 +pos=<7011597,20313939,78973760>, r=77111391 +pos=<-52588778,60847764,58672703>, r=97223909 +pos=<-15256628,22229514,41271494>, r=78285813 +pos=<34156359,101451279,54422671>, r=63500492 +pos=<21509300,111056381,53419268>, r=68080733 +pos=<14593452,57851278,-19237975>, r=88677170 +pos=<1781540,75186457,59902472>, r=58421778 +pos=<-33041189,51450575,51533175>, r=61139326 +pos=<15782750,66980930,90439887>, r=66752517 +pos=<-36107313,40071259,65952487>, r=87451603 +pos=<-14638698,63394833,75249799>, r=78397768 +pos=<-22832073,77228624,62320318>, r=87495607 +pos=<87393628,62821666,29411048>, r=95341264 +pos=<-16740099,42436581,56244211>, r=56010749 +pos=<20445816,54943259,60909642>, r=73012739 +pos=<15983434,51447682,96599706>, r=57178341 +pos=<-1059151,70062397,74572375>, r=70808526 +pos=<-35739090,59134133,40541874>, r=80512741 +pos=<22868206,41119100,92637902>, r=54114178 +pos=<13457096,20227235,89352457>, r=81131188 +pos=<53583940,59655001,69818825>, r=56527814 +pos=<37367140,55788282,41622861>, r=90197118 +pos=<12409098,92091021,58284823>, r=63081300 diff --git a/2018/src/day23.rs b/2018/src/day23.rs new file mode 100644 index 0000000..6246ee9 --- /dev/null +++ b/2018/src/day23.rs @@ -0,0 +1,492 @@ +use std::io; +use std::io::{BufRead, Write}; +use std::cmp; +use std::process::{Command, Stdio}; +use rand::prelude::*; + +const LARGE: i64 = i64::max_value() / 16; + +#[allow(dead_code)] +fn leq3(a: T, b: T, c: T) -> bool { + a <= b && b <= c +} + +#[derive(Clone, PartialEq, Eq, Debug)] +struct Pos { x: i64, y: i64, z: i64 } + +impl Pos { + fn new(x: i64, y: i64, z: i64) -> Self { + Pos { x, y, z } + } + + fn new_v(v: i64) -> Self { + Pos::new(v, v, v) + } + + #[used] + fn dist(&self, b: &Pos) -> i64 { + (self.x - b.x).abs() + (self.y - b.y).abs() + (self.z - b.z).abs() + } + + fn distf(&self, b: &FPos) -> f64 { + (self.x as f64 - b.x).abs() + (self.y as f64 - b.y).abs() + (self.z as f64 - b.z).abs() + } + + #[used] + fn dot(&self, b: &Pos) -> i64 { + self.x * b.x + self.y * b.y + self.z * b.z + } + + #[used] + fn add(&self, b: &Pos) -> Pos { + Pos::new(self.x + b.x, self.y + b.y, self.z + b.z) + } + + fn max(&self, b: &Pos) -> Pos { + Pos::new(cmp::max(self.x, b.x), cmp::max(self.y, b.y), cmp::max(self.z, b.z)) + } + + fn min(&self, b: &Pos) -> Pos { + Pos::new(cmp::min(self.x, b.x), cmp::min(self.y, b.y), cmp::min(self.z, b.z)) + } +} + +#[derive(Debug)] +struct Bot { + pos: Pos, + rad: i64, +} + +fn parse_bot(line: &str) -> Bot { + let mut numbers = vec![0]; + let mut multiplier = 1; + + for c in line.chars() { + if c == ',' { + numbers.push(0); + multiplier = 1; + } else if c == '-' { + multiplier = -1; + } else if let Some(dig) = c.to_digit(10) { + let last = numbers.last_mut().unwrap(); + *last = *last * 10 + multiplier * dig as i64; + } + } + + assert!(numbers.len() == 4); + Bot { + pos: Pos { x: numbers[0], y: numbers[1], z: numbers[2] }, + rad: numbers[3], + } +} + +#[derive(Clone, PartialEq, Eq, Debug)] +struct Intersection { + // If p is any point inside the bounds, then order the 8 planes by intersection with the rays: + // <(1, 1, 1)>, <(1, 1, -1)>, <(1, -1, 1)>, <(1, -1, -1)>, <(-1, 1, 1)>, <(-1, 1, -1)>, <(-1, -1, 1)>, <(-1, -1, -1)> + // Then represent a plane by the x-coordinate of its intersection with the x-axis. + // All bounds are inclusive. + bounds: [i64; 8], +} + +impl Intersection { + fn all() -> Self { + let pos = LARGE; + let neg = -LARGE; + Self { bounds: [pos, pos, pos, pos, neg, neg, neg, neg] } + } + + #[used] + fn empty() -> Self { + let pos = LARGE; + let neg = -LARGE; + Self { bounds: [neg, neg, neg, neg, pos, pos, pos, pos] } + } + + fn is_empty(&self) -> bool { + self.bounds[0] < self.bounds[7] + || self.bounds[1] < self.bounds[6] + || self.bounds[2] < self.bounds[5] + || self.bounds[3] < self.bounds[4] + } + + fn from_bot(bot: &Bot) -> Self { + let pos = bot.pos.add(&Pos::new(bot.rad, 0, 0)); + let neg = bot.pos.add(&Pos::new(-bot.rad, 0, 0)); + + let res = Self { + bounds: [ + pos.dot(&Pos::new(1, 1, 1)), + pos.dot(&Pos::new(1, 1, -1)), + pos.dot(&Pos::new(1, -1, 1)), + pos.dot(&Pos::new(1, -1, -1)), + neg.dot(&Pos::new(1, -1, -1)), + neg.dot(&Pos::new(1, -1, 1)), + neg.dot(&Pos::new(1, 1, -1)), + neg.dot(&Pos::new(1, 1, 1)), + ] + }; + + if res.bounds[0] - res.bounds[7] != 2 * bot.rad + || res.bounds[1] - res.bounds[6] != 2 * bot.rad + || res.bounds[2] - res.bounds[5] != 2 * bot.rad + || res.bounds[3] - res.bounds[4] != 2 * bot.rad { + println!("bot={:?}", bot); + println!("bounds={:?}", res.bounds); + assert!(false); + } + + res + } + + fn intersection(&self, o: &Self) -> Self { + Self { + bounds: [ + cmp::min(self.bounds[0], o.bounds[0]), + cmp::min(self.bounds[1], o.bounds[1]), + cmp::min(self.bounds[2], o.bounds[2]), + cmp::min(self.bounds[3], o.bounds[3]), + cmp::max(self.bounds[4], o.bounds[4]), + cmp::max(self.bounds[5], o.bounds[5]), + cmp::max(self.bounds[6], o.bounds[6]), + cmp::max(self.bounds[7], o.bounds[7]), + ] + } + } + + fn dist_origin(&self) -> i64 { + println!("{:?}", self); + let pts = self.all_points(); + println!("{} points in self", pts.len()); + let res = pts.iter().map(|p| p.dist(&Pos::new(0, 0, 0))).min().unwrap(); + println!("{}", res); + res + } + + fn contains(&self, pos: &Pos) -> bool { + leq3(self.bounds[7], pos.dot(&Pos::new(1, 1, 1)), self.bounds[0]) + && leq3(self.bounds[6], pos.dot(&Pos::new(1, 1, -1)), self.bounds[1]) + && leq3(self.bounds[5], pos.dot(&Pos::new(1, -1, 1)), self.bounds[2]) + && leq3(self.bounds[4], pos.dot(&Pos::new(1, -1, -1)), self.bounds[3]) + } + + fn all_points(&self) -> Vec { + (self.bounds[5] + self.bounds[6] ..= self.bounds[1] + self.bounds[2]).map(move |p1| { + (self.bounds[6] + self.bounds[7] - p1 ..= self.bounds[0] + self.bounds[1] - p1).map(move |p2| { + (-self.bounds[3] + p1 - p2 ..= -self.bounds[4] + p1 - p2).map(move |p3| { + println!("candidate {:?}", Pos::new(p1, p2, p3)); + Pos::new(p1, p2, p3) + }) + }).flatten() + }).flatten().filter(|p| self.contains(p)).collect() + } +} + +#[allow(dead_code)] +fn backtrack i64>(bots: &[Intersection], selected: &[usize], max_count: &mut i64, min_dist: &mut i64, count: i64, inter: Intersection, dist_func: &F) { + // println!("backtrack: max_count={} min_dist={} count={}", max_count, min_dist, count); + + if count > *max_count { + *max_count = count; + *min_dist = dist_func(&inter); + // println!("New max count: {} at dist {}; inter={:?}", count, *min_dist, inter); + } else if count == *max_count { + let d = dist_func(&inter); + if d < *min_dist { + *min_dist = d; + // println!(" New min dist: {}", d); + } + } + + let rest = selected.iter().map(|&i| i).filter(|&i| !inter.intersection(&bots[i]).is_empty()).collect::>(); + // println!("rest.len() = {}", rest.len()); + + if rest.len() as i64 + count < *max_count { + return; + } + + if rest.len() == 0 { + return; + } + + let inter2 = inter.intersection(&bots[rest[0]]); + backtrack(bots, &rest[1..], max_count, min_dist, count + 1, inter2, dist_func); + backtrack(bots, &rest[1..], max_count, min_dist, count, inter, dist_func); +} + +#[allow(dead_code)] +fn part2_via_backtracking(bots: &[Bot]) -> i64 { + let inters = bots.iter().map(|b| Intersection::from_bot(&b)).collect::>(); + let mut max_count = 0; + let mut min_dist = LARGE; + backtrack(&inters, &(0..inters.len()).collect::>(), &mut max_count, &mut min_dist, 0, Intersection::all(), &|_| 0); + min_dist = LARGE; + backtrack(&inters, &(0..inters.len()).collect::>(), &mut max_count, &mut min_dist, 0, Intersection::all(), &|i| i.dist_origin()); + min_dist +} + +fn partial_min<'a, T: PartialOrd>(a: &'a T, b: &'a T) -> Option<&'a T> { + match a.partial_cmp(b) { + Some(cmp::Ordering::Less) => Some(a), + Some(cmp::Ordering::Equal) => Some(a), + Some(cmp::Ordering::Greater) => Some(b), + None => None + } +} + +fn partial_max<'a, T: PartialOrd>(a: &'a T, b: &'a T) -> Option<&'a T> { + match a.partial_cmp(b) { + Some(cmp::Ordering::Less) => Some(b), + Some(cmp::Ordering::Equal) => Some(a), + Some(cmp::Ordering::Greater) => Some(a), + None => None + } +} + +#[derive(Clone, PartialEq, Debug)] +struct FPos { x: f64, y: f64, z: f64 } + +impl FPos { + fn new(x: f64, y: f64, z: f64) -> Self { + Self { x, y, z } + } + + fn from_pos(pos: &Pos) -> Self { + Self { x: pos.x as f64, y: pos.y as f64, z: pos.z as f64 } + } + + fn add(&self, b: &Self) -> Self { + Self::new(self.x + b.x, self.y + b.y, self.z + b.z) + } + + fn scale(&self, b: f64) -> Self { + Self::new(self.x * b, self.y * b, self.z * b) + } + + fn max(&self, b: &Self) -> Self { + Self::new(*partial_max(&self.x, &b.x).unwrap(), *partial_max(&self.y, &b.y).unwrap(), *partial_max(&self.z, &b.z).unwrap()) + } + + fn min(&self, b: &Self) -> Self { + Self::new(*partial_min(&self.x, &b.x).unwrap(), *partial_min(&self.y, &b.y).unwrap(), *partial_min(&self.z, &b.z).unwrap()) + } +} + +fn dist_weight(bot: &Bot, pos: &FPos) -> f64 { + let d = bot.pos.distf(pos); + if d <= bot.rad as f64 { + 1.0 + } else { + let x = d - bot.rad as f64; + 0.0009 / (x + 1.0) + } +} + +fn score_function(bots: &[Bot], pos: &FPos) -> f64 { + bots.iter().map(|bot| dist_weight(bot, pos)).sum() +} + +fn random_point_in_box(minpt: &FPos, maxpt: &FPos) -> FPos { + FPos::new(random::() * (maxpt.x - minpt.x) + minpt.x, + random::() * (maxpt.y - minpt.y) + minpt.y, + random::() * (maxpt.z - minpt.z) + minpt.z) +} + +fn random_point() -> FPos { + random_point_in_box(&FPos::new(-1.0, -1.0, -1.0), &FPos::new(1.0, 1.0, 1.0)) +} + +fn improve(bots: &[Bot], pos: FPos, heat: f64) -> (FPos, f64) { + let mut best_pos = pos.clone(); + let mut best_score = score_function(bots, &pos); + + for _ in 0..10 { + let pt = pos.add(&random_point().scale(heat)); + let sc = score_function(bots, &pt); + if sc > best_score { + best_score = sc; + best_pos = pt; + } + } + + (best_pos, best_score) +} + +fn containing_box(pts: &[FPos]) -> (FPos, FPos) { + let minpt = pts.iter().fold(FPos::new(1.0e34, 1.0e34, 1.0e34), |p1, p| p1.min(p)); + let maxpt = pts.iter().fold(FPos::new(-1.0e34, -1.0e34, -1.0e34), |p1, p| p1.max(p)); + (minpt, maxpt) +} + +#[allow(dead_code)] +fn anneal_maximum(bots: &[Bot]) -> FPos { + let minpt = FPos::from_pos(&bots.iter().fold(Pos::new_v(LARGE), |p1, bot| p1.min(&bot.pos))); + let maxpt = FPos::from_pos(&bots.iter().fold(Pos::new_v(-LARGE), |p1, bot| p1.max(&bot.pos))); + + let num_points = 100; + + let mut pts = Vec::new(); + for _ in 0..num_points { + pts.push(random_point_in_box(&minpt, &maxpt)) + } + + let mut heat = 1000000.0; + for iter in 0..16000 { + let mut best_score = 0.0; + + for i in 0..pts.len() { + match improve(bots, pts[i].clone(), heat) { + (p, s) => { + pts[i] = p; + if s > best_score { + best_score = s; + } + } + } + } + + if iter % 100 == 0 { + println!("iter={} heat={} best_score={} {:?}", iter, heat, best_score, containing_box(&pts)); + heat *= 0.9; + if heat < 1.0 { heat = 1.0; } + + pts.sort_by(|a, b| score_function(bots, b).partial_cmp(&score_function(bots, a)).unwrap()); + pts.truncate(num_points / 2); + + for _ in 0..num_points / 2 { + pts.push(random_point_in_box(&minpt, &maxpt)); + } + } + } + + pts.iter().max_by_key(|pt| score_function(bots, &pt) as i64).unwrap().clone() +} + +fn build_smtlib(bots: &[Bot]) -> String { + let mut res = String::new(); + res.push_str("(define-fun abs ((x Int)) Int (ite (< x 0) (- x) x))\n"); + + res.push_str("(declare-const x Int)\n"); + res.push_str("(declare-const y Int)\n"); + res.push_str("(declare-const z Int)\n"); + res.push_str("(declare-const nrange Int)\n"); + res.push_str("(declare-const distorigin Int)\n"); + + for i in 0..bots.len() { + res.push_str(&format!("(declare-const eq{} Int)\n", i)); + } + + for i in 0..bots.len() { + res.push_str(&format!("(assert (= eq{} (ite (<= (+ (abs (- x {})) (abs (- y {})) (abs (- z {}))) {}) 1 0)))\n", + i, bots[i].pos.x, bots[i].pos.y, bots[i].pos.z, bots[i].rad)); + } + + res.push_str("(assert (= nrange (+\n"); + for i in 0..bots.len() { + res.push_str(&format!(" (ite (<= (+ (abs (- x {})) (abs (- y {})) (abs (- z {}))) {}) 1 0)\n", + bots[i].pos.x, bots[i].pos.y, bots[i].pos.z, bots[i].rad)); + } + res.push_str(")))\n"); + + res.push_str("(assert (= distorigin (+ (abs x) (abs y) (abs z))))\n"); + res.push_str("(maximize nrange)\n"); + res.push_str("(minimize distorigin)\n"); + res.push_str("(check-sat)\n"); + // res.push_str("(get-model)\n"); + res.push_str("(eval distorigin)\n"); + + res +} + +#[allow(dead_code)] +fn build_cplex(bots: &[Bot]) -> String { + let minpt = &bots.iter().fold(Pos::new_v(LARGE), |p1, bot| p1.min(&bot.pos)); + + let isign = |c, case| if case & (1 << c) == 0 { "" } else { "-" }; + let sign = |c, case| if case & (1 << c) == 0 { "+" } else { "-" }; + let mul = |c, case, n: i64| if case & (1 << c) == 0 { n } else { -n }; + + let mut res = String::new(); + res.push_str("maximize 300000000 nrange - distorigin\n"); + + res.push_str("subject to\n"); + for i in 0..bots.len() { + for case in 0..8 { + // bC = bot.C - min.C + // ±(x - bx) + ±(y - by) + ±(z - bz) <= rad + 1e12 (1 - ei) + // ±(x + y + z) - ±(bx + by + bz) <= rad + 1e12 - 1e12 ei + // ±(x + y + z) - ±(bx + by + bz) + 1e12 ei <= rad + 1e12 + // ±x ± y ± z + 1e12 ei <= rad + 1e12 ± bx ± by ± bz + res.push_str(&format!(" {}x {} y {} z + 1000000000000 e{} <= {}\n", + isign(0, case), sign(1, case), sign(2, case), i, + bots[i].rad + 1000000000000 + mul(0, case, bots[i].pos.x - minpt.x) + mul(1, case, bots[i].pos.x - minpt.x) + mul(2, case, bots[i].pos.x - minpt.x))); + } + } + + res.push_str(" nrange"); + for i in 0..bots.len() { + res.push_str(&format!(" - e{}", i)); + } + res.push_str(" = 0\n"); + + for case in 0..8 { + // ±(x - mx) + ±(y - my) + ±(z - mz) <= distorigin + // ±(x + y + z) - ±(mx + my + mz) <= distorigin + // ±x ± y ± z <= distorigin - ±(mx + my + mz) + // ±x ± y ± z - distorigin <= - ±mx - ±my - ±mz + res.push_str(&format!(" {}x {} y {} z - distorigin <= {}\n", + isign(0, case), sign(1, case), sign(2, case), + -mul(0, case, minpt.x) - mul(1, case, minpt.y) - mul(2, case, minpt.z))); + } + + res.push_str("bounds\n"); + res.push_str(" 0 <= nrange\n"); + res.push_str(" 0 <= distorigin\n"); + res.push_str(" 0 <= x\n"); + res.push_str(" 0 <= y\n"); + res.push_str(" 0 <= z\n"); + + res.push_str("general\n"); + res.push_str(" nrange distorigin x y z\n"); + + res.push_str("binary\n"); + for i in 0..bots.len() { + res.push_str(&format!(" e{}", i)); + } + res.push_str("\n"); + + res.push_str("end\n"); + + res +} + +pub fn main(reader: T) -> io::Result<(String, String)> { + let bots = reader.lines().map(|l| parse_bot(&l.unwrap())).collect::>(); + + // println!("{}", build_smtlib(&bots)); + // println!("{}", build_cplex(&bots)); + + let largest = (0..bots.len()).max_by_key(|&i| bots[i].rad).unwrap(); + + let part1 = bots.iter().filter(|bot| bot.pos.dist(&bots[largest].pos) <= bots[largest].rad).count(); + + // let part2 = anneal_maximum(&bots); + // let part2 = part2_via_backtracking(&bots); + + let mut child = Command::new("z3") + .arg("-in") + .stdin(Stdio::piped()) + .stdout(Stdio::piped()) + .spawn() + .unwrap(); + + child.stdin.as_mut().unwrap().write_all(build_smtlib(&bots).as_bytes()).unwrap(); + + let output = String::from_utf8(child.wait_with_output().unwrap().stdout).unwrap(); + + let part2 = output.lines().last().unwrap().to_string(); + + // Ok((part1.to_string(), String::new())) + + Ok((part1.to_string(), part2)) +} diff --git a/2018/src/main.rs b/2018/src/main.rs index c45b084..aac9302 100644 --- a/2018/src/main.rs +++ b/2018/src/main.rs @@ -28,8 +28,9 @@ mod day19; mod day20; mod day21; mod day22; +mod day23; -static NUM_DAYS: i32 = 22; +static NUM_DAYS: i32 = 23; fn day_switch(day: i32, reader: T) -> io::Result<(String, String)> { match day { @@ -55,6 +56,7 @@ fn day_switch(day: i32, reader: T) -> io::Result<(String, String)> { 20 => day20::main(reader), 21 => day21::main(reader), 22 => day22::main(reader), + 23 => day23::main(reader), _ => Err(Error::new(ErrorKind::Other, "Invalid day")) } } -- cgit v1.2.3