🌟 Advent of Code (AoC) 2020 🌟

PermalÀnk
Medlem ★
●

Dag: 7
SprÄk: VB.Net

Det blev inte sÄ snyggt som jag hade hoppats pÄ. TÀnkte först skapa instanser av klassen "Bag" som i sin tur skulle innehÄlla en lista av instanser av Bag enligt reglerna i filen, och lÄta klassen gÄ igenom sitt eget innehÄll och rÀkna. Sen ramlade hjÀrnan in pÄ ett annat spÄr och i slutÀnden blev det nÄn konstig hybrid av klassinstanser, rekursion och textparsning.

Imports System.IO Module Program Sub Main(args As String()) Dim partOneCount As Integer = 0 Dim bags As New List(Of Bag) For Each rule In File.ReadLines("input.txt") Dim colorAndContents = rule.Split("bags contain") Dim contents = colorAndContents.Last().Split(","c) bags.Add(New Bag(colorAndContents(0).Trim(), contents)) Next For Each bag In bags If ContainsColor(bag, "shiny gold", bags, False) Then partOneCount += 1 Next Dim partTwoCount = BagCount(bags.Find(Function(b) b.Color = "shiny gold"), bags) Console.WriteLine("Part 1: " & partOneCount) Console.WriteLine("Part 2: " & partTwoCount) End Sub Function ContainsColor(currentBag As Bag, color As String, bags As List(Of Bag), includeOwnColor As Boolean) If currentBag.Color = color And includeOwnColor Then Return True Dim bagsToSearch As New List(Of Bag) For Each bag In currentBag.Contents Dim bagColor = bag.Split(" "c)(1) & " " & bag.Split(" "c)(2) If ContainsColor(bags.Find(Function(b) b.Color = bagColor), "shiny gold", bags, True) Then Return True Next Return False End Function Function BagCount(currentBag As Bag, bags As List(Of Bag)) As Integer Dim contentCount As Integer = 0 For Each item In currentBag.Contents Dim numBags = Integer.Parse(item.Split(" "c)(0)) Dim bagColor = item.Split(" "c)(1) & " " & item.Split(" "c)(2) contentCount += numBags For i = 1 To numBags contentCount += BagCount(bags.Find(Function(b) b.Color = bagColor), bags) Next Next Return contentCount End Function Class Bag Public ReadOnly Property Color As String Public ReadOnly Property Contents As List(Of String) Public Sub New(color As String, contents As String()) Me.Color = color Me.Contents = New List(Of String) For Each bag In contents If bag.Trim() <> "no other bags." Then Me.Contents.Add(bag.Trim()) End If Next End Sub End Class End Module

Dold text
PermalÀnk
Medlem ★
●

Dag 7. LÀs inte om du vill lösa uppgiften helt pÄ egen hand. Jag behöver hjÀlp.

Är det meningen att man ska loopa mer Ă€n tvĂ„ gĂ„nger? I sĂ„ fall hur vet man nĂ€r man kan sluta loopa?

Jag skapar först en lista av fÀrger som har shiny gold som direct child. Resultat nedanför.

[striped tomato, clear yellow, wavy beige, faded fuchsia, shiny lavender, pale magenta]

Sen loopar jag genom listan igen och kollar varje child, om en child Àr med i den listan jag först skapade lÀggs det till i rÀkningen.

Blir fel svar ÀndÄ, jag behöver gÀrna tips pÄ algoritm. Jag har försökt förstÄ era lösningar men tyvÀrr ingen framgÄng.

Dold text
Visa signatur

| Mobo: Gigabyte X570 GAMING X | CPU: AMD Ryzen 9 3900X + Dark Rock 4 | RAM: 32GB @ 3000MHz | GPU: Gigabyte RTX 3080 OC | PSU: Seasonic GX 850W | Chassi: NZXT S340 Elite Matte Black | M.2: Samsung 970 Evo 500GB & 1000GB | HDD: 4TB | Monitors: Acer Predator X34 GS & Acer XB270HU |

PermalÀnk
●
Skrivet av Dave1080:

Dag 7. LÀs inte om du vill lösa uppgiften helt pÄ egen hand. Jag behöver hjÀlp.

Är det meningen att man ska loopa mer Ă€n tvĂ„ gĂ„nger? I sĂ„ fall hur vet man nĂ€r man kan sluta loopa?

Jag skapar först en lista av fÀrger som har shiny gold som direct child. Resultat nedanför.

[striped tomato, clear yellow, wavy beige, faded fuchsia, shiny lavender, pale magenta]

Sen loopar jag genom listan igen och kollar varje child, om en child Àr med i den listan jag först skapade lÀggs det till i rÀkningen.

Blir fel svar ÀndÄ, jag behöver gÀrna tips pÄ algoritm. Jag har försökt förstÄ era lösningar men tyvÀrr ingen framgÄng.

Dold text

Ja du mÄste kolla ALLA som dom ligger i ocksÄ. Och sedan mÄste du kolla alla dom osv tills dom du nÄr en fÀrg som inte sjÀlv ligger i en annan vÀska. Den skulle kunna ligga inpackad i över 100 vÀskor om det sÄ vill sig, sÄ ja det Àr meningen att du ska loopa tills det Àr fÀrdigt (hint: fler Àn 2 gÄnger)

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

