Advent of Code 2022 : Day 9

Instead of sharing code, I wonder: Whats the fastest way to do part 2? Its not hard to get Part 1 to O(N) time, but I gave up on Part 2 and did it in O(N^3) time lol. (Iterating over each tail piece for each tile moved for each move). I imagine you can do it in at least O(N^2) if you tried, tho

Extremely tidied up version. Actual one for the first star I tracked the pre-move head position and set tail to it if non-adjacent post-move. Second star I exhaustively cased all 8 relative positions because however I did the absolute value math the first time didn't work and I didn't want to frick with it.

Another fun trick: use Python's complex numbers as coordinates:

    snek = [0j] * (10 if second else 2)
    visited = set([0j])

    def moveh(c, h):
        return h + {'U': 1j, 'R': 1, 'D': -1j, 'L': -1}[c]

    def movet(h, t):
        diff = h - t
        if abs(diff.real) > 1 and abs(diff.imag) > 1:
            return (t.real + diff.real / 2) + 1j * (t.imag + diff.imag / 2)
        elif abs(diff.real) > 1:
            return (t.real + diff.real / 2) + 1j * h.imag
        elif abs(diff.imag) > 1:
            return h.real                   + 1j * (t.imag + diff.imag / 2)
        return t

    for s in data:
        dir, dist = s.split()
        for _ in range(int(dist)):
            snek[0] = moveh(dir, snek[0])
            for i in range(len(snek) - 1):
                snek[i + 1] = movet(snek[i], snek[i + 1])
            visited.add(snek[-1])

    return len(visited)

edit: thx to @hbtz

    def movet(h, t):
        d = h - t
        if abs(d.real) > 1 or abs(d.imag) > 1:
            return t + d.real / max(1, abs(d.real)) + 1j * d.imag / max(1, abs(d.imag))
        return t

still ezpz

*** stack smashing detected ***: terminated
Annullato (core dump creato)

C++chads simply cannot stop winning

I've been filtered by p2 for over 2 hours because somehow

vec = sign(pos(i,:)-pos(i+1,:));

pos(i+1,:) = pos(i+1,:) + vec;

isn't the same as

pos(i+1,:) = pos(i+1,:) + sign(pos(i,:)-pos(i+1,:));

I hate matlab so much it's unreal. There is literally no reason this should ever happen

frick me this ones gonna suck

I did part a without classes. Part b is reworked that also works with part a

with open('input09.txt') as file:
    lines = [line.strip().split(' ') for line in file]


# part b
class Segment:
    def __init__(self, link_down) -> None:
        self.x = 0
        self.y = 0
        self.link_down = link_down
        self.visited = set()
        
    def move(self, x, y):
        self.x += x
        self.y += y
        if self.link_down != None:
            self.link_down.update(self)
        
    def update(self, link_up):
        distance_x = abs(link_up.x - self.x)
        distance_y = abs(link_up.y - self.y)
        if distance_x >= 2 or distance_y >= 2:
            self.x += min(max(link_up.x - self.x, -1), 1)
            self.y += min(max(link_up.y - self.y, -1), 1)
        if self.link_down != None:
            self.link_down.update(self)
        else:
            self.visited.add('{}/{}'.format(self.x, self.y))


tail = Segment(None)
head_seg = tail
for i in range(9): # 1 for part a
    seg = Segment(head_seg)
    head_seg = seg

for line in lines:
    if line[0] == 'R':
        for i  in range(int(line[1])):
            head_seg.mp4e(1,0)
    elif line[0] == 'L':
        for i  in range(int(line[1])):
            head_seg.mp4e(-1,0)
    elif line[0] == 'U':
        for i  in range(int(line[1])):
            head_seg.mp4e(0,1)
    else:
        for i  in range(int(line[1])):
            head_seg.mp4e(0,-1)
print("Tail visited:",len(tail.visited))

I got filtered for a LONG time on part 2 because my logic was setting the head to whatever position it should be in, then iterating all the steps of the tail pieces from where they are to where they should be. I still feel like this should have worked, it worked fine on the test inputs.

I switched it to move the head one space at a time and then iterate the tail pieces every time it moved and got a slightly different (but correct) answer.

Edit: code, spits out part 1 in s[1] and part 2 in s[9]

var lines = document.body.innerText.split("\n");
lines.splice(lines.length-1,1);

var h = {x: 0,y: 0};
var t = {x: 0,y: 0};
var k = [];
var s = [];
s[0] = new Set();

for (var i=0;i<10;i++) {
    k[i] = {x: 0,y: 0};
}

function moveH(x,y) {
    k[0].x += x;
    k[0].y += y;
    s[0].add(k[0].x.toString() + "," + k[0].y.toString());
  
    for (var i=1; i<10; i++) {
        moveK(k[i-1],k[i],i);
    }
}

