Följ Black Week pÄ SweClockers

🌟 Advent of Code (AoC) 2020 🌟

PermalÀnk
●

Kom igÄng lite sent. Ville prova köra i Rust för att öva lite. Avslutade precis dag 4, kÀndes lite enformig.

Dag: 1-4
SprÄk: Rust
Lösning: Github

PermalÀnk
Medlem ★
●

Dag: 9
SprÄk: VB.Net

Fick brÄka med nÄgra Off-by-one-fel innan bitarna föll pÄ plats.

Imports System.IO Module Program Sub Main(args As String()) Dim input As New List(Of Long) For Each line In File.ReadAllLines("input.txt") If Not String.IsNullOrWhiteSpace(line) Then input.Add(Long.Parse(line)) Next Dim partOne = input(FindInvalidIndex(25, input)) Dim partTwo = FindContiguous(FindInvalidIndex(25, input), input) Console.WriteLine("Part 1: " & partOne.ToString()) Console.WriteLine("Part 2: " & partTwo.ToString()) End Sub Function FindContiguous(index As Integer, input As List(Of Long)) As Long For i = 0 To index - 1 Dim sum As Integer = input(i) For j = i + 1 To index - 1 sum += input(j) If sum = input(index) Then Return input(i) + input(j) Next Next Return 0 End Function Function FindInvalidIndex(preamble As Integer, input As List(Of Long)) As Long For i = preamble To input.Count - 1 If Not isValid(preamble, input, i) Then Return i Next Return 0 End Function Function isValid(preamble As Integer, input As List(Of Long), indexToTest As Integer) For i = indexToTest - preamble To indexToTest - 1 For j = i + 1 To indexToTest - 1 If input(i) + input(j) = input(indexToTest) Then Return True Next Next Return False End Function End Module

Dold text

Skrivet av wgren:

Som Ruby programmerare (bland annat) sÄ mÄste jag sÀga att VB.Net Àr behagligt lÀsbart. NÀr man börjat vÀnja sig vid sprÄk som inte har brackets i olika former och semikolon överallt sÄ sticker dom i ögonen nÀr man kommer tillbaka till sprÄk (C och alla dess barn exvis) som krÀver dom.

Ja jag gillar den "pratiga" syntaxen i VB.
Å andra sidan kan det bli lite wall-of-text-kĂ€nsla över koden ibland och mycket knappande pĂ„ tangentbordet.

PermalÀnk
Medlem
●

Ville bara visa hur fula mina koder brukar vara nÀr jag lyckats fÄ rÀtt svar för första gÄngen - innan all tid jag lÀgger ned pÄ att förbÀttra koderna.

PermalÀnk
Medlem
●

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

PermalÀnk
Medlem
●

Dag: 9
SprÄk: Rust

