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

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

Rust - dag 10

Sent svar idag p.g.a. julmiddag, Àr en imorgon ocksÄ...

Inte vÀrldens elegantaste lösning, men rÀtt svar i alla fall. AnvÀnder gcd() (största gemensamma nÀmnare) för att rÀkna ut riktningsvektorn till alla asteroider frÄn vald punkt för laserkanonen, det gör att alla asteroider utefter samma linje Àr garanterade att fÄ samma riktningsvektor. Sorterar allt efter detta, roterar det hela sÄ uppÄt fÄr lÀgsta vÀrde och tar bort duplikat. GÄr sedan runt i arrayen med riktningsvektorer och tar bort asteroider till det att 200 st Àr borttagna.

use super::Solution; use std::collections::HashSet; use MapContent::*; #[derive(PartialEq, Debug)] enum MapContent { Space, Astroid, } type Coord = (i32, i32); #[derive(Clone, Copy)] struct Visible { pos: Coord, count: usize, } // State required to solve day 10 pub struct State { map: Vec<Vec<MapContent>>, } fn is_on_map(pos: Coord, width: i32, height: i32) -> bool { pos.0 >= 0 && pos.1 >= 0 && pos.0 < width && pos.1 < height } fn hit( map: &Vec<Vec<MapContent>>, removed: &HashSet<Coord>, origin: Coord, dir: Coord, ) -> Option<Coord> { let mut pos = origin; loop { pos.0 = pos.0 + dir.0; pos.1 = pos.1 + dir.1; if !is_on_map(pos, map[0].len() as i32, map.len() as i32) { return None; } if !removed.contains(&pos) && map[pos.1 as usize][pos.0 as usize] == Astroid { return Some(pos); } } } fn is_visible(map: &Vec<Vec<MapContent>>, from: Coord, to: Coord, dir: Coord) -> bool { if let Some(pos) = hit(map, &HashSet::new(), from, dir) { if pos == to { return true } } false } fn dir_vector(base: Coord, pos: Coord) -> Coord { let dx = pos.0 - base.0; let dy = pos.1 - base.1; let gcd = num::integer::gcd(dx, dy); (dx / gcd, dy / gcd) } fn count_visible(map: &Vec<Vec<MapContent>>, pos: Coord) -> usize { let mut count = 0; for row in 0..map.len() { let y = row as i32; for col in 0..map[row].len() { let x = col as i32; if map[row][col] == Astroid && (x != pos.0 || y != pos.1) { if is_visible(map, pos, (x, y), dir_vector(pos, (x, y))) { count = count + 1; } } } } count } fn to_visibles(map: &Vec<Vec<MapContent>>) -> Vec<Visible> { let mut v = Vec::new(); for row in 0..map.len() { let y = row as i32; for col in 0..map[row].len() { let x = col as i32; if map[row][col] == Astroid { v.push(Visible { pos: (x, y), count: count_visible(map, (x, y)), }); } } } v } fn select_best_astroid(map: &Vec<Vec<MapContent>>) -> Visible { *to_visibles(map) .iter() .max_by(|a, b| a.count.cmp(&b.count)) .unwrap() } fn angle(pos: Coord) -> f64 { let a = (-pos.1 as f64).atan2(-pos.0 as f64) * 180.0 / 3.1415; if a < 90.0 { a + 360.0 } else { a } } fn unique_dir_vecs(map: &Vec<Vec<MapContent>>, laser_pos: Coord) -> Vec<Coord> { let mut dir_vecs = Vec::new(); for row in 0..map.len() { for col in 0..map[row].len() { let pos = (col as i32, row as i32); if map[row][col] == Astroid && laser_pos != pos { dir_vecs.push(dir_vector(laser_pos, pos)); } } } dir_vecs.sort_by(|&a, &b| angle(a).partial_cmp(&angle(b)).unwrap()); dir_vecs.dedup(); dir_vecs } fn nth_destroyed(nth: usize, map: &Vec<Vec<MapContent>>, laser_pos: Coord) -> Coord { let mut removed = HashSet::new(); let dir_vecs = unique_dir_vecs(&map, laser_pos); let mut n = nth; let mut dir_it = dir_vecs.iter().cycle(); loop { let &dir = dir_it.next().unwrap(); if let Some(pos) = hit(&map, &removed, laser_pos, dir) { removed.insert(pos); n = n - 1; if n == 0 { return pos; } } } } impl Solution for State { fn part1(&self) -> String { select_best_astroid(&self.map).count.to_string() } fn part2(&self) -> String { let best = select_best_astroid(&self.map).pos; let pos = nth_destroyed(200, &self.map, best); (pos.0 * 100 + pos.1).to_string() } } pub fn solution(lines: Vec<&str>) -> Box<dyn Solution> { Box::new(State { map: lines .iter() .map(|&row| { row.chars() .map(|pos| if pos == '.' { Space } else { Astroid }) .collect() }) .collect(), }) }

