/tech/ - Technology★

>>842153

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.

>>842157

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) <= b)) {
    f = 0;
}

>>841744

>>841772

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';
}

>>842019

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

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.

>>842167

>made it so that you can C-c, alter registers, and then resume the simulation

why do you need this?

>>842167

>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.

>>842169

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

>>842170

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

>>842162

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

>>842177

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

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

>>842177

It's the opposite

>>842179

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

>>842178

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);
}
}

>>842183

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.

>>842183

…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.

>>842187

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.

>>842183

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++
  }
}

>>842183

> fuck this task already.

Heh.

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

>>842190

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.

>>842163

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';
}

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

>>842193

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';
}

>>842152

Hi magicgoose

>>842218

Hi but please don't find me by IP address

>>842221

>say Hi to him for me

nope, why would I?

>>842223

Is he not your leader?

>>842224

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

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: https://play.rust-lang.org/?gist=03f2020bdb9cd0d4ca43cb6d37cbaad0

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);
}

>>842245

>>841463

>>842209

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';
}

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!

>>842496

>>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.

>>842496

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.

>>842496 (cont.)

>Mathematica prices: $320 for "home and hobby"; $2700 for a single user industry license.

>>842510

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.

>>842514

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

>>842496

>real-world python is actually a completely unreadable mess

>real-world

>golfed

LOL

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

>>842496

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

>>842587

$ time pypy3 yoba.py

1673

real 0m0.545s

user 0m0.511s

sys 0m0.029s

>>842479

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';
}

>>842563

thatsthejoke.webm

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.

начали за здравие, кончили за упокой.

>part 2 requires all stars

Suck my dick.

>>842989

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

>>843028

you should program a FPGA for this task.

>>843056

You will fall to crippling depression before you reach 30.

>>843056

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.

>>843057

Well at least I will be a wizard by then.

>>843059

Explain Rust macros to me please.

>not being a wizard already

>>/fringe/

>>843063

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

>>843063

Well there is a chapter about them in the book which explains the basics: https://doc.rust-lang.org/stable/book/first-edition/macros.html

Then there is a pretty in depth intro here: https://danielkeep.github.io/practical-intro-to-macros.html

>>842597

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';
}

>>843358

>Merry Christmas, and hopefully Santa brought you lots of proprietary software and Apple products.

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.

https://www.reddit.com/r/adventofcode/comments/7m7ykj/ama_request_winner_of_the_aoc2017/

>>843536

>beaten

>by mostly python

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

what I learned from adventofcode:

<haskell is completely horrifying

>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.

>>843540

you forgot something:

>Mostly python, some rust.

>>843550

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.

>>843550

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?

>>843612

so that means haskell is a trolling language

(you can troll your employer by using haskell)

bump XDDDDD

>>847966

why?

btw, started doing project euler recently, 30 problems solved so far

>>847970

>>>/babbage/ Lifeless new board, but the idea is to have a tech (and science) board without the deadweights.