🌟 Advent of Code (AoC) 2021 🌟

PermalÀnk
Medlem ♄ ★
●
Skrivet av GLaDER:

Dag: 24
SprÄk: Python 3
Lösning: GitHub

Jag vill sÀga att dagens uppgift Àr rÀtt sorts uppgift för mig. Jag har alltid tyckt om assemblering och brukar ha lÀtt för att se mönster; men icke. NÀr jag snubblade över https://github.com/dphilipson/advent-of-code-2021/blob/master... blev det dock lÀttare och jag kunde inspireras fram till lösningen ovan.

Dold text

Dag: 25
SprÄk: Python 3
Lösning: GitHub

Idag gjorde jag en upptÀckt i Python!

SjÀlva steglogiken i min initiala lösning sÄg ut sÄhÀr:

def move(east, south, width, height): new_east = dict() new_south = dict() for (x, y) in east: if ((x + 1) % width, y) not in east | south: new_east[((x + 1) % width, y)] = ">" else: new_east[(x, y)] = ">" for (x, y) in south: if (x, (y + 1) % height) not in south | new_east: new_south[(x, (y + 1) % height)] = "v" else: new_south[(x, y)] = "v" return new_east, new_south

Jag tyckte det var snyggt att jag lyckades hÄlla isÀr östgÄende och södergÄende sjögurkor i olika ordböcker och sedan bara slÄ ihop dem vid behov. (Egentligen var jag inne pÄ att göra samma sak, fast med listor, men dit kom jag aldrig.) Lösningen ovan Àr dock vansinnigt lÄngsam. Jag kan bara anta att just: x | y-operationen Àr vÀÀÀldigt lÄngsam.

Skrev om lösningen till att bara anvÀnda en ordbok:

def move_east(sea, width): new_sea = dict() for (x, y) in sea: if sea[(x, y)] == ">" and ((x + 1) % width, y) not in sea: new_sea[((x + 1) % width, y)] = ">" else: new_sea[(x, y)] = sea[(x, y)] return new_sea def move_south(sea, height): new_sea = dict() for (x, y) in sea: if sea[(x, y)] == "v" and (x, (y + 1) % height) not in sea: new_sea[(x, (y + 1) % height)] = "v" else: new_sea[(x, y)] = sea[(x, y)] return new_sea

och nu fÄr jag en lösing pÄ typ 1.5 sekunder.

Kan nÄgon av Python-proffsen hÀr i trÄden komma med nÄgon insikt hÀr?

Dold text

Det gÄr sÀkert att golfa lite till och fÄ till Ànnu snyggare kod, men jag har fortfarande inte tagit tag i uppgift 19; den har prio. Det Àr dock julfirande pÄ ingÄng hÀr sÄ det ligger i farans riktning att jag fÄr lösa uppgift 19 pÄ planet tillbaka till Sverige, i mellandagarna.

Tack för i Är kamrater. Lika trevligt som alltid!

PermalÀnk
●

Dag 24
SprÄk: Svenska

VĂ€ldigt klurig och kul dag tycker jag!

Byggde en ALU, men fattade inte sÄ noga vad jag skulle anvÀnda den till, sÄ övergick till att studera koden istÀllet.

Ganska snart ser man att alla siffror hanteras snarlikt i en 14 stegs loop.
Ett tal ackumuleras mellan varje iterationssteg. Och koden avslöjar att det har bas 26.
Skriver man ut det ackumulerade talet mellan varje iteration (dvs för varje siffra i input) sÄ ser man att det fungerar som en stack, dÀr föregÄende tal kan multipliceras med 26 eller delas bort, beroende pÄ ett villkor pÄ input. Vissa steg i itertionen kan inte reducera stacken, dÄ divisionen Àr 1 i dem. Dessa kommer bygga stacken oavsett och man kan maximera eller minimera dem endast med hÀnseende till att dess stackbidrag senare Àr reducerbart.
I sista iterationen mÄste "stacken" vara mellan 13-21 för att kunna delas bort för att nÄ 0.

Genom att studera additions-konstanterna sÄ kan man lösa ut största och minsta giltiga tal!

(NÀr nu algoritmen Àr avslöjad, kan man sÀkert fiffla ihop ett program som löser det ocksÄ, men ser ingen anledning till det nu.)

Dold text
PermalÀnk
●
Skrivet av GLaDER:

Dag: 25
SprÄk: Python 3
Lösning: GitHub

