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

PermalÀnk
Medlem ★
●
Skrivet av Bryal:

Om det Àr fullblÄsta OS-trÄdar du skapar sÄ har de indeed en hel del overhead. Skapa istÀllet lika mÄnga trÄdar i programmet som du har trÄdar i processorn, sÄ kan du eliminera mycket overhead frÄn frÀmst kontextbyte.

Ok, minns bara att jag för lÀnge sedan gjorde en server pÄ en tvÄkÀrnig processor som spawnade tusentals trÄdar utan att blinka, det var i VB.Net... NÄgon windowsversion efter NT.

PermalÀnk
Medlem
●

Jag plockar bort tvÄ saker frÄn scala koden jag postar, imports och sökvÀgen till dagens input. All kod bör vara körbar om man lÀgger till:

import java.nio.file.Path import scala.io.Source import scala.util.Using import scala.util.chaining._ val filePath = Path.of("""C:\vÀg\till\dagens\input\dagXX.txt""")

Dold text

Körtiden Àr "typ omedelbar" för all scala kod och "nÄgot lÄngsam" för apl koden.

Dag: 7
SprÄk: Scala (dotty)
Dags att skriva om intcode igen istÀllet för att ÄteranvÀnda. Ut med arrays och in med nÄgot Ät det mer funktionella hÄllet. Inte bara haskell man kan vara lat i.