Dag 7. LÀs inte om du vill lösa uppgiften helt pÄ egen hand. Jag behöver hjÀlp.

Är det meningen att man ska loopa mer Ă€n tvĂ„ gĂ„nger? I sĂ„ fall hur vet man nĂ€r man kan sluta loopa?

Jag skapar först en lista av fÀrger som har shiny gold som direct child. Resultat nedanför.

[striped tomato, clear yellow, wavy beige, faded fuchsia, shiny lavender, pale magenta]

Sen loopar jag genom listan igen och kollar varje child, om en child Àr med i den listan jag först skapade lÀggs det till i rÀkningen.

Blir fel svar ÀndÄ, jag behöver gÀrna tips pÄ algoritm. Jag har försökt förstÄ era lösningar men tyvÀrr ingen framgÄng.

Dold text

Förslag i spoilern

Det du jobbar med Àr egentligen en riktad graf.

(Bag 1) -> (Bag 2) -> (Bag 4) -> (no other) | ^ | | v | (Bag 3) -> (Bag 5)

Nedan har du ytterligare lite hjÀlp pÄ bÄda uppgifterna.

PÄ första uppgiften anvÀnde jag en graftraverseringsalgoritm för att besöka alla vÀskor.

för varje vÀska: hitta vÀgen frÄn vÀskan till "no other" rÀkna alla vÀgar dÀr "shiny gold" finns med i vÀgen

Kika pÄ UCS och se om det leder dig nÄgon vart

Dold text

Andra uppgiften lyckades jag inte lösa utan hjÀlp. Tillslut fick jag till en rekursiv lösning pÄ formen:

func rÀkna vÀskor(vÀska): vÀskor att bÀra = 1 för varje vÀska v inuti min vÀska: vÀskor att bÀra += (antal vÀskor av sort v) * rÀkna vÀskor(v) return vÀskor att bÀra

Dold text
Dold text
Visa signatur

:(){ :|:& };:

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

PermalÀnk
Medlem ★
●
Skrivet av GLaDER:

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

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

Idag fick jag brottas med hur Golang hanterar whitespace nÀr man itererar över en strÀng. Inga konstigheter frÄn sprÄkets sida, egentligen, men jag blev ÀndÄ tagen lite pÄ sÀngen och fick lÀgga nÄgra extra minuter pÄ att förstÄ varför jag fick fel svar.

DÀrtill spenderade jag en del tid pÄ att leta igenom standardbiblioteket strings efter funktioner av sorten unique(), set(), eller liknande, men hittade inget. IstÀllet gav jag mig pÄ att bygga min egna variant.

Blev dock vÀldigt nöjd nÀr Part 2 gick att lösa med en vÀldigt enkel extension av min egensnickrade uniqueRunes()!

Dold text

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

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

Nu börjar det bli svÄrt. Som jag skrev i inlÀgget ovan klarade jag inte att lösa del 2 utan att ta hjÀlp. Rekursion har aldrig varit min starka sida, men jag var helt övertygad om att det var rÀtt vÀg att gÄ. Huff och puff. Hoppas pÄ en uppgift mer i min smak, i morgon

Dold text
Visa signatur

:(){ :|:& };:

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

PermalÀnk
Medlem ★
●
Skrivet av Dave1080:

Dag 7. LÀs inte om du vill lösa uppgiften helt pÄ egen hand. Jag behöver hjÀlp.

Är det meningen att man ska loopa mer Ă€n tvĂ„ gĂ„nger? I sĂ„ fall hur vet man nĂ€r man kan sluta loopa?

Jag skapar först en lista av fÀrger som har shiny gold som direct child. Resultat nedanför.

[striped tomato, clear yellow, wavy beige, faded fuchsia, shiny lavender, pale magenta]

Sen loopar jag genom listan igen och kollar varje child, om en child Àr med i den listan jag först skapade lÀggs det till i rÀkningen.

Blir fel svar ÀndÄ, jag behöver gÀrna tips pÄ algoritm. Jag har försökt förstÄ era lösningar men tyvÀrr ingen framgÄng.

Dold text
Skrivet av huggeMugg:

Ja du mÄste kolla ALLA som dom ligger i ocksÄ. Och sedan mÄste du kolla alla dom osv tills dom du nÄr en fÀrg som inte sjÀlv ligger i en annan vÀska. Den skulle kunna ligga inpackad i över 100 vÀskor om det sÄ vill sig, sÄ ja det Àr meningen att du ska loopa tills det Àr fÀrdigt (hint: fler Àn 2 gÄnger)

Dold text
Skrivet av GLaDER:

Förslag i spoilern

Det du jobbar med Àr egentligen en riktad graf.

(Bag 1) -> (Bag 2) -> (Bag 4) -> (no other) | ^ | | v | (Bag 3) -> (Bag 5)

Nedan har du ytterligare lite hjÀlp pÄ bÄda uppgifterna.

PÄ första uppgiften anvÀnde jag en graftraverseringsalgoritm för att besöka alla vÀskor.

för varje vÀska: hitta vÀgen frÄn vÀskan till "no other" rÀkna alla vÀgar dÀr "shiny gold" finns med i vÀgen

Kika pÄ UCS och se om det leder dig nÄgon vart

Dold text

Andra uppgiften lyckades jag inte lösa utan hjÀlp. Tillslut fick jag till en rekursiv lösning pÄ formen:

func rÀkna vÀskor(vÀska): vÀskor att bÀra = 1 för varje vÀska v inuti min vÀska: vÀskor att bÀra += (antal vÀskor av sort v) * rÀkna vÀskor(v) return vÀskor att bÀra

Dold text
Dold text

@Dave1080 jag har ocksÄ totalkörtfast.

Har sett sÄna hÀr problem förut och gÄtt bet pÄ dom varenda gÄng. Har en algoritmbok som pratar om BFS och Djikstra's men inte kommit sÄ lÄngt Ànnu i den. KÀnns inte gÄngbart att försöka lÀra mig de begreppen innan det Àr dags att sova sÄ vÀljer nog att skippa den hÀr dagen sÄ fÄr jag hoppas pÄ att det kommer nÄgot mer gÄngbart imorgon.

Dold text
Visa signatur

PrimÀr: R9 3900X | ASUS X570-F Gaming | NH-D15 | 64GB@3200MHz | RTX 3080 10GB | Seasonic 850W | Fractal Define R6 |
Gamla bettan: i5 750@3.8GHz | 8GB | HD5770 | Corsair VS 550W | FD R2 |

PermalÀnk
Medlem ★
●

@Daz, @Dave1080

SlÀnger in lösningsförslag:

Del 1
Jag byggde upp en dictionary dÀr varje vÀska blir en nyckel vars vÀrde Àr en lista av de vÀskor den i sin tur innehÄller.
Sedan kan man m.h.a. rekursion samla pÄ sig alla vÀskor som innehÄller eftersökt vÀska tills man nÄr en tom vÀska.

Del 2
Samma princip som första delen, men vÀrdena i dictionaryn blir istÀllet egna dictionaries dÀr vÀskan blir nyckel och vÀrdet Àr antalet förekomster.

Även hĂ€r kan det lösas m.h.a. rekursion dĂ€r vi berĂ€knar summan av totala antalet vĂ€skor som eftersökt vĂ€ska innehĂ„ller. Resultatet adderas sedan ihop genom att multiplicera med antalet förekomster.

sum = sum(dict[key].values()) for k in dict[key].keys(): occurrences = dict[key][k] sum += occurrences * countBags(k, dict) return sum

Dold text
Visa signatur

AMD Ryzen 7 1700X 3.8 GHz 20MB | ASUS PRIME X370-PRO | MSI GeForce GTX 1080 Gaming X 8GB | G.Skill 16GB DDR4 3200 MHz CL14 Flare X | Corsair RM650x 650W

PermalÀnk
Medlem
●

Dag 7 lösningar

Del 1

Jag inverterade strukturen som ges som input (utsida -> insida), till en HashMap som mappar insida -> set med yttre vÀskor.

Sen Àr det bara att börja med "shiny gold" och iterera tills resulat-setet inte vÀxer lÀngre (fixed point iteration).

Dold text

Del 2

Löses enkelt med input datastrukturen och rekursion. Algoritmen antyds tydligt i uppgiften. (notera multiplikation med 1)

Citat:

So, a single shiny gold bag must contain 1 dark olive bag (and the 7 bags within it) plus 2 vibrant plum bags (and the 11 bags within each of those): 1 + 1*7 + 2 + 2*11 = 32 bags!

Dold text
PermalÀnk
Hedersmedlem ★
●

Dag: 7
SprÄk: Powershell
KĂ€llkod: Github

Inte helt nöjd med prestandan pÄ denna. Tar hela 7,6 sekunder att köra pÄ min laptop med en i5-8300H, men jag har inte hunnit optimera detta. FÄr titta pÄ lösningarna för att se om det finns nÄgon bÀttre algoritm jag missat, eller om det bara Àr sÄ att Powershell Àr sÄ lÄngsamt för syftet. SÄdÀr, nu tar den cirka 200 millisekunder istÀllet efter en enkel optimering. Det kÀnner jag mig mer nöjd med.

Blev inte sÀrskilt ideomatiskt powershell heller, men det Àr svÄrt med den hÀr sortens problem ocksÄ.

PermalÀnk
Medlem
●
Skrivet av Dave1080:

Dag 7. LÀs inte om du vill lösa uppgiften helt pÄ egen hand. Jag behöver hjÀlp.

> Är det meningen att man ska loopa mer Ă€n tvĂ„ gĂ„nger? I sĂ„ fall hur vet man nĂ€r man kan sluta loopa?

Jag löste bÄda rekursivt (metoder som anropar sig sjÀlva med nya parametrar). Har en kollega som löste det pÄ ett annat sÀtt för han gillar inte rekursion (tycker det Àr krÄngligt) sÄ det gÄr uppenbarligen, typ med en while-loop och muterbara datastrukturer kan jag tÀnka. Men sÄ hÀr löste jag dom (i pseudokod).

Uppgift 1: Parsa filen sÄ du fÄr en Map(String -> List[String]). Vi struntar i siffrorna i uppgift 1, sÄ det blir exvis