Lite av en brute-force lösning men ÀndÄ avklarad pÄ 20 ms pÄ en i7-5600U

fss

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
SkÄne
Registrerad
Aug 2009

Lugnare dag idag, men man börjar se ett mönster
* lÀgg till instruktinen reset till intcode som ÄsterstÀller alla fÀlt i programmet men fortsÀtter exekvera pÄ nuvarande position
* lÀgg till mode4 som istÀllet adresserar ett program i en annan intcode computer som körs parallellt, kör 10 program parallellt
* reset kan nu ta en parameter, reset 10 backar programkoden 10 steg. Kör program som kan backa tusentals steg
* allt ovan kör 100 parallella program som kan backa 1000-tals steg

●
TrÀdvy PermalÀnk
Medlem ♄
Plats
Jönköping
Registrerad
Mar 2002

Dag 10 i Kotlin

Satt uppe lite vÀl sent för att fixa denna igÄr, har tidigare Är haft problem med att bli smÄtt besatt och inte kan gÄ ivÀg frÄn problemet innan det Àr helt löst. Det har pÄverkat sömn och andra viktigare saker att göra. FÄr försöka ha bÀttre karaktÀr och slÀppa problemen efter en viss tid och fortsÀtta en annan dag istÀllet, annars fÄr jag nog lÀgga ner

Reflektion:

GrÀvde mig ner i en grop som till 99.9% fungerade sÄ hade svÄrt att slÀppa den och bankade huvudet mot skÀrmen innan jag kom pÄ att man kan anvÀnda atan2 rakt av.

Dold text

fun buildMap(input: Iterable<String>): Set<Pair<Int, Int>> { return input.withIndex().fold(setOf()) { acc, indexedRow -> indexedRow.value.withIndex().fold(acc) { accInner, indexedValue -> when (indexedValue.value) { '#' -> accInner + setOf(Pair(indexedValue.index, indexedRow.index)) '.' -> accInner else -> throw IllegalStateException() } } } } fun maxLineOfSight(asteroidMap: Set<Pair<Int, Int>>): Triple<Int, Int, Int>? = asteroidMap.map { (x, y) -> val angles = asteroidMap.fold(setOf<Double>()) { acc, (xx, yy) -> if (x == xx && y == yy) acc else acc + atan2(y.toDouble() - yy, x.toDouble() - xx) } Triple(x, y, angles.size) }.maxBy { it.third } fun part1(input: Iterable<String>): Triple<Int, Int, Int>? = maxLineOfSight(buildMap(input)) fun part2(input: Iterable<String>): List<Pair<Int, Int>> { val asteroidMap = buildMap(input) val (targetX, targetY, _) = maxLineOfSight(asteroidMap)!! val targetsByAngle = asteroidMap .fold(mapOf<Double, List<Pair<Int, Int>>>()) { acc, (x, y) -> if (x == targetX && y == targetY) acc else { val angle = atan2(y.toDouble() - targetY, x.toDouble() - targetX) acc + Pair(angle, (acc[angle] ?: listOf()) + Pair(x, y)) } } .toList() .sortedBy { it.first } val start = targetsByAngle.dropWhile { (angle, _) -> angle < -Math.PI / 2 } val end = targetsByAngle.takeWhile { (angle, _) -> angle < -Math.PI / 2 } val fireOrder = (start + end) .map { it.second .sortedBy { (x, y) -> sqrt((x.toDouble() - targetX).pow(2) + (y.toDouble() - targetY).pow(2)) } .toMutableList() } .toMutableList() val result = mutableListOf<Pair<Int, Int>>() while (fireOrder.isNotEmpty()) { fireOrder.forEach { result.add(it.removeAt(0)) } fireOrder.removeIf { it.isEmpty() } } return result }

