🌟 Advent of Code (AoC) 2022 🌟

2022-12-11 12:54

Permalänk

henrikj82

Medlem

Registrerad: Jul 2005

●

Dag 10
Språk: C#

Dag 10 var oväntat lätt, skönt efter att ha haft sådana problem med dag 9.

        public static int CycleCheck(int cycle, int x)
        {
            cycle = cycle + 1;
            if (cycle == 20) return cycle * x;
            if (cycle == 60) return cycle * x;
            if (cycle == 100) return cycle * x;
            if (cycle == 140) return cycle * x;
            if (cycle == 180) return cycle * x;
            if (cycle == 220) return cycle * x;
            return 0;
        }
        public static string CrtCheck(string crt, int cycle, int x)
        {            
            if (crt.Length<40 && cycle == x || x == cycle - 1 || x == cycle + 1) return "#";
            else if (crt.Length < 80 && cycle-40 == x || x == cycle-40 - 1 || x == cycle-40 + 1) return "#";
            else if (crt.Length < 120 && cycle-80 == x || x == cycle-80 - 1 || x == cycle-80 + 1) return "#";
            else if (crt.Length < 160 && cycle-120 == x || x == cycle - 120 - 1 || x == cycle - 120 + 1) return "#";
            else if (crt.Length < 200 && cycle == x - 160 || x == cycle - 160-1 || x == cycle - 160 + 1) return "#";
            else if (crt.Length < 240 && cycle - 200 == x || x == cycle - 200 - 1 || x == cycle - 200 + 1) return "#";
            else return ".";
        }
        public static void Day10()
        {
            String[] data = File.ReadAllLines("Day10.txt");
            int step1 = 0;
            int x = 1;
            int cycle = 0;
            string crt="";
            for(int i = 0; i < data.Length; i++)
            {
                if(i==0) crt = crt + CrtCheck(crt, cycle, x);
                string[] check = data[i].Split(" ");                                
                if (check[0] == "noop")
                {                    
                    cycle++;
                    step1 = step1 + CycleCheck(cycle, x);
                    crt = crt + CrtCheck(crt, cycle, x);
                }
                if (check[0]=="addx")
                {                  
                    cycle++;
                    step1 = step1 + CycleCheck(cycle,x);
                    crt = crt + CrtCheck(crt, cycle, x);                    
                    cycle++;
                    x = x + int.Parse(check[1]);
                    step1 = step1 + CycleCheck(cycle,x);
                    crt = crt + CrtCheck(crt, cycle, x);
                }
            }       
            Console.WriteLine();
            Console.WriteLine("Day10");
            Console.WriteLine("Step1 " + step1 + " Step2 ");
            Console.WriteLine();
            for (int i = 0; i < crt.Length; i++)
            {
                if (i % 40 == 0 && i != 0) Console.WriteLine();
                Console.Write(crt[i]);
            }
        }

Dold text

Rapportera Redigera

Citera flera Citera

2022-12-11 13:17

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Skrivet av Flexbert:

Dag: 11
Språk: Go

Fru och barn har magsjuka, så det var lite svårt att få tid att fokusera.

Många slice operationer står säkert för majoriteten av tiden, får se ifall jag får tid och göra något åt det.

pkg: aoc2022/11/a
cpu: Intel(R) Core(TM) i7-7920HQ CPU @ 3.10GHz
BenchmarkPartOne-8   	   34596	     36360 ns/op
BenchmarkPartTwo-8   	      43	  27310350 ns/op

package main

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

type Monkey struct {
	StartItems      []int
	Operation       func(a int, b int) int // new = old * 19
	OpValB          int
	TestDivideByVal int
	TestTrueMonkey  int
	TestFalseMonkey int
	InspectCount    int
}

func mul(old int, b int) int    { return old * b }
func mulOld(old int, b int) int { return old * old }
func add(old int, b int) int    { return old + b }
func addOld(old int, b int) int { return old + old }

func calcTopTwoMonkeyInspections(monkeys []Monkey, rounds int, reduceFactor int) int {
	for c := 0; c < rounds; c++ {
		for i, m := range monkeys {
			for _, val := range monkeys[i].StartItems {
				worryLevel := monkeys[i].Operation(val, m.OpValB)
				if reduceFactor == 3 {
					worryLevel /= reduceFactor
				} else {
					worryLevel %= reduceFactor
				}
				if worryLevel%m.TestDivideByVal == 0 {
					monkeys[m.TestTrueMonkey].StartItems = append(monkeys[m.TestTrueMonkey].StartItems, worryLevel)
				} else {
					monkeys[m.TestFalseMonkey].StartItems = append(monkeys[m.TestFalseMonkey].StartItems, worryLevel)
				}
				monkeys[i].StartItems = monkeys[i].StartItems[1:]
				monkeys[i].InspectCount++
			}
		}
	}

	inspectCounts := make([]int, len(monkeys))
	for _, m := range monkeys {
		inspectCounts = append(inspectCounts, m.InspectCount)
	}
	sort.Sort(sort.Reverse(sort.IntSlice(inspectCounts)))
	return inspectCounts[0]* inspectCounts[1]
}

func getPartOne(monkeys []Monkey) int {
	return calcTopTwoMonkeyInspections(monkeys, 20, 3)
}

func getPartTwo(monkeys []Monkey) int {
	product := 1
	for _, m := range monkeys {
		product *= m.TestDivideByVal
	}
	return calcTopTwoMonkeyInspections(monkeys, 10000, product)
}

func getRows(filename string) []Monkey {
	file, err := os.Open(filename)
	if err != nil {
		panic(err)
	}
	defer file.Close()
	scanner := bufio.NewScanner(file)
	monkeys := make([]Monkey, 0)
	monkeyId := 0
	for scanner.Scan() {
		row := scanner.Text()
		if strings.Contains(row, "Monkey") {
			fmt.Sscanf(row, "Monkey %d:",
				&monkeyId)
			m := Monkey{}
			monkeys = append(monkeys, m)
		} else if strings.Contains(row, "Starting items:") {
			numberPart := strings.Split(row, ":")[1]
			numbers := strings.Split(numberPart, ",")
			for _, num := range numbers {
				val, err := strconv.Atoi(strings.TrimSpace(num))
				if err != nil {
					panic(err)
				}
				monkeys[monkeyId].StartItems = append(monkeys[monkeyId].StartItems, val)
			}
		} else if strings.Contains(row, "Operation:") {
			formulaPart := strings.Split(row, ":")[1]
			var f func(a int, b int) int
			if strings.Contains(formulaPart, "new = old + old") {
				f = addOld
			} else if strings.Contains(formulaPart, "new = old * old") {
				f = mulOld
			} else if strings.Contains(formulaPart, "new = old * ") {
				f = mul
				num := strings.Replace(formulaPart, "new = old *", "", 1)
				val, err := strconv.Atoi(strings.TrimSpace(num))
				if err != nil {
					panic(err)
				}
				monkeys[monkeyId].OpValB = val
			} else if strings.Contains(formulaPart, "new = old + ") {
				f = add
				num := strings.Replace(formulaPart, "new = old +", "", 1)
				val, err := strconv.Atoi(strings.TrimSpace(num))
				if err != nil {
					panic(err)
				}
				monkeys[monkeyId].OpValB = val
			}
			monkeys[monkeyId].Operation = f
		} else if strings.Contains(row, "Test: divisible by ") {
			fmt.Sscanf(row, "  Test: divisible by %d", &monkeys[monkeyId].TestDivideByVal)
		} else if strings.Contains(row, "If true: throw to monkey") {
			fmt.Sscanf(row, "    If true: throw to monkey %d", &monkeys[monkeyId].TestTrueMonkey)
		} else if strings.Contains(row, "If false: throw to monkey") {
			fmt.Sscanf(row, "    If false: throw to monkey %d", &monkeys[monkeyId].TestFalseMonkey)
		}
	}
	return monkeys
}

func main() {
	fmt.Println("Part one:", getPartOne(getRows("../input.txt")))
	fmt.Println("Part two:", getPartTwo(getRows("../input.txt")))
}

Dold text

Gå till inlägget

Du skrev ju tidigare att M1 rimligen borde vara betydligt snabbare än din Intel CPU.

I de riktigt enkla fallen har vi sett att så inte är fallet. Nu med lite mer komplicerade fall ser det annorlunda ut.

Är nog inte dina slicing operationer som är problemet, våra lösningar ligger väldigt nära varandra sett till struktur. Kör jag din kod blir också benchmark-resultaten likvärdiga mina vilket är ca 3x snabbare än på din dator

goos: darwin
goarch: arm64
pkg: aoc2022/x
BenchmarkPartOne-8   	  101563	     11934 ns/op	   29032 B/op	     154 allocs/op
BenchmarkPartTwo-8   	     133	   8952131 ns/op	11062305 B/op	  160602 allocs/op
PASS
ok  	aoc2022/x	4.709s

Benchmark med Flexberts kod

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

2022-12-11 13:19

Permalänk

Flexbert

Medlem

Plats: Oslo
Registrerad: Okt 2001

●

Skrivet av Yoshman:

Du skrev ju tidigare att M1 rimligen borde vara betydligt snabbare än din Intel CPU.

I de riktigt enkla fallen har vi sett att så inte är fallet, men nu mer lite mer komplicerade fall ser det annorlunda ut.

Är nog inte dina slicing operationer som är problemet, våra lösningar ligger väldigt nära varandra sett till struktur. Kör jag din kod blir också benchmark-resultaten likvärdiga mina vilket är ca 3x snabbare än på din dator

goos: darwin
goarch: arm64
pkg: aoc2022/x
BenchmarkPartOne-8   	  101563	     11934 ns/op	   29032 B/op	     154 allocs/op
BenchmarkPartTwo-8   	     133	   8952131 ns/op	11062305 B/op	  160602 allocs/op
PASS
ok  	aoc2022/x	4.709s

Benchmark med Flexberts kod

Gå till inlägget

Nice, ändrade den lite och fick halva tiden

Rapportera Redigera

Citera flera Citera

2022-12-11 13:29

Permalänk

Mickur

Medlem ★

Plats: Örebro
Registrerad: Mar 2007

●

Skrivet av Yoshman:

Dag: 11
Språk: Go

package main

import (
	"encoding/csv"
	"fmt"
	"strconv"
	"strings"
)

type WorryLevel uint64
type Items []WorryLevel
type WorryLevelAdjustment func(WorryLevel) WorryLevel
type Monkey struct {
	items       Items
	inspect     WorryLevelAdjustment
	divisor     WorryLevel
	recipients  [2]int
	inspections WorryLevel
}
type Monkeys []Monkey

// Item receiver functions

func (items Items) empty() bool {
	return len(items) == 0
}

func (items *Items) enqueue(item WorryLevel) {
	*items = append(*items, item)
}

func (items *Items) dequeue() WorryLevel {
	first := (*items)[0]
	*items = (*items)[1:]
	return first
}

// Monkeys receiver functions

