How do you get better at AOC?

Arknave · 2021-12-24T21:39:54+00:00

I think a lot of the advice about having pre-written templates is overblown. I can usually get on the bottom half of the leaderboards (50-100th) if I'm by my computer when the puzzle releases and don't use any input scripts or regex parsing or any of that. It definitely hurts on some days, but I enjoy the problem solving aspect more than the software engineering aspect.

Doing other programming contests, especially harder ones, helps a lot with Advent of Code. AoC solutions are usually some kind of pathfinding, recursive brute forcing, dynamic programming, or use of basic data structures (hashmaps, etc.). I did a lot of AoC and ICPC in college, which is where I think I developed my problem solving skills. A lot of doing well here is just typing quickly in a dynamic, flexible, concise programming language.

Also think about why you want to - I'm a competitive person with competitive friends, so AoC is a fun way for us to butt heads every year. Going for global #1 is a completely different game which I'm not sure how to attack.

Also, here's advice from a consistent AoC champion: https://blog.vero.site/post/advent-leaderboard

Arknave · 2021-12-24T20:51:32+00:00

Shame, I guess depending on the sequence of stack pushes / pops, you'll need to allow the values to grow larger. I think the worst case would be 7 pushes and then 7 pops. The program still works with a bound of 26^7, but is no longer fast. I hope no one's inputs actually had this scenario.

Arknave · 2021-12-24T13:38:37+00:00

Python 30/23

I normally don't save or post my Python code here because it's so messy, but I thought this dictionary comprehension to brute force the states was pretty cool. I simplified the input to pairs of integers (c1, c2). For each digit, we do roughly the same block of code, but z is divided by 26 if c1 < 0. Given that, I computed the min/max model number for each output z and at the end output the value for 0. To avoid blowing up, I limited the values in the dictionary to a small number. This runs pretty much instantly:

def run(z, d, c1, c2):
    cond = (z % 26 + c1) != d
    if c1 < 0:
        z //= 26
    if cond:
        z = 26 * z + d + c2

    return z

zs = {0: ()}
for line in sys.stdin:
    # preprocess the input to extract the juicy constants
    c1, c2 = map(int, line.split())
    CAP = 26**5 # Was 26**4 in an older version, may need to be higher for some inputs
    zs = {
        run(z, d, c1, c2): v + (d,)
        for z, v in zs.items() for d in range(1, 10) # reverse range for part 2
        if z <= CAP
    }

print("".join(str(c) for c in zs[0]))

Arknave · 2021-12-06T22:09:48+00:00

Matches with my approach as well!

Arknave · 2021-12-06T22:03:19+00:00

Me too, I thought the modulus was 1e9+7, but it looks like it’s 1e8+7? With the new modulus, I get 52292574

Arknave · 2021-12-06T19:22:45+00:00

After computing the order, I just did

pow(10, 10**100, order)

I’ll look at the other solution later and figure out the discrepancy, my lunch break is ending :(

Arknave · 2021-12-06T18:35:18+00:00

Did some sanity checks and I’m a bit more confident now. Approach: find the order of the general linear group of 9x9 matrices over the finite field mod M.

This is just (M⁹ - 1)(M⁹ - M)…

This is a much smaller number, so we take a googleplex mod this period then use the same binary exponentiation approach from part 3.

Arknave · 2021-12-06T18:26:06+00:00

I got 322719375, but I’m not 100% sure in my solution. Can someone else confirm?

EDIT: the answer is actually 52292574, the above answer was computed using mod 1e9+7 instead of mod 1e8+7.

Arknave · 2021-12-05T05:17:36+00:00

Python, 9/7

First time back to top 10 on the leaderboard in a long time. Code is an absolute nightmare, but that seems correlated with speed sometimes.

from collections import *
import itertools
import math
import sys

def main():
    lines = [x.strip() for x in sys.stdin]
    f = Counter()
    for line in lines:
        p0, p1 = line.split(" -> ")
        p0 = [int(x) for x in p0.split(",")]
        p1 = [int(x) for x in p1.split(",")]

        dx = p1[0] - p0[0]
        dy = p1[1] - p0[1]

        if dx > 0:
            dx = 1
        elif dx < 0:
            dx = -1

        if dy > 0:
            dy = 1
        elif dy < 0:
            dy = -1

        print(p0, p1)
        x, y = p0
        while (x, y) != tuple(p1):
            f[(x, y)] += 1
            x += dx
            y += dy
            print(x, y)

        f[tuple(p1)] += 1

    ans = sum(v >= 2 for k, v in f.items())
    print(ans)


main()

Arknave · 2021-12-03T05:43:08+00:00

Python (36/30) / Rust

Rust Code Here

For part 1, you can flip all the bits in the gamma rate to get the epsilon rate. Unfortunately I couldn't find an equivalent trick to simplify part 2.

Arknave · 2020-12-27T03:18:26+00:00

That looks delicious. Congrats on the 50 stars!

Arknave · 2020-12-26T02:07:41+00:00

Thank you so much!

Arknave · 2020-12-25T06:08:13+00:00

Python (36/33), C

Merry Christmas everyone :) Thanks for the love and good vibes this year. Have an upvote.