Dold text

"Knowledge amplification. What he learns, we all learn. What he knows, we all benefit from."

●
TrÀdvy PermalÀnk
Medlem ♄ ★
Registrerad
Mar 2015

Dag 11 Uppgift 1&2
SprÄk C#
IntCode behövde ej uppdateras. Snodde Yoshmans teckenbaserade lösning för att skippa bitmap.

private void button11_Click(object sender, EventArgs e) { string input = DailyInput.GetInput(11); System.Diagnostics.Stopwatch watch = System.Diagnostics.Stopwatch.StartNew(); IntCode robot = new IntCode(input); Dictionary<string, ByteColor> hull = new Dictionary<string, ByteColor>(); HullCoord curPos = new HullCoord(0, 0); bool llContinue = true; int x = 0; int y = 0; if (this.numSubTask.Value==1) { hull.Add(curPos.ToString(), ByteColor.Black); } else { hull.Add(curPos.ToString(), ByteColor.White); } while (llContinue) { if (!hull.ContainsKey(curPos.ToString())) { hull.Add(curPos.ToString(), ByteColor.Black); } robot.AddInput((long)hull[curPos.ToString()]); long? colCode = robot.Compute(); if (colCode!=null) { hull[curPos.ToString()] = (ByteColor)colCode; long? turnCode = robot.Compute(); if (turnCode!=null) { curPos.Turn((TurnDirection)turnCode); curPos.Step(); } else { llContinue = false; } } else { llContinue = false; } } if (!robot.EndedCorrectly) { throw new Exception("Never got end code"); } if (this.numSubTask.Value==1) { this.txtAnswer.Text = hull.Count().ToString(); } else { Dictionary<ByteColor, string> colorCharacter = new Dictionary<ByteColor, string>(); colorCharacter.Add(ByteColor.Black, "█"); colorCharacter.Add(ByteColor.White, "▒"); colorCharacter.Add(ByteColor.Transparent, "."); int minx = 0; int miny = 0; int maxx = 0; int maxy = 0; foreach (KeyValuePair<string,ByteColor> item in hull) { HullCoord curCord = new HullCoord(item.Key); if (curCord.x<minx) { minx = curCord.x; } if (curCord.y<miny) { miny = curCord.y; } if (curCord.x>maxx) { maxx = curCord.x; } if (curCord.y>maxy) { maxy = curCord.y; } } int offsetx = 0 - minx; int offsety = 0 - miny; int width = maxx - minx +1; int height = maxy-miny +1; ByteColor[,] image = new ByteColor[width, height]; txtDebug.Clear(); for (int iy = 0; iy < height; iy++) { for (int ix = 0; ix < width; ix++) { string cCoord = (ix + offsetx).ToString() + "," + (iy + offsety).ToString(); image[ix, iy] = ByteColor.Black; if (hull.ContainsKey(cCoord)) { image[ix, iy] = hull[cCoord]; } txtDebug.AppendText(colorCharacter[image[ix, iy]]); } txtDebug.AppendText(System.Environment.NewLine); } } watch.Stop(); Int64 elapsedMs = watch.ElapsedMilliseconds; label1.Text = elapsedMs.ToString(); }

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