func (monkeys *Monkeys) doRound(reliefValue WorryLevel) {
	for m := 0; m < len(*monkeys); m++ {
		monkey := &(*monkeys)[m]
		for !monkey.items.empty() {
			newWorryLevel := monkey.inspect(monkey.items.dequeue())
			if reliefValue == 3 {
				newWorryLevel /= reliefValue
			} else {
				newWorryLevel %= reliefValue
			}
			recipient := monkey.recipients[1]
			if newWorryLevel%monkey.divisor == 0 {
				recipient = monkey.recipients[0]
			}
			(*monkeys)[recipient].items.enqueue(newWorryLevel)
			monkey.inspections++
		}
	}
}

func (monkeys *Monkeys) doNRounds(n int, reliefDivisor WorryLevel) {
	for round := 0; round < n; round++ {
		monkeys.doRound(reliefDivisor)
	}
}

func (monkeys Monkeys) clone() Monkeys {
	clones := Monkeys{}
	for _, m := range monkeys {
		clone := m
		m.items = append(Items{}, m.items...)
		clones = append(clones, clone)
	}
	return clones
}

// Functions

func monkeyBusinessAfter(monkeys Monkeys, rounds int, reliefDivisor WorryLevel) WorryLevel {
	monkeys.doNRounds(rounds, reliefDivisor)
	return monkeyBusiness(monkeys)
}

func monkeyBusiness(monkeys Monkeys) WorryLevel {
	wls := [2]WorryLevel{}
	for _, monkey := range monkeys {
		if wls[0] < monkey.inspections {
			wls[1] = wls[0]
			wls[0] = monkey.inspections
		} else if wls[1] < monkey.inspections {
			wls[1] = monkey.inspections
		}
	}
	return wls[0] * wls[1]
}

func reliefValue(monkeys Monkeys) WorryLevel {
	rd := WorryLevel(1)
	for _, monkey := range monkeys {
		rd *= monkey.divisor
	}
	return rd
}

func day11(input []string) {
	monkeys := parseMonkeys(input)
	fmt.Println(monkeyBusinessAfter(monkeys.clone(), 20, 3))
	fmt.Println(monkeyBusinessAfter(monkeys, 10000, reliefValue(monkeys)))
}

func init() {
	Solutions[11] = day11
}

// Parsing of input

func parseWorryLevel(s string) WorryLevel {
	if wl, err := strconv.Atoi(s); err == nil {
		return WorryLevel(wl)
	} else {
		panic("Failed to parse worry level")
	}
}

func parseMonkeyItems(line string) Items {
	items := Items{}
	parts := strings.Split(line, ": ")
	r := csv.NewReader(strings.NewReader(parts[1]))
	r.TrimLeadingSpace = true
	record, err := r.Read()
	if err != nil {
		panic("Failed to parse monkey items")
	}
	for _, worryLevel := range record {
		items.enqueue(parseWorryLevel(worryLevel))
	}
	return items
}

func parseWorryLevelAdjustment(line string) WorryLevelAdjustment {
	parts := strings.Fields(line)
	secondArg := parts[5]
	if secondArg == "old" {
		return func(old WorryLevel) WorryLevel { return old * old }
	}
	arg := parseWorryLevel(secondArg)
	operator := parts[4]
	if operator == "*" {
		return func(old WorryLevel) WorryLevel { return old * arg }
	}
	return func(old WorryLevel) WorryLevel { return old + arg }
}

func parseDivisor(line string) WorryLevel {
	return parseWorryLevel(strings.Fields(line)[3])
}

func parseRecipient(line string) int {
	return int(parseWorryLevel(strings.Fields(line)[5]))
}

func parseMonkey(input []string, row *int) Monkey {
	monkey := Monkey{}
	monkey.items = parseMonkeyItems(input[*row+1])
	monkey.inspect = parseWorryLevelAdjustment(input[*row+2])
	monkey.divisor = parseDivisor(input[*row+3])
	monkey.recipients[0] = parseRecipient(input[*row+4])
	monkey.recipients[1] = parseRecipient(input[*row+5])
	*row += 7
	return monkey
}

func parseMonkeys(input []string) Monkeys {
	monkeys := Monkeys{}
	row := 0
	for row < len(input) {
		monkeys = append(monkeys, parseMonkey(input, &row))
	}
	return monkeys
}

Lösning

Läste del 2 femtielva gånger för att försöka hitta beskrivningen på vad "dividera med 3" skulle ersättas med.

När jag övertygat mig själv om att det inte fanns något "färdigt recept" blev nästa steg att plocka ut stickprov av exemplen och börja testa vad som gav rätt svar.

Enda egentligen konkreta hint:en är att alla tal i "Test: divisible by ..." är primtal

Inte en favorit-dag. Speciellt inte när parsning tar en hyfsat stor del av lösningen, vill alltid kunna resonera om koden och tycker det är betydligt lättare om man stoppar in saker i namngivna strukturer.

Kommentarer

func BenchmarkDay11_parsing(b *testing.B) {
	input := inputAsString(11)
	for n := 0; n < b.N; n++ {
		parseMonkeys(input)
	}
}

func BenchmarkDay11_part1(b *testing.B) {
	monkeys := parseMonkeys(inputAsString(11))
	for n := 0; n < b.N; n++ {
		monkeyBusinessAfter(monkeys.clone(), 20, 3)
	}
}

func BenchmarkDay11_part2(b *testing.B) {
	monkeys := parseMonkeys(inputAsString(11))
	for n := 0; n < b.N; n++ {
		monkeyBusinessAfter(monkeys.clone(), 10000, reliefValue(monkeys))
	}
}

M1 MacMini

goos: darwin
goarch: arm64
pkg: aoc2022
BenchmarkDay11_parsing-8   	  129234	      9394 ns/op	   41232 B/op	     178 allocs/op
BenchmarkDay11_part1-8     	   94996	     12582 ns/op	   27352 B/op	     280 allocs/op
BenchmarkDay11_part2-8     	     138	   8665079 ns/op	11092312 B/op	  161090 allocs/op
PASS
ok  	aoc2022	5.920s

Benchmark

Gå till inlägget

Hej!
Skulle du kunna berätta vad varje kolumn i benchmarkoutputten är? Jag antar att dom sista tre är hur många nanosekunder det tar att köra, hur mycket minne som allokeras samt antal allokeringar? Men det första talet där är jag osäker på!

Edit: Kan det måhända vara hur många gånger den hinner köra under en viss tid?

Senast redigerat 2022-12-11 13:43

Visa signatur

CPU: 7950X 5GHz@1.1v | RAM: 32GB 6000MHz CL36 | GPU: KFA² 3090 SG w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3 / Supreme CD-99

Rapportera Redigera

Citera flera Citera

2022-12-11 13:56

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Skrivet av Mickur:

Hej!
Skulle du kunna berätta vad varje kolumn i benchmarkoutputten är? Jag antar att dom sista tre är hur många nanosekunder det tar att köra, hur mycket minne som allokeras samt antal allokeringar? Men det första talet där är jag osäker på!

Edit: Kan det måhända vara hur många gånger den hinner köra under en viss tid?

Gå till inlägget

1a namnet på testet
2a antal iterationer som kördes
3e (ns/op) tiden att köra en iteration
4e (B/op) är hur mycket minne som allokeras per iteration
5e (allocs/op) är antalet gånger som minne allokeras per iteration

Antalet iterationer bestäms av ramverket så totaltiden blir "vettig", är därför generella strukturen är

    // one time setup-code
    for n := 0; n < b.N; n++ { /* thing(s) to benchmark */ }

Du får gärna göra en liknade beskrivning av det ramverk du kör för C# (använder främst C# ihop med Unity, så har inte superkoll på övriga dotnet ramverk + kanske något mer än jag som undrar).

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)

2022-12-11 13:59

Permalänk

Mickur

Medlem ★

Plats: Örebro
Registrerad: Mar 2007

●

Skrivet av Yoshman:

1a namnet på testet
2a antal iterationer som kördes
3e (ns/op) tiden att köra en iteration
4e (B/op) är hur mycket minne som allokeras per iteration
5e (allocs/op) är antalet gånger som minne allokeras per iteration

Antalet iterationer bestäms av ramverket så totaltiden blir "vettig", är därför generella strukturen är

    // one time setup-code
    for n := 0; n < b.N; n++ { /* thing(s) to test */ }

Du får gärna göra en liknade beskrivning av det ramverk du kör för C# (använder främst C# ihop med Unity, så har inte superkoll på övriga dotnet ramverk + kanske något mer än jag som undrar).

Gå till inlägget

Låter som att det var precis som jag trodde då!

Här är vad jag lyckats få ner min lösning till just nu

BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22621.900)
AMD Ryzen 9 7950X, 1 CPU, 32 logical and 16 physical cores
.NET SDK=7.0.100
  [Host]   : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2
  .NET 7.0 : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2

Job=.NET 7.0  Runtime=.NET 7.0  

|       Method |            Mean |         Error |        StdDev |   Gen0 |   Gen1 | Allocated |
|------------- |----------------:|--------------:|--------------:|-------:|-------:|----------:|
|        Parse |        846.3 ns |       6.24 ns |       5.84 ns | 0.2317 | 0.0029 |   3.79 KB |
| SolvePartOne |     25,957.1 ns |     129.32 ns |     120.97 ns | 0.3662 |      - |   6.39 KB |
| SolvePartTwo | 12,578,633.6 ns | 239,218.31 ns | 223,764.95 ns |      - |      - |   5.23 KB |

// * Legends *
  Mean      : Arithmetic mean of all measurements
  Error     : Half of 99.9% confidence interval
  StdDev    : Standard deviation of all measurements
  Gen0      : GC Generation 0 collects per 1000 operations
  Gen1      : GC Generation 1 collects per 1000 operations
  Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B)
  1 ns      : 1 Nanosecond (0.000000001 sec)

Dold text

Macbook Air får också lite kärlek! Mycket intressanta resultat!

BenchmarkDotNet=v0.13.2, OS=macOS 13.0.1 (22A400) [Darwin 22.1.0]
Apple M1, 1 CPU, 8 logical and 8 physical cores
.NET SDK=7.0.100
  [Host]   : .NET 7.0.0 (7.0.22.51805), Arm64 RyuJIT AdvSIMD
  .NET 7.0 : .NET 7.0.0 (7.0.22.51805), Arm64 RyuJIT AdvSIMD

Job=.NET 7.0  Runtime=.NET 7.0  

|       Method |         Mean |       Error |      StdDev |   Gen0 |   Gen1 | Allocated |
|------------- |-------------:|------------:|------------:|-------:|-------:|----------:|
|        Parse |     1.069 us |   0.0133 us |   0.0125 us | 0.6180 | 0.0057 |   3.79 KB |
| SolvePartOne |    18.691 us |   0.0644 us |   0.0538 us | 1.0376 |      - |   6.39 KB |
| SolvePartTwo | 9,102.675 us | 134.0734 us | 125.4123 us |      - |      - |   5.24 KB |

// * Hints *
Outliers
  Benchmarker.SolvePartOne: .NET 7.0 -> 2 outliers were removed (18.97 us, 19.08 us)

// * Legends *
  Mean      : Arithmetic mean of all measurements
  Error     : Half of 99.9% confidence interval
  StdDev    : Standard deviation of all measurements
  Gen0      : GC Generation 0 collects per 1000 operations
  Gen1      : GC Generation 1 collects per 1000 operations
  Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B)
  1 us      : 1 Microsecond (0.000001 sec)

Dold text

