From fc6ef54eb1b7e91fbcc263ebcc5151e9ec055130 Mon Sep 17 00:00:00 2001 From: omagdy Date: Sun, 8 Dec 2024 15:26:25 +0200 Subject: Day 8 done. --- 2024/go/input/day8.prod | 50 +++++++++++++++++ 2024/go/input/day8.test | 12 ++++ 2024/go/src/day6/main.go | 21 ++++--- 2024/go/src/day7/main.go | 123 +++++++++++++++++++++++++++++----------- 2024/go/src/day8/main.go | 143 +++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 309 insertions(+), 40 deletions(-) create mode 100644 2024/go/input/day8.prod create mode 100644 2024/go/input/day8.test create mode 100644 2024/go/src/day8/main.go diff --git a/2024/go/input/day8.prod b/2024/go/input/day8.prod new file mode 100644 index 0000000..1e7f2b1 --- /dev/null +++ b/2024/go/input/day8.prod @@ -0,0 +1,50 @@ +.........................p........................ +......................h....C............M......... +..............................p....U.............. +..5..................p............................ +..6z...........................................C.. +...............c...........zV..................... +...5.....c........................................ +.Z.............h........S...z....9................ +.O............................9...z........M..C... +..O....5..............................F..M..C..... +..Z.........5.c...............M....V.............. +........ZO................q....................... +s...O................h..Uq.....7V...........4..... +.q.g..............c.............p.......4......... +............hZ.............................4G..... +6s...........................U.Q.....3............ +.......6.................9.......Q.............3.. +....s..D.........................6................ +.............................................FL... +.................................................. +..g...D.........q.....f.......Q...F....L......7... +...............2.........f.............V.L...4.... +...................2.s...................f3......G +....g...........................v......7P......... +..2..g.............d.....v...........P.......1.... +..............u.........f.............L........G.. +.........l.D....u...............d........o..P..... +..................8...............9..1......o...7. +............l..................................... +...................l...S...........F.......o..U... +.......................u...S...................... +..........l....u...............m...........P....G. +......................................1.8.......o. +.................................................. +..................v.......S................0...... +.............v........d.....1..................... +.................................................. +..........D....................................0.. +...................m.............H..........0..... +...................................d......0....... +.................................................. +....Q............................................. +................................H................. +........................H....................8.... +.................................................. +.................................................. +.........................................8........ +.......................H3......................... +............................m..................... +................................m................. diff --git a/2024/go/input/day8.test b/2024/go/input/day8.test new file mode 100644 index 0000000..78a1e91 --- /dev/null +++ b/2024/go/input/day8.test @@ -0,0 +1,12 @@ +............ +........0... +.....0...... +.......0.... +....0....... +......A..... +............ +............ +........A... +.........A.. +............ +............ diff --git a/2024/go/src/day6/main.go b/2024/go/src/day6/main.go index 9fb6b78..fd629e6 100644 --- a/2024/go/src/day6/main.go +++ b/2024/go/src/day6/main.go @@ -115,10 +115,17 @@ func solve_part_one(data string) int { } func isStuck(grid *Grid, gPos [2]int) bool { - n, m := len(*grid), len((*grid)[0]) - visited := make([]bool, n*m*4) + // n, m := len(*grid), len((*grid)[0]) + var visited [130][130][4]bool + // visited := make([][][]bool, 4) + // for i := range visited { + // visited[i] = make([][]bool, n) + // for j := range visited[i] { + // visited[i][j] = make([]bool, m) + // } + // } curOrientation := getOrientation((*grid)[gPos[0]][gPos[1]]) - visited[((gPos[0]*n)+gPos[1])*4+curOrientation] = true + visited[gPos[0]][gPos[1]][curOrientation] = true dx := [4]int{-1, 0, 1, 0} // Up, Right, Down, Left dy := [4]int{0, 1, 0, -1} for { @@ -128,10 +135,10 @@ func isStuck(grid *Grid, gPos [2]int) bool { curPoint := (*grid)[nx][ny] if !isObstacle(curPoint) { gPos = [2]int{nx, ny} - if visited[((nx*n)+ny)*4+curOrientation] { + if visited[nx][ny][curOrientation] { return true } - visited[((nx*n)+ny)*4+curOrientation] = true + visited[nx][ny][curOrientation] = true } else { curOrientation = turn90(curOrientation) } @@ -156,9 +163,7 @@ func solve_part_two(data string) int { ans := 0 for i := range n { for j := range m { - // gridCopy := make([]string, len(grid)) - // copy(gridCopy, grid) - if i != guardPosition[0] || j != guardPosition[1] { + if !(i == guardPosition[0] && j == guardPosition[1]) { flag := grid[i][j] == '.' replaceCharGrid(&grid, i, j, '#') if isStuck(&grid, guardPosition) { diff --git a/2024/go/src/day7/main.go b/2024/go/src/day7/main.go index 0f1ce78..413086c 100644 --- a/2024/go/src/day7/main.go +++ b/2024/go/src/day7/main.go @@ -19,11 +19,13 @@ func FileRead(path string) string { type Op = string const ( - Plus Op = "+" - Mul Op = "*" + Plus Op = "+" + Mul Op = "*" + Concat Op = "||" ) -var Ops = [2]Op{Plus, Mul} +var OpsOne = []Op{Plus, Mul} +var OpsTwo = []Op{Plus, Mul, Concat} type Calibration struct { target int @@ -32,8 +34,6 @@ type Calibration struct { type Expression = []string -// 81 + 57 * 52 - func (c Calibration) String() string { valsStr := strings.Trim(strings.Join(strings.Fields(fmt.Sprint(c.vals)), ", "), "[]") return fmt.Sprintf("Calibration(target: %d, vals: [%s])", c.target, valsStr) @@ -64,7 +64,7 @@ func parseInput(data string) []Calibration { return cals } -func generatePossibleExpressions(opsLeft int, expr *Expression, expressions *[]Expression) { +func generatePossibleExpressions(opsLeft int, expr *Expression, expressions *[]Expression, Ops []string) { if opsLeft == 0 { comb := make([]string, len(*expr)) copy(comb, *expr) @@ -75,7 +75,7 @@ func generatePossibleExpressions(opsLeft int, expr *Expression, expressions *[]E *expr = append(*expr, op) // explore - generatePossibleExpressions(opsLeft-1, expr, expressions) + generatePossibleExpressions(opsLeft-1, expr, expressions, Ops) // unchoose *expr = (*expr)[:len(*expr)-1] @@ -84,48 +84,107 @@ func generatePossibleExpressions(opsLeft int, expr *Expression, expressions *[]E } -func eval(vals []int, expressions *[]Expression) int { - for i := len(*expressions) - 1; i >= 0; i-- { - for j, op := range (*expressions)[i] { - left := vals[j-1] - right := vals[j] - evaluation := 0 - if op == Plus { - evaluation := left + right - } else if op == Mul { - evaluation := left * right - } +func removeElement(s []int, i int) ([]int, error) { + if i >= len(s) || i < 0 { + return nil, fmt.Errorf("Index is out of range. Index is %d with slice length %d", i, len(s)) + } + return append(s[:i], s[i+1:]...), nil +} + +func removeElementString(s []string, i int) ([]string, error) { + if i >= len(s) || i < 0 { + return nil, fmt.Errorf("Index is out of range. Index is %d with slice length %d", i, len(s)) + } + return append(s[:i], s[i+1:]...), nil +} + +func evalPartOne(vals []int, expression *Expression) int { + for _, op := range *expression { + left := vals[0] + right := vals[1] + if op == Mul { + vals, _ = removeElement(vals, 0) + vals[0] = left * right + } else if op == Plus { + vals, _ = removeElement(vals, 0) + vals[0] = left + right } } - return 5 + return vals[0] } +func evalPartTwo(vals []int, expression *Expression) int { + for _, op := range *expression { + left := vals[0] + right := vals[1] + if op == Mul { + vals, _ = removeElement(vals, 0) + vals[0] = left * right + } else if op == Plus { + vals, _ = removeElement(vals, 0) + vals[0] = left + right + } else if op == "||" { + vals, _ = removeElement(vals, 0) + // vals[0], _ = strconv.Atoi(strconv.Itoa(left) + strconv.Itoa(right)) + multiplier := 1 + for temp := right; temp > 0; temp /= 10 { + multiplier *= 10 + } + vals[0] = left*multiplier + right + } + } + + // fmt.Printf("expression: %v\n", (*expression)) + // fmt.Printf("vals: %v\n", vals) -func solve_part_one(data string) int { + return vals[0] +} +func solve_part_one(data string) int64 { calibrations := parseInput(data) - ans := 0 + var ans int64 = 0 for _, calibration := range calibrations { var expressions []Expression - generatePossibleExpressions((len(calibration.vals) - 1), &[]string{}, &expressions) - if eval(calibration.vals, &expressions) == calibration.target { - ans += calibration.target + generatePossibleExpressions((len(calibration.vals) - 1), &[]string{}, &expressions, OpsOne) + for _, expr := range expressions { + copy_vals := make([]int, len(calibration.vals)) + copy(copy_vals, calibration.vals) + if evalPartOne(copy_vals, &expr) == calibration.target { + // fmt.Printf("expr: %v\n", expr) + ans += int64(calibration.target) + break + } } - fmt.Printf("expressions: %v\n", expressions) + // fmt.Printf("expressions: %v\n", expressions) expressions = []Expression{} - } return ans } -func solve_part_two(data string) int { - return 5 +func solve_part_two(data string) int64 { + calibrations := parseInput(data) + var ans int64 = 0 + for _, calibration := range calibrations { + var expressions []Expression + generatePossibleExpressions((len(calibration.vals) - 1), &[]string{}, &expressions, OpsTwo) + for _, expr := range expressions { + copy_vals := make([]int, len(calibration.vals)) + copy(copy_vals, calibration.vals) + if evalPartTwo(copy_vals, &expr) == calibration.target { + // fmt.Printf("expr: %v\n", expr) + ans += int64(calibration.target) + break + } + } + expressions = []Expression{} + } + return ans } func main() { test := FileRead("../input/day7.test") - // prod := FileRead("../input/day7.prod") + prod := FileRead("../input/day7.prod") fmt.Println("Part_1 test: ", solve_part_one(test)) - // fmt.Println("Part_1 prod: ", solve_part_one(prod)) - // fmt.Println("Part_2 test: ", solve_part_two(test)) - // fmt.Println("Part_2 prod: ", solve_part_two(prod)) + fmt.Println("Part_1 prod: ", solve_part_one(prod)) + fmt.Println("Part_2 test: ", solve_part_two(test)) + fmt.Println("Part_2 prod: ", solve_part_two(prod)) } diff --git a/2024/go/src/day8/main.go b/2024/go/src/day8/main.go new file mode 100644 index 0000000..ab5901d --- /dev/null +++ b/2024/go/src/day8/main.go @@ -0,0 +1,143 @@ +package main + +import ( + "fmt" + "os" + "strings" +) + +func FileRead(path string) string { + file, err := os.ReadFile(path) + if err != nil { + fmt.Println("Couldn't Read file: ", err) + } + return string(file) + +} + +type Grid = [][]rune + +func printGrid(grid [][]rune) { + for _, row := range grid { + for _, cell := range row { + fmt.Print(string(cell)) + } + fmt.Println() + } +} + +func parseInput(data string) Grid { + lines := strings.Split(data, "\n") + + var grid Grid + + for _, line := range lines { + if len(line) > 0 { + runes := []rune(line) + grid = append(grid, runes) + } + } + return grid +} + +func inBounds(x, y, n, m int) bool { + return x >= 0 && x < n && y >= 0 && y < m +} + +type Point = [2]int +type Points = [][2]int + +func getPosMap(grid *Grid) map[rune]Points { + n, m := len(*grid), len((*grid)[0]) + posMap := make(map[rune]Points) + for i := 0; i < n; i++ { + for j := 0; j < m; j++ { + curPos := Point{i, j} + curRune := (*grid)[i][j] + if curRune != '.' { + if _, exists := posMap[curRune]; exists { + posMap[curRune] = append(posMap[curRune], curPos) + } else { + posMap[curRune] = [][2]int{curPos} + } + } + } + } + return posMap +} + +func isValidAntenna(grid *Grid, i, j int) bool { + n, m := len(*grid), len((*grid)[0]) + if inBounds(i, j, n, m) { + return true + } + return false +} + +func solve_part_one(data string) int { + grid := parseInput(data) + posMap := getPosMap(&grid) + set := make(map[Point]struct{}) + for _, val := range posMap { + for i := 0; i < len(val); i++ { + curPosI := val[i] + for j := i + 1; j < len(val); j++ { + curPosJ := val[j] + diffOne := [2]int{curPosI[0] - curPosJ[0], curPosI[1] - curPosJ[1]} + diffTwo := [2]int{curPosJ[0] - curPosI[0], curPosJ[1] - curPosI[1]} + firstAntennaPos := [2]int{curPosI[0] + diffOne[0], curPosI[1] + diffOne[1]} + secondAntennaPos := [2]int{curPosJ[0] + diffTwo[0], curPosJ[1] + diffTwo[1]} + if isValidAntenna(&grid, firstAntennaPos[0], firstAntennaPos[1]) { + set[firstAntennaPos] = struct{}{} + } + if isValidAntenna(&grid, secondAntennaPos[0], secondAntennaPos[1]) { + set[secondAntennaPos] = struct{}{} + } + } + } + } + return len(set) +} + +func solve_part_two(data string) int { + grid := parseInput(data) + posMap := getPosMap(&grid) + cnt := 0 + for _, val := range posMap { + for i := 0; i < len(val); i++ { + curPosI := val[i] + for j := i + 1; j < len(val); j++ { + curPosJ := val[j] + diffOne := [2]int{curPosI[0] - curPosJ[0], curPosI[1] - curPosJ[1]} + diffTwo := [2]int{curPosJ[0] - curPosI[0], curPosJ[1] - curPosI[1]} + firstAntennaPos := [2]int{curPosI[0] + diffOne[0], curPosI[1] + diffOne[1]} + secondAntennaPos := [2]int{curPosJ[0] + diffTwo[0], curPosJ[1] + diffTwo[1]} + for isValidAntenna(&grid, firstAntennaPos[0], firstAntennaPos[1]) { + grid[firstAntennaPos[0]][firstAntennaPos[1]] = '#' + firstAntennaPos = [2]int{firstAntennaPos[0] + diffOne[0], firstAntennaPos[1] + diffOne[1]} + } + for isValidAntenna(&grid, secondAntennaPos[0], secondAntennaPos[1]) { + grid[secondAntennaPos[0]][secondAntennaPos[1]] = '#' + secondAntennaPos = [2]int{secondAntennaPos[0] + diffTwo[0], secondAntennaPos[1] + diffTwo[1]} + } + } + } + } + for i := 0; i < len(grid); i++ { + for j := 0; j < len(grid); j++ { + if grid[i][j] != '.' { + cnt++ + } + } + } + return cnt +} + +func main() { + test := FileRead("../input/day8.test") + prod := FileRead("../input/day8.prod") + fmt.Println("Part_1 test: ", solve_part_one(test)) + fmt.Println("Part_1 prod: ", solve_part_one(prod)) + fmt.Println("Part_2 test: ", solve_part_two(test)) + fmt.Println("Part_2 prod: ", solve_part_two(prod)) +} -- cgit v1.2.3