"blÄ" -> ["vit", "röd", "guld"] "svart" -> ["blÄ"] "vit" -> [] Skapa en metod "sökaren" som tar emot tvÄ StrÀnglistor: attUndersöka och hittade. define sökaren(attUndersöka, hittade): IF attUndersöka listan Àr tom RETURN "hittade" listan parametern precis som vi fick in den. Nu Àr vi klara, kallas basfallet i rekursion) ELSE plocka ut ett element "x" frÄn attUndersöka sÄ attUndersöka Àr ett element mindre. lÀgg "x" i listan över hittade gÄ igenom datastrukturen och hitta dom alla dom rader dÀr listorna innehÄller "x". lÀgg till nycklarna som pekar pÄ dom listorna till listan attUndersöka OM dom inte redan finns dÀr RETURN sökaren(nyaAttUndersöka, nyaHittade)

SÄ anropar du sökaren med Listan ["guld"] och tom lista, eftersom det Àr guld vi vill undersöka, och vi har inte hittat nÄgot Àn.
Första varvet: attUndersöka Àr inte tom. SÄ vi plockar ur "guld", och hittar att blÄa vÀskor innehÄller guldvÀskor. Vi anropar sökaren med Listorna ["blÄ"] respektive ["guld"] och returnerar vad det varvet returnerar
Andra varvet: attUndersöka Àr inte tom. Ta ut "blÄ", hitta "svart". Anropa sökaren med ["svart"] respektive ["guld", "blÄ"] och returnerar du vet vad.
Tredje varvet: attUndersöka Àr inte tom. Ta ut svart, hitta inget. Anropa sökaren med tom lista och ["guld", "blÄ", "svart"]
FjÀrde varvet: attUndersöka Àr tom, vi returnerar hittade: ["guld", "blÄ", "svart"] och det poppar upp och blir slutgiltiga svaret. LÀngden pÄ "hittade" minus ett (för vi skiter i "guld", vi ville bara ha hur mÄnga möjliga yttre vÀskor den har) Àr svaret.

Uppgift 2:

Kolla pÄ min kod ovan och se om du förstÄr, jag orkar inte skriva en sÄ lÄng förklaring igen.
#18791461
Men allt fram till totalWeight lÀser och parsar bara filen till en Map sÄ som jag vill ha den, den hÀr gÄngen mÄste vi bry oss om siffrorna i texten ocksÄ. SÄ sjÀlva körningen Àr totalWeight som anropar sig sjÀlv tills den Àr klar efter att jag anropat den första gÄngen. Men istÀllet för en "hittade" lista sÄ returnerar den rekursivt vad varje vÀska innehÄller (gÄnger antal av den typen).

GLaDER hade en rÀtt tydlig förklaring pÄ uppgift 2 ocksÄ tyckte jag.

Dold text
PermalÀnk
Medlem
●

FrÄn reddit:

https://www.reddit.com/r/adventofcode/comments/k8ccpz/shiny_g...

PermalÀnk
Medlem
●
Skrivet av BigMomma:

Dag: 7
SprÄk: VB.Net

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.

PermalÀnk
Datavetare ★
●

Dag: 7
SprÄk: Swift
Lösning: GitHub

Idag kom mina bristande kunskaper i Swift definitivt upp till ytan. Är inte den lösning jag ville ha (framförallt inte pĂ„ del 1, del 2 Ă€r mer OK:ish), utan blev den jag fick till givet kunskapsnivĂ„ i sprĂ„ket (aldrig anvĂ€nt Swift innan AoC 2020 dag 1). ÖvervĂ€gde ett tag att dumpa Swift för Ă„rets AoC, men det hade ju verkligen varit att ge upp.

Hoppas pÄ repris av förra Äret, var Àven dÄ rÀtt tungt att sitta med ett sprÄk jag aldrig anvÀnt innan AoC, i det fallet Rust. Men pÄ slutet gick det riktigt bra och idag Àr Rust en av mina absoluta favoritsprÄk. Hoppas att Rust ersÀtter C++ som mest populÀra systemsprÄk nÄgon dag.

Har uppdaterat mitt Swift-hjÀlp-bibliotek med en benchmark funktion. Men redan insett att Swift inte riktigt ligger pÄ C, C++ och Rust nivÄ.

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 ★
●

@huggeMugg @GLaDER @noMad17 @wgren

Jag Àr helt otroligt övervÀldigad av vilka bra och detaljerade svar jag fick. En sak ska ni alla hÀr i trÄden ha jÀvligt klart för er och det Àr att jag suger pÄ rekursiva funktioner. Jag fattar konceptet, men hjÀrnan slutar funka hela tiden nÀr jag försöker skriva en. Jag har Àrligt talat aldrig skrivit en proper rekursiv funktion under hela mina 3 Är. Det kanske mÀrks?

Bara part 1 sÄ lÀnge, uppdaterar inlÀgget om jag lyckas lösa part 2 inom kort.
Inspirerad av wgrens idé.

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

Löst del 2 nu ocksÄ. Hemsk utmaning, men fÄr erkÀnna att det var sjukt nyttigt.
Visa signatur

| Mobo: Gigabyte X570 GAMING X | CPU: AMD Ryzen 9 3900X + Dark Rock 4 | RAM: 32GB @ 3000MHz | GPU: Gigabyte RTX 3080 OC | PSU: Seasonic GX 850W | Chassi: NZXT S340 Elite Matte Black | M.2: Samsung 970 Evo 500GB & 1000GB | HDD: 4TB | Monitors: Acer Predator X34 GS & Acer XB270HU |

PermalÀnk
Medlem ★
●
Skrivet av GLaDER:

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

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