function norm(v) {
    return { 
        x: (!v.x ? 0 : (v.x > 0 ? 1 : -1)),
        y: (!v.y ? 0 : (v.y > 0 ? 1 : -1))
    };
}

function moveK(last,current,index) {
    var d = {x: last.x - current.x, y: last.y - current.y};

    if (!s[index]) {
        s[index] = new Set();
        s[index].add("0,0");
    }

    while (Math.abs(d.x) > 1 || Math.abs(d.y) > 1) {
        var nd = norm(d);
        current.x += nd.x;
        current.y += nd.y;
        d.x -= nd.x;
        d.y -= nd.y;
        s[index].add(current.x.toString() + "," + current.y.toString());
    }
}

lines.forEach(function(line) {
    var args = line.split(" ");
    var n = !isNaN(Number(args[1])) ? Number(args[1]) : 0;
    for (var i=0;i<args[1];i++) {      
        switch (args[0]) {
            case 'U':
                moveH(0,-1);
                break;
            case 'L':
                moveH(-1,0);
                break;
            case 'R':
                moveH(1,0);
                break;
            case 'D':
                moveH(0,1);
                break;
        }
    }
});

In my part one, i just set the tail = previous position of head, if head and tail were >sqrt(2) away, took me way to long, to notice it

#include <iostream> 
#include <cmath>
#include <set>
#include <fstream>
#include <string>
#include <vector>
#include <numbers>

struct Point {
    int x = 0;
    int y = 0;

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

    double inline distance(const Point& b) const {
        return std::sqrt(
            std::pow(x - b.x, 2) +
            std::pow(y - b.y, 2)
        );
    }

    Point calculate_move_vector(const Point& p) const {
        Point out;
        out.x = (p.x - x);
        out.y = (p.y - y);
        if(out.x != 0) out.x = out.x / std::abs(out.x);
        if(out.y != 0) out.y = out.y / std::abs(out.y);
        return out;
    }

    Point& operator+=(const Point& p) {
        this->x += p.x;
        this->y += p.y;
        return *this;
    }
};

struct Instruction {
    char direction;
    int moves;
};

void move(std::vector<Point>& knots, Instruction ins, std::set<Point>& v) {
    Point dir;
    if (ins.direction == 'R') dir = { 1, 0 };
    else if (ins.direction == 'U') dir = { 0, 1 };
    else if (ins.direction == 'L') dir = { -1, 0 };
    else dir = { 0, -1 };

    while (ins.mp4es > 0) {
        ins.mp4es = ins.mp4es - 1;
        knots[0] += dir;
        for (size_t i{ 1 }; i < knots.size(); ++i) {
            if (knots[i - 1].distance(knots[i]) > std::numbers::sqrt2_v<double>) knots[i] += knots[i].calculate_move_vector(knots[i - 1]);
        }
        v.insert(knots.back());
    }
}


int main()
{
    std::set<Point> visited_part_one;
    std::set<Point> visited_part_two;

    std::vector<Point> partOne{ { 0, 0 } , { 0, 0 } };
    std::vector<Point> partTwo(10);

    std::ifstream file("input.txt");

    std::string line;
    char cmd;
    while (file >> cmd) {
        Instruction ins;
        ins.direction = cmd;
        file >> ins.mp4es;
        move(partOne, ins, visited_part_one);
        move(partTwo, ins, visited_part_two);
    }
    std::cout << "Part One:" << visited_part_one.size() << '\n';
    std::cout << "Part Two:" << visited_part_two.size() << '\n';

    return -1;
}

Lost like 9 minutes because I forgot to add the final position to the visited set