case class State(mem: Vector[Int], ins: LazyList[Int], outs: List[Int] = Nil, ip: Int = 0) private def read(n: Int): Int = (mem(ip) / math.pow(10, (n + 1).toDouble).toInt) % 10 match case 0 => mem(mem(ip + n)) case 1 => mem(ip + n) private def write(n: Int)(value: Int): Vector[Int] = mem.updated(mem(ip + n), value) def step: Option[State] = 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 99 => None end State @main def day07: Unit = val input = Using.resource(Source.fromFile(filePath.toFile))(_.mkString.split(",")).flatMap(_.toIntOption).toVector def maxThruster(program: Vector[Int], range: Range): Option[Int] = range.permutations.flatMap { perm => lazy val outs: LazyList[Int] = perm.foldLeft(0 #:: outs)((ins, p) => LazyList.unfold(State(program, p #:: ins))(_.step.map(m => m.outs -> m)).flatten) outs }.maxOption maxThruster(input, 0 to 4).foreach(println) maxThruster(input, 5 to 9).foreach(println) end day07

Dold text
PermalÀnk
Medlem ★
●

Hade varit nice om det gick att hÀmta sin input, men man mÄste vara inloggad, nÄgon som löst det? Jag loggade in med google.

PermalÀnk
Medlem ★
●

Dag 8 Uppgift 1&2
SprÄk C#
BÄda gick pÄ ca 75ms med en del onödiga grejer, enklaste uppgiften hittills.

private void task08single(string input) { int imageWidth = 25; int imageHeigth = 6; int imageSize = imageHeigth * imageWidth; int layerCount = input.Length / imageSize; int[,,] imageData = new int[layerCount, imageWidth, imageHeigth]; int[,] layerColorCount = new int[layerCount, 10]; for (int i = 0; i < input.Length; i++) { GetCoordinate(25, 6, i, out int layer, out int x, out int y); int color = ToSafeInt(input.Substring(i, 1)); imageData[layer, x, y] = color; layerColorCount[layer, color] = layerColorCount[layer, color] + 1; } int minZeroes = imageSize; int leastZeroesLayer = -1; for (int i = 0; i < layerCount; i++) { if (layerColorCount[i,0]<minZeroes) { minZeroes = layerColorCount[i, 0]; leastZeroesLayer = i; } } if (this.numSubTask.Value==1) { txtDebug.Clear(); for (int y = 0; y < imageHeigth; y++) { for (int x = 0; x < imageWidth; x++) { txtDebug.AppendText(imageData[leastZeroesLayer, x, y].ToString()); } txtDebug.AppendText(System.Environment.NewLine); } int result = layerColorCount[leastZeroesLayer, 1] * layerColorCount[leastZeroesLayer, 2]; txtAnswer.Text = result.ToString(); } else { Color[,] finalImage = new Color[imageWidth, imageHeigth]; for (int y = 0; y < imageHeigth; y++) { for (int x = 0; x < imageWidth; x++) { finalImage[x, y] = (Color)imageData[0, x, y]; } } for (int y = 0; y < imageHeigth; y++) { for (int x = 0; x < imageWidth; x++) { int l = 1; while (finalImage[x, y]==Color.Transparent && l<layerCount) { finalImage[x, y] = (Color)imageData[l, x, y]; l++; } } } txtDebug.Clear(); Bitmap bitmapMessage = new Bitmap(imageWidth, imageHeigth, System.Drawing.Imaging.PixelFormat.Format32bppArgb); for (int y = 0; y < imageHeigth; y++) { for (int x = 0; x < imageWidth; x++) { System.Drawing.Color pxColor; if (finalImage[x,y]==Color.Black) { pxColor = System.Drawing.Color.Black; } else { if (finalImage[x, y] == Color.White) { pxColor = System.Drawing.Color.White; } else { pxColor = System.Drawing.Color.Transparent; } } bitmapMessage.SetPixel(x, y, pxColor); txtDebug.AppendText(((int)finalImage[x, y]).ToString()); } txtDebug.AppendText(System.Environment.NewLine); } pictureBox1.Image = bitmapMessage; } } private void GetCoordinate(int width,int heigth,int sequence, out int layer, out int x, out int y) { int imagesize = width * heigth; layer = sequence / (imagesize); int pixelpos = sequence % imagesize; x = pixelpos % width; y = pixelpos / width; }

Dold text
PermalÀnk
Datavetare ★
●

Rust - dag 8

VÀxlar lite fram och tillbaka mellan "streams" och vanlig imperativ stil. KÀnner nog att den senare Àr enklare ihop med Rusts borrow-checker, Àr nog ocksÄ den lÀmpligare stilen om Rust skulle bli ett OS-sprÄk dÄ man lÀttare ser exakt vad som hÀnder (nÄgot som ofta Àr kritiskt i OS p.g.a. extrema prestandakrav).

Helt klart ger "streams" modellen klart kompaktare kod i majoriten av fallen, men kod ska primÀrt optimeras för att vara enkelt att lÀsa, inte snabbt att skriva!

use super::Solution; use regex::Regex; const WIDTH: usize = 25; const HEIGHT: usize = 6; const BLACK: char = '0'; const TRANSPARENT: char = '2'; // State required to solve day 8 pub struct State { layers: Vec<String>, } pub fn solution(lines: Vec<&str>) -> Box<dyn Solution> { let re = Regex::new(&format!("(.{{{}}})", WIDTH * HEIGHT)).unwrap(); let mut layers = Vec::new(); for cap in re.captures_iter(lines[0]) { layers.push(String::from(&cap[1])); } Box::new(State { layers: layers }) } fn render(layers: &Vec<String>, width: usize, height: usize) -> Vec<String> { let mut image = Vec::new(); for h in 0..height { let mut row = String::from(""); for w in 0..width { let mut pixel = TRANSPARENT; for layer in layers { if pixel == TRANSPARENT { pixel = layer.chars().nth(h * width + w).unwrap(); if pixel != TRANSPARENT { pixel = if pixel == BLACK { '▒' } else { '█' } } } } row.push(pixel) } image.push(row) } image } fn count_pixels(layer: &String, pixel: char) -> usize { layer.chars().filter(|&pxl| pxl == pixel).count() } impl Solution for State { fn part1(&self) -> String { let zeros: Vec<usize> = self .layers .iter() .map(|layer| count_pixels(layer, '0')) .collect(); let min_zeros = zeros.iter().min().unwrap(); let selected_layer = &self.layers[zeros.iter().position(|cnt| cnt == min_zeros).unwrap()]; (count_pixels(&selected_layer, '1') * count_pixels(&selected_layer, '2')).to_string() } fn part2(&self) -> String { let msg = render(&self.layers, WIDTH, HEIGHT); "\n".to_string() + &msg.join("\n") } }

En lösning i Rust för dag 8

Day 1
đŸ•Żïž Part 1 : 3305115
đŸ•Żïž Part 2 : 4954799
⌚ Took : 0 ms

Day 2
đŸ•Żïž Part 1 : 4090701
đŸ•Żïž Part 2 : 6421
⌚ Took : 0 ms

Day 3
đŸ•Żïž Part 1 : 1211
đŸ•Żïž Part 2 : 101386
⌚ Took : 24 ms

Day 4
đŸ•Żïž Part 1 : 2050
đŸ•Żïž Part 2 : 1390
⌚ Took : 13 ms

Day 5
đŸ•Żïž Part 1 : 11193703
đŸ•Żïž Part 2 : 12410607
⌚ Took : 0 ms

Day 6
đŸ•Żïž Part 1 : 251208
đŸ•Żïž Part 2 : 397
⌚ Took : 9 ms

Day 7
đŸ•Żïž Part 1 : 437860
đŸ•Żïž Part 2 : 49810599
⌚ Took : 0 ms

Day 8
đŸ•Żïž Part 1 : 2760
đŸ•Żïž Part 2 :
▒██▒▒▒██▒▒█▒▒█▒████▒███▒▒
█▒▒█▒█▒▒█▒█▒▒█▒█▒▒▒▒█▒▒█▒
█▒▒█▒█▒▒▒▒█▒▒█▒███▒▒███▒▒
████▒█▒██▒█▒▒█▒█▒▒▒▒█▒▒█▒
█▒▒█▒█▒▒█▒█▒▒█▒█▒▒▒▒█▒▒█▒
█▒▒█▒▒███▒▒██▒▒████▒███▒▒
⌚ Took : 0 ms

Exekveringstider för alla dagar sÄ hÀr lÄngt pÄ en i7-8559U utrustad NUC körandes Ubuntu 18.04
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 ★
●

Python. List comprehensions Àr kraftfulla, men kanske inte helt lÀttlÀsta för den som inte skrivit dem. FrÄga gÀrna om ni Àr nyfikna pÄ vad de gör.

import collections def read_layers(): with open('aoc8.txt') as f: data = [int(c) for c in f.read().strip()] return [data[i:i + 25 * 6] for i in xrange(0, len(data), 25 * 6)] layers = read_layers() # part one m = min([collections.Counter(x) for x in layers], key = lambda c: c[0]) print m[1] * m[2] # part two pic = ''.join([' *'[[l[i] for l in layers if l[i] != 2][0]] for i in range(25 * 6)]) for i in range(0, 25 * 6, 25): print pic[i:i + 25]

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

Python. List comprehensions Àr kraftfulla, men kanske inte helt lÀttlÀsta för den som inte skrivit dem. FrÄga gÀrna om ni Àr nyfikna pÄ vad de gör.

import collections def read_layers(): with open('aoc8.txt') as f: data = [int(c) for c in f.read().strip()] return [data[i:i + 25 * 6] for i in xrange(0, len(data), 25 * 6)] layers = read_layers() # part one m = min([collections.Counter(x) for x in layers], key = lambda c: c[0]) print m[1] * m[2] # part two pic = ''.join([' *'[[l[i] for l in layers if l[i] != 2][0]] for i in range(25 * 6)]) for i in range(0, 25 * 6, 25): print pic[i:i + 25]

Dold text

försöker testa men xrange saknas...

[EDIT] sorry, var lite snabb, var bara att byta till range i Python 3.7
sÄ hÀr blev den körbar för mig

import collections import sys import os import time def read_layers(): with open(GetInputFileName()) as f: data = [int(c) for c in f.read().strip()] return [data[i:i + 25 * 6] for i in range(0, len(data), 25 * 6)] def GetScriptPath(): return os.path.dirname(os.path.realpath(__file__)) + os.sep def GetInputFileName(): return GetScriptPath() + "input08.txt" def main(): layers = read_layers() # part one start_time = time.perf_counter_ns()/1000000 m = min([collections.Counter(x) for x in layers], key = lambda c: c[0]) print (m[1] * m[2]) print("milliseconds --- " + str((time.perf_counter_ns()/1000000 - start_time))) # part two start_time = time.perf_counter_ns()/1000000 pic = ''.join([' *'[[l[i] for l in layers if l[i] != 2][0]] for i in range(25 * 6)]) for i in range(0, 25 * 6, 25): print (pic[i:i + 25]) print("milliseconds --- " + str((time.perf_counter_ns()/1000000 - start_time))) if __name__ == "__main__": main()

Dold text

ca 15 ggr snabbare Àn min C# kod. Sjukt snygg lösning.

PermalÀnk
Datavetare ★
●
Skrivet av Mordekai:

Ok, minns bara att jag för lÀnge sedan gjorde en server pÄ en tvÄkÀrnig processor som spawnade tusentals trÄdar utan att blinka, det var i VB.Net... NÄgon windowsversion efter NT.

I de flesta programsprÄk samt i de flesta trÄd-APIer har man tyvÀrr blandat ihop tvÄ oberoende koncept:

  • uppdelning av uppgifter i oberoende körbara enheter (concurrency)

  • anvĂ€nde av flera CPU-trĂ„dar (parallellism)

Är normalt mycket bĂ€ttre att lĂ„ta OS eller nĂ„got ramverk sköta det senare, detta dĂ„ det krĂ€vs kunskap om systemet för att avgöra vad som Ă€r optimalt dĂ€r. Det förra Ă€r dĂ€remot nĂ„got som enbart den som skapar programvaran kan veta nĂ„got om.

Alla parallella program Àr "concurrent", men det omvÀnda gÀller inte. Vi ser ju rÀtt mycket fokus pÄ "asynkron programmering" just nu, det Àr just fallet att fÄ "concurrency" men utan att blanda in parallellism (trenden mot mikroservices gör detta otroligt anvÀndbart).

Är nĂ„got jag gillar hos Go, dĂ€r uttrycker man enbart det första m.h.a. "goroutines". Go-plattformen fixar parallellismen beroende pĂ„ underliggande plattform och potentiell parallellism frĂ„n programmet! Coroutiner/async koncepten ger som sagt bara det första, men man tappar parallellism (gĂ„r sjĂ€lvklart att manuellt fixa till). FĂ„r i princip samma prestanda hos min dag 7 lösning i Go vare sig man kör pĂ„ en CPU-trĂ„d eller lĂ„ter den anvĂ€nda alla CPU-trĂ„dar.

Go har ocksĂ„ en annan cool finess, anropsstacken kan vĂ€xa dynamiskt sĂ„ rekursion Ă€r lĂ„ngt mer "sĂ€kert". Är ocksĂ„ detta som gör att man kan ha brutalt med goroutines, de startar alltid med en extremt liten anropsstack.

Python Àr lite av en katastrof just pÄ den hÀr punkten. Python anvÀnder OS-trÄdar, men p.g.a. dess design (Global Interpreter Lock) fÄr man noll parallellism men betalar ÀndÄ overhead för OS-trÄdar. Som tur Àr har man lagt till "async" nyckelordet i Python 3.5.

Men vi ser hÀr vad som Àr Pythons styrka: ofta betydligt kortare lösningar för Advent of Code problem dÀr Àn i systemsprÄken. Vilket Àr helt förvÀntat givet vad fokus i de olika fallen.

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: 8
SprÄk: Haskell

{-# LANGUAGE LambdaCase #-} module Day8 (part1, part2) where import Data.List.Split import Data.List import Lib part1 :: IO Int part1 = fmap (snd . minimumOn fst . map f . chunksOf (width * height)) readInput where f cs = (nDigs '0' cs, nDigs '1' cs * nDigs '2' cs) nDigs c cs = length (filter (== c) cs) part2 :: IO () part2 = readInput >>= putStrLn . unlines . chunksOf width . map stack . transpose . chunksOf (width * height) where stack = \case '0' : _ -> ' ' '1' : _ -> '█' '2' : cs -> stack cs _ -> error "stack" width, height :: Int width = 25 height = 6 readInput :: IO String readInput = readFile "inputs/day-8"

Dold text
Visa signatur

Arbets- / Spelstation: Arch Linux - Ryzen 5 3600 - RX 7900 XT - 32G DDR4
Server: Arch Linux - Core i5-10400F - 16G DDR4

PermalÀnk
Medlem
●

Dag: 8
SprÄk: Scala

Jag försökte fÄ ihop en kortare lösning i APL eftersom det hÀr var ett sÄ pass lÀtt problem men var tvungen att ge upp efter nÄn timme. Inser att jag nog mÄste lÀgga ett par dagar pÄ att lÀra mig grunderna bÀttre.

val layers = Files.readAllBytes(filePath).map(_ - '0').grouped(25 * 6).toArray layers .minBy(_.count(_ == 0)) .groupMapReduce(identity)(_ => 1)(_ + _) .pipe(m => println(m(1) * m(2))) layers.transpose .flatMap(_.find(_ != 2)) .grouped(25) .map(_.map(x => if (x == 1) "█" else " ").mkString) .foreach(println)

Dold text
PermalÀnk
Medlem
●

AoC ♄
Hoppas bara man har tid att fullfölja hela...

Dag: 8
SprÄk: ES6
Tid: ~2ms resp. ~0.3ms (stock 2500k)

Uppgift 1:

Klicka för mer information

const img = require('./input') const metaInfo = { x: 25, y: 6, } const SpaceImageChecksum = (image, size) => { const countLayer = input => ({ zeros: input.match(/0/g).length, ones: input.match(/1/g).length, twos: input.match(/2/g).length }) const layerRegExp = new RegExp(`.{1,${size.x*size.y}}`, 'g') const layers = image.match(layerRegExp) const reducedLayers = layers.map(countLayer) const fewestZeros = reducedLayers.sort((a,b) => a.zeros - b.zeros) return fewestZeros[0].ones * fewestZeros[0].twos } console.log(SpaceImageChecksum(img, metaInfo))

Visa mer

Uppgift 2:

Klicka för mer information

const img = require('./input') const metaInfo = { x: 25, y: 6, } const SpaceImageDecoder = (image, size) => { const layerRegExp= new RegExp(`.{1,${size.x*size.y}}`, 'g') const layers = image.match(layerRegExp) const finalImage = new Array(size.y).fill(undefined).map(_=>[]) for (let y = 0; y < size.y; y++) { for (let x = 0; x < size.x; x++) { const layerIndex = (y+1)*size.x + x - size.x const pixel = layers.find(l => l.charAt(layerIndex) !== '2').charAt(layerIndex) finalImage[y].push(pixel === '1' ? '█' : ' ') } } return finalImage.map(r => r.join('')).join(`\n`) } console.log(SpaceImageDecoder(img, metaInfo))

Visa mer
Visa signatur

CPU: Intel i5 2500K @ 4,7GHz Mobo: Asus P8Z68-V
GPU: Asus STRIX 970 RAM: 8GB Corsair Vengence 1600 MHz CL9
PSU: OCZ ModXStream 700W Chassi: NZXT Phantom

Citera sÄ att jag hittar tillbaka!

PermalÀnk
Medlem ★
●
Skrivet av Mordekai:

ca 15 ggr snabbare Àn min C# kod. Sjukt snygg lösning.

15 lÄter vÀldigt mycket. JÀmför du verkligen Àpplen och Àpplen? Du tog inte med inlÀsningen av filen i Python-fallet och det borde stÄ för en mÀrkbar del av körtiden.

PermalÀnk
Medlem
●
Skrivet av Mordekai:

Dag 8 Uppgift 1&2
SprÄk C#
BÄda gick pÄ ca 75ms med en del onödiga grejer, enklaste uppgiften hittills.

private void task08single(string input) { int imageWidth = 25; int imageHeigth = 6; int imageSize = imageHeigth * imageWidth; int layerCount = input.Length / imageSize; int[,,] imageData = new int[layerCount, imageWidth, imageHeigth]; int[,] layerColorCount = new int[layerCount, 10]; for (int i = 0; i < input.Length; i++) { GetCoordinate(25, 6, i, out int layer, out int x, out int y); int color = ToSafeInt(input.Substring(i, 1)); imageData[layer, x, y] = color; layerColorCount[layer, color] = layerColorCount[layer, color] + 1; } int minZeroes = imageSize; int leastZeroesLayer = -1; for (int i = 0; i < layerCount; i++) { if (layerColorCount[i,0]<minZeroes) { minZeroes = layerColorCount[i, 0]; leastZeroesLayer = i; } } if (this.numSubTask.Value==1) { txtDebug.Clear(); for (int y = 0; y < imageHeigth; y++) { for (int x = 0; x < imageWidth; x++) { txtDebug.AppendText(imageData[leastZeroesLayer, x, y].ToString()); } txtDebug.AppendText(System.Environment.NewLine); } int result = layerColorCount[leastZeroesLayer, 1] * layerColorCount[leastZeroesLayer, 2]; txtAnswer.Text = result.ToString(); } else { Color[,] finalImage = new Color[imageWidth, imageHeigth]; for (int y = 0; y < imageHeigth; y++) { for (int x = 0; x < imageWidth; x++) { finalImage[x, y] = (Color)imageData[0, x, y]; } } for (int y = 0; y < imageHeigth; y++) { for (int x = 0; x < imageWidth; x++) { int l = 1; while (finalImage[x, y]==Color.Transparent && l<layerCount) { finalImage[x, y] = (Color)imageData[l, x, y]; l++; } } } txtDebug.Clear(); Bitmap bitmapMessage = new Bitmap(imageWidth, imageHeigth, System.Drawing.Imaging.PixelFormat.Format32bppArgb); for (int y = 0; y < imageHeigth; y++) { for (int x = 0; x < imageWidth; x++) { System.Drawing.Color pxColor; if (finalImage[x,y]==Color.Black) { pxColor = System.Drawing.Color.Black; } else { if (finalImage[x, y] == Color.White) { pxColor = System.Drawing.Color.White; } else { pxColor = System.Drawing.Color.Transparent; } } bitmapMessage.SetPixel(x, y, pxColor); txtDebug.AppendText(((int)finalImage[x, y]).ToString()); } txtDebug.AppendText(System.Environment.NewLine); } pictureBox1.Image = bitmapMessage; } } private void GetCoordinate(int width,int heigth,int sequence, out int layer, out int x, out int y) { int imagesize = width * heigth; layer = sequence / (imagesize); int pixelpos = sequence % imagesize; x = pixelpos % width; y = pixelpos / width; }

Dold text

SprÄk C, bÄda tog 1-2 ms. (mest för att getchar() Àr lÄngsam)

Kör med :
cat input | ./part1

Del 1:

#include <stdio.h> #define HEIGHT (6) #define WIDTH (25) void readlayer(int h, int w, int *z, int *o, int *t) { int i, j, zeros, ones, twos; char ch; zeros = ones = twos = 0; for (i = 0; i < w*h; i++) { ch = getchar(); if (ch == '0') zeros++; if (ch == '1') ones++; if (ch == '2') twos++; } *z = zeros;*o = ones;*t = twos; } void main() { int zeros, ones, twos; int minzeros, minresult; minzeros = WIDTH*HEIGHT; do { readlayer(HEIGHT, WIDTH, &zeros, &ones, &twos); if (((zeros + ones + twos) > 0) && (zeros < minzeros)) { minzeros = zeros; minresult = ones * twos; } } while (feof(stdin) == 0); printf("Result: 1:s * 2:s %d \n", minresult); }

Dold text

Del 2:

#include <stdio.h> #define HEIGHT (6) #define WIDTH (25) char image[HEIGHT][WIDTH]; void readlayer(int h, int w) { int i, j; char ch; for (i = 0; i < h; i++) { for (j = 0; j < w; j++) { ch = getchar(); if (image[i][j] == '2') { image[i][j] = ch; } } } } void main() { int i, j, ch; /* init image to transparent */ for (i = 0; i < HEIGHT; i++) { for (j = 0; j < WIDTH; j++) { image[i][j] = '2'; } } do { readlayer(HEIGHT, WIDTH); } while (feof(stdin) == 0); printf("\n"); for (i = 0; i < HEIGHT; i++) { for (j = 0; j < WIDTH; j++) { ch = image[i][j]; if (ch == '0') printf(" "); if (ch == '1') printf("**"); if (ch == '2') printf(".."); } printf("\n"); } }

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

15 lÄter vÀldigt mycket. JÀmför du verkligen Àpplen och Àpplen? Du tog inte med inlÀsningen av filen i Python-fallet och det borde stÄ för en mÀrkbar del av körtiden.

Nej jag utgÄr Àven i min kod frÄn en strÀng i minnet. Men min kod Àr ju kass, det Àr det som Àr poÀngen, jag stegar igenom strÀngen tecken för tecken och rÀknar ut x,y,z för varje tecken, helt idiotiskt. Blev i en tidigare uppgifter tagen pÄ sÀngen nÀr data inte kom i en snÀll ordning (Orbital Map). Sedan var det mer ett sÀtt att göra koden lÀttlÀst/hanterlig/ÄteranvÀndbar.

PermalÀnk
●

Dag 8 i Kotlin

fun part1(input: List<Int>, width: Int, height: Int): Int { val chunkSize = width * height val frame = input.windowed(chunkSize, chunkSize).minBy { it.count { it == 0 } }!! return frame.filter { it == 1 }.count() * frame.filter { it == 2 }.count() } fun part2(input: List<Int>, width: Int, height: Int): String { val chunkSize = width * height val image = Array(chunkSize) { 2 } input.windowed(chunkSize, chunkSize).forEach { row -> row.withIndex().forEach { indexedValue -> if (image[indexedValue.index] == 2) { image[indexedValue.index] = indexedValue.value } } } return image.toList() .windowed(width, width) .joinToString("\n") { it.joinToString(separator = "") .replace('1', '#') .replace('0', ' ') } }

Dold text
Visa signatur

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

PermalÀnk
Datavetare ★
●

Go - dag 8

Just i det hÀr fallet kan man fÄ en riktigt kort lösning Àven i ett sprÄk som Go dÀr det inte finns saker som "list-comprehension" och dÀr standardbiblioteket inte har supermycket saker för strÀnghantering. Kanske inte den mest lÀsbara lösningen, Àven om det inte Àr sÄ illa.

package main import ("fmt"; "io/ioutil") const WIDTH = 25 const HEIGHT = 6 type Count struct { zeros, ones, twos int } func main() { data,_ := ioutil.ReadFile("input08.txt") image := [HEIGHT][WIDTH]rune{} sel := Count{WIDTH, 0, 0} cur := Count{} for i, layerPixel := range []rune(string(data)) { switch layerPixel { case '0': cur.zeros++ case '1': cur.ones++ case '2': cur.twos++ } if (i + 1) % (WIDTH * HEIGHT) == 0 { if sel.zeros > cur.zeros { sel = cur } cur = Count{} } imagePixel := &image[i / WIDTH % HEIGHT][i % WIDTH] if *imagePixel == 0 && layerPixel != '2' { if layerPixel == '1' { *imagePixel = '█' } else { *imagePixel = '▒' } } } fmt.Printf("Part 1: %v\n", sel.ones * sel.twos) fmt.Println("Part 2:") for _, line := range image { fmt.Println(string(line[:])) } }

Som bonus löses bÄda delarna i ett pass av indata
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: 9
SprÄk: Scala (dotty)

Ännu en intcode utmaning. SjĂ€lv har jag börjat tröttna och skulle föredra helt olika utmaningar varje dag. Det mĂ„ste vara vĂ€ldigt trĂ„kigt om man kört fast pĂ„ en av de tidigare intcode dagarna nĂ€r varannan ny utmaning krĂ€ver att man löst alla andra först.
Behövdes inte sÄ mÄnga Àndringar frÄn dag 7 men missade först tvÄ ord i slutet av en mening vilket gjorde att opcode 3 inte fungerade som den skulle.

case class State( 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).toDouble).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 step: Option[State] = 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 end State @main def day09main: Unit = val input = Using.resource(Source.fromFile(filePath.toFile))(_.mkString.split(",")).flatMap(_.toLongOption) val program = Iterator.from(0).map(_.toLong).zip(input).toMap.withDefaultValue(0L) Iterator.unfold(State(program, LazyList(1)))(_.step.map(s => s.outs -> s)).flatten.foreach(println) Iterator.unfold(State(program, LazyList(2)))(_.step.map(s => s.outs -> s)).flatten.foreach(println)

Dold text
PermalÀnk
Medlem
●

Dag: 9
SprÄk: Haskell

Ja, vid det hÀr laget Àr man ju vÀl nöjd med Intcode. Bra att det verkar vara fÀrdigt nu Ätminstone.

Min lösning skiljer sig inte mycket mot tidigare dagar. Missade först att man skulle börja med "stort" tomt minne den hÀr gÄngen, sÄ fick lite out-of-bounds indexering först.

{-# LANGUAGE LambdaCase, TemplateHaskell, TypeApplications #-} module Day9 (part1, part2) where import Control.Monad.State import Control.Monad.Writer import Control.Applicative import Data.List.Split import Lens.Micro.Platform (makeLenses, use, to, modifying, (<<%=), assign) import Data.Sequence (Seq) import Data.Composition import qualified Data.Sequence as Seq newtype Addr = Addr Int deriving (Ord, Eq) type Pc = Int type Mem = Seq Int data St = St { _pc :: Pc, _base :: Addr, _inp :: [Int], _mem :: Mem } makeLenses ''St type Eval a = StateT St (Writer [Int]) a part1 :: IO [Int] part1 = fmap (run [1] . parse) readInput part2 :: IO [Int] part2 = fmap (run [2] . parse) readInput readInput :: IO String readInput = readFile "inputs/day-9" parse :: String -> Mem parse s = let m = Seq.fromList (fmap read (splitOn "," s)) in m Seq.>< Seq.fromFunction (8000 - Seq.length m) (const 0) run :: [Int] -> Mem -> [Int] run = execWriter . evalStateT eval .* St 0 (Addr 0) eval :: Eval () eval = step >>= \case True -> pure () False -> eval step :: Eval Bool step = do (opcode, modes) <- nextInstr let binop' = binop (modes !! 0) (modes !! 1) (modes !! 2) let jmpIf' = jmpIf (modes !! 0) (modes !! 1) case opcode of 1 -> binop' (+) 2 -> binop' (*) 3 -> input (modes !! 0) 4 -> output (modes !! 0) 5 -> jmpIf' (/= 0) 6 -> jmpIf' (== 0) 7 -> binop' (fromEnum .* (<)) 8 -> binop' (fromEnum .* (==)) 9 -> adjustBase (modes !! 0) 99 -> pure () _ -> error "Undefined opcode" pure (if opcode == 99 then True else False) where nextInstr = fmap (\x -> (extractOpcode x, extractModes x)) next extractOpcode x = mod x 100 extractModes x = map (\n -> mod (div x (10 ^ n)) 10) [2 :: Int ..] next = load . Addr =<< (pc <<%= (+ 1)) binop amode bmode cmode f = do v <- liftA2 f (getArg amode) (getArg bmode) store v cmode input mode = do i <- fmap head (inp <<%= tail) store i mode output mode = tell . pure =<< getArg mode jmpIf amode bmode pred = do (a, b) <- liftA2 (,) (getArg amode) (getArg bmode) when (pred a) (assign pc b) adjustBase mode = modifying base =<< fmap addAddr (getArg mode) store v mode = getAddr mode >>= \(Addr i) -> modifying mem (Seq.update i v) load (Addr i) = use (mem . to (flip Seq.index i)) :: Eval Int getArg = \case 1 -> next -- Immediate mode n -> load =<< getAddr n getAddr = \case 0 -> fmap Addr next -- Address mode 2 -> relativeBase =<< next -- Relative mode _ -> error "getAddr" relativeBase x = use (base . to (addAddr x)) :: Eval Addr addAddr b (Addr a) = (Addr (a + b))

Dold text
Visa signatur

Arbets- / Spelstation: Arch Linux - Ryzen 5 3600 - RX 7900 XT - 32G DDR4
Server: Arch Linux - Core i5-10400F - 16G DDR4

PermalÀnk
Medlem ★
●

Ok, jag förstÄr faktiskt inte parametermode och skriv till adress. Helt ologiskt.
Detta Àr exemplet
109,1,204,-1,1001,100,1,100,1008,100,16,101,1006,101,0,99

pos[0], mode=value, instruction=change base, base++1
pos[2], mode=baseoffset, instruction = output, lÀs frÄn basadress-1, output 109
pos[4], mode=address,value,address, instruction add, skriv adress[100]+value[1] till adress[100]
errror adress 100 finns ej...

Vad har jag snurrat till?

[edit] oops missade

Citat:

The computer's available memory should be much larger than the initial program. Memory beyond the initial program starts with the value 0 and can be read or written like any other memory. (It is invalid to try to access memory at a negative address, though.)

PermalÀnk
Medlem ★
●

Jag har kört fast... nÄgon som ser buggen? FÄr tvÄ outputs, först ett vÀrde sedan noll. Alternativt, kan nÄgon tÀnka sig att byta inputs sÄ jag kan testa min med en annan input, eller du kan se om du ocksÄ fÄr tvÄ outputs med min input (osannolikt)?

EDIT: Löst
Stör mig pÄ att adressen att skriva till alltid Àr absolut oavsett parameter mode 0 eller 1 men med parametermode 2 Àndras skrivadressen. Tack @pacc det hjÀlpte mig hitta felet. Nu Àr det mer spaghetti Àn nÄgonsin.

using System; using System.Collections; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows.Forms; using System.IO; using System.Threading; using System.Text.RegularExpressions; //https://adventofcode.com/ namespace AdventOfCode2019 { public partial class frmAdventOfCode : Form { private void button9_Click(object sender, EventArgs e) { string input = DailyInput.GetInput(9); this.txtInput.Text = input; System.Diagnostics.Stopwatch watch = System.Diagnostics.Stopwatch.StartNew(); IntCode computer = new IntCode(); long[] inputs = new long[1]; if (this.numSubTask.Value>0 && this.numSubTask.Value <3) { inputs[0] = (int)this.numSubTask.Value; } computer.Init(input,inputs); bool stillRunning = true; long lastOutput=0; while (stillRunning) { long? output = computer.Compute(); if (output!=null) { lastOutput = (long)output; this.txtDebug.AppendText(System.Environment.NewLine + lastOutput.ToString()); } if (computer.EndedCorrectly) { stillRunning = false; } } this.txtAnswer.Text = lastOutput.ToString(); watch.Stop(); Int64 elapsedMs = watch.ElapsedMilliseconds; label1.Text = elapsedMs.ToString(); } } }

AnvÀndningen av intcodeklassen

using System; using System.Collections.Generic; namespace AdventOfCode2019 { public class IntCode { private bool endedCorrectly = false; public bool EndedCorrectly { get { return endedCorrectly; } } private int rBase = 0; public bool isInitialized = false; int currentPosition = 0; int inputstep = 0; private string _program; private Dictionary<OpCode, int> parameterCount = new Dictionary<OpCode, int>(); private Dictionary<int, long> _outputs = new Dictionary<int, long>(); private Dictionary<long, long> _data = new Dictionary<long, long>(); private Dictionary<int,long> _inputs = new Dictionary<int, long>(); public void wdata(long address,long value) { if (!_data.ContainsKey(address)) { _data.Add(address, value); } else { _data[address] = value; } } public long data(long address) { if (!_data.ContainsKey(address)) { _data.Add(address, 0); } return _data[address]; } public enum OpCode { Add=1, Mul=2, In=3, Out=4, JiT=5, JiF=6, Les=7, Eq=8, RB=9, End=99 } public enum ParamMode { Ref=0, Val=1, RBRef=2 } public void AddInput(long input) { int nextInpPos = _inputs.Count; _inputs.Add(nextInpPos, input); } public IntCode(string program, long? input=null) { _program = program; if (input!=null) { AddInput((int)input); } Initialize(); } public IntCode() { } public void Init(string program, long[] inputs = null) { _program = program; if (inputs != null) { foreach (long item in inputs) { AddInput(item); } } Initialize(); } private void Initialize() { parameterCount.Clear(); parameterCount.Add(OpCode.Add, 3); parameterCount.Add(OpCode.Mul, 3); parameterCount.Add(OpCode.In, 1); parameterCount.Add(OpCode.Out, 1); parameterCount.Add(OpCode.JiT, 2); parameterCount.Add(OpCode.JiF, 2); parameterCount.Add((OpCode.Les), 3); parameterCount.Add(OpCode.Eq, 3); parameterCount.Add(OpCode.RB, 1); parameterCount.Add(OpCode.End, 0); //data = GetSafeIntArray(_program); //data = GetSafeLongArray(_program); _data = GetSafeLongDictionary(_program); isInitialized = true; } private static int[] GetSafeIntArray(string input) { string[] strArr = input.Split(','); int[] intArr = new int[strArr.Length]; for (int i = 0; i < strArr.Length; i++) { intArr[i] = ToSafeInt(strArr[i]); } return intArr; } private static long[] GetSafeLongArray(string input) { string[] strArr = input.Split(','); long[] intArr = new long[strArr.Length]; for (int i = 0; i < strArr.Length; i++) { //intArr[i] = ToSafeInt(strArr[i]); intArr[i] = ToSafeLong(strArr[i]); } return intArr; } private static Dictionary<long,long> GetSafeLongDictionary(string input) { Dictionary<long, long> tempdict = new Dictionary<long, long>(); string[] strArr = input.Split(','); long[] intArr = new long[strArr.Length]; for (int i = 0; i < strArr.Length; i++) { tempdict.Add(i, ToSafeLong(strArr[i])); } return tempdict; } private static int ToSafeInt(string val, int error = -1) { int test; bool isint = int.TryParse(val, out test); if (isint) { return test; } return error; } private static long ToSafeLong(string val, long error = -1) { long test; bool islong = long.TryParse(val, out test); if (islong) { return test; } return error; } public static ParamMode[] getParameterModes(string modes) { ParamMode[] pModes = new ParamMode[modes.Length]; for (int i = 0; i < modes.Length; i++) { pModes[modes.Length - i - 1] = (ParamMode)ToSafeInt(modes.Substring(i, 1)); } return pModes; } public long? Compute() { if (!isInitialized) { throw new Exception("Computer is not initialized!"); } long? lastOutPut = null; //int posCount = data.Length; bool noExit = true; //string lastOutPut = String.Empty; int outputstep = 0; _outputs.Clear(); while (noExit) { string posCode = data(currentPosition).ToString("D5"); OpCode opCode = (OpCode)ToSafeInt(posCode.Substring(3, 2)); ParamMode[] parameterMode = getParameterModes(posCode.Substring(0, 3)); int paramCount = parameterCount[opCode]; if (opCode==OpCode.End) { endedCorrectly = true; noExit = false; return null; } if (posCode=="00203") { outputstep = outputstep; } long[] parameters=new long[paramCount]; long[] values = new long[paramCount]; long[] waddress = new long[paramCount]; for (int i = 0; i < paramCount; i++) { parameters[i] = data(currentPosition + 1 + i); switch (parameterMode[i]) { case ParamMode.Ref: values[i] = data(parameters[i]); waddress[i]= parameters[i]; break; case ParamMode.Val: values[i] = parameters[i]; waddress[i] = parameters[i]; break; case ParamMode.RBRef: values[i] = data(rBase+ parameters[i]); waddress[i] = parameters[i] + rBase; break; default: break; } } switch (opCode) { case OpCode.Add: wdata(waddress[2],values[0] + values[1]); //data[parameters[2]] = values[0] + values[1]; currentPosition = currentPosition + 1 + paramCount; break; case OpCode.Mul: wdata(waddress[2], values[0] * values[1]); //data[parameters[2]] = values[0] * values[1]; currentPosition = currentPosition + 1 + paramCount; break; case OpCode.In: wdata(waddress[0], _inputs[inputstep]); //data[parameters[0]] = _inputs[inputstep]; inputstep++; currentPosition = currentPosition + 1 + paramCount; break; case OpCode.Out: _outputs.Add(outputstep, values[0]); outputstep++; currentPosition = currentPosition + 1 + paramCount; return values[0]; case OpCode.JiT: if (values[0]!=0) { currentPosition = (int)values[1]; } else { currentPosition = currentPosition + 1 + paramCount; } break; case OpCode.JiF: if (values[0] == 0) { currentPosition = (int)values[1]; } else { currentPosition = currentPosition + 1 + paramCount; } break; case OpCode.Les: if (values[0]<values[1]) { //data[parameters[2]] = 1; wdata(waddress[2],1); } else { wdata(waddress[2], 0); //data[parameters[2]] = 0; } currentPosition = currentPosition + 1 + paramCount; break; case OpCode.Eq: if (values[0] == values[1]) { wdata(waddress[2],1); //data[parameters[2]] = 1; } else { wdata(waddress[2], 0); //data[parameters[2]] = 0; } currentPosition = currentPosition + 1 + paramCount; break; case OpCode.RB: rBase = rBase + (int)values[0]; currentPosition = currentPosition + 1 + paramCount; break; case OpCode.End: endedCorrectly = true; noExit = false; currentPosition = currentPosition + 1; break; default: break; } if (!nextIsValid(data(currentPosition))) { throw new Exception("Hur kom vi hit?"); } } return null; } private bool nextIsValid(long nextInstruction) { string posCode = data(currentPosition).ToString("D5"); OpCode opCode = (OpCode)ToSafeInt(posCode.Substring(3, 2)); return parameterCount.ContainsKey(opCode); } } }

IntCode-klassen
PermalÀnk
Medlem ★
●

@Mordekai: Skriver BOOST(1) ut mer Àn ett vÀrde sÄ Àr det den OP-kod som ger felaktigt resultat som skrivs ut.

Min mode-funktion sedan tidigare returnerade vÀrdet som mode-indexerades,
(t.ex return p[p[i+1]] eller return p[i+1] (mitt program Àr i siffror i en array / lista))
men i.o.m mode2 sÄ mÄste man ocksÄ kunna tilldela ett vÀrde med mode-indexering,
jag hackade lite fult in relativt index vid alla tilldelningar allteftersom BOOST klagade...

Detta gick inte fel för mode0 / mode1; för t.ex input Àr det Àr vÀl bara p[p[i+1]] = x som Àr vettigt?

Tips om felet jag och Mordekai hade
PermalÀnk
Datavetare ★
●

Rust - dag 9

MÄlet för mig med AoC2019 Àr lÄngt mer att fÄ lite övning i Rust-programmering Àn att lösa uppgifterna. Gjorde dÀrför nu en rejÀl refactor pÄ dag 5, 7 och 9 sÄ alla kan lösas med samma intcode implementation. AnvÀnder trÄdar och kanaler som @Bryal tipsade om hÀr.

Löste "stora minnet" som jag misstÀnker de flesta andra ocksÄ gjort: anvÀnd en associativ array frÄn "minnescell" till vÀrdet i den cellen.

Postar bara intcode.rs, ett fungerande projekt finns hÀr

use AddressMode::*; use Instruction::*; use num_derive::FromPrimitive; use num_traits::FromPrimitive; use num_traits::pow; use std::collections::HashMap; use std::sync::mpsc::*; use std::thread; pub type Intcode = i64; #[derive(Debug, FromPrimitive, PartialEq)] enum AddressMode { Position = 0, Immediate = 1, Relative = 2, } #[derive(Debug, FromPrimitive, PartialEq)] enum Instruction { Add = 1, Mul = 2, In = 3, Out = 4, JmpIfTrue = 5, JmpIfFalse = 6, LessThan = 7, Equals = 8, AdjustBase = 9, Halt = 99, } fn to_mode(opcode: Intcode, position: Intcode) -> AddressMode { FromPrimitive::from_i32(opcode as i32 / pow(10, (position + 1) as usize) % 10).expect("Invalid mode") } fn to_instr(opcode: Intcode) -> Instruction { FromPrimitive::from_i32(opcode as i32 % 100).expect("Invalid instruction") } fn get(mem: &HashMap<Intcode, Intcode>, addr: Intcode) -> Intcode { *mem.get(&addr).unwrap_or(&0) } fn run(mem: &mut HashMap<Intcode, Intcode>, input: Receiver<Intcode>, output: Sender<Intcode>) { let mut ip: Intcode = 0; let mut relative_base: Intcode = 0; loop { let mut deferred_st = None; { let opcode = get(mem, ip); let ld = |offset| { let val = get(mem, ip + offset); match to_mode(opcode, offset) { Position => get(mem, val), Immediate => val, Relative => get(mem, relative_base + val), } }; let st = |offset, val| { let imm = get(mem, ip + offset); match to_mode(opcode, offset) { Position => Some((val, imm)), Immediate => panic!("Invalid store mode"), Relative => Some((val, relative_base + imm)), } }; let mut binop = |op: &dyn Fn(Intcode, Intcode) -> Intcode| { deferred_st = st(3, op(ld(1), ld(2))); ip + 4 }; let jmp_if = |pred: &dyn Fn(Intcode) -> bool| { if pred(ld(1)) { ld(2) } else { ip + 3 } }; ip = match to_instr(opcode) { Add => binop(&|a, b| a + b), Mul => binop(&|a, b| a * b), In => { deferred_st = st(1, input.recv().unwrap()); ip + 2 } Out => { output.send(ld(1)).unwrap(); ip + 2 } JmpIfTrue => jmp_if(&|val| val != 0), JmpIfFalse => jmp_if(&|val| val == 0), LessThan => binop(&|a, b| if a < b { 1 } else { 0 }), Equals => binop(&|a, b| if a == b { 1 } else { 0 }), AdjustBase => { relative_base = relative_base + ld(1); ip + 2 } Halt => break, } } // All immutable borrows must go out of scope before it is OK to store // to 'mem', so this kind of simulates "write-back" step in a CPU... if let Some((val, addr)) = deferred_st { mem.insert(addr, val); } } } pub fn exec( program: &Vec<Intcode>, input: Receiver<Intcode>, boot_output: Option<Intcode>, ) -> Receiver<Intcode> { let (tx, output) = channel(); if let Some(bo) = boot_output { tx.send(bo).unwrap() } let mut memory = HashMap::new(); for (addr, &val) in program.iter().enumerate() { memory.insert(addr as Intcode, val); } thread::spawn(move || { run(&mut memory, input, tx); }); output }

Varningen om att det skulle kunna ta lÄng tid gÀller dÄ inte Rust, trots att det nu kördes pÄ en fyra Är gammal laptop med i7-5600U. Tog totalt 48 ms att lösa bÄda dag 9 uppgifterna
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:

MÄlet för mig med AoC2019 Àr lÄngt mer att fÄ lite övning i Rust-programmering Àn att lösa uppgifterna. Gjorde dÀrför nu en rejÀl refactor pÄ dag 5, 7 och 9 sÄ alla kan lösas med samma intcode implementation. AnvÀnder trÄdar och kanaler som @Bryal tipsade om hÀr.

Löste "stora minnet" som jag misstÀnker de flesta andra ocksÄ gjort: anvÀnd en associativ array frÄn "minnescell" till vÀrdet i den cellen.

Postar bara intcode.rs, ett fungerande projekt finns hÀr

use AddressMode::*; use Instruction::*; use num_derive::FromPrimitive; use num_traits::FromPrimitive; use num_traits::pow; use std::collections::HashMap; use std::sync::mpsc::*; use std::thread; pub type Intcode = i64; #[derive(Debug, FromPrimitive, PartialEq)] enum AddressMode { Position = 0, Immediate = 1, Relative = 2, } #[derive(Debug, FromPrimitive, PartialEq)] enum Instruction { Add = 1, Mul = 2, In = 3, Out = 4, JmpIfTrue = 5, JmpIfFalse = 6, LessThan = 7, Equals = 8, AdjustBase = 9, Halt = 99, } fn to_mode(opcode: Intcode, position: Intcode) -> AddressMode { FromPrimitive::from_i32(opcode as i32 / pow(10, (position + 1) as usize) % 10).expect("Invalid mode") } fn to_instr(opcode: Intcode) -> Instruction { FromPrimitive::from_i32(opcode as i32 % 100).expect("Invalid instruction") } fn get(mem: &HashMap<Intcode, Intcode>, addr: Intcode) -> Intcode { *mem.get(&addr).unwrap_or(&0) } fn run(mem: &mut HashMap<Intcode, Intcode>, input: Receiver<Intcode>, output: Sender<Intcode>) { let mut ip: Intcode = 0; let mut relative_base: Intcode = 0; loop { let mut deferred_st = None; { let opcode = get(mem, ip); let ld = |offset| { let val = get(mem, ip + offset); match to_mode(opcode, offset) { Position => get(mem, val), Immediate => val, Relative => get(mem, relative_base + val), } }; let st = |offset, val| { let imm = get(mem, ip + offset); match to_mode(opcode, offset) { Position => Some((val, imm)), Immediate => panic!("Invalid store mode"), Relative => Some((val, relative_base + imm)), } }; let mut binop = |op: &dyn Fn(Intcode, Intcode) -> Intcode| { deferred_st = st(3, op(ld(1), ld(2))); ip + 4 }; let jmp_if = |pred: &dyn Fn(Intcode) -> bool| { if pred(ld(1)) { ld(2) } else { ip + 3 } }; ip = match to_instr(opcode) { Add => binop(&|a, b| a + b), Mul => binop(&|a, b| a * b), In => { deferred_st = st(1, input.recv().unwrap()); ip + 2 } Out => { output.send(ld(1)).unwrap(); ip + 2 } JmpIfTrue => jmp_if(&|val| val != 0), JmpIfFalse => jmp_if(&|val| val == 0), LessThan => binop(&|a, b| if a < b { 1 } else { 0 }), Equals => binop(&|a, b| if a == b { 1 } else { 0 }), AdjustBase => { relative_base = relative_base + ld(1); ip + 2 } Halt => break, } } // All immutable borrows must go out of scope before it is OK to store // to 'mem', so this kind of simulates "write-back" step in a CPU... if let Some((val, addr)) = deferred_st { mem.insert(addr, val); } } } pub fn exec( program: &Vec<Intcode>, input: Receiver<Intcode>, boot_output: Option<Intcode>, ) -> Receiver<Intcode> { let (tx, output) = channel(); if let Some(bo) = boot_output { tx.send(bo).unwrap() } let mut memory = HashMap::new(); for (addr, &val) in program.iter().enumerate() { memory.insert(addr as Intcode, val); } thread::spawn(move || { run(&mut memory, input, tx); }); output }

Varningen om att det skulle kunna ta lÄng tid gÀller dÄ inte Rust, trots att det nu kördes pÄ en fyra Är gammal laptop med i7-5600U. Tog totalt 48 ms att lösa bÄda dag 9 uppgifterna

Ja, har ocksÄ skrivit min IntCode för bakÄtkompatibilitet men nu vÄgar jag inte prova lÀngre..
Min uppgift 1 tog 1ms medans uppgift 2 tog 420ms

PermalÀnk
Datavetare ★
●
Skrivet av pacc:

Detta gick inte fel för mode0 / mode1; för t.ex input Àr det Àr vÀl bara p[p[i+1]] = x som Àr vettigt?

Det verkar vara tvÄ fall dÀr input instruktionen anvÀnder relativ adressering (mode=2), sÄ rÀcker inte med att enbart hantera mode=0. mode=1 Àr dÀremot aldrig tillÄtet för nÄgot som skriver till minnet.

@Mordekai: Tips om det strular Àr att skriva testfall för informationen man fÄr i uppgiften

"Here are some example programs that use these features:

  1. 109,1,204,-1,1001,100,1,100,1008,100,16,101,1006,101,0,99 takes no input and produces a copy of itself as output.

  2. 1102,34915192,34915192,7,4,7,99,0 should output a 16-digit number.

  3. 104,1125899906842624,99 should output the large number in the middle.

"

Det översatte jag till bl.a. detta, d.v.s. sÀtt programmet till vektorn och kolla att output blir det stora vÀrdet.

#[test] fn d9_ex3() { let program = vec![104, 1125899906842624, 99]; let (_, sink) = channel(); let output = exec(&program, sink, None); assert_eq!(1125899906842624, output.recv().unwrap()); }

Visa signatur

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

PermalÀnk
●

Dag 9 i Kotlin

Jag kan hÄlla med alla föregÄende talare att man Àr rÀtt mÀtt pÄ intcode nu. TrÄkigt nÀr alla exempel fungerar perfekt pÄ direkten riktiga problemet fungerade inte alls. Satt nog en halvtimme i debug-lÀge och stegade igenom alla operationer för att förstÄ vad dom var ute efter skulle hÀnda...

class Computer(private val program: MutableMap<Long, Long>) { val input = mutableListOf<Long>() var position = 0L var relativeBase = 0L fun addInput(value: Long): Computer { input.add(value) return this } fun getFullOutput(): List<Long> { val value = getOutput() return if (value == null) listOf() else listOf(value) + getFullOutput() } fun getOutput(): Long? = execute() private fun getParam(mode: Long, offset: Long): Long = when (mode) { 0L -> program.getOrDefault(program.getOrDefault(position + offset, 0), 0) 1L -> program.getOrDefault(position + offset, 0) 2L -> program.getOrDefault(program.getOrDefault(position + offset, 0) + relativeBase, 0) else -> throw IllegalStateException() } private tailrec fun execute(): Long? { val instruction = program[position]!! val operation = instruction % 100 val paramMode1 = instruction / 100 % 10 val paramMode2 = instruction / 1000 % 10 val paramMode3 = instruction / 10000 % 10 return when (operation) { 1L, 2L -> { val param1 = getParam(paramMode1, 1) val param2 = getParam(paramMode2, 2) val value = if (operation == 1L) param1 + param2 else param1 * param2 when (paramMode3) { 0L -> program[program[position + 3]!!] = value 2L -> program[program[position + 3]!! + relativeBase] = value else -> throw IllegalArgumentException("") } position += 4 execute() } 3L -> { val value = input.removeAt(0) when (paramMode1) { 0L -> program[program[position + 1]!!] = value 2L -> program[program[position + 1]!! + relativeBase] = value else -> throw IllegalArgumentException("") } position += 2 execute() } 4L -> { val value = getParam(paramMode1, 1) position += 2 value } 5L, 6L -> { val param1 = getParam(paramMode1, 1) val param2 = getParam(paramMode2, 2) position = if ((operation == 5L && param1 != 0L) || (operation == 6L && param1 == 0L)) param2 else position + 3 execute() } 7L, 8L -> { val param1 = getParam(paramMode1, 1) val param2 = getParam(paramMode2, 2) val value = if ((operation == 7L && param1 < param2) || (operation == 8L && param1 == param2)) 1L else 0L when (paramMode3) { 0L -> program[program[position + 3]!!] = value 2L -> program[program[position + 3]!! + relativeBase] = value else -> throw IllegalStateException() } position += 4 execute() } 9L -> { val param1 = getParam(paramMode1, 1) relativeBase += param1 position += 2 execute() } 99L -> null else -> throw IllegalStateException() } } }

Dold text
Visa signatur

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

PermalÀnk
Medlem ★
●

Dag 9. Nu börjar intcode kunna sĂ„ mycket sĂ„ det till och med blir svĂ„rt att skriva riktigt kort kod i Python. Över 40 rader, suck...

import operator program = [1102, 34463338, 34463338, ..., 109, -3, 2105, 1, 0] op = [None, operator.add, operator.mul, None, None, None, None, operator.lt, operator.eq] def intcode(p, indata): pc, rb, m = 0, [0], list(p) + [0] * 100000 def index(i, x): return [lambda: m[pc + i], lambda: pc + i, lambda: rb[0] + m[pc + i]][x]() def args(): x = m[pc] // 100 return m[index(1, x % 10)], m[index(2, x // 10 % 10)], index(3, x // 100) def binop(pc): a1, a2, i3 = args() m[i3] = op[m[pc] % 100](a1, a2) return pc + 4 def input(pc): m[(m[pc] // 100 == 2) * rb[0] + m[pc + 1]] = indata.pop(0) return pc + 2 def output(pc): print(args()[0]) return pc + 2 def condjump(pc): a1, a2, _ = args() return a2 if a1 == (m[pc] % 100 == 5) else pc + 3 def adjust(pc): rb[0] += args()[0] return pc + 2 instr = [None, binop, binop, input, output, condjump, condjump, binop, binop, adjust] while m[pc] != 99: pc = instr[m[pc] % 100](pc) intcode(program, [1]) intcode(program, [2])

Dold text
PermalÀnk
Medlem ★
●

Dag 10
Uppgift 1&2
SprÄk C#

private void button10_Click(object sender, EventArgs e) { string[] lines = GetLinesArr(this.txtInput.Text); List<Asteroid> asteroids = new List<Asteroid>(); for (int y = 0; y < lines.Length; y++) { for (int x = 0; x < Regex.Replace(lines[y], "[^.#]", "").Length; x++) { if (Regex.Replace(lines[y], "[^.#]", "").Substring(x,1)=="#") { asteroids.Add(new Asteroid(x, y)); } } } int maxVisible = 0; Asteroid bestAsteroid=null; foreach (Asteroid curAsteroid in asteroids) { int counted = asteroids.Select(a => a.AngleRad(curAsteroid)).Distinct().Count() - 1; if (counted>maxVisible) { maxVisible = counted; bestAsteroid = curAsteroid; } } if (bestAsteroid!=null) { if (this.numSubTask.Value==1) { this.txtAnswer.Text = maxVisible.ToString(); } else { this.txtDebug.AppendText(System.Environment.NewLine + "Station = " + bestAsteroid.ToString()); asteroids.Remove(bestAsteroid); foreach (Asteroid item in asteroids) { item.origoAngle = bestAsteroid.AngleDeg(item); item.origoDistance = bestAsteroid.Distance(item); } List<double> angles = asteroids.Select(a => a.origoAngle).Distinct().ToList(); angles.Sort(); double[] aarr = angles.ToArray(); int eliminatedAt = 1; int apos = 0; while (eliminatedAt<asteroids.Count) { if (asteroids.Where(a => (a.EliminatedAt == 0) && (a.origoAngle == aarr[apos])).OrderBy(ar => ar.origoDistance).ToList().Count > 0) { asteroids.Where(a => (a.EliminatedAt == 0) && (a.origoAngle == aarr[apos])).OrderBy(ar => ar.origoDistance).First().EliminatedAt = eliminatedAt; } apos++; if (apos>(aarr.Length-1)) { apos = 0; } eliminatedAt++; } Asteroid twohundred = asteroids.Where(a => a.EliminatedAt == 200).FirstOrDefault(); this.txtAnswer.Text=(twohundred.x*100+twohundred.y).ToString(); } } }

Main

public class Asteroid { public int x { get; } public int y { get; } public double origoAngle { get; set; } public double origoDistance { get; set; } public int EliminatedAt { get; set; } public Asteroid(int _x, int _y) { x = _x; y = _y; } public double AngleRad(Asteroid other) { if (this.Equals(other)) { return -999; } return Math.Atan2(other.y - y, other.x - x); } public double AngleDeg(Asteroid other) { if (this.Equals(other)) { return -999; } return (450+Math.Atan2(other.y - y, other.x - x)*180/Math.PI) % 360; } public double Distance(Asteroid other) { double part1 = (other.y - y); double part2 = (other.x - x); double test = Math.Sqrt(part1*part1 + part2*part2); return test; } public override string ToString() { return x.ToString() + ":" + y.ToString(); } }

HjÀlpklass
PermalÀnk
Medlem ★
●

@Mordekai: Duktigt

Lookup-tabell för alla punkter mellan tvÄ andra (positiva koordinater)
Den pythoniska lösningen gör min hemska 25-raders funktion till en oneliner....

Ta alla asteroider och ge varsin en lista med alla andra koordinater, ta sedan bort de som vid ett uppslag har en asteroid emellan.

Hitta asteroiden med störst lista, sortera den med en vinkelfunktion för att kunna fÄ svaret pÄ uppgift 2.

import math # lookup table for all intermediates def intermediates(xsize, ysize): inter = {} for x in range(2,xsize+1, 1): inter[x,0] = [] for xx in range(1,x): inter[x,0].append((xx,0)) for y in range(2,ysize+1, 1): inter[0,y] = [] for yy in range(1,y): inter[0,y].append((0,yy)) for x in range(1,(xsize + 1)/2): for y in range(1,(ysize + 1)/2): l = [(x,y)] i = 2 while x*i <= xsize and y*i <= ysize: if not (x*i, y*i) in inter: inter[(x*i, y*i)] = [] for e in l: if not e in inter[(x*i, y*i)]: inter[(x*i, y*i)].append(e) l.append((x*i,y*i)) i += 1 return inter def angle(a): return -math.atan2( a[0] - maxa[0], a[1] - maxa[1]) F = open("10.in.py", "r") l = F.readline() maps = [] x = 0 while l: maps.append(list(l[:-1])) l = F.readline() x += 1 ylen = len(maps[0]) xlen = len(maps) asteroids = {} for x in range(len(maps[0])): for y in range(len(maps)): if maps[y][x] == '#': asteroids[(x,y)] = [] #all possible links for a in asteroids: for b in asteroids: asteroids[a].append(b) asteroids[a].remove(a) inter = intermediates(xlen, ylen) for a in asteroids: removelist = [] for b in asteroids[a]: if (a[0] <= b[0]): xdist = b[0] - a[0] ydist = b[1] - a[1] ysign = 1 if (ydist < 0): ydist = -ydist ysign = -1 if (xdist, ydist) in inter: for i in inter[(xdist, ydist)]: if maps[a[1] + i[1]*ysign][a[0] + i[0]] == '#': # found asteroid between a,b - remove links removelist.append(b) for b in removelist: if b in asteroids[a]: asteroids[a].remove(b) asteroids[b].remove(a) maxn = 0 maxa = (-1,-1) for a in asteroids: if len(asteroids[a]) > maxn: maxn = len(asteroids[a]) maxa = a print maxa , " , ", maxn asteroids[maxa].sort(key=angle) print asteroids[maxa][199] maps[maxa[1]][maxa[0]] = 'O' for a in asteroids[(maxa)]: if maps[a[1]][a[0]] == '.': maps[a[1]][a[0]] = '*' if maps[a[1]][a[0]] == '#': maps[a[1]][a[0]] = 'o' for m in maps: print ''.join(m)

Dold text
PermalÀnk
Medlem
●

Dag: 10
SprÄk: Haskell

Ja, denna var allt lite lurigare Àn att leka med Intcode-maskinen. Lade lite vÀl mycket tid pÄ att fÄ pointsOnLine korrekt, speciellt med tanke pÄ att det fanns en mycket simplare lösning som @Mordekai hittade...

module Day10 (part1, part2) where import Data.Set (Set) import qualified Data.Set as Set import Control.Applicative import Data.Maybe import Data.List import Data.Functor import Lib type Point = (Int, Int) type Asteroid = Point part1 :: IO Int part1 = fmap (snd . findBestLoc . parse) readInput part2 :: IO Int part2 = readInput <&> \s -> let as = parse s (p, _) = findBestLoc as -- They start counting from 1st, we start from 0th (x, y) = nthDestroyed 199 as p in (x * 100 + y) findBestLoc :: Set Asteroid -> (Point, Int) findBestLoc as = let countVisible = Set.size . detect as in maximumOn snd (map (\p -> (p, countVisible p)) (Set.toList as)) nthDestroyed :: Int -> Set Asteroid -> Point -> Asteroid nthDestroyed n as p@(x0, y0) = let ds = detect as p n' = n - Set.size ds angle (x1, y1) = let (dx, dy) = (x1 - x0, y1 - y0) in (pi - atan2 (fromIntegral dx) (fromIntegral dy)) :: Double in if n' <= 0 then sortOn angle (Set.toList ds) !! n else nthDestroyed n' (Set.difference as ds) p detect :: Set Asteroid -> Point -> Set Asteroid detect as p = let closestBetween q = listToMaybe (filter (flip Set.member as) (pointsOnLine p q)) in Set.fromList (catMaybes (map closestBetween (Set.toList as))) pointsOnLine :: Point -> Point -> [Point] pointsOnLine (x0, y0) (x1, y1) = let dx' = x1 - x0 (dx, sx) = (abs dx', signum dx') dy = y1 - y0 xs = filter (\x -> mod (x * dy) dx == 0) [1 .. dx] y x = div (x * dy) dx in if dx == 0 then map (\y' -> (x0, y0 + signum dy * y')) [1 .. abs dy] else map (\x -> (x0 + sx * x, y0 + y x)) xs parse :: String -> Set Asteroid parse s = Set.fromList $ do (l, y) <- zip (lines s) [0 ..] (c, x) <- zip l [0 ..] if c == '#' then pure (x, y) else empty readInput :: IO String readInput = readFile "inputs/day-10"

Dold text
Visa signatur

Arbets- / Spelstation: Arch Linux - Ryzen 5 3600 - RX 7900 XT - 32G DDR4
Server: Arch Linux - Core i5-10400F - 16G DDR4

PermalÀnk
Medlem ★
●

VÀrt att nÀmna Àr att jag som 11-Äring hade löst denna betydligt snabbare, det enda jag gjorde hela dagarna, kvÀllarna, nÀtterna var att rita olika cirkelbaserade mönster mha cosinus och sinus. Mandelbrot kunde jag liksom inte förstÄ hur jag skulle fÄ som jag ville, grejer som var poppis i början pÄ Ättitalet. Det var pÄ en Sinclair Spectrum 48k, i Basic och Forth.