Edit: Lyckats få ner tiden lite genom att höja den initiala storleken på ett par collections. Parsingen ser riktigt skarp ut nu. Lösningarna har nog ett gäng optimeringar kvar att hitta.

Senast redigerat 2022-12-11 15:25

Visa signatur

CPU: 7950X 5GHz@1.1v | RAM: 32GB 6000MHz CL36 | GPU: KFA² 3090 SG w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3 / Supreme CD-99

Rapportera Redigera

Citera flera Citera

2022-12-11 14:10

Permalänk

Trihxeem

Medlem ★

Plats: Sverige
Registrerad: Dec 2007

●

Dag 11:
Löste första delen hyfsat lätt men har INGEN aning vad man ska göra i del 2, förstår inte en vad själva problemet är.
Så: I'm out, lycka till ni som fortsätter

Visa signatur

Att förespråka Mac på Swec är som att förespråka hybridbilar på en raggarträff i Mora.

Rapportera Redigera

Citera flera Citera

2022-12-11 14:11

Permalänk

Mickur

Medlem ★

Plats: Örebro
Registrerad: Mar 2007

●

Skrivet av Trihxeem:

Dag 11:
Löste första delen hyfsat lätt men har INGEN aning vad man ska göra i del 2, förstår inte en vad själva problemet är.
Så: I'm out, lycka till ni som fortsätter

Gå till inlägget

Lite ledtrådar ifall du ångrar dig!

Hur stora tal klarar din valda datatyp av? Kan du höja taket? Kan du kanske göra talen du jobbar med mindre så du inte slår i taket?

Dold text

Visa signatur

CPU: 7950X 5GHz@1.1v | RAM: 32GB 6000MHz CL36 | GPU: KFA² 3090 SG w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3 / Supreme CD-99

Rapportera Redigera

Citera flera Citera

2022-12-11 16:36

Permalänk

Skyclaw

Medlem ★

Registrerad: Jun 2006

●

Dag: 11
Språk: C++

Del 1 var straight forward och skoj, del 2 stökade till det. Inte ens uint64 var tillräckligt för att lagra datan ens i 20 iterationer så fick göra en lösning med en "super-modulus" där m.test är nämnaren i test-divisionen:

  uint64_t superMod = 1;
  for (Monkey m : monkeys) {
    superMod *= m.test;
  }

Använde den sedan i loopen:

while (!monkeys[i].holdingItems.empty()) {
        uint64_t item = monkeys[i].holdingItems.front();
        monkeys[i].counter++;
        monkeys[i].holdingItems.pop();
        item = doOperation(item, monkeys[i].operation);
        item = item % superMod;
        if (item % monkeys[i].test == 0ll) {
          monkeys[monkeys[i].ifTrueThrowTo].holdingItems.push(item);
        } else {
          monkeys[monkeys[i].ifFalseThrowTo].holdingItems.push(item);
        }

Hela koden för dagen följer nedan.

#include <queue>
#include <vector>

#include "../AoCHelper/AoCHelper.h"

struct Monkey {
  std::queue<uint64_t> holdingItems{};
  std::string operation;
  uint64_t test;
  int ifTrueThrowTo;
  int ifFalseThrowTo;
  size_t counter{0};
};

uint64_t doOperation(uint64_t item, std::string& operation) {
  std::vector<std::string> splitOperation = myLib::split(operation, ' ');
  uint64_t lhs{};
  uint64_t rhs{};
  if (splitOperation[3] == "old") {
    lhs = item;
  } else {
    lhs = std::stoll(splitOperation[3]);
  }

  if (splitOperation[5] == "old") {
    rhs = item;
  } else {
    rhs = std::stoll(splitOperation[5]);
  }

  if (splitOperation[4] == "*") {
    return lhs * rhs;
  } else if (splitOperation[4] == "+") {
    return lhs + rhs;
  }
  return 0;
}

std::vector<Monkey> parseInput(std::vector<std::string> input) {
  std::vector<Monkey> monkeys{};
  for (std::string row : input) {
    if (row == "") {
      continue;
    }
    std::vector<std::string> splitRow = myLib::split(row, ' ');
    if (row.substr(0, 6) == "Monkey") {
      Monkey m{};
      monkeys.push_back(m);
    } else if (splitRow[2] == "Starting") {
      for (int i = 4; i < splitRow.size(); i++) {
        if (splitRow[i].back() == ',') {
          splitRow[i].pop_back();
        }
        monkeys.back().holdingItems.push(std::stoll(splitRow[i]));
      }
    } else if (splitRow[2] == "Operation:") {
      std::string operation = myLib::split(row, ':')[1];
      monkeys.back().operation = operation;
    } else if (splitRow[2] == "Test:") {
      monkeys.back().test = std::stoll(splitRow[5]);
    } else if (splitRow[4] == "If") {
      if (splitRow[5] == "true:") {
        monkeys.back().ifTrueThrowTo = std::stoi(splitRow[9]);
      } else {
        monkeys.back().ifFalseThrowTo = std::stoi(splitRow[9]);
      }
    }
  }
  return monkeys;
}

void puzzle_one(std::vector<std::string> input) {
  int answer{};
  std::vector<Monkey> monkeys = parseInput(input);
  for (int round = 0; round < 20; round++) {
    for (int i = 0; i < monkeys.size(); i++) {
      while (!monkeys[i].holdingItems.empty()) {
        uint64_t item = monkeys[i].holdingItems.front();
        monkeys[i].counter++;
        monkeys[i].holdingItems.pop();
        item = doOperation(item, monkeys[i].operation);
        item = item / 3;
        if (item % monkeys[i].test == 0) {
          monkeys[monkeys[i].ifTrueThrowTo].holdingItems.push(item);
        } else {
          monkeys[monkeys[i].ifFalseThrowTo].holdingItems.push(item);
        }
      }
    }
  }
  std::sort(
      monkeys.begin(), monkeys.end(),
      [](const Monkey& a, const Monkey& b) { return a.counter > b.counter; });
  answer = monkeys[0].counter * monkeys[1].counter;
  std::cout << "Puzzle one: " << answer << std::endl;
}

void puzzle_two(std::vector<std::string> input) {
  size_t answer{};
  std::vector<Monkey> monkeys = parseInput(input);
  uint64_t superMod = 1;
  for (Monkey m : monkeys) {
    superMod *= m.test;
  }
  for (int round = 0; round < 10000; round++) {
    for (int i = 0; i < monkeys.size(); i++) {
      while (!monkeys[i].holdingItems.empty()) {
        uint64_t item = monkeys[i].holdingItems.front();
        monkeys[i].counter++;
        monkeys[i].holdingItems.pop();
        item = doOperation(item, monkeys[i].operation);
        item = item % superMod;
        if (item % monkeys[i].test == 0ll) {
          monkeys[monkeys[i].ifTrueThrowTo].holdingItems.push(item);
        } else {
          monkeys[monkeys[i].ifFalseThrowTo].holdingItems.push(item);
        }
      }
    }
  }
  std::sort(
      monkeys.begin(), monkeys.end(),
      [](const Monkey& a, const Monkey& b) { return a.counter > b.counter; });
  answer = monkeys[0].counter * monkeys[1].counter;
  std::cout << "Puzzle two: " << answer << std::endl;
}

int main() {
  std::vector<std::string> exampleInput{"Monkey 0:",
                                        "  Starting items: 79, 98",
                                        "  Operation: new = old * 19",
                                        "  Test: divisible by 23",
                                        "    If true: throw to monkey 2",
                                        "    If false: throw to monkey 3",
                                        "",
                                        "Monkey 1:",
                                        "  Starting items: 54, 65, 75, 74",
                                        "  Operation: new = old + 6",
                                        "  Test: divisible by 19",
                                        "    If true: throw to monkey 2",
                                        "    If false: throw to monkey 0",
                                        "",
                                        "Monkey 2:",
                                        "  Starting items: 79, 60, 97",
                                        "  Operation: new = old * old",
                                        "  Test: divisible by 13",
                                        "    If true: throw to monkey 1",
                                        "    If false: throw to monkey 3",
                                        "",
                                        "Monkey 3:",
                                        "  Starting items: 74",
                                        "  Operation: new = old + 3",
                                        "  Test: divisible by 17",
                                        "    If true: throw to monkey 0",
                                        "    If false: throw to monkey 1"};
  AoCHelper a1{"2022", "11"};
  std::vector<std::string> result = a1.get_input();
  puzzle_one(result);
  puzzle_two(result);
}

Dold text

Rapportera Redigera

Citera flera Citera

2022-12-11 16:43

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Skrivet av Mickur:

Låter som att det var precis som jag trodde då!

Här är vad jag lyckats få ner min lösning till just nu

BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22621.900)
AMD Ryzen 9 7950X, 1 CPU, 32 logical and 16 physical cores
.NET SDK=7.0.100
  [Host]   : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2
  .NET 7.0 : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2

Job=.NET 7.0  Runtime=.NET 7.0  

|       Method |            Mean |         Error |        StdDev |   Gen0 |   Gen1 | Allocated |
|------------- |----------------:|--------------:|--------------:|-------:|-------:|----------:|
|        Parse |        846.3 ns |       6.24 ns |       5.84 ns | 0.2317 | 0.0029 |   3.79 KB |
| SolvePartOne |     25,957.1 ns |     129.32 ns |     120.97 ns | 0.3662 |      - |   6.39 KB |
| SolvePartTwo | 12,578,633.6 ns | 239,218.31 ns | 223,764.95 ns |      - |      - |   5.23 KB |

// * Legends *
  Mean      : Arithmetic mean of all measurements
  Error     : Half of 99.9% confidence interval
  StdDev    : Standard deviation of all measurements
  Gen0      : GC Generation 0 collects per 1000 operations
  Gen1      : GC Generation 1 collects per 1000 operations
  Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B)
  1 ns      : 1 Nanosecond (0.000000001 sec)

Dold text

Macbook Air får också lite kärlek! Mycket intressanta resultat!

BenchmarkDotNet=v0.13.2, OS=macOS 13.0.1 (22A400) [Darwin 22.1.0]
Apple M1, 1 CPU, 8 logical and 8 physical cores
.NET SDK=7.0.100
  [Host]   : .NET 7.0.0 (7.0.22.51805), Arm64 RyuJIT AdvSIMD
  .NET 7.0 : .NET 7.0.0 (7.0.22.51805), Arm64 RyuJIT AdvSIMD

Job=.NET 7.0  Runtime=.NET 7.0  

|       Method |         Mean |       Error |      StdDev |   Gen0 |   Gen1 | Allocated |
|------------- |-------------:|------------:|------------:|-------:|-------:|----------:|
|        Parse |     1.069 us |   0.0133 us |   0.0125 us | 0.6180 | 0.0057 |   3.79 KB |
| SolvePartOne |    18.691 us |   0.0644 us |   0.0538 us | 1.0376 |      - |   6.39 KB |
| SolvePartTwo | 9,102.675 us | 134.0734 us | 125.4123 us |      - |      - |   5.24 KB |

// * Hints *
Outliers
  Benchmarker.SolvePartOne: .NET 7.0 -> 2 outliers were removed (18.97 us, 19.08 us)