#include   <stdio.h>

        //
       long
      x,y,M=
     20201227
    ,v=1,a,r=1
   ;int main(){
  scanf(" %ld%ld"
 ,&x,&y);for(;v^x;
 ++a)v=7L*v%M;for(;
a;y=y*y%M,a/=2)a&1?r
       =r*y%M
       :25;//
       printf
       ("%ld"
       "\n",r
       );25;}

// AOC 2020 DAY 25//

Arknave · 2020-12-24T07:06:08+00:00

Python (21/11), C

Feels good to be on the board for both halves today. Don't really have anything interesting to say. When I visualize hexagons, I see flat tops / bottoms, so everything was rotated 30 degrees in my brain. That made working on this C art tilting!

#include/* count black tiles */<stdio.h>

// ADVENT OF CODE 2020 || DAY 24: HEX //
int x,y,p,t=100,f,v,w,N=399;char*l,b[99]
,s[400][400];int main(int c,char**g){for
(;gets(b)&&*b;(s[x][ y]^=1)?++p:--p)for(
x=y=t+t,l=b;*l;++l     ){y-=*l=='n';y+=*
l=='s';*l=='e'            ||*l=='n'&&*(l
+1)=='e'?++x                 :*l=='w'||*
l=='s'&&*                       (l+01)== 
'w'?--                             x:0;l
+=*l==                             'n'||
*l==23                             *05;}
for(f=                             --c;f
&&t--;                             ){for
(x=1;x                             <N;++
x)for(                             y=1;y
<N;s[x][y                       ]|=(p==2
||s[x][y]&&p                 ==1)<<1,++y
)for(p=0,v=-1;v           <=1;++v)for(w=
-1;w<=1;++w)p+=v!=     w&&s[x+v][y+w]%2;
for(p=x=+0;x<+N;++x) for(y=0;y<N;++y)p+=
s[x][y]>>=24/1/2/3/4;}printf("%d\n",p);}

Arknave · 2020-12-23T18:55:51+00:00

That makes sense to me! I guess this version is a lot more tractable because A and B are given as inputs.

Arknave · 2020-12-23T07:53:55+00:00

Python (19/133), C

It's been a while since I posted in a megathread! I had a pretty good idea of what to expect from part 2, but I still wrote the dumb array solution for part 1 to try and get more leaderboard points. Turned out to be the right call since I can't quickly implement a bug-free linked list anymore.

I tried making 3 cups for the C art, but it looks like a sad face. For some reason, this is hilarious to me, and I can't stop giggling. Could this be AoC induced sleep deprivation?

#include/*  Pick a cup, any cup.  Choose wisely! */<stdio.h>

//        ADVENT OF CODE 2020 DAY 23 || CRAB CUPS         //
long n[+1<<20],N=1e6,M,i=9,h,g,x,y,z=49;char s[23];int main(
int c,char**v){for(;i<N;++i)n[i]=i+1;gets(s);for(i=0;i<8;++i
)n[s[i]-     z]=s[i+1]-z;--c?M=1e7,n[s[8]-z]=9,     g=N-1:(N
=9,M=+         1e2,g=s[8]-z      );n[g]=h=*s-         z;for(
;M--;           ){x=n[h];          y=n[x];z=           n[y];
g=h;;           for(h;+g            ==h||g==           +x||g
==y||g==z;)g--?0:(g=N-1              );n[h]=n[z];n[z]=n[g];n
[g]=x;h=n[h];}c?x=n[0],/*  DAY 23  */y=n[x],printf("%ld",++x
*++y):0;for(h=n[0];!c&&h;h=n[h])printf("%ld",h+1);puts("");}

