# Advent of Code 2017 #3

Camden Hernandez

Advent of Code is a series of small programming puzzles for a variety of skill levels. They are self-contained and are just as appropriate for an expert who wants to stay sharp as they are for a beginner who is just learning to code. Each puzzle calls upon different skills and has two parts that build on a theme.

Daniel Phillips

you need to analyze the real meaning of the inner loop and replace it with an efficient O(1) implementation.

I chose to translate the puzzle input into (invalid) Java with gotos first, then eliminated gotos (fortunately there are no intersections, so they translate into while-do nicely), and started looking from there.

Sebastian Anderson

so in order to get the second star I had to replace code which looked like this (after trivial simplifications):

long e = 2;
do {
if (e * d == b) {
f = 0;
}
e += 1;
} while (e != b);

with this code:

if (((b % d) == 0) && ((b / d) >= 2) && ((b / d) <= b)) {
f = 0;
}

Benjamin Perez

day 20. void particle_swarm(string_view input)
{
struct particle_t { int64_t p[3], v[3]; int8_t a[3]; };
vector<particle_t> particles;
int8_t mina = uint8_t(~0u) >> 1;
int16_t i = 0, mini = 0;
for (string_view line : input | split(by_line)){
auto [px, py, pz, vx, vy, vz, ax, ay, az, _] = parse_n<9>(line, by_int);
particles.push_back({{to<int64_t>(px), to<int64_t>(py), to<int64_t>(pz)},
{to<int64_t>(vx), to<int64_t>(vy), to<int64_t>(vz)},
{to<int8_t>(ax), to<int8_t>(ay), to<int8_t>(az)}});
if (int8_t a = abs(particles.back().a[0]) + abs(particles.back().a[1]) + abs(particles.back().a[2]); a < mina)
mina = a, mini = i;
++i;
}
cout << "part 1: " << mini << '\n';
unordered_map<u32string, size_t> colcheck;
vector<size_t> collided;
for (int i = 0, j = 0; i < 40; ++i, j = 0, colcheck.clear(), collided.clear()){
for (auto& part : particles){
auto key = u32string((char32_t*)&part.p, 6);
if (auto it = colcheck.find(key); it != colcheck.end()){
if (it->second != ~0u){
collided.push_back(it->second);
it->second = ~0u;
}
collided.push_back(j);
} else
colcheck.emplace(move(key), j);
for (int k = 0; k < 3; ++k)
part.p[k] += part.v[k] += part.a[k];
++j;
}
for (size_t k = collided.size(); k --> 0;)
particles.erase(particles.begin() + collided[k]);
}
cout << "part 2: " << particles.size() << '\n';
}

Jackson Thompson

some languages like python have special meaning for accessing negative indices for example.

Charles Jones

day 23: I added registers and an instruction display "<-- you are here") to day18 code, and made it so that you can C-c, alter registers, and then resume the simulation. The "decompile this assembler" task can go fuck itself.

Aaron Ortiz

made it so that you can C-c, alter registers, and then resume the simulation
why do you need this?

Ian Thomas

The "decompile this assembler" task can go fuck itself.
you don't need to decompile all of the code.
the relevant part is quite easy if you don't give up because it looks scary. I am not a reverse engineer of any kind yet managed to get into the global leaderboard with this one.

Angel Ramirez

you don't. it's much, much harder to complete the task with any feat of programming than by rewriting the assembler.
I believe you. I don't want to do it.

Kevin Jackson

Took me a while to get the second part of today's puzzle. Ran into my answer being off by one and thinking that h incremented for the opposite condition it actually does

Blake Sanchez

Took a break and went back to it, mine looks like a primality test

Easton Perez

... which Mathematica can figure out for me, instead of optimizing the code.

Count[Range[107900, 124900, 17], _?CompositeQ]

Nolan Bennett

It's the opposite

Owen Green

Heh, yeah I figured that as soon as I hit reply and went back to it. Best puzzle so far (2nd is the dancers).

Juan Jackson