// * Legends *
  Mean      : Arithmetic mean of all measurements
  Error     : Half of 99.9% confidence interval
  StdDev    : Standard deviation of all measurements
  Gen0      : GC Generation 0 collects per 1000 operations
  Gen1      : GC Generation 1 collects per 1000 operations
  Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B)
  1 us      : 1 Microsecond (0.000001 sec)

Dold text

Edit: Lyckats få ner tiden lite genom att höja den initiala storleken på ett par collections. Parsingen ser riktigt skarp ut nu. Lösningarna har nog ett gäng optimeringar kvar att hitta.

Gå till inlägget

Undrar om jag tog en väldigt omväg... Tänkte att det är tillfälle att lura ut hur man använder BenchmarkDotNet.

Fråga: vilka modifikationer gör du för att testa ditt program? Fick plocka ned ditt program i delar och stoppa in i ramverket för att få det att fungera, tror det ändå blev rätt i slutändan (givet att du kör med 7950X verkar det som Microsoft tillslut fått ordning på ARM64 prestanda, min M1Pro laptop är inte speciellt långt efter din 7950X )

BenchmarkDotNet=v0.12.1, OS=macOS 13.0.1 (22A400) [Darwin 22.1.0]
Apple M1 Pro, 1 CPU, 10 logical and 10 physical cores
.NET Core SDK=7.0.100
  [Host]     : .NET Core 6.0.11 (CoreCLR 6.0.1122.52304, CoreFX 6.0.1122.52304), Arm64 RyuJIT
  DefaultJob : .NET Core 6.0.11 (CoreCLR 6.0.1122.52304, CoreFX 6.0.1122.52304), Arm64 RyuJIT


|       Method |         Mean |     Error |    StdDev |
|------------- |-------------:|----------:|----------:|
| SolvePartOne |     31.17 us |  0.060 us |  0.056 us |
| SolvePartTwo | 13,830.25 us | 34.804 us | 32.555 us |

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  1 us   : 1 Microsecond (0.000001 sec)

Pushade mina saker till GitHub, exempel på hur tester + benchmarks ser ut för dag 11 finns här

Go 1.18 och .Net Core 7 verkar prestera väldigt snarlikt i den här typen av kod, i alla fall på MacOS.

Edit: ah, fanns flera versioner. Körde dotnet koden från denna post så mitt resultat ska väl jämföras mot detta

BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22621.900)
AMD Ryzen 9 7950X, 1 CPU, 32 logical and 16 physical cores
.NET SDK=7.0.100
  [Host]   : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2
  .NET 7.0 : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2

Job=.NET 7.0  Runtime=.NET 7.0  

|       Method |         Mean |      Error |     StdDev |   Gen0 | Allocated |
|------------- |-------------:|-----------:|-----------:|-------:|----------:|
| SolvePartOne |     26.46 us |   0.092 us |   0.086 us | 0.3662 |   6.46 KB |
| SolvePartTwo | 12,753.91 us | 213.036 us | 199.274 us |      - |    6.7 KB |

// * Hints *
Outliers
  Benchmarker.SolvePartTwo: .NET 7.0 -> 2 outliers were detected (12.37 ms, 12.38 ms)

// * Legends *
  Mean      : Arithmetic mean of all measurements
  Error     : Half of 99.9% confidence interval
  StdDev    : Standard deviation of all measurements
  Gen0      : GC Generation 0 collects per 1000 operations
  Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B)
  1 us      : 1 Microsecond (0.000001 sec)

Dold text

Senast redigerat 2022-12-11 17:04

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

2022-12-11 16:52

Permalänk

Mickur

Medlem ★

Plats: Örebro
Registrerad: Mar 2007

●

Skrivet av Yoshman:

Undrar om jag tog en väldigt omväg... Tänkte att det är tillfälle att lura ut hur man använder BenchmarkDotNet.

Fråga: vilka modifikationer gör du för att testa ditt program? Fick plocka ned ditt program i delar och stoppa in i ramverket för att få det att fungera, tror det ändå blev rätt i slutändan (givet att du kör med 7950X verkar det som Microsoft tillslut fått ordning på ARM64 prestanda, min M1Pro laptop är inte speciellt långt efter din 7950X )

BenchmarkDotNet=v0.12.1, OS=macOS 13.0.1 (22A400) [Darwin 22.1.0]
Apple M1 Pro, 1 CPU, 10 logical and 10 physical cores
.NET Core SDK=7.0.100
  [Host]     : .NET Core 6.0.11 (CoreCLR 6.0.1122.52304, CoreFX 6.0.1122.52304), Arm64 RyuJIT
  DefaultJob : .NET Core 6.0.11 (CoreCLR 6.0.1122.52304, CoreFX 6.0.1122.52304), Arm64 RyuJIT


|       Method |         Mean |     Error |    StdDev |
|------------- |-------------:|----------:|----------:|
| SolvePartOne |     31.17 us |  0.060 us |  0.056 us |
| SolvePartTwo | 13,830.25 us | 34.804 us | 32.555 us |

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  1 us   : 1 Microsecond (0.000001 sec)

Pushade mina saker till GitHub, exempel på hur tester + benchmarks ser ut för dag 11 finns här

Gå till inlägget

Hela min kod i benchmark-projektet nedan. Har säkert skett ett gäng förbättringar efter jag postade min kod tidigare. Och enligt mina benchmarks några poster upp så slår min M1 Macbook Air min 7950X, ajajaj. Dock har jag ju dragit ner på single-core till fördel för multi-core på lägre volt på 7950X. Men det är ändå väldigt imponerande för en passivt kyld laptop...

using AoCUtils;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;

namespace BenchmarkSandbox
{
    public class Program
    {
        public static void Main(string[] args)
        {
            BenchmarkRunner.Run<Benchmarker>();
        }
    }

    [MemoryDiagnoser]
    [SimpleJob(RuntimeMoniker.Net70)]
    public class Benchmarker
    {
        private string[] input;

        [GlobalSetup]
        public void Setup()
        {
            input = File.ReadAllLines("inputs/2022-Day11.txt");
        }
        
        [Benchmark]
        public List<Monkey> Parse()
        {
            return ParseMonkeys(input);
        }
        
        [Benchmark]
        public ulong SolvePartOne()
        {
            var monkeys = ParseMonkeys(input);
            RunRounds(monkeys, 20, false);
            SortMonkeys(monkeys);
            return monkeys[0].Activity * monkeys[1].Activity;
        }

        [Benchmark]
        public ulong SolvePartTwo()
        {
            var monkeys = ParseMonkeys(input);
            RunRounds(monkeys, 10000, true);
            SortMonkeys(monkeys);
            return monkeys[0].Activity * monkeys[1].Activity;
        }

        public List<Monkey> ParseMonkeys(IReadOnlyList<string> input)
        {
            var monkeyList = new List<Monkey>(10);

            for (var i = 0; i < input.Count; i++)
            {
                var monkey = new Monkey();

                // Parse items
                var itemsString = input[i + 1].AsSpan(18).ToString();
                var items = itemsString.Split(", ");
                for (var j = 0; j < items.Length; j++) monkey.Items.Enqueue(AoCParsing.FastULongParse(items[j]));

                // Parse operation
                var operation = input[i + 2][23];
                var operationValue =
                    input[i + 2][25] == 'o'
                        ? 0
                        : AoCParsing.FastULongParse(input[i + 2].AsSpan(25)); // Set to 0 if "old", otherwise parse it
                monkey.Operation = (operation, operationValue);

                // Parse test
                monkey.TestDivision = AoCParsing.FastULongParse(input[i + 3].AsSpan(21));
                monkey.TestTargets = (AoCParsing.FastIntParse(input[i + 4].AsSpan(29)),
                    AoCParsing.FastIntParse(input[i + 5].AsSpan(30)));

                monkeyList.Add(monkey);

                i += 6;
            }

            return monkeyList;
        }

        public void RunRounds(IReadOnlyList<Monkey> monkeys, int rounds, bool isPartTwo)
        {
            ulong divideBy = 3;

            if (isPartTwo)
            {
                divideBy = 1;
                for (var k = 0; k < monkeys.Count; k++) divideBy *= monkeys[k].TestDivision;
            }

            for (var i = 0; i < rounds; i++)
                // Monkeys
            for (var j = 0; j < monkeys.Count; j++)
                // Items
                while (monkeys[j].Items.Count != 0)
                {
                    var item = monkeys[j].Inspect(isPartTwo, divideBy);
                    monkeys[item.Item2].Items.Enqueue(item.Item1);
                }
        }

        public void SortMonkeys(List<Monkey> monkeys)
        {
            monkeys.Sort(delegate(Monkey m1, Monkey m2)
            {
                if (m1.Activity < m2.Activity)
                    return 1;

                if (m1.Activity > m2.Activity)
                    return -1;

                return 0;
            });
        }
    }
}

public class Monkey
{
    public readonly Queue<ulong> Items = new(10);
    public ulong Activity;
    public (char, ulong) Operation;
    public ulong TestDivision;
    public (int, int) TestTargets;

    public (ulong, int) Inspect(bool isPartTwo, ulong divideBy)
    {
        Activity++;

        var item = Items.Dequeue();

        switch (Operation.Item1)
        {
            case '+':
                item += Operation.Item2 == 0 ? item : Operation.Item2;
                break;

            case '*':
                item *= Operation.Item2 == 0 ? item : Operation.Item2;
                break;
        }

        if (isPartTwo)
            item %= divideBy;
        else
            item /= divideBy;

        return item % TestDivision == 0 ? (item, TestTargets.Item1) : (item, TestTargets.Item2);
    }
}

Dold text

Senast redigerat 2022-12-11 16:58

Visa signatur

CPU: 7950X 5GHz@1.1v | RAM: 32GB 6000MHz CL36 | GPU: KFA² 3090 SG w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3 / Supreme CD-99

Rapportera Redigera

Citera flera Citera

2022-12-11 18:01

Permalänk

henrikj82

Medlem

Registrerad: Jul 2005

●

Dag 11
Språk: C#

