AoC Day 14 : Sands of time

Today's problem was fairly easy. I adopted a brute force approach since who cares, I am not gonna die for using ~2MiB of system memory, maybe it's slow but surely it works

real    0m0,103s
user    0m0,095s
sys     0m0,007s

little late guys:

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

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

const AIR: u8 = 0;
const ROCK: u8 = 1;
const SAND: u8 = 2;

let shiftX: u16 = 490;
let sandX: u16 = 500 - shiftX;
let depth: u16 = 13;
let width: u16 = 20;
let grid: u8[][] = [];
let maxY:u16=0, minX:u16=1000, maxX:u16=0;

function setup(input:str):void {
  const strLines: Arr<str> = input.split('\n');
  const pntLines
    = strLines.map<Arr<Pnt>>((l:str) => l.split(' -> ').map<Pnt>(
      (ln:str) => {
        const p = ln.split(',').map((p:str)=>u16.parse(p));
        return new Pnt(p[0],p[1]);
      }
    ));
  // console.log(pntLines.map(
  //   (pln:Arr<Pnt>)=>pln.toString()).join('\n')
  // );
  pntLines.forEach((pln:Arr<Pnt>) => {
    pln.forEach((p:Pnt) => {
      if (p.y > maxY) maxY=p.y;
      if (p.x < minX) minX=p.x;
      if (p.x > maxX) maxX=p.x;
    })
  });

  console.log(`${minX} ${maxX} ${maxY}`);

  depth = maxY+3;
  width = depth*2;
  shiftX = 500 - u16(Math.floor(width/2));
  sandX = 500 - shiftX;
  grid = new Array<u8>(depth).map(
    () => new Array<u8>(width).fill(AIR)
  );

  console.log(`${depth} ${width} ${shiftX} ${sandX}`)

  pntLines.forEach((pln:Arr<Pnt>) => {
    let curPnt:Pnt = pln[0];
    for (let i = 0; i < pln.length; i++) {
      const p:Pnt = pln[i];
      const dx:i16 = i16(curPnt.x) - i16(p.x);
      const dy:i16 = i16(curPnt.y) - i16(p.y);
      // console.log(`---- ${dx} ${dy}`)
      for (let x:u16 = p.x;
        dx<0 ? x>=curPnt.x : x<=curPnt.x;
        dx<0 ? x-- : x++) {
        for (let y:u16 = p.y; 
          dy<0 ? y>=curPnt.y : y<=curPnt.y;
          dy<0 ? y-- : y++) {
          grid[y][x-shiftX] = ROCK;
          // console.log(`${y} ${x-SHIFT_X}`)
        }
      }
      curPnt=p;
    }
  });

  for (let x:u16 = 0; x < width; x++) {
    grid[maxY+2][x] = ROCK;
  }
}

function print(): void {
  console.log(grid.map((row:Arr<u8>) => row.map(
    (c:u8) => c===ROCK?'#' : c===SAND?'o' : '.').join('')
  ).join('\n'));
}

function doOneSand(): boolean {
  let snd = new Pnt(sandX, 0);

  if (grid[0][500-shiftX]) {
    console.log('sand creation blocked');
    return false;
  };

  while (true) {
    if (snd.y > depth-1 || snd.x < 0 || snd.x >= width-1) {
      console.log('abyss reached');
      return false;
    }
    if (!grid[snd.y+1][snd.x]) {
      snd.y = snd.y+1;
    } else if (!grid[snd.y+1][snd.x-1]) {
      snd.y = snd.y+1;
      snd.x = snd.x-1;
    } else if (!grid[snd.y+1][snd.x+1]) {
      snd.y = snd.y+1;
      snd.x = snd.x+1;
    } else {
      break;
    }
  }

  grid[snd.y][snd.x] = SAND;
  return true;
};

export function run(input: str):void {
  setup(input);

  let numSnd: u32 = 0;
  while(doOneSand()) numSnd++;
  console.log(numSnd.toString());

  print();
};

too lazy to remove debug code

Harcoded the area and misread the instruction so my parttwo stops if the sand is one tile below the source. So naturally i just moved the source up by one.

#include <iostream>
#include <array>
#include <cassert>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

constexpr int HEIGHT = 1000;
constexpr int WIDTH = 1000;

struct Coordinate {
    int x;
    int y;

    auto operator<=>(const Coordinate& r) const = default;

    Coordinate(int x, int y) {
        this->x = x;
        this->y = y;
    }
    
    Coordinate left() {
        return { x - 1, y };
    }

    Coordinate right() {
        return { x + 1, y };
    }
};

template<size_t W, size_t H>
class Map {
private:
    Coordinate sand_source{0,0};
    void draw_horizontal(Coordinate& a, Coordinate& b) {
        int start = a.x;
        int end = b.x;
        if (start > end) std::swap(start, end);
        
        std::array<char, W>& row = map[a.y];
        std::fill(row.begin() + start, row.begin() + end + 1, '#');
    }
    void draw_vertical(Coordinate& a, Coordinate& b) {
        int start = a.y;
        int end = b.y;
        if (start > end) std::swap(start, end);

        for (; start <= end; ++start) {
            map[start][a.x] = '#';
        }
    }
    bool place_sand(Coordinate& p) {
        map[p.y][p.x] = 'o';
        return true;
    }
public:
    std::array <std::array<char, W>, H> map;