who knows, maybe in my case the bigger picture is also primality test.
I only optimized the inner loop (which is a test for divisibility by a specific number + some bounds) and it was fast enough to get the answer so I didn't look further. I won't bother to do it, fuck this task already.

the simplified code looked like this at that point:

public class Main {
public static void main(String[] args) {
long a = 1, b = 0, c = 0, d = 0, f = 0, g = 0, h = 0;

b = 108400;
c = b + 17000;
do {
f = 1;
d = 2;
do {
// REPLACEMENT START
if (((b % d) == 0) && ((b / d) >= 2) && ((b / d) <= b)) {
f = 0;
}
// OPTIMIZED ABOVE, SOURCE BELOW
// long e = 2;
// do {
// if (e * d == b) {
// f = 0;
// }
// e += 1;
// } while (e != b);
// REPLACEMENT END
d += 1;
g = d - b;
} while (g != 0);
if (f == 0) {
h += 1;
}
g = b - c;
b += 17;
} while (g != 0);

System.out.println(h);
}
}

Grayson Allen

I liked this one. It actually made me give up at first <excuse>It was very busy and LOUD at my place (muh autism)</excuse>, so that didn't help, but I enjoyed working it out when I went back to it.

Ryan Hernandez

…and if the "assembly" was like 100x larger, I'd probably write a simple decompiler myself, which would at the very least convert relative jumps to goto with labels (outputting C code which supports that), or maybe also try to eliminate goto where possible(it is not possible in the general case and the algorithm must be funny). but of course I am too lazy to do that without any kind of reward lol.

Alexander Bennett

I almost wrote a graph to show where the jumps were occuring, but it was easy enough to do it with a text editor, and inserting labels, so I could keep track.

Easton Watson

Your disassembly was a bit strange. Here's the pseudocode I came up with.
b = 105700
for (n = 0; n < 1000; n++) {
f = 1
for (d = 2; d < b; d++) {
for (e = 2; e < b; e++) {
if (d * e == b) {
f = 0
}
}
}
b += 17
}
if (f == 0) {
h++
}
}

Bentley Turner

Heh.
< Problems worthy of attack, prove their worth by fighting back.

Angel Smith

it's because I didn't bother to simplify the code any more when I spotted where is the slow part and how to rewrite it.
I think all these `do`-`while` loops must be possible to translate to `for`, and it'd be shorter after that.

Dominic Ross

day 21. void fractal_art(string_view input)
{
const auto by_pattern = +[](char c){ return c == '.' || c == '#' || c == '/'; };
const auto no_slash = +[](string_view sv){ string s; copy_if(begin(sv), end(sv), back_inserter(s), [](char c){ return c != '/'; }); return move(s); };
unordered_map<string, string> rules;
for (string_view line : input | split(by_line)){
auto [from_, to_, _] = parse_n<2>(line, by_pattern);
string from = no_slash(from_), to = no_slash(to_);
int8_t sz = 2 | (from.size() & 1);
const auto rotations = [&]{
int8_t i = 0; do {
rules[from] = to;
string rot(from.size(), '\0');
for (int8_t j = 0; j < sz; ++j)
for (int8_t k = 0; k < sz; ++k)
rot[sz * (sz - k - 1) + j] = from[sz * j + k];
from = move(rot);
} while (++i < 4);
};
rotations();
if (sz == 3){
for (int8_t j = 0, sz2 = sz * sz; j < sz2; j += sz)
swap(from[j], from[j + sz - 1]);
rotations();
}
}
string buf1 = ".#...####", buf2, * from = &buf1, * to = &buf2; size_t sz = 3;
const auto generate_art = [&](size_t n){
for (size_t i = 0, nsz, subsz; i < n; ++i, sz = nsz, swap(buf1, buf2)){
if (sz & 1) nsz = sz + sz / 3, subsz = 3;
else nsz = sz + (sz >> 1), subsz = 2;
to->resize(nsz * nsz);
string subfrom(subsz * subsz, '\0'), subto;
size_t sz2 = sz * sz, sz_subsz = sz * subsz, nsz_subsz = nsz * subsz;
for (size_t j = 0, jj = 0; j < sz2; j += sz_subsz - sz, jj += nsz_subsz)
for (size_t jend = j + sz; j < jend; j += subsz, jj += subsz + 1){
for (size_t a = 0, b = 0; a < sz_subsz; a += sz, b += subsz)
for (size_t c = 0; c < subsz; ++c)
subfrom[b + c] = (*from)[j + a + c];
subto = rules[subfrom];
for (size_t a = 0, b = 0; a < nsz_subsz + nsz; a += nsz, b += subsz + 1)
for (size_t c = 0; c < subsz + 1; ++c)
(*to)[jj + a + c] = subto[b + c];
}
}
};
generate_art(5);
cout << "part 1: " << count(begin(*from), end(*from), '#') << '\n';
generate_art(13);
cout << "part 2: " << count(begin(*from), end(*from), '#') << '\n';
}

