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.
adventofcode.com
Previous thread:
Other urls found in this thread:
en.wikipedia.org
play.rust-lang.org
play.rust-lang.org
play.rust-lang.org
doc.rust-lang.org
danielkeep.github.io
reddit.com
twitter.com
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.
okay, the leaderboard is filled.
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)
day 20. void particle_swarm(string_view input){ struct particle_t { int64_t p[3], v[3]; int8_t a[3]; }; vector 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(line, by_int); particles.push_back({{to(px), to(py), to(pz)}, {to(vx), to(vy), to(vz)}, {to(ax), to(ay), to(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 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
some languages like python have special meaning for accessing negative indices for example.
day 23: I added registers and an instruction display "
why do you need this?
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.
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.
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
Took a break and went back to it, mine looks like a primality test
... which Mathematica can figure out for me, instead of optimizing the code.
Count[Range[107900, 124900, 17], _?CompositeQ]
It's the opposite
Heh, yeah I figured that as soon as I hit reply and went back to it. Best puzzle so far (2nd is the dancers).
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)
I liked this one. It actually made me give up at first It was very busy and LOUD at my place (muh autism), so that didn't help, but I enjoyed working it out when I went back to it.
…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.
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.
Your disassembly was a bit strange. Here's the pseudocode I came up with.
b = 105700for (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++ }}
Heh.
< Problems worthy of attack, prove their worth by fighting back.
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.
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 rules; for (string_view line : input | split(by_line)){ auto [from_, to_, _] = parse_n(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
I was going back to problem 22, interesting background for that: en.wikipedia.org
day 22. constexpr array 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 xy; const array* dir; };uint8_t& at(unordered_map& grid, const array& xy) { return grid[*(const uint64_t*)&xy[0]]; };auto make_sporifica_virus(string_view input){ unordered_map grid; vector 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
Hi magicgoose
Hi but please don't find me by IP address
I would never do that, say Hi to him for me.
nope, why would I?
Is he not your leader?
I'm a free man and I'm not a number
I am not.
Pretty fun one. Unfortunately I accidentally deleted the code for part 1. But it was basically the same as day 18 (>>841463).
Code for part 2: play.rust-lang.org
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);}
...
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 data; int cur_data = 0; const auto val_or_reg = [&](string_view x){ return isalpha(x[0]) ? &data[x[0]] : &(data[--cur_data] = to(x)); }; vector prog; for (string_view line : input | split(by_line)){ auto [ins, x, y, _] = parse_n(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
well the contest is almost over.
did anyone learn anything? I learned
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.
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.
(cont.)
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.
Just for practise really. I solved these problems in a high level language Mathematica, and want to see it from another perspective.
LOL
353 bytes
from collections import defaultdict as DC=D(lambda:D(int))for l in open('i'):a,b=map(int,l.split('/'));C[a][b]+=1;C[b][a]+=1def 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,mprint(M(0,0,0)[1])
Part 1 is similar but a bit easier, I am too lazy to integrate it here
I learned
$ time pypy3 yoba.py
1673
real 0m0.545s
user 0m0.511s
sys 0m0.029s
day 24. templateRet elec_moat_rec(int8_t last, unordered_multimap& 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(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 pieces; for (string_view line : input | split(by_line)){ auto [as, bs, _] = parse_n(line, by_num); int8_t a = to(as), b = to(bs); pieces.emplace(a, b); pieces.emplace(b, a); } cout
OCaml. nothing clever. fastest part2 so far.
thatsthejoke.webm
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.
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.
начали за здравие, кончили за упокой.
Suck my dick.
according to pic related part 2 was probably not that challenging anyway.
there's no challenge at all, the only challenge is that you need to have all the other stars
I've tried a few other ways to do this, but avoiding pattern-matching just means avoiding speed. (marginally in this case)
you should program a FPGA for this task.
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
You will fall to crippling depression before you reach 30.
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.
Well at least I will be a wizard by then.
Explain Rust macros to me please.
>>/fringe/
afaik semantically basically like Clojure macros but with the added complexity of satisfying type checker.
Well there is a chapter about them in the book which explains the basics: doc.rust-lang.org
Then there is a pretty in depth intro here: danielkeep.github.io
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(input, by_num); size_t n_iter = to(n_iter_s); struct state_t { int8_t write[2], moved[2], next[2]; }; vector 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 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
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.
Diagram for the first 400 iterations, not too exciting.
Merry Grav-Mass, and also go eat a dick.
D-did we get beaten by 4/g/? Hopefully that one poster is just an outlier.
reddit.com
in a cooking contest, the guy who shits in the bowl finishes first, but he doesn't win :^)
what I learned from adventofcode:
you forgot something:
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.
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.
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?
so that means haskell is a trolling language
(you can troll your employer by using haskell)
bump XDDDDD
why?
btw, started doing project euler recently, 30 problems solved so far
>>>/babbage/ Lifeless new board, but the idea is to have a tech (and science) board without the deadweights.