Idag gjorde jag en upptÀckt i Python!

SjÀlva steglogiken i min initiala lösning sÄg ut sÄhÀr:

def move(east, south, width, height): new_east = dict() new_south = dict() for (x, y) in east: if ((x + 1) % width, y) not in east | south: new_east[((x + 1) % width, y)] = ">" else: new_east[(x, y)] = ">" for (x, y) in south: if (x, (y + 1) % height) not in south | new_east: new_south[(x, (y + 1) % height)] = "v" else: new_south[(x, y)] = "v" return new_east, new_south

Jag tyckte det var snyggt att jag lyckades hÄlla isÀr östgÄende och södergÄende sjögurkor i olika ordböcker och sedan bara slÄ ihop dem vid behov. (Egentligen var jag inne pÄ att göra samma sak, fast med listor, men dit kom jag aldrig.) Lösningen ovan Àr dock vansinnigt lÄngsam. Jag kan bara anta att just: x | y-operationen Àr vÀÀÀldigt lÄngsam.

Skrev om lösningen till att bara anvÀnda en ordbok:

def move_east(sea, width): new_sea = dict() for (x, y) in sea: if sea[(x, y)] == ">" and ((x + 1) % width, y) not in sea: new_sea[((x + 1) % width, y)] = ">" else: new_sea[(x, y)] = sea[(x, y)] return new_sea def move_south(sea, height): new_sea = dict() for (x, y) in sea: if sea[(x, y)] == "v" and (x, (y + 1) % height) not in sea: new_sea[(x, (y + 1) % height)] = "v" else: new_sea[(x, y)] = sea[(x, y)] return new_sea

och nu fÄr jag en lösing pÄ typ 1.5 sekunder.

Kan nÄgon av Python-proffsen hÀr i trÄden komma med nÄgon insikt hÀr?

Dold text

Det gÄr sÀkert att golfa lite till och fÄ till Ànnu snyggare kod, men jag har fortfarande inte tagit tag i uppgift 19; den har prio. Det Àr dock julfirande pÄ ingÄng hÀr sÄ det ligger i farans riktning att jag fÄr lösa uppgift 19 pÄ planet tillbaka till Sverige, i mellandagarna.

Tack för i Är kamrater. Lika trevligt som alltid!

Hmm, jag har inte helt satt mig in i din lösning men jag tycker det ser ut som att ditt misstag Àr att du berÀknar unionen pÄ nytt mellan east och south, för varje element i east. I och med att du inte uppdaterar east eller south skulle du kunna berÀkna unionen (en gÄng) innan loopen istÀllet. Samma sak i andra loopen med south | new_east.

Dold text
PermalÀnk
Medlem ♄
●
PermalÀnk
Datavetare ♄ ★
●

Dag: 25
SprÄk: Rust

Givet hur reglerna för förflyttning Àr designade gÄr det att göra dessa m.h.a. bitoperationer för att hantera upp till 64 sjögurkor i stöten
Tar <500 ”s att lösa problemet pÄ en M1.

Men blir inte precis den kortaste/enklaste lösningen...

