/tech/ - Technology and Computing

Technology, computing, and related topics (like anime)

LynxChan updated to 2.5.7, let me know whether there are any issues (admin at j dot w).

Reports of my death have been greatly overestimiste.

Still trying to get done with some IRL work, but should be able to update some stuff soon.


Max message length: 6144

Drag files to upload or
click here to select them

Maximum 5 files / Maximum size: 20.00 MB


(used to delete files and postings)

Open file (36.33 KB 642x418 adventofshame2018.png)
Advent of Code is coming Anonymous 11/13/2019 (Wed) 01:06:13 No.698
We're 20 days out, which is clearly not enough time for 8kun/tech/ to come back.
20 days out is also about as much preparation as you'd need to use Advent of Code to learn a new language. So:
1. are you competing this year?
2. what language(s) are you going to use?
3. where are you going to talk about the puzzles?
Thanks anon I didn't know about it. I'd probably like to pick up Python tbh.
Python? Gross!
last year we had Ada, Mathematica, C++, Rust, but not much Python that I remember.
OTOH, Python is incredibly popular in general and in other places, like the subreddit, so you'll get instant feedback and lots of different ways to accomplish the puzzles, to compare your own work to, so learning Python through Advent of Code sounds like it'd be pretty effective.
>read my mind
>make this game
>whoever finishes first wins
>leaderboard fags kicking people off due to nigger cliques
I doubt I'll bother. Last year was enough for me.
I enjoyed it last year, even though I never ranked below 300.

>2. what language(s) are you going to use?
The language of the gods: Haskell. It makes the earlier problems easier and later problems EXTRA TOUGH because they're usually best solved imperatively.
But I'll fall back to Python or C++ when GHC wants to allocate 10TB of memory and I can't figure out why.

>3. where are you going to talk about the puzzles?
/g/ a shit, /tech/ is dead, le reddit is about namefagging and upvotes, so probably just a group chat with >friends.
Change my mind to blogpost and reply here.
Open file (72.02 KB 1024x683 steve klabnik 7.jpg)
Rust is the best language :^)
Open file (70.76 KB 763x310 tech_fags.png)
Everyone starts out with a memelang but you can't solve 2 nigger retard puzzles a day with a memelang. Also once you realise you're gonna score 0 for the entire competition and the only contest is on private leaderboards then people get bored.
>hurr durr why did people drop out of advent of 2d-grids???
2018 was the worst year by far.

