diff options
| -rw-r--r-- | day13.go | 2 | ||||
| -rw-r--r-- | day15.go | 159 | ||||
| -rw-r--r-- | day15.txt | 28 | ||||
| -rw-r--r-- | flake.nix | 1 | ||||
| -rw-r--r-- | radixsort.go | 48 | ||||
| -rw-r--r-- | selectionsort.go | 23 |
6 files changed, 261 insertions, 0 deletions
@@ -5,6 +5,7 @@ import ( "fmt" "log" "os" + "sort" "strconv" ) @@ -148,6 +149,7 @@ func swap(packets []*packet, key, i int) []*packet { } func quicksort(packets []*packet, comp func(p1, p2 *packet) (int, compcode)) []*packet { + sort.Slice var qs func(p []*packet) qs = func(p []*packet) { key := len(p) - 1 diff --git a/day15.go b/day15.go new file mode 100644 index 0000000..45322a0 --- /dev/null +++ b/day15.go @@ -0,0 +1,159 @@ +package main + +import ( + "bufio" + "fmt" + "log" + "math" + "os" + "regexp" + "strconv" +) + +type empty struct{} + +type Coord struct { + x, y int +} + +type Sensor struct { + loc Coord + closestBeacon Coord +} + +type visiter []byte + +func (v visiter) getNeighbors(c Coord, w, h int, shiftx, shifty int) []byte { + up := (c.x + shiftx + (c.y+shifty-1)*w) % len(v) + down := (c.x + shiftx + (c.y+shifty+1)*w) % len(v) + left := (c.x + shiftx - 1 + (c.y+shifty)*w) % len(v) + right := (c.x + shiftx + 1 + (c.y+shifty)*w) % len(v) + + b := make([]byte, 4) + for i, n := range []int{up, down, left, right} { + if n < 0 { + b[i] = 2 + } else { + b[i] = v[n] + } + } + return b +} + +func (v visiter) visit(c Coord, w, h int, shiftx, shifty int) { + v[(c.x+shiftx+(c.y+shifty)*w)%len(v)] |= 1 +} + +func (v visiter) beacon(c Coord, w, h int, shiftx, shifty int) { + v[(c.x+shiftx+(c.y+shifty)*w)%len(v)] |= 2 +} + +func manhattanDistance(c1, c2 Coord) int { + return int(math.Abs(float64(c2.x-c1.x)) + math.Abs(float64(c2.y-c1.y))) +} + +type rowVisiter []map[Coord]bool + +func (v rowVisiter) visitRow(c Coord, beacon bool, shifty int) { + if _, ok := v[c.y+shifty][c]; !ok { + v[c.y+shifty][c] = beacon + } +} + +func main() { + fi, err := os.Open("day15.txt") + if err != nil { + log.Fatal(err) + } + bs := bufio.NewScanner(fi) + + inputPattern := regexp.MustCompile( + `Sensor at x=(-?\d+), y=(-?\d+): closest beacon is at x=(-?\d+), y=(-?\d+)`, + ) + + sensors := []Sensor(nil) + allcoords := []Coord(nil) + for bs.Scan() { + line := bs.Text() + coordstrings := inputPattern.FindAllStringSubmatch(line, 3)[0][1:] + coords := make([]int, len(coordstrings)) + for i, c := range coordstrings { + n, err := strconv.Atoi(c) + if err != nil { + log.Fatal(err) + } + coords[i] = n + } + c := []Coord{{coords[0], coords[1]}, {coords[2], coords[3]}} + allcoords = append(allcoords, c...) + sensors = append(sensors, Sensor{c[0], c[1]}) + } + + xmax, xmin := 0, 0 + ymax, ymin := 0, 0 + for _, c := range allcoords { + if c.x > xmax { + xmax = c.x + } + if c.x < xmin { + xmin = c.x + } + if c.y > ymax { + ymax = c.y + } + if c.y < ymin { + ymin = c.y + } + } + padding := 0 + xmax, xmin = xmax+padding, xmin-padding + ymax, ymin = ymax+padding, ymin-padding + + width, height := xmax-xmin, ymax-ymin + shiftx, shifty := -xmin, -ymin + visit := make(rowVisiter, height+1) + for i := range visit { + visit[i] = make(map[Coord]bool) + } + fmt.Println(len(visit), width, height, shiftx, shifty) + + for _, s := range sensors { + sensorVisit := make(map[Coord]empty) + toVisit := []Coord{s.loc} + dist := manhattanDistance(s.loc, s.closestBeacon) + visit.visitRow(s.closestBeacon, true, shifty) + fmt.Println("new sensor", s.loc, s.closestBeacon, dist) + for len(toVisit) > 0 { + visiting := toVisit[0] + toVisit = toVisit[1:] + + for _, c := range []Coord{ + {visiting.x, visiting.y + 1}, + {visiting.x, visiting.y - 1}, + {visiting.x - 1, visiting.y}, + {visiting.x + 1, visiting.y}, + } { + if _, ok := sensorVisit[c]; !ok && manhattanDistance(s.loc, c) <= dist { + if c.y+shifty >= len(visit) { + visit = append(visit, make(map[Coord]bool)) + } + if c.y+shifty < len(visit) { + visit = append([]map[Coord]bool{make(map[Coord]bool)}, visit...) + shifty++ + } + visit.visitRow(c, false, shifty) + sensorVisit[c] = empty{} + toVisit = append(toVisit, c) + } + } + } + } + count := 0 + fmt.Println(visit) + for _, beacon := range visit[10+shifty] { + if !beacon { + count++ + } + } + fmt.Println(count) +} diff --git a/day15.txt b/day15.txt new file mode 100644 index 0000000..315b0f4 --- /dev/null +++ b/day15.txt @@ -0,0 +1,28 @@ +Sensor at x=655450, y=2013424: closest beacon is at x=967194, y=2000000 +Sensor at x=1999258, y=1017714: closest beacon is at x=3332075, y=572515 +Sensor at x=2159800, y=3490958: closest beacon is at x=2145977, y=3551728 +Sensor at x=3990472, y=1891598: closest beacon is at x=3022851, y=2629972 +Sensor at x=188608, y=354698: closest beacon is at x=-1037755, y=-391680 +Sensor at x=286630, y=3999086: closest beacon is at x=-1202308, y=3569538 +Sensor at x=2022540, y=3401295: closest beacon is at x=2013531, y=3335868 +Sensor at x=65063, y=2648597: closest beacon is at x=967194, y=2000000 +Sensor at x=2533266, y=439414: closest beacon is at x=3332075, y=572515 +Sensor at x=1728594, y=2416005: closest beacon is at x=967194, y=2000000 +Sensor at x=1156357, y=1867331: closest beacon is at x=967194, y=2000000 +Sensor at x=825519, y=3323952: closest beacon is at x=2013531, y=3335868 +Sensor at x=3278267, y=201451: closest beacon is at x=3332075, y=572515 +Sensor at x=3679732, y=1213595: closest beacon is at x=3332075, y=572515 +Sensor at x=896808, y=1637672: closest beacon is at x=967194, y=2000000 +Sensor at x=2035362, y=3363480: closest beacon is at x=2013531, y=3335868 +Sensor at x=2056169, y=3442413: closest beacon is at x=2013531, y=3335868 +Sensor at x=2631999, y=1884495: closest beacon is at x=3022851, y=2629972 +Sensor at x=3149604, y=3870003: closest beacon is at x=3707835, y=4152776 +Sensor at x=3579002, y=1702: closest beacon is at x=3332075, y=572515 +Sensor at x=2306088, y=2605428: closest beacon is at x=3022851, y=2629972 +Sensor at x=2428132, y=3171598: closest beacon is at x=2013531, y=3335868 +Sensor at x=1447212, y=3938104: closest beacon is at x=2145977, y=3551728 +Sensor at x=3131240, y=3166665: closest beacon is at x=3022851, y=2629972 +Sensor at x=3865496, y=2980765: closest beacon is at x=3022851, y=2629972 +Sensor at x=2508598, y=3611761: closest beacon is at x=2145977, y=3551728 +Sensor at x=2144092, y=3514660: closest beacon is at x=2145977, y=3551728 +Sensor at x=3947251, y=469499: closest beacon is at x=3332075, y=572515 @@ -15,6 +15,7 @@ nativeBuildInputs = [pkgs.bashInteractive]; buildInputs = with pkgs; [ go_1_19 + gotests gofumpt gotools (pkgs.buildGoModule rec { diff --git a/radixsort.go b/radixsort.go new file mode 100644 index 0000000..806a5f8 --- /dev/null +++ b/radixsort.go @@ -0,0 +1,48 @@ +package main + +import ( + "fmt" + "math/rand" +) + +const ( + signedMin = -(1 << 31) + signedMax = (1 << 31) - 1 +) + +func countsort(in []int32, r uint32) { + count := make([]int32, r) + + for i := range in { + count[in[i]]++ + } + + for i := 1; i < len(in)-1; i++ { + count[i] += count[i-1] + } + + var pointer int32 + for i := 0; i < len(count)-1; i++ { + for count[i] > 0 && pointer < count[i] { + in[pointer] = int32(i) + pointer++ + } + } +} + +func radix() { +} + +func input(r *rand.Rand, n int) []int32 { + out := make([]int32, n) + for i := 0; i < n; i++ { + out[i] = int32(r.Intn(signedMax)) + } + return out +} + +func main() { + in := input(rand.New(rand.NewSource(1)), 1<<8) + countsort(in, signedMax) + fmt.Println(in) +} diff --git a/selectionsort.go b/selectionsort.go new file mode 100644 index 0000000..67a33cf --- /dev/null +++ b/selectionsort.go @@ -0,0 +1,23 @@ +package main + +import "fmt" + +var sortingdata []int = []int{1, 23, 4, 234, 123, 4, 4512, 0} + +func selectionSort(in []int) []int { + end := len(in) + for i := 0; i < end; i++ { + min := i + for j := i; j < end; j++ { + if in[j] < in[min] { + min = j + } + } + in[i], in[min] = in[min], in[i] + } + return in +} + +func main() { + fmt.Println(selectionSort(sortingdata)) +} |