🌟 Advent of Code (AoC) 2022 🌟

Permalänk
Medlem
Skrivet av abelsson:

Jaha, nu var årets upplaga slut! Några reflektioner?

Det här var första året jag gjorde AoC (och dag 1 var första rust-programmet jag någonsin skrivit) och jag måste säga att det var väldigt tillfredsställande att skapa ihop stjärnor och jag lyckades få ihop alla 50, alla utom en på rätt dag Jag tyckte det var kul variation på problem och svårighetsnivåer, men favoriten är nog dag 22 eller 24 medan dag 16 var den mest frustrerade. Har ni andra någon dag som ni tyckte var speciell?

Om nån - mot förmodan - vill se så finns alla mina lösningar på: https://github.com/abelsson/aoc2022

Kudos till dig, att lära mig rust genom aoc är något jag själv planerat några år men aldrig blivit av.

24 var min favorit.
22 tog mig längst tid att lösa men jag uppskattade hur annorlunda den var mot resterande uppgifter. Den blev även betydligt lättare när jag insåg att

man kunde skapa en fysisk kub av en närliggande postitlapp och slippa belasta närtiddsminnet med en kanterna av en visualiserad 3dkub

Dold text

16 var nog den där jag blev minst nöjd med min lösning. Jag skar bort delar av sökrymden med diverse heuristisks och är inte säker på att lösningen finns kvar för alla typer av inputs.
25 var lite av ett antiklimax för mig. Visst, talbaser är fair game men inte den typen av problem som jag kliver upp klockan 05:45 för

Tack till alla som postat i tråden! Även om jag själv inte bidragit har det varit kul att läsa andras tankar om problemen

Permalänk
Medlem

Dag: 13
Språk: Basic v2.0 (Commodore 64)
Får se hur långt C64:an orkar med och inte blir för lång kod, mest för en kul utmaning

0 FORI=0TO7:READA$(I),B$(I):NEXT:FORI=0TO7:A=LEN(A$(I)):B=LEN(B$(I)):FORQ=1TOA
1 C=ASC(MID$(A$(I),Q,1)):IFC>47THENIFC<58THENC$=C$+RIGHT$(STR$(C-48),1)
2 NEXT:FORQ=1TOB:C=ASC(MID$(B$(I),Q,1)):DATA"[1,1,3,1,1]","[1,1,5,1,1]"
3 IFC>47THENIFC<58THEND$=D$+RIGHT$(STR$(C-48),1):DATA"[[1],[2,3,4]]","[[1],4]"
4 NEXT:G=LEN(C$):H=LEN(D$):L=G:IFH>GTHENL=H:DATA"[9]","[[8,7,6]]","[[4,4],4,4]"
5 IFG=0THENIFH=0THEN9:DATA"[[4,4],4,4,4]","[7,7,7,7]","[7,7,7]","[]","[3]"
6 FORQ=1TOL:IFVAL(MID$(C$,Q,1))<VAL(MID$(D$,Q,1))THENT=T+(I+1):Q=L
7 IFVAL(MID$(C$,Q,1))>VAL(MID$(D$,Q,1))THEN9:DATA"[[[]]]","[[]]"
8 NEXTQ:DATA"[1,[2,[3,[4,[5,6,7]]]],8,9]", "[1,[2,[3,[4,[5,6,0]]]],8,9]"
9 C$="":D$="":NEXTI:PRINTT

Dold text
Visa signatur