Jose Green

I was going back to problem 22, interesting background for that: en.wikipedia.org/wiki/Langton's_ant.

Jordan Wilson

day 22. constexpr array<int8_t, 5> sporifica_virus_dirs[4] = {{-1, 0, 3, 2, 1}, {1, 0, 2, 3, 0}, {0, -1, 0, 1, 3}, {0, 1, 1, 0, 2}};
struct carrier_t { array<int32_t, 2> xy; const array<int8_t, 5>* dir; };
uint8_t& at(unordered_map<uint64_t, uint8_t>& grid, const array<int32_t, 2>& xy) { return grid[*(const uint64_t*)&xy[0]]; };
auto make_sporifica_virus(string_view input)
{
unordered_map<uint64_t, uint8_t> grid;
vector<string_view> grid_center;
for (string_view line : input | split(by_line))
grid_center.push_back(line);
for (int32_t w2 = grid_center[0].size() / 2, h2 = grid_center.size() / 2, y = -h2; y <= h2; ++y)
for (int32_t x = -w2; x <= w2; ++x)
at(grid, {x, y}) = uint8_t(grid_center[y + h2][x + w2] == '#') << 1;
return pair(move(grid), carrier_t{{0, 0}, &sporifica_virus_dirs[2]});
}
void sporifica_virus1(string_view input)
{
auto [grid, carrier] = make_sporifica_virus(input);
size_t infection_counter = 0;
for (int i = 0; i < 10'000; ++i){
uint8_t& cur = at(grid, carrier.xy);
carrier.dir = &sporifica_virus_dirs[(*carrier.dir)[2 | (cur >> 1)]];
infection_counter += (cur ^= 2) >> 1;
carrier.xy[0] += (*carrier.dir)[0]; carrier.xy[1] += (*carrier.dir)[1];
}
cout << "part 1: " << infection_counter << '\n';
}
void sporifica_virus2(string_view input)
{
auto [grid, carrier] = make_sporifica_virus(input);
size_t infection_counter = 0;
for (int i = 0; i < 10'000'000; ++i){
uint8_t& cur = at(grid, carrier.xy);
switch (cur){
break; case 0: carrier.dir = &sporifica_virus_dirs[(*carrier.dir)[2]];
break; case 1:
break; case 2: carrier.dir = &sporifica_virus_dirs[(*carrier.dir)[3]];
break; case 3: carrier.dir = &sporifica_virus_dirs[(*carrier.dir)[4]];
}
infection_counter += (++cur &= 3) == 2;
carrier.xy[0] += (*carrier.dir)[0]; carrier.xy[1] += (*carrier.dir)[1];
}
cout << "part 1: " << infection_counter << '\n';
}

David Fisher

Hi magicgoose

Logan Myers

Landon Brooks

I would never do that, say Hi to him for me.

Easton Torres

say Hi to him for me
nope, why would I?

Thomas Diaz

Daniel Lopez

I'm a free man and I'm not a number

Benjamin Long

I am not.

Liam Lee

Pretty fun one. Unfortunately I accidentally deleted the code for part 1. But it was basically the same as day 18 (>>841463).
fn main() {
let mut count = 0;

for i in 0..1001 {
let b = 105700 + i * 17;

for j in 2..b {
if b % j == 0 {
count += 1;
break;
}
}
}

println!("Part 2: {}", count);
}