use std::io; pub fn run<R>(input: R) where R: io::BufRead, { let data = input .lines() .filter_map(|s| s.ok()) .filter_map(|v| v.parse::<usize>().ok()) .collect::<Vec<_>>(); let answer = solve1(&data, 25).unwrap(); println!("Svar 1: {}", answer); // 41682220 println!("Svar 2: {}", solve2(&data, answer).unwrap()); // 5388976 } fn solve1(data: &[usize], preamble_length: usize) -> Option<usize> { let mut iter = data.iter().skip(preamble_length); let mut step = 0; let result = loop { let next = iter.next()?; if sum_exist(&data[step..preamble_length + step], *next).is_some() { step += 1; } else { break next; } }; Some(*result) } fn solve2(data: &[usize], answer_part1: usize) -> Option<usize> { let mut start = 0usize; let mut end = 1usize; let svar = loop { let sum = data[start..end].iter().sum::<usize>(); if sum == answer_part1 { break data[start..end].iter().min()? + data[start..end].iter().max()?; } else if sum < answer_part1 { end += 1; } else { start += 1; } }; Some(svar) } fn sum_exist(data: &[usize], value: usize) -> Option<usize> { data.iter() .map(|&a| data.iter().map(move |&b| a + b)) .flatten() .find(|&x| x == value) }

Dold text

Edit detaljer: Det gÄr i solve1 helt ersÀtta VecDeque och anvÀnda dataslicen för "fönstret".. Och sedan Àr Hashsetet lite onödigt. Det hade varit bÀttre att loopa och bryta direkt vid match.

Edit 2: Uppdaterade efter mina egna kommentarer

Visa signatur

AMD Ryzen 3700X, Gigabyte Elite X570, 32GB Ballistix Sport, NH-D15S, SAPPHIRE NITRO+ RX 7900 XTX, Corsair AX760, LG OLED C2 42"

PermalÀnk
●

Dag: 9
SprÄk: Haskell

import Data.Char import Data.List stringToInt :: [Char] -> Int stringToInt = foldl addDigit 0 where addDigit num d = 10*num + digitToInt d isSumOf :: Int -> [Int] -> Bool isSumOf _ [] = False isSumOf val (t:terms) = (val - t) `elem` terms || isSumOf val terms findFirstNonSum :: [Int] -> [Int] -> Int findFirstNonSum prev (curr:rest) | isSumOf curr prev = findFirstNonSum ((tail prev) ++ [curr]) rest | otherwise = curr findContinousSum :: Int -> [Int] -> Int findContinousSum num terms | csIdx > 0 = smallest + largest | otherwise = findContinousSum num (tail terms) where csIdx = isContinousSumOf num terms csSorted = sort $ take csIdx terms smallest = head csSorted largest = last csSorted isContinousSumOf :: Int -> [Int] -> Int isContinousSumOf val (t:terms) | val == t = 0 | (val - t > 0) = 1 + isContinousSumOf (val-t) terms | otherwise = (-val) main = do contents <- readFile "input.txt" let numbers = map stringToInt $ lines contents let preamble = take 25 numbers let xmas = drop 25 numbers let noSumNum = findFirstNonSum preamble xmas return (noSumNum, findContinousSum noSumNum numbers)

Dold text
PermalÀnk
Medlem ★
●

Dag 10, vÀldigt missnöjd idag,

trotts att jag var inne pÄ DP-spÄret igÄr sÄ hade jag total hjÀrnslÀpp och vÀgrade fÄ till det.

part1$ <in sort -n | awk '$1 - x == 1 { a += 1 } $1 - x == 3 { b += 1 } { x = $1 } END { print a * (b + 1) }' part2$ <in sort -n | awk '{ n[NR] = $1 } END { print ff(0, 1) } function ff(c, i) { if (c in s) { return s[c] } else { return s[c] = f(c, i) } } function f(c, i) { if (n[i] - c <= 3) { if (i == NR) { return 1 } return ff(n[i], i + 1) + ff(c, i + 1) } }'

Part 2 oneliner

<in sort -n | awk '{ n[NR] = $1 } END { print f(0, 1) } function f(c, i) { return c in s ? s[c] : s[c] = n[i] - c <= 3 ? i == NR ? 1 : f(n[i], i + 1) + f(c, i + 1) : 0 }'

Dold text
oneliner
Visa signatur

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

PermalÀnk
Datavetare ★
●

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

Trodde det hela skulle krÀva att man lyfter in "bignum" paket dÄ Swift saknar inbyggt stöd, men gissar att man anpassat problemet sÄ det fÄr plats i Int64 (fungerade för mig i alla fall).

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: 10
SprÄk: Nim
Lösning: GIthub

Part1 var busenkel med Part2 var en riktig kluring! Försökte mig pÄ en rekursiv variant och den hÄller fortfarande pÄ och körs NÀr man insÄg hur man skulle göra blev det "botten upp" sÄ att sÀga...

PermalÀnk
●
Skrivet av Yoshman:

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

Trodde det hela skulle krÀva att man lyfter in "bignum" paket dÄ Swift saknar inbyggt stöd, men gissar att man anpassat problemet sÄ det fÄr plats i Int64 (fungerade för mig i alla fall).

Jag blev ocksÄ lite orolig men vi hade gott om plats över, det största talet en int64 kan ha Àr 9223372036854775807 och vÄra svar var i runda slÀngar 40 000 gÄnger mindre Àn det

PermalÀnk
●

Dag: 10
SprÄk: Haskell

import Data.Char import Data.List import Data.Map (Map) import qualified Data.Map as Map stringToInt :: [Char] -> Int stringToInt = foldl addDigit 0 where addDigit num d = 10*num + digitToInt d adapterChain :: [Int] -> Int -> Int -> (Int,Int) adapterChain (a:[]) j1 j3 = (j1,j3+1) adapterChain (a:adapters) j1 j3 = case ((head adapters) - a) of (1) -> adapterChain adapters (j1+1) j3 (3) -> adapterChain adapters j1 (j3+1) (_) -> adapterChain adapters j1 j3 -- | iterate throgh list in reverse order, at each increment calculate possible arrangements using previous calculations adapterArrangements :: Map Int Int -> [Int] -> Int adapterArrangements m a | a == [] = get 0 m --end | Map.null m = adapterArrangements (Map.insert key 1 m) (init a) -- init map | otherwise = adapterArrangements (Map.insert key val m) (init a) -- incremental step where get :: Int -> Map Int Int -> Int get v m' = if Map.member v m' then m' Map.! v else 0 key = last a val = (get (key+1) m) + (get (key+2) m) + (get (key+3) m) main = do contents <- readFile "input.txt" let rows = lines contents let adapters = (0:(sort $ map stringToInt rows)) return ((\x -> (fst x) * (snd x)) $ adapterChain adapters 0 0, adapterArrangements Map.empty adapters)

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

Dag: 9
SprÄk: Go
Lösning: GitHub

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

Jag Àlskar frÄgor likt dagens! Del 1 var enkel och Del 2 var orimlig att klara med brute force.

Mitt första försök pÄ Del 2 var att generera alla möjliga kombinationer av index för min input, och sedan addera ihop dem, ett, i taget. Att först generera alla kombinationer och sedan börja rÀkna gjorde att programmet gjorde slut pÄ RAM redan i fjÀrde loopen. Att generera varje kombination "on the fly" fungerade, rent minnesmÀssigt, men efter ~5 minuter tÀnkte jag att det mÄste finnas ett bÀttre sÀtt.

Min slutliga lösning jobbar bara med index och rör sig sĂ„ sakteligen genom listan av möjliga inputs. Jag tror fortfarande att rad 44 och 45 Ă€r lite onödiga (det borde vara mer effektivt att hĂ„lla candidateSum utanför loopen och sen addera/subtrahera allt eftersom), men lösningen kör pĂ„ ~200ÎŒs, sĂ„ det fĂ„r duga.

EDIT:
En sak slog mig precis. Har jag bara tur som hade mitt contagious set pÄ rad? Exemplet pÄ hemsidan har ju ocksÄ det, men jag kan inte lÀsa mig fram till att sÄ alltid Àr fallet, i beskrivningen.

EDIT2:
Det Àr inte contagious, utan contiguous........ jag Àr inte lÀskunnig. Sorry. DÄ var ju mitt första försök (generera alla kombinationer) bara jÀttedumt.

Dold text

Dag: 10
SprÄk: Go
Lösning: GitHub

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

Idag var det svÄrt med del 2. OmgÄende tÀnkte jag att jag skulle anvÀnda memoization, men det var lÀngesedan jag sysslade med Dynamic Programming. Jag hade för mÄnga bollar i luften och tog inte en sak i taget. Tillslut fick jag ta nÄgra djupa andetag och tillsammans med Internet lyckades jag fÄ ihop en bra lösning.

Dold text
Visa signatur

:(){ :|:& };:

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

PermalÀnk
Medlem
●

Jahapp, uppgift 1 löste jag pÄ under 10 minuter och med en oneliner sÄ kÀnde mig vÀldigt mallig, men har kört fast helt pÄ uppgift 2, Àven efter att jag gav upp och tittade pÄ andras lösningar. Hilfe?

Edit: Never mind, hittade buggen.

Ger rÀtt pÄ exempelinput (exvis 19208), och Àr snabb. Men ger för högt vÀrde pÄ riktiga input enligt AoC. But why?

def paths(in: List[Int]) = { in.tails.filter(!_.isEmpty).foldLeft(Map[Int, BigInt](0 -> BigInt(1))) { case (map, head::tail) => { val validAdapters: List[Int] = tail.takeWhile((x) => x - head < 4) val currentPaths: BigInt = map.get(head).get validAdapters.foldLeft(map) { (nmap, elem) => nmap.updated(elem, currentPaths + nmap.get(elem).getOrElse(BigInt(0)) ) } } }.get(in.last) } // Uppgift 1 input.foldLeft((0,0,0)) { case ((last, ones, threes), x) => if (x-last == 3) (x, ones, threes+1) else if (x-last == 1) (x, ones + 1, threes) else (x, ones, threes) }

Felet: Jag hade gjort en import scala.collection.mutable._ i min REPL nÀr jag satt och labbade, sÄ nÄgonstans refererade jag till en mutable Map, eller det blev en implicit conversion eller nÄgot. Startade jag om min REPL och pastade koden ovan funkade det.

Dold text
Tails förklaring. Och nu Àven bugg förklaring.
PermalÀnk
Medlem ★
●

Dag 10 del 2 Àr första för mig som var lite klurig.

InsÄg ganska snart att min rekursiva funktion skulle ta lÀÀÀÀnge att slutföra.

Sen satte jag alla tal i grupper. Grupperna var inte nÀrmre Àn 3 frÄn nÀsta grupp. Sen löste jag varje grupp för sig i min rekursiva och gÄngrade ihop alla grupperna.

Det jag undrar Àr om sÄdana grupper ej vore möjlig hur hade man dÄ löst det?

Dold text
PermalÀnk
Medlem
●
Skrivet av Larrxi:

hur hade man dÄ löst det?

Kollegas förklaring pÄ hans eleganta lösning:

PermalÀnk
Medlem ★
●

Dag: 10
SprÄk: JavaScipt

Del ett var trivial, del tvÄ var det inte...

function calculate(list) { let one = 0; let three = 0; let part2Array = []; let tempArray = []; list.push(0); list.sort(function (a, b) { return a - b }); list.push(list[list.length - 1] + 3); for (let i = 1; i < list.length; i++) { tempArray.push(list[i - 1]); if (list[i] - list[i - 1] === 1) { one++; } else if (list[i] - list[i - 1] === 3) { three++; part2Array.push(tempArray); tempArray = []; } } console.log("Part 1: " + one * three); let res = 1; for (let i = 0; i < part2Array.length; i++) { res *= countAlternatives(part2Array[i]); } console.log("Part 2: " + res); } function countAlternatives(list) { if (list.length <= 1) { return 1; } let res = 0; for (let j = 1; j < 4; j++) { if ((list[j] - list[0]) <= 3) { res += countAlternatives(list.slice(j)); } else { break; } } return res; } async function fetchInput() { var response = await fetch('input.txt'); var text = await response.text(); const list = text.split("\n").map(function (x) { return parseInt(x, 10); }); calculate(list); } fetchInput();

Dold text

Skrivet av Larrxi:

Dag 10 del 2 Àr första för mig som var lite klurig.

InsÄg ganska snart att min rekursiva funktion skulle ta lÀÀÀÀnge att slutföra.

Sen satte jag alla tal i grupper. Grupperna var inte nÀrmre Àn 3 frÄn nÀsta grupp. Sen löste jag varje grupp för sig i min rekursiva och gÄngrade ihop alla grupperna.

Det jag undrar Àr om sÄdana grupper ej vore möjlig hur hade man dÄ löst det?

Dold text

Tack för tipset, var detta som tillslut gjorde att jag löste det. Hade snabbt skrivit ihop en rekursiv lösning som i teorin fungerar, men som nog hade behövt köra tills universum kallnat helt utan att fÄ fram ett svar.

Dold text
Skrivet av wgren:

Kollegas förklaring pÄ hans eleganta lösning:

Tack för lÀnken. Har tjuvkikat pÄ en del andra lösningar idag, och sett att de flesta anvÀnder nÄgon variant av denna. Att implementera den Àr trivialt, men jag förstÄr Àrligt talat fortfarande inte intuitivt hur och varför det fungerar....

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

Kollegas förklaring pÄ hans eleganta lösning:

Jag kom frÄn andra hÄllet;

pÄ hur mÄnga sÀtt kan jag nÄ slut-enheten frÄn joltage X? Sen "plus 1" eller inte frÄn nuvarande joltage för att nÄ X.

Dold text

@Yoshman har en mer udda lösning idag i mitt tycke .. undrar hur tanke-gÄngen gick dÀr. FörstÄr första steget men jag hade nog tÀnkt om inför andra frÄgan.

Visa signatur

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

PermalÀnk
Medlem ★
●

Dag 10, Python

from numpy import prod input = set(map(int, open("input","r"))) limit = max(input) + 3 s = [0] + sorted(input) + [limit] l = [s[i+1] - s[i] for i in range(len(input) - 1)] def combinations(j, l): if j == l[-1]: yield 1 else: for a in filter(lambda v: j+1 <= v <= j+3, l): yield from combinations(a, l) def split_on_3s(l): start = 0 for i in range(len(l) - 1): if l[i] + 3 == l[i+1]: yield l[start:i + 1] start = i + 1 yield l[start:] print(l.count(1) * l.count(3), prod([sum([x for x in combinations(l[0], l)]) for l in filter(lambda x:len(x) > 2, split_on_3s(s))]))

Dold text
PermalÀnk
Medlem
●
Skrivet av jaqob:

Tack för lÀnken. Har tjuvkikat pÄ en del andra lösningar idag, och sett att de flesta anvÀnder nÄgon variant av denna. Att implementera den Àr trivialt, men jag förstÄr Àrligt talat fortfarande inte intuitivt hur och varför det fungerar....

Dold text

Om du gÄr lÀngst en stig och vet att det finns tvÄ olika vÀgar att hitta till punkten du Àr nu. Du ser tre andra vÀgar framÄt, du gÄr till den första, dÀr har nÄgon skrivit "det finns 5 olika sÀtt att hitta hit" pÄ en lapp, du stryker 5 och skriver 7 istÀllet, och gör sÄ pÄ alla tre vÀgarna. Finns det ingen lapp pÄ nÄgon av dom resterande sÄ fÄr du skriva en ny med "finns 2 olika sÀtt" pÄ och lÀgga dit. NÀr du gÄtt genom alla vÀgar sÄ kollar du lappen i Rom (eftersom alla vÀgar leder till Rom) för att se alla möjliga vÀgar dit.

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

Jag kom frÄn andra hÄllet;

pÄ hur mÄnga sÀtt kan jag nÄ slut-enheten frÄn joltage X? Sen "plus 1" eller inte frÄn nuvarande joltage för att nÄ X.

Dold text

@Yoshman har en mer udda lösning idag i mitt tycke .. undrar hur tanke-gÄngen gick dÀr. FörstÄr första steget men jag hade nog tÀnkt om inför andra frÄgan.

TÀnkte att det mÄste ha nÄgot med att multiplicera antalet varianter man kan ordna serier av ökningar med 1 jolt. Faktoriserade 19208 (andra exemplet), funderade över vad som kan matcha de minsta faktorerna och insÄg att det Àr antalet sÀtt man kan ordna ...3,1,3... ...3,1,1,3... ...3,1,1,1,3 och 3,1,1,1,1,3. SÄ konverterade serien till en ny serier som listar hur mÄnga "1" man har i rad, sedan var det bara översÀtta det till antal kombinationer för varje lÀngd och multiplicera.

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 wgren:

Kollegas förklaring pÄ hans eleganta lösning:

Ja det dÀr var en fin lösning. Tack!

PermalÀnk
Medlem ★
●

Dag: 10
SprÄk: VB.Net

Edit: Ändrade till en for-loop istĂ€llet för while i del 2.

Imports System.IO Module Program Sub Main(args As String()) Dim adapters As New List(Of Integer) adapters.Add(0) For Each line In File.ReadAllLines("input.txt") If Not String.IsNullOrWhiteSpace(line) Then adapters.Add(Integer.Parse(line)) Next adapters.Sort() adapters.Add(adapters.Last() + 3) Console.WriteLine("Part One: " & PartOne(adapters).ToString()) Console.WriteLine("Part Two: " & PartTwo(adapters).ToString()) End Sub Function PartOne(adapters As List(Of Integer)) As Integer Dim ones As Integer = 0 Dim threes As Integer = 0 For i = 0 To adapters.Count - 2 If adapters(i + 1) - adapters(i) = 1 Then ones += 1 If adapters(i + 1) - adapters(i) = 3 Then threes += 1 Next Return ones * threes End Function Function PartTwo(adapters As List(Of Integer)) As Long Dim total As Long = 1 Dim counter As Integer = 1 For index = 0 To adapters.Count - 2 If adapters(index + 1) - adapters(index) = 1 Then counter += 1 Else If counter = 3 Then total *= 2 If counter = 4 Then total *= 4 If counter = 5 Then total *= 7 counter = 1 End If Next Return total End Function End Module

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

SÄ konverterade serien till en ny serier som listar hur mÄnga "1" man har i rad, sedan var det bara översÀtta det till antal kombinationer för varje lÀngd och multiplicera.

SÄ gjorde jag med! Jag ser att bÄde du och jag (och kanske alla?) max har 4 ettor i rad och dÀrför manuellt kunde rÀkna ut hur mÄnga variationer varje antal ettor ger och hÄrdkoda upp till 4. Det stör mig att jag inte lyckades hitta en generell lösning (X ettor i rad ger Y variationer).

PermalÀnk
Medlem
●
Skrivet av BigMomma:

Dag: 10
SprÄk: VB.Net

Imports System.IO Module Program Sub Main(args As String()) Dim adapters As New List(Of Integer) adapters.Add(0) For Each line In File.ReadAllLines("input.txt") If Not String.IsNullOrWhiteSpace(line) Then adapters.Add(Integer.Parse(line)) Next adapters.Sort() adapters.Add(adapters.Last() + 3) Console.WriteLine("Part One: " & PartOne(adapters).ToString()) Console.WriteLine("Part Two: " & PartTwo(adapters).ToString()) End Sub Function PartOne(adapters As List(Of Integer)) As Integer Dim ones As Integer = 0 Dim threes As Integer = 0 For i = 0 To adapters.Count - 2 If adapters(i + 1) - adapters(i) = 1 Then ones += 1 If adapters(i + 1) - adapters(i) = 3 Then threes += 1 Next Return ones * threes End Function Function PartTwo(adapters As List(Of Integer)) As Long Dim total As Long = 1 Dim index As Integer = 0 Dim counter As Integer = 1 While index < adapters.Count - 1 If adapters(index + 1) - adapters(index) = 1 Then counter += 1 Else If counter = 3 Then total *= 2 If counter = 4 Then total *= 4 If counter = 5 Then total *= 7 counter = 1 End If index += 1 End While Return total End Function End Module

Dold text

Har suttit ett bra tag med del 2, och jag mÄste sÀga att din lösning ser riktigt elegant ut. Kan du inte förklara logiken bakom, förstÄr inte trots att jag ser facit i din kod.

PermalÀnk
Medlem ★
●

Dag 10, Python, andra försöket

Jag hade pÄ kÀnn att man bara behövde titta pÄ differenserna Àven i uppgift tvÄ, men vill bli klar. Efter att ha kika pÄ Yoshmans lösning var de uppenbart att jag skulle kollat lite mer pÄ detta. Denna ful-lösning för uppgift tvÄ

  1. l innehÄller en lista med alla elementvisa differenser

  2. konverterar differenserna till en strÀng

  3. splittar den pÄ tecken nummer 3

  4. tar lÀngden pÄ alla kvarvarande strÀngar med ettor

  5. anvÀnder Counter för att rÀkna hur mÄnga strÀngar som finns av de olika lÀngderna

  6. kör en ful listuppslagning för att översÀtta till hur mÄnga lösningar den strÀnglÀngden genererar

  7. multiplicerar dessa

  8. multiplicerar alla produkter

from numpy import prod from collections import Counter input = set(map(int, open("input","r"))) s = [0] + sorted(input) + [max(input) + 3] l = [s[i+1] - s[i] for i in range(len(s) - 1)] print(l.count(1) * l.count(3), prod([prod([[1,1,2,4,7][k]] * v) for k,v in Counter(map(len,"".join(map(chr, l)).split(chr(3)))).items()]))

Dold text
PermalÀnk
Medlem ★
●
Skrivet av S-MAX:

Har suttit ett bra tag med del 2, och jag mÄste sÀga att din lösning ser riktigt elegant ut. Kan du inte förklara logiken bakom, förstÄr inte trots att jag ser facit i din kod.

Lösningen gÄr ut pÄ att hitta sekvenser av adaptrar med 1 jolt skillnad. För varje sÄdan sekvens rÀknar man ut hur mÄnga variationer som finns för den sekvensen, och multiplicerar detta med totalsumman.
De steg som ökar med 3 mÄste tas med i den ordningen de stÄr. De kan bara arrangeras pÄ ett sÀtt och kan ignoreras i utrÀkningen (eftersom berÀkningen skulle bli att multiplicera totalsumman med 1). I min lösning anvÀnds de stegen för att markera slutet pÄ en sekvens med 1 jolt-steg.

Loopen gÄr igenom alla adaptrar i listan och stegar upp en rÀknare nÀr skillnaden mot föregÄende adapter Àr 1 jolt.
NÀr ett steg inte Àr 1 jolt (det Àr alltid 1 eller 3 jolt) har vi nÄtt slutet pÄ en sekvens och kan berÀkna antalet möjliga variationer för den. Efter utrÀkningen ÄterstÀlls rÀknaren och börjar rÀkna pÄ nÀsta sekvens.

Om det ser ut sÄ hÀr i listan: 10, 13, 14, 15, 18
DÄ Àr 13, 14, 15 en sekvens av 1 jolt steg.

sekvenser med 1 eller 2 adaptrar kan bara arrangeras pÄ ett sÀtt och kan ignoreras.

Om det Àr 3 adaptrar i sekvensen kan de arrangeras pÄ tvÄ sÀtt.
10, 13, 14, 15, 18
10, 13, 15, 18

4 adaptrar kan arrangeras pÄ 4 olika sÀtt sÄ hÀr:
10, 13, 14, 15, 16, 19
10, 13, 14, 16, 19
10, 13, 15, 16, 19
10, 13, 16, 19

Och 5 adaptrar kan arrangeras pÄ 7 olika sÀtt.

Jag hade ingen sekvens med fler Àn 5 adaptrar i min input, sÄ jag har inte lagt till nÄgon kod för det.

Dold text
PermalÀnk
Medlem
●

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

Första gick för lÀtt, sÄ de var det givet att andra skulle vara svÄrare. Byggde en lösning som rÀknade rÀtt, men som krÀvde att samtliga resultat sparades i en map. NÀr testet tog över sekunden att köra var det bara inse att det aldrig skulle gÄ. Mot kvÀllen gav jag upp och lÄnade friskt av @Yoshman. Imponerande, denna lösning rÀknar allt pÄ 10”s.

package main import ( "bufio" "fmt" "os" "sort" "strconv" ) func getNumbers(rows []string) []int { numbers := []int{0} for _, row := range rows { value, _ := strconv.Atoi(row) numbers = append(numbers, value) } sort.Ints(numbers) numbers = append(numbers, numbers[len(numbers)-1]+3) return numbers } func getPartOne(numbers []int) int { diffs := map[int]int{} for i := 1; i < len(numbers); i++ { diff := numbers[i] - numbers[i-1] diffs[diff]++ } return diffs[1] * diffs[3] } func getPartTwo(numbers []int) int { oneMap := []int{1, 1, 2, 4, 7} oneCount := 0 result := 1 for i := 1; i < len(numbers); i++ { if numbers[i]-numbers[i-1] == 1 { oneCount++ } else { result *= oneMap[oneCount] oneCount = 0 } } return result } func getRows(filename string) []string { file, _ := os.Open(filename) defer file.Close() scanner := bufio.NewScanner(file) var rows []string for scanner.Scan() { rows = append(rows, scanner.Text()) } return rows } func main() { rows := getRows("../input.txt") fmt.Println("PartOne", getPartOne(getNumbers(rows))) fmt.Println("PartTwo", getPartTwo(getNumbers(rows))) }

Dold text
PermalÀnk
Medlem
●
Skrivet av BigMomma:

Lösningen gÄr ut pÄ att hitta sekvenser av adaptrar med 1 jolt skillnad. För varje sÄdan sekvens rÀknar man ut hur mÄnga variationer som finns för den sekvensen, och multiplicerar detta med totalsumman.
De steg som ökar med 3 mÄste tas med i den ordningen de stÄr. De kan bara arrangeras pÄ ett sÀtt och kan ignoreras i utrÀkningen (eftersom berÀkningen skulle bli att multiplicera totalsumman med 1). I min lösning anvÀnds de stegen för att markera slutet pÄ en sekvens med 1 jolt-steg.

Loopen gÄr igenom alla adaptrar i listan och stegar upp en rÀknare nÀr skillnaden mot föregÄende adapter Àr 1 jolt.
NÀr ett steg inte Àr 1 jolt (det Àr alltid 1 eller 3 jolt) har vi nÄtt slutet pÄ en sekvens och kan berÀkna antalet möjliga variationer för den. Efter utrÀkningen ÄterstÀlls rÀknaren och börjar rÀkna pÄ nÀsta sekvens.

Om det ser ut sÄ hÀr i listan: 10, 13, 14, 15, 18
DÄ Àr 13, 14, 15 en sekvens av 1 jolt steg.

sekvenser med 1 eller 2 adaptrar kan bara arrangeras pÄ ett sÀtt och kan ignoreras.

Om det Àr 3 adaptrar i sekvensen kan de arrangeras pÄ tvÄ sÀtt.
10, 13, 14, 15, 18
10, 13, 15, 18

4 adaptrar kan arrangeras pÄ 4 olika sÀtt sÄ hÀr:
10, 13, 14, 15, 16, 19
10, 13, 14, 16, 19
10, 13, 15, 16, 19
10, 13, 16, 19

Och 5 adaptrar kan arrangeras pÄ 7 olika sÀtt.

Jag hade ingen sekvens med fler Àn 5 adaptrar i min input, sÄ jag har inte lagt till nÄgon kod för det.

Dold text

Tack, grymt bra förklarat!

PermalÀnk
Datavetare ★
●
Skrivet av lydell:

SÄ gjorde jag med! Jag ser att bÄde du och jag (och kanske alla?) max har 4 ettor i rad och dÀrför manuellt kunde rÀkna ut hur mÄnga variationer varje antal ettor ger och hÄrdkoda upp till 4. Det stör mig att jag inte lyckades hitta en generell lösning (X ettor i rad ger Y variationer).

RÀtt sÀker att jag hittat vilken serie den följer: Tribinacci. Skriver man ut den serien fÄr man

0,0,1,1,4,7,13,24,44

StÀmmer i alla fall för 4 och 5 ettor i rad, nÄgot bevis har jag dock inte men finns kanske nÄgon som orkar reda ut det?
SÄ Àndrade min lösning till att anvÀnda det i stÀllet för hÄrdkodade antal permutationer.

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 10

Del 2

Jag gjorde en rÀttfram rekursiv lösning med memoization (i Rust). För min input sÄ anropas den rekursiva funktionen totalt 184 ggr, sÄ det tar inte lÄng tid.

fn p2_recursive(mut adapter_idx: usize, bag: &Bag, cache: &mut HashMap<Adapter, usize>) -> usize { if adapter_idx >= bag.len() - 1 { return 1; } let adapter = bag[adapter_idx]; let mut cnt = 0; adapter_idx += 1; while let Some(next) = bag.get(adapter_idx) { if *next > adapter + 3 { break; } cnt += match cache.get(next) { Some(partial) => *partial, None => { let partial = p2_recursive(adapter_idx, bag, cache); cache.insert(*next, partial); partial } }; adapter_idx += 1; } cnt } pub fn part2(bag: &Bag) -> usize { let mut cache = HashMap::with_capacity(bag.len()); p2_recursive(0, bag, &mut cache) }

Dold text