Del 1 var rätt så lätt även om det tog tid att dela upp all data i rätt delar, del 2 var lurig för jag visste inte att man kunde multiplicera olika nämnare med varandra för att få ut gemensam nämnare men nu har jag lärt mig det efter att ha suttit fast ett par timmar och googlat och experimenterat. Mycket kod och knappast snabbkört som vanligt.

        public static int Day12Calc(char[,] mountain, char[,] mountain2, int[] win, List<string> pos, List<int> partTwoPos, bool CalcAll)
        {
            int stepReturn = 10000;
            int counter = 0;
            again:
            for (int i = 0; i < mountain2.GetLength(0); i++)
            {
                for (int j = 0; j < mountain2.GetLength(1); j++)
                {
                    mountain2[i, j] = ' ';
                }
            }
            if (CalcAll == true)
            {
                pos.Clear();
                pos.Add(partTwoPos[counter].ToString() + ";" + partTwoPos[counter + 1].ToString());
                counter = counter + 2;
            }
            int step = 0;
            string won = "no";
            while (won == "no")
            {
                for(int i = pos.Count()-1; i > -1; i--)
                {                    
                    string[] split = pos[i].Split(";");
                    if (int.Parse(split[0]) != 0 && int.Parse(split[0]) != mountain2.GetLength(0) - 1 && int.Parse(split[1]) != 0 && int.Parse(split[1]) != mountain2.GetLength(1) - 1)
                    {
                        if (mountain2[int.Parse(split[0]) - 1, int.Parse(split[1])] == 'X' && mountain2[int.Parse(split[0]) + 1, int.Parse(split[1])] == 'X' && mountain2[int.Parse(split[0]), int.Parse(split[1]) - 1] == 'X' && mountain2[int.Parse(split[0]) + 1, int.Parse(split[1]) + 1] == 'X') pos.RemoveAt(i);
                    }
                    else if (int.Parse(split[0]) == 0 && mountain2[int.Parse(split[0]) + 1, int.Parse(split[1])] == 'X') pos.RemoveAt(i);
                }
                int tracker = 0;
                for (int i = pos.Count() - 1; i > -1; i--)
                {
                    string[] split = pos[i].Split(";");
                    if (int.Parse(split[0]) + 1 != mountain.GetLength(0))
                    {
                        if (mountain[int.Parse(split[0]), int.Parse(split[1])] - mountain[int.Parse(split[0]) + 1, int.Parse(split[1])] > -2)
                        {
                            string info = "";
                            int calc = int.Parse(split[0]) + 1;
                            if (win[0] == calc && win[1] == int.Parse(split[1]))
                            {
                                won = "yes!";
                                if (step < stepReturn) stepReturn = step + 1;
                            }
                            info = calc.ToString() + ";";
                            info = info + split[1];
                            pos.Add(info);
                            if (mountain2[calc, int.Parse(split[1])] == ' ')
                            {
                                mountain2[calc, int.Parse(split[1])] = 'X';
                                tracker++;
                            }
                        }
                    }
                    if (int.Parse(split[0]) - 1 != -1)
                    {
                        if (mountain[int.Parse(split[0]), int.Parse(split[1])] - mountain[int.Parse(split[0]) - 1, int.Parse(split[1])] > -2)
                        {
                            string info = "";
                            int calc = int.Parse(split[0]) - 1;
                            if (win[0] == calc && win[1] == int.Parse(split[1]))
                            {
                                won = "yes!";
                                if (step < stepReturn) stepReturn = step + 1;
                            }
                            info = calc.ToString() + ";";
                            info = info + split[1];
                            pos.Add(info);                            
                            if (mountain2[calc, int.Parse(split[1])] == ' ')
                            {
                                mountain2[calc, int.Parse(split[1])] = 'X';
                                tracker++;
                            }
                        }
                    }
                    if (int.Parse(split[1]) + 1 != mountain.GetLength(1))
                    {
                        if (mountain[int.Parse(split[0]), int.Parse(split[1])] - mountain[int.Parse(split[0]), int.Parse(split[1]) + 1] > -2)
                        {
                            string info = "";
                            int calc = int.Parse(split[1]) + 1;
                            if (win[1] == calc && win[0] == int.Parse(split[0]))
                            {
                                won = "yes!";
                                if (step < stepReturn) stepReturn = step+1;
                            }
                            info = split[0] + ";";
                            info = info + calc.ToString();
                            pos.Add(info);                            
                            if (mountain2[int.Parse(split[0]), calc] == ' ')
                            {
                                mountain2[int.Parse(split[0]), calc] = 'X';
                                tracker++;
                            }
                        }
                    }
                    if (int.Parse(split[1]) - 1 != -1)
                    {
                        if (mountain[int.Parse(split[0]), int.Parse(split[1])] - mountain[int.Parse(split[0]), int.Parse(split[1]) - 1] > -2)
                        {
                            string info = "";
                            int calc = int.Parse(split[1]) - 1;
                            if (win[1] == calc && win[0] == int.Parse(split[0]))
                            {
                                won = "yes!";
                                if (step < stepReturn) stepReturn = step + 1;
                            }
                            info = split[0] + ";";
                            info = info + calc.ToString();
                            pos.Add(info);                            
                            if (mountain2[int.Parse(split[0]), calc] == ' ')
                            {
                                mountain2[int.Parse(split[0]), calc] = 'X';
                                tracker++;
                            }
                        }
                    }
                }
                if (tracker == 0) won = "stuck";
                pos = pos.Distinct().ToList();
                step++;                
            }            
            if (counter < partTwoPos.Count() && CalcAll==true) goto again;
            return stepReturn;
        }

Dold text

Senast redigerat 2022-12-12 20:25

Rapportera Redigera

Citera flera Citera

2022-12-11 18:06

Permalänk

Gorgonzola

Medlem ★

Registrerad: Feb 2004

●

Dag 11 Spoiler:

https://www.mathsisfun.com/numbers/common-denominator.html

Dold text

Rapportera Redigera

Citera flera Citera

2022-12-11 18:17

Permalänk

huggeMugg

Medlem

Registrerad: Dec 2020

●

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

Del 1 hade en riktigt trälig parsing och del 2 var riktigt knivig. Jag definierade min egen ModNumber-datatyp som höll koll på det nuvarande talets modulus för alla tal upp till 23. Och implementerade + och * för den så jag kunde återanvända mycket av koden från del 1:

Dold text

type ModNumber = object
    mods: seq[int]

proc initModNumber(n: int, maxMod: int = 23): ModNumber =
  result.mods = newSeq[int](maxMod + 1)
  for i in 1 .. maxMod:
    result.mods[i] = n mod i

proc `+`(m: ModNumber, x: int): ModNumber =
  result = m # copy
  for i in 1 .. m.mods.high:
    result.mods[i] = (result.mods[i] + x) mod i

proc `+`(m: ModNumber, x: ModNumber): ModNumber =
  result = m # copy
  for i in 1 .. m.mods.high:
    result.mods[i] = (result.mods[i] + x.mods[i]) mod i

proc `*`(m: ModNumber, x: int): ModNumber =
  result = m # copy
  for i in 1 .. m.mods.high:
    result.mods[i] = result.mods[i] * x mod i

proc `*`(m: ModNumber, x: ModNumber): ModNumber =
  result = m # copy
  for i in 1 .. m.mods.high:
    result.mods[i] = result.mods[i] * x.mods[i] mod i

Dold text

Rapportera Redigera

Citera flera Citera

2022-12-11 19:11

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Skrivet av Gorgonzola:

Dag 11 Spoiler:

https://www.mathsisfun.com/numbers/common-denominator.html

Dold text

Gå till inlägget

Fast är det verkligen den delen som är svår att lura ut i del 2?

Skulle säga att det skulle varit betydligt enklare att fatta vad man skulle göra om uppgiften explicit sagt: din algoritm måste ge samma resultat som om man låter "worry levels" öka till hur stora värden som helst. Var den delen som det tog mig ett bra tag att fatta...

Är ju det som står, men var i alla fall för mig lite indirekt då jag tänkte: finns ju oändligt med sätt att hålla ett tal på vettig nivå... Polletten trillade ner efter att kikat på min indata och test-data där jag noterade att det man skulle använda i modulus beräkningen var alltid små primtal (fast det är egentligen inget krav, men det fick mig att börjar titta i rätt riktning).

Att just modulus med produkten av alla modulus-test värden fungerar (alla produkter av det fungerar också) är för att just den förändringen av "worry levels" kommer ge samma resultat som om man lät "worry levels" öka fritt beror, det i sin tur p.g.a.

WL(free-running) mod X = A = ((WL(free-running) mod K) mod X)
WL(free-running) mod Y = B = ((WL(free-running) mod K) mod Y)
WL(free-running) mod Z = C = ((WL(free-running) mod K) mod Z)

Om

K = X * Y * Z

D.v.s. man kan minska WR med mod K där K är produkten av alla apors "modulus test värde", alla tester kommer ändå ge samma resultat.

Spoiler för del 2

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

2022-12-11 19:28

Permalänk

Mickur

Medlem ★

Plats: Örebro
Registrerad: Mar 2007

●

Mitt första försök till att få det att fungera var helt enkelt att bara ta bort divisionen från del 1. Märkte då såklart att en int inte räcker till, så drog till med ulongs. När inte det heller gav rätt output började jag fastna.

Jag förstod ju snabbt att något behövde göras med talen för att hindra dom från att slå över, och det var där det mesta av min tid gick åt. Och som Yoshman säger så är ju deras förväntade lösning helt annorlunda från hur del 1 fungerade. Dels måste man komma på att man behöver komma på en lösning som "bibehåller" deras värden och sedan hitta hur man kan ta sig dit. Och jag kan väl erkänna att jag borde ha hittat lösningen snabbare.

Var inte roligt alls idag...

Mina korta tankar angående del 2

Edit: Jag verkar dock klättra en placering från gårdagen trots att jag vaknade klockan 8 idag.

Senast redigerat 2022-12-11 19:54

Visa signatur

CPU: 7950X 5GHz@1.1v | RAM: 32GB 6000MHz CL36 | GPU: KFA² 3090 SG w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3 / Supreme CD-99

Rapportera Redigera

Citera flera Citera

2022-12-11 19:41

Permalänk

Gorgonzola

Medlem ★

Registrerad: Feb 2004

●

Skrivet av Yoshman:

Fast är det verkligen den delen som är svår att lura ut i del 2?

Skulle säga att det skulle varit betydligt enklare att fatta vad man skulle göra om uppgiften explicit sagt: din algoritm måste ge samma resultat som om man låter "worry levels" öka till hur stora värden som helst. Var den delen som det tog mig ett bra tag att fatta...

Är ju det som står, men var i alla fall för mig lite indirekt då jag tänkte: finns ju oändligt med sätt att hålla ett tal på vettig nivå... Polletten trillade ner efter att kikat på min indata och test-data där jag noterade att det man skulle använda i modulus beräkningen var alltid små primtal (fast det är egentligen inget krav, men det fick mig att börjar titta i rätt riktning).

Att just modulus med produkten av alla modulus-test värden fungerar (alla produkter av det fungerar också) är för att just den förändringen av "worry levels" kommer ge samma resultat som om man lät "worry levels" öka fritt beror, det i sin tur p.g.a.

WL(free-running) mod X = A = ((WL(free-running) mod K) mod X)
WL(free-running) mod Y = B = ((WL(free-running) mod K) mod Y)
WL(free-running) mod Z = C = ((WL(free-running) mod K) mod Z)

Om

K = X * Y * Z

D.v.s. man kan minska WR med mod K där K är produkten av alla apors "modulus test värde", alla tester kommer ändå ge samma resultat.

Spoiler för del 2

Gå till inlägget

Vet inte om det är det svåra, men med min lösning för del1 så behövde jag bara ändra det och antal rundor för att få svaret

Rapportera Redigera

Citera flera Citera

2022-12-11 19:59

Permalänk

henrikj82

Medlem

Registrerad: Jul 2005

●

Skrivet av Gorgonzola:

Vet inte om det är det svåra, men med min lösning för del1 så behövde jag bara ändra det och antal rundor för att få svaret

Gå till inlägget

Samma här, behövde bara byta ut en rad i själva beräkningen efter att jag kom fram till vad som skulle göras. totalt var det väl 3 rader ny kod i uppgift 2 mot 1:an så för mig var matematiken hela grejen. (vilket tog lång tid för mig, länge sedan jag gick i skolan)

Rapportera Redigera

Citera flera Citera

2022-12-11 20:40

Permalänk

Pie-or-paj

Medlem ★

Plats: Nyköping
Registrerad: Apr 2008