Nu börjar det bli svÄrt. Som jag skrev i inlÀgget ovan klarade jag inte att lösa del 2 utan att ta hjÀlp. Rekursion har aldrig varit min starka sida, men jag var helt övertygad om att det var rÀtt vÀg att gÄ. Huff och puff. Hoppas pÄ en uppgift mer i min smak, i morgon

Dold text

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

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

Idag gick det precis som jag vill! Min initiala idé fungerade och jag fick lÀra mig lite nya grejer om sprÄket jag anvÀnder. Idag lÄg klurigheten i att slices skickas runt "by reference" som default, och att jag dÀrför behövde skapa en ny kopia för varje variant av programmet.

Jag hoppas fler pussel gÄr ut pÄ att hjÀlpa vÄr stolsgranne, och om historisk data Àr en indikation för framtida problem borde det vara just sÄ.

Dold text
Visa signatur

:(){ :|:& };:

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

PermalÀnk
Medlem
●

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

Enklare idag, slapp rekursionen. Kan garanterat optimera lite, fÄr se om jag har tid senare.

package main import ( "bufio" "fmt" "os" "strconv" "strings" ) type Instruction struct { Operation string Value int } func getInstructions(rows []string) []Instruction { instructions := []Instruction{} for _, row := range rows { opEnd := strings.Index(row, " ") operation := row[:opEnd] row = row[opEnd+1:] value, _ := strconv.Atoi(row) instructions = append(instructions, Instruction{Operation: operation, Value: value}) } return instructions } func getPartOne(instructions []Instruction) int { globalAccelator := 0 visited := map[int]bool{} for i := 0; ; { inst := instructions[i] if _, ok := visited[i]; ok { break } visited[i] = false if inst.Operation == "nop" { i++ } if inst.Operation == "acc" { globalAccelator += inst.Value i++ } if inst.Operation == "jmp" { i += inst.Value % len(instructions) } } return globalAccelator } func getPartTwo(instructions []Instruction) int { globalAccelator := 0 alternatives := map[int][]Instruction{} found := false for i := range instructions { inst := instructions[i] if inst.Operation == "jmp" { copyInstructions := make([]Instruction, len(instructions)) copy(copyInstructions, instructions) copyInstructions[i].Operation = "nop" alternatives[i] = copyInstructions continue } if inst.Operation == "nop" { copyInstructions := make([]Instruction, len(instructions)) copy(copyInstructions, instructions) copyInstructions[i].Operation = "jmp" alternatives[i] = copyInstructions continue } } for _, altInstruction := range alternatives { if found { break } visited := map[int]bool{} globalAccelator = 0 for i := 0; ; { if i == len(altInstruction) { found = true break } inst := altInstruction[i] if _, ok := visited[i]; ok { break } visited[i] = false if inst.Operation == "nop" { i++ } if inst.Operation == "acc" { globalAccelator += inst.Value i++ } if inst.Operation == "jmp" { i += inst.Value % len(altInstruction) } } } return globalAccelator } 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(getInstructions(rows))) fmt.Println("PartTwo", getPartTwo(getInstructions(rows))) }

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

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

Enklare idag, slapp rekursionen. Kan garanterat optimera lite, fÄr se om jag har tid senare.

package main import ( "bufio" "fmt" "os" "strconv" "strings" ) type Instruction struct { Operation string Value int } func getInstructions(rows []string) []Instruction { instructions := []Instruction{} for _, row := range rows { opEnd := strings.Index(row, " ") operation := row[:opEnd] row = row[opEnd+1:] value, _ := strconv.Atoi(row) instructions = append(instructions, Instruction{Operation: operation, Value: value}) } return instructions } func getPartOne(instructions []Instruction) int { globalAccelator := 0 visited := map[int]bool{} for i := 0; ; { inst := instructions[i] if _, ok := visited[i]; ok { break } visited[i] = false if inst.Operation == "nop" { i++ } if inst.Operation == "acc" { globalAccelator += inst.Value i++ } if inst.Operation == "jmp" { i += inst.Value % len(instructions) } } return globalAccelator } func getPartTwo(instructions []Instruction) int { globalAccelator := 0 alternatives := map[int][]Instruction{} found := false for i := range instructions { inst := instructions[i] if inst.Operation == "jmp" { copyInstructions := make([]Instruction, len(instructions)) copy(copyInstructions, instructions) copyInstructions[i].Operation = "nop" alternatives[i] = copyInstructions continue } if inst.Operation == "nop" { copyInstructions := make([]Instruction, len(instructions)) copy(copyInstructions, instructions) copyInstructions[i].Operation = "jmp" alternatives[i] = copyInstructions continue } } for _, altInstruction := range alternatives { if found { break } visited := map[int]bool{} globalAccelator = 0 for i := 0; ; { if i == len(altInstruction) { found = true break } inst := altInstruction[i] if _, ok := visited[i]; ok { break } visited[i] = false if inst.Operation == "nop" { i++ } if inst.Operation == "acc" { globalAccelator += inst.Value i++ } if inst.Operation == "jmp" { i += inst.Value % len(altInstruction) } } } return globalAccelator } 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(getInstructions(rows))) fmt.Println("PartTwo", getPartTwo(getInstructions(rows))) }

Dold text

Vad tror du om att sparka igÄng massor med go routines för att lösa del 2? Jag har för dÄlig koll pÄ sprÄket för att göra det "i farten", men jag tÀnker mig att man borde kunna starta N parallella körningar pÄ nÄgot vis.