use crate::solution::Solution; use std::fmt::Debug; const WIDTH: usize = 139; const HEIGHT: usize = 137; // Size of 3 is WIDTH / 3 rounded towards infinity type Row = [u64; 3]; struct Day25 { state: State, } impl Solution for Day25 { fn part1(&mut self) -> String { self.move_steps().to_string() } fn part2(&mut self) -> String { String::from("") } } impl Day25 { fn move_steps(&self) -> u32 { let mut steps = 0; let mut prev_state = self.state; loop { steps += 1; let mut state = prev_state; state.move_east(); state.move_south(); if state == prev_state { break steps; } prev_state = state; } } } pub fn new(input: &str) -> Box<dyn Solution> { let mut state = State { east: [Row::default(); HEIGHT], south: [Row::default(); HEIGHT], }; for (row, cols) in input.lines().enumerate() { for (col, ch) in cols.chars().enumerate() { let (i, shift) = col_to_index_and_shift(col); match ch { '>' => state.east[row][i] |= 1 << shift, 'v' => state.south[row][i] |= 1 << shift, _ => (), } } } Box::new(Day25 { state }) } fn col_to_index_and_shift(col: usize) -> (usize, usize) { let i = col / 64; let mut shift = if i < 2 { 63 } else { WIDTH % 64 - 1 }; shift -= col % 64; (i, shift) } #[derive(Clone, Copy, PartialEq)] struct State { east: [Row; HEIGHT], south: [Row; HEIGHT], } impl State { fn move_east(&mut self) { for row_num in 0..HEIGHT { let east_row = self.east[row_num]; let south_row = self.south[row_num]; let rotated_row = [ (east_row[0] >> 1) | (east_row[2] << 63), (east_row[1] >> 1) | (east_row[0] << 63), (east_row[2] >> 1) | ((east_row[1] & 1) << ((WIDTH - 1) % 64)), ]; let occupied = [ east_row[0] | south_row[0], east_row[1] | south_row[1], east_row[2] | south_row[2], ]; let moving = [ rotated_row[0] & !occupied[0], rotated_row[1] & !occupied[1], rotated_row[2] & !occupied[2], ]; let need_clr = [ (moving[0] << 1) | (moving[1] >> 63), (moving[1] << 1) | (moving[2] >> ((WIDTH - 1) % 64)), ((moving[2] << 1) & ((1 << WIDTH % 64) - 1) as u64) | (moving[0] >> 63), ]; self.east[row_num] = [ (east_row[0] | moving[0]) & !need_clr[0], (east_row[1] | moving[1]) & !need_clr[1], (east_row[2] | moving[2]) & !need_clr[2] ]; } } fn move_south(&mut self) { let first_row = self.south[0]; let mut just_moved = Row::default(); for row_num in 0..HEIGHT { let is_last_row = row_num + 1 == HEIGHT; let from_south_row = self.south[row_num]; let (east_row, south_row) = if is_last_row { (self.east[0], first_row) } else { (self.east[row_num + 1], self.south[row_num + 1]) }; let occupied = [ south_row[0] | east_row[0] | just_moved[0], south_row[1] | east_row[1] | just_moved[1], south_row[2] | east_row[2] | just_moved[2], ]; let moving = [ from_south_row[0] & !occupied[0], from_south_row[1] & !occupied[1], from_south_row[2] & !occupied[2], ]; just_moved = moving; self.south[row_num] = [ from_south_row[0] & !moving[0], from_south_row[1] & !moving[1], from_south_row[2] & !moving[2], ]; if is_last_row { self.south[0] = [ self.south[0][0] | moving[0], self.south[0][1] | moving[1], self.south[0][2] | moving[2], ]; } else { self.south[row_num + 1] = [ south_row[0] | moving[0], south_row[1] | moving[1], south_row[2] | moving[2], ]; } } } }

Dold text
PermalÀnk
Medlem ♄ ★
●

Dag: 25
SprÄk: Python (numpy)

import numpy as np from itertools import count a = np.array([[".v>".index(c) for c in l.strip()] for l in open("input25").readlines()], dtype = np.byte) def move(a): e = np.roll(a,-1, axis = 1) cond = ((a == 2) & (e == 0)) a[cond] = 0 a += np.roll(cond * 2, 1, axis = 1) s = np.roll(a,-1, axis = 0) cond = ((a == 1) & (s == 0)) a[cond] = 0 a += np.roll(cond * 1, 1, axis = 0) return a for i in count(1): steady = a.copy() a = move(a) if (a == steady).all(): break print(i)

Dold text
PermalÀnk
Medlem ♄ ★
●

Dag: 24
SprÄk: Python (Ganska snÀll Python, inga nÀstlade list comprehensions )

Denna lösning Àr lite av en "bredden först"-variant. Den kör den virtuella maskinen för alla inputs parallellt. Maskinen jobbar med tupler som bestÄr av ett vÀrde och en numpy-array med bitmasker för vilken input detta vÀrde Àr giltigt. 14 siffror med vÀrden mellan 1 och 9 blir 22876792454961 olika inputs att testa Mitt första försök gick in i vÀggen straxt efter 100 instruktioner. Instruktionerna eql, div och mod drar ju ner pÄ antalet vÀrden, men det var först nÀr jag lÀst vad @MultiMike skrev och jag löst det för hand jag insÄg att det faktiskt skulle kunna gÄ att göra.

Om vi tittar pÄ koden sÄ bestÄr den av 14 snarlika sektioner

inp w mul x 0 add x z mod x 26 div z A add x B eql x w eql x 0 mul y 0 add y 25 mul y x add y 1 mul z y mul y 0 add y w add y C mul y x add z y

Om vi översÀtter detta till exempelvis Python skulle det kunna se ut sÄ hÀr