●

Skrivet av Yoshman:

Fast är det verkligen den delen som är svår att lura ut i del 2?

Skulle säga att det skulle varit betydligt enklare att fatta vad man skulle göra om uppgiften explicit sagt: din algoritm måste ge samma resultat som om man låter "worry levels" öka till hur stora värden som helst. Var den delen som det tog mig ett bra tag att fatta...

Är ju det som står, men var i alla fall för mig lite indirekt då jag tänkte: finns ju oändligt med sätt att hålla ett tal på vettig nivå... Polletten trillade ner efter att kikat på min indata och test-data där jag noterade att det man skulle använda i modulus beräkningen var alltid små primtal (fast det är egentligen inget krav, men det fick mig att börjar titta i rätt riktning).

Att just modulus med produkten av alla modulus-test värden fungerar (alla produkter av det fungerar också) är för att just den förändringen av "worry levels" kommer ge samma resultat som om man lät "worry levels" öka fritt beror, det i sin tur p.g.a.

WL(free-running) mod X = A = ((WL(free-running) mod K) mod X)
WL(free-running) mod Y = B = ((WL(free-running) mod K) mod Y)
WL(free-running) mod Z = C = ((WL(free-running) mod K) mod Z)

Om

K = X * Y * Z

D.v.s. man kan minska WR med mod K där K är produkten av alla apors "modulus test värde", alla tester kommer ändå ge samma resultat.

Spoiler för del 2

Gå till inlägget

Jag la en del tid på att byta till en u128, och sen en biguint när 128 visade sig för liten och sedan testa i release mode när det visade sig ta vääldigt lång tid... Men efter att till slut förstått att jag behöver hitta ett sätt att minska siffrorna var modulus med produkten av alla modulus-test värden den självklara lösningen. Så för mig var det det iaf. Efter att jag förstått att bruteforce inte kommer funka var det ca 2min att återställa och implementera det för att kunna lösa nummer 2

Dold text

Rapportera Redigera

Citera flera Citera

2022-12-11 21:08

Permalänk

l4nky

Medlem ★

Registrerad: Jan 2005

●

Skrivet av Zlashy:

Dag: 11
Språk: C#

Steg ett gick ju hyfsat enkelt. Men steg två fastnade jag ordentligt. Jag förstod att det blev alldeles för stora tal och på något sätt behövde talen minskas. Iom man bara kollar delbarhet så förstod jag att man borde kunde minska de på något sätt, men kom inte fram till riktigt hur. Fick ta till mig lite tips och lösningen blev att multiplicera alla apors "divide by" för att få fram en gemensam nämnare som man använde för att minska talen. Logiskt nu i efterhand men hade nog haft svårt att komma på det själv tyvärr.

using System.Text.RegularExpressions;

namespace AOC2022.Puzzles;

internal partial class Puzzle11 : Puzzle<long, long>
{
    [GeneratedRegex(@Monkey (\d+):)] private static partial Regex MonkeyRegex();
    [GeneratedRegex(@(\*|\+{1}))] private static partial Regex OperationRegex();

    record Monkey(int Id, List<long> Items, Func<long, long> Operation, int DivisibleBy, int TrueMonkey, int FalseMonkey)
    {
        public int Inspection = 0;

        public IEnumerable<(int MonkeyId, long Item)> MakeTurn(decimal worryRelief, int superModulo)
        {
            foreach (var item in Items)
            {
                Inspection++;
                var newWorryLevel = (long) Math.Floor(Operation(item) / worryRelief) % superModulo;
                yield return (newWorryLevel % DivisibleBy == 0 ? TrueMonkey : FalseMonkey, newWorryLevel);
            }

            Items.Clear();
        }
    }
    
    protected override void Solve(string[] lines)
    {
        One = RunMonkeys(lines, 20);
        Two = RunMonkeys(lines, 10000);
    }

    private static long RunMonkeys(string[] lines, int rounds)
    {
        var monkeys = lines
            .Select((x, i) => x.StartsWith("Monkey") ? i : -1)
            .Where(x => x >= 0)
            .Select(x =>
            {
                var monkeyId = int.Parse(MonkeyRegex().Match(lines[x]).Groups[1].Value);
                var startingItems = lines[x + 1].Split(": ")[1].Split(',', StringSplitOptions.TrimEntries).Select(long.Parse);
                var operation = ParseOperation(lines[x + 2].Split("= ")[1]);
                var divisibleBy = int.Parse(lines[x + 3].Split(" ")[^1]);
                var trueMonkey = int.Parse(lines[x + 4].Split(" ")[^1]);
                var falseMonkey = int.Parse(lines[x + 5].Split(" ")[^1]);
                return new Monkey(monkeyId, startingItems.ToList(), operation, divisibleBy, trueMonkey, falseMonkey);
            })
            .ToDictionary(x => x.Id);

        var superModulo = monkeys.Values.Aggregate(1, (current, monkey) => current * monkey.DivisibleBy);

        foreach (var (monkeyId, item) in Enumerable.Range(1, rounds)
            .SelectMany(x => monkeys.Values)
            .SelectMany(x => x.MakeTurn(rounds == 20 ? 3 : 1, superModulo)))
        {
            monkeys[monkeyId].Items.Add(item);
        }

        return monkeys.Values.OrderByDescending(x => x.Inspection)
            .Take(2).Aggregate(1L, (a, b) => a * b.Inspection);
    }

    private static Func<long, long> ParseOperation(string op)
    {
        var test = OperationRegex().Split(op).Select(x => x.Trim()).ToList();

        var useMultiply = test[1] == "*";
        return worryLevel =>
        {
            var parts = test
                .Where((x, i) => i != 1)
                .Select(x =>x switch
                {
                    "old" => worryLevel,
                    _ => long.Parse(x)
                })
                .ToList();

            return useMultiply ? parts[0] * parts[1] : parts[0] + parts[1];
        };
    }
}

Dold text

Gå till inlägget

Hade ungefär samma problem!

Var inne en sväng på att kolla om det var jämnt delbart med alla apornas värden individuellt. Men det blev såklart fel. Självklart var det multiplikation av deras värden innan modulo. Tog en del tid!

För andra som vill läsa på

Dold text

Rapportera Redigera

Citera flera Citera

2022-12-11 21:26

Permalänk

l4nky

Medlem ★

Registrerad: Jan 2005

●

Dag: 11
Språk: C#

Del två var lite jobbig idag, märks att man inte har så stark mattebakgrund!

| Method |         Mean |     Error |    StdDev |   Gen0 |   Gen1 | Allocated |
|------- |-------------:|----------:|----------:|-------:|-------:|----------:|
|  Run_A |     26.79 us |  0.216 us |  0.191 us | 1.8921 | 0.0305 |   15.7 KB |
|  Run_B | 10,421.52 us | 72.612 us | 64.369 us |      - |      - |  15.97 KB |

public sealed class MonkeyInTheMiddle : Puzzle<ulong>
{
    private sealed class Monkey
    {
        public Monkey
        (
            IEnumerable<int> items,
            char operation,
            int? operationValue,
            int test,
            int monkeyTrue,
            int monkeyFalse,
            Func<long, long>? worryManagement
        )
        {
            Test = test;
            _monkeyTrue = monkeyTrue;
            _monkeyFalse = monkeyFalse;
            _worryManagement = worryManagement;
            _items = new Queue<long>(items.Select(i => (long) i));
            _operation = operation;
            _operationValue = operationValue ?? null;
        }

        private readonly Queue<long> _items;
        private readonly int _monkeyTrue;
        private readonly int _monkeyFalse;
        private readonly Func<long, long>? _worryManagement;
        private readonly char _operation;
        private readonly long? _operationValue;
        public int Test { get; }

        public ulong Inspections { get; private set; }

        private long CalculateWorry(long value)
        {
            return _operation switch
            {
                '*' => value * (_operationValue == null ? value : _operationValue!.Value),
                '+' => value + (_operationValue == null ? value : _operationValue!.Value),
                _ => throw new InvalidOperationException()
            };
        }

        public (long worry, int index) CalculateWorryIndex(int monkeyMods)
        {
            Inspections++;
            long value = _items.Dequeue();
            long worry = CalculateWorry(value);
            long managedWorry = worry;
            if (_worryManagement != null)
                managedWorry = _worryManagement(worry);
            managedWorry %= monkeyMods;
            return managedWorry % Test == 0 ? (managedWorry, _monkeyTrue) : (managedWorry, _monkeyFalse);
        }

        public void Catch(long value)
        {
            _items.Enqueue(value);
        }

        public bool HasItems()
        {
            return _items.Count > 0;
        }
    }

    public override ulong A(string data)
    {
        const int rounds = 20;
        return RunMonkeyBusiness(data, rounds, m => m / 3);
    }

    public override ulong B(string data)
    {
        const int rounds = 10000;
        return RunMonkeyBusiness(data, rounds, null);
    }

    private ulong RunMonkeyBusiness(string data, int rounds, Func<long, long>? worryManagement)
    {
        var monkeys = ParseMonkeys(data, worryManagement);
        var modValues = monkeys.Select(m => m.Test).Aggregate(1, (a, b) => a * b);
        for (int i = 0; i < rounds; i++)
        {
            foreach (Monkey monkey in monkeys)
            {
                while (monkey.HasItems())
                {
                    var item = monkey.CalculateWorryIndex(modValues);
                    monkeys[item.index].Catch(item.worry);
                }
            }
        }

        return monkeys
            .OrderByDescending(m => m.Inspections)
            .Take(2)
            .Aggregate((ulong) 1, (i, monkey) => i * monkey.Inspections);
    }

    private static List<Monkey> ParseMonkeys(string data, Func<long, long>? worryManagement)
    {
        List<Monkey> monkeys = new List<Monkey>();
        var lines = data.Split("\r\n\r\n");

        for (var i = 0; i < lines.Length; i++)
        {
            var mLines = lines[i].Split("\r\n");
            monkeys.Insert(i, new Monkey(
                mLines[1][18..].Split(',').Select(k => k.ParseInt()),
                mLines[2][23],
                mLines[2][24..].ParseIntNullable(),
                mLines[3][21..].ParseInt(),
                mLines[4][29..].ParseInt(),
                mLines[5][29..].ParseInt(),
                worryManagement)
            );
        }

        return monkeys;
    }
}

Dold text

Rapportera Redigera

Citera flera Citera

2022-12-11 21:30

Permalänk

Pelegrino

Medlem ★

Plats: Lund
Registrerad: Maj 2013

●

Det finns inget som ger en så mycket imposter syndrome som AoC. Även på svinlätta uppgifter så gör man något lite felt och när man tittar på andra lösningar ser man ingen skillnad.

Blir så när man går över till frontend på heltid och inte jobbar med algoritmer längre

Jag vill visa att jag kan -> Jag mår dåligt över att jag inte kan -> Jag måste visa att jag kan -> repeat

Senast redigerat 2022-12-11 21:37

Visa signatur

CPU: Ryzen 5600xGPU: 1080 TI ROG Strix RAM:2x16GB G.skill Trident @ 3600MHz MoBo: Asus B550FPSU: Corsair SF750
En resa till Nordkorea
2 dagar i Tjernobyl

Rapportera Redigera

Citera flera Citera (1)

2022-12-12 10:12