Dag: 11
SprÄk: Haskell

Trodde att vi skulle vara klara med Intcode, men nu var det iallafall bara applikation av den, och inte (nödvÀndigtvis) nÄgot direkt vidarearbete.

Fick Äterigen tillfÀlle att skriva en (enligt mig) snygg lösning mha. laziness i del 1. SÄnt e skoj!

type Pos = (Int, Int) part1 :: IO Int part1 = fmap (fst . paintShip Set.empty . parse) readInput part2 :: IO () part2 = putStrLn . drawHull . snd . paintShip (Set.singleton (0, 0)) . parse =<< readInput where drawHull h = let h' = Set.toList h (xs, ys) = (map fst h', map snd h') (bot, top) = (minimum ys, maximum ys) (left, right) = (minimum xs, maximum xs) in unlines $ flip map (reverse [bot .. top]) $ \y -> flip map [left .. right] $ \x -> if Set.member (x, y) h then '█' else ' ' paintShip :: Set Pos -> Mem -> (Int, Set Pos) paintShip initHull pgm = let os = run is pgm (colors, turns) = unzip (map head2 (chunksOf 2 os)) up = (0, 1) (poss, _) = unzip (scanl move ((0, 0), up) turns) hulls = scanl paint initHull (zip colors poss) is = zipWith (fromEnum .* Set.member) poss hulls nPanelsVisited = Set.size (Set.fromList poss) in (nPanelsVisited, last hulls) where move :: ((Int, Int), (Int, Int)) -> Int -> ((Int, Int), (Int, Int)) move (pos, dir) = \case 0 -> let dir' = turnLeft dir in (addPos pos dir', dir') _ -> let dir' = turnRight dir in (addPos pos dir', dir') turnLeft (dx, dy) = (-dy, dx) turnRight (dx, dy) = (dy, -dx) addPos (x, y) (dx, dy) = (x + dx, y + dy) paint hull (c, pos) = case c of 0 -> Set.delete pos hull _ -> Set.insert pos hull

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
Datavetare ♄ ★
Plats
Stockholm
Registrerad
Jun 2011

Rust - day 11

type Coord = (i32, i32); #[derive(Clone, Copy, Debug, PartialEq)] enum Paint { Black, White, } fn paint_hull(program: &Vec<Intcode>, start_tile_col: Paint) -> HashMap<Coord, Paint> { let (input, sink) = channel(); let output = exec(program, sink, None); let mut hull = HashMap::new(); let mut pos = (0, 0); let mut dir = (0, 1); // Facing up let mut color_cur_tile = start_tile_col; loop { if let Err(_) = input.send(if color_cur_tile == Paint::Black { 0 } else { 1 }) { break; }; let color = if let Ok(col) = output.recv() { if col == 0 { Paint::Black } else { Paint::White } } else { break; }; dir = match output.recv().unwrap() { 0 /* Left */ => (-dir.1, dir.0), _ /* Right */ => (dir.1, -dir.0), }; hull.insert(pos, color); pos.0 = pos.0 + dir.0; pos.1 = pos.1 + dir.1; color_cur_tile = if let Some(&color) = hull.get(&pos) { color } else { Paint::Black }; } hull } fn bound_box(hull: &HashMap<Coord, Paint>) -> (Coord, Coord) { let top = hull.keys().map(|p|p.1).min().unwrap(); let left = hull.keys().map(|p|p.0).min().unwrap(); let bottom = hull.keys().map(|p|p.1).max().unwrap(); let right = hull.keys().map(|p|p.0).max().unwrap(); ((left, top), (right, bottom)) } impl Solution for State { fn part1(&self) -> String { paint_hull(&self.program, Paint::Black).len().to_string() } fn part2(&self) -> String { let hull = paint_hull(&self.program, Paint::White); let (tl, br) = bound_box(&hull); let mut plate = Vec::new(); for y in (tl.1..=br.1).rev() { plate.push('\n'); for x in tl.0..=br.0 { let pos = (x as i32, y as i32); let ch = if let Some(&col) = hull.get(&pos) { if col == Paint::Black { '▒' } else { '█' } } else { '▒' }; plate.push(ch); } }; plate.iter().collect() } }