import numpy as np
def updateTail(chx,chy,ctx,cty):
    dx = chx-ctx
    dy = chy-cty
    if max(abs(dx),abs(dy)) < 2:
        return (ctx,cty)
    if dx == 0 and abs(dy) == 2:
        cty += dy//2
        return (ctx,cty)
    if dy == 0 and abs(dx) == 2:
        ctx += dx//2
        return (ctx,cty)
    else:
        return (ctx+dx//abs(dx),cty+dy//abs(dy))
def updateKnots(chx,chy,knots):
    for i in range(len(knots)):
        knots[i] = updateTail(chx,chy,knots[i][0],knots[i][1])
        chx,chy = knots[i][0],knots[i][1]
    return knots

f = open('AOC2022Day9.txt')
lines = f.read().strip().split('\n')
info = [line.split(' ') for line in lines]
visited = set()
chx = 0
chy = 0
ctx = 0
cty = 0
knots = [(0,0) for i in range(9)]
for i in info:
    direc = i[0]
    numsteps = int(i[1])
    for j in range(numsteps):
        visited.add(knots[-1])
        if direc == 'R':
            chx += 1
        elif direc == 'L':
            chx -= 1
        elif direc == 'U':
            chy += 1
        elif direc == 'D':
            chy -= 1
        knots = updateKnots(chx,chy,knots)
visited.add(knots[-1])
print(len(visited))

When that part 2 showed up i almost started sweating but it was actually pretty fine

import math
file=open("input.txt")

class Knot():
    def __init__(self, xpos, ypos):
        self.xpos = xpos
        self.ypos = ypos
        
k_c = 10
knots = []
for x in range (0,k_c):
    knots.append(Knot(0,0))

t_his = [(0,0)]
t_cnt = 1

def check(x, y):
    global t_his
    for val in t_his:
        if (x,y) == val: return True
    return False

def nextpos(x1, y1, x2, y2):
    if(abs(x1 - x2) > 1):
        x2 += int(math.copysign(1, x1 - x2))
        if y1 != y2:
            y2 += int(math.copysign(1, y1 - y2))
    if(abs(y1 - y2) > 1):
        y2 += int(math.copysign(1, y1 - y2))
        if x1 != x2:
            x2 +=  int(math.copysign(1, x1 - x2))
    return(x2, y2)
            
for line in file:
    cmds = line.rstrip().split()
    dir = (0,0)
    if cmds[0] == 'L': dir = (-1, 0)
    if cmds[0] == 'R': dir = (1, 0)
    if cmds[0] == 'U': dir = (0, 1)
    if cmds[0] == 'D': dir = (0, -1)
    
    for mag in range(0, int(cmds[1])):
        knots[0].xpos += dir[0]
        knots[0].ypos += dir[1]
        
        for knot in range(1, k_c):
            (knots[knot].xpos, knots[knot].ypos) = nextpos(knots[knot-1].xpos,knots[knot-1].ypos,knots[knot].xpos,knots[knot].ypos)
        
        if not check(knots[k_c-1].xpos, knots[k_c-1].ypos):
            t_his.append((knots[k_c-1].xpos, knots[k_c-1].ypos))
            t_cnt += 1
print(t_cnt)

Part one wasn't too bad, but scaling for part 2 . Probably easier than my inital impressions with a 20 seconds skim

i did not like this puzzle at all

Having some issues with part 1, it passes the test input but not the real one. Might not be able to finish this one.

import math

headCords = [0, 0]

tailCords = [0, 0]

tailSet = set()

tailSet.add("0 0")

R = 'R'

L = 'L'

D = 'D'

U = 'U'

def getDistance():

    return math.sqrt((headCords[0] - tailCords[0]) * (headCords[0] - tailCords[0]) + (headCords[1] - tailCords[1]) * (headCords[1] - tailCords[1]))

with open('input', 'r') as f:

    for line in f:

        dir, num = line.strip().split(' ')

        num = int(num)

        if dir is R:

            # print(R)

            headCords[0] += num

        elif dir is L:

            # print(L)

            headCords[0] -= num

        elif dir is U:

            # print(U)

            headCords[1] += num

        elif dir is D:

            # print(D)

            headCords[1] -= num

        else:

            never = 'This should never happen'

            now = 'It happened'

            assert(never is now)

        # print(getDistance())

        while getDistance() > 1.45:

            if headCords[0] is tailCords[0]:

                if headCords[1] > tailCords[1]:

                    tailCords[1] += 1

                else:

                    tailCords[1] -= 1

            elif headCords[1] is tailCords[1]:

                if headCords[0] > tailCords[0]:

                    tailCords[0] += 1

                else:

                    tailCords[0] -= 1

            else:

                if headCords[0] > tailCords[0]:

                    tailCords[0] += 1

                else:

                    tailCords[0] -= 1

                if headCords[1] > tailCords[1]:

                    tailCords[1] += 1

                else:

                    tailCords[1] -= 1

            if str(tailCords[0]) + ' ' + str(tailCords[1]) not in tailSet:

                tailSet.add(str(tailCords[0]) + ' ' + str(tailCords[1]))

# print('Final Tailset', tailSet)

print(len(tailSet))

let a=fs.readFileSync('/tmp/xpo','utf8').split('\n').filter(a=>a).map(a=>a.split(' ')).flatMap(a=>[...new Array(+a[1])].map(_=>a[0]))

for (let num of [2, 10]) {
let poses = [...new Array(num)].map(a=>[0,0])
let history = new Set()

for (let d of a) {
  let [x,y] = {R: [1,0], L:[-1,0], U: [0,1], D:[0,-1]}[d]
  poses[0][0] += x; poses[0][1] += y;
  for (let i = 0; i < poses.length-1; i++) {
    let [hx,hy]=poses[i],[tx,ty]=poses[i+1]
    let ax = Math.abs(tx-hx), ay=Math.abs(ty-hy), dx = Math.sign(tx-hx), dy = Math.sign(ty-hy)
    if (ax==2&&ay==2) { tx = hx + dx; ty = hy + dy;
    }
    else if (ax == 2) { ty = hy; tx = hx + dx }
    else if (ay == 2) { tx = hx; ty = hy + dy }
    poses[i+1] = [tx, ty]
    if (i === poses.length-2) history.add(tx + ':' + ty)
  }
}
console.error(history.size)
}

vanilla js parsing :/ also vanilla js can't treat lists as values

better late than never:

import * as fs from 'fs'

let pos = Array.from({length: 10},() => ({r:0, c:0}));
const g1: {[k: string]: number} = {'0-0': 1};
const g9: {[k: string]: number} = {'0-0': 1};

fs.readFileSync(process.argv[2], 'utf-8').split('\n').map(l => {
  const [dir, amt] = l.match(/\S+/g) || [];
  for (let i=0; i < Number(amt); i++) {
    if (dir === 'R') pos[0].c += 1;
    else if (dir === 'L') pos[0].c -= 1;
    else if (dir === 'U') pos[0].r += 1;
    else if (dir === 'D') pos[0].r -= 1;

    pos.forEach((nPos, i) => {
      if (i === 0) return;
      const pPos = pos[i-1];
      const dc = pPos.c-nPos.c;
      const dr = pPos.r-nPos.r;

      if (dc === 2) {
        nPos.c = pPos.c-1;
        if (Math.abs(dr) <= 1) nPos.r = pPos.r
      } 
      if (dc === -2) {
        nPos.c = pPos.c+1;
        if (Math.abs(dr) <= 1) nPos.r = pPos.r;
      }
      if (dr === 2) {
        nPos.r = pPos.r-1;
        if (Math.abs(dc) <= 1) nPos.c = pPos.c;
      }
      if (dr === -2) {
        nPos.r = pPos.r+1
        if (Math.abs(dc) <= 1) nPos.c = pPos.c;
      }
      if (i === 1) g1[`${nPos.r}-${nPos.c}`]=1;
      else if (i === 9) g9[`${nPos.r}-${nPos.c}`]=1;
    });
  }
})

console.log(Object.keys(g1).length, Object.keys(g9).length);

Late submission because I was watching divegrass and nearly forgot to submit today

Messy but it works. Part 2 made me have to rewrite the whole thing since I assumed the tail would always take the position of the head in the previous state.

with open('day9_input.txt', 'r') as inp:
    foo = inp.read().split('\n')

rope_pos = [[0,0], [0,0], [0,0], [0,0], [0,0], [0,0], [0,0], [0,0], [0,0], [0,0]]
history = set()

for f in foo:
    f = f.split(' ')
    for n in range(int(f[1])):
        for m in range(len(prev_pos)):
            prev_pos[m] = rope_pos[m]
        if f[0] == 'L':
            rope_pos[0] = [rope_pos[0][0]-1, rope_pos[0][1]]
        elif f[0] == 'R':
            rope_pos[0] = [rope_pos[0][0]+1, rope_pos[0][1]]
        elif f[0] == 'U':
            rope_pos[0] = [rope_pos[0][0], rope_pos[0][1]+1]
        elif f[0] == 'D':
            rope_pos[0] = [rope_pos[0][0], rope_pos[0][1]-1]
        for m in range(1, len(rope_pos)):
            if abs(rope_pos[m-1][0] - rope_pos[m][0]) > 1 or abs(rope_pos[m-1][1] - rope_pos[m][1]) > 1:
                candidate_pos = [[rope_pos[m][0]+1, rope_pos[m][1]],
                                [rope_pos[m][0]-1, rope_pos[m][1]],
                                [rope_pos[m][0], rope_pos[m][1]+1],
                                [rope_pos[m][0], rope_pos[m][1]-1],
                                [rope_pos[m][0]+1, rope_pos[m][1]+1],
                                [rope_pos[m][0]-1, rope_pos[m][1]+1],
                                [rope_pos[m][0]+1, rope_pos[m][1]-1],
                                [rope_pos[m][0]-1, rope_pos[m][1]-1]]
                min_displacement = 10
                min_candidate = []
                for c in candidate_pos:
                    if (abs(rope_pos[m-1][0] - c[0]) + abs(rope_pos[m-1][1] - c[1])) < min_displacement:
                        min_displacement = (abs(rope_pos[m-1][0] - c[0]) + abs(rope_pos[m-1][1] - c[1]))
                        min_candidate = c
                rope_pos[m] = min_candidate
        history.add(str(rope_pos[-1]))
print(len(history))