Permalänk

Pie-or-paj

Medlem ★

Plats: Nyköping
Registrerad: Apr 2008

●

Dag: 12
Språk: Rust

Kommenter:

Kul att äntligen få med lite pathfinding, känns som det brukar komma tidigare? Ville vara först på den privata leaderboarden så drog in ett bibliotek vilket känns lite småfuskigt men är det tävling så

Strulade ett tag med fel path length för att jag hade råkat sätta fel höjd på slutpunkten, så blev tvungen att implementera visning av pathen för att kunna debugga det på ett vettigt sätt.

Dold text

Lösning:

use pathfinding::prelude::astar;

struct Board {
	heightmap: Vec<Vec<i32>>,
	start: (usize, usize),
	end: (usize, usize),
}

fn char_to_height(c: char) -> i32 {
	c as i32 - 'a' as i32
}

fn parse(input: &str) -> Board {
	let mut heightmap = vec![];
	let mut start = (0, 0);
	let mut end = (0, 0);
	for (y, line) in input.lines().enumerate() {
		let mut row = vec![];
		for (x, c) in line.chars().enumerate() {
			match c {
				'S' => {
					start = (x, y);
					row.push(char_to_height('a'));
				}
				'E' => {
					end = (x, y);
					row.push(char_to_height('z'));
				}
				c => row.push(char_to_height(c)),
			}
		}
		heightmap.push(row);
	}
	Board {
		heightmap,
		start,
		end,
	}
}

fn get_neighboars((x, y): (usize, usize), board: &Board) -> Vec<((usize, usize), usize)> {
	let mut neighbors = vec![];
	if x > 0 {
		neighbors.push((x - 1, y));
	}
	if x < board.heightmap[0].len() - 1 {
		neighbors.push((x + 1, y));
	}
	if y > 0 {
		neighbors.push((x, y - 1));
	}
	if y < board.heightmap.len() - 1 {
		neighbors.push((x, y + 1));
	}
	neighbors
		.into_iter()
		.filter(|&(nx, ny)| (board.heightmap[ny][nx] - board.heightmap[y][x]) < 2)
		.map(|(x, y)| ((x, y), 1))
		.collect::<Vec<_>>()
}

fn print_nav(board: &Board, path: &Vec<(usize, usize)>) {
	let mut nav = vec![];
	for (y, heightmap_row) in board.heightmap.iter().enumerate() {
		let mut row = vec![];
		for (x, _) in heightmap_row.iter().enumerate() {
			if path.contains(&(x, y)) {
				row.push('X');
			} else {
				row.push('.');
			}
		}
		nav.push(row);
	}

	let mut previous = board.start;
	for (x, y) in path.iter().skip(1) {
		let (px, py) = &previous;
		let step = (*x, *y);
		if y > py {
			nav[*py][*px] = 'v';
		} else if y < py {
			nav[*py][*px] = '^';
		} else if x > px {
			nav[*py][*px] = '>';
		} else if x < px {
			nav[*py][*px] = '<';
		}
		previous = step;
	}
	for row in nav {
		for c in row {
			print!("{}", c);
		}
		println!("");
	}
}

pub fn one() {
	let input = include_str!("input1.txt");
	let board = parse(input);
	let path = astar(
		&board.start,
		|&(x, y)| get_neighboars((x, y), &board),
		|&(x, y)| (board.end.0.abs_diff(x) + board.end.1.abs_diff(y)),
		|&p| p == board.end,
	);

	println!("{:?}", path);
	let path = path.unwrap().0;
	println!("{}", input);
	print_nav(&board, &path);

	let result = path.len();

	println!("Day 12, part 1: {:?}", result - 1);
}

pub fn two() {
	let input = include_str!("input1.txt");
	let board = parse(input);
	let starting_points = board
		.heightmap
		.iter()
		.enumerate()
		.flat_map(|(y, row)| {
			row.iter()
				.enumerate()
				.filter(|(_, &c)| c == 0)
				.map(move |(x, _)| (x, y))
		})
		.collect::<Vec<_>>();
	let mut results = vec![];
	for starting_point in starting_points {
		let path = astar(
			&starting_point,
			|&(x, y)| get_neighboars((x, y), &board),
			|&(x, y)| (board.end.0.abs_diff(x) + board.end.1.abs_diff(y)),
			|&p| p == board.end,
		);
		if let Some(result) = path {
			let path = result.0;
			let result = path.len() - 1;
			results.push((result, path));
		}
	}
	results.sort();
	print_nav(&board, &results[0].1);
	let result = results[0].0;
	println!("Day 12, part 2: {:?}", result);
}

Dold text

Senast redigerat 2022-12-12 10:27 Lite clean up

Rapportera Redigera

Citera flera Citera (1)

2022-12-12 10:32

Permalänk

GLaDER

Medlem ★

Plats: *.home.arpa
Registrerad: Nov 2011

●

Skrivet av GLaDER:

Dag: 11
Språk: Python 3
Lösning: GitHub

Årets första "Del 2 ökar bara antalet iterationer men det går inte att köra bruteforce"-uppgift. Får gärna vara årets sista också

Dold text

Gå till inlägget

Dag: 12
Språk: Python 3
Lösning: GitHub

Jag tycker att de här uppgifterna borde bli lättare med tiden, men så verkar inte vara fallet

Dold text

Visa signatur

:(){ :|:& };:

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

Får det lov att vara en kaffe?

Rapportera Redigera

Citera flera Citera

2022-12-12 10:45

Permalänk

Dakkie

Medlem ★

Plats: Stockholm
Registrerad: Jul 2010

●

Skrivet av Rådström:

Jag hade samma problem och kom fram till att kataloger kan heta samma sak men finnas på olika ställen i strukturen. Kanske ett tips för din lösning, eller inte.

Gå till inlägget

omg det måste vara det

Visa signatur

Rapportera Redigera

Citera flera Citera

2022-12-12 12:22

Permalänk

jclr

Medlem

Registrerad: Mar 2018

●

Dag: 12
Språk: Scala

scala worksheet - börjat tröttna lite så nöjde mig med att plocka fram rätt svar.

val input = Using.resource(Source.fromFile("""12.txt"""))(_.getLines().toVector)

val sizeY = input.length
val sizeX = input(0).length

val heights = input.flatMap(_.split(""))

val start = heights.indexWhere(_ == "S")
val end   = heights.indexWhere(_ == "E")

val heightsFixed = heights.updated(start, "a").updated(end, "z").map(_.head)

def neighbours(idx: Int) =
   val x = idx % sizeX
   val y = idx / sizeX
   val h = heightsFixed(idx)
   Vector((0, 1), (1, 0), (-1, 0), (0, -1))
      .map((dx, dy) => (x + dx, y + dy))
      .collect { case (x, y) if x >= 0 && x < sizeX && y >= 0 && y < sizeY => x + y * sizeX }
      .filter(i => (heightsFixed(i) - h) <= 1)

val heightGraph = heightsFixed.indices.map(neighbours)

def bfs(graph: IndexedSeq[IndexedSeq[Int]], start: Set[Int], end: Int) =
   Iterator
      .iterate((start, Set.empty[Int], 0)) { case (frontier, visited, depth) =>
         val visited0  = frontier.union(visited)
         val frontier0 = frontier.flatMap(graph).diff(visited0)
         (frontier0, visited0, depth + 1)
      }
      .collectFirst { case (f, _, d) if f.contains(end) => d }

bfs(heightGraph, Set(start), end)
bfs(heightGraph, heightsFixed.zipWithIndex.collect { case (c, i) if c == 'a' => i }.toSet, end)

Dold text

Rapportera Redigera

Citera flera Citera

2022-12-12 13:32

Permalänk

Mickur

Medlem ★

Plats: Örebro
Registrerad: Mar 2007

●

Dag: 12
Språk: C#
Kommentar: Det knepiga var nog att få till pathfindingen, sen var det ganska lätt att lösa även del 2!

using System.Diagnostics;

Console.WriteLine("Mickur's Advent of Code 2022 - Day 12!");

// Setup
var input = File.ReadAllLines("input.txt");

var sw = new Stopwatch();
sw.Start();

var hill = new Hill(input);

sw.Stop();
Console.WriteLine($"Finished creating the grid in {sw.ElapsedMilliseconds} ms ({sw.ElapsedTicks} ticks)");
sw.Restart();

var partOneAnswer = hill.PartOne();

sw.Stop();
Console.WriteLine($"Finished part one in {sw.ElapsedMilliseconds} ms ({sw.ElapsedTicks} ticks)");
sw.Restart();

var partTwoAnswer = hill.PartTwo();

sw.Stop();
Console.WriteLine($"Finished part two in {sw.ElapsedMilliseconds} ms ({sw.ElapsedTicks} ticks)");

Console.WriteLine($"Part One Answer: {partOneAnswer} steps");
Console.WriteLine($"Part Two Answer: {partTwoAnswer} steps");

public class Hill
{
    private readonly int[,] _hillGrid;
    private readonly int _width;
    private readonly int _height;

    private readonly int _startX;
    private readonly int _startY;

    private readonly int _endX;
    private readonly int _endY;

    private readonly List<(int, int)> _possibleStartingLocations = new List<(int, int)>();

    public Hill(string[] input)
    {
        _width = input[0].Length;
        _height = input.Length;

        _hillGrid = new int[_width, _height];

        for (var y = 0; y < _height; y++)
        {
            for (var x = 0; x < _width; x++)
            {
                if(input[y][x] == 'a' || input[y][x] == 'S')
                    _possibleStartingLocations.Add((x, y));
                
                if (input[y][x] == 'S')
                {
                    _startX = x;
                    _startY = y;
                    _hillGrid[x, y] = 96;
                }

                else if (input[y][x] == 'E')
                {
                    _endX = x;
                    _endY = y;
                    _hillGrid[x, y] = 123;
                }

                else
                {
                    _hillGrid[x, y] = input[y][x];
                }
            }
        }
    }

    public int PartOne()
    {
        return SolveFromLocation(_startX, _startY);
    }
    
    public int PartTwo()
    {
        var shortest = int.MaxValue;

        foreach (var startingPoint in _possibleStartingLocations)
        {
            var steps = SolveFromLocation(startingPoint.Item1, startingPoint.Item2);

            if (steps >= 0 && steps < shortest)
                shortest = steps;
        }

        return shortest;
    }

    public int SolveFromLocation(int x, int y, bool isPartTwo = false)
    {
        var positionVisited = new HashSet<(int, int)>();
        var queue = new Queue<((int, int), int)>(); // Coordinates and steps

        queue.Enqueue(((x, y), 0));

        while (queue.Count > 0)
        {
            var positionAndCount = queue.Dequeue();
            var posX = positionAndCount.Item1.Item1;
            var posY = positionAndCount.Item1.Item2;
            var count = positionAndCount.Item2;
            var currLocationValue = _hillGrid[posX, posY];

            // In Part Two, starting value is always 97.
            if (isPartTwo && currLocationValue == 96)
                currLocationValue = 97;
            
            if (posX == _endX && posY == _endY)
            {
                return count;
            }

            if (!positionVisited.Contains((posX, posY)))
            {
                positionVisited.Add((posX, posY));

                // Move up possible?
                if (posY > 0 && currLocationValue >= _hillGrid[posX, posY - 1] - 1)
                    queue.Enqueue(((posX, posY - 1), count + 1));

                // Move down possible?
                if (posY < _height - 1 && currLocationValue >= _hillGrid[posX, posY + 1] - 1)
                    queue.Enqueue(((posX, posY + 1), count + 1));

                // Move left possible?
                if (posX > 0 && currLocationValue >= _hillGrid[posX - 1, posY] - 1)
                    queue.Enqueue(((posX - 1, posY), count + 1));

                // Move right possible?
                if (posX < _width - 1 && currLocationValue >= _hillGrid[posX + 1, posY] - 1)
                    queue.Enqueue(((posX + 1, posY), count + 1));
            }
        }

        return -1;
    }
}