Utan Intcode kod dÄ den Àr samma som tidigare dagar som anvÀnder datorn

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
Jönköping
Registrerad
Mar 2002

Dag 11 i Kotlin

Min utskrift i del 2 blev spegelvÀnd och upp och ner först

kommentar

val translation = mapOf( Pair(Pair(0, 1), Pair(Pair(-1, 0), Pair(1, 0))), Pair(Pair(0, -1), Pair(Pair(1, 0), Pair(-1, 0))), Pair(Pair(1, 0), Pair(Pair(0, 1), Pair(0, -1))), Pair(Pair(-1, 0), Pair(Pair(0, -1), Pair(0, 1))) ) fun part1(input: String): Int { val computer = Day09.Computer(Day09.parse(input)) return travel(computer, Pair(0, 0), Pair(0, 1), mapOf()).size } fun part2(input: String): String { val computer = Day09.Computer(Day09.parse(input)) val result = travel(computer, Pair(0, 0), Pair(0, 1), mapOf(Pair(Pair(0, 0), listOf(1)))) val minX = result.keys.map { it.first }.min()!! val maxX = result.keys.map { it.first }.max()!! val minY = result.keys.map { it.second }.min()!! val maxY = result.keys.map { it.second }.max()!! return (minY..maxY).reversed().fold("") { accY, y -> (minX..maxX).fold(accY) { accX, x -> accX + if ((result[Pair(x, y)]?.last() ?: 0) == 1) "█" else " " } + "\n" } } tailrec fun travel(computer: Day09.Computer, coordinate: Pair<Int, Int>, direction: Pair<Int, Int>, state: Map<Pair<Int, Int>, List<Int>>): Map<Pair<Int, Int>, List<Int>> { val color = state[coordinate]?.last() ?: 0 val newState = when (computer.addInput(color.toLong()).getOutput()) { null -> return state 0L -> state + Pair(coordinate, (state[coordinate] ?: listOf()) + 0) 1L -> state + Pair(coordinate, (state[coordinate] ?: listOf()) + 1) else -> throw IllegalStateException() } val newDirection = when (computer.getOutput()) { 0L -> translation[direction]!!.first 1L -> translation[direction]!!.second else -> throw IllegalStateException() } val newCoordinate = Pair(coordinate.first + newDirection.first, coordinate.second + newDirection.second) return travel(computer, newCoordinate, newDirection, newState) }

kod

"Knowledge amplification. What he learns, we all learn. What he knows, we all benefit from."

●
Datavetare ♄ ★
Plats
Stockholm
Registrerad
Jun 2011

Rust - dag 12

En minimal 3D-vektor implementation gjorde del 1 superenkelt

đŸ•Żïž Part 1 : 7202 đŸ•Żïž Part 2 : 537881600740876 ⌚ Took : 19 ms

Kanske finns enklare sÀtt. Men en observation Àr i alla fall att rörelserna pÄ de olika axlarna Àr oberoende. GÄr dÀrför att separat rÀkna ut perioden per axel. Multiplicerar man sedan de tre perioderna sÄ har man en antal steg dÀr man garanterat Àr tillbaka till starten.

Problemet Àr att det kanske inte Àr perioden, utan perioden multiplicerad med nÄgon heltalsfaktor. Faktoriserade dÄ talet, kollande om nÄgon faktor Àr jÀmt delbar med alla tre perioderna för axlarna och minskar varje axels period med det. Sedan blir det nya perioden. rinse-and-repeat till dess att man bara kan dela med 1.

tankar kring del 2...