Gabriel Gonzalez

day 23. Oh part 2, you and your silly prime numbers. void coprocessor_conflagration(string_view input)
{
static uint64_t mul_count = 0;
unordered_map<int, int64_t> data; int cur_data = 0;
const auto val_or_reg = [&](string_view x){ return isalpha(x[0]) ? &data[x[0]] : &(data[--cur_data] = to<int64_t>(x)); };
vector<ins_t<size_t(*)(int64_t*, int64_t*, size_t)>> prog;
for (string_view line : input | split(by_line)){
auto [ins, x, y, _] = parse_n<3>(line, by_word);
switch (line[2]){
break; case 't': prog.push_back({+[](int64_t* to, int64_t* from, size_t pc){ *to = *from; return pc + 1; }, &data[x[0]], val_or_reg(y)});
break; case 'b': prog.push_back({+[](int64_t* to, int64_t* from, size_t pc){ *to -= *from; return pc + 1; }, &data[x[0]], val_or_reg(y)});
break; case 'l': prog.push_back({+[](int64_t* to, int64_t* from, size_t pc){ *to *= *from; ++mul_count; return pc + 1; }, &data[x[0]], val_or_reg(y)});
break; case 'z': prog.push_back({+[](int64_t* to, int64_t* from, size_t pc){ return pc + size_t(*to ? *from : 1); }, val_or_reg(x), val_or_reg(y)});
}
}
for (size_t pc = 0, sz = prog.size(); pc < sz;)
pc = prog[pc].op(prog[pc].to, prog[pc].from, pc);
cout << "part 1: " << mul_count << '\n';

static constexpr auto test = [](int64_t v){
if (!(v & 1))
return false;
for (int64_t a = 3; a <= sqrt(v); a += 2)
if (v % a == 0)
return false;
return true;
};
int64_t h = 0;
for (int64_t inib = 84 * 100 + 100000, b = inib;; b += 17) {
if (!test(b))
++h;
if (b == inib + 17000)
break;
}
cout << "part 2: " << h << '\n';
}
Finally caught up!

Jaxson Price

well the contest is almost over.
did anyone learn anything? I learned
forth is a meme
you can create mutable circular lists in OCaml without resort to magic
rust is such an onerous language to use properly that all of the advent examples were written in an improper dialect
c++ is such a verbose language that in practice nobody will be able to run your snippets because they won't know to pass -std=c++cy+2^(-0_0-)7 or to add required boilerplate
real-world python is actually a completely unreadable mess!

Noah Martinez

c++ is such a verbose language that in practice nobody will be able to run your snippets because they won't know to pass -std=c++cy+2^(-0_0-)7 or to add required boilerplate
Didn't think anyone else would be interested in actually running my code, though. It wouldn't be too hard for me to provide a header file with all the necessary #includes/helper functions if someone asked.

Easton Robinson

Didn't learn any major concepts, but it was nice to discover the formal names for a few of these problems. For instance, I wasn't aware of Langton's Ant. If anything, it just rekindled a desire to do more low-level coding.

Jaxson James

(cont.)
Mathematica prices: \$320 for "home and hobby"; \$2700 for a single user industry license.

Tyler Allen

why just low level coding?
I only remember the knothash stuff as sort of low level. A lot of the rest was just weird. Implement a little VM; do some stuff with tiles or hextiles.

Jayden Rivera

Just for practise really. I solved these problems in a high level language Mathematica, and want to see it from another perspective.

Matthew Gonzalez

real-world python is actually a completely unreadable mess
real-world
golfed
LOL

Cameron White

353 bytes

from collections import defaultdict as D
C=D(lambda:D(int))
for l in open('i'):a,b=map(int,l.split('/'));C[a][b]+=1;C[b][a]+=1
def M(a,b,c):
d=C[c];e=set(k for k,v in d.items()if v>0)
if not e:return a,b
l=m=0
for f in e:
d[f]-=1;C[f][c]-=1;g,h=M(a+1,c+b+f,f)
if g>l or(g==l and h>m):m=h;l=g
d[f]+=1
C[f][c]+=1
return l,m
print(M(0,0,0)[1])

