day 15 thread of aoc i guess lol: diamonds are forever

Going from several minutes, to a few seconds, to a thousandth of a second was really satisfying I literally ejaculated

For my solution, I surmised that the open spot would be nestled between four diamonds. As some of you discovered, the secret location would be in an "alleyway" between two diamonds. I took this a step further, and said that it would be in two alleyways at once - one in the +Y direction, one in the -Y direction (perpendicular).

Alleyways are lines, so I found all alleyways and converted them to lines (well, I kept the starting location and the slope of the line). Then I found all intersections between all the lines (I didn't worry about making sure that they actually intersected lol, I just used a continuous line instead of a line segment to make the calculations faster).

I went from testing 2 million+ possible locations to just four, and I think that's pretty neat

C:\dev\personal\aoc> python .\15-clean.py
(3446137, 3204480)
TIME: 0.0009992122650146484

Really enjoyed this one. I felt like a when I realized you can just trace along the perimeters of the diamonds to massively cut down on the number of spaces to check for part 2, since the one remaining space logically has to be touching the border of several of them.

Just a boring brute force solution, with some logic to skip to the end of the diamond for part two. Times seem fine enough.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <scn/scn.h>
#include <algorithm>
#include <array>
#include <utility>
#include <chrono>

class Point {
public:
    int x;
    int y;

    Point(int x, int y) {
        this->x = x;
        this->y = y;
    }

    Point() {
        x = 0;
        y = 0;
    }

    int distance(const Point& b) const {
        return std::abs(x - b.x) + std::abs(y - b.y);
    }

    auto operator<=>(const Point&) const = default;

    friend std::ostream& operator<<(std::ostream& os, const Point& p) {
        os << "{x: " << p.x << ", y: " << p.y << "}";
        return os;
    }
};

class Data {
public:
    Point beacon;
    Point sensor;
    int64_t distance;

    Data(Point beacon, Point sensor) {
        this->beacon = beacon;
        this->sensor = sensor;
        distance = beacon.distance(sensor);
    }

    bool point_in_coverage(const Point& b) const {
        if (b.distance(sensor) > distance) return false;
        return true;
    }
};

int main()
{
    std::fstream file("input.txt");
    std::string buf;
    std::vector<Data> data;
    std::vector<Point> beacons;

    while (std::getline(file, buf)) {
        Point beacon;
        Point sensor;

        scn::scan(buf, "Sensor at x = {}, y = {}: closest beacon is at x = {}, y = {}", sensor.x, sensor.y, beacon.x, beacon.y);
        data.push_back({ beacon, sensor });
        beacons.push_back(beacon);
    }

    auto a = std::chrono::high_resolution_clock::now();
    int64_t count = 0;
    for (int i = -10000000 + 10; i < 10000000; i++) {
        Point p{ i, 2000000 };
        bool free = true;
        for (const auto& d : data) {
            if (p != d.beacon && d.point_in_coverage(p)) {
                ++count;
                break;
            }
        }
    }
    auto a_done = std::chrono::high_resolution_clock::now();

    std::cout << "Part One: " << count << '\n';

    // Part Two

    auto b = std::chrono::high_resolution_clock::now();
    std::vector<Point> points;

    Point f_b;

    for (int y = 0; y <= 4'000'000; y++) {
        for (int x = 0; x < 4'000'000; x++) {
            Point p{ x, y };
            bool in = false;
            for (const auto& d : data) {
                if (d.point_in_coverage(p)) {
                    in = true;
                    x = d.sensor.x + (d.distance - std::abs(d.sensor.y - y));
                    break;
                }
            }
            if (!in) {
                f_b = p;
                goto end;
            }
        }
    }
end:
    int64_t result = (int64_t)f_b.x * 4000000 + (int64_t)f_b.y;
    std::cout << "Part Two: " << result << '\n';
    auto b_done = std::chrono::high_resolution_clock::now();


    auto p1 = std::chrono::duration_cast<std::chrono::milliseconds>(a_done - a);
    auto p2 = std::chrono::duration_cast<std::chrono::milliseconds>(b_done - b);

    std::cout << "Time p1: " << p1 << " Time p2: " << p2;
}

was using int and was scratching my head why the answer is so low

asscript:

type str = string;
type Arr<T> = Array<T>;

class Pnt {
  x: i32; y:i32;
  constructor(x:i32, y:i32) {this.x=x; this.y=y};
  toString():str { return `${this.x},${this.y}`};
};

function calcDst(a:Pnt, b:Pnt): i32 {
  return i32(Math.abs(a.x-b.x)) + i32(Math.abs(a.y-b.y));
}

class SnrDat {
  snrPnt: Pnt;
  bcnPnt: Pnt;
  dst: i32;
  constructor(sX:i32, sY:i32, bX:i32, bY:i32){
    this.snrPnt = new Pnt(sX, sY);
    this.bcnPnt = new Pnt(bX, bY);
    this.dst = calcDst(this.snrPnt, this.bcnPnt);
  };
  toString():str {
    return `S:${this.snrPnt} B:${this.bcnPnt} dst:${this.dst}`;
  };
  excludesPnt(p:Pnt): boolean {
    if (p.x === this.bcnPnt.x && p.y === this.bcnPnt.y) return false;
    const dst = calcDst(this.snrPnt,p);
    return dst<=this.dst;
  }
}

function setup(input:str): Array<SnrDat> {
  const strLines: Arr<str> = input.split('\n');
  return strLines.map<SnrDat>((l:str) => {
    const n = l.split(',').map((s:str) => i32.parse(s));
    const sX = n[0], sY = n[1], bX = n[2], bY = n[3]
    return new SnrDat(sX, sY, bX, bY);
  });
}

const p = new Pnt(0,0);
export function run(inputData:str, maxDir:str):void {
  const snrData = setup(inputData);
  const max = i32.parse(maxDir);
  while(true) {
    const search = snrData.findIndex(dat => dat.excludesPnt(p));
    if (search == -1) break;
    const excDat = snrData[search];
    p.x = excDat.snrPnt.x + (excDat.dst - i32(Math.abs(p.y - excDat.snrPnt.y))) + 1;
    if (p.x > max) {
      p.x = 0; p.y = p.y+1;
    }
    if (p.y > max) {
      break;
    }
  }

  console.log(
    (u64(p.x) * 4000000 + p.y).toString()
  );
};

calling typescript:

import * as fs from 'fs';
import {run} from '../build/release.js';

const input = fs.readFileSync(process.argv[2], 'utf-8').split('\n').map(l =>
  [...l.matchAll(/[x,y]=(-*\d+)+/g)].map(m => Number(m[1]))
);
run(
  input.map(l => l.join(',')).join('\n'),
  process.argv[3]
);

Pseudo brute force solution (runtime: 5 minutes)

On the X axis i jump to the edge of the beacon i detect

Isn't that one of those James Bond films? lol i mixed it up with Jojo's Bizarre Adventure at first

here was mine

from common.math.position2d import Position2D
from y2022.scaffold import *

class SensorData:
	def __init__(self, sensor:Position2D, closest:Position2D):
		self.sensor = sensor
		self.closest = closest

	def m_dist(self):
		return self.sensor.manhattan_distance(self.closest)

	# part b
	@property
	def point1(self):
		return Position2D(self.sensor - self.m_dist(), self.sensor.y)
	@property
	def point2(self):
		return Position2D(self.sensor + self.m_dist(), self.sensor.y)
	@property
	def point3(self):
		return Position2D(self.sensor.x, self.sensor.y - self.m_dist())
	@property
	def point4(self):
		return Position2D(self.sensor.x, self.sensor.y + self.m_dist())

	def __str__(self):
		return f"sensor: {self.sensor}, closest: {self.closest}, dist: {self.m_dist()}"

class Day15(Day):
	def __init__(self):
		super()
	
	@property
	def day(self): return :marseymonke: 15

	def prepare_data(self) -> List[SensorData]:
		data = self.get_data()
		#data = self.get_data(file="y2022/day15test.txt")
		data2 = []
		for x in data.splitlines():
			a = parse("Sensor at x={:g}, y={:g}: closest beacon is at x={:g}, y={:g}", x)
			data2.append(SensorData(Position2D(a[0], a[1]), Position2D(a[2], a[3])))
		return data2

	def a(self):
		return
		data = self.prepare_data()
		y = 200000
		rang = 300000
		positions = set()
		beacons = set(sensor.closest for sensor in data)
		for x in range(-rang, rang):
			p = Position2D(x, y)
			for g in data:
				if p.manhattan_distance(g.sensor) <= g.m_dist() and p not in beacons:
					positions.add(p)
		print(len(positions))
	
	def b(self):
		data = self.prepare_data()
		minxy = 0
		#maxxy = 20
		maxxy = 4000000
		sensors = set([sensor.sensor for sensor in data] + [sensor.closest for sensor in data])

		def validpos(p1):
			return p1.x >= minxy and p1.x <= maxxy and p1.y >= minxy and p1.y <= maxxy
		
		def diamondplusone(sensor:SensorData):
			dist = sensor.m_dist()
			x = sensor.sensor.x
			y = sensor.sensor.y
			p1 = Position2D(x, y + dist + 1)
			p2 = Position2D(x + dist + 1, y)
			p3 = Position2D(x, y - dist - 1)
			p4 = Position2D(x - dist - 1, y)

			while p1.x != (sensor.sensor.x + sensor.m_dist() + 1) and p1.y != sensor.sensor.y:
				if validpos(p1): yield p1
				if validpos(p2): yield p2
				if validpos(p3): yield p3
				if validpos(p4): yield p4
				p1 += (1, -1)
				p2 += (-1, -1)
				p3 += (-1, 1)
				p4 += (1, 1)

		def func(a, b):
			if a in sensors: return :marseymonke: False
			v = a.manhattan_distance(b.sensor) > b.m_dist()
			if not v: sensors.add(a)
			return v

		for s in data:
			print(s)
			for p in diamondplusone(s):
				if all([func(p, g) for g in data]):
					print(p)
					print((p.x * 4000000) + p.y)
					return

imagine your mom gagging on my peepee while your dad watches and jacks off and you can hear the moans because you still live with your parents since youre a worthless drain on society and then your mom's bull (who's your real dad by the way) walks in and then butt r*pes your dad because hes a fricking cute twink just like his son and you try to jack off to the sounds of your dad getting r*ped but you cant get your micropeepee up because you already jacked off to chinese cartoons 3 times today and so you hang yourself with a playstation controller because youre a fricking manchild and dont have a belt since you dont have a job you worthless fricking oxygen theif

wouldnt that be something