đŸ•Żïž Advent of Code 2019 đŸ•Żïž

TrÀdvy PermalÀnk
Medlem ♄
Plats
NördCentrum
Registrerad
Jun 2011

Dag: 14
SprÄk: Haskell

Haha, skrev nÀstan exakt samma program som @Yoshman, fast Haskell! Antar att det bara finns sÄ mÄnga sÀtt man kan lösa ett problem pÄ.

{-# LANGUAGE NumDecimals #-} module Day14 (part1, part2) where import Data.Map (Map) import qualified Data.Map as Map import Control.Applicative import Data.Foldable import Data.Bifunctor import Lib import Parse type Chemical = String type Reactions = Map Chemical (Int, [(Int, Chemical)]) part1 :: IO Int part1 = fmap (produce 1 "FUEL" . parse) readInput part2 :: IO Int part2 = do inp <- readInput let reacts = parse inp produceFuel n = produce n "FUEL" reacts collectedOres = 1e12 -- Leftover chemicals from a previous fuel production could make the next -- batch cheaper, so we can't simply produce 1 fuel from scratch and -- calculate how many of those we can afford. Instead, calculate a lower -- bound and do a binary search. let maxOresPerFuel = produceFuel 1 lowerBound = div collectedOres maxOresPerFuel pure $ bsearchIntMax (\n -> produceFuel n < collectedOres) lowerBound collectedOres -- | Returns how much ORE it costs to produce the desired quantity and chemical -- from scratch produce :: Int -> Chemical -> Reactions -> Int produce num chemical reacts = fst (produce' num chemical (fmap (const 0) reacts)) where produce' n chem store = case (n, chem) of (0, _) -> (0, store) (_, "ORE") -> (n, store) _ -> let avail = store Map.! chem avail' = max 0 (avail - n) fromStore = avail - avail' n' = n - fromStore (perReact, deps) = reacts Map.! chem nReacts = div (n' - 1) perReact + 1 leftOver = perReact * nReacts - n' store' = Map.insert chem (avail' + leftOver) store in foldl' (\(o, s) (m, c) -> first (o +) (produce' (m * nReacts) c s)) (0, store') deps parse :: String -> Reactions parse = fmap Map.fromList (applyParser (sepEndBy reaction eol)) where reaction = do inputs <- sepBy amountChem (string ", ") string " => " (n, c) <- amountChem pure (c, (n, inputs)) amountChem = liftA2 (,) int (space1 *> word) readInput :: IO String readInput = readFile "inputs/day-14"

Och sÄ den binÀra sökningen frÄn min hjÀlpmodul:

bsearchIntMax :: (Int -> Bool) -> Int -> Int -> Int bsearchIntMax p low high = if low < high - 1 then let mid = low + div (high - low) 2 in uncurry (bsearchIntMax p) $ if p mid then (mid, high) else (low, mid) else if p high then high else low

Dold text

Gibb: Win10 - Ryzen 5 3600 - RX 580 - 16G 3000MHz DDR4
Server: Arch - 2 * Xeon X5570 - R9 280X - 32G DDR3 ECC

●
TrÀdvy PermalÀnk
Medlem ♄ ★
Plats
Uppsala
Registrerad
Dec 2008

Hmm,

Är det nĂ„gon annan som har problem med uppgift 15? Jag har en vĂ€g frĂ„n startpunkten till lĂ€ckan pĂ„ 212 steg, men nĂ€r jag matar in det fĂ„r jag som svar att det Ă€r för lĂ„gt?

●
TrÀdvy PermalÀnk
Medlem
Registrerad
Okt 2006
Skrivet av Ingetledigtnamn:

Hmm,

Är det nĂ„gon annan som har problem med uppgift 15? Jag har en vĂ€g frĂ„n startpunkten till lĂ€ckan pĂ„ 212 steg, men nĂ€r jag matar in det fĂ„r jag som svar att det Ă€r för lĂ„gt?

Hade inga problem.
Jag hade fler steg men det finns ju flera olika inputs..
Det Àr inte bara ett off-by-one error?

xbox live

●
TrÀdvy PermalÀnk
Datavetare ♄ ★
Plats
Stockholm
Registrerad
Jun 2011

Rust - dag 15

Skulle föredra att man sÄg bÄda delarna direkt. Fattar varför det Àr uppdelat pÄ det sÀttet för de som deltar i tÀvlingen, men gör att de tar lite lÀngre Àn nödvÀndigt för oss som bara vill lösa problem som en form av alternativt korsord...

Löste dagens lucka genom att först mappa upp hela utrymmet och spara det som en karta, detta genom att köra droid:en m.h.a. djupet-först (enklare att dÄ kunna göra "undo" pÄ förflyttning).

Löser sedan bÄda problemen i en smÀll genom att starta pÄ syresystemet, fylla alla tomma rutor med syre och registrera hur lÄngt man rört sig frÄn syresystemet nÀr man fyller startpunkten (svar pÄ del 1). Svar pÄ del 2 Àr maximalt antal steg frÄn startpunkten nÀr alla tomma rutor Àr fyllda med syre.

type Map = HashMap<Vec2D, Tile>; #[derive(Debug, PartialEq)] enum Dir { North, South, West, East, } // Tuple with direction forward and direction to undo fn to_dirs(to: Vec2D, from: Vec2D) -> (Dir, Dir) { if to.x == from.x { if to.y > from.y { (Dir::North, Dir::South) } else { (Dir::South, Dir::North) } } else { if to.x > from.x { (Dir::East, Dir::West) } else { (Dir::West, Dir::East) } } } fn from_dir(dir: Dir) -> Intcode { match dir { Dir::North => 1, Dir::South => 2, Dir::West => 3, _ => 4, } } #[derive(Copy, Clone, Debug, PartialEq)] enum Tile { Wall, Space, Oxygen, } fn to_tile(ic: Intcode) -> Tile { match ic { 0 => Tile::Wall, 1 => Tile::Space, 2 => Tile::Oxygen, _ => panic!("Invalid feedback code"), } } #[derive(Clone, Copy, Debug, Hash, Eq, PartialEq)] struct Vec2D { x: i32, y: i32, } fn next_pos(pos: Vec2D, pred: &dyn Fn(&Vec2D) -> bool) -> Vec<Vec2D> { vec![ Vec2D { x: pos.x, y: pos.y + 1 }, Vec2D { x: pos.x, y: pos.y - 1 }, Vec2D { x: pos.x - 1, y: pos.y }, Vec2D { x: pos.x + 1, y: pos.y }, ] .into_iter() .filter(pred) .collect() } fn depth_first( pos: Vec2D, map: &mut Map, joystick: &Sender<Intcode>, droid: &Receiver<Intcode>, ) { for np in next_pos(pos, &|p| !map.contains_key(p)) { let (dir, undo) = to_dirs(np, pos); joystick.send(from_dir(dir)).unwrap(); let tile = to_tile(droid.recv().unwrap()); map.insert(np, tile); if tile != Tile::Wall { depth_first(np, map, joystick, droid); joystick.send(from_dir(undo)).unwrap(); if to_tile(droid.recv().unwrap()) != Tile::Space { panic!("Failed to undo move"); } } } } fn explore_map(program: &Vec<Intcode>) -> Map { let (joystick, sink) = channel(); let output = exec(program, sink, None); let mut map = HashMap::new(); map.insert(Vec2D { x: 0, y: 0 }, Tile::Space); depth_first(Vec2D { x: 0, y: 0 }, &mut map, &joystick, &output); map } fn fill_map_with_oxygen(map: &mut Map) -> (u32, u32) { let start_pos = Vec2D { x: 0, y: 0 }; let &oxygen_pos = map.iter().filter(|(_, &v)| v == Tile::Oxygen).next().unwrap().0; let mut q = VecDeque::new(); q.push_back((oxygen_pos, 0)); let mut steps_to_start = 0; let mut steps_to_fill = 0; // Breadth-first search with oxygen while let Some((pos, steps)) = q.pop_front() { for np in next_pos(pos, &|p| map.get(p).unwrap() == &Tile::Space) { q.push_back((np, steps + 1)); map.insert(np, Tile::Oxygen); } if pos == start_pos { steps_to_start = steps; } steps_to_fill = steps; } (steps_to_start, steps_to_fill) } impl Solution for State { fn part1(&self) -> String { let mut map = explore_map(&self.program); let (steps_to_oxygen, _) = fill_map_with_oxygen(&mut map); steps_to_oxygen.to_string() } fn part2(&self) -> String { let mut map = explore_map(&self.program); let (_, min_to_fill) = fill_map_with_oxygen(&mut map); min_to_fill.to_string() } }

Bra snurr i Rust, trots multitrÄdad lösning som i Intcode fallen faktiskt försÀmrar prestanda och löser egentligen allt tvÄ gÄnger... Denna tog totalt 40 ms pÄ i7-8559U

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

●
TrÀdvy PermalÀnk
Medlem ♄
Plats
NördCentrum
Registrerad
Jun 2011

Dag: 15
SprÄk: Haskell

Hmm, blev inte sÄ nöjd med denna dagens lösning. Inte överdrivet lÄng förvisso, men ganska svÄrlÀst tycker jag. Hade svÄrt att ÄteranvÀnda breadth-first search funktionen för bÄda delarna pÄ ett fint och ordentligt sÀtt. Nu blev den lite fulhackad istÀllet.

{-# LANGUAGE LambdaCase #-} module Day15 (part1, part2) where import Data.Set (Set) import qualified Data.Set as Set import Data.Functor import Data.Maybe import Data.Sequence (Seq) import qualified Data.Sequence as Seq import Data.Either import Vec import Intcode type Pos = Vec2 Int part1 :: IO Int part1 = fmap (fst . findO2System . parseIntcode) readInput part2 :: IO Int part2 = readInput <&> \s -> let pgm = parseIntcode s (_, o2Cont) = findO2System pgm in fromLeft (error "multiple O2 systems?") (bfs o2Cont) findO2System :: Mem -> (Int, Continuation) findO2System pgm = let (_, startCont) = stepIntcode pgm in fromRight (error "O2 system not found") (bfs (fromJust startCont)) -- | Breadth-first search to find either the time to fill the chamber with -- oxygen (if starting in the position of the oxygen system), or the oxygen -- system itself. bfs :: Continuation -> Either Int (Int, Continuation) bfs cont = bfs' Set.empty (Vec2 0 0, 0, cont) Seq.empty bfs' :: Set Pos -> (Pos, Int, Continuation) -> Seq (Pos, Int, Continuation) -> Either Int (Int, Continuation) bfs' visiteds (p, l, (Cont cont)) nexts = let dirs = filter (not . flip Set.member visiteds . snd) $ zip [1, 2, 3, 4] (map (p +) [Vec2 0 1, Vec2 0 (-1), Vec2 (-1) 0, Vec2 1 0]) l' = l + 1 bfs'' = \case [] -> Right [] (dir, q) : ds -> case cont dir of ((_, [0]), _) -> bfs'' ds ((_, [1]), Just cont') -> fmap ((q, l', cont') :) (bfs'' ds) ((_, [2]), Just cont') -> Left cont' _ -> error "unexpected case in bfs''" in case bfs'' dirs of Left cont' -> Right (l', cont') Right ns -> case Seq.viewl (nexts Seq.>< Seq.fromList ns) of Seq.EmptyL -> Left l next Seq.:< nexts' -> bfs' (Set.union (Set.fromList (p : (map (\(q, _, _) -> q) ns))) visiteds ) next nexts' readInput :: IO String readInput = readFile "inputs/day-15"

Behövde ocksÄ göra en Àndring till min Intcode-maskin sÄ att den kan returnera continuations. Tidigare kunde den bara ta en lista av inputs som potentiellt var cykliskt definierad i termer av outputen med hjÀlp av laziness, men detta medförde att jag inte kunde köra en gemensam exekvering för de första n inputsen, och sedan grena exekveringen till 4st dÀr varje gren fortsÀtter med olika inputs.

Nu fungerar Intcode maskinen istÀllet sÄ att den avbryter exekveringen och returnerar en continuation nÀr den stöter pÄ en input instruction. En continuation tar ett inmatningsvÀrde och fortsÀtter exekveringen tills man nÄr halt eller ytterligare en input instruktion igen. Continuationen man fÄr kan man sedan dela pÄ 4 och mata varje gren med var sitt vÀderstreck.

De intressanta delarna av Àndringen:

runIntcode :: [Int] -> Mem -> (Mem, [Int]) runIntcode inps pgm = let run is = \case ((_, outs), Just (Cont cont)) -> second (outs ++) (run (tail is) (cont (head is))) (r, Nothing) -> r in run inps (stepIntcode pgm) -- | Run the Intcode program until it asks for input or halts stepIntcode :: Mem -> ((Mem, [Int]), Maybe Continuation) stepIntcode pgm = evalState stepIntcode' (IntcodeSt 0 (Addr 0) pgm) where stepIntcode' = do (r, outs) <- runWriterT multistep m <- use mem fmap ((m, outs), ) $ case r of Nothing -> pure Nothing Just mode -> do st <- get let cont inp = evalState (store inp mode *> stepIntcode') st pure (Just (Cont cont)) multistep :: Intcode (Maybe Mode) multistep = step >>= \case Continue -> multistep Halt -> pure Nothing Input mode -> pure (Just mode)

Dold text

Gibb: Win10 - Ryzen 5 3600 - RX 580 - 16G 3000MHz DDR4
Server: Arch - 2 * Xeon X5570 - R9 280X - 32G DDR3 ECC

●
TrÀdvy PermalÀnk
Medlem
Registrerad
Mar 2018

Dag: 15
SprÄk: Scala

Lite mer variation Àn tidigare intcode Àven om det inte skiljer sÄ mycket mellan del 1 och 2. Bfs Ät ena hÄllet och sen bfs tillbaka utan att starta om.

val input = Using.resource(Source.fromFile(filePath.toFile))(_.mkString.split(",")).flatMap(_.toLongOption) val memory = Iterator.from(0).map(_.toLong).zip(input).toMap.withDefaultValue(0L) final case class Droid(program: ProgramState, position: Vec2 = Vec2.Zero, status: Int = -1, step: Int = 0) { private val moves = Map(1 -> Vec2.Up, 2 -> Vec2.Down, 3 -> Vec2.Left, 4 -> Vec2.Right) def neighbours: Iterator[Droid] = for { in <- (1 to 4).iterator (ps, out) = Iterator .unfold(program.copy(ins = LazyList(in)))(_.next.map(s => (s.outs.map(s -> _), s))) .flatten .next() if out != 0 } yield Droid(ps, position + moves(in), out.toInt, step + 1) } def bfs(start: Droid) = LazyList .iterate((Queue(start), Set(start.position))) { case (queue, discovered) => val (ds, rest) = queue.dequeue val neighbours = ds.neighbours.filterNot(d => discovered.contains(d.position)).toSet rest.enqueueAll(neighbours) -> (discovered ++ neighbours.map(_.position)) } .map(_._1) val Droid(ps, pos, _, steps1) = bfs(Droid(ProgramState(memory))).find { _.head.status == 2 }.get.head println(s"part1: $steps1") val Droid(_, _, _, steps2) = bfs(Droid(ps, pos)).takeWhile { _.nonEmpty }.last.head println(s"part2: $steps2")

Samma ProgramState (intcode) som tidigare:

final case class ProgramState( mem: Map[Long, Long], ins: LazyList[Long] = LazyList.empty, outs: List[Long] = Nil, rb: Long = 0, ip: Long = 0) { private def mode(n: Int): Long = (mem(ip) / math.pow(10, n + 1).toInt) % 10 private def read(n: Int): Long = mode(n) match { case 0 => mem(mem(ip + n)) case 1 => mem(ip + n) case 2 => mem(rb + mem(ip + n)) } private def write(n: Int)(value: Long): Map[Long, Long] = mode(n) match { case 0 => mem.updated(mem(ip + n), value) case 2 => mem.updated(rb + mem(ip + n), value) } def next: Option[ProgramState] = mem(ip) % 100 match { case 1 => Some(copy(mem = write(3)(read(1) + read(2)), outs = Nil, ip = ip + 4)) case 2 => Some(copy(mem = write(3)(read(1) * read(2)), outs = Nil, ip = ip + 4)) case 3 => Some(copy(mem = write(1)(ins.head), ins = ins.tail, outs = Nil, ip = ip + 2)) case 4 => Some(copy(outs = read(1) :: Nil, ip = ip + 2)) case 5 => if (read(1) != 0) Some(copy(outs = Nil, ip = read(2))) else Some(copy(outs = Nil, ip = ip + 3)) case 6 => if (read(1) == 0) Some(copy(outs = Nil, ip = read(2))) else Some(copy(outs = Nil, ip = ip + 3)) case 7 => Some(copy(mem = write(3)(if (read(1) < read(2)) 1 else 0), outs = Nil, ip = ip + 4)) case 8 => Some(copy(mem = write(3)(if (read(1) == read(2)) 1 else 0), outs = Nil, ip = ip + 4)) case 9 => Some(copy(outs = Nil, rb = rb + read(1), ip = ip + 2)) case 99 => None } }

Dold text
Dold text
●
TrÀdvy PermalÀnk
Medlem ♄
Plats
NördCentrum
Registrerad
Jun 2011
Skrivet av jclr:

Dag: 15
SprÄk: Scala

Lite mer variation Àn tidigare intcode Àven om det inte skiljer sÄ mycket mellan del 1 och 2. Bfs Ät ena hÄllet och sen bfs tillbaka utan att starta om.

val input = Using.resource(Source.fromFile(filePath.toFile))(_.mkString.split(",")).flatMap(_.toLongOption) val memory = Iterator.from(0).map(_.toLong).zip(input).toMap.withDefaultValue(0L) final case class Droid(program: ProgramState, position: Vec2 = Vec2.Zero, status: Int = -1, step: Int = 0) { private val moves = Map(1 -> Vec2.Up, 2 -> Vec2.Down, 3 -> Vec2.Left, 4 -> Vec2.Right) def neighbours: Iterator[Droid] = for { in <- (1 to 4).iterator (ps, out) = Iterator .unfold(program.copy(ins = LazyList(in)))(_.next.map(s => (s.outs.map(s -> _), s))) .flatten .next() if out != 0 } yield Droid(ps, position + moves(in), out.toInt, step + 1) } def bfs(start: Droid) = LazyList .iterate((Queue(start), Set(start.position))) { case (queue, discovered) => val (ds, rest) = queue.dequeue val neighbours = ds.neighbours.filterNot(d => discovered.contains(d.position)).toSet rest.enqueueAll(neighbours) -> (discovered ++ neighbours.map(_.position)) } .map(_._1) val Droid(ps, pos, _, steps1) = bfs(Droid(ProgramState(memory))).find { _.head.status == 2 }.get.head println(s"part1: $steps1") val Droid(_, _, _, steps2) = bfs(Droid(ps, pos)).takeWhile { _.nonEmpty }.last.head println(s"part2: $steps2")

Samma ProgramState (intcode) som tidigare:

final case class ProgramState( mem: Map[Long, Long], ins: LazyList[Long] = LazyList.empty, outs: List[Long] = Nil, rb: Long = 0, ip: Long = 0) { private def mode(n: Int): Long = (mem(ip) / math.pow(10, n + 1).toInt) % 10 private def read(n: Int): Long = mode(n) match { case 0 => mem(mem(ip + n)) case 1 => mem(ip + n) case 2 => mem(rb + mem(ip + n)) } private def write(n: Int)(value: Long): Map[Long, Long] = mode(n) match { case 0 => mem.updated(mem(ip + n), value) case 2 => mem.updated(rb + mem(ip + n), value) } def next: Option[ProgramState] = mem(ip) % 100 match { case 1 => Some(copy(mem = write(3)(read(1) + read(2)), outs = Nil, ip = ip + 4)) case 2 => Some(copy(mem = write(3)(read(1) * read(2)), outs = Nil, ip = ip + 4)) case 3 => Some(copy(mem = write(1)(ins.head), ins = ins.tail, outs = Nil, ip = ip + 2)) case 4 => Some(copy(outs = read(1) :: Nil, ip = ip + 2)) case 5 => if (read(1) != 0) Some(copy(outs = Nil, ip = read(2))) else Some(copy(outs = Nil, ip = ip + 3)) case 6 => if (read(1) == 0) Some(copy(outs = Nil, ip = read(2))) else Some(copy(outs = Nil, ip = ip + 3)) case 7 => Some(copy(mem = write(3)(if (read(1) < read(2)) 1 else 0), outs = Nil, ip = ip + 4)) case 8 => Some(copy(mem = write(3)(if (read(1) == read(2)) 1 else 0), outs = Nil, ip = ip + 4)) case 9 => Some(copy(outs = Nil, rb = rb + read(1), ip = ip + 2)) case 99 => None } }

Dold text
Dold text

Smart att lÄta bfs returnera listan av de ordnade trÀffarna och bara köra find/last pÄ den! Just avsaknaden av det som gjorde att min egen kod kÀndes lite obehaglig. StjÀl den idén!

{-# LANGUAGE LambdaCase #-} module Day15 (part1, part2) where import qualified Data.Set as Set import Data.Functor import Data.Maybe import Data.List import qualified Data.Sequence as Seq import Vec import Intcode type PathLength = Int type Tile = Int part1 :: IO Int part1 = fmap (fst . findO2System . parseIntcode) readInput part2 :: IO Int part2 = readInput <&> \s -> let pgm = parseIntcode s (_, o2Cont) = findO2System pgm (_, l, _) = last (bfs o2Cont) in l findO2System :: Mem -> (PathLength, Continuation) findO2System pgm = let (_, startCont) = stepIntcode pgm (_, l, c) = fromJust (find (\(t, _, _) -> t == 2) (bfs (fromJust startCont))) in (l, c) bfs :: Continuation -> [(Tile, PathLength, Continuation)] bfs c = bfs' Set.empty (0, Vec2 0 0 :: Vec2 Int, 0, c) Seq.empty where bfs' visiteds (tile, p, l, Cont cont) nexts = let dirs = filter (not . flip Set.member visiteds . snd) $ zip [1, 2, 3, 4] (map (p +) [Vec2 0 1, Vec2 0 (-1), Vec2 (-1) 0, Vec2 1 0]) l' = l + 1 neighbours = filter (\(t, _, _, _) -> t /= 0) $ map (\(dir, p') -> let ((_, tile'), cont') = cont dir in (head tile', p', l', fromJust cont') ) dirs visiteds' = Set.union (Set.fromList (p : map (\(_, p', _, _) -> p') neighbours)) visiteds in (tile, l, Cont cont) : case Seq.viewl (nexts Seq.>< Seq.fromList neighbours) of Seq.EmptyL -> [] next Seq.:< nexts' -> bfs' visiteds' next nexts' readInput :: IO String readInput = readFile "inputs/day-15"

Dold text

Gibb: Win10 - Ryzen 5 3600 - RX 580 - 16G 3000MHz DDR4
Server: Arch - 2 * Xeon X5570 - R9 280X - 32G DDR3 ECC

●
TrÀdvy PermalÀnk
Medlem ♄
Plats
Stockholm
Registrerad
Mar 2006

Mycket kul problem idag

●
TrÀdvy PermalÀnk
Datavetare ♄ ★
Plats
Stockholm
Registrerad
Jun 2011

Rust - dag 16

Tror jag hittade en bug i kompilator eller kanske troligare i standardbiblioteket, ska undersöka mer noggrant och dra ivÀg en buggrapport om sÄ Àr fallet. MÄste bara dubbelkolla att jag fattat dokumentationen rÀtt.

Har en lösning pÄ del 2 med mutable iteratorer som reverseras, blir rÀtt svar frÄn start till fas #1 och nÀstan rÀtt svar i fas #2. Allt Àr rÀtt utom de sista ~600 tecknen som verkar lite blockmÀssigt omkastade (sÄ inte totalt skrÀp). Satt rÀtt lÀnge med det, Àr ju fortfarande rÀtt ny pÄ Rust sÄ var lÀnge övertygad om att jag missförstÄtt nÄgot.

En observation bÄde hÀr och i ett par tidigare fall som jag skrivit om frÄn mer C-stil (imperativ) till att anvÀnda pipelines: ni som kör sprÄk dÀr immutable Àr normen, vilken prestandaförsÀmring Àr rimligt att förvÀnta sig över en imperativ lösning med mutable-state? Att den senare rimligen Àr mer effekt borde ju vara fallet givet att den modeller matchar moderna CPUers cache-design vÀldigt bra.

Har sett 2-10 gÄnger bÀttre prestanda i Rust om man kör med C-stil (Àr bara dÄ Rust nÄr C/C++ prestanda) i problem hÀr i Advent of Code.

Oavsett lÀr den variant som lÀr komma pÄ frÄga i Rust om/nÀr det börjas anvÀnda som OS-kernel sprÄk vara rÀtt C-lik. Finns ju ÀndÄ massor med fördelar i Rust över C och C++!!!

const FFT_PATTERN: [i32; 4] = [0, 1, 0, -1]; #[derive(Clone, Copy, Debug)] struct FftPattern { period: usize, rep: usize, idx: usize, } fn fft_pattern(period: usize) -> FftPattern { FftPattern { period: period, rep: 0, idx: 0, } } impl Iterator for FftPattern { type Item = i32; fn next(&mut self) -> Option<i32> { if self.rep == 0 && self.idx == FFT_PATTERN.len() { None } else { let ret = FFT_PATTERN[self.idx]; self.rep += 1; if self.rep == self.period { self.rep = 0; self.idx += 1; } Some(ret) } } } fn normal_phase(input: &Vec<i32>) -> Vec<i32> { (1..=input.len()) .map(|idx| { input .iter() .zip(fft_pattern(idx).cycle().skip(1)) .map(|(&val, pat)| val * pat) .sum() }) .map(|n: i32| n.abs() % 10) .collect() } fn rev_phase(input: &Vec<i32>) -> Vec<i32> { input .iter() .rev() .scan(0, |tot, &n| { *tot += n; Some((*tot).abs() % 10) }) .collect::<Vec<_>>() .into_iter() .rev() .collect::<Vec<_>>() } fn fft(signal: &Vec<i32>, phase: &dyn Fn(&Vec<i32>) -> Vec<i32>) -> String { (0..100) .fold(signal.clone(), |signal, _| phase(&signal)) .iter() .take(8) .map(|digit| digit.to_string()) .join("") } impl Solution for State { fn part1(&self) -> String { fft(&self.signal, &normal_phase) } fn part2(&self) -> String { let offset = self.signal .iter() .take(7) .join("") .parse::<usize>() .unwrap(); let real_signal = self.signal .clone() .into_iter() .cycle() .take(10000 * self.signal.len()) .skip(offset) .collect::<Vec<_>>(); fft(&real_signal, &rev_phase) } }

Den hÀr varianten Àr lÄngsammare men blir i alla fall rÀtt svar :)

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

●
TrÀdvy PermalÀnk
Medlem ♄
Registrerad
Aug 2015
Skrivet av Yoshman:

Tror jag hittade en bug i kompilator eller kanske troligare i standardbiblioteket, ska undersöka mer noggrant och dra ivÀg en buggrapport om sÄ Àr fallet. MÄste bara dubbelkolla att jag fattat dokumentationen rÀtt.

Har en lösning pÄ del 2 med mutable iteratorer som reverseras, blir rÀtt svar frÄn start till fas #1 och nÀstan rÀtt svar i fas #2. Allt Àr rÀtt utom de sista ~600 tecknen som verkar lite blockmÀssigt omkastade (sÄ inte totalt skrÀp). Satt rÀtt lÀnge med det, Àr ju fortfarande rÀtt ny pÄ Rust sÄ var lÀnge övertygad om att jag missförstÄtt nÄgot.

En observation bÄde hÀr och i ett par tidigare fall som jag skrivit om frÄn mer C-stil (imperativ) till att anvÀnda pipelines: ni som kör sprÄk dÀr immutable Àr normen, vilken prestandaförsÀmring Àr rimligt att förvÀnta sig över en imperativ lösning med mutable-state? Att den senare rimligen Àr mer effekt borde ju vara fallet givet att den modeller matchar moderna CPUers cache-design vÀldigt bra.

Har sett 2-10 gÄnger bÀttre prestanda i Rust om man kör med C-stil (Àr bara dÄ Rust nÄr C/C++ prestanda) i problem hÀr i Advent of Code.

Oavsett lÀr den variant som lÀr komma pÄ frÄga i Rust om/nÀr det börjas anvÀnda som OS-kernel sprÄk vara rÀtt C-lik. Finns ju ÀndÄ massor med fördelar i Rust över C och C++!!!

const FFT_PATTERN: [i32; 4] = [0, 1, 0, -1]; #[derive(Clone, Copy, Debug)] struct FftPattern { period: usize, rep: usize, idx: usize, } fn fft_pattern(period: usize) -> FftPattern { FftPattern { period: period, rep: 0, idx: 0, } } impl Iterator for FftPattern { type Item = i32; fn next(&mut self) -> Option<i32> { if self.rep == 0 && self.idx == FFT_PATTERN.len() { None } else { let ret = FFT_PATTERN[self.idx]; self.rep += 1; if self.rep == self.period { self.rep = 0; self.idx += 1; } Some(ret) } } } fn normal_phase(input: &Vec<i32>) -> Vec<i32> { (1..=input.len()) .map(|idx| { input .iter() .zip(fft_pattern(idx).cycle().skip(1)) .map(|(&val, pat)| val * pat) .sum() }) .map(|n: i32| n.abs() % 10) .collect() } fn rev_phase(input: &Vec<i32>) -> Vec<i32> { input .iter() .rev() .scan(0, |tot, &n| { *tot += n; Some((*tot).abs() % 10) }) .collect::<Vec<_>>() .into_iter() .rev() .collect::<Vec<_>>() } fn fft(signal: &Vec<i32>, phase: &dyn Fn(&Vec<i32>) -> Vec<i32>) -> String { (0..100) .fold(signal.clone(), |signal, _| phase(&signal)) .iter() .take(8) .map(|digit| digit.to_string()) .join("") } impl Solution for State { fn part1(&self) -> String { fft(&self.signal, &normal_phase) } fn part2(&self) -> String { let offset = self.signal .iter() .take(7) .join("") .parse::<usize>() .unwrap(); let real_signal = self.signal .clone() .into_iter() .cycle() .take(10000 * self.signal.len()) .skip(offset) .collect::<Vec<_>>(); fft(&real_signal, &rev_phase) } }

Den hÀr varianten Àr lÄngsammare men blir i alla fall rÀtt svar :)

Hej!
Vad behöver jag mer för kod för att testa din lösning? Saknar main tex, dessutom sÄ fÄr jag följande meddelanden:

error[E0405]: cannot find trait `Solution` in this scope
--> src/main.rs:76:6
|
76 | impl Solution for State {
| ^^^^^^^^ not found in this scope

error[E0412]: cannot find type `State` in this scope
--> src/main.rs:76:19
|
76 | impl Solution for State {
| ^^^^^ not found in this scope

●
TrÀdvy PermalÀnk
Medlem ♄ ★
Plats
Skaune
Registrerad
Okt 2002

Fann att tiden tröt till lite och att Powershell kanske inte Àr helt rÀtt sprÄk för ÀndamÄlet.
Har funderat ett tag pÄ att lÀra mig nÄgot annat sprÄk och jag tÀnkte att jag ska ge Go ett försök.

Har nu pilla nÄgra timmar med Go och kommit fram till att jag Àr ordentligt fÀrgad av Powershell. MÄste försöka slÀppa det lite!

Testade runt lite med dag 1 med hjÀlp av en annan som skrivit i Go. Verkade helt ok enkelt sÄ jag tÀnkte att jag provar att hoppa pÄ dag 2 helt sjÀlv!
Dock Àr detta hittills endast dag 2 del 1 (och inte snyggt om jag jÀmför med hur andra skriver Go )

package main import ( "fmt" ) func main() { x2 := []int{1, 12, 2, 3, 1, 1, 2, 3, 1, 3, 4, 3, 1, 5, 0, 3, 2, 6, 1, 19, 2, 19, 9, 23, 1, 23, 5, 27, 2, 6, 27, 31, 1, 31, 5, 35, 1, 35, 5, 39, 2, 39, 6, 43, 2, 43, 10, 47, 1, 47, 6, 51, 1, 51, 6, 55, 2, 55, 6, 59, 1, 10, 59, 63, 1, 5, 63, 67, 2, 10, 67, 71, 1, 6, 71, 75, 1, 5, 75, 79, 1, 10, 79, 83, 2, 83, 10, 87, 1, 87, 9, 91, 1, 91, 10, 95, 2, 6, 95, 99, 1, 5, 99, 103, 1, 103, 13, 107, 1, 107, 10, 111, 2, 9, 111, 115, 1, 115, 6, 119, 2, 13, 119, 123, 1, 123, 6, 127, 1, 5, 127, 131, 2, 6, 131, 135, 2, 6, 135, 139, 1, 139, 5, 143, 1, 143, 10, 147, 1, 147, 2, 151, 1, 151, 13, 0, 99, 2, 0, 14, 0} t := int(len(x2)) / 4 l := 0 //pos0 := x2[0] for j := 0; j < t; j++ { inp1 := l + 1 inp2 := l + 2 pos3 := l + 3 if x2[l] == 1 { pos1 := x2[inp1] tar1 := x2[pos1] pos2 := x2[inp2] tar2 := x2[pos2] wb := tar1 + tar2 tar3 := x2[pos3] x2[tar3] = wb } else if x2[l] == 2 { pos1 := x2[inp1] tar1 := x2[pos1] pos2 := x2[inp2] tar2 := x2[pos2] wb := tar1 * tar2 tar3 := x2[pos3] x2[tar3] = wb } else if x2[l] == 99 { fmt.Println("-----------> ", x2[0]) } else { fmt.Println("WTF!") } l++ l++ l++ l++ } }

GoLang Day2 Part1

Ett problem Àr t ex att jag inte Àn helt fattat hur fan man lÀser in en fil som input

🟱 Main: Ryzen7 2700X | Strix x470-I | 32GB | GTX1070 | Samsung C49RG9
đŸ”” unRaid: Ryzen5 2600 | B450M DS3H | 32GB
🟠 Tfn: OnePlus 6T Thunder Purple

-:| @ eller citera för svar |:-

●
TrÀdvy PermalÀnk
Datavetare ♄ ★
Plats
Stockholm
Registrerad
Jun 2011
Skrivet av SAFA:

Hej!
Vad behöver jag mer för kod för att testa din lösning? Saknar main tex, dessutom sÄ fÄr jag följande meddelanden:

error[E0405]: cannot find trait `Solution` in this scope
--> src/main.rs:76:6
|
76 | impl Solution for State {
| ^^^^^^^^ not found in this scope

error[E0412]: cannot find type `State` in this scope
--> src/main.rs:76:19
|
76 | impl Solution for State {
| ^^^^^ not found in this scope

Har bara postat delarna som löser aktuellt problem, dessa Àr sedan instoppade i ett Rust-program som innehÄller alla lösningar jag gjort sÄ hÀr lÄngt (vilket verkar blivit till dag 17, sedan tog julstressen prioritet )

Allt finns pÄ min github, inklusive dag 17. För dag 17 har mÄnga löst ut A, B och C manuellt, min lösning rÀknar ut det hela sÄ ska fungera för alla input (förvÄnad att programmet Àr sÄ pass snabbt givet misshandlade av regex...).

Om du vill testa prestanda ska du inte följa mina instruktioner pÄ github, de Àr för att köra pÄ enklast möjliga sÀtt men blir debug-byggen. Gör detta för optimerade byggen

$ git clone https://github.com/kjn-void/advent-of-code-2019.git $ cd advent-of-code-2019 $ cargo build --release $ ./target/release/aoc2019 17

Detta bygger alla lösningar och kör sedan dag 17 med min input (byt ut src/day17/input.txt mot egen input om sÄ önskas).

Skrivet av GreyWilk:

Fann att tiden tröt till lite och att Powershell kanske inte Àr helt rÀtt sprÄk för ÀndamÄlet.
Har funderat ett tag pÄ att lÀra mig nÄgot annat sprÄk och jag tÀnkte att jag ska ge Go ett försök.

Har nu pilla nÄgra timmar med Go och kommit fram till att jag Àr ordentligt fÀrgad av Powershell. MÄste försöka slÀppa det lite!

Testade runt lite med dag 1 med hjÀlp av en annan som skrivit i Go. Verkade helt ok enkelt sÄ jag tÀnkte att jag provar att hoppa pÄ dag 2 helt sjÀlv!
Dock Àr detta hittills endast dag 2 del 1 (och inte snyggt om jag jÀmför med hur andra skriver Go )

package main import ( "fmt" ) func main() { x2 := []int{1, 12, 2, 3, 1, 1, 2, 3, 1, 3, 4, 3, 1, 5, 0, 3, 2, 6, 1, 19, 2, 19, 9, 23, 1, 23, 5, 27, 2, 6, 27, 31, 1, 31, 5, 35, 1, 35, 5, 39, 2, 39, 6, 43, 2, 43, 10, 47, 1, 47, 6, 51, 1, 51, 6, 55, 2, 55, 6, 59, 1, 10, 59, 63, 1, 5, 63, 67, 2, 10, 67, 71, 1, 6, 71, 75, 1, 5, 75, 79, 1, 10, 79, 83, 2, 83, 10, 87, 1, 87, 9, 91, 1, 91, 10, 95, 2, 6, 95, 99, 1, 5, 99, 103, 1, 103, 13, 107, 1, 107, 10, 111, 2, 9, 111, 115, 1, 115, 6, 119, 2, 13, 119, 123, 1, 123, 6, 127, 1, 5, 127, 131, 2, 6, 131, 135, 2, 6, 135, 139, 1, 139, 5, 143, 1, 143, 10, 147, 1, 147, 2, 151, 1, 151, 13, 0, 99, 2, 0, 14, 0} t := int(len(x2)) / 4 l := 0 //pos0 := x2[0] for j := 0; j < t; j++ { inp1 := l + 1 inp2 := l + 2 pos3 := l + 3 if x2[l] == 1 { pos1 := x2[inp1] tar1 := x2[pos1] pos2 := x2[inp2] tar2 := x2[pos2] wb := tar1 + tar2 tar3 := x2[pos3] x2[tar3] = wb } else if x2[l] == 2 { pos1 := x2[inp1] tar1 := x2[pos1] pos2 := x2[inp2] tar2 := x2[pos2] wb := tar1 * tar2 tar3 := x2[pos3] x2[tar3] = wb } else if x2[l] == 99 { fmt.Println("-----------> ", x2[0]) } else { fmt.Println("WTF!") } l++ l++ l++ l++ } }

GoLang Day2 Part1

Ett problem Àr t ex att jag inte Àn helt fattat hur fan man lÀser in en fil som input

HÀr Àr ett exempel pÄ hur du kan lÀsa in Intcode frÄn fil till en array-of-int (nÄgot du senare kommer behöva Àndra till int64)

import ( "io/ioutil" "strconv" "strings" ) type Program []int func loadProgram(fn string) Program { fileContent, err := ioutil.ReadFile(fn) if err != nil { panic(err) } prog := Program{} for _, strVal := range strings.Split(string(fileContent), ",") { ic, err := strconv.Atoi(strings.TrimSpace(strVal)) if err != nil { panic(err) } prog = append(prog, ic) } return prog }

LĂ€sa in en Intcode som text i Go

Edit: lade till de "imports" som krÀvs för "lÀsa in filen i Go" koden.

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

●
TrÀdvy PermalÀnk
Datavetare ♄ ★
Plats
Stockholm
Registrerad
Jun 2011

Trista att tiden, som vanligt, börja tryta allt för mycket nÀr man kommer riktigt nÀra jul.

Var dock inte helt nöjd med att slÀppt taget tidigare Àn förra Äret, dÄ körde jag fram till dag 18 Àven om jag tidigare Àn i Är börja halka efter (gjorde dag 16-18 efter jul förra Äret).

SÄ en liten förbÀttring i Är, har nu tagit mig till dag 18. Det innan jul

Dag 18 var faktiskt rÀtt kul, rÀtt lÄngt ifrÄn vad jag numera jobbar med och första lösningen var allt annat Àn optimal dÄ jag missade en optimering som borde varit sjÀlvklart efter Held Harp trÄden...

"Every subpath of a path of minimum distance is itself of minimum distance."

Min lösning anvÀnder sig av best-first-search (best med avseende pÄ minimalt antal steg) genom labyrinten för att plocka nycklar. Kikat pÄ andra lösning, mÄnga verkar anvÀnda sig av breadth-first-search vilket fungerar pÄ exemplen och uppenbarligen mÄnga inputs (dock inte min, blir nÄgra snÀpp för lÄng vÀg dÄ).

Utan optimeringen ovan tog det mÄnga minuter att lösa varje del, detta dÄ man expanderar alla permutationer av att ta t.ex. nyckelserie "a, b, c" i stÀllet för att bara expandera den bÀsta "a, b, c" stÄende i t.ex. "c".

Lösningen finns hÀr. Slutversionen fixar att lösa bÄde del 1 och 2 pÄ endast 45 ms (i7-8559U).

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

●
TrÀdvy PermalÀnk
Medlem ♄
Registrerad
Aug 2015
Skrivet av Yoshman:

Har bara postat delarna som löser aktuellt problem, dessa Àr sedan instoppade i ett Rust-program som innehÄller alla lösningar jag gjort sÄ hÀr lÄngt (vilket verkar blivit till dag 17, sedan tog julstressen prioritet )

Allt finns pÄ min github, inklusive dag 17. För dag 17 har mÄnga löst ut A, B och C manuellt, min lösning rÀknar ut det hela sÄ ska fungera för alla input (förvÄnad att programmet Àr sÄ pass snabbt givet misshandlade av regex...).

Om du vill testa prestanda ska du inte följa mina instruktioner pÄ github, de Àr för att köra pÄ enklast möjliga sÀtt men blir debug-byggen. Gör detta för optimerade byggen

$ git clone https://github.com/kjn-void/advent-of-code-2019.git $ cd advent-of-code-2019 $ cargo build --release $ ./target/release/aoc2019 17

Detta bygger alla lösningar och kör sedan dag 17 med min input (byt ut src/day17/input.txt mot egen input om sÄ önskas).

Funkar galant!
InsÄg jag missat en optimering nÀr dag 16 tog ca 3 timmar för att fÄ rÀtt svar.
Rust verkar hyggligt effektivt, har jÀmfört lite pÄ dag 15, 16, 17. Kört med samma input för att det ska gÄ att jÀmföra.

Dag 15:
Rust user+sys: 79 + 39 ms (bÄde del 1 o 2)
C del1: user+sys: 18 + 22 ms (tar en del tid att rita labyrinten i bÄda fallen)
C del2: user+sys: 15 + 21 ms

Dag 16:
Rust user+sys: 263 + 4 ms
C: user+sys: 239 + 4 ms

Dag17:
Rust user+sys: 42 + 3ms
C user+sys: 3 + 2 ms

●
TrÀdvy PermalÀnk
Datavetare ♄ ★
Plats
Stockholm
Registrerad
Jun 2011
Skrivet av SAFA:

Funkar galant!
InsÄg jag missat en optimering nÀr dag 16 tog ca 3 timmar för att fÄ rÀtt svar.
Rust verkar hyggligt effektivt, har jÀmfört lite pÄ dag 15, 16, 17. Kört med samma input för att det ska gÄ att jÀmföra.

Dag 15:
Rust user+sys: 79 + 39 ms (bÄde del 1 o 2)
C del1: user+sys: 18 + 22 ms (tar en del tid att rita labyrinten i bÄda fallen)
C del2: user+sys: 15 + 21 ms

Dag 16:
Rust user+sys: 263 + 4 ms
C: user+sys: 239 + 4 ms

Dag17:
Rust user+sys: 42 + 3ms
C user+sys: 3 + 2 ms

GÄr ju att skriva vÀldigt 1:1 mot C i Rust, i det lÀget Àr det typiskt inom felmarginalen samma prestanda.

Kör du pÄ din 3900X och pÄ Linux? KÀnns som det Àr lÄg prestanda för dag 16, men rÀtt samma för övriga stÀlld mot min 3900X (som kör Ubuntu server 18.04). AnvÀnder senaste stabila Rust-kompilatorn (v1.40.0), den man fÄr frÄn "rustup" om man anvÀnder "stable" taggen.

Day

3900X ms (user+sys)

9900K (user+sys)

15

76+27

68+5

16

147+4

139+4

17

39+4

24+5

Edit: tror inte det Àr meningsfullt att försöka mÀta "sys" i dessa fall. FÄr allt frÄn 0 till 13 ms dag 17 pÄ 3900X datorn. Nog bÀttre att mÀta "real" dÄ det Àr sÄ lÄng tid det faktiskt tar, det vÀrdet stÀmmer rÀtt exakt med det mitt Rust-program sjÀlv mÀter.

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

●
TrÀdvy PermalÀnk
Medlem ♄
Registrerad
Aug 2015
Skrivet av Yoshman:

GÄr ju att skriva vÀldigt 1:1 mot C i Rust, i det lÀget Àr det typiskt inom felmarginalen samma prestanda.

Kör du pÄ din 3900X och pÄ Linux? KÀnns som det Àr lÄg prestanda för dag 16, men rÀtt samma för övriga stÀlld mot min 3900X (som kör Ubuntu server 18.04). AnvÀnder senaste stabila Rust-kompilatorn (v1.40.0), den man fÄr frÄn "rustup" om man anvÀnder "stable" taggen.

Day

3900X ms (user+sys)

9900K (user+sys)

15

76+27

68+5

16

147+4

139+4

17

39+4

24+5

Edit: tror inte det Àr meningsfullt att försöka mÀta "sys" i dessa fall. FÄr allt frÄn 0 till 13 ms dag 17 pÄ 3900X datorn. Nog bÀttre att mÀta "real" dÄ det Àr sÄ lÄng tid det faktiskt tar, det vÀrdet stÀmmer rÀtt exakt med det mitt Rust-program sjÀlv mÀter.

Jo, det Àr pÄ min 3900x, men det gick full last i bakgrunden pÄ alla trÄdar sÄ programmet fÄr dela pÄ en kÀrna, sen Àr boost avstÀngd för att den ska vara lite tystare. SÄ det lÀr ju pÄverka cachen en del ocksÄ.

Real Àr ju bra om man inte kör annat samtidigt eller har lite utskrifter kvar.

En sak man skulle vilja ha i schemalÀggaren Àr att kunna sÀga att en process ska ha exklusiv tillgÄng till en kÀrna sÄ det inte lÀggs andra trÄdar pÄ den.

●
TrÀdvy PermalÀnk
Medlem ♄ ★
Plats
Uppsala
Registrerad
Dec 2008

TrÄden tappade lite fart runt lucia, nÀr uppgifterna blev lite knepigare och tiden tog slut för de flesta. Nu, Àntligen, har jag löst alla uppgifter i kalendern. Just nu kÀnns det mest som att det Àr skönt att det Àr över och att jag kan Äterknyta bekantskapen med Arthur Morgan i Red Dead Redemption 2.

Det har varit kul, men stundtals ganska frustrerande att leta buggar. Det Àr hyfsat stora problem och ganska oförlÄtande nÀr man letar buggar. Om gör man nÄgot slarvfel, till exempel rÄkar spara koordinaterna till sin syrelÀcka som x,x istÀllet för x,y, sÄ spelar det ingen roll hur bra ens bredden-först-sökning fungerar. Man fÄr obönhörligt fel svar och har ingen aning om varför. Japp, nu har jag rÀknat, det Àr 212 steg till 'O'et i labyrinten, varför sÀger webbsidan att det Àr fel svar?

Man skall Àven lÀsa uppgiften noga och bara göra det som stÄr i uppgiften. StÄr det att man skall rÀkna ut det minsta antal steg man mÄste ta för att hÀmta alla nycklar (smÄ bokstÀver) i labyrinten skall man inte rÀkna ut minsta antalet steg för att besöka bÄde dörrar (stora bokstÀver) och nycklar (smÄ bokstÀver). Samma sak hÀr, programmet rÀknar rÀtt, men rÀknar man inte ut det man borde rÀknat ut fÄr man ocksÄ fel svar.

Uppgift 22.2 var omöjlig. Efter mycket tankemöda gav jag upp och kollade pÄ reddit, men inte ens nÀr jag lÀste den Tutorial som nÄgon vÀnlig sjÀl skrivit förstod jag matematiken bakom.

Jag tÀnkte avsluta med lösningen till julaftons uppgift. Det var en förenkling a Conways Game of Life. 30 rader Python dÀr jag missbrukar list comprehensions och kör lite fultrix fixar bÄde del 1 och del 2. Se det mest som kuriosa, inte en kodningsstil jag rekommenderar pÄ jobbet.

from itertools import chain,product initial = "........#..#..#.#.#....##" neighbors = [[] for _ in range(25)] for x,y in product(range(4),range(5)): for i,n in [( x * 5 + y, (x + 1) * 5 + y), (y * 5 + x, y * 5 + x + 1), ((x + 1) * 5 + y, x * 5 + y), (y * 5 + x + 1, y * 5 + x )]: neighbors[i].append(n) state = tuple([0 + (c == '#') for c in initial]) s = set() while state not in s: s.add(state) state = tuple([[0,1,1-state[i],0,0][sum([state[o] for o in neighbors[i]])] for i in range(25)]) print("Part1:", sum([v << i for i,v in enumerate(state)])) neighbors[12] = [] # Always zero for x in range(5): # Add more neighbors for i,n in [(7, 25 + x), (11, 25 + x * 5), (13, 25 + 4 + x * 5), (17, 25 + 20 + x), (x, -25 + 7), (x * 5, -25 + 11), (x * 5 + 4, -25 + 13), (x + 20, -25 + 17)]: neighbors[i].append(n) state, e = [0 + (c == '#') for c in initial], [0] * 25 for _ in range(200): state = list(chain(e, state, e)) l = len(state) state = chain(*[[[0,1,1-state[d + i],0,0,0,0,0,0][sum([state[d + o] for o in neighbors[i] if d + o >= 0 and d + o < l])] for i in range(25)] for d in range(0, l, 25)]) print("Part2:", sum(state))

Dold text
●
TrÀdvy PermalÀnk
Medlem ♄
Registrerad
Aug 2015
Skrivet av Ingetledigtnamn:

TrÄden tappade lite fart runt lucia, nÀr uppgifterna blev lite knepigare och tiden tog slut för de flesta. Nu, Àntligen, har jag löst alla uppgifter i kalendern. Just nu kÀnns det mest som att det Àr skönt att det Àr över och att jag kan Äterknyta bekantskapen med Arthur Morgan i Red Dead Redemption 2.

Det har varit kul, men stundtals ganska frustrerande att leta buggar. Det Àr hyfsat stora problem och ganska oförlÄtande nÀr man letar buggar. Om gör man nÄgot slarvfel, till exempel rÄkar spara koordinaterna till sin syrelÀcka som x,x istÀllet för x,y, sÄ spelar det ingen roll hur bra ens bredden-först-sökning fungerar. Man fÄr obönhörligt fel svar och har ingen aning om varför. Japp, nu har jag rÀknat, det Àr 212 steg till 'O'et i labyrinten, varför sÀger webbsidan att det Àr fel svar?

Jo, satt sjÀlv alldeles för lÀnge och debuggade dag23. Jag hade ÄteranvÀnt en tidigare kod för att swappa int-koden vid byte av VM men missat att den fortfarande var pÄ 32 bitar och inte uppdaterad till 64.

Skrivet av Ingetledigtnamn:

Man skall Àven lÀsa uppgiften noga och bara göra det som stÄr i uppgiften. StÄr det att man skall rÀkna ut det minsta antal steg man mÄste ta för att hÀmta alla nycklar (smÄ bokstÀver) i labyrinten skall man inte rÀkna ut minsta antalet steg för att besöka bÄde dörrar (stora bokstÀver) och nycklar (smÄ bokstÀver). Samma sak hÀr, programmet rÀknar rÀtt, men rÀknar man inte ut det man borde rÀknat ut fÄr man ocksÄ fel svar.

Uppgift 22.2 var omöjlig. Efter mycket tankemöda gav jag upp och kollade pÄ reddit, men inte ens nÀr jag lÀste den Tutorial som nÄgon vÀnlig sjÀl skrivit förstod jag matematiken bakom.

Jag tÀnkte avsluta med lösningen till julaftons uppgift. Det var en förenkling a Conways Game of Life. 30 rader Python dÀr jag missbrukar list comprehensions och kör lite fultrix fixar bÄde del 1 och del 2. Se det mest som kuriosa, inte en kodningsstil jag rekommenderar pÄ jobbet.

from itertools import chain,product initial = "........#..#..#.#.#....##" neighbors = [[] for _ in range(25)] for x,y in product(range(4),range(5)): for i,n in [( x * 5 + y, (x + 1) * 5 + y), (y * 5 + x, y * 5 + x + 1), ((x + 1) * 5 + y, x * 5 + y), (y * 5 + x + 1, y * 5 + x )]: neighbors[i].append(n) state = tuple([0 + (c == '#') for c in initial]) s = set() while state not in s: s.add(state) state = tuple([[0,1,1-state[i],0,0][sum([state[o] for o in neighbors[i]])] for i in range(25)]) print("Part1:", sum([v << i for i,v in enumerate(state)])) neighbors[12] = [] # Always zero for x in range(5): # Add more neighbors for i,n in [(7, 25 + x), (11, 25 + x * 5), (13, 25 + 4 + x * 5), (17, 25 + 20 + x), (x, -25 + 7), (x * 5, -25 + 11), (x * 5 + 4, -25 + 13), (x + 20, -25 + 17)]: neighbors[i].append(n) state, e = [0 + (c == '#') for c in initial], [0] * 25 for _ in range(200): state = list(chain(e, state, e)) l = len(state) state = chain(*[[[0,1,1-state[d + i],0,0,0,0,0,0][sum([state[d + o] for o in neighbors[i] if d + o >= 0 and d + o < l])] for i in range(25)] for d in range(0, l, 25)]) print("Part2:", sum(state))

Dold text

Jo 22:2 var svÄr, fick ocksÄ kolla pÄ reddit.
Grunden för lösningen Àr att ett korts position C vid blandning förflyttas enligt:
Cn+1 = (K * Cn + B) modulo antalet kort.
B fÄr man fram genom att se var kort 0 hamnar efter en blandning.
K fÄr man fram genom att se skillnaden mellan var kort 1 och 0 hamnar efter en blandning.
Sen spelar det ingen roll hur mÄnga gÄnger man blandar leken - man fÄr bara olika vÀrden pÄ B och K. Blandar man leken "baklÀnges" sÄ ger det andra vÀrden pÄ B, K men fortfarande samma formel.

Skrev man i del 1 blandningen som att man skyfflar runt i en vektor med "kort" sÄ inses att man kan inte göra samma för del 2. DÀremot kan man hÄlla koll pÄ hur ett kort förflyttas.

NÀsta steg Àr att ta fram B och K för tvÄ blandningar, sen anvÀnder man dessa för att ta fram nya B och K för 4 blandningar, sen 8 osv... PÄ sÄ sÀtt kan man fÄ fram godtyckligt mÄnga blandningar genom att kombinera dessa.

●
TrÀdvy PermalÀnk
Datavetare ♄ ★
Plats
Stockholm
Registrerad
Jun 2011

Lyckades ocksÄ beta av alla problem detta Är. Advent of code Àr faktiskt ett lysande sÀtt att sÀtta sig i ett nytt sprÄk pÄ ett sÀtt dÀr man har nÄgot konkret att lösa och dÀr slutpunkten för varje delmoment inte Àr allt för avlÀgset. Enda jag hoppade i Rust var problem 22 del 2, orkade inte leta fram ett lÀmpligt big-num bibliotek (och fick overflow error nÀr jag försökte köra med i128).

Allt finns pÄ gibhub.

Efter att kikat i Reddit-trÄden skulle sÀga att sÀttet de flesta löste dag 21 (Springdroid adventure) och dag 25 (Cryostasis) kÀnns lite "fuskigt" dÄ de skrev skriptet för hand resp. spelade igenom textÀventyret som manuellt. Löste bÄda programmatisk.

Dag 22 gick att "brute-forace" genom följande insikt: "T" registret behövs egentligen inte, Àr ju bara vÀrdet pÄ "J" som spelar roll. Inget av register A-I behöver lÀsas mer Àn en gÄng. Med dessa villkor var det ju bara att generera varje möjligt program (som har en logisk skillnad mot tidigare program) samt cacha fallen som gÄtt fel och verifiera varje generarat skript mot (dÄ intcode datorn inte Àr supersnabb). Min lösning gick dÄ pÄ 190 ms pÄ en i7-8559U.

Dag 25 delade jag in i tre delar. Första dÀr alla icke-dödliga föremÄl letades upp samt noterade var "Security Checkpoint" lÄg, sökte med DFS sÄ nÀr det hela var avklarat stod roboten vid start igen. Del tvÄ var att gÄ till "Security Checkpoint". Del tre var helt enkelt att testa alla tÀnkbara kombinationer av föremÄl (totalt 256 st dÄ det fanns 8 föremÄl). Gick dÄ att lösa pÄ 138 ms.

Har ju undersökt Rust mycket med frÄgestÀllningen: verkar det snabbt nog redan nu för att anvÀnda i OS-utveckling? Svaret Àr verkar vara: ja, förutsatt att man skriver relativt C-likt (finns ju ÀndÄ massor med fördelar kring sÀkerhet i Rust)!

Körde inte med nĂ„gon listkomprehension för dag 24 (Planet of Discord), utan en bit-array för varje nivĂ„. Blev inte nĂ€rheten lika superkompakt lösning som @Ingetledigtnamn klĂ€mde till med i Python. ÄndĂ„ nöjd, gick att följa problembeskrivningen vĂ€ldigt 1:1 m.h.a. Rust "pattern-matching" och de ~120 rader lösningen tog var trots allt ganska precis 100x snabbare (tog 10 ms) jĂ€mfört med Python3 lösningen pĂ„ min dator (anvĂ€nder sjĂ€lv Python en hel del, men det Ă€r knappast rĂ€tt val i prestandakritiska fall...).

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

●
TrÀdvy PermalÀnk
Medlem ♄
Registrerad
Aug 2015
Skrivet av Yoshman:

Lyckades ocksÄ beta av alla problem detta Är. Advent of code Àr faktiskt ett lysande sÀtt att sÀtta sig i ett nytt sprÄk pÄ ett sÀtt dÀr man har nÄgot konkret att lösa och dÀr slutpunkten för varje delmoment inte Àr allt för avlÀgset. Enda jag hoppade i Rust var problem 22 del 2, orkade inte leta fram ett lÀmpligt big-num bibliotek (och fick overflow error nÀr jag försökte köra med i128).

Allt finns pÄ gibhub.

Efter att kikat i Reddit-trÄden skulle sÀga att sÀttet de flesta löste dag 21 (Springdroid adventure) och dag 25 (Cryostasis) kÀnns lite "fuskigt" dÄ de skrev skriptet för hand resp. spelade igenom textÀventyret som manuellt. Löste bÄda programmatisk.

Dag 22 gick att "brute-forace" genom följande insikt: "T" registret behövs egentligen inte, Àr ju bara vÀrdet pÄ "J" som spelar roll. Inget av register A-I behöver lÀsas mer Àn en gÄng. Med dessa villkor var det ju bara att generera varje möjligt program (som har en logisk skillnad mot tidigare program) samt cacha fallen som gÄtt fel och verifiera varje generarat skript mot (dÄ intcode datorn inte Àr supersnabb). Min lösning gick dÄ pÄ 190 ms pÄ en i7-8559U.

Dag 25 delade jag in i tre delar. Första dÀr alla icke-dödliga föremÄl letades upp samt noterade var "Security Checkpoint" lÄg, sökte med DFS sÄ nÀr det hela var avklarat stod roboten vid start igen. Del tvÄ var att gÄ till "Security Checkpoint". Del tre var helt enkelt att testa alla tÀnkbara kombinationer av föremÄl (totalt 256 st dÄ det fanns 8 föremÄl). Gick dÄ att lösa pÄ 138 ms.

Har ju undersökt Rust mycket med frÄgestÀllningen: verkar det snabbt nog redan nu för att anvÀnda i OS-utveckling? Svaret Àr verkar vara: ja, förutsatt att man skriver relativt C-likt (finns ju ÀndÄ massor med fördelar kring sÀkerhet i Rust)!

Körde inte med nĂ„gon listkomprehension för dag 24 (Planet of Discord), utan en bit-array för varje nivĂ„. Blev inte nĂ€rheten lika superkompakt lösning som @Ingetledigtnamn klĂ€mde till med i Python. ÄndĂ„ nöjd, gick att följa problembeskrivningen vĂ€ldigt 1:1 m.h.a. Rust "pattern-matching" och de ~120 rader lösningen tog var trots allt ganska precis 100x snabbare (tog 10 ms) jĂ€mfört med Python3 lösningen pĂ„ min dator (anvĂ€nder sjĂ€lv Python en hel del, men det Ă€r knappast rĂ€tt val i prestandakritiska fall...).

Skulle sÀga att vad som kan anses fuskigt kan ju diskuteras. Just dag 21 och 25 verkar ju skrivna för att kunna köras manuellt om man jÀmför med de tidigare.

Sen Àr det ju alltid en grÀnsdragning, ser att i din dag25 finns en svart-lista pÄ saker man inte ska ta, gÄr ju lÄta programmet hitta dessa ocksÄ men blir ju mer komplext.
Vidare sÄ Àr ju input:en olika sÄ tex funkar inte din dag25 med min input. Blir:

thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/libcore option.rs:378:21 stack backtrace: 0: backtrace::backtrace::libunwind::trace at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/libunwind.rs:88 1: backtrace::backtrace::trace_unsynchronized at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/mod.rs:66 .....

Dold text

Snygg lösning pÄ dag21. Jag rÀknade alldeles för pessimistiskt pÄ antal kombinationer sÄ skippade försöka med en brute-force utan körde den för hand i stÀllet.

●
TrÀdvy PermalÀnk
Datavetare ♄ ★
Plats
Stockholm
Registrerad
Jun 2011
Skrivet av SAFA:

Skulle sÀga att vad som kan anses fuskigt kan ju diskuteras. Just dag 21 och 25 verkar ju skrivna för att kunna köras manuellt om man jÀmför med de tidigare.

Sen Àr det ju alltid en grÀnsdragning, ser att i din dag25 finns en svart-lista pÄ saker man inte ska ta, gÄr ju lÄta programmet hitta dessa ocksÄ men blir ju mer komplext.
Vidare sÄ Àr ju input:en olika sÄ tex funkar inte din dag25 med min input. Blir:

thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/libcore option.rs:378:21 stack backtrace: 0: backtrace::backtrace::libunwind::trace at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/libunwind.rs:88 1: backtrace::backtrace::trace_unsynchronized at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/mod.rs:66 .....

Dold text

Snygg lösning pÄ dag21. Jag rÀknade alldeles för pessimistiskt pÄ antal kombinationer sÄ skippade försöka med en brute-force utan körde den för hand i stÀllet.

Tack för beta-testande
Hade gjort en miss i pĂ„ första rutan för dag 25, det fallerar pĂ„ fall dĂ€r det finns en utgĂ„ng Ă„t vĂ€ster i "Hull Breach". Är fixat nu (har inte testat med just din input, men har nu testat med ett par andra Ă€n min egen och fĂ„r precis symtomen du postade om första rummet har en utgĂ„ng Ă„t vĂ€st, annars fungerar det).

Är inte nöjd med explicit svartlista, men för dag 25 Ă€r som du sĂ€ger: nog lite meningen att man ska spela sig igenom den interaktivt. TĂ€nkte först bygga upp svartlistan automatiskt, men sĂ€ttet man dör pĂ„ Ă€r ju unik för alla fem fallen pĂ„ svartlistan sĂ„ blev liksom ingen poĂ€ng med att detektera dessa i stĂ€llet för att bara smacka in prylarna.

Skiter man i tiden för att lösa problem kan nuvarande lösning göras helautomatiskt rÀtt enkelt: starta med tom svartlista, kör lösningen med en timeout pÄ sÀg 10 sek (kommer i praktiken bara behövas för "infinite loop"). Om man fÄr timeout eller om programmet avslutas med nÄgot annat Àn exit(0) (nÄgot som Àr trivialt att hantera i t.ex. bash eller egentligen vad som helst som kan starta en process) lÀgger man till det sista som plockades upp i svartlistan, kompilerar om och kör igen...

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

●