Forum Mjukvara Programmering och digitalt skapande TrÄd InlÀgg

🌟 Advent of Code (AoC) 2022 🌟

8 9 10 11 12 13 14 15
Skriv svar
PermalÀnk
Medlem
●

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
Redigera
Citera flera Citera
PermalÀnk
Datavetare ★
●
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

Redigera
Citera flera Citera
PermalÀnk
Medlem
●
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

Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●
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
Visa signatur

CPU: 7950X | RAM: 32GB | GPU: 3090 w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3

Redigera
Citera flera Citera
PermalÀnk
Datavetare ★
●
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

Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●
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
Visa signatur

CPU: 7950X | RAM: 32GB | GPU: 3090 w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3

Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●

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.

Nuvarande stationÀr: 7800X3D, 128Gb ram, 4Tb nvme, 3x8Tb sata-ssd, 4070 Ti S

Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●
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 | RAM: 32GB | GPU: 3090 w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3

Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●

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
Redigera
Citera flera Citera
PermalÀnk
Datavetare ★
●
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
Visa signatur

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

Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●
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
Visa signatur

CPU: 7950X | RAM: 32GB | GPU: 3090 w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3

Redigera
Citera flera Citera
PermalÀnk
Medlem
●

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
Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●

Dag 11 Spoiler:

Redigera
Citera flera Citera
PermalÀnk
Medlem
●

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
Redigera
Citera flera Citera
PermalÀnk
Datavetare ★
●
Skrivet av Gorgonzola:

Dag 11 Spoiler:

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

Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●

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
Visa signatur

CPU: 7950X | RAM: 32GB | GPU: 3090 w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3

Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●
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

Redigera
Citera flera Citera
PermalÀnk
Medlem
●
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)

Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●
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
Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●
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
Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●

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
Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●

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

Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●

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 Lite clean up
Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●
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?

Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●
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

ASUS ROG Strix B650E-F Gaming WIFI | 2 TB Kingston Fury M.2 NVMe SSD | 32 GB Kingston DDR5 | Rysen 7 7800x3D | ASUS GeForce RTX 4070 12 GB | Fractal Design North

Redigera
Citera flera Citera
PermalÀnk
Medlem
●

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
Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●

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
Visa signatur

CPU: 7950X | RAM: 32GB | GPU: 3090 w/ AlphaCool Eisblock Aurora
Ljudkort: Modius + Magnius | Lurar: GoldPlanar GL2000 / Sennheiser HD 650 / Philips Fidelio X3

Redigera
Citera flera Citera
PermalÀnk
Medlem
●

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
Redigera
Citera flera Citera
PermalÀnk
Medlem
●

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
Redigera
Citera flera Citera
PermalÀnk
Medlem ★
●

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
Redigera
Citera flera Citera
8 9 10 11 12 13 14 15
Skriv svar