••••    ¨˜”°ºXTROº°”˜¨ •••• •••• Letar du efter något? •••• ••••  The Little Ninja  ••••
•••• C64 0.98MHz/64K •••• ••••   Prova det ultimata!   •••• •••• Komplett Cracktro ••••
••••  -Tack för såsen..  •••• ••••     GO `GOOGLE´ NOW   •••• ••••    250bytes Intro   ••••

Permalänk
Datavetare
Skrivet av abelsson:

Jaha, nu var årets upplaga slut! Några reflektioner?

Det här var första året jag gjorde AoC (och dag 1 var första rust-programmet jag någonsin skrivit) och jag måste säga att det var väldigt tillfredsställande att skapa ihop stjärnor och jag lyckades få ihop alla 50, alla utom en på rätt dag Jag tyckte det var kul variation på problem och svårighetsnivåer, men favoriten är nog dag 22 eller 24 medan dag 16 var den mest frustrerade. Har ni andra någon dag som ni tyckte var speciell?

Om nån - mot förmodan - vill se så finns alla mina lösningar på: https://github.com/abelsson/aoc2022

Gillade också 24, det efter jag insåg att min "snabba" variant som baserade sig enbart på bit-operationer inte var så snabb. Är möjligt att hantera snöstormen tillstånd enbart med en enda integer samt dess ursprungliga tillstånd.

Med den insikten blev det både enklare och snabbare...

goos: darwin goarch: arm64 pkg: aoc2022 BenchmarkDay24_parsing-10 90315 11377 ns/op 9184 B/op 294 allocs/op BenchmarkDay24_part1-10 61 19287990 ns/op 8760548 B/op 276388 allocs/op BenchmarkDay24_part2-10 20 55455177 ns/op 25256915 B/op 796742 allocs/op

Dold text

Har använt AoC till att sätta mig i 3 olika programspråk, Rust 2019 (som jag också körde förra året), Swift 2020 och i år Go.

Skrev i börjat att jag sneglat på Go tidigare, men inte riktigt sett någon direkt poäng att sätta mig in i språket. Go är definitivt inte det språk som ge de kortaste lösningarna, inte ens jämfört med t.ex. Rust eller Swift (och framförallt inte då jag begränsade mig till att lösa året AoC enbart med språket Go + dess standardbibliotek).

Go:s tooling är helt fantastiskt och måste säga att de som designade Go har verkligen tänkt på vad som spelar roll i "large scale projects". Go är kanske inte det roligaste språket att skriva kod i, men i lägen där jag ska sätta mig in i vad andra skrivit börjar jag mer och mer luta åt att Go nog är min absoluta favorit!

Edit: har rimligen missat att posta ett gäng dagar, blev otroligt hektiskt från lucia och framåt... För den som är intresserad finns alla dagarna + tester (exemplen i uppgifterna + ibland lite egna tester) på GitHub.

Edit: map[T]S är inte supersnabb i Go, 2x prestanda dag 24 genom att använda en array i stället...
Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Medlem

Dag: 19
Språk: Python (Bredden först-lösning. Numpy givetvis )

Måste säga att detta var den bökigaste uppgiften att lösa. Kanske till viss del beroende på att jag envisades med att köra BFS. Den blev dock hyfsat effektiv till slut, körtiden mäts i sekunder, inte minuter.

Varje blueprint blir en matris med de state-förändringar som sker om man bygger en robot av typ X. Blueprint-matrisen adderas till matrisen med alla nuvarande state och ut kommer en 5 gånger så stor matris. Det blir snabbt en ohållbart stor sökrymd. Följande fyra regler håller ner antalet states så det faktiskt funkar att köra BFS.

Bort med alla states

  • som inte hade tillräckligt med resurser för att bygga den roboten,

  • som has byggt fler robotar av en viss typ än vad vi kan använda varje minut,

  • där man kunde ha byggt en gorde robot men inte gjorde det,

  • där man byggt en robot som kunde ha byggts minuten innan (detta state kommer alltid vara ett sämre allternative än det state där roboten byggdes den förra minuten).

Den sista regeln är det som gör det möjligt att köra BFS. Det skulle gå att klippa mer i sökrymden, men det funkar OK nu. Minnesåtgången håller sig under 5GB.

import re import numpy as np from collections import defaultdict from math import prod adm, res, cost, robots, br = 0, 1, 1, 2, 3 # adm, resources, cost, robots, built robot ore, cly, obs, geo = 0, 1, 2, 3 bm, cbm, lbm, lcbm = 0, 1, 2, 3 # Built Mask, Can Build Mask, Last Build Mask, Last Can Build Mask bp = [] for l in open("input19").readlines(): _, or0, cl0, ob0, ob1, ge0, ge2 = tuple(map(int, re.findall(r'\d+', l))) bp.append( np.array( # Adm, Cost Owned robots Built Robot [[[1, 0, 0, 0], [-or0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0]], [[2, 0, 0, 0], [-cl0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 0, 0]], [[4, 0, 0, 0], [-ob0, -ob1, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0]], [[8, 0, 0, 0], [-ge0, 0, -ge2, 0], [0, 0, 0, 0], [0, 0, 0, 1]], [[0, 0, 0, 0], [ 0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]], dtype=np.int_)) def tick(states, bp, limit): s = (states.reshape((-1, 16)) + bp.reshape((-1, 1, 16))).reshape(-1, 4, 4) # Did we have enough resources to build? s = s[s[:,res,:].min(axis = 1) >= 0,:] # No need to have more robots than the resource use each minute s = s[(s[:,robots,:geo] <= limit).all(axis = 1),:] # Can we build geode robot? s = s[((s[:, adm, cbm] & 8) != 0) == s[:, br, geo],:] # Should have built earlier? s = s[ ~np.logical_and( np.logical_and(s[:, adm, bm] != 0, s[:, adm, lbm] == 0), (s[:, adm, bm] & s[:, adm, lcbm]) != 0),:] # Each robot collects one resource s[:, res, :] += s[:,robots,:] # Built any new robots? s[:, robots, :] += s[:, br,:] # Bookkeeping s[:, adm, lbm] = s[:, adm, bm] s[:, adm, lcbm] = s[:, adm, cbm] s[:, adm, bm] = 0 s[:, adm, cbm] = ( (s[:, res, :] + bp[geo, cost, :] >= 0).all(axis = 1) << 3 | (s[:, res, :] + bp[obs, cost, :] >= 0).all(axis = 1) << 2 | (s[:, res, :] + bp[cly, cost, :] >= 0).all(axis = 1) << 1 | (s[:, res, :] + bp[ore, cost, :] >= 0).all(axis = 1)) s[:, br: ,:] = 0 return s def bfs(bp, minutes): l = [] for i,b in enumerate(bp): limit = -b[:, cost, :geo].min(axis=0) s = np.array([[0,0,0,0], [0,0,0,0], [1,0,0,0], [0,0,0,0]]) for j in range(minutes): s = tick(s, b, limit) l.append((i + 1, s[:, res, geo].max())) return l print(sum(map(prod, bfs(bp, 24))), prod(map(lambda x: x[1], bfs(bp[:3], 32))))

Dold text
Permalänk
Medlem

Dag: 20
Språk: C++ (Det bara skrek dubbellänkad lista och pekarmanipulation. Inget för Python...)

#include <iostream> #include <fstream> #include <vector> #include <cstdint> using namespace std; struct List { int64_t val; List *prev; List *next; List(int64_t v, struct List *&last) : val(v), next(this), prev(this) {} void remove() { next->prev = prev; prev->next = next; next = prev = this; } void precede(List *elem) { prev = elem->prev; next = prev->next; elem->prev = this; prev->next = this; } }; List *forward(List *p, int n) { for (auto i = 0; i < n; ++i) p = p->next; return p; } int64_t solve(int64_t scale, int times) { ifstream file; file.open("input20"); List *first = nullptr; List *last = nullptr; vector<List *> v; int64_t n; while (file >> n) { List *elem(new List(n * scale, last)); v.push_back(elem); if (first) { elem->precede(first); } else { first = elem; } } int64_t count = v.size() - 1; for (int j = 0; j < times; ++j) { for (auto i : v ) { auto steps = i->val % count; if (steps > 0) { List *p = i; for (auto j = 0; j < steps; ++j) { p = p->next; } i->remove(); i->precede(p->next); } if (steps < 0) { List *p = i; for (auto j = 0; j > steps; --j) { p = p->prev; } i->remove(); i->precede(p); } } } auto p = first; while (p->val != 0) { p = p->next; } return forward(p, 1000)->val + forward(p, 2000)->val + forward(p, 3000)->val; } int main() { cout << solve(1, 1) << ", " << solve(811589153, 10) << '\n'; return 0; }

Dold text
Permalänk
Medlem

Dag: 22
Språk: Python (Numpy kan rotera kuber...)

Det blev ganska mycket kod, men att mappa sidorna på kuber var lite knöligt.

import numpy as np import re from math import gcd map_, moves = tuple(open("input22").read().split('\n\n')) map_ = map_.split('\n') sx, sy = max(len(l) for l in map_), len(map_) grid = np.zeros((sy, sx), dtype = np.int_) for y, l in enumerate(map_): grid[y, :len(l)] = [' .#'.find(c) for c in l] def rotL(cube): return np.rot90(cube, axes=(0,2)) def rotR(cube): return np.rot90(cube, k = -1, axes=(0,2)) def rotU(cube): return np.rot90(cube, axes=(0,1)) def turnL(cube, pos = (0, 0, 0)): return np.rot90(cube, axes=(2,1)), (0, pos[2], cube.shape[1] - pos[1] - 1) def turnR(cube, pos): return np.rot90(cube, axes=(1,2)), (0, cube.shape[2] - pos[2] - 1, pos[1]) def corners(cube): return cube[0,0,0], cube[0,-1,0], cube[0,0,-1], cube[0,-1,-1] def find_start_face(cube, first): for _ in range(3): if set(corners(cube)) == set(first): return cube cube = rotL(cube) if set(corners(cube)) == set(first): return cube cube = rotU(cube) def project_grid_onto_cube(grid): fs = gcd(sx, sy) first = None faces = dict() cube = np.zeros([fs + 2] * 3, dtype=np.int_) # Mark corners for navigation for ix,x in enumerate([0, fs + 1]): for iy,y in enumerate([0, fs + 1]): for iz,z in enumerate([0, fs + 1]): cube[x,y,z] = ix << 2 | iy << 1 | iz for iy, y in enumerate(range(0, sy, fs)): # Map face and rotate for ix, x in enumerate(range(0, sx, fs)): if grid[y:y+fs, x:x+fs].sum(): cube[0, 1:-1, 1:-1] = grid[y:y+fs, x:x+fs] c = corners(cube) faces[frozenset(c)] = (c, (y, x)) first = first if first else c cube = rotL(cube) # Rotate back and rotate down if non-zero face on the down side for ix, x in enumerate(range(sx - fs, -1, -fs)): cube = rotR(cube) if y + fs < sy and grid[y:y+fs, x:x+fs].sum() and grid[y+fs: y+2*fs, x:x+fs].sum(): cube = rotU(cube) # cube = find_start_face(cube, first) while corners(cube) != faces[frozenset(first)][0]: cube, _ = turnL(cube) return [cube, faces] def project_grid_onto_plane(grid): faces = dict() cube = np.zeros([1, grid.shape[0] + 2, grid.shape[1] + 2], dtype=np.int_) for iy,y in enumerate([0, grid.shape[0] + 1]): for iz,z in enumerate([0, grid.shape[1] + 1]): cube[0,y,z] = iy << 1 | iz cube[0, 1:-1, 1:-1] = grid c = corners(cube) faces[frozenset(c)] = (c, (0, 0)) return [cube, faces] def flip(cube, pos): return rotL(cube), tuple(pos - np.array((0,0,cube.shape[0] - 2))) def skip(cube, pos): while cube[pos] == 0: pos = tuple((pos + np.array((0,0,1))) % cube.shape) return cube, pos def next_move(moves): while moves: if m := re.match('\d+', moves): moves = moves[len(m[0]):] yield int(m[0]) if moves: m, moves = moves[0], moves[1:] yield m def next_pos(cube, pos, on_zero): pos = tuple(pos + np.array((0,0,1))) return (cube, pos) if cube[pos] else on_zero(cube, pos) def do_moves(cube, faces, on_zero): cube, pos = skip(cube, (0,1,1)) for n in next_move(moves): if n == 'L': cube, pos = turnL(cube, pos) elif n == 'R': cube, pos = turnR(cube, pos) else: for i in range(n): ncube, npos = next_pos(cube, pos, on_zero) if ncube[npos] == 2: break cube, pos = ncube, npos (c, (y,x)) = faces[frozenset(corners(cube))] dir = 0 while corners(cube) != c: cube, pos = turnL(cube, pos) dir += 1 return (pos[1] + y) * 1000 + (pos[2] + x) * 4 + dir print([do_moves(*f1(grid), f2) for f1, f2 in [(project_grid_onto_plane, skip), (project_grid_onto_cube, flip)]])

Dold text
Permalänk
Medlem

Dag: 23
Språk: Python

import numpy as np import copy grid = np.array([[".#".find(c) for c in l.strip()] for l in open("input23").readlines()]) def propose(g, p, props, dir): if g[p[0] - 1 : p[0] + 2, p[1] - 1: p[1] + 2].sum() == 1: return for i in range(dir, dir + 4): if i % 4 == 0 and (g[p[0] - 1, p[1] - 1: p[1] + 2] == 0).all(): # N props[p] = (p[0] - 1, p[1]) return if i % 4 == 1 and (g[p[0] + 1, p[1] - 1: p[1] + 2] == 0).all(): # S props[p] = (p[0] + 1, p[1]) return if i % 4 == 2 and (g[p[0] - 1 : p[0] + 2, p[1] - 1 ] == 0).all(): # W props[p] = (p[0], p[1] - 1) return if i % 4 == 3 and (g[p[0] - 1 : p[0] + 2, p[1] + 1 ] == 0).all(): # E props[p] = (p[0], p[1] + 1) return def round(g, dir): if g[0,:].sum() or g[-1,:].sum() or g[:,0].sum() or g[:,-1].sum(): g = np.pad(g, 1) coords = list(zip(*np.where(g == 1))) props = dict() for p in coords: propose(g, p, props, dir) for p in props.values(): g[p] -= 1 for p1, p2 in props.items(): if g[p2] == -1: g[p2] = 1 g[p1] = 0 g[g < 0] = 0 return g g = grid def one(g): for i in range(10): g = round(g, i) xs, ys = np.where(g == 1) return (xs.max() - xs.min() + 1) * (ys.max() - ys.min() + 1) - g.sum() def two(g): for i in range(9999): lastg = copy.deepcopy(g) g = round(g, i) if g.shape == lastg.shape and (lastg == g).all(): return i + 1 print(one(grid), two(grid))

Dold text
Permalänk
Medlem

Dag: 24
Språk: Python (Numpy igen...)

import numpy as np symbols = ".<>^v#" g = np.array([[symbols.find(c) for c in l.strip()] for l in open("input24").readlines()], dtype = np.uint8) b = np.array(([((g == i).astype(np.uint8) << i)[1:-1,1:-1] for i, _ in enumerate(symbols)]))[1:5] def move_blizzards(g, b): for i, (k, a) in enumerate([(-1, 1), (1, 1), (-1, 0), (1, 0)]): b[i] = np.roll(b[i], k, axis = a) g[1:-1,1:-1] = b.sum(axis = 0) return g steps = np.array([[0, 0], [-1, 0], [ 1, 0], [ 0, -1], [ 0, 1]]) def minute(t, g, b, pos, start): g = move_blizzards(g, b) return t + 1, g, {next for p in pos for s in steps if ((p + s) < g.shape).all() and g[next := tuple(p + s)] == 0} | {start} def traverse(t, g, b, start, goal): pos = {start} while goal not in pos: t, g, pos = minute(t, g, b, pos, start) return t, g start, goal = (0,1), (len(g) - 1, len(g[0]) -2) there, _ = traverse(0, g, b, start, goal) back, _ = traverse(there, g, b, goal, start) again, _ = traverse(back, g, b, start, goal) print(there, again)

Dold text
Permalänk
Medlem

Dag: 14
Språk: Basic v2.0 (Commodore 64)
Jobbigast var att rita ut "stenmuren" med kordinater, fick lite Boulder Dash vibbar av denna
=Tecknet för 'Clear Screen' ❤

0 P=1:FORI=0TO6:READA:READB:X(I)=A-492:Y(I)=B:NEXT:PRINT"";
1 FORI=0TO9:PRINTCHR$(I+48);"...........":NEXT
2 FORI=OTOP:A=X(I):B=X(I+1):IFX(I)>X(I+1)THENA=X(I+1):B=X(I)
3 C=Y(I):D=Y(I+1):IFY(I)>Y(I+1)THENC=Y(I+1):D=Y(I)
4 FORX=ATOB:FORY=CTOD:POKE1024+X+Y*40,35:NEXT:NEXT:NEXT:O=3:P=5:IFI<5THEN2
5 X=8:Y=40:R=1024:DATA498,4,498,6,496,6,503,4,502,4,502,9,494,9
6 A=PEEK(R+Y+X):W=Y:V=X:B=PEEK(R+Y+X-41):IFY>400THENPRINT,T:END
7 D=PEEK(R+Y+X-1):E=PEEK(R+Y+X+1):IFA=35THENA=87
8 S=0:IFA=87THENS=1
9 IFS=1AND(B=46ANDD=46)OR(B=35ANDD=46)THENX=X-1:GOTO12
10 IFS=1ANDD=87ANDE=46THENX=X+1:GOTO12
11 IFA=87THENX=8:Y=40:T=T+1:GOTO6
12 POKE1024+Y+X,87:POKE1024-40+W+V,46:Y=Y+40:GOTO6

Dold text

Edit: Tog en titt på 15, men har ännu inte fått nå grepp om vad man ska göra

Visa signatur

••••    ¨˜”°ºXTROº°”˜¨ •••• •••• Letar du efter något? •••• ••••  The Little Ninja  ••••
•••• C64 0.98MHz/64K •••• ••••   Prova det ultimata!   •••• •••• Komplett Cracktro ••••
••••  -Tack för såsen..  •••• ••••     GO `GOOGLE´ NOW   •••• ••••    250bytes Intro   ••••