use super::Solution; use primes::factors_uniq; use regex::Regex; use std::ops::Add; use std::cmp::Ordering; type PlanetSystem = Vec<Moon>; fn energy(planet_system: &PlanetSystem) -> i32 { planet_system.iter().fold(0, |energy, moon| { energy + moon.pos.energy() * moon.vel.energy() }) } #[derive(Clone, Copy, Debug, PartialEq)] struct Vec3 { x: i32, y: i32, z: i32, } impl Vec3 { fn energy(&self) -> i32 { self.x.abs() + self.y.abs() + self.z.abs() } fn c_cmp(&self, other: Vec3) -> Vec3 { let cmp = |a: i32, b: i32| match a.cmp(&b) { Ordering::Less => -1, Ordering::Greater => 1, Ordering::Equal => 0, }; Vec3 { x: cmp(self.x, other.x), y: cmp(self.y, other.y), z: cmp(self.z, other.z), } } } impl Add for Vec3 { type Output = Vec3; fn add(self, other: Vec3) -> Vec3 { Vec3 { x: self.x + other.x, y: self.y + other.y, z: self.z + other.z, } } } impl Default for Vec3 { fn default() -> Self { Vec3 { x: 0, y: 0, z: 0 } } } #[derive(Clone, Copy, Debug, PartialEq)] struct Moon { pos: Vec3, vel: Vec3, } impl Moon { fn step_time(&self, moons: &PlanetSystem) -> Moon { let vel = moons .iter() .fold(self.vel, |new_vel, moon| new_vel + moon.pos.c_cmp(self.pos)); Moon { pos: self.pos + vel, vel: vel, } } } fn step_time(moons: &PlanetSystem) -> PlanetSystem { let mut next_moons = Vec::new(); for moon in moons { next_moons.push(moon.step_time(moons)); } next_moons } // State required to solve day 12 pub struct State { moons: PlanetSystem, } impl Solution for State { fn part1(&self) -> String { energy(&(0..1000).fold(self.moons.clone(), |cur_moons, _| step_time(&cur_moons))) .to_string() } fn part2(&self) -> String { let get_x = |v: Vec3| v.x; let get_y = |v: Vec3| v.y; let get_z = |v: Vec3| v.z; let chk = |moons: &PlanetSystem, get: &dyn Fn(Vec3) -> i32| { moons.iter().zip(self.moons.iter()).fold(true, |pred, m| { pred && get(m.0.vel) == 0 && get(m.0.pos) == get(m.1.pos) }) }; let mut x = 0; let mut y = 0; let mut z = 0; let mut steps: u64 = 0; let mut moons = self.moons.clone(); while x == 0 || y == 0 || z == 0 { moons = step_time(&moons); steps = steps + 1; if x == 0 && chk(&moons, &get_x) { x = steps; } if y == 0 && chk(&moons, &get_y) { y = steps; } if z == 0 && chk(&moons, &get_z) { z = steps; } } loop { let fact = factors_uniq(x * y * z); if let Some(denom) = fact .iter() .filter(|&d| x % d == 0 && y % d == 0 && z % d == 0) .last() { x = x / denom; y = y / denom; z = z / denom; } else { break; } } (x * y * z).to_string() } } fn parse_input(lines: Vec<&str>) -> PlanetSystem { let re = Regex::new(r"<x=(?P<x>[-]?\d+), y=(?P<y>[-]?\d+), z=(?P<z>[-]?\d+)>").unwrap(); let mut planet_system = Vec::new(); for line in lines { let caps = re.captures(line).unwrap(); planet_system.push(Moon { pos: Vec3 { x: caps["x"].parse::<i32>().unwrap(), y: caps["y"].parse::<i32>().unwrap(), z: caps["z"].parse::<i32>().unwrap(), }, vel: Vec3::default(), }); } planet_system } pub fn solution(lines: Vec<&str>) -> Box<dyn Solution> { Box::new(State { moons: parse_input(lines), }) }

Del 2 Àr inte vacker, fungerade inte pÄ första försöket om man sÀger sÄ...
uniq

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

●