Part 1 is similar but a bit easier, I am too lazy to integrate it here

Evan Parker

I learned
decompiling code is not always hard as fuck
python is okay even for brute force solutions, just throw pypy at it if cpython takes too long (well I knew it already but now it is battle tested)
some forgotten tricks for golfing python
I should be solving more of challenges similar to these in free time (project euler, etc) because it's somewhat painful when you didn't do brain fitness for a long time

Justin Nelson

\$ time pypy3 yoba.py
1673

real 0m0.545s
user 0m0.511s
sys 0m0.029s

Kevin Walker

day 24. template<typename Ret, typename Maxcheck>
Ret elec_moat_rec(int8_t last, unordered_multimap<int8_t, int8_t>& pieces, uint8_t depth, Maxcheck&& m)
{
Ret maxv{};
for (auto [it, end] = pieces.equal_range(last); it != end; ++it)
if (it->second != -1){
int8_t pins = exchange(it->second, -1);
auto [it2, end2] = pieces.equal_range(pins);
for (; it2 != end2; ++it2)
if (it2->second == last)
break;
it2->second = -1;
if (auto res = elec_moat_rec<Ret>(pins, pieces, depth + 1, m); m(res, maxv, last + pins))
maxv = res;
it->second = pins;
it2->second = last;
}
return maxv;
}
void electromagnetic_moat(string_view input)
{
unordered_multimap<int8_t, int8_t> pieces;
for (string_view line : input | split(by_line)){
auto [as, bs, _] = parse_n<2>(line, by_num);
int8_t a = to<int8_t>(as), b = to<int8_t>(bs);
pieces.emplace(a, b);
pieces.emplace(b, a);
}
cout << "part 1: " << elec_moat_rec<uint16_t>(0, pieces, 0, [](auto& res, auto maxv, auto strength){
res += strength;
return res > maxv;
}) << '\n';
cout << "part 2: " << elec_moat_rec<pair<uint8_t, uint16_t>>(0, pieces, 0, [](auto& res, auto maxv, auto strength){
++res.first;
res.second += strength;
return res > maxv;
}).second << '\n';
}

Carter Gonzalez

OCaml. nothing clever. fastest part2 so far.

Leo Thomas

thatsthejoke.webm

Chase Evans
Thomas Sullivan

easy day, but part 2 is gated on my completing day 21 and part 2 of day 23, and neither of those are ever happening.
Still, look at that nice loop.

Luis Nguyen

day 25 sucks, translating code by hand is not fun. at least if it were a lot bigger, it would make sense to automate that.
начали за здравие, кончили за упокой.

Joshua Nelson

part 2 requires all stars
Suck my dick.

Justin Thomas

according to pic related part 2 was probably not that challenging anyway.

Jaxson Price

there's no challenge at all, the only challenge is that you need to have all the other stars

John Moore

I've tried a few other ways to do this, but avoiding pattern-matching just means avoiding speed. (marginally in this case)

Joshua Gutierrez

you should program a FPGA for this task.

Christopher Young

Very fun puzzle. Wrote a macro that generated the state machine. Very disappointing that there isn't a part 2 though.
play.rust-lang.org/?gist=a8cb154611aef9f2bbcdcd1a48e63a87

Oliver Jackson

You will fall to crippling depression before you reach 30.

Landon Peterson

Next step would be writing a procedural macro that parses the input and generates the state_machine! macro invocation. But I don't want to parse stuff.

Noah Morales

Well at least I will be a wizard by then.

Brayden Allen

Explain Rust macros to me please.

>>/fringe/

Landon Clark

afaik semantically basically like Clojure macros but with the added complexity of satisfying type checker.

Caleb Edwards

Well there is a chapter about them in the book which explains the basics: doc.rust-lang.org/stable/book/first-edition/macros.html
Then there is a pretty in depth intro here: danielkeep.github.io/practical-intro-to-macros.html