This weekend is a good time to practice AoC on a previous year.
Leaderboard code here: 208834-7de8f664
>Steve used to be this svelte
Did Rust make him fat?
Did the stress of trying to be productive with Rust finally get to him?
Poor guy.
the flower-water puzzle was fun, so I don't think the 2d grids were the problem. It felt more like he would implement something amusing and then come up with a task description that exactly required his original implementation, and then put a lot of work into adjusting the rules to exclude other implementations. The worst puzzles involved 2d grids because that allowed for lots of precise behavior, so his reverse-engineer a puzzle strategy resulted in tasks crazier to read than http://boundvariable.org/um-spec.txt
Is this one for julay specifically? Or is it for the whole webring, or even 8chan too?
haven't seen it anywhere else, but both of the other ids are on it are from 8chan.
looks like there's going to be no /tech/ on 8kun through 9Dec, and still no guarantee after that, so I'm not counting on spending AoC there.
Gonna try to remember this and actually work on it instead of getting distracted with other stuff. I'll use Clojure, and I 'll probably just talk about it here unless I forget
Advent of Code checklist
- [ ] grids
- [ ] particle movement in n-dimensional space
- [ ] native-code compiler for made-up assembly language
- [ ] circular data structure with efficient element removal and addition
- [ ] self-serializing persistent data structures (so if part 2 asks for something we just calculated, we don't have to recalculate it)
- [ ] bignums
>sudden feeling of dread, disgust
- [ ] make sure I can work with unicode emojis
>self-serializing persistent data structures
at no point during a problem should your program take more than a minute, because that means fixing bugs takes forever. so with that in mind you don't need persistence.

also don't forget a decent graph library so you don't waste half a day debugging your DFS and remember to paste debug output in a spreadsheet to easily check and plot your output.
Did python last year for shits and giggles. Not sure what I'll use or if I'll bother next year.
>Change my mind to blogpost and reply here
It's not gonna get better if you don't post
>It's not gonna get better if you don't post
Excellent point.
Now give me a performant data structure for infinite grids in C++. You know, to make this board better.
well that image was more to show how dumb the contest is. These are the average points/star for each person.

1st: 8.22
2nd: 8.16
3rd: 7.80
4th: 8.72
5th: 7.96
6th: 4.95
7th: 5.85
8th: 4.87
9th: 4.48
10th: 10
11th: 2.41

The scoring is like a race of 3 people and they place 1st, 10th and 15th. Yeah makes a lot of sense to me.
you get more points for earlier answers.
The main contest is like that but private leaderboards seem like they are based on percentile placing. So if you finish 100th/100 it's the same as being 10th/10 or 40000th/40000.
You try to finish super fast in the first few days since that is the easiest way to get points, since there's more people being slow. Then after about half-way unless you are finishing in the first hour you should just give up since completing stars won't really give you any points since you'll be last all the time.
Open file (133.53 KB 852x670 leaderboard.png)
>seem like
pic related

I can still reach 59 points by doing the other 24 days of AoC2018. And then make 6 dummy accounts surging me to 359 while #365713 only gets to 354. Because fuck #365713, he doesn't deserve the top spot with 10 stars missing.
Or just sort by number of stars.
A bold move, sir. However, I will require you to provide some evidence or argument.
Cool to see a thread here already.

1. Yes
2. *le Python
3. Maybe here, maybe on 4chins

Only 60 hours remaining so GET HYPE.
You can?
>muh points
Holy shit STFU. Nobody cares.
>it's the taking part that counts

Tonight is the night boys and girls (boys). Are you ready?
day one deeeelang
import std;

int fuelreq(int mass) {
int reqsum;
while (1) {
int req = mass / 3 - 2;
if (req < 1) return reqsum;
reqsum += req;
mass = req;

void main() {
writeln(input.map!(m => fuelreq(m)).sum);
Holy shit I'm sleepy
- parse all lines including the empty one, ending up 2 below the right answer
- use a temp variable for the inner loop but keep using the initial fuel in the calculation instead of the temp var, resulting in an endless loop
- use `mod` instead of `div` when switching languages because you're too sleepy to recognize the endless loop
- include the initial fuel in the module sum

sum . fmap (sum . takeWhile (>0) . tail . iterate (\n->(n`div`3)-2) . read) . lines <$> readFile "day-1"
Here's my Clojure

(defn module-fuel
[mass & {:keys [subtotal]
:or {subtotal 0}}]
(let [fuel (-> mass
(/ 3)
(- 2))]
(if (<= fuel 0)
(module-fuel fuel :subtotal (+ subtotal fuel)))))

;;The answer
(apply + (map module-fuel input))

fn solve(input: &str) -> (u32, u32) {
.map(|s| s.parse::<u32>().unwrap() / 3 - 2)
.fold((0, 0), |(a, b), i| {
a + i,
b + std::iter::successors(Some(i), |&i| (i / 3).checked_sub(2)).sum::<u32>()
BIG BOY for today: 10^321123 or https://raw.githubusercontent.com/JulayShitposter/aoc/master/2019/day/1/bigboy for lazy cunts
md5sum (part1\npart2\n): d8340d97495209959e17ecb4a5456ed6

Hats off to anyone solving (the hash of) 10^123456789
what is this?
It's a different input for anyone who wants more of a challenge.

Tbf today there's not much more to do than making the input fucking huge, so you're reliant on ${your language}'s bignums and their performance. That is, unless you can figure out a shortcut to the end result.
Most other days a Big Boy input requires you to actually rewrite your algorithm for performance.
236.56user 3.13system 4:01.11elapsed

>d answer right way
>ugly af
>compelled to write clean version
this didn't happen with Ada.
We got opcodes.
bool op(ref int[] code, ref int pos) {
switch (code[pos]) {
case 1: // add
code[code[pos+3]] = code[code[pos+1]] + code[code[pos+2]];
case 2: // mul
code[code[pos+3]] = code[code[pos+1]] * code[code[pos+2]];
case 99: // hlt
return false;
pos += 4;
return true;

is the core of the ugly d anyway.
I should've been comfortable enough with D enums to use those instead, without rewriting to them.
and these same opcodes are coming up again:
>"Good, the new computer seems to be working correctly! Keep it nearby during this mission - you'll probably use it again. Real Intcode computers support many more features than your new one
Naming a programming language after a woman (and just a simple secretary one at that) is bound to be a cursed situation anon. Otherwise, we'd all be writing code using Ada amiright?
she was more like a tech-savvy venture capitalist than a secretary. She proposed making a business of Babbage's invention.
source: some blog I can't find anymore, that tried to seriously ask if she was a puffed-up feminist myth or the real deal, and concluded that both are true: she was the real deal as a fancier of computing, but her "first programmer" creds are puffed-up feminist myths.
I think it was 4-6 puzzles last year. It's just the same but with more opcodes, boring stuff.
>take a minute to read part 2
>literally the only relevant information is "now set mem[1] and mem[2] such that the result is magicNumber"
Thanks obama

for (noun = 0; noun <= 99; noun++)
for (verb = 0; verb <= 99; verb++) {
while (i<l.length) {
switch (l[i]) {
case 1: l[l[i+3]] = l[l[i+1]]+l[l[i+2]]; break;
case 2: l[l[i+3]] = l[l[i+1]]*l[l[i+2]]; break;
default: console.log(l[i]); i=999999999;
if (l[0] == magicNumber)

Ain't nobody got time to download the input file or write clean code. :^)
>nobody got time to download the input file
this is amazing in its own way.
Rust is the most powerful language

fn solve(input: &str) -> (u32, u32) {
let mem: Vec<_> = input
.map(|s| s.parse().unwrap())

macro_rules! run {
($a:expr, $b:expr) => {{
let mut mem = mem.clone();
mem[1] = $a;
mem[2] = $b;

run(&mut mem);

let a = run!(12, 2);

for noun in 0..=99 {
for verb in 0..=99 {
if run!(noun, verb) == 19690720 {
return (a, noun * 100 + verb);


fn run(mem: &mut [u32]) {
use std::ops::*;

let mut pos = 0;

macro_rules! ops {
($($a:literal => $dst:literal = ($f:path, $($arg:literal),*)),*) => {
loop {
match mem[pos] {
99 => break,
$($a => {
let mut inc = 2;
let tmp = $f($({ inc += 1; mem[mem[pos + $arg] as usize] }),*);
mem[mem[pos + $dst] as usize] = tmp;
pos += inc;
_ => panic!()

1 => 3 = (Add::add, 1, 2),
2 => 3 = (Mul::mul, 1, 2)
templates and static foreach {} are just better than macros like that.
import std;

Tuple!(int, int) solve(string input) {
const int[] mem = input
.map!(s => to!int(s))

int run(int noun, int verb)() {
int[] mem = mem.dup;
mem[1] = noun;
mem[2] = verb;
return mem[0];

immutable int a = run!(12, 2);

static foreach (noun; 0 .. 100) {
static foreach (verb; 0 .. 100) {
if (run!(noun, verb) == 19690720) {
return tuple(cast(int) a, noun * 100 + verb);

void run(ref int[] mem) {
int pos = 0;

void op(int opcode, int c, alias fun, int a, int b)() {
if (mem[pos] == opcode) {
mem[mem[pos+c]] = binaryFun!fun(mem[mem[pos+a]], mem[mem[pos+b]]);

while (mem[pos] != 99) {
op!(1, 3, "a + b", 1, 2);
op!(2, 3, "a * b", 1, 2);
pos += 4;

void main() {
auto res = solve(File("input.txt").readln);
writeln("part1: ", res[0]);
writeln("part2: ", res[1]);

except that this takes 20+ seconds to compile, holy shit.
No one saw the other post :^)
(defn intcode-add [prog pos]
(let [a (get prog (+ pos 1))
b (get prog (+ pos 2))
c (get prog (+ pos 3))]
[(assoc prog c (+ (get prog a) (get prog b))) (+ pos 4)]))

(defn intcode-multiply [prog pos]
(let [a (get prog (+ pos 1))
b (get prog (+ pos 2))
c (get prog (+ pos 3))]
[(assoc prog c (* (get prog a) (get prog b))) (+ pos 4)]))

(defn run-intcode-program [program a b]
(loop [state [(-> program
(assoc 1 a)
(assoc 2 b))
(let [prog (first state)
pos (second state)
opcode (get prog pos)]
(if (= opcode 99)
(get prog 0)
(recur (cond
(= opcode 1) (intcode-add prog pos)
(= opcode 2) (intcode-multiply prog pos)
(throw (ex-info (str "Read bad opcode: " opcode) {:type :bad-opcode}))))))))
what's with the double spacing that almost every code example has?
>>885 (all me)
are the only exceptions.
Open file (140.37 KB 1024x828 faec.png)
>see image of intersection
>don't read the question, just see the words "manhattan distance" and "intersection"
>start parsing the input and writing down self-intersections
>it's wrong
>see some sleepy bugs, fix them
>it's wrong
>try the test input
>not the same answer
>actually read this time
>it's not one line of input but two and you have to find the intersections BETWEEN them
core of the logic:
struct Grid {
int[Coord] grid;

void plot(Move[] wire, int id) {
auto at = Coord(0, 0);
grid[at] |= id;
foreach (move; wire) {
foreach (i; 0 .. move.dist) {
at.move(move.dir, 1);
grid[at] |= id;

int part1(int id) {
int[Coord] intersections;
auto start = Coord(0, 0);
foreach (k, v; grid) {
if (v == id) {
intersections[k] = manhattan_distance(k, start);
int[] dists = intersections.values.sort.array;
return dists[1];

void main() {
Move[][2] input =
slurp!string("input.txt", "%s")
.map!(line => line.splitter(',').map!Move.array)

Grid grid;
grid.plot(input[0], 1);
grid.plot(input[1], 2);
I see your core of the logic and raise you my clusterfuck of the logic:
manhattan = (x,y) => Math.abs(x)+Math.abs(y)
d.map(([dir,r])=>{switch (dir) {
case 'R': for (i=0;i<r;i++) {
x++} break;
case 'L': for (i=0;i<r;i++) {
x--} break;
case 'U': for (i=0;i<r;i++) {
y++} break;
case 'D': for (i=0;i<r;i++) {
y--} break;
e.map(([dir,r])=>{switch (dir) {
case 'R': for (i=0;i<r;i++,s++) {if (ps[[x,y]] && s+ps[[x,y]]<steps && !(x==0 && y==0)) {steps=s+ps[[x,y]]};
x++} break;
case 'L': for (i=0;i<r;i++,s++) {if (ps[[x,y]] && s+ps[[x,y]]<steps && !(x==0 && y==0)) {steps=s+ps[[x,y]]};
x--} break;
case 'U': for (i=0;i<r;i++,s++) {if (ps[[x,y]] && s+ps[[x,y]]<steps && !(x==0 && y==0)) {steps=s+ps[[x,y]]};
y++} break;
case 'D': for (i=0;i<r;i++,s++) {if (ps[[x,y]] && s+ps[[x,y]]<steps && !(x==0 && y==0)) {steps=s+ps[[x,y]]};
y--} break;
//also it's off by two but that's solved by hand

No hating unless you ranked higher than me :^)
>all tests work
>data doesn't
Well at least we got fucking grids by day 3 lmfao.
Don't blame the anons, anon. Stephen Lynx is a nigger.
day4 = let
r = ['0'..'9']
monotonic = [[a,b,c,d,e,f] | a<-r, b<-r, a<=b, c<-r, b<=c, d<-r, c<=d, e<-r, d<=e, f<-r, e<=f]
part1 = length $ filter (inRange (lower,upper)) $ [read m | m<-monotonic, length (group m) <= 5]
part2 = length . filter (inRange (lower,upper)) $ [read m | m<-monotonic, any ((==2) . length) $ group m]
in [part1, part2]

It's not pretty but it does the job.
Perhaps I should've used tails to save a little time writing the number generator, or produce the whole range (lower,upper) and filter all (uncurry (<=)) . pairs . show. Yes, filtering on the actual range would've been smarter given this small range.
Anyone here?

He is an absolute retard, yes, but he did fix those newlines. Now robi is a nigger for not keeping julay up to date.
Ho ho ho, it's another intcode problem!

>tfw you spend 15 minutes debugging your machine because you use parameter 1 instead of 0 for the output
I'm never gonna make it to the global leaderboard.

Building on >>915 :

`).map(line => {l=line.split`,`.map(x=>parseInt(x))
while (i<l.length) {
get = n => Math.floor(l[i] / Math.pow(10,n+2))%10 == 1 ? i+n+1 : l[i+n+1]
switch (l[i]%100) {
case 1: l[l[i+3]] = l[get(0)]+l[get(1)]; i+=4; break;
case 2: l[l[i+3]] = l[get(0)]*l[get(1)]; i+=4; break;
case 3: l[l[i+3]] = input[inp++]; i+=2; break;
case 4: output.push(l[get(0)]); i+=2; break;
case 5: if (l[get(0)] > 0) i = l[get(1)]; else i+=3; break;
case 6: if (l[get(0)] == 0) i = l[get(1)]; else i+=3; break;
case 7: l[l[i+3]] = l[get(0)]<l[get(1)] ? 1 : 0; i+=4; break;
case 8: l[l[i+3]] = l[get(0)]==l[get(1)] ? 1 : 0; i+=4; break;
default: console.log(l[i]); i=999999999;


I think today it's time to clean up that code a bit.
my biggest mistake was reading an input of '1' as an input of 49, instead of 1.
checkin in, but the linebreaks and loss of the catalog sidebar make this a lot less attractive of a board :/
>where are you going to talk about the puzzles?
I don't think we can call these things puzzles.
I should switch to another language, because the spaghetti is getting real and I'm going down the leaderboard:
rorbs = {}
planets = {}
`.map(l => {const [a,b] = l.split`)`;
if (!orbs[a]) orbs[a] = [b]; else orbs[a].push(b)
if (!rorbs[b]) rorbs[b] = [a]; else rorbs[b].push(a)
isntroot[b] = 1
planets[a] = 1
planets[b] = 1
recurse = (p,n) => {
total = 0
if (!orbs[p]) return 0;
for (const p2 of orbs[p]) {
total += n+recurse(p2,n+1)
return total
for (const p of Object.keys(planets)) {
if (!isntroot[p]) {
parents = p => {ps=[]
while (rorbs[p]) {
p = rorbs[p]
return ps}

sp = parents('SAN')
mindist = 999999999
parents('YOU').map((p,i) => sp.map((p2,j) => {
if (p==p2 && i+j<mindist) mindist = i+j}))
Prepare for another day of intcode :^)

fn solve(input: &str) -> (i32, i32) {
let mem: Vec<_> = input.split(',').map(|s| s.parse().unwrap()).collect();

let amplify = |phases: [i32; 5]| {
let mut halted = false;
let mut signal = 0;
let mut vms: Vec<Intcode> = phases
.map(|&phase| Intcode::with_input(mem.clone(), vec![phase]))

while !halted {
for vm in vms.iter_mut() {
halted = vm.run().is_ok();
signal = vm.output.pop().unwrap();


successors(Some([0, 1, 2, 3, 4]), next)
successors(Some([5, 6, 7, 8, 9]), next)

fn next(a: &[i32; 5]) -> Option<[i32; 5]> {
let mut i = a.len() - 1;

while i > 0 && a[i - 1] >= a[i] {
i -= 1;

if i == 0 {
return None;

let mut j = a.len() - 1;
while j >= i && a[j] <= a[i - 1] {
j -= 1;

let mut a = *a;
a.swap(j, i - 1);

Well that was annoying. I'm not a big fan of these build upon previous day things.
Intcode is what keeps the importniggers away from the leaderboard.
God fucking dammit, I didn't expect another intcode problem so soon. It took me over 5 hours to solve today, because I only had a shitty version in C# that somehow gave wrong answers for the examples, even though it worked fine on day 5.
runMachine = let
run pc mem i = let
at = (!) mem
set x v = mem // [(x,v)]
(flags,op) = at pc `divMod` 100
modes n = let
(n',f) = n `divMod` 10
mode = if f == 0 then at else id
in mode : modes n'
(noun:verb:dest:_) = zipWith ($) (modes flags) [pc+1..]
binOp (?) = run (pc+4) (set dest $ fromEnum $ at noun ? at verb) i
in case op of
1 -> binOp (+)
2 -> binOp (*)
3 -> let (x:i') = i in run (pc+2) (set noun x) i'
4 -> at noun : run (pc+2) mem i
5 | at noun > 0 -> run (at verb) mem i
5 -> run (pc+3) mem i
6 | at noun == 0 -> run (at verb) mem i
6 -> run (pc+3) mem i
7 -> binOp (<)
8 -> binOp (==)
99 -> []
in run 0

-- everything I would have to write for today:
cluster m [f1, f2, f3, f4, f5] =
let a = runMachine m (f1 : 0 : e)
b = runMachine m (f2 : a)
c = runMachine m (f3 : b)
d = runMachine m (f4 : c)
e = runMachine m (f5 : d)
in e

>tfw you try to use State and STArray and making actual data types for the machine, but you only end up wasting hours
Never try to be smarter than Haskell. Just be as lazy as Haskell.
LARP in 10 seconds.
lmao that drop in difficulty
Haskell wins once again

day8 =
let part1 = print . (\xs -> count 1 xs * count 2 xs) . minimumBy (compare `on` filter (==0)) . parse
part2 = putStrLn . unlines . per 25 . fmap ones . L.foldl' (zipWith merge) (repeat 2) . parse
count n = length . filter (==n)
merge 2 x = x
merge x _ = x
ones 1 = '@'
ones _ = ' '
per n [] = []
per n xs = let (first,rest) = splitAt n xs in first : per n rest
parse = per (25*6) . fmap (read . pure) . head
in [part1,part2]

Yeah, he should've switched around today's and yesterday's.
>tfw filtered by the easiest day thus far
--------Part 2--------
Day Time Rank Score
8 00:30:04 1012 0
>add a single instruction
>download more RAM

A shame I just missed out on the global leaderboard because I switched around the program counter and relative base.
>write some shitfest for part 2
<wrong answer
>alright, I may have fucked up the algorithm
<wrong answer
>umm maybe it's off by one
<wrong answer
>no really, it must be one of these

Fuck me, I was still working with the test input. No wonder the alleged off-by-one was 802.
Shit didn't know this existed. Its not like I have the time or energy for this anyway. Got school sucking up all I've got.
>Got school sucking up all I've got.
You know that's a lie.
Start with days 1, 8 and 4. They're pretty much trivial if you know anything about programming. And once you've solved those, you can try the intcode days (2, 5, 7, 9) if you want to learn about machine code or try one of the upcoming puzzles.
Fucked up today's challenge. I didn't know of any good vector manipulation libraries to deal with either parts.

School shouldn't stop you, especially if you have weekends free.
Although hitting the leaderboard will be mostly impossible, you should still be able to finish all the challenges day-by-day. Even 30 minutes of free time is usually enough to complete 1 AoC puzzle.
And hell, you have enough time to post here, no?
>vector manipulation libraries
drugs are bad mkay
All you need is atan2 or phase to convert a pair of numbers to an angle. Actually you don't even need that, you can compare vectors directly.
Other than that it's just bruteforcing each asteroid. Or using some parameter space to quickly get asteroids along a line, like a Hough transform, but I'm not sure that's possible.
>process state value = ("produce state' ", "just get the current cell")
>input = mapAccumL process start output
>output = runMachine input
<*** Exception: <<loop>>
>output = runMachine (0:tail input)
<runs normally

Fuck me sideways. The head of input literally only depends on the initial state.
Today was F U N. When the problem asks you to think for yourself, suddenly the whole leaderboard is up for grabs.
I don't even know why I stored all states in a set when my answer is only valid assuming it first repeats the initial state.

Who's going to do all 500 trillion simulation steps? It should only take you a day or so on an optimized program.
>Who's going to do all 500 trillion simulation steps?
The retardation is strong with me today. It took me only 2 hours to realize all you have to do is keep track of the pad and the ball while parsing every triple of the output, and send an input whenever you get a new ball position. There's still absolutely no reason to make a machine that returns control on input let alone make an interactive terminal program.
Had >fun with today's challenge once I figured out how the fuck the game's i/o worked.
>let alone make an interactive terminal program.
I imagine most people did precisely that. How else would you even figure out what the running 'game' is?>>1075
>How else would you even figure out what the running 'game' is?
I read the description. And I outputted the board a couple of times to check if I parsed it right and looked like breakout.
Open file (4.45 KB 261x78 still_not_11.png)
I was really scared that part 2 would change the reactions to allow for multiple paths (e.g. A+B->C, A+2B->2C, find optimal path...). Instead, part 2 was just as simple as part 1 + bruteforce binary search.
Open file (164.92 KB 1002x718 nkeoKb7.jpg)
Congrats, now join our leaderboard >>801 :^)

I should've prepared better for graph problems. Now it was a shitfest of manual processing and copy-pasting intermediate results between languages, because of course >javascript doesn't have a quick&dirty graph library.
And I did the fucking binary search BY HAND. That should NEVER happen.
>see Day 15
>"heh, it's just BFS"
<tfw off-by-one
<tfw had the right answer for half-an-hour
<tfw would've solved it even faster if I'd copied last year's code
Today is probably one of the last chances I have at actually hitting leaderboard speed. A fucking shame, since I've not done as well as I did last year.
>"heh, it's just BFS"
Yeah except for the fucking turtle.
I've just wasted an hour reverse engineering the machine because I'm starting to hate intcode puzzles.
>muh intcode
>The first seven digits of your initial input signal also represent the message offset.
>The first seven digits of your initial input
>initial input

14971 user 20 1024.7g 1.8g 3.7m R 390.1 5.6 55:25.35 day16

Also I feel like I should optimize it.
Although I wasn't fully filtered for today, my method's still highly sub-optimal: I just used a summed-array to bring down my run-time speed to a workable ~5 minutes.
<he only read the question statement 1 hour after finishing his shitcode
>Also I feel like I should optimize it.
wew. My solution doesn't look as bad now.
><he only read the question statement 1 hour after finishing his shitcode
>assuming you didn't read the question correctly rather than having a bug in your code
And it made proper use of 4 cores, so it was running for only 15 minutes by that time.

Funny I realize only now that, because the offset is given and the matrix has such a neat shape, that should've given me a hint. It makes for a slight improvement over 70 minutes of CPU time:

$ time ./day16
real 0m0.463s
user 0m0.459s
sys 0m0.004s

Still, I'm happy with the nlogn algorithm that got me the star (it runs for about 2 minutes or 2 seconds if you keep i>=offset):

step() {
int total = 0;

for (int i = len; i--;) {
total += state[i];
sum[i] = total;

for (int i = 1; i <= len; i++) {
total = 0;
for (int j = 1; j*i <= len; j++) {
total += ((j%4) < 2 ? 1 : -1) * sum[j*i-1];
state[i-1] = abs(total%10);
Today was tedious and had literally no programming.
I counted the intersections by hand and I constructed the path by hand, even making branches at every intersection, which turned out to be completely wasted effort.
Now I really want to make a big boy with straight pieces split across functions and turns at intersections. Because that does require programming.
Your bigboy is fucking bugged.


There are two possible direction I can take at the '?'.
>There are two possible direction I can take at the '?'.
>the absolute state of namefags
Yes. Now activate your head spaghetti to conclude that you have to traverse at least one of those scaffolds more than once.

The only sense in which it's "bugged" is that 3-way intersections are not explicitly stated in part one where they matter, but no one cares about part one.

I forgot to give solutions to >>1101 by the way:
md5sum of a valid input: b72a21be600c0ab2f43b4c17530fff95
md5sum of the output: 31e3c1625c87b911f8fc377fb2b0857c
No, m8. 3-way intersections are not part of the puzzle specification.
Sure they are faggot.
same place it specifies corners.
>ctrl + f corner
>Phrase not found
Ok, retard. How about you provide a quotation?
There are no 3-way intersections and the robot never takes a turn at an intersection and it never follows the same segment twice in the examples and inputs, but nowhere does it say these things are disallowed.
If you can't handle the bigboy, that's fine, but stop crying that it's somehow wrong.

Be glad I didn't put L,L or R,R in the path. That resulted in eldritch abominations like

Nevermind the three tentacles, those are comparatively easy to deal with, but at some point the robot stops at the ? and turns around. In the middle of a segment. Good luck finding that out.
>hurr durr the puzzle description doesn't say that it isn't allowed
>that means that it could happen even though in the entirety of AoC this was never the case
I'm not crying, I'm just telling you that you're bigboy input doesn't follow the specification.
Today was easy, but I'm not very proud of my O(x) solution of following the 2 edges of the tractor beam.
Or actually, I don't feel proud because I'm still filtered by yesterday. After BFS failed, I was convinced to learn how to reinvent Dijkstra, but my solution isn't running fast enough.
BFS does work.
It was a good idea to take a break yesterday, given how few people have solved it. Guess I'll do it tonight or during the weekend.

Thanks, I'll keep that in mind.
>THREE HOURS I just HAD to hardcode the area that has inner portals and the maximum depth and forget to change them when switching between test input and real input. Also I had an off-by-one for part 2 for some reason.
Today's part 1 was a copy-paste because of what I did in >>1134. Haven't done part 2 yet; Dickstra runs out of memory despite working swiftly on the test input. >>1136 I don't get how. My BFS for day 18 creates a new "state" (i.e. starts a concurrent BFS from the key, forgetting the tiles it's been to for backtracking) for every key it finds, and that quickly balloons to a million items in the queue. Same thing happens if I take each key as an edge and run BFS With Priority Queue. In-between the two, I also tried a recursive DFS to see if I'd luck out in finding an optimal minima at the start. It unsurprisingly failed. I'll be re-looking the problem eventually, but I'll remain >filtered till then.
>>1139 I don't know if your approach is correct but yes it get's huge. Takes like 3 mins for mine to run.
>>1113 ah nice the code-tag double spacing is finally fixed.
Compared to Day 17, this was a cakewalk. --------Part 2-------- Day Time Rank Score 21 00:35:56 119 0 My rank is surprisingly high up for the brainlet solution I made, which boiled down to Trial and Error with Pen and Paper
>>1145 >tfw you think the jump bot cycles through the instructions executing ONE instruction per step, so you have to blindly try loads of instruction combinations I haven't even checked, but do the registers start at 0 every step? I just assume they keep their values. With part 2 I was struggling with how to flatten the tree of conditions so I could just NOT, OR and AND the temp register all the way through, totally ignoring that the jump register can be used at any point. By the way, day 17 part 1 is a cakewalk too and part 2 is pretty easy when you assume that the problem is easy. The robot never turns at an intersection, so there's only a single path [spoiler]that you can trace by hand and then put in any editor that highlights selections to quickly find the functions[/spoiler]
>>1146 >can't even nest spoilers lynxchan a shit
>>1146 >I haven't even checked, but do the registers start at 0 every step? I think they do. I proved it on my end by trying RUN ................. ................. ................. #####@########### ^ crashes here and NOT A T OR T J RUN ................. ................. @................ #####..#.######## ^ bot does not repeatedly jump v ................. ................. .@............... #####..#.######## The 2nd one is equivalent to T = !A; J |= T; RUN; If J retained its value, the bot would continuously jump after it meets its first empty hole, because (true |= bool) == 1. Instead, the bot stops jumping after the first jump (at the hole from the first RUN), which means that J was reset at some point. >spoiler I eyeballed the thing manually with Pen&Paper. Text selection would've been extremely helpful.
>what is the position of card 2019 >position of >not "which card is at position 2019" fuck my reading comprehension
Reversing the shuffle operation for 2020 was simple enough, but how do you compute that 101741582076661 times in a row? I'm at about a couple million iterations right now, but every card position thus far has been unique.
Does anyone have a proof of the period of an iterated polynomial in a field? I know x+b (b>0) has period p and a*x (a>0,x>1 or a>1,x>0) has period p-1, but for a*x+b I could only assume that it has period p or, in the end, p-1 because I was off by one. ...Which makes sense because when a>1 there's exactly one identity e=ae+b --> b=e(1-a) --> e=b/(1-a)=b*c for any b because every non-zero element (1-a) has a unique inverse. >>1154 Same. It would've actually been better if he did ask for position 2019, because now part 1 is just a trivial case of part 2. Today is definitely big brain time, unless you cheat yourself and look up the algorithms. I know my finite fields and still it took 4 hours to get the right answer. That includes lots of off-by-one errors and I-have-no-fucking-clue-because-it's-all-opaque-numbers errors. I highly recommend you keep printing the output of part 1 using your part 1 algorithm AND using your part 2 algorithm the whole time. >>1155 Protip 1: you get back to the original deck after 119315717514046 shuffles, so why shuffle backwards a lot when you can shuffle forwards slighty less? Protip 2: write the shuffle operations as functions from the old position to the new position, e.g. restacking is new = -old-1 (mod length). 2.1: When your shuffle operations all look like new=a*old+b you can compose them and turn all the operations in your input into a single one, e.g. r=p+7, s=3*r+0 --> s=3*(p+7)+0=3*p+21.2.2: Put differently, cut -7 turns any [a,b] into [a,b+7] and restacking turns [a,b] into [-a,-1-b], with [a,b] starting at [1,0] because no operation must mean p=1*p+0 of course. Protip 3: Find a shortcut for applying a linear function a trillion times. :^)
>>1156 >Does anyone have a proof of the period of an iterated polynomial in a field? This sounds very similar to the wanting to know the period of a LCG. This is only for polynomials of degree 1 though. https://en.wikipedia.org/wiki/Linear_congruential_generator#Period_length
>>1157 Fuck, how could I forget about LCGs? Unfortunately it's just as hard to find anything about LCGs with m prime and c>0.
>>1156 >a*x (a>0,x>1 or a>1,x>0) has period p-1 Fuck, there are only totient(n-1) primitive elements in a field, like 2^k only cycles through 1->2->4->1 in GF(7). So I'm lucky totient(119315717514046)=59657858757022 means a >50% chance of 2020 being primitive. Not that it really matters, because any cycle length has to divide 119315717514046, so worst case I'm just going through a small cycle a couple of times too many.
7 hours remaining. You better have completed all of days 1-24 or you're not getting your last star tomorrow!
10 more minutes, and I'll be free from this LARPfest
>Unrecognized command My intcode machine is fucking broken.
Do you really solve day 18 with dumb BFS on the grid? I feel like there should be an elegant solution involving graph transformations or straight up linear programming, but I'm just too brainlet to see it.
>>1180 >dumb BFS At the very least, you can preprocess the grid and add a few heuristics to get a pseudo-A* running far faster than plain BFS. There shouldn't be a faster solution than that, since the problem statement boils down to a modified Traveling Salesman.

Report/Delete/Moderation Forms

no cookies?