Äcklig och ful kod

Senast redigerat 2022-12-12 13:48

Visa signatur

CPU: 7950X 5GHz@1.1v | RAM: 32GB 6000MHz CL36 | GPU: KFA² 3090 SG w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3 / Supreme CD-99

Rapportera Redigera

Citera flera Citera

2022-12-12 15:40

Permalänk

henrikj82

Medlem

Registrerad: Jul 2005

●

Dag 12
Språk C#
Denna uppgift kändes riktigt svår och det tog ett tag innan jag kom på hur man enkelt kunde söka igenom hela textmassan, lösningen blev tyvärr dock sjukt långsam då jag min metod för sökningen är väldigt ineffektiv och det tar flera minuter att för beräkningen att genomföras. Jag får nog titta på eventuella optimeringar senare och tar gärna emot tips på detta men just nu är jag sjukt nöjd att det gick att lösa. Riktigt kul uppgift tyckte jag som aldrig sett något liknande innan.

        public static int Day12Calc(char[,] mountain, char[,] mountain2, int[] win, List<string> pos, List<int> partTwoPos, bool CalcAll)
        {
            int stepReturn = 10000;
            int counter = 0;
            again:
            for (int i = 0; i < mountain2.GetLength(0); i++)
            {
                for (int j = 0; j < mountain2.GetLength(1); j++)
                {
                    mountain2[i, j] = ' ';
                }
            }
            if (CalcAll == true)
            {
                pos.Clear();
                pos.Add(partTwoPos[counter].ToString() + ";" + partTwoPos[counter + 1].ToString());
                counter = counter + 2;
            }
            int step = 0;
            string won = "no";
            while (won == "no")
            {
                int tracker = 0;
                for (int i = pos.Count() - 1; i > -1; i--)
                {
                    string[] split = pos[i].Split(";");
                    if (int.Parse(split[0]) + 1 != mountain.GetLength(0))
                    {
                        if (mountain[int.Parse(split[0]), int.Parse(split[1])] - mountain[int.Parse(split[0]) + 1, int.Parse(split[1])] > -2)
                        {
                            string info = "";
                            int calc = int.Parse(split[0]) + 1;
                            if (win[0] == calc && win[1] == int.Parse(split[1]))
                            {
                                won = "yes!";
                                if (step < stepReturn) stepReturn = step + 1;
                            }
                            info = calc.ToString() + ";";
                            info = info + split[1];
                            pos.Add(info);
                            if (mountain2[calc, int.Parse(split[1])] == ' ')
                            {
                                mountain2[calc, int.Parse(split[1])] = 'X';
                                tracker++;
                            }
                        }
                    }
                    if (int.Parse(split[0]) - 1 != -1)
                    {
                        if (mountain[int.Parse(split[0]), int.Parse(split[1])] - mountain[int.Parse(split[0]) - 1, int.Parse(split[1])] > -2)
                        {
                            string info = "";
                            int calc = int.Parse(split[0]) - 1;
                            if (win[0] == calc && win[1] == int.Parse(split[1]))
                            {
                                won = "yes!";
                                if (step < stepReturn) stepReturn = step + 1;
                            }
                            info = calc.ToString() + ";";
                            info = info + split[1];
                            pos.Add(info);                            
                            if (mountain2[calc, int.Parse(split[1])] == ' ')
                            {
                                mountain2[calc, int.Parse(split[1])] = 'X';
                                tracker++;
                            }
                        }
                    }
                    if (int.Parse(split[1]) + 1 != mountain.GetLength(1))
                    {
                        if (mountain[int.Parse(split[0]), int.Parse(split[1])] - mountain[int.Parse(split[0]), int.Parse(split[1]) + 1] > -2)
                        {
                            string info = "";
                            int calc = int.Parse(split[1]) + 1;
                            if (win[1] == calc && win[0] == int.Parse(split[0]))
                            {
                                won = "yes!";
                                if (step < stepReturn) stepReturn = step+1;
                            }
                            info = split[0] + ";";
                            info = info + calc.ToString();
                            pos.Add(info);                            
                            if (mountain2[int.Parse(split[0]), calc] == ' ')
                            {
                                mountain2[int.Parse(split[0]), calc] = 'X';
                                tracker++;
                            }
                        }
                    }
                    if (int.Parse(split[1]) - 1 != -1)
                    {
                        if (mountain[int.Parse(split[0]), int.Parse(split[1])] - mountain[int.Parse(split[0]), int.Parse(split[1]) - 1] > -2)
                        {
                            string info = "";
                            int calc = int.Parse(split[1]) - 1;
                            if (win[1] == calc && win[0] == int.Parse(split[0]))
                            {
                                won = "yes!";
                                if (step < stepReturn) stepReturn = step + 1;
                            }
                            info = split[0] + ";";
                            info = info + calc.ToString();
                            pos.Add(info);                            
                            if (mountain2[int.Parse(split[0]), calc] == ' ')
                            {
                                mountain2[int.Parse(split[0]), calc] = 'X';
                                tracker++;
                            }
                        }
                    }
                }
                if (tracker == 0) won = "stuck";
                pos = pos.Distinct().ToList();
                step++;                
            }            
            if (counter < partTwoPos.Count() && CalcAll==true) goto again;
            return stepReturn;
        }
        public static void Day12()
        {
            String[] data = File.ReadAllLines("Day12.txt");
            char[,] mountain = new char[data.Length, data[0].Length];
            char[,] mountain2 = new char[data.Length, data[0].Length];
            List<string> pos = new List<string>();                        
            int step1 = 0; int step2 = 0;
            int[] win = new int[2];
            List<int> partTwoPos = new List<int>();
            for (int i = 0; i < data.Length; i++)
            {
                for (int j = 0; j < data[i].Length; j++)
                {
                    mountain[i, j] = data[i][j];
                    if (data[i][j] == 'S')
                    {
                        string info ="";
                        mountain[i, j] = 'a';
                        info = i.ToString() +";" ;
                        info = info+ j.ToString();
                        pos.Add(info);
                    }
                    else if (data[i][j] == 'E')
                    {
                        mountain[i, j] = 'z';
                        win[0] = i;
                        win[1] = j;
                    }
                    else if (data[i][j]=='a')
                    {
                        mountain[i, j] = data[i][j];
                        partTwoPos.Add(i);
                        partTwoPos.Add(j);
                    }
                    else mountain[i, j] = data[i][j];
                }
            }
            step1 = Day12Calc(mountain, mountain2, win, pos, partTwoPos, false);                       
            step2= Day12Calc(mountain, mountain2, win, pos, partTwoPos, true);  
            Console.WriteLine();
            Console.WriteLine("Day12");
            Console.Write("Step1 " + step1 + " step2 " + step2);
        }

Dold text

Rapportera Redigera

Citera flera Citera

2022-12-12 16:07

Permalänk

Zlashy

Medlem

Registrerad: Dec 2004

●

Dag: 12
Språk: C#

Denna kändes ganska lik dag 15 från förra året, där jag använde dijkstra. Det fungerade fint här med

Edit: Skrev om den lite för att snabba upp steg 2.

namespace AOC2022.Puzzles;

internal class Puzzle12 : Puzzle<long, long>
{
    protected override void Solve(string[] lines)
    {
        var grid = Grid.CreateGrid<char>(lines, x => x);
        
        One = GetSteps(grid, 'S');
        Two = GetSteps(grid, 'S', 'a');
    }

    private static int GetSteps(char[,] grid, params char[] endLocations)
    {
        var from = Grid.Iterate(grid).First(x => grid[x.x, x.y] == 'E');
        var tos = Grid.Iterate(grid).Where(x => endLocations.Contains(grid[x.x, x.y])).ToHashSet();

        return GetSteps(grid, from, tos);
    }

    private static int GetSteps(char[,] grid, (int x, int y) from, IReadOnlyCollection<(int x, int y)> targets)
    {
        var queue = new Queue<(int x, int y)>();
        var totalSteps = new int[grid.GetLength(0), grid.GetLength(1)];

        totalSteps[from.x, from.y] = 0;
        queue.Enqueue(from);

        while (queue.TryDequeue(out var p))
        {
            foreach (var n in Grid.GetNeighbours(grid, p, false))
            {
                if (IsMovePossible(grid[p.x, p.y], grid[n.x, n.y]) && totalSteps[n.x, n.y] == 0)
                {
                    totalSteps[n.x, n.y] = totalSteps[p.x, p.y] + 1;
                    if (targets.Contains(n))
                    {
                        return totalSteps[n.x, n.y];
                    }
                    queue.Enqueue(n);
                }
            }
        }

        return 0;
    }

    private static bool IsMovePossible(char from, char to) => GetElevation(to) >= GetElevation(from) - 1;

    private static char GetElevation(char elev) => elev switch
    {
        'S' => 'a',
        'E' => 'z',
        _ => elev
    };
}

Dold text

Senast redigerat 2022-12-12 22:32

Rapportera Redigera

Citera flera Citera

2022-12-12 16:33

Permalänk

Pie-or-paj

Medlem ★

Plats: Nyköping
Registrerad: Apr 2008

●

Jag får nog titta på eventuella optimeringar senare och tar gärna emot tips på detta men just nu är jag sjukt nöjd att det gick att lösa. Riktigt kul uppgift tyckte jag som aldrig sett något liknande innan.

Det är ett standardproblem (som t.ex. sortering) som kallas "pathfinding" och precis som andra standardproblem finns det standardalgorithmer. Dijkstra är troligtvis den som är mest basic och är den "enklaste" lösningen. A* eller A-star kanske du har hört talas om i samband med spel vilket är en vanlig, mer optimerad optimerad, variant av Dijkstra.

En kodmässigt enklare lösning men lite mindre uppenbar (och ointressant om du pratar om optimeringar) är att se kartan som en graf och göra en BFS. Allt det här är olika graf-sök/navigerings algorithmer där Breadth-first search är en av de mest grundläggande och pathfinding ett specifikt subsätt. Om du pluggar coputer science kommer då få höra om och implementera ett helt gäng olika och defiinitivt dessa tre.

Så är du sugen på att lära dig lite mer och optimera koden rekommenderar jag varmt att försöka implementera Dijkstra utifrån pseudokoden på Wikipedia Ett typexempel på bra att ha gjort någon gång så att du vet vad du ska söka efter när det kommer upp men definitivt inget som en behöver kunna utantill.

Tips/lösning till dag 12

Rapportera Redigera

Citera flera Citera (1)

🌟 Advent of Code (AoC) 2022 🌟

Externa nyheter

Spelnyheter från FZ