🌟 Advent of Code (AoC) 2020 🌟

2020-12-15 09:09

Permalänk

GLaDER

Medlem ★

Plats: *.home.arpa
Registrerad: Nov 2011

●

Skrivet av GLaDER:

Dag: 14
Språk: Go
Lösning: Main,

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

När det stod att talen var 36 bitar borde jag låtit bli att vara lat och köra på med vanliga int; men Del 1 gick ju toppenbra utan att ta till 64-bitars-tal så.... Aja. Dagens svåraste grej, för mig, var att fixa så att "001X0XX1" expanderades på rätt sätt. Det slutade med, tycker jag, en ganska snygg lösning där jag tar återanvände mitt favoritsätt att traversera träd.

Dold text

Gå till inlägget

Dag: 15
Språk: Go
Lösning: Main

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

Idag tyckte jag att jag var ganska snabb. Som sig bör fick jag direkt en tanke på hur jag borde lösa uppgiften men sen gick tankeprocessen ungefär såhär:

Började läsa beskrivningen
Ah! Använd en map för associera ett nummer med när det senast anropades.
läste vidare i beskrivningen
Oh.. jag behöver hålla koll på fler anrop än senaste, hm. ska nog använda en slice istället för en map då...
Kodar lite.
Inser att jag behöver min map för att associera numret med listan av anrop. Både map och slice alltså!
Kodar lite till.
Yes! Snabb och snygg lösning. Första stjärnan på plats ~3000! Det är min bästa sedan Day 1.

Sen la jag två timmar -- två timmar -- på att använda en slice med längd två (och hela tiden bara ha exakt de två tal jag behöver tillgängliga) istället för en slice med godtycklig längd. Tror aldrig jag haft så här många off-by-one errors... Stjärna två: Plats ~7000.

Dold text

Visa signatur

:(){ :|:& };:

🏊🏻‍♂️ 🚴🏻‍♂️ 🏃🏻‍♂️ ☕

Får det lov att vara en kaffe?

Rapportera Redigera

Citera flera Citera (1)

2020-12-15 10:13

Permalänk

huggeMugg

Medlem

Registrerad: Dec 2020

●

Dag: 15
Språk: Nim
Lösning: Github

Det här var lite antiklimaktiskt Hade förväntat mig mer, men man ska väl inte klaga

Rapportera Redigera

Citera flera Citera (1)

2020-12-15 10:35

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Dag: 15
Språk: Swift
Lösning: Github

Enda "smarta" jag gjorde var att notera att talet aldrig kan bli fler än antal rundor och i de flesta fall är det betydligt lägre. Så bästa prestanda får man genom att rakt upp och ned köra en array för historia där talet är index och värdet är senaste rundan det nämndes.

Även med "för lite" fysiskt RAM blir det snabbt med en array då majoriteten av array:en behöver bara virtuellt minne, men då den aldrig används behöver det aldrig backas av fysiskt RAM.

Att gå från Dictionary<Int, Int> -> Array<Int> gav ~x4 speedup

➜  day15 git:(main) ✗ swift run -c release
🌟 Part 1 : 981
⌚ Elapsed : 0 ms
🌟 Part 2 : 164878
⌚ Elapsed : 398 ms

Dold text

Visa signatur

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

Rapportera Redigera

Citera flera Citera (2)

2020-12-15 11:24

Permalänk

Flexbert

Medlem

Plats: Oslo
Registrerad: Okt 2001

●

Dag: 15
Språk: Golang
Lösning:

Ska skriva om den senare för använda en array istället..
Del1: 71µs
Del2: 2,5s

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func getLast(numbers []int, stop int) int {
	lastIndexes := map[int]int{}
	numberLen := len(numbers)
	for i := 1; i < numberLen; i++ {
		lastIndexes[numbers[i-1]] = i
	}
	last := numbers[numberLen-1:][0]

	for i := numberLen; i < stop; i++ {
		new := 0
		if lastIndex, ok := lastIndexes[last]; ok {
			new = i - lastIndex
		}
		lastIndexes[last] = i
		last = new
	}
	return last
}

func getPartOne(numbers []int) int {
	return getLast(numbers, 2020)
}

func getPartTwo(numbers []int) int {
	return getLast(numbers, 30000000)
}

func getNumbers(filename string) []int {
	file, _ := os.Open(filename)
	defer file.Close()
	scanner := bufio.NewScanner(file)
	numbers := []int{}
	for scanner.Scan() {
		row := scanner.Text()
		fields := strings.Split(row, ",")
		for _, field := range fields {
			val, _ := strconv.Atoi(field)
			numbers = append(numbers, val)
		}
	}
	return numbers
}

func main() {
	numbers := getNumbers("../input.txt")
	fmt.Println("PartOne", getPartOne(numbers))
	fmt.Println("PartTwo", getPartTwo(numbers))
}

Dold text

Rapportera Redigera

Citera flera Citera (1)

2020-12-15 11:47

Permalänk

Dave1080

Medlem ★

Registrerad: Jan 2008

●

Skrivet av gibbon_:

Så nu kan du få svaret inom en dag kanske?

Feta steps är absolut rätt riktning

Om du hittat T där buss 3 avgår, behöver du titta på T+1 eller T+2?

Om du hittat T där buss 3 OCH 5 avgår, behöver du titta på T+3?

ytterligare

om du vill ha ytterligare en nudge

Gå till inlägget

Yes, jag tittade på en Kotlin-lösning från Reddit som använde sig utav Chinese remainder theorem. Satt och försökte förstå, men det gick bara inte. Bestämmer mig för att detta helt enkelt är överkurs för mig.

Sen när jag kollade på uppgiftsbeskrivningen för dag 14 fattade jag ingenting. Speciellt detta stycke:

Skrivet av AOC:

This program starts by specifying a bitmask (mask = ....). The mask it specifies will overwrite two bits in every written value: the 2s bit is overwritten with 0, and the 64s bit is overwritten with 1.

Skulle nån kunna förklara för mig vad som skall göras?

Ändå rätt nöjd med att det tog 13 dagar innan jag blev helt sänkt.

Visa signatur

Rapportera Redigera

Citera flera Citera

2020-12-15 12:15

Permalänk

lydell

Medlem ★

Plats: Stockholm
Registrerad: Nov 2019

●

Skrivet av Dave1080:

Skulle nån kunna förklara för mig vad som skall göras?

Gå till inlägget

Här är exemplet med 11 lite mer utförligt:

Konvertera 11 till binärt (1011).
Skriv masken under. Fyll på med nollor framför 1011 så att de blir lika långa.

value:  000000000000000000000000000000001011  (decimal 11)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result:

Gå sedan från höger till vänster, en siffra i taget.

Om mask-tecknet är X, ta siffran från värdet.
Om mask-tecknet är 0, ta 0.
Om mask-tecknet är 1, ta 1.

Mask-tecknet längst till höger är X, så då tar vi 1:an längst till höger i värdet.

value:  000000000000000000000000000000001011  (decimal 11)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result:                                    1

Nästa mask-tecken är 0. Då blir det alltid 0.

value:  000000000000000000000000000000001011  (decimal 11)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result:                                   01

Och så vidare tills hela resultatet är ifyllt:

value:  000000000000000000000000000000001011  (decimal 11)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result: 000000000000000000000000000001001001

Det är alltså så som du “lägger ihop en mask och ett tal”. Sen är ju uppgiften lite mer än så, men detta kanske får dig på rätt spår?

Rapportera Redigera

Citera flera Citera

2020-12-15 12:22

Permalänk

GLaDER

Medlem ★

Plats: *.home.arpa
Registrerad: Nov 2011

●

Skrivet av Dave1080:

Yes, jag tittade på en Kotlin-lösning från Reddit som använde sig utav Chinese remainder theorem. Satt och försökte förstå, men det gick bara inte. Bestämmer mig för att detta helt enkelt är överkurs för mig.

Gå till inlägget

Du behöver inte använda CRT för att lösa uppgiften Du har fått några tips ovan om att loopa på ett lite smartare sätt.

Skrivet av Dave1080:

Sen när jag kollade på uppgiftsbeskrivningen för dag 14 fattade jag ingenting. Speciellt detta stycke:

This program starts by specifying a bitmask (mask = ....). The mask it specifies will overwrite two bits in every written value: the 2s bit is overwritten with 0, and the 64s bit is overwritten with 1.

Skulle nån kunna förklara för mig vad som skall göras?

Ändå rätt nöjd med att det tog 13 dagar innan jag blev helt sänkt.

Gå till inlägget

Jag tycker att exemplet på AoC hjälper mycket!

Om du får följande som input:

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0

ska värdena 11, 101, och 0 modifieras av "masken" och det modifierade värdet ska sedan skrivas till minnesadresserna 8, 7, och 8. (Ja, du kommer skriva över värdet på minnesadress 8.)

Sen får man ett exempel på hur själva maskningen ska gå till:

value:  000000000000000000000000000000001011  (decimal 11)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result: 000000000000000000000000000001001001  (decimal 73

Ovan har du talet 11 återgivet både decimalt (bas 10) och på binär form (bas 2). Om du kollar på binärformen ser du att den är lika lång som masken. Du kan nu använda reglerna som är beskrivna av AoC för att få fram ditt modifierade tal:

A 0 or 1 overwrites the corresponding bit in the value, while an X leaves the bit in the value unchanged.

När jag skrev min kod löste jag det såhär:

mask = ""
mem = dict()

for row in input:
  if "mask" in row:
    mask = parseMask(row)
  else:
    addr, value = parseMemVal(row)
    mem[addr] = maskedValue(mask, value)

Kruxet är givetvis att skriva maskedValue(). Säg till om du vill ha vidare guidning

Dold text

Senast redigerat 2020-12-15 14:00 Typo.

Visa signatur

:(){ :|:& };:

🏊🏻‍♂️ 🚴🏻‍♂️ 🏃🏻‍♂️ ☕

Får det lov att vara en kaffe?

Rapportera Redigera

Citera flera Citera (2)

2020-12-15 13:00

Permalänk

Flexbert

Medlem

Plats: Oslo
Registrerad: Okt 2001

●

Skrivet av Yoshman:

Dag: 15
Språk: Swift
Lösning: Github

Enda "smarta" jag gjorde var att notera att talet aldrig kan bli fler än antal rundor och i de flesta fall är det betydligt lägre. Så bästa prestanda får man genom att rakt upp och ned köra en array för historia där talet är index och värdet är senaste rundan det nämndes.

Även med "för lite" fysiskt RAM blir det snabbt med en array då majoriteten av array:en behöver bara virtuellt minne, men då den aldrig används behöver det aldrig backas av fysiskt RAM.

Att gå från Dictionary<Int, Int> -> Array<Int> gav ~x4 speedup

➜  day15 git:(main) ✗ swift run -c release
🌟 Part 1 : 981
⌚ Elapsed : 0 ms
🌟 Part 2 : 164878
⌚ Elapsed : 398 ms

Dold text

Gå till inlägget

Om jag använder arrayer så är jag nere på:
Del1: 5µs
Del2: 750ms

Dold text

Rapportera Redigera

Citera flera Citera

2020-12-15 13:50

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Skrivet av Flexbert:

Om jag använder arrayer så är jag nere på:
Del1: 5µs
Del2: 750ms

Dold text

Gå till inlägget

Kan köra ditt ursprungliga program på 1,7s (med min input, men det borde inte spela någon roll). Lärde mig att de fått igång Go på M1 Mac nu, endera vänta till nästa release av Go så kommer det förpackat eller läs denna tråd så finns instruktioner för att bygga från git. Det som är lite underförstått är att man först måste ladda ner x86_64 versionen för MacOS, lägga den i PATH, sen kör man bootstrap scriptet och specificerar ARM64 som CPU och Darwin som OS.

$ file $(which go)
/Volumes/Samsung_T5/go-darwin-arm64-bootstrap/bin/go: Mach-O 64-bit executable arm64

Du postade aldrig array-versionen va?

Visa signatur

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

Rapportera Redigera

Citera flera Citera

2020-12-15 14:29

Permalänk

Flexbert

Medlem

Plats: Oslo
Registrerad: Okt 2001

●

Skrivet av Yoshman:

Kan köra ditt ursprungliga program på 1,7s (med min input, men det borde inte spela någon roll). Lärde mig att de fått igång Go på M1 Mac nu, endera vänta till nästa release av Go så kommer det förpackat eller läs denna tråd så finns instruktioner för att bygga från git. Det som är lite underförstått är att man först måste ladda ner x86_64 versionen för MacOS, lägga den i PATH, sen kör man bootstrap scriptet och specificerar ARM64 som CPU och Darwin som OS.

$ file $(which go)
/Volumes/Samsung_T5/go-darwin-arm64-bootstrap/bin/go: Mach-O 64-bit executable arm64

Du postade aldrig array-versionen va?

Gå till inlägget

Nä, här har du den. Mitt bench-test är utan indataläsning.

main.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func getLast(numbers []int, stop int) int {
	lastIndexes := make([]int, stop)
	numberLen := len(numbers)
	for i := 1; i < numberLen; i++ {
		lastIndexes[numbers[i-1]] = i
	}
	last := numbers[numberLen-1:][0]

	for i := numberLen; i < stop; i++ {
		new := 0
		if lastIndexes[last] != 0 {
			new = i - lastIndexes[last]
		}
		lastIndexes[last] = i
		last = new
	}
	return last
}

func getPartOne(numbers []int) int {
	return getLast(numbers, 2020)
}

func getPartTwo(numbers []int) int {
	return getLast(numbers, 30000000)
}

func getNumbers(filename string) []int {
	file, _ := os.Open(filename)
	defer file.Close()
	scanner := bufio.NewScanner(file)
	numbers := []int{}
	for scanner.Scan() {
		row := scanner.Text()
		fields := strings.Split(row, ",")
		for _, field := range fields {
			val, _ := strconv.Atoi(field)
			numbers = append(numbers, val)
		}
	}
	return numbers
}

func main() {
	numbers := getNumbers("../input.txt")
	fmt.Println("PartOne", getPartOne(numbers))
	fmt.Println("PartTwo", getPartTwo(numbers))
}

main_test.go

package main

import "testing"

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

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

go test --bench .

Dold text

Rapportera Redigera

Citera flera Citera

2020-12-15 16:45

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Skrivet av Flexbert:

Nä, här har du den. Mitt bench-test är utan indataläsning.

main.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func getLast(numbers []int, stop int) int {
	lastIndexes := make([]int, stop)
	numberLen := len(numbers)
	for i := 1; i < numberLen; i++ {
		lastIndexes[numbers[i-1]] = i
	}
	last := numbers[numberLen-1:][0]

	for i := numberLen; i < stop; i++ {
		new := 0
		if lastIndexes[last] != 0 {
			new = i - lastIndexes[last]
		}
		lastIndexes[last] = i
		last = new
	}
	return last
}

func getPartOne(numbers []int) int {
	return getLast(numbers, 2020)
}

func getPartTwo(numbers []int) int {
	return getLast(numbers, 30000000)
}

func getNumbers(filename string) []int {
	file, _ := os.Open(filename)
	defer file.Close()
	scanner := bufio.NewScanner(file)
	numbers := []int{}
	for scanner.Scan() {
		row := scanner.Text()
		fields := strings.Split(row, ",")
		for _, field := range fields {
			val, _ := strconv.Atoi(field)
			numbers = append(numbers, val)
		}
	}
	return numbers
}

func main() {
	numbers := getNumbers("../input.txt")
	fmt.Println("PartOne", getPartOne(numbers))
	fmt.Println("PartTwo", getPartTwo(numbers))
}

main_test.go

package main

import "testing"

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

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

go test --bench .

Dold text

Gå till inlägget

$ go test --bench=. 
goos: darwin
goarch: arm64
pkg: day15
BenchmarkPartOne-8   	  569848	      2101 ns/op
BenchmarkPartTwo-8   	       3	 369253292 ns/op
PASS
ok  	day15	4.623s

Visa signatur

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

Rapportera Redigera

Citera flera Citera

2020-12-15 17:28

Permalänk

Flexbert

Medlem

Plats: Oslo
Registrerad: Okt 2001

●

Skrivet av Yoshman:

$ go test --bench=. 
goos: darwin
goarch: arm64
pkg: day15
BenchmarkPartOne-8   	  569848	      2101 ns/op
BenchmarkPartTwo-8   	       3	 369253292 ns/op
PASS
ok  	day15	4.623s

Gå till inlägget

Snyggt, får köpa mig en sådan. Den krossar ju min: Mbp 2017, 3,1 GHz Quad-Core Intel Core i7.

Rapportera Redigera

Citera flera Citera

2020-12-15 23:04

Permalänk

Dave1080

Medlem ★

Registrerad: Jan 2008

●

Skrivet av lydell:

Här är exemplet med 11 lite mer utförligt:

Konvertera 11 till binärt (1011).
Skriv masken under. Fyll på med nollor framför 1011 så att de blir lika långa.

value:  000000000000000000000000000000001011  (decimal 11)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result:

Gå sedan från höger till vänster, en siffra i taget.

Om mask-tecknet är X, ta siffran från värdet.
Om mask-tecknet är 0, ta 0.
Om mask-tecknet är 1, ta 1.

Mask-tecknet längst till höger är X, så då tar vi 1:an längst till höger i värdet.

value:  000000000000000000000000000000001011  (decimal 11)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result:                                    1

Nästa mask-tecken är 0. Då blir det alltid 0.

value:  000000000000000000000000000000001011  (decimal 11)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result:                                   01

Och så vidare tills hela resultatet är ifyllt:

value:  000000000000000000000000000000001011  (decimal 11)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result: 000000000000000000000000000001001001

Det är alltså så som du “lägger ihop en mask och ett tal”. Sen är ju uppgiften lite mer än så, men detta kanske får dig på rätt spår?

Gå till inlägget

Stort tack för en otroligt bra förklaring! Jag skrev ihop koder som kunde lösa exemplet i beskrivningen, men det blev fel när jag skulle köra med den riktiga inputen. Tror det blev tokigt när jag körde Long.toString(radix: 2) rakt av. Problemet är ju kombination av min okunskap om binära tal och saknaden av debugmöjligheter. Det var lite som mission impossible så jag letade upp en lösning på reddit och hämtade inspiration därifrån. Skrattade lite för mig själv, hade ändå inte klarat det själv. Ändå nice att lära mig operators som substringAfter och zip.

Här är lösningen för del 1 om ni är nyfikna. Del 2 kommer jag inte att röra.

Skrivet av GLaDER:

Du behöver inte använda CRT för att lösa uppgiften Du har fått några tips ovan om att loopa på ett lite smartare sätt.

Jag tycker att exemplet på AoC hjälper mycket!

Om du får följande som input:

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0

ska värdena 11, 101, och 0 modifieras av "masken" och det modifierade värdet ska sedan skrivas till minnesadresserna 8, 7, och 8. (Ja, du kommer skriva över värdet på minnesadress 8.)

Sen får man ett exempel på hur själva maskningen ska gå till:

value:  000000000000000000000000000000001011  (decimal 11)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result: 000000000000000000000000000001001001  (decimal 73

Ovan har du talet 11 återgivet både decimalt (bas 10) och på binär form (bas 2). Om du kollar på binärformen ser du att den är lika lång som masken. Du kan nu använda reglerna som är beskrivna av AoC för att få fram ditt modifierade tal:

A 0 or 1 overwrites the corresponding bit in the value, while an X leaves the bit in the value unchanged.

När jag skrev min kod löste jag det såhär:

mask = ""
mem = dict()

for row in input:
  if "mask" in row:
    mask = parseMask(row)
  else:
    addr, value = parseMemVal(row)
    mem[addr] = maskedValue(mask, value)

Kruxet är givetvis att skriva maskedValue(). Säg till om du vill ha vidare guidning

Dold text

Gå till inlägget

Tack till dig också! Ja ok, in that case kommer jag att backa till dag 13 och försöka klura ut det.

Visa signatur

Rapportera Redigera

Citera flera Citera

2020-12-16 09:28

Permalänk

Ingetledigtnamn

Medlem ★

Plats: Uppsala
Registrerad: Dec 2008

●

Dag 16, Python. Nej, den här lösning är jag inte särskilt nöjd med. Den blev varken kort eller elegant, istället blev den både lång och imperativ

Filinläsningen var inte så mycket man kunde göra något åt.
Listan matches innehåller kolumn och alla regler som en viss kolumn är giltig för.
Hitta den kolumn som bara matchar en regel, stoppa den i uniques, ta bort den regeln från matches och leta igen.

import re
from numpy import prod

def readinput():
    f = open("input")

    rules = []
    while True:
        line = f.readline().strip()
        m = re.search(r'(.+): (\d+)\-(\d+) or (\d+)\-(\d+)', line)
        if not m: break
        rules.append((m[1], ((int(m[2]), int(m[3])), (int(m[4]), int(m[5])))))
    
    f.readline()
    line = f.readline().strip()
    ticket = [int(i) for i in line.split(',')]
    f.readline()
    line = f.readline()
    others = [[int(i) for i in line.split(',')] for line in f.readlines()]
    return rules, ticket, others
    
def valid(x):
    return any([lo <= x <= hi for r in rules for lo, hi in r[1]])

rules, ticket, others = readinput()

v = [t for t in others if (all([valid(i) for i in t]))]

matches = [(c, set([i for i,rule in enumerate(rules)
             if all([any([lo <= v <= hi for lo, hi in rule[1]])
                     for v in [t[c] for t in v]])]))
           for c in range(len(ticket))]

uniques = []
while len(uniques) < len(matches):
    unique = [x for x in matches if len(x[1]) == 1][0]
    u = list(unique[1])[0]
    uniques.append((unique[0], u))
    for m in matches:
        if u in m[1]:
            m[1].remove(u)
    
print(sum([i
           for t in others
           for i in t
           if not(valid(i))]),
      prod([ticket[c]
            for c,r in uniques
            if rules[r][0].startswith('departure')]))

Dold text

Senast redigerat 2020-12-16 10:53 Förenklade lite

Rapportera Redigera

Citera flera Citera (1)

2020-12-16 11:01

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Dag: 16
Språk: Swift
Lösning: Github

Inga konstigheter, listade bara alla rader som var giltiga för alla giltiga biljetter och körde sedan en djupet först sökning för att hitta en kombination där alla fält användes.

Edit: ok, en sak. Sorterade listan med möjligheter så att man tittar på fallen med minst antal möjligheter först, tar jag bort den sorteringen (som inte är nödvändig för korrekthet) tar det >1 minut att hitta svaret.

$ swift run -c release
🌟 Part 1 : 19060
⌚ Elapsed : 0 ms
🌟 Part 2 : 953713095011
⌚ Elapsed : 4 ms

Dold text

Senast redigerat 2020-12-16 11:28

Visa signatur

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

Rapportera Redigera

Citera flera Citera (1)

2020-12-16 12:11

Permalänk

GLaDER

Medlem ★

Plats: *.home.arpa
Registrerad: Nov 2011

●

Skrivet av GLaDER:

Dag: 15
Språk: Go
Lösning: Main

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

Idag tyckte jag att jag var ganska snabb. Som sig bör fick jag direkt en tanke på hur jag borde lösa uppgiften men sen gick tankeprocessen ungefär såhär:

Började läsa beskrivningen
Ah! Använd en map för associera ett nummer med när det senast anropades.
läste vidare i beskrivningen
Oh.. jag behöver hålla koll på fler anrop än senaste, hm. ska nog använda en slice istället för en map då...
Kodar lite.
Inser att jag behöver min map för att associera numret med listan av anrop. Både map och slice alltså!
Kodar lite till.
Yes! Snabb och snygg lösning. Första stjärnan på plats ~3000! Det är min bästa sedan Day 1.

Sen la jag två timmar -- två timmar -- på att använda en slice med längd två (och hela tiden bara ha exakt de två tal jag behöver tillgängliga) istället för en slice med godtycklig längd. Tror aldrig jag haft så här många off-by-one errors... Stjärna två: Plats ~7000.

Dold text

Gå till inlägget

Dag: 16
Språk: Go
Lösning: Main

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

Kod. Kod. Kod.

Idag blev det långt. Jag löste Del 1 ganska smärtfritt, men jag lyckades verkligen inte hålla tungan i rätt mun när jag skulle hantera olika sorters index och värden. Det blev superviktigt att använda riktigt tydliga variabelnamn, för jag blandade konstant ihop "indexet i en ticket", "värdet index" som jag höll reda på, etc. Inte ens nu, när allting fungera, är jag helt hundra på vad som är vad.

Vad värre är lade jag säkert en timme på en lösning som var inversen till den jag tillslut fick rätt svar med.

Kärnan i min fungerande lösning ser ni nedan.

for c, v := range constraints {
	lowList := util.MakeRange(v[0][0], v[0][1])
	highList := util.MakeRange(v[1][0], v[1][1])
	vRange := append(lowList, highList...)

	availIds := util.MakeRange(0, len(tickets[0])-1)

	for _, ticket := range tickets {
		for valueIdx, ticketValue := range ticket {
			if !util.IntInSlice(ticketValue, vRange) {
				availIds = util.RemoveIntByValue(valueIdx, availIds)				}
		}
	}
	constraintToRange[c] = append(constraintToRange[c], availIds...)
}

Grundpremissen är att jag har en lista: vRange, som innehåller alla giltiga värden för en viss constraint. För varje ticket skapar jag sedan en lista med alla möjliga index (availIds). Därefter kollar jag siffran på varje position i ticket. Om siffran inte återfinns i vRange tar jag bort den från availIds.

AoC inputen är gjord så att minst en constraint bara kommer ha en siffra i availIds. Så i en annan del av koden loopar jag helt enkelt över alla constraints. Om det bara finns ett värde i availIds är jag klar med det constraintet. Då tar jag bort det IDt från alla andra constraints och vipps är det minst en constraint som bara har ett värde igen.

Problemet med mitt initiala lösningsförslag var att jag gjorde tvärtom. Jag började med en tom lista och loopade igenom alla tickets. "Fungerar det här indexet? Ja. Lägg till." Förhoppningen var att ett index per constraint skulle vara "högst", men så blev det inte... Bläh.

Dold text

Visa signatur

:(){ :|:& };:

🏊🏻‍♂️ 🚴🏻‍♂️ 🏃🏻‍♂️ ☕

Får det lov att vara en kaffe?

Rapportera Redigera

Citera flera Citera (1)

2020-12-16 12:44

Permalänk

gibbon_

Medlem ★

Plats: Sydney
Registrerad: Aug 2003

●

Dag 16, ngl, börjar tappa tålamodet på awk nu. Komplexiteten börjar bli för mycket för ett så primitivt verktyg. Inte för att problemen i sig kräver några finare features, men det går åt en viss "kognitiv belastning" åt att mappa allt till strängar och hashmaps. Idag tappade jag förtroendet lite på min lösning halvvägs genom, och då sved det extra när man knappt minns vad som är vad längre. Tack för statiskt typade språk, säger jag bara.

BEGIN { reading = "rules" }

/your ticket/ { reading = "mine" }
/nearby tickets/ { reading = "nearby" }

reading == "rules" && length($0) {
	rules[++num_rules] = $0
	split($(NF - 2), range, "-"); for (i = range[1]; i <= range[2]; i++) { accept[num_rules","i] }
	split($NF, range, "-"); for (i = range[1]; i <= range[2]; i++) { accept[num_rules","i] }
}

reading == "mine" && /[0-9,]+/ { split($0, mine, ",") }

reading == "nearby" && /[0-9,]+/ {
	ticket_ok = 1
	split($0, values, ",")
	for (f in values) {
		ok = 0
		for (r = 1; r <= num_rules; r++) {
			ok = ok || r","values[f] in accept
		}
		if (!ok) {
			ticket_ok = 0
			p1 += values[f]
		}
	}
	if (ticket_ok) {
		tickets[$0]
	}
}

END {
	for (n = 1; n <= num_rules; n++) { left[n] }
	while (length(left) > 0) {
		for (f = 1; f <= num_rules; f++) {
			cnt = 0
			for (r = 1; r <= num_rules; r++) {
				if (!(r in left)) { continue }
				ok = 1
				for (t in tickets) {
					split(t, values, ",")
					ok = ok && r","values[f] in accept
				}
				if (ok) {
					cnt++
					rule = r
				}
			}
			if (cnt == 1) {
				field_map[f] = rule
				delete left[rule]
			}
		}
	}
	p2 = 1
	for (f in field_map) { p2 *= rules[field_map[f]] ~ /^departure/ ? mine[f] : 1 }
	print p1
	print p2
}

Var inte allt för nöjd med ovan, särskilt att göra så mycket jobb på slutet när man säkert sett tillräckligt tidigare i programmet.. Blev ~15ggr snabbare när jag höll lite extra state för att minnas från rad till rad vilka fält som fortfarande är ok för diverse kolumner.

BEGIN { reading = "rules" }

/your ticket/ { reading = "mine" }
/nearby tickets/ { reading = "nearby" }

reading == "rules" && length($0) {
	rules[++num_rules] = $0
	split($(NF - 2), range, "-"); for (i = range[1]; i <= range[2]; i++) { accept[num_rules","i] }
	split($NF, range, "-"); for (i = range[1]; i <= range[2]; i++) { accept[num_rules","i] }
}

reading == "mine" && /[0-9,]+/ { split($0, mine, ",") }

reading == "nearby" && /[0-9,]+/ {
	ticket_ok = 1
	split($0, values, ",")
	for (f in values) {
		ok = 0
		for (r = 1; r <= num_rules; r++) {
			ok = ok || r","values[f] in accept
		}
		if (!ok) {
			ticket_ok = 0
			p1 += values[f]
		}
	}
	if (ticket_ok) {
		tickets[$0]
		for (f in values) {
			for (r = 1; r <= num_rules; r++) {
				map[f","r] = (!(f","r in map) || map[f","r]) && r","values[f] in accept
			}
		}
	}
}

END {
	p2 = 1
	for (n = 1; n <= num_rules; n++) { left[n] }
	for (f = 1; length(left); f = (f % num_rules) + 1) {
		cnt = 0
		for (r in left) {
			if (map[f","r]) { cnt++; rule = r }
		}
		if (cnt == 1) {
			p2 *= rules[rule] ~ /^departure/ ? mine[f] : 1;
			delete left[rule]
		}
	}
	print p1
	print p2
}

Dold text

Jag tror med detta att jag får ge upp mina hopp om att nå top 5 (anonymous user #122421), det lär bara bli värre härifrån. Mårten, om du ser detta, vem du än är.. fan ta dig Min hemliga nemesis senaste veckan eller så.. Med det sagt.. ta top 3 från den där andra anonyme! God speed

Senast redigerat 2020-12-16 13:36

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

Rapportera Redigera

Citera flera Citera (1)

2020-12-16 15:25

Permalänk

huggeMugg

Medlem

Registrerad: Dec 2020

●

Dag: 16
Språk: Nim
Lösning: Github

Gjorde det nog mer invecklat än det hade behövt vara på del 2...

Rapportera Redigera

Citera flera Citera (1)

2020-12-16 20:34

Permalänk

Ingetledigtnamn

Medlem ★

Plats: Uppsala
Registrerad: Dec 2008

●

Skrivet av gibbon_:

Dag 16, ngl, börjar tappa tålamodet på awk nu. Komplexiteten börjar bli för mycket för ett så primitivt verktyg.

Gå till inlägget

Du har gjort ett bra jobb. Jag är klart imponerad över att du lyckats lösa problemen in awk (och de andra kommandoradsverktygen).

Rapportera Redigera

Citera flera Citera

2020-12-16 22:00

Permalänk

Dave1080

Medlem ★

Registrerad: Jan 2008

●

Skrivet av Ingetledigtnamn:

Du har gjort ett bra jobb. Jag är klart imponerad över att du lyckats lösa problemen in awk (och de andra kommandoradsverktygen).

Gå till inlägget

Ja, jag är väldigt imponerad över er alla som kommit så här långt på ett främmande språk. Jag fixar det inte ens på mitt favoritspråk. Jag är inte ute efter nån tröst, detta är bara häftigt tycker jag. Inspirerande.

Visa signatur

Rapportera Redigera

Citera flera Citera

2020-12-16 22:02

Permalänk

Flexbert

Medlem

Plats: Oslo
Registrerad: Okt 2001

●

Idag blir det ingen lösning från mig, fick aldrig ordning på sista delen.

Rapportera Redigera

Citera flera Citera (1)

2020-12-17 02:09

Permalänk

Dave1080

Medlem ★

Registrerad: Jan 2008

●

Dag: 15
Språk: Kotlin
Lösning: GitHub

Förlorade tyvärr väldigt mycket tid på en bugg där det var rätt svar för del 1 men aldrig för del 2. Trodde att det var för att Int inte kunde hantera så stora siffror, men det visade sig senare att jag hade deklarerat listan och mapen som top-level variables..... sjukt onödigt. Sen var uppgiften lite ful och stökade till det med att börja med index 1.

Visa signatur

Rapportera Redigera

Citera flera Citera

2020-12-17 07:14

Permalänk

gibbon_

Medlem ★

Plats: Sydney
Registrerad: Aug 2003

●

Uppenbarligen något fundamentalt jag missar idag, för exemplet stämmer inte alls med hur jag läser reglerna för hur kartan ska uppdateras.

Before any cycles:

z=0
.#.
..#
###

"If a cube is inactive but exactly 3 of its neighbors are active, the cube becomes active. Otherwise, the cube remains inactive."

After 1 cycle:

z=0
#.#
.##
.#.

Övre vänster hörn, hur blev den aktiv?

Edit: Idiot.. De gjorde ju tom en edit i uppgifts-beskrivningen, de la till "(and the frame of view follows the active cells in each cycle)", och jag förstod fortfarande inte.. Givetvis menade de att övre raden är y=0 i exemplet och y=1 efter en cykel, för y=0 hade inga aktiva kuber kvar..

Vidare hade jag stavat fel på en variabel, vilket såklart awk inte skrek på och hanterade som 0 istället.

Senast redigerat 2020-12-17 08:14

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

Rapportera Redigera

Citera flera Citera

2020-12-17 08:15

Permalänk

Larrxi

Medlem ★

Registrerad: Sep 2006

●

Skrivet av gibbon_:

Uppenbarligen något fundamentalt jag missar idag, för exemplet stämmer inte alls med hur jag läser reglerna för hur kartan ska uppdateras.

Before any cycles:

z=0
.#.
..#
###

"If a cube is inactive but exactly 3 of its neighbors are active, the cube becomes active. Otherwise, the cube remains inactive."

After 1 cycle:

z=0
#.#
.##
.#.

Övre vänster hörn, hur blev den aktiv?

Edit: Idiot.. De gjorde ju tom en edit i uppgifts-beskrivningen, de la till "(and the frame of view follows the active cells in each cycle)", och jag förstod fortfarande inte.. Givetvis menade de att övre raden är y=0 i exemplet och y=1 efter en cykel, för y=0 hade inga aktiva kuber kvar..

Vidare hade jag stavat fel på en variabel, vilket såklart awk inte skrek på och hanterade som 0 istället.

Gå till inlägget

Ja gag satt en timme och klurade på varför jag inte får det som exemplet.
Exemplet är det fel på.
Men följer du reglerna så är det bara att lösa.

Är det fel med flit eller har någon klantat sig?

Rapportera Redigera

Citera flera Citera

2020-12-17 09:11

Permalänk

GLaDER

Medlem ★

Plats: *.home.arpa
Registrerad: Nov 2011

●

Skrivet av GLaDER:

Dag: 16
Språk: Go
Lösning: Main

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

Kod. Kod. Kod.

Idag blev det långt. Jag löste Del 1 ganska smärtfritt, men jag lyckades verkligen inte hålla tungan i rätt mun när jag skulle hantera olika sorters index och värden. Det blev superviktigt att använda riktigt tydliga variabelnamn, för jag blandade konstant ihop "indexet i en ticket", "värdet index" som jag höll reda på, etc. Inte ens nu, när allting fungera, är jag helt hundra på vad som är vad.

Vad värre är lade jag säkert en timme på en lösning som var inversen till den jag tillslut fick rätt svar med.

Kärnan i min fungerande lösning ser ni nedan.

for c, v := range constraints {
	lowList := util.MakeRange(v[0][0], v[0][1])
	highList := util.MakeRange(v[1][0], v[1][1])
	vRange := append(lowList, highList...)

	availIds := util.MakeRange(0, len(tickets[0])-1)

	for _, ticket := range tickets {
		for valueIdx, ticketValue := range ticket {
			if !util.IntInSlice(ticketValue, vRange) {
				availIds = util.RemoveIntByValue(valueIdx, availIds)				}
		}
	}
	constraintToRange[c] = append(constraintToRange[c], availIds...)
}

Grundpremissen är att jag har en lista: vRange, som innehåller alla giltiga värden för en viss constraint. För varje ticket skapar jag sedan en lista med alla möjliga index (availIds). Därefter kollar jag siffran på varje position i ticket. Om siffran inte återfinns i vRange tar jag bort den från availIds.

AoC inputen är gjord så att minst en constraint bara kommer ha en siffra i availIds. Så i en annan del av koden loopar jag helt enkelt över alla constraints. Om det bara finns ett värde i availIds är jag klar med det constraintet. Då tar jag bort det IDt från alla andra constraints och vipps är det minst en constraint som bara har ett värde igen.

Problemet med mitt initiala lösningsförslag var att jag gjorde tvärtom. Jag började med en tom lista och loopade igenom alla tickets. "Fungerar det här indexet? Ja. Lägg till." Förhoppningen var att ett index per constraint skulle vara "högst", men så blev det inte... Bläh.

Dold text

Gå till inlägget

Dag: 17
Språk: Go
Lösning: Main, Paket för Block

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

Jag fick ta hjälp av Internet för att lösa Del 1, men min slutliga lösning är väldigt inspirerad av Dag 11. Stora skillnaden från Dag 11 är:

jag använder en []Cube för att hålla koll på aktiva koordinater
jag använder map[Cube]int under själva simuleringen för att mappa koordinater till aktiva grannar

Den här lösningen är utökbar till godtyckligt många dimensioner, vilket gjorde steget mellan Del 1 och Del 2 trivial.

Dold text

Senast redigerat 2020-12-17 09:26

Visa signatur

:(){ :|:& };:

🏊🏻‍♂️ 🚴🏻‍♂️ 🏃🏻‍♂️ ☕

Får det lov att vara en kaffe?

Rapportera Redigera

Citera flera Citera (2)

2020-12-17 09:34

Permalänk

gibbon_

Medlem ★

Plats: Sydney
Registrerad: Aug 2003

●

Dag 17, awk.

$ <in awk -v num_cycles=6 -f d17p2.awk

d17p2.awk

{ split($1, v, ""); for (x in v) { if (v[x] == "#") { map[x" "NR" "1" "1] } } max_x = length(v); max_y = NR }
END {
	min_x = min_y = min_z = max_z = min_w = max_w = 1
	d[-1]; d[0]; d[1]
	for (x in d) { for (y in d) { for (z in d) { for (w in d) { dirs[x" "y" "z" "w] } } } }
	delete dirs[0" "0" "0" "0]

	for (cycle = 0; cycles < num_cycles; cycles++) {
		delete add
		delete rem
		for (x = min_x - 1; x <= max_x + 1; x++) {
			for (y = min_y - 1; y <= max_y + 1; y++) {
				for (z = min_z - 1; z <= max_z + 1; z++) {
					for (w = min_w - 1; w <= max_w + 1; w++) {
						c = x" "y" "z" "w
						cnt = 0
						for (dir in  dirs) {
							split(dir, d)
							cnt += x + d[1]" "y + d[2]" "z + d[3]" "w + d[4] in map
						}
						if (c in map && cnt != 2 && cnt != 3) { rem[c] }
						if (!(c in map) && cnt == 3) { add[c] }
					}
				}
			}
		}
		for (c in rem) { delete map[c] }
		for (c in add) {
			map[c]
			split(c, v)
			min_x = v[1] < min_x ? v[1] : min_x; max_x = v[1] > max_x ? v[1] : max_x
			min_y = v[2] < min_y ? v[2] : min_y; max_y = v[2] > max_y ? v[2] : max_y
			min_z = v[3] < min_z ? v[3] : min_z; max_z = v[3] > max_z ? v[3] : max_z
			min_w = v[4] < min_w ? v[4] : min_w; max_w = v[4] > max_w ? v[4] : max_w
		}
	}

	print length(map)
}

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

Rapportera Redigera

Citera flera Citera (1)

2020-12-17 09:52

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Dag: 17
Språk: Swift
Lösning: Github

Tänkte först att x- och y-dimensionen var oändlig genom att dessa koordinater wrappade, men det hade man ju insett var fel om man noterade att bredd/höjd i exemplet ökade vid andra cykeln...

$ swift run -c release
🌟 Part 1 : 359
⌚ Elapsed : 64 ms
🌟 Part 2 : 2228
⌚ Elapsed : 675 ms

Dold text

Visa signatur

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

Rapportera Redigera

Citera flera Citera (2)

2020-12-17 10:34

Permalänk

huggeMugg

Medlem

Registrerad: Dec 2020

●

Dag: 17
Språk: Nim
Lösning: Github

Jag fortsatte på gårdagens spår och använde sets för att hålla reda på vilka koordinater som var aktiva. Det förenklade framförallt när jag skulle kolla vilka inaktiva grannar som eventuellt skulle bli aktiva nästa cykel, det var bara att lägga till alla grannar i ett sets medan jag ändå loopade igenom dom när jag räknade antal grannar till de aktiva cellerna. Blev dock lite mycket repetition av koden då jag hårdkodat en Vec3 typ till Part1 så det blev en kopiering rakt av men byte till Vec4 då.

Part 1: 313
Part 2: 2640
Part1 ............................... 8.304 ms    ±0.313  x10
Part2 ............................. 302.407 ms    ±4.558  x10

Dold text

Rapportera Redigera

Citera flera Citera (1)

2020-12-17 12:38

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Dag: 17
Språk: C++/OpenMP
Lösning: Github

Lunchkul, mest för att det går. Maximal teoretisk speedup är antal unika x-dimensioner, varje kub för nästa generation kan ju beräknas oberoende och hålla delmängden av nya aktiva kuber på varje separat tråd för att sedan köra en union av alla delmängder på slutet.

Använder en annan dator i detta fall, MacOS/ARM64 saknar stöd för OpenMP än
Kör på en 3900X

$ ./day17 
Part 1 : 359
Took : 10ms
Part 2 : 2228
Took : 28ms

Dold text

Visa signatur

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

Rapportera Redigera

Citera flera Citera

2020-12-17 14:03

Permalänk

Ingetledigtnamn

Medlem ★

Plats: Uppsala
Registrerad: Dec 2008

●

Dag 17. NumPy. Inte supereffektiv, men ganska elegant.

Lösningarna blev ju ganska lika.

import numpy as np

a = np.array([[1 if x == '#' else 0 for x in line.strip()]
              for line in open("input")])[np.newaxis,:,:]
for i in range(6):
    a = np.pad(a, 1, mode='constant', constant_values=(0,0))
    a2 = np.pad(a, 1, mode='constant', constant_values=(0,0))
    xs, ys, zs = a.shape
    ns = np.array([[[np.sum(a2[x:x+3, y:y+3, z:z+3]) - a[x,y,z]
                     for z in range(zs)]
                    for y in range(ys)]
                   for x in range(xs)])
    n3 = np.where(ns == 3,1,0)
    n2 = np.where(ns == 2,1,0)
    a = a * (n2 + n3) + (1 - a) * n3
print(np.sum(a))

a = np.array([[1 if x == '#' else 0 for x in line.strip()]
              for line in open("input")])[np.newaxis,np.newaxis,:,:]
for i in range(6):
    a = np.pad(a, 1, mode='constant', constant_values=(0,0))
    a2 = np.pad(a, 1, mode='constant', constant_values=(0,0))
    xs, ys, zs, ws = a.shape
    ns = np.array([[[[np.sum(a2[x:x+3, y:y+3, z:z+3, w:w+3])
                      - a[x,y,z,w]
                      for w in range(ws)]
                     for z in range(zs)]
                    for y in range(ys)]
                   for x in range(xs)])
    n3 = np.where(ns == 3,1,0)
    n2 = np.where(ns == 2,1,0)
    a = a * (n2 + n3) + (1 - a) * n3
print(np.sum(a))

Dold text

Rapportera Redigera

Citera flera Citera (1)

🌟 Advent of Code (AoC) 2020 🌟

Externa nyheter

Spelnyheter från FZ