Ethan Johnson

And day 25. Ends with an easy one. void halting_problem(string_view input)
{
int8_t state = input[15] - 'A';
auto [n_iter_s, _] = parse_n<1>(input, by_num);
size_t n_iter = to<size_t>(n_iter_s);
struct state_t { int8_t write[2], moved[2], next[2]; };
vector<state_t> spec;
for (size_t state_descr; (state_descr = input.find("In", 1)) != string_view::npos;){
input.remove_prefix(state_descr);
int8_t this_state = input[9] - 'A';
if (spec.size() < this_state + 1) spec.resize(this_state + 1);
for (int8_t i = 0; i < 2; ++i, input.remove_prefix(116)){
spec[this_state].write[i] = input[63] - '0';
spec[this_state].moved[i] = input[93] == 'l' ? -1 : (input.remove_prefix(1), 1);
spec[this_state].next[i] = input[125] - 'A';
}
}
deque<int8_t> tape(1, 0);
size_t pos = 0;
for (size_t i = 0; i < n_iter; ++i){
int8_t cur_val = tape[pos];
tape[pos] = spec[state].write[cur_val];
if (spec[state].moved[cur_val] == -1){
if (pos == 0)
tape.push_front(0);
else
--pos;
} else {
if (pos == tape.size() - 1)
tape.push_back(0);
++pos;
}
state = spec[state].next[cur_val];
}
cout << "part 1: " << count(begin(tape), end(tape), 1) << '\n';
cout << "There is no part 2." << '\n';
}

Hunter Thomas

Days 24 and 25, better late than never. There's a builtin function in Mathematica for running Turing machines, but unfortunately it suited for massive inputs like this problem, and I had to roll my own. Merry Christmas, and hopefully Santa brought you lots of proprietary software and Apple products.

Jaxson Gonzalez

Diagram for the first 400 iterations, not too exciting.

Austin Gonzalez

Merry Christmas, and hopefully Santa brought you lots of proprietary software and Apple products.
Merry Grav-Mass, and also go eat a dick.

Ian Cooper

D-did we get beaten by 4/g/? Hopefully that one poster is just an outlier.

Lincoln Butler

beaten
by mostly python
in a cooking contest, the guy who shits in the bowl finishes first, but he doesn't win :^)

Camden Wood

I did it in 50 lines and it's super clear what's going on, it's basically like a normal language except that it takes 8G of RAM
<a naive solution in a real language sips kilobytes
I did it in a natural way and it took 1 hour to run so I changed an import and then it took 8s and then I added jumping jacks and now it takes 1s
<a naive solution in a real language takes <1ms
I did it in a single line and the logic is so dense that explaining it would take 12 pages of an academic paper. Nobody will ever be able to alter this program for any reason but what do you want, that 50-line bullshit that that total noob wrote?
<in a real language hiring a 'Lang Programmer' is usually well enough to get your 'Lang code' hacked on, unless the code is really obviously obfuscated
christ, imagine having to hire a Haskell guy. Imagine code review.
OTOH with the Haskell community the way it is, you could literally terrorize Haskell projects by showing up, rewriting essential bits of their code to be completely inscrutable, and then laughing as the project collapses when the maintainers can't bring themselves to reject or to simplify the knot.

Carter Baker

you forgot something:
Mostly python, some rust.

Michael Hall

I've mentioned it before on the board, but a while back when I was really into Haskell, I'd write programs that I couldn't even understand myself just 6 months later due to the point-free style and ridiculous abstractions. I thought knowing both of those made me very smart. While elegant, the programs were horrible to refactor, and in producing real world code, I ended up being less productive than low-skilled ruby programmers.

Henry Kelly

Now that the competition is over, are any of you doing any of the other challenges, like Project Euler? For AoC there are years 2015 and 2016 if you haven't got around to them yet.

Jaxon Wood

haskell is a meme language. are there any haskell projects that haven't fizzled and failed because it's like programming with a straight-jacket on?

Alexander Harris

so that means haskell is a trolling language