inp w x = x * 0 x = x + z x = x % 26 z = z / A x = x + B x = (x == w) x = (x == 0) y = y * 0 y = y + 25 y = y * x y = y + 1 z = z * y y = y * 0 y = y + w y = y + C y = y * x z = x + y

Efter lite uttrycksförenklingar blir det

inp w x = (z % 26 + B != w) z = z / A z = z * (25 * x + 1) z = z + (w + C) * x

x kommer bara kunna ha vÀrdet 1 eller 0 sÄ lÄt oss konstantpropagera de vÀrdena.

inp w if z % 26 + B != w: x = 1 z = z / A z = z * (25 * x + 1) z = z + (w + C) * x else: x = 0 z = z / A z = z * (25 * x + 1) z = z + (w + C) * x

förenkla igen

inp w if z % 26 + B != w: z = (z / A) * 26 + w + C else: z = z / A

VÀrdena för A Àr antingen 1 eller 26, sju av varje, och pÄ den hÀr formen Àr det ganska klart att de enda fallen dÀr vi kommer fÄ tillbaka en nolla i z Àr dÄ vi lyckas lyckas utföra divisionen med 26 utan att lÀgga till nÄgra nya vÀrden till z. Med andra ord, om nÄgra av testerna i eql x w Àr sanna Àr det bara de vÀrdena vi behöver fortsÀtta att kontrollera. Inga av de andra vÀrden kommer att kunna fÄ ner z till 0 igen.

HÀr kommer pmonad, den virtuella maskinen som kör alla inputs parallellt. Koden Àr ganska rÀttfram. Det enda knepiga Àr shrink som reducerar storleken pÄ det state som skickas runt. Körtid pÄ min Skylake Àr runt 30 minuter och minnesÄtgÄngen Àr mÄttlig.

from collections import defaultdict from itertools import product import re import numpy as np program = [re.match("(\w\w\w) (\w) ?(\w|\-?\d+)?$", l.strip()) for l in open("input24").readlines()] anydigit = 0x3fe norestrictions = np.array([anydigit] * 14) def shrink(l): """Merge list members if they are identical in all but one restriction""" def is_mergeable_range(a, i): """Since a is sorted it is enough to look at nine sequential elements to see if they are mergeable range. Comparing row i to the next eight row produces a boolean matrix. "and" it columnwise to see if all the rows compared identically to row i. If that was true for 13 columns we can merge the nine restrictions into one. """ return (i + 8 < a.shape[0] and np.logical_and.reduce(a[i + 1:i + 9] == a[i]).sum() == 13) # Collect restrictions per value d = defaultdict(list) for v, r in l: d[v].append(r) for v, l in d.items(): last = [] while len(l) != len(last): last = l a = np.array(l, dtype = np.short) include_in_sort = tuple(a[:,i] for i in range(14) if (a[:,i] != anydigit).any()) # If merged back to [anydigit, anydigit, ..., anydigit] we're done if include_in_sort: a = a[np.lexsort(include_in_sort)] l = [] i = 0 while i < a.shape[0]: if is_mergeable_range(a, i): l.append(np.bitwise_or.reduce(a[i:i + 9])) i += 9 else: l.append(a[i]) i += 1 d[v] = l # Go back to the (one value, one restriction) form return [(v, r) for v, restrictions in d.items() for r in restrictions] def input_digit(condition, i): """The value i and the matching restriction""" a = norestrictions.copy() a[condition] = 1 << i return a def inp(a, b, state): """Set a to [1,2, ..., 9] with matching restrictions""" digit = state['digit'] state['digit'] += 1 state[a] = [(i, input_digit(digit, i)) for i in range(1, 10)] return state def addi(a, b, state): state[a] = [(v + b, r) for v, r in state[a]] return state def add(a, b, state): """Add all values in a to all values in b if the restrictions allow it. Special case for adding something to zero. """ s = state[a] if s[0] == 0 and (s[1] == norestrictions).all(): # copy operation? state[a] = state[b] else: state[a] = [(t1 + t2, r) for (t1, r1), (t2, r2) in product(s, state[b]) if (r := r1 & r2).all()] return state def muli(a, b, state): """Multiply all values in a with b, unless b is 0, then it is just 0""" if b != 0: state[a] = [(v * b, r) for v, r in state[a]] else: state[a] = [(0, norestrictions)] return state def mul(a, b, state): """Multiply all values in a with all values in b if the restrictions allow it. Special case for multiplying something with one. """ s = state[a] if s[0] == 1 and (s[1] == norestrictions).all(): # copy operation? state[a] = state[b] else: state[a] = [(t1 * t2, r) for (t1, r1), (t2, r2) in product(s, state[b]) if (r := r1 & r2).all()] return state def divi(a, b, state): b = int(b) state[a] = shrink([(v // b, x) for v, x in state[a]]) return state def modi(a, b, state): b = int(b) state[a] = shrink([(v % b, x) for v, x in state[a]]) return state def eqli(a, b, state): state[a] = [(int(v == b), x) for v, x in state[a]] return state def eql(a, b, state): """Test all values in a for equality with all values in b and enforce restrictions. To reduce the amount of data we only keep the numbers that can lead to a successful result and we know the "eql x w" instruction must be true for the numbers that will be accepted by MONAD. So if any test was successful, keep only the "true" values and discard the "false" values. """ l = [[],[]] for (t1, r1), (t2, r2) in product(state[a], state[b]): e = int(t1 == t2) l[e].append((e, r1 & r2)) state[a] = l[1] or shrink(l[0]) return state def pmonad(): def is_immediate(b): return b and b[0] in "-0123456789" start = [(0, norestrictions)] state = { 'digit' : 0, 'x' : start, 'y' : start, 'z' : start, 'w' : start } for m in program: instr, a, b = m[1], m[2], m[3] if is_immediate(b): instr += "i" b = int(b) # No need for a switch, just evaluate instr to get the function state = eval(instr)(a, b, state) return state['z'] z0 = pmonad() decode = { 1 << i : str(i) for i in range(10) } l = [int("".join(decode[digit] for digit in zero[1])) for zero in z0] print(max(l), min(l))

