🌟 Advent of Code (AoC) 2020 🌟

PermalÀnk
Medlem ★
●
Skrivet av Ingetledigtnamn:

Varför vill du ha en lista? Du har ju en 2D tabell att leta i. Det Àr bara att gÄ i en riktning i taget tills du hittar ett sÀte. Tomt eller inte.

Precis, jag lÀste lite slarvigt. Jag lÀste det som att man mÄste kolla alla sÀten i ett visst hÄll och inte bara den första. My bad. Har i alla fall löst det nu, redigerat mitt inlÀgg.

Skrivet av Sajox:

Det Àr fler som har det kÀmpigt

Första gÄngen jag provar AOC med sprÄket Rust. Har inte gjort sÄ mycket med Rust mer Àn lÀst och hÀngt med för att det Àr ett intressant sprÄk.

Jobbar som utvecklare och efter 8 timmar direkt sÀtta sig ner med AOC har haft sina pÄfrestningar. Min hjÀrna mÄste fÄ slappna av efter jobbet. Kommer nog sitta i mÄn av tid och lösa pusslen nÀr man Àr sugen.

Ja, jag hÄller med. Jag tror att de flesta av oss besitter pÄ den egenskapen att aldrig ge upp och det kan ibland vara dÄligt. Utöver det har AOC varit sjukt nyttigt, ÀndÄ!

Visa signatur

| Mobo: Gigabyte X570 GAMING X | CPU: AMD Ryzen 9 3900X + Dark Rock 4 | RAM: 32GB @ 3000MHz | GPU: Gigabyte RTX 3080 OC | PSU: Seasonic GX 850W | Chassi: NZXT S340 Elite Matte Black | M.2: Samsung 970 Evo 500GB & 1000GB | HDD: 4TB | Monitors: Acer Predator X34 GS & Acer XB270HU |

PermalÀnk
Datavetare ★
●

Dag: 11
SprÄk: CUDA

#include <chrono> #include <cstdint> #include <fstream> #include <functional> #include <iostream> #include <string> #include <vector> __device__ int cnt_adjacent_occupied(const uint8_t *cur, int idx, int width, int height) { int cx = idx % width; int cy = idx / width; int cnt = 0; for (int y = cy-1; y <= cy+1; y++) { for (int x = cx-1; x <= cx+1; x++) { if (!(x == cx && y == cy) && (x >= 0 && x < width && y >= 0 && y < height) && cur[x + y * width]) { cnt++; } } } return cnt; } __global__ void day11_1_kernel(const uint8_t *tiles, const uint8_t *cur, uint8_t *nxt, int width, int height) { int idx = blockIdx.x * blockDim.x + threadIdx.x; if (idx < width * height && tiles[idx] != '.') { // Inside valid set of tiles and on a chair int cnt = cnt_adjacent_occupied(cur, idx, width, height); if (cnt == 0 || cnt < 4 && cur[idx]) { nxt[idx] = '#'; } else { nxt[idx] = 0; } } } static void * gpu_buf(void *host_ptr, size_t buf_len) { void *gpu_ptr; cudaMallocManaged(&gpu_ptr, buf_len); if (host_ptr == nullptr) { memset(gpu_ptr, 0, buf_len); } else { memcpy(gpu_ptr, host_ptr, buf_len); } return gpu_ptr; } static void day11(const std::vector<uint8_t> &tiles, int width, int height) { int thrds_per_block = 1024; int num_blocks = (width * height + thrds_per_block - 1) / thrds_per_block; uint8_t *gpu_tiles = (uint8_t *)gpu_buf((void *)tiles.data(), tiles.size()); uint8_t *gpu_occ1 = (uint8_t *)gpu_buf(nullptr, tiles.size()); uint8_t *gpu_occ2 = (uint8_t *)gpu_buf(nullptr, tiles.size()); for (int gen = 0; ; gen++) { uint8_t *cur = (gen & 1) ? gpu_occ1 : gpu_occ2; uint8_t *nxt = (gen & 1) ? gpu_occ2 : gpu_occ1; day11_1_kernel<<<thrds_per_block, num_blocks>>>(gpu_tiles, cur, nxt, width, height); cudaDeviceSynchronize(); if (memcmp(cur, nxt, tiles.size()) == 0) { break; } } int cnt = 0; for (int i = 0; i < width * height; i++) { if (gpu_occ2[i]) { cnt++; } } std::cout << "Part 1 : " << cnt << '\n'; cudaFree(gpu_tiles); cudaFree(gpu_occ1); cudaFree(gpu_occ2); } static int measure(std::function<void()> fn) { auto start = std::chrono::high_resolution_clock::now(); fn(); auto finish = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(finish - start); return duration.count(); } int main(int argc, char *argv[]) { std::ifstream fin("input.txt"); std::string line; std::vector<uint8_t> tiles; int width; int height = 0; while (std::getline(fin, line)) { width = line.size(); height++; for (auto t: line) { tiles.push_back(t); } } auto d = measure([&]() { day11(tiles, width, height); }); std::cout << "Took : " << d << "ms\n"; }

Lösning

Lade inte allt för mycket tid pĂ„ denna. Även om berĂ€kningen av varje generation blir vĂ€ldigt effektiv och framförallt vĂ€ldigt enkelt pĂ„ en GPU Ă€r storleken pĂ„ vĂ€ntrummet för liten (98x97 tiles). Kostnaden att starta en GPU-kernel Ă€r tiotals mikrosekunder, tyvĂ€rr finns inget vettigt sĂ€tt att synkronisera GPU-trĂ„dar mellan vad Nvidia kallar "blocks" (i praktiken mellan SMs). Man kan inte ha mer Ă€n 1024 trĂ„dar per SM, dĂ„ 98 * 97 > 1024 mĂ„ste man anvĂ€nda flera SMs för att lösa en ruta per GPU-trĂ„d.

Synkroniseringen krÀver dÄ att man gÄr via CPU alt. gör en betydligt mer komplicerad GPU-kernel som kan hÄlla sin inom en SM. Kör man via CPU blir kostanden att starta och vÀnta in hundratals kernels den dominerande faktor och lösningen tar ~500 ms pÄ mitt system. D.v.s. problemet Àr sÄ pass litet att det lÀmar sig bÀttre för CPU, inte sÄ förvÄnande dÄ det Àven var tveksam boost av att anvÀnda flera CPU-kÀrnor.

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: 12
SprÄk: Golang
Lösning:

Idag lÀste jag inte instruktionerna och försökte fÄ sidan att acceptera ett negativt tal vid del1. Och vid del2, gjorde jag fel pÄ riktning sÄ jag fick rÀtt svar i testet, men pÄ fel koordinater. Anyway, idag fick jag chansen att anvÀnda en pekare för att modifiera min ship struct. Om jag inte gjort det hade jag behövt returnera de nya koordinaterna, eftersom golang Àr pass-by-value (du fÄr in en kopia).

PartOne: 57”s
PartTwo: 38”s

BenchmarkPartOne-8 20785 57319 ns/op
BenchmarkPartTwo-8 30882 38502 ns/op

package main import ( "bufio" "fmt" "math" "os" "strconv" ) type Ship struct { Y int X int Direction string WayPointY int WayPointX int WayPointDirection string } type Instruction struct { Direction string Value int } type Move struct { X int Y int } func getPartOne(rows []string) float64 { instructions := getInstructions(rows) directions := map[string]Move{ "E": Move{X: 1, Y: 0}, "N": Move{X: 0, Y: -1}, "S": Move{X: 0, Y: 1}, "W": Move{X: -1, Y: 0}} ship := Ship{Direction: "E"} for _, inst := range instructions { if inst.Direction == "F" { move(&ship, directions[ship.Direction], inst.Value) } else if inst.Direction == "L" { changeDirection(&ship, inst) } else if inst.Direction == "R" { changeDirection(&ship, inst) } else { move(&ship, directions[inst.Direction], inst.Value) } } return math.Abs(float64(ship.X)) + math.Abs(float64(ship.Y)) } func getPartTwo(rows []string) float64 { instructions := getInstructions(rows) ship := Ship{WayPointX: 10, WayPointY: -1} for _, inst := range instructions { if inst.Direction == "F" { dir := Move{ Y: ship.WayPointY, X: ship.WayPointX, } move(&ship, dir, inst.Value) } else if inst.Direction == "L" { changeDirectionWaypoint(&ship, inst) } else if inst.Direction == "R" { changeDirectionWaypoint(&ship, inst) } else { if inst.Direction == "N" { ship.WayPointY -= inst.Value } else if inst.Direction == "E" { ship.WayPointX += inst.Value } else if inst.Direction == "S" { ship.WayPointY += inst.Value } else if inst.Direction == "W" { ship.WayPointX -= inst.Value } } } return math.Abs(float64(ship.X)) + math.Abs(float64(ship.Y)) } func changeDirectionWaypoint(ship *Ship, instruction Instruction) { changes := instruction.Value / 90 for i := 0; i < changes; i++ { oldY := ship.WayPointY oldX := ship.WayPointX ship.WayPointX = oldY ship.WayPointY = oldX if instruction.Direction == "R" { ship.WayPointX *= -1 } if instruction.Direction == "L" { ship.WayPointY *= -1 } } } func changeDirection(ship *Ship, instruction Instruction) { direction := []string{"N", "E", "S", "W"} index := 0 changes := instruction.Value / 90 for i, val := range direction { if val == ship.Direction { index = i break } } if instruction.Direction == "R" { index = (index + changes) % len(direction) } else if instruction.Direction == "L" { index -= changes for index < 0 { index += len(direction) } } ship.Direction = direction[index] } func move(ship *Ship, move Move, depth int) { for i := 0; i < depth; i++ { ship.X += move.X ship.Y += move.Y } } func getInstructions(rows []string) []Instruction { instructions := []Instruction{} for _, row := range rows { direction := row[:1] value, _ := strconv.Atoi(row[1:]) instructions = append(instructions, Instruction{Direction: direction, Value: value}) } return instructions } func getRows(filename string) []string { file, _ := os.Open(filename) defer file.Close() scanner := bufio.NewScanner(file) var rows []string for scanner.Scan() { rows = append(rows, scanner.Text()) } return rows } func main() { rows := getRows("../input.txt") fmt.Println("PartOne", getPartOne(rows)) fmt.Println("PartTwo", getPartTwo(rows)) }

Dold text
PermalÀnk
Medlem ★
●
Skrivet av Dave1080:

Sen kan jag tycka att det kÀnns som att det Àr bara folk som faktiskt löser skriver hÀr. Kom igen, det finns vÀl mycket fler som ocksÄ har det kÀmpigt?!

Ja det börjar bli kÀmpigt hÀr ocksÄ. Tiden och energin rÀcker inte riktigt till nu nÀr det börjar bli svÄrare.
Jag löste Dag 11 del 1, men nÀr det kom till del 2 tog bÄde tiden och orken slut, och jag kÀnde att motivationen dök nÀr jag började halka efter. Men jag ska nog försöka lösa Ätminstone nÄgra dagar till.

PermalÀnk
Medlem ★
●
Skrivet av GLaDER:

Dag: 12
SprÄk: Go
Lösning: Main

First answer retrieved in: 31.28”s Second answer retrieved in: 26.55”s

Glöm inte att kika in pÄ vÄr leaderboard: 115994-59705230

Dagens lÀrdomar:

  1. I go sÄ Àr inte % som jag förvÀntade mig. (Exempel).

  2. Exemplet för part 2 svÀngde bara höger, sÄ jag fick rÀtt pÄ testet trots att min kod var fel. (BÄda brancherna i min if/else-if-sats hade rotDir == "R".) SÄ gÄr det nÀr man försöker vara duktig och tÀcka alla baser, istÀllet för att bara köra if/else.

  3. Jag har svÄrt att hitta balansen mellan "snabbast möjliga fulhack" och "lÀra mig Golang ordentligt". Det gör att mina lösningar blir mellanmjölk. Varken snabba eller Go-iska.

Dold text

Dag: 13
SprÄk: Go
Lösning: Main, Modulen som löser Del 2

First answer retrieved in: 14.337”s Second answer retrieved in: 29.897”s

Glöm inte att kika in pÄ vÄr leaderboard: 115994-59705230