Visa signatur

:(){ :|:& };:

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

PermalÀnk
Medlem ★
●

Dag 8, awk.

part1$ <in awk '{ o[NR] = $1; p[NR] = $2 } END { i = 1 while (i <= NR && !(i in v)) { if (o[i] ~ /acc/) { a += p[i] } if (o[i] ~ /jmp/) { i += p[i] - 1 } v[i++] } print a }' part2$ <in awk '{ o[NR] = $1; p[NR] = $2 } /jmp/ || /nop/ { t[NR] } END { for (x in t) { delete v; a = 0; i = 1 while (i <= NR && !(i in v)) { if (o[i] ~ /acc/) { a += p[i] } if (o[i] ~ /jmp/ && i != x) { i += p[i] - 1 } if (o[i] ~ /nop/ && i == x) { i += p[i] - 1 } v[i++] } if (i > NR) { print a } } }'

Dold text
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: 7
SprÄk: JavaScript

Nu har jag lagt ALLDELES för mycket tid pĂ„ att försöka fĂ„ en fungerande lösning att köra snabbare och se bĂ€ttre ut, utan att egentligen lyckas. Är vĂ€l relativt nöjd med sjĂ€lva rekursionen (Haraldsson hade kanske inte varit nöjd, men...), men parsningen lĂ€mnar ganska mycket att önska.

function bagContent(list, bagColor, content) { let returnValue = 0; for (let i = 0; i < list.length; i++) { if (list[i].mainBag === bagColor) { if (list[i].containgBags) { for (let j = 0; j < list[i].containgBags.length; j++) { if (list[i].containgBags[j].name === content) { return 1; } else if (list[i].containgBags[j].name === 'other') { return 0; } returnValue += bagContent(list, list[i].containgBags[j].name, content); } } } } return returnValue; } function bagCount(list, bagColor, nrOfBags) { let returnValue = 1; for (let i = 0; i < list.length; i++) { if (list[i].mainBag === bagColor) { for (let j = 0; j < list[i].containgBags.length; j++) { if (list[i].containgBags[j].name === 'other') { return parseInt(nrOfBags, 10); } returnValue += bagCount(list, list[i].containgBags[j].name, list[i].containgBags[j].number); } } } return nrOfBags * returnValue; } function parse(text) { let list = text.split('\n'); for (let i = 0; i < list.length; i++) { if (list[i].length > 0) { let temp = list[i].split('bags contain'); list[i] = {}; list[i].mainBag = temp[0]; list[i].containgBags = temp[1]; list[i].mainBag = list[i].mainBag.trim(); list[i].containgBags = list[i].containgBags.split(','); for (let j = 0; j < list[i].containgBags.length; j++) { list[i].containgBags[j] = list[i].containgBags[j].trim(); let [number, ...name] = list[i].containgBags[j].split(' '); name = name.join(' '); name = name.substring(0, name.lastIndexOf(' ')); list[i].containgBags[j] = {}; list[i].containgBags[j].name = name; list[i].containgBags[j].number = number; } } } let containsGold = 0; for (let i = 0; i < list.length; i++) { if (bagContent(list, list[i].mainBag, 'shiny gold') > 0) { containsGold++; } } console.log(containsGold); console.log(bagCount(list, 'shiny gold', 1) - 1); } async function fetchInput() { const response = await fetch('input.txt'); const text = await response.text(); parse(text); } function startCode() { fetchInput(); } startCode();

Dold text
PermalÀnk
Medlem
●
Skrivet av GLaDER:

Vad tror du om att sparka igÄng massor med go routines för att lösa del 2? Jag har för dÄlig koll pÄ sprÄket för att göra det "i farten", men jag tÀnker mig att man borde kunna starta N parallella körningar pÄ nÄgot vis.

Beror nog pÄ din dator, men jag Àr skeptisk. Ser vÀl mer use-caset nÀr du har sega subrutiner (rest-call för att lÀsa in config pÄ nytt t ex) som inte ska blockera huvudtrÄden. Allt gÄr ju fort nog ÀndÄ för att man inte ska behöva optimera.

Du fÄr vÀl testa med "go test -bench ."

func BenchmarkPartOne(b *testing.B) { rows := getRows("../input.txt") for i := 0; i < b.N; i++ { getPartOne(getInstructions(rows)) } } func BenchmarkPartTwo(b *testing.B) { rows := getRows("../input.txt") for i := 0; i < b.N; i++ { getPartTwo(getInstructions(rows)) } }

BenchmarkPartOne-8 28435 42126 ns/op BenchmarkPartTwo-8 234 4819626 ns/op

Dold text
PermalÀnk
Medlem ★
●

Dag 8, Python

instructions = [l.split() for l in open('input', 'r')] + [['stop', 0]] def acc(pc, accumulator, offset): return pc + 1, accumulator + offset def jmp(pc, accumulator, offset): return pc + offset, accumulator def nop(pc, accumulator, offset): return pc + 1, accumulator def stop(pc, accumulator, offset): print('Part 2', accumulator) return 0, 0 # This pc has been executed, terminates execution swaps = { 'jmp':'nop', 'nop':'jmp'} def swap(i, instructions): s = instructions[i][0] if s in swaps: instructions[i][0] = swaps[s] run(instructions) instructions[i][0] = s def run(instructions): executed = set() pc, accumulator = 0, 0 while pc not in executed: executed.add(pc) i = instructions[pc] pc, accumulator = eval(i[0])(pc, accumulator, int(i[1])) return accumulator print('Part 1', run(instructions)) for i in range(len(instructions)): swap(i, instructions)

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

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