Dold text
PermalÀnk
Datavetare ♄ ★
●

Ett mÄl med Ärets AoC var att lösa alla 25 luckorna pÄ under 1 sekund, det med indata liggande pÄ fil sÄ inga specialoptimeringar för just min indata.

Blev inte sÄ utmanande, Àven om ett par dagar vara hyfsat berÀkningsintensiva. I slutÀndan rÀckte det med en RPi4 för att komma under 1 sekund, kan lösa alla dagar pÄ ~850 ms dÀr medan det tar ~150 ms pÄ M1.

LÀngst tid (strax över 50 % av totaltiden) tog dag 23.

PermalÀnk
●
Skrivet av Yoshman:

Ett mÄl med Ärets AoC var att lösa alla 25 luckorna pÄ under 1 sekund, det med indata liggande pÄ fil sÄ inga specialoptimeringar för just min indata.

Blev inte sÄ utmanande, Àven om ett par dagar vara hyfsat berÀkningsintensiva. I slutÀndan rÀckte det med en RPi4 för att komma under 1 sekund, kan lösa alla dagar pÄ ~850 ms dÀr medan det tar ~150 ms pÄ M1.

LÀngst tid (strax över 50 % av totaltiden) tog dag 23.

Starkt jobbat!
Rust gÄr verkligen att fÄ prestanda ur om man hÄller tungan rÀtt i mun.

Kan absolut förstÄ tjusningen i att optimera körtiden. SjÀlv försökte jag mest nÄ i mÄl i första hand, och fÄ till kod som jag inte behövde skÀmmas för som bonus. Helst med funktionella lösningar, med icke muterande datastrukturer dÀr det var görbart.

Även om jag de sista dagarna anvĂ€nt alldeles för mĂ„nga timmar mot vad jag rĂ€knade med att lĂ€gga innan allt drog igĂ„ng, sĂ„ tycker att det var nyttigt att motionera hjĂ€rnan med dessa övningar. Det har ocksĂ„ varit vĂ€ldigt lĂ€rorikt och intressant att se andras lösningar pĂ„ problemen. Flera vassa programmerare hĂ€ckar hĂ€r tycker jag som har fiffiga lösningar!

MÄste ÀndÄ lovorda Scala som jag anvÀnde för mina lösningar. Det Àr en fröjd att programmera i. TypsÀkert och "concise". Flera gÄnger har jag jÀmfört med pythonlösningarna, dÄ det Àr nÄgon form av "mÄttstock" pÄ hur kompakt det kan bli, och tycker Scala inte ligger lÄngt efter trots typsÀkerhet. Ser fram emot att börja programmera Scala 3, som blir Ànnu trevligare vad gÀller lÀsbarhet.