Del 1 var inga problem. Parsea tabellen och hitta första efterföljande tiden som delar nÄgon av bussarna jÀmt.

Innan jag hann ta mig an Del 2 var jag tvungen att Äka en svÀng till affÀren, sÄ (mot mitt bÀttre vetande) skrev jag en bruteforce-lösning (loopa över alla tider, kolla om samtliga bussar delar den tiden jÀmt). Startade programmet och Äkte till ICA

programmet hade inte terminerat nÀr jag kom hem, 50 minuter senare

VÀl i bilen klurade jag lite och kom fram till det hÀr mÄste vara ett problem dÀr man ska nyttja Euklides algoritm. PÄ nÄgot sÀtt ville jag ju hitta talet som delade alla bussIDn med dess avgÄngstidsdeltan.

Det tog en rejÀl rÀd pÄ Internet innan jag mindes: Chinese remainder theorem! Bah. Först skÀmdes jag för att CRT hade flytt mitt minne; sen skÀmdes jag Àn mer för att jag hade glömt exakt hur man anvÀnder algoritmen... Men Svenska Wikipedia har en toppenförklaring som Àr direkt överförbar till dagens AoC-problem.

DÀrtill hittade jag en bra modul pÄ GitHub för att lösa CRT, sÄ min lösning pÄ Del 2 Àr egentligen bara att jag anvÀnder en 3pp...

Dold text
Visa signatur

:(){ :|:& };:

đŸŠđŸ»â€â™‚ïž   đŸšŽđŸ»â€â™‚ïž   đŸƒđŸ»â€â™‚ïž   ☕

PermalÀnk
Medlem ★
●

Idag var bra trÄkig..

Dag 13, awk

part1$ <in tr ',' '\n' | awk 'NR == 1 { e = $1 } !/x/ { n = (int(e / $1) + 1) * $1; print n, (n - e) * $1 }' | sort -n | head -1 | cut -d' ' -f2 part2$ <in tr ',' '\n' | awk 'BEGIN { step = 1 } NR > 1 && !/x/ { while ((t + NR - 2) % $1 != 0) { t += step } step *= $1 } END { print t }'

Har suttit och stört mig pÄ den dÀr while satsen ett tag nu, men man kanske inte kommer undan.. PÄ tok för rostig diskret matematik för att göra nÄgot Ät saken.

Dold text
Visa signatur

"Some poor, phoneless fool is probably sitting next to a waterfall somewhere, totally unaware of how angry and scared he's supposed to be." - Duncan Trussell

PermalÀnk
Medlem ★
●

Dag 13, Python

map och filter-hÀrvan ser till att fÄ ut indata pÄ formen
[(23, 0), (37, 17), (431, 23), (13, 36), (17, 37), (19, 42), (409, 54), (41, 64), (29, 83)]