Men var har du din util? Den mÄste vara mycket intressantare Àn main.

PermalÀnk
●

Dag: 8
SprÄk: Nim
Lösning: Github

Dagens problem varit riktigt roligt att sitta och pilla med men det blev lite vÀl mycket onödig kod som vanligt

PermalÀnk
Medlem ★
●

Dag: 8
SprÄk: F#

open System open System.IO type Instruction = | NoOperation of int | AccumulatorOperation of int | JumpOperation of int type TerminationReason = | InfiniteLoop | TerminatedSuccessfully let stringSplit (token:string) (input:string) = input.Split(token, StringSplitOptions.RemoveEmptyEntries) let words = stringSplit " " let parseRow input = let parts = input |> words let value = parts.[1] |> int match parts.[0] with | "nop" -> (NoOperation value) | "acc" -> (AccumulatorOperation value) | "jmp" -> (JumpOperation value) let runProgram (program:Instruction array) = let rec runProgram' pc instructionsAlreadyRan acc = if (Set.contains pc instructionsAlreadyRan) then (acc, InfiniteLoop) elif (pc >= program.Length) then (acc, TerminatedSuccessfully) else let instructionToRun = program.[pc] match instructionToRun with | NoOperation _ -> runProgram' (pc+1) (instructionsAlreadyRan.Add pc) acc | AccumulatorOperation value -> runProgram' (pc+1) (instructionsAlreadyRan.Add pc) (acc+value) | JumpOperation value -> runProgram' (pc+value) (instructionsAlreadyRan.Add pc) (acc) runProgram' 0 Set.empty 0 let fixProgram program = let swapOperation = function | JumpOperation value -> NoOperation value | NoOperation value -> JumpOperation value | other -> other let rec fixProgram' head instructions = match instructions with | [] -> None | currentOperation::restOfInstructions when (swapOperation currentOperation <> currentOperation)-> let newProgram = head @ (swapOperation currentOperation)::restOfInstructions let (acc, terminationReason) = runProgram (newProgram |> Array.ofList) if(terminationReason = TerminatedSuccessfully) then Some acc else fixProgram' (head@[currentOperation]) restOfInstructions | currentOperation::restOfInstruction -> fixProgram' (head@[currentOperation]) restOfInstruction fixProgram' [] (program |> List.ofArray) [<EntryPoint>] let main argv = let instructions = File.ReadAllLines "example.txt" |> Array.map parseRow let (acc, _)= instructions |> runProgram printfn "Task 1: %i" acc printfn "Task 2: %A" (instructions |> fixProgram) 0

Dold text
Visa signatur

Jag Àr en optimist; det Àr aldrig sÄ dÄligt sÄ att det inte kan bli sÀmre.

PermalÀnk
Medlem ★
●

Dag: 8
SprÄk: JavaScript

Jag tycker det kÀnns som att idag var betydligt mycket enklare Àn tidigare dagar. Men kul uppgift
Men det Àr ÀndÄ vÀldigt imponerande att de snabbaste löser det pÄ strax över tre minuter, Àr ju trots allt lite kod som behöver skrivas.

function executeProgram(instructions, res) { let visited = new Array(instructions.length).fill(0); let accumulator = 0; let pc = 0; let exitReason = 1; let loopProtection = 0; while (loopProtection < 100000) { if (pc === parseInt(instructions.length)) { exitReason = 1; break; } if (visited[pc] > 0) { exitReason = 0; break; } visited[pc]++; let op = instructions[pc][0]; let modifyer = instructions[pc][1]; switch (op) { case "acc": accumulator += parseInt(modifyer); pc++; break; case "jmp": pc += parseInt(modifyer); break; case "nop": pc++; break; default: } loopProtection++; } res.accumulator = accumulator; return exitReason; } function calculate(text) { var instruction = text.split("\n"); for (let i = 0; i < instruction.length; i++) { instruction[i] = instruction[i].split(' '); } let res = { accumulator: 0 }; executeProgram(instruction, res); console.log("Result Part 1:" + res.accumulator); for (let i = 0; i < instruction.length; i++) { if (instruction[i][0] === "nop") { instruction[i][0] = "jmp"; } else if (instruction[i][0] === "jmp") { instruction[i][0] = "nop"; } if (executeProgram(instruction, res)) { console.log("Result Part 2:" + res.accumulator); break; } if (instruction[i][0] === "nop") { instruction[i][0] = "jmp"; } else if (instruction[i][0] === "jmp") { instruction[i][0] = "nop"; } } } async function fetchInput() { var response = await fetch('input.txt'); var text = await response.text(); calculate(text); } fetchInput();

Dold text
PermalÀnk
Datavetare ★
●

Dag: 8
SprÄk: Swift
Lösning: GitHub

Lite omstÀndlig, fast lite p.g.a. att det gav möjlighet till att lÀra sig minst en ny sak om Swift Àven idag

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