    Map() {
        map = {};
        for (std::array<char, W>& row : map) {
            std::fill(row.begin(), row.end(), '.');
        }
    }
    bool is_room(const Coordinate p) const {
        return (p.x >= 0 && p.y >= 0 && p.x < W && p.y < H) && map[p.y][p.x] == '.';
    }

    void draw_line(Coordinate a, Coordinate b) {
        assert(a.x == b.x ||a.y == b.y && "Can't draw diagonals");
        if (a.x == b.x) draw_vertical(a, b);
        else draw_horizontal(a, b);
    }

    void add_sand_source(Coordinate sand_source) {
        this->sand_source = sand_source;
        map[sand_source.y][sand_source.x] = '+';
    }

    bool drop_sand() {
        if (map[sand_source.y - 1][sand_source.x] != '.') return false;

        Coordinate location = { sand_source.x, sand_source.y - 1 };

        while (location.y >= 0) {
            if (is_room(location)) location.y -= 1;
            else if (is_room(location.left())) location.x -= 1;
            else if (is_room(location.right())) location.x += 1;
            else {
                location.y += 1;
                return place_sand(location);
            }
        }

        return false;
    }
};

template<size_t W, size_t H>
std::ostream& operator<<(std::ostream& os, const Map<W, H>& map) {
    for (auto it = map.map.rbegin(); it < map.map.rend(); ++it) {
        for (char c : *it) os << c;
        os << '\n';
    }
    return os;
}

int run(bool partTwo = false) {
    auto area = new Map<WIDTH, HEIGHT>();

    std::fstream file("input.txt");
    std::string buf;
    int min{ 0 };

    while (std::getline(file, buf)) {
        int x{ 0 };
        int y{ 0 };
        
        std::string d_buf = "";
        
        std::vector<Coordinate> coord;

        for (char c : buf) {
            if (c == ',') {
                x = std::stoi(d_buf);
                d_buf = "";
            }
            else if (c == '-') {
                y = std::stoi(d_buf);
                min = std::max(y, min);
                d_buf = "";
                coord.push_back({ x, HEIGHT - y - 2});
            }
            else if (std::isdigit(c)) {
                d_buf += c;
            }
        }
        y = std::stoi(d_buf);
        min = std::max(y, min);
        d_buf = "";
        coord.push_back({ x, HEIGHT - y - 2 });

        for (size_t i{ 1 }; i < coord.size(); ++i) {
            area->draw_line(coord[i - 1], coord[i]);
        }
    }
    if (partTwo) area->draw_line({ 0,HEIGHT - min - 4 }, { WIDTH - 1, HEIGHT - min - 4 });
    area->add_sand_source({ 500, HEIGHT - 1 });

    int total{ 0 };
    while (area->drop_sand()) {
        total++;
    }

    return total;
}

int main() {
    std::cout << "Part One: " << run() << '\n';
    std::cout << "Part Two: " << run(true);
}

I probably overdid it since I assume there's a way of simulating it without recreating the entire temple structure in matrix format, but doing it that way seemed more fun.

foo = []
path_list = []
min_x, max_x, max_y = 0, 1000, 0

with open('day14_input.txt', 'r') as inp:
    foo = inp.read().split('\n')
for f in foo:
    f = f.split(' -> ')
    path = []
    for g in f:
        x, y = int(g.split(',')[0]), int(g.split(',')[1])
        if y >= max_y:
            max_y = y+1
        path.append([x, y])
    path_list.append(path)

grid = [['.' for x in range(max_x-min_x+1)] for y in range(max_y+1)]
grid.append(['#' for x in range(max_x-min_x+1)])

for path in path_list:
    for n in range(len(path)-1):
        if path[n][1] == path[n+1][1]:
            for x in range(min(path[n][0], path[n+1][0]), max(path[n][0], path[n+1][0])+1):
                grid[path[n][1]][x-min_x] = '#'
        elif path[n][0] == path[n+1][0]:
            for y in range(min(path[n][1], path[n+1][1]), max(path[n][1], path[n+1][1])+1):
                grid[y][path[n][0]-min_x] = '#'

def add_sand(x_pos):
    y_pos = 0
    if grid[y_pos][x_pos] != '.':
        return False
    while True:
        if grid[y_pos+1][x_pos] == '.':
            y_pos += 1
        elif grid[y_pos+1][x_pos-1] == '.':
            x_pos -= 1
            y_pos += 1
        elif grid[y_pos+1][x_pos+1] == '.':
            x_pos += 1
            y_pos += 1
        else:
            grid[y_pos][x_pos] = 'o'
            return True

count = 0
while add_sand(500):
    count += 1
print(count)

brute force solution

finally a problem where i don't have to learn some bullshit al-ghul-rhythms

Shit I got work today, gonna be lateeeeee

ogey that's moderately washed

my parser is horrible but works fine

40-50ms for the whole thing

>tfw you get the recursive sand-placing logic right first try but fricked up the wall loading

My code literally takes only 0.001ms

IM DELETING YOU, BROTHER!

█]]]]]]]]]]]]]]]]]] 10% complete.....

████]]]]]]]]]]]]] 35% complete.....

████████]]]]]]] 60% complete.....

████████████] 99% complete.....

ERROR! Brothers of Islam are irreplaceable I could never delete you Brother!

Send this to ten other Mujahideen who would give their lives for ﷲAllahﷲ Or never get called Brother again

If you get

0 Back: Juhanam for you

3 back: you're off the martyr list

5 back: you have pleased Allah greatly

10+ back: JANAHﷲ!ﷲ