f = open('input', 'r') start = int(f.readline()) line = f.readline() times = list(map(lambda x: (int(x[1]), x[0]), filter(lambda x: x[1] != 'x', enumerate(line.split(','))))) m = min([(((start + t - 1) // t) * t, t) for t,_ in times]) def task2(t, l, step): if not l: return t factor, offset = l[0] while True: t += step if (t + offset) % factor == 0: return task2(t, l[1:], step * factor) print((m[0] - start) * m[1], task2(0, times, 1))

Dold text
PermalÀnk
Medlem ★
●

Dag: 12
SprÄk: Kotlin
Lösning: GitHub

TyvÀrr börjar detta bli lite alltför svÄrt. Del 1 var rÀtt lÀtt, men inte del 2. Jag försökte i alla fall mig pÄ den ordentligt men fastnade i att hur man skulle tÀnka nÀr man bytte direction pÄ waypointen. Tex by default börjar den alltid 10 units east och 1 unit north om fartyget.

Men det var skitkul att helt naturligt anvÀnda mig utav rekursiva funktioner - nÄt jag aldrig hade gjort utan AOC. En viktig learning.

IkvÀll ska jag nog rita en x/y diagram och sÀtta ut punkterna enligt 90 gradersintervallen sÄ att jag fÄr bÀttre överseende och sen koda utifrÄn det. Nu ut pÄ promenad.

EDIT: Nu ger jag upp pÄ riktigt, jag klarar inte av att klura ut hur jag kan flytta pÄ waypointen helt enkelt. Trots att jag ritat en stöddiagram. PÄ rad 66 har jag skrivit en kommentar för detta. Min lösning fungerar bara för kodexemplet och bara om E körs först. Ni Àr alltid vÀlkomna med tips och hjÀlp.

EDIT 2: Kollade pĂ„ era lösningar och insĂ„g att jag gjorde det mycket mer komplext Ă€n vad det behövde vara. Blev inspirerad av @huggeMugg lösning och tillĂ€mpade det pĂ„ min. Äntligen.

Visa signatur

| Mobo: Gigabyte X570 GAMING X | CPU: AMD Ryzen 9 3900X + Dark Rock 4 | RAM: 32GB @ 3000MHz | GPU: Gigabyte RTX 3080 OC | PSU: Seasonic GX 850W | Chassi: NZXT S340 Elite Matte Black | M.2: Samsung 970 Evo 500GB & 1000GB | HDD: 4TB | Monitors: Acer Predator X34 GS & Acer XB270HU |

PermalÀnk
Medlem
●

Dag: 13
SprÄk: Golang
Lösning:

Ännu en brute-forcelösning. Del en gĂ„r raskt, del tvĂ„ tar cirka 9h.. Borde gett upp tidigare.

package main import ( "bufio" "fmt" "os" "strconv" "strings" ) type BusTable struct { Timestamp int Schedule []int } func getPartOne(rows []string) int { busTable := getBusTable(rows) departTime, busID := findBus(busTable) return (departTime - busTable.Timestamp) * busID } func findBus(busTable BusTable) (int, int) { for i := busTable.Timestamp; i < busTable.Timestamp+1000; i++ { for _, busID := range busTable.Schedule { if busID == -1 { continue } if i%busID == 0 { return i, busID } } } return 0, 0 } func getPartTwo(rows []string) int { busTable := getBusTable(rows) prod := 1 for _, val := range busTable.Schedule { if val != -1 { prod *= val } } k := prod / busTable.Schedule[0] i := busTable.Schedule[0] * k for k > 0 { isValid := true for j := 0; j < len(busTable.Schedule); j++ { if busTable.Schedule[j] == -1 { continue } else if ((i + j) % busTable.Schedule[j]) != 0 { isValid = false break } } if isValid { return i } k-- i = k * busTable.Schedule[0] if i%1000000000 == 0 { fmt.Println(i) } } return 0 } func getBusTable(rows []string) BusTable { bus := BusTable{} bus.Timestamp, _ = strconv.Atoi(rows[0]) fields := strings.Split(rows[1], ",") for _, field := range fields { val, err := strconv.Atoi(field) if err != nil { val = -1 } bus.Schedule = append(bus.Schedule, val) } return bus } func getRows(filename string) []string { file, _ := os.Open(filename) defer file.Close() scanner := bufio.NewScanner(file) var rows []string for scanner.Scan() { rows = append(rows, scanner.Text()) } return rows } func main() { rows := getRows("../input.txt") fmt.Println("PartOne", getPartOne(rows)) fmt.Println("PartTwo", getPartTwo(rows)) }

Dold text
PermalÀnk
Datavetare ★
●

Dag: 10 13
SprÄk: Swift
Lösning: Github

Nu blev det dags för BigNumber. MÀrks att Swift har Àndrats rÀtt mycket mellan versioner, i alla fall fram till 4.0 och senare. Lite frustrerande nÀr man följer instruktionerna för att inse att paketet kan inte ens inkluderas... Men gick att lösa tillslut, i grunden har man valt att ta bakÄtinkompatibla Àndringar som faktiskt resulterat i ett bÀttre/enklare sprÄk.

LÀste pÄ en del om "Chinese remainder theorem", men verkar ju som man kan göra en vÀldigt trivial lösning om man har BigNumber stöd

  • Leta pĂ„ ett "timestamp" som Ă€r jĂ€mnt dividerbart med första bus ID, helt enkelt genom att testa att dividera ett tal man ökar med 1 till det gĂ„r jĂ€mnt upp

  • Ändra steglĂ€ngd till en multipel av bus ID

  • Gör om punkt 1 för resten av linjerna, för varje linje multiplicera steglĂ€ngden med bus ID

Dold text
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 ★
●
Skrivet av Flexbert:

Dag: 13
SprÄk: Golang
Lösning:

Ännu en brute-forcelösning. Del en gĂ„r raskt, del tvĂ„ tar cirka 9h.. Borde gett upp tidigare.

package main import ( "bufio" "fmt" "os" "strconv" "strings" ) type BusTable struct { Timestamp int Schedule []int } func getPartOne(rows []string) int { busTable := getBusTable(rows) departTime, busID := findBus(busTable) return (departTime - busTable.Timestamp) * busID } func findBus(busTable BusTable) (int, int) { for i := busTable.Timestamp; i < busTable.Timestamp+1000; i++ { for _, busID := range busTable.Schedule { if busID == -1 { continue } if i%busID == 0 { return i, busID } } } return 0, 0 } func getPartTwo(rows []string) int { busTable := getBusTable(rows) prod := 1 for _, val := range busTable.Schedule { if val != -1 { prod *= val } } k := prod / busTable.Schedule[0] i := busTable.Schedule[0] * k for k > 0 { isValid := true for j := 0; j < len(busTable.Schedule); j++ { if busTable.Schedule[j] == -1 { continue } else if ((i + j) % busTable.Schedule[j]) != 0 { isValid = false break } } if isValid { return i } k-- i = k * busTable.Schedule[0] if i%1000000000 == 0 { fmt.Println(i) } } return 0 } func getBusTable(rows []string) BusTable { bus := BusTable{} bus.Timestamp, _ = strconv.Atoi(rows[0]) fields := strings.Split(rows[1], ",") for _, field := range fields { val, err := strconv.Atoi(field) if err != nil { val = -1 } bus.Schedule = append(bus.Schedule, val) } return bus } func getRows(filename string) []string { file, _ := os.Open(filename) defer file.Close() scanner := bufio.NewScanner(file) var rows []string for scanner.Scan() { rows = append(rows, scanner.Text()) } return rows } func main() { rows := getRows("../input.txt") fmt.Println("PartOne", getPartOne(rows)) fmt.Println("PartTwo", getPartTwo(rows)) }

Dold text

9h. KĂ€re himmel. TĂ„lmodigt!

Visa signatur

:(){ :|:& };:

đŸŠđŸ»â€â™‚ïž   đŸšŽđŸ»â€â™‚ïž   đŸƒđŸ»â€â™‚ïž   ☕

PermalÀnk
Medlem
●
Skrivet av GLaDER:

9h. KĂ€re himmel. TĂ„lmodigt!

SmÄ Àndringar och vi Àr nede pÄ 5”s och 18”s. ..

Dag 13 (igen):
SprÄk: Golang

Borde förstÄtt att det gick att öka/minska loop variabeln mer aggressivt.

package main import ( "bufio" "fmt" "os" "strconv" "strings" ) type BusTable struct { Timestamp int Schedule []int } func getPartOne(rows []string) int { busTable := getBusTable(rows) departTime, busID := findBus(busTable) return (departTime - busTable.Timestamp) * busID } func findBus(busTable BusTable) (int, int) { for i := busTable.Timestamp; i < busTable.Timestamp+1000; i++ { for _, busID := range busTable.Schedule { if busID == -1 { continue } if i%busID == 0 { return i, busID } } } return 0, 0 } func getPartTwo(rows []string) int { busTable := getBusTable(rows) prod := 1 for _, id := range busTable.Schedule { if id != -1 { prod *= id } } i := 1 for i < prod { scheduleMatchTime := 1 isValid := true for j := 0; j < len(busTable.Schedule); j++ { id := busTable.Schedule[j] if id == -1 { continue } else if ((i + j) % id) != 0 { isValid = false break } scheduleMatchTime *= id } if isValid { return i } i += scheduleMatchTime } return 0 } func getBusTable(rows []string) BusTable { bus := BusTable{} bus.Timestamp, _ = strconv.Atoi(rows[0]) fields := strings.Split(rows[1], ",") for _, field := range fields { val, err := strconv.Atoi(field) if err != nil { val = -1 } bus.Schedule = append(bus.Schedule, val) } return bus } func getRows(filename string) []string { file, _ := os.Open(filename) defer file.Close() scanner := bufio.NewScanner(file) var rows []string for scanner.Scan() { rows = append(rows, scanner.Text()) } return rows } func main() { rows := getRows("../input.txt") fmt.Println("PartOne", getPartOne(rows)) fmt.Println("PartTwo", getPartTwo(rows)) }

Dold text
PermalÀnk
Medlem ★
●

Gav mig pÄ dag 13 ÀndÄ och det flöt pÄ, jag tÀnkte ut en lösning som fungerade direkt. Vilken hÀrlig kÀnsla. Klockan Àr dock mycket nu sÄ jag slÀpper och njuter av segerns sötma tills imorgon dÀr jag provar pÄ del 2.

Dag: 13, endast del 1
SprÄk: Kotlin
Lösning: GitHub

Visa signatur

| Mobo: Gigabyte X570 GAMING X | CPU: AMD Ryzen 9 3900X + Dark Rock 4 | RAM: 32GB @ 3000MHz | GPU: Gigabyte RTX 3080 OC | PSU: Seasonic GX 850W | Chassi: NZXT S340 Elite Matte Black | M.2: Samsung 970 Evo 500GB & 1000GB | HDD: 4TB | Monitors: Acer Predator X34 GS & Acer XB270HU |

PermalÀnk
Medlem ★
●

@Yoshman Àr tillbaka pÄ dag 10 och @Flexbert kör dag 14 redan.. Tror folk börjar bli trötta

Visa signatur

"Some poor, phoneless fool is probably sitting next to a waterfall somewhere, totally unaware of how angry and scared he's supposed to be." - Duncan Trussell

PermalÀnk
Medlem ★
●
Skrivet av GLaDER:

Dag: 13
SprÄk: Go
Lösning: Main, Modulen som löser Del 2

First answer retrieved in: 14.337”s Second answer retrieved in: 29.897”s

Glöm inte att kika in pÄ vÄr leaderboard: 115994-59705230

Del 1 var inga problem. Parsea tabellen och hitta första efterföljande tiden som delar nÄgon av bussarna jÀmt.

Innan jag hann ta mig an Del 2 var jag tvungen att Äka en svÀng till affÀren, sÄ (mot mitt bÀttre vetande) skrev jag en bruteforce-lösning (loopa över alla tider, kolla om samtliga bussar delar den tiden jÀmt). Startade programmet och Äkte till ICA

programmet hade inte terminerat nÀr jag kom hem, 50 minuter senare

VÀl i bilen klurade jag lite och kom fram till det hÀr mÄste vara ett problem dÀr man ska nyttja Euklides algoritm. PÄ nÄgot sÀtt ville jag ju hitta talet som delade alla bussIDn med dess avgÄngstidsdeltan.

Det tog en rejÀl rÀd pÄ Internet innan jag mindes: Chinese remainder theorem! Bah. Först skÀmdes jag för att CRT hade flytt mitt minne; sen skÀmdes jag Àn mer för att jag hade glömt exakt hur man anvÀnder algoritmen... Men Svenska Wikipedia har en toppenförklaring som Àr direkt överförbar till dagens AoC-problem.

DÀrtill hittade jag en bra modul pÄ GitHub för att lösa CRT, sÄ min lösning pÄ Del 2 Àr egentligen bara att jag anvÀnder en 3pp...

Dold text

Dag: 14
SprÄk: Go
Lösning: Main,

Glöm inte att kika in pÄ vÄr leaderboard: 115994-59705230

NÀr det stod att talen var 36 bitar borde jag lÄtit bli att vara lat och köra pÄ med vanliga int; men Del 1 gick ju toppenbra utan att ta till 64-bitars-tal sÄ.... Aja. Dagens svÄraste grej, för mig, var att fixa sÄ att "001X0XX1" expanderades pÄ rÀtt sÀtt. Det slutade med, tycker jag, en ganska snygg lösning dÀr jag tar ÄteranvÀnde mitt favoritsÀtt att traversera trÀd.

Dold text
Visa signatur

:(){ :|:& };:

đŸŠđŸ»â€â™‚ïž   đŸšŽđŸ»â€â™‚ïž   đŸƒđŸ»â€â™‚ïž   ☕

PermalÀnk
Medlem ★
●

Dag 14, awk.

$ <in sed -E 's/\[(.*)\] =/ \1 /' | awk -f d14.awk

d14.awk

/mask/ { delete idx split($3, v, "") for (n = length(v) - 1; n >= 0; n--) { mask[n] = v[length(v) - n] if (mask[n] == "X") { idx[n] = length(idx) } } } /mem/ { into_binary($2, address) into_binary($3, value) for (n = 0; n < length(mask); n++) { address_masked[n] = mask[n] == "0" ? address[n] : mask[n] value_masked[n] = mask[n] == "X" ? value[n] : mask[n] } mem[$2] = into_decimal(value_masked) for (i = 0; i < 2^length(idx); i++) { into_binary(i, flux) for (n in idx) { address_masked[n] = flux[idx[n]]; } mem2[into_decimal(address_masked)] = $3 } } END { print sum_memory(mem) } END { print sum_memory(mem2) } function into_binary(val, result) { delete result for (n = 0; val > 0; n++) { result[n] = int(val % 2) val /= 2 } } function into_decimal(binary) { result = 0 for (n = 0; n < length(binary); n++) { result += binary[n] ? 2^n : 0 } return result } function sum_memory(mem) { sum = 0 for (i in mem) { sum += mem[i] } return sum }

MacOS kommer med nÄgon sunkig awk implementation frÄn 2007, och denna har inte stöd för bitvis operationer.. SÄ dÄ fick det bli sÄhÀr.

Dold text
Visa signatur

"Some poor, phoneless fool is probably sitting next to a waterfall somewhere, totally unaware of how angry and scared he's supposed to be." - Duncan Trussell

PermalÀnk
Medlem
●

Dag: 14
SprÄk: Golang
Lösning:

Finns sÀkert nÄgon smart bit operation, men jag gick för strÀngar..

Del1: 5ms
Del2: 98ms

package main import ( "bufio" "fmt" "math" "os" "strconv" "strings" ) type Program struct { Mask string Data []Data } type Data struct { Memory int Value int } func getPartOne(rows []string) int { programs := getPrograms(rows) sum := 0 result := map[int]int{} for _, program := range programs { for _, data := range program.Data { binaryValue := fmt.Sprintf("%036b", data.Value) for j, r := range program.Mask { if r == rune('X') { continue } binaryValue = replaceAtIndex(binaryValue, r, j) } resultValue, _ := strconv.ParseInt(binaryValue, 2, 64) result[data.Memory] = int(resultValue) } } for key := range result { sum += result[key] } return sum } func replaceAtIndex(in string, r rune, i int) string { out := []rune(in) out[i] = r return string(out) } func getPartTwo(rows []string) int { programs := getPrograms(rows) //fmt.Printf("Programs: %v\n", programs) sum := 0 result := map[int]int{} for _, program := range programs { for _, data := range program.Data { memoryBinaryValue := fmt.Sprintf("%036b", data.Memory) xIndexes := []int{} memoryAddresses := []string{} for j, r := range program.Mask { if r == rune('0') { continue } if r == rune('X') { xIndexes = append(xIndexes, j) } memoryBinaryValue = replaceAtIndex(memoryBinaryValue, r, j) } permutationCount := int(math.Pow(2, float64(len(xIndexes)))) for i := 0; i < permutationCount; i++ { indexBinaryValue := fmt.Sprintf("%0*b", len(xIndexes), i) tempMemoryBinaryValue := memoryBinaryValue for j := 0; j < len(indexBinaryValue); j++ { tempMemoryBinaryValue = strings.Replace(tempMemoryBinaryValue, "X", string(indexBinaryValue[j]), 1) } memoryAddresses = append(memoryAddresses, tempMemoryBinaryValue) } for _, memoryAddressValue := range memoryAddresses { memoryAdr, _ := strconv.ParseInt(memoryAddressValue, 2, 64) result[int(memoryAdr)] = data.Value } } } for key := range result { sum += result[key] } return sum } func getPrograms(rows []string) []Program { programs := []Program{} program := Program{} for i, row := range rows { if strings.HasPrefix(row, "mask") { if i > 0 { programs = append(programs, program) program = Program{} } startValueTag := "= " startValueIndex := strings.Index(row, startValueTag) program.Mask = row[startValueIndex+len(startValueTag):] } else { startMemoryTag := "[" startMemoryIndex := strings.Index(row, startMemoryTag) endMemoryIndex := strings.Index(row, "]") memoryVal := row[startMemoryIndex+len(startMemoryTag) : endMemoryIndex] memory, _ := strconv.Atoi(memoryVal) startValueTag := "= " startValueIndex := strings.Index(row, startValueTag) valueVal := row[startValueIndex+len(startValueTag):] value, _ := strconv.Atoi(valueVal) program.Data = append(program.Data, Data{ Memory: memory, Value: value, }) } } programs = append(programs, program) return programs } func getRows(filename string) []string { file, _ := os.Open(filename) defer file.Close() scanner := bufio.NewScanner(file) var rows []string for scanner.Scan() { rows = append(rows, scanner.Text()) } return rows } func main() { rows := getRows("../input.txt") fmt.Println("PartOne", getPartOne(rows)) fmt.Println("PartTwo", getPartTwo(rows)) }

Dold text
PermalÀnk
Medlem
●
Skrivet av gibbon_:

@Yoshman Àr tillbaka pÄ dag 10 och @Flexbert kör dag 14 redan.. Tror folk börjar bli trötta

Ja nÀrmar mig vÀggen.

PermalÀnk
Datavetare ★
●

Dag: 14
SprÄk: Swift
Lösning: Github

SvÄraste delen Àr kanske att fÄ inlÀggen rÀtt

Vet inte om det Àr för att jag (Äter igen) valt ett sprÄk jag inte behÀrskar, men Àr det inte problemen i Är lite mer Ät hÄllet att mycket a av lösningen handlar om att lÀsa in indata i ett "bekvÀmt" format? Spenderade typ 1/4 pÄ inlÀsning denna gÄng.

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 ★
●
Skrivet av Yoshman:

Vet inte om det Àr för att jag (Äter igen) valt ett sprÄk jag inte behÀrskar, men Àr det inte problemen i Är lite mer Ät hÄllet att mycket a av lösningen handlar om att lÀsa in indata i ett "bekvÀmt" format? Spenderade typ 1/4 pÄ inlÀsning denna gÄng.

Jag hÄller med dig. Jag la mycket hjÀrnverksamhet pÄ att tÀnka pÄ hur jag skulle parsea data.

Visa signatur

:(){ :|:& };:

đŸŠđŸ»â€â™‚ïž   đŸšŽđŸ»â€â™‚ïž   đŸƒđŸ»â€â™‚ïž   ☕

PermalÀnk
●

Dag: 14
SprÄk: Nim
Lösning: Github

Det mÀrks att det börjar bli en annan nivÄ pÄ uppgifterna nu. GÄrdagen gick katastrofalt, satt med papper och penna i en timme och försökte hitta nÄt men icke sa nicke. Sen kollade jag vad @GLaDER skrev om CRT, vilket jag aldrig hört talas om men med den gick det finemang.

Idag gick det bÀttre, det Àr ganska trevligt och sitta och skriva VMs men bit-operationer Àr vÀl inte min starka sida direkt. Men fick en tid pÄ 0.5ms respektive 10ms pÄ part1 och part2 till sist.

Dold text
PermalÀnk
Medlem ★
●

Dag 14, Python (Ingen list comprehension i dag heller, men ett regexp och en generator. Skulle kunna ha kört reduce, men det fick bli en vanlig for-loop över raderna.)

import re def Xbits(x, i): if i >= 36: yield 0 return bit = (1 << i) for y in Xbits(x, i + 1): yield y if x & bit: yield bit + y def mask(m, mem1, mem2, mask1, mask0, maskX): return (mem1, mem2, int(m[4].replace('X', '0'), 2), int(m[4].replace('X', '1'), 2), int(m[4].replace('1', '0').replace('X', '1'), 2)) def mem(m, mem1, mem2, mask1, mask0, maskX): mem1[int(m[3])] = int(m[4]) & mask0 | mask1 for x in Xbits(maskX, 0): mem2[int(m[3]) & ~maskX | mask1 + x] = int(m[4]) return mem1, mem2, mask1, mask0, maskX mem1, mem2 = {}, {} mask1 = mask0 = maskX = 0 for line in open("input"): m = re.search('(mask|mem)(\[(\d+)\])? = ([01X]{36}|(\d+))', line) mem1, mem2, mask1, mask0, maskX = eval(m[1])(m, mem1, mem2, mask1, mask0, maskX) print(sum(mem1.values()), sum(mem2.values()))

Dold text
PermalÀnk
Medlem
●

Tröttnat nÄgot pÄ AoC men skrev en simd optimerad version av Dag 11 del 1 i Scala/jdk16. Tar lite mindre Àn 0.2ms att köra utan io och med uppvÀrmd jvm pÄ en i7-8559U.

object Day11: val input = Files.readString(Path.of("11.txt")).split('\n') val inputHeight = input.length val inputWidth = input.head.length val spec = ByteVector.SPECIES_PREFERRED val height = inputHeight + 2 val width = (inputWidth + spec.length() - 1) / spec.length() * spec.length() + 2 val seatMasks = Array.ofDim[Boolean](height * width) for y <- 1 to inputHeight x <- 1 to inputWidth do seatMasks(y * width + x) = (input(y - 1)(x - 1) == 'L') def part1(seats: Array[Byte], seats2: Array[Byte], n: Int = 0): Int = var changed = false var y = 1 while y < height-1 do var x = 1 val mid = y * width val up = (y - 1) * width val down = (y + 1) * width while x < spec.loopBound(width) do val left = x - 1 val right = x + 1 val sum = ByteVector.fromArray(spec, seats, up + left).add( ByteVector.fromArray(spec, seats, up + x)).add( ByteVector.fromArray(spec, seats, up + right)).add( ByteVector.fromArray(spec, seats, mid + left)).add( ByteVector.fromArray(spec, seats, mid + right)).add( ByteVector.fromArray(spec, seats, down + left)).add( ByteVector.fromArray(spec, seats, down + x)).add( ByteVector.fromArray(spec, seats, down + right)) val cv = ByteVector.fromArray(spec, seats, mid + x) val sm = VectorMask.fromArray(spec, seatMasks, mid + x) val em = sum.compare(VectorOperators.EQ ,0) val om = sum.compare(VectorOperators.GE, 4) val uv = cv.blend(ByteVector.broadcast(spec, 0).add(ByteVector.broadcast(spec, 1), em), (em.or(om)).and(sm)) uv.intoArray(seats2, mid + x) changed = changed || cv.compare(VectorOperators.NE, uv).anyTrue() x += spec.length() end while y += 1 end while if changed then part1(seats2, seats, n + 1) else n end part1 def main(args: Array[String]): Unit = val seats = Array.ofDim[Byte](height * width) val seats2 = Array.ofDim[Byte](height * width) part1(seats, seats2) println(seats.count(_ == 1))

Dold text
PermalÀnk
Medlem ★
●
Skrivet av gibbon_:

Dag 14, awk.

$ <in sed -E 's/\[(.*)\] =/ \1 /' | awk -f d14.awk

d14.awk

/mask/ { delete idx split($3, v, "") for (n = length(v) - 1; n >= 0; n--) { mask[n] = v[length(v) - n] if (mask[n] == "X") { idx[n] = length(idx) } } } /mem/ { into_binary($2, address) into_binary($3, value) for (n = 0; n < length(mask); n++) { address_masked[n] = mask[n] == "0" ? address[n] : mask[n] value_masked[n] = mask[n] == "X" ? value[n] : mask[n] } mem[$2] = into_decimal(value_masked) for (i = 0; i < 2^length(idx); i++) { into_binary(i, flux) for (n in idx) { address_masked[n] = flux[idx[n]]; } mem2[into_decimal(address_masked)] = $3 } } END { print sum_memory(mem) } END { print sum_memory(mem2) } function into_binary(val, result) { delete result for (n = 0; val > 0; n++) { result[n] = int(val % 2) val /= 2 } } function into_decimal(binary) { result = 0 for (n = 0; n < length(binary); n++) { result += binary[n] ? 2^n : 0 } return result } function sum_memory(mem) { sum = 0 for (i in mem) { sum += mem[i] } return sum }

MacOS kommer med nÄgon sunkig awk implementation frÄn 2007, och denna har inte stöd för bitvis operationer.. SÄ dÄ fick det bli sÄhÀr.

Dold text

Fortfarande inte vackert, men ca. 30ggr snabbare om ens awk har stöd för det..

/mask/ { split($3, v, "") mask = 0 x1 = 0 delete idx for (n = 0; n < length(v); n++) { mask += (v[length(v) - n] == 1) * 2^n x1 += (v[length(v) - n] == "X") * 2^n if (v[length(v) - n] == "X") { idx[length(idx)] = n } } x0 = compl(x1) delete fluxers for (i = 0; i < 2^length(idx); i++) { flux = 0 for (n in idx) { flux += int(i / 2^n) % 2 ? 2^idx[n] : 0 } fluxers[or(mask, flux)] } } /mem/ { mem[$2] = or(and($3, x1), mask) for (flux in fluxers) { mem2[or(and(or($2, flux), x0), and(flux, x1))] = $3 } } END { print sum_memory(mem) } END { print sum_memory(mem2) } function sum_memory(mem) { sum = 0 for (i in mem) { sum += mem[i] } return sum }

Dold text
Visa signatur

"Some poor, phoneless fool is probably sitting next to a waterfall somewhere, totally unaware of how angry and scared he's supposed to be." - Duncan Trussell

PermalÀnk
Medlem ★
●

AlltsÄ, va? Dag 13 del 2. Kompilerar ni fram svaret pÄ nÄgra sekunder? Min kod har löst alla dessa exempel:

7,13,x,x,59,x,31,19

och

The earliest timestamp that matches the list 17,x,13,19 is 3417.
67,7,59,61 first occurs at timestamp 754018.
67,x,7,59,61 first occurs at timestamp 779210.
67,7,x,59,61 first occurs at timestamp 1261476.
1789,37,47,1889 first occurs at timestamp 1202161486.

Dold text

Varav den sistnÀmnda tog ca 5 minuter att bruteforcera. Nu kör jag med originalinputen och enligt min berÀkning skulle det ta 83.000 gÄnger sÄ gÄng tid, dvs nÀstan 7000 timmar. 288 jÀvla dagar.

Jag kÀnner mig sÄ dum och mÄllös!

Visa signatur

| Mobo: Gigabyte X570 GAMING X | CPU: AMD Ryzen 9 3900X + Dark Rock 4 | RAM: 32GB @ 3000MHz | GPU: Gigabyte RTX 3080 OC | PSU: Seasonic GX 850W | Chassi: NZXT S340 Elite Matte Black | M.2: Samsung 970 Evo 500GB & 1000GB | HDD: 4TB | Monitors: Acer Predator X34 GS & Acer XB270HU |

PermalÀnk
Medlem ★
●

Jag har nu kommenterat ut koder för att se vad som gÄr sÄ himla lÄngsamt. Det var tydligen BigInteger klassen i Kotlin, dess modulus operator verkar vara vÀldigt trög, tyvÀrr. Jag optimerade koden till att lösa det sista exemplet pÄ 2m 22s istÀllet för 5 minuter, sen kommenterade jag ut allt och breakade loopen sÄ fort iteratorn hamnade pÄ samma tal. Tog 11s. SÄ jag fÄr komma pÄ ett sÀtt att ha feta steps och försöka undvika att anvÀnda BigIntegers modulusmetod.

Detta Àr roligt!

EDIT: Jag vet inte varför jag inte bara anvÀnde Long frÄn början. Nere pÄ 37 sekunder nu för exemplet. Fortfarande för hemskt lÄngsamt. NÀr jag testade att bara köra plain timestamp++ för varje loop tog det ÀndÄ fett lÄng tid sÄ jag förstod att jag mÄste göra stora kliv i loopen och inte bara steppa upp med 1. Har nÄgon tips pÄ hur jag kan rÀkna ut dessa kliv?

GitHub.

Visa signatur

| Mobo: Gigabyte X570 GAMING X | CPU: AMD Ryzen 9 3900X + Dark Rock 4 | RAM: 32GB @ 3000MHz | GPU: Gigabyte RTX 3080 OC | PSU: Seasonic GX 850W | Chassi: NZXT S340 Elite Matte Black | M.2: Samsung 970 Evo 500GB & 1000GB | HDD: 4TB | Monitors: Acer Predator X34 GS & Acer XB270HU |

PermalÀnk
Medlem ★
●
Skrivet av Dave1080:

Jag har nu kommenterat ut koder för att se vad som gÄr sÄ himla lÄngsamt. Det var tydligen BigInteger klassen i Kotlin, dess modulus operator verkar vara vÀldigt trög, tyvÀrr. Jag optimerade koden till att lösa det sista exemplet pÄ 2m 22s istÀllet för 5 minuter, sen kommenterade jag ut allt och breakade loopen sÄ fort iteratorn hamnade pÄ samma tal. Tog 11s. SÄ jag fÄr komma pÄ ett sÀtt att ha feta steps och försöka undvika att anvÀnda BigIntegers modulusmetod.

Detta Àr roligt!

SÄ nu kan du fÄ svaret inom en dag kanske?

Feta steps Àr absolut rÀtt riktning

Om du hittat T dÀr buss 3 avgÄr, behöver du titta pÄ T+1 eller T+2?

Om du hittat T dÀr buss 3 OCH 5 avgÄr, behöver du titta pÄ T+3?

ytterligare
om du vill ha ytterligare en nudge
Visa signatur

"Some poor, phoneless fool is probably sitting next to a waterfall somewhere, totally unaware of how angry and scared he's supposed to be." - Duncan Trussell

PermalÀnk
Medlem ★
●

Dag 15, awk.

Är det bara jag eller var del 2 en luring?

$ <in tr ',' '\n' | awk '{ speak($1) } END { while (1) { speak(pp[n] ? p[n] - pp[n] : 0) } } function speak(m) { pp[m] = p[m]; p[m] = ++t; print n = m }' | sed -n '2020p;30000000p;30000000q'

Börjar bli less pÄ bristande gamla BSD varianter av kommandon i macOS..

Dold text
Visa signatur

"Some poor, phoneless fool is probably sitting next to a waterfall somewhere, totally unaware of how angry and scared he's supposed to be." - Duncan Trussell

PermalÀnk
Medlem ★
●

Dag 15, Python

Uppgift 1 tog ett par försök att fÄ allting rÀtt. Sedan kikade jag pÄ uppgift tvÄ och satt lÀnge och letade mönster i min output frÄn ettan och suckade över mina bortglömda mattekurser. NÀr jag prövade att bara köra loopen till 30000000 var det ju inga problem. Det mÄste bara varit ett filter för alltför naiva lösningar.

age = {} count = 1 for n in [5,2,8,16,18,0,1]: age[n] = (count, count) last = n count += 1 while count <= 30000000: if last in age: last = age[last][1] - age[last][0] else: last = 0 if last in age: age[last] = (age[last][1], count) else: age[last] = (count, count) if (count in [2020, 30000000]): print(last) count += 1

Dold text
Meningsbyggnad
PermalÀnk
Medlem ★
●

@Ingetledigtnamn

Det jag menade med luring.

Jag insÄg direkt att jag inte hade en aning för del 2, och tÀnkte att 30M iterationer Àr vÀl inte sÄ farligt.. SÄ jag satte igÄng den medan jag började tÀnka vidare lite men fick svar inom kort.
BÄda vÄra lösningar Àr ju ganska "naiva". Enda halv-vettiga lösningen jag kan tÀnka mig som skulle fÄ problem med del 2 Àr vÀl en rekursiv sÄdan.
Kan fortfarande inte tÀnka mig nÄgon sÀrskilt smart lösning annars.

Dold text
Visa signatur

"Some poor, phoneless fool is probably sitting next to a waterfall somewhere, totally unaware of how angry and scared he's supposed to be." - Duncan Trussell