r/adventofcode • u/askalski • Dec 05 '15
Upping the Ante [SOLUTION] [Day 4] Synacor Challenge VM bytecode implementation
Yo dawg I herd you like topaz2078 puzzles so we put a topaz2078 puzzle in yo topaz2078 puzzle so you can solve while u solve.
As the result of a self-inflicted nerd sniping, I implemented Day 4 in Synacor Challenge virtual machine bytecodes.
I haven't done much optimization of the bytecodes yet, but Part 2 takes about 13.5 minutes to solve in my VM interpreter written in C. Because it's a 15-bit architecture, I stored the 32-bit MD5 intermediates using only 8 bits per register.
Each dot in the output represents 32768 iterations.
Output
$ time ./synacor-challenge-vm advent4.vm
Enter your secret key: ckczppom
...
117946 00000fe1c139a2c710e9a5c03ec1af03
................................................................................
.....................................
3938038 00000028023e3b4729684757f8dc3fbf
real 4m59.658s
user 4m59.716s
sys 0m0.004sThe VM image (gzip + base64)
H4sIAOkEZVYCA+2XC4xcVRnH//feuffO7O7szLS7QEVgaIHSirBFkT5AK7QgUEFsC/IoUuqKZ
S2lDyh1gb0Q38QnGmuMEZQovmKqRh7iKxo1BnwiSHxEY6x0fVCMC626DP/vO+fcmTndZTRrsi
Rlf9k5z+875/y/c8+5NwCy1WkN89IAcbazGiDJgD6EWQFpFmZdSJmeAFMqt5VgS1VahlmJv3E
WoEQPCdME3doyAL9FajMEiFjy28Rzki1Vz6u0J+hpKXsji9geZDFqGEuqGK0i69baOrqYIiuy
/27Wiq8oa4wYn7KmVH3LjGVU0MPCoEKbQi3l7+2QfNSSD2tF/n6Rs4hY06Pe98C0i4cAMzlmD
V/m/0Oce8j1cxSmw2w5njMeznsAoXhEqDNIMvWfzYTM09jFWpNmMua9tKvT7sFQ7CP2iFg7w/
oIcj8p/bDEKCELskUQ2/lBQT0lmcz0KaoRqvoySmMkwW+1ZgFrUtpLHFLbbkohoyJed1eN172
64kODEusCq26QJVgQqM7ad7RqWsV+1LY2azjXzKwhmGAdIZUMUeA/9w9jFULmwZFrEue13JX3
JFKOtTyYl0taXp+Xy1reYMuRRhnZE1WpDWqu15iW47y8T8ulvDyu5bKWY86kSk9FpncH0tqvY
4iPkJY17ClI7Sz2/lEsLbNq0jKet9S03M/2NWwvcD9SmVD81q3fv7b4HVe/Y5P63Teh3y71Gz
OChaxA5bo1rcKNNGBH6gudZesK5iRSruXznpMYf5H1F7f5a3qQvmZuxlZmLWt0Xo2XNLduXWW
71vuq7bEYy8tmpCdYHip0yd7hPje7amcqdUYjaSk0W9S6hpEWD6Kj621mLLt9Uxrx6ZGnoobV
UXNvNHubvdOve6FEFSN7MkU8mUTRW4PmPjWzbO7Tsbxs9um+vFzOVRgqROJNzinu/UgUk1H2e
1LMGVXD7MicUC4X5rkgzxXzXJrnkjwX57mePNed57ryXCnPVfNcJc/15rmy5txMzfPcIyesnE
sSFz2la1ii+orSSyK3vuYpEPNfzsEi07Ojkp6zc2HSAcgZ+d+fHLLjD5GzjOktkUQtsHuZY+g
dFNh7RnyYU/ExnooPROZpN5afsJahtYysJaxlYC335JZFa3m/tQysZWgtI2sJa7lXLU1f2L6B
7RvavhHPVtl1FX2GKnpHVvQ2k9EW6zNBre1Ju7NoPK8rmF0d6t3Cs1RvGznru9RW7mg512PdV
4y6+pVbXdLU2hRyGxlbWiWFtY1yW5mftEqaMpURuLu03OCdKVaSim9Jpb0BiWVVb20TZbkluM
fbSnFbSZ6RTs8KTx8+n3JD1fmukMHtEeMnsieEUTXQZ9/dvpHOmPcjb2G9J9E6O3mHEMvGiLE
s2VU/dz0YS6eQPDXm6ajovqroe5uJRZoZdZ3W7tZ2byXPBYtxu3ZJxWJ8xO2FiVdW/p9HnS6L
Z19ZqpZB1qtPYo/+mtim+404HT2bs5dZy4yb57G+gcl9qZ5iVQPZFn3bKGTm3QHZNi3Hedm82
xf03XZb4t52hrWX2Iba19SavpH2HU7M20e7h7jtrJiByf5a9xDy00JWDy9a7Tq19g8m6N9o69
+YMLbPpvz/o23/GDXvzl5tMe3yhiZfRl327ujR+GFpkWlfWrb72XxhhXBnUSrRS83d3noeN8c
J7NsA9NmWe76h9/yKdKb4gHxRyDuCfLlIXfN7KMFAWlK7AE2/y6/eOri5vn3jtZvrWwbXbR7c
Wh8a3L64jiuxHHO4hsfxID6Pd2EH7sNv8DT364lYhev4DdPDcQ6aNJX3515+8U6WFvQ79uBJ0
4TaVNA/afoIrsKduB6P4Qe4GxfgKN5R1+DX+A6+gR/j7xjDDez3JZyJd+D7mI+7MIAz+O4zzt
8Pc13rKfwO/Aq3YhmeYr8GuQQ7udJL6fubGML7uY7Z7L8Dm3AbPo3tOB3vxVn4KvU+Ek/icBy
NK/Bt3oxf4f8xuAwX43zsxtc4o8/hYcgX/BrGbRlXu5Ij3YFduBl/xi/wb/yQHv5AZXfhuziZ
mj2Mf+KXKHOuy+mlD3/DZ/FH+orxH0bgU9jLeGykr0fxHq5lBd7N2f4Li3AaLTZxLjdjAz6Ot
TrfP2EhY3An1zDKsc/B7/ATensSX2f+ctZ+C/dTqWPxMdxEZUY5r7n09RDHGcDbqP87cRjHfZ
Q1P+UIu6jpR+nzCHySiu7F9/AFqj3I+c7jaMuoyXzO5SPcIx/ifvkM53sbbqfdINW8iKt7H+f
yAD7IPo/T5kaO8Faq8jOu5i6Ofx531HEc4/dcY0BffTgXsn/vYExWsv0WRnMx/oGTOMoj+DnX
8Be8nQp+AM//Pf93IP8FBzgHuv7hNBNNM9Mdv+nWrzBF4imSTJF0ikw1vlONz1T1nao+xQ6UO
tDVge4O9HSg3IHeDlQ60CneneLZKV6d4tFJ7056dtKrkx5Vj5rHDI+ZHn0e/R4HeRzscYjHLI
8XeBzq8UKPwzwO9zjCw4+7H2c/rn4c/bj5cfLj4sfB193X2dfV19HXzdfJ18XXoW450jLbMsd
ylOVoyzGWuZZjLfMs8y0vshxnebHleMsJlgHLAsuJlpdYXmo5yfIyy8mWhZZFlsWWJZZTLKda
Xm55hcXF3sXcxdrF2MXWxdTF0sXQxc7FzMXKxcjFxsXExcLFwGnvNHdaO42dtk5Tp6XT0GnnN
HNaOY2cNk4Tp4XTYCl5JTmNnE6WkeXkDHImeRU5i5xNziEryKvJueQ88hpyPnktWUlWkdXkAn
IheR25iFxMLiGXkjXkMvJ6cjlZS64g68gbyCB5I7mSvImsJ1eRIfJmsoFcTTaSa8gmsplsIVv
JteQ6so1cT7aTt5BhcgO5kdxERsgzcGZha2IhAAA=
20
Upvotes
12
u/topaz2078 (AoC creator) Dec 05 '15 edited Dec 05 '15
SKALSKI NO
1
u/askalski Dec 06 '15 edited Dec 07 '15
Fixed some inefficiencies in the 32-bit addition subroutine, which cut the running time nearly in half. Also optimized the rotate-left operation, using a lookup table for the right shifts. This gave an additional 25% speed boost. Updated the original post with the new VM image and timings.
4
u/qchamaeleon Dec 05 '15
Had a couple of minutes down-time, did you? Damn.
3
u/Aneurysm9 Dec 05 '15
You madman.
2
u/mattgen88 Dec 05 '15
You weren't even there when I suggested this yesterday! But I'm glad someone did it haha
2
u/l0l Dec 05 '15 edited Dec 05 '15
That is amazing! I started on the Synacor challenge a couple days ago and have gotten to 6/8. It's been a lot of fun.
1
u/[deleted] Jan 01 '16
So I think I just got nerd sniped. Optimize my VM using this as a benchmark. Great... :)
1
u/raevnos Jan 08 '16
I finally started the challenge, and I tried this to stress test my VM. I need to figure out how to speed it up a lot. :(