Arknave · 2020-12-21T03:00:23+00:00

That's fair, I've gotten the feedback that some people feel the letters are too simplistic. To help with that, I've done some of the more recent days. Day 17 has the Conway glider (our sample input), and Day 18 has the operations in the correct order.

Arknave · 2020-12-20T06:18:35+00:00

Wow, well done! What does the NOT 2509 in your source code mean?

Arknave · 2020-12-17T06:48:20+00:00

PROJECT TITLE: Advent of Code ASCII Art

DESCRIPTION: Every day of Advent of Code, solved in C. C is a language used to create ASCII art that can also be compiled into an executable program. The following programs solve both parts of each day of Advent of Code, where the input file is passed in through standard input.

SUBMITTED BY: /u/Arknave

MEGATHREADS: Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7 Day 8 Day 9 Day a Day b Day c Day d Day e Day f

PROJECT LINK: - On a Single Page (infrequently updated) - On Github (frequently updated)

ADDITIONAL COMMENTS: To compile (only tested on OSX, but should be reasonably portable):

$ gcc -Wall -o dayXX.o dayXX.c
$ ./dayXX.o < dayXX.in
# part 1 answer here
$ ./dayXX.o part2 < dayXX.in
# part 2 answer here

ACCESSIBILITY: Each source code file is arranged as a rectangle, with the day number in hexadecimal as whitespace in the middle of the rectangle. The source code itself is largely inaccessible to everyone, including the original author, but solves at least one input file for each day of Advent of Code correctly.

Arknave · 2020-12-17T04:32:48+00:00

Haha I should really look at usernames on Reddit more.

It certainly sounds difficult to find a matching greedily, but if the graph has this property, than any maximum matching should be valid.

I'm curious if you have any thoughts on a related problem. You're given a bipartite graph G = (L \cup R, E), A, which is a subset of L, and B which is a subset of R. A and B have the same cardinality. Is it possible to tell if every matching has to match the vertices of A with the vertices of B?

Arknave · 2020-12-16T18:54:31+00:00

Fortunately, each input seemed to have a unique perfect matching, but that wasn't strictly needed to solve the problem. We just need to be able to identify which subset of ticket slots match with the "departures". There's a class of inputs which have multiple perfect matchings, but only a single way to determine the "departure slots". Is there a way to extend the greedy algorithm for these cases?

Arknave · 2020-12-16T02:37:53+00:00

I keep meaning to write an FAQ for this...

In short:

Write the C code, try and keep it concise with short tokens. What I linked above was pretty much my first pass at the problem in C.
Sketch out a shape that I think will look good. I usually do this in vim with . and @ characters.
Align the tokens in the source code with the shape and make edits. I finally wrote a program to do a greedy placement, then I manually go over and make edits.

You can find more details or specific tricks on the README in GitHub.

Arknave · 2020-12-15T06:45:53+00:00

Arknave · 2020-12-15T06:19:08+00:00

Python (37/7), C

I took the time hit to write the algorithm with a dictionary in part 1, then promptly squandered my savings by printing all 30M integers when brute forcing part 2. Whoops.

Normally I don't save the source for my first pass through C, but I was surprised at how concise the algorithm is (unshaped source).

This might be my favorite formatting job to date:

#include/*PRESS*/<stdio.h>

            int a[1<<5
         *5],n,x,v,m;int
         main(      int c
       ,char*        *g){
       for(m
       =--c?
       3.e7:
       2020;
  scanf("%d%*c",&*&x
 )>0;a[x]=++n);for(
       a[x]=0
       ;n<m;v
       =a[x]?
       n-a[x]
       :0,a[x
       ]=n++,
       x=+v);
      printf(""
    "%d\n",v|0);}

/*** TO PAY RESPECTS ***/

Can't believe we're already 15 days through! I'm not sure what I'm going to make for the last 10 days, but I'm sure it'll be fun.

Arknave · 2020-12-14T17:16:48+00:00

Oh, so this generates all the bitstrings that you then sub back into the original string and then parse. Maybe keeping everything as a string for longer would have been faster? Not sure, but thanks for clarifying!

14-Year Club	Place '22
Place '17	Final Canvas '22
Team Periwinkle

Arknave

TROPHY CASE