En sak ska ni alla hÀr i trÄden ha jÀvligt klart för er och det Àr att jag suger pÄ rekursiva funktioner. Jag fattar konceptet, men hjÀrnan slutar funka hela tiden nÀr jag försöker skriva en. Jag har Àrligt talat aldrig skrivit en proper rekursiv funktion under hela mina 3 Är. Det kanske mÀrks?

Det Àr inte sÄ svÄrt. Du mÄste bara tÀnka pÄ rÀtt sÀtt. Det finns ett tankesÀtt som kallas wishful thinking inom programmeringen och det passar perfekt för rekursion. Om vi tar exemplet frÄn söndagen dÀr en vÀska kunde innehÄlla ett antal andra vÀskor.

SÀg att vi skall skriva en funktion total(fÀrg) som rÀknar ut hur mÄnga vÀskor en vÀska av fÀrgen fÀrg innehÄller totalt. Om vi tittar pÄ en vÀska i taget mÄste vi hantera tvÄ fall:

  • Om vĂ€ska[fĂ€rg] inte innehĂ„ller nĂ„gon annan vĂ€ska Ă€r det lĂ€tt: det totala antalet vĂ€skor blir 1.

  • Om vĂ€ska[fĂ€rg] innehĂ„ller andra vĂ€skor blir det krĂ„ngligare, men om vi hade en funktion som rĂ€knade ut hur mĂ„nga vĂ€skor det fanns totalt i en annan vĂ€ska skulle det inte vara sĂ„ svĂ„rt. Med en sĂ„dan funktion skulle vi bara behöva anropa den och multiplicera med antal för alla vĂ€skor som vĂ€ska[fĂ€rg] innehĂ„ller. Men, vilken tur, vi hĂ„ller ju pĂ„ att skriva en funktion som rĂ€knar ut hur mĂ„nga vĂ€skor en vĂ€ska av fĂ€rg innehĂ„ller totalt, vi kan anvĂ€nda den

I nÄgon form av pseudo-kod skulle det kunna se ut sÄ hÀr:

total(fÀrg) { if (vÀska[fÀrg].empty()) return 1 # det enkla fallet else { # det lite krÄngligare fallet sum = 1 # Starta med 1 för att ta med vÀska[fÀrg] foreach v in vÀska[fÀrg] { sum += v.antal * total(v.fÀrg) # Rekursivt anrop } return sum } }

PermalÀnk
Medlem ★
●
Skrivet av Ingetledigtnamn:

Men var har du din util? Den mÄste vara mycket intressantare Àn main.

Det stÄr ju pÄ rad 7 i filen. Men hÀr har du en direktlÀnk -> $REPO/util/, och till dagens huvudspelare -> $REPO/util/handheld.go.

Det gÄr faktiskt ocksÄ att klicka pÄ funktionerna i GitHubs GUI.

Dold text
Visa signatur

:(){ :|:& };:

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

PermalÀnk
Medlem ★
●
Skrivet av Ingetledigtnamn:

Det Àr inte sÄ svÄrt. Du mÄste bara tÀnka pÄ rÀtt sÀtt. Det finns ett tankesÀtt som kallas wishful thinking inom programmeringen och det passar perfekt för rekursion.

Skrivet av https://wiki.c2.com/?WishfulThinking:

"Wishful Thinking" is a good way to think about recursion:
When seeing a recursive call, you should not think about the code being executed on each sub call. Instead, just imagine that the sub call does its job correctly.
Thus, you prove the correctness of the function by assuming that it is correct (on simpler input). This is some positive kind of self-fulfilling prophecy.
Of course you still have to check for trivial cases and need to assure that the recursive call handles a simpler case of your problem. But those are minor issues. The hardest part is to understand the recursive calls.
Without the technique of wishful thinking, you can't handle problems like "Towers of Hanoi", let alone more complicated ones.

Yes, makes sense, jag satt och försökte tÀnka i mitt huvud vad som hÀnde funktion efter funktion nÀr det egentligen rÀckte med att först skriva en fungerande funktion utan att tÀnka rekursivt överhuvudtaget och sen lÄta den kalla pÄ sig sjÀlv. DÄ löser resten av sig sjÀlvt. Tack för kodexemplet!

Är grön pĂ„ er alla som tydligen har tid pĂ„ morgon/dag. Jag fĂ„r vackert vĂ€nta tills ikvĂ€ll, annars kommer jag inte att göra mitt jobb.

(Jag vet att jag skriver pÄ SweClockers nu!)

Visa signatur

| Mobo: Gigabyte X570 GAMING X | CPU: AMD Ryzen 9 3900X + Dark Rock 4 | RAM: 32GB @ 3000MHz | GPU: Gigabyte RTX 3080 OC | PSU: Seasonic GX 850W | Chassi: NZXT S340 Elite Matte Black | M.2: Samsung 970 Evo 500GB & 1000GB | HDD: 4TB | Monitors: Acer Predator X34 GS & Acer XB270HU |

PermalÀnk
Medlem ★
●
Skrivet av GLaDER:

Det stÄr ju pÄ rad 7 i filen.

Jag försökte med rad 7 och tryckte in den i firefox, men fick 404. TÀnkte att man kanske mÄste ha access till sidan eller nÄt, men din direktlÀnk pekar faktiskt till ett annat stÀlle Àn rad 7 hÀnvisar.

Att man kunde klicka pÄ funktionerna visste jag inte. Tackar för den lektionen.