For this one, I started by treated the elevation as a graph. A location was said to be connected to another location in the graph if the other location could be reached from the current location. Then, I would start at the starting location and follow the graph until I reached the end. Along the way, I would keep track of the distance from the start - this doubled as a way to prevent me from having to deal with loops.

I don't really know much about traditional pathfinding algorithims but mine worked fine, so 💅. IDK if "wavefront" is what people in the feild call what I did, but it makes sense to me to imagine a wave crashing against the rocks...

import numpy as np
lines = []
with open("12.input", "r") as f:
    lines = f.readlines()

START_INDICATOR = -1
END_INDICATOR = 900

landscape = np.array([['abcdefghijklmnopqrstuvwxyz'.index(letter) if letter not in ['S', 'E'] else (START_INDICATOR if letter == 'S' else END_INDICATOR) for letter in line.strip()] for line in lines])

class LocationNode:
    def __init__(self, coordinates: tuple[int, int], connecting_locations: list[tuple[int, int]]) -> None:
        self.coordinates = coordinates
        self.connecting_locations = connecting_locations

INDICATOR_TO_VALUE = {START_INDICATOR : 0, END_INDICATOR: 25} | {i:i for i in range(26)}

locations  = np.empty(shape=landscape.shape, dtype=LocationNode)
for x in range(landscape.shape[0]):
    for y in range(landscape.shape[1]):
        directions = []
        if (x != 0):                    directions.append((INDICATOR_TO_VALUE[landscape[x-1,y]], (x-1, y)))
        if (x != landscape.shape[0]-1): directions.append((INDICATOR_TO_VALUE[landscape[x+1,y]], (x+1, y)))
        if (y != 0):                    directions.append((INDICATOR_TO_VALUE[landscape[x,y-1]], (x, y-1)))
        if (y != landscape.shape[1]-1): directions.append((INDICATOR_TO_VALUE[landscape[x,y+1]], (x, y+1)))
        locations[x, y] = LocationNode((x, y), [a[1] for a in directions if a[0]-INDICATOR_TO_VALUE[landscape[x,y]]<=1])

starting_location_array = np.where(landscape == START_INDICATOR)
starting_location = (starting_location_array[0][0], starting_location_array[1][0])
ending_location_array = np.where(landscape == END_INDICATOR)
ending_location = (ending_location_array[0][0], ending_location_array[1][0])

def get_distances(start: tuple[int,int]):
    distances = np.full(shape=landscape.shape, fill_value=-1, dtype=int)
    wavefront = [start]
    distance = 0
    while len(wavefront) != 0:
        new_wavefront = []
        for location in wavefront:
            distances[location] = distance
            new_wavefront = new_wavefront + [a for a in locations[location].connecting_locations if distances[a] == -1]
        distance+=1
        wavefront = set(new_wavefront)
    
    return distances

print(f"PART 1: {get_distances(starting_location)[ending_location]}")
print("Finding bests...")
a_locations = np.where(landscape == 0)

distances = []
for i in range(len(a_locations[0])+1):
    if i != len(a_locations[0]):
        x = a_locations[0][i]
        y = a_locations[1][i]
    else:
        x = starting_location[0]
        y = starting_location[1]
    location_node : LocationNode = locations[x,y]
    result = get_distances((x,y))[ending_location]
    if result != -1:
        distances.append(result)
distances.sort()
print(F'PART 2: {distances[0]}')

>People are importing a library to do simple path-finding.

: Hello, cringe department? I'd like to make a report.

I had everything prepared, EVERYTHING, and still failed miserably because of bugs.

    g = networkx.DiGraph()

    def translate(c):
        if c == 'S': return ord('a')
        if c == 'E': return ord('z')
        return ord(c)

    def get(p):
        i, j = p
        if 0 <= i < len(data):
            if 0 <= j < len(data[i]):
                return translate(data[i][j])
        return -5

    start, goal = [], None

    for i, s in enumerate(data):
        for j, c in enumerate(s):
            p = (i, j)
            if c == 'S' or (c == 'a' and second):
                start.append(p)
            elif c == 'E':
                assert not goal
                goal = p

            for dir in directions4:
                p2 = addv2(p, dir)
                if get(p2) - get(p) <= 1:
                    g.add_edge(p, p2)

    found, visited = bfs_full(start, lambda x: x == goal, lambda x: g.neighbors(x))
    assert found
    p = bfs_extract_path(goal, visited)
    return len(p) - 1

>be me

>C++chad

>see routing problem A→B

>decide to implementmaxx A*

>???

>spend 1 hour to find the proper C++® STL™ way to implement a min heap

>SEGFAULTmaxxing

>spend 1 hour GDBmaxxing

>mixed up two C++® iterators™, calling close.erase(in_open_it) in place of close.erase(in_close_it)

>itworks.mp4

>PART B

>???

>FIND ALL PATHS FROM THE END TO ALL POINTS AT ELEVATION ZERO

>I SHOULD HAVE IMPLEMENTED DIJKSTRA

@everyone snakes @drama_enthusiast discuss

spent first 15 or so mins looking up how to use a graph library

then i spent forever trying to debug a problem where it told me the positions i was giving to shortest_path were not in my graph. this is because i accidentally gave it the matrix instead, but it didnt even tell me i wasn't giving it a graph no type checking is cancer

after that i spent a while getting destroyed by my edge construction being if-elif instead of pure if like it's supposed to be

Amogus?

my feelings got hurt when i got filtoored by math yesterday so im going to drink a bunch tonight and look at this tomorrow

Importing a pathfinding algorithm felt like cheating but my DFS never returned

butt: moderately washed

matlab ()

idk what a* is or whatever so I just dijkstra'd the first part, slapped a for loop for the second part, and optimized it by making only one dijkstra from the end to the start, which finds the start and the optimal starting point.

The code is still a bit messy and I have absolutely no idea why it only works when I take out the last element of my priority queue instead of the first, regardless of the sorting order (that was true for the forward dijkstra too so it's not that)

spent some time thinking of proper algorithm that can handle multiple sources or targets, but then gave up. You could most likely use djikstra to start at the end point, calculate the distance to every node and the pick the starting nodes with the lowest distance. Instead of just doing a BFS from every starting node to the End Node. But why would i implement that one manually and people that use library algorithm are .

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <array>

typedef std::pair<int32_t, int32_t> coordinate;

constexpr char max_char = 'z';

int32_t run(std::vector<std::vector<char>>& map, std::vector<coordinate>& start_points) {
	std::array<int32_t, 4> dirx{ 0,0,1,-1 };
	std::array<int32_t, 4> diry{ 1,-1,0, 0 };

	size_t RR = map.size();
	size_t CC = map[0].size();
	int32_t shortest_distance = INT32_MAX;

	for (auto start : start_points) {
		std::vector<std::vector<int32_t>> dist(RR, std::vector<int32_t>(CC));
		for (auto& row : dist) std::fill(row.begin(), row.end(), -1);

		std::queue<coordinate> q;
		q.push(start);
		dist[start.first][start.second] = 0;
		while (!q.empty()) {
			auto p = q.front();
			q.pop();
			char current = map[p.first][p.second];
			if (current == 'S') current = 'a';
			for (size_t i{ 0 }; i < 4; i++) {
				int y = p.first + diry[i];
				int x = p.second + dirx[i];
				if (y >= 0 && x >= 0 && y < RR && x < CC && dist[y][x] == -1 &&
					(
						(map[y][x] != 'E' && map[y][x] - current <= 1) ||
						(map[y][x] == 'E' && current == max_char)
						)) {
					dist[y][x] = 1 + dist[p.first][p.second];
					if (map[y][x] == 'E') shortest_distance = std::min(dist[y][x], shortest_distance);
					q.push(std::make_pair(y, x));
				}
			}
		}
	}

	return shortest_distance;

}

int main() {
	std::ifstream file("input.txt");
	std::string buf;
	std::vector<std::vector<char>> map;
	std::vector<coordinate> partOne_starts;
	std::vector<coordinate> partTwo_starts;

	size_t c_y = 0;
	while (std::getline(file, buf)) {
		map.push_back({});
		size_t c_x = 0;
		for (char c : buf) {
			if (c == 'S') partOne_starts.push_back(std::make_pair(c_y, c_x));
			if (c == 'S' || c == 'a') partTwo_starts.push_back(std::make_pair(c_y, c_x));
			map.back().push_back(c);
			++c_x;
		}
		++c_y;
	}
	std::cout << "Part One: " << run(map, partOne_starts) << '\n';
	std::cout << "Part Two: " << run(map, partTwo_starts) << '\n';
	return -1;
}

This is some breadth first search ffs, felt jewish chad school all over again, also how the frick are you strags so fast?!

lmao, they put a bunch of effort into generating the final swirl and gave up with the rest it's a mountain you fricking idiot

solution with heatmap colours, I was bored today

Babby's first shortest path graph algorithm. I got incredibly lucky with part 2, I only had to modify one line lol.

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

maze = [[0 for x in range(len(foo[0]))] for y in range(len(foo))] 
dist = [[6969 for x in range(len(foo[0]))] for y in range(len(foo))] 

dest_pos = []
for f in range(len(foo)):
    for g in range(len(foo[0])):
        if foo[f][g] == 'S': # or foo[f][g] == 'a': (for Part 2)
            maze[f][g] = 1
            dist[f][g] = 0
        elif foo[f][g] == 'E':
            dest_pos = [g, f]
            maze[f][g] = 26
        else:
            maze[f][g] = ord(foo[f][g]) - 96

def get_valid_adj(x, y):
    adj = []
    if x > 0 and maze[y][x-1]-1 <= maze[y][x]:
        adj.append([x-1, y])
    if y > 0 and maze[y-1][x]-1 <= maze[y][x]:
        adj.append([x, y-1])
    if x < len(foo[0])-1 and maze[y][x+1]-1 <= maze[y][x]:
        adj.append([x+1, y])
    if y < len(foo)-1 and maze[y+1][x]-1 <= maze[y][x]:
        adj.append([x, y+1])
    return adj

current_steps = 0
while True:
    for f in range(len(foo)):
        for g in range(len(foo[0])):
            if dist[f][g] == current_steps:
                for a in get_valid_adj(g, f):
                    if a == dest_pos:
                        print(current_steps+1)
                        quit()
                    elif dist[a[1]][a[0]] == 6969:
                        dist[a[1]][a[0]] = current_steps+1
    current_steps += 1

Implemented my own totally faggy version of a-star. Edit: Included both variants in my result

with open('input12.txt') as file:
    lines = [[ord(c)-ord('a') for c in list(line.strip())] for line in file] # -14 == S # -28 == E
    
class Node():
    def __init__(self,x ,y, steps, cost) -> None:
        self.x = x
        self.y = y
        self.height = lines[y][x]
        self.steps = steps
        if self.height == -28:
            self.height = 25
        elif self.height == -14:
            self.height = 0
        self.cost = self.steps + self.height
        
def check_neighbours(node_next_x, node_next_y, node, x_axis=True, reverse=False):
    if (x_axis and 0 <= node_next_x < len(lines[node_next_y])) or (not x_axis and 0 <= node_next_y < len(lines)):
        if reverse:
            height_diff = node.height-lines[node_next_y][node_next_x]
        else:
            height_diff = lines[node_next_y][node_next_x]-node.height
        if "{}/{}/{}/{}".format(node_next_x,node_next_y,node.x,node.y) not in looked_set and height_diff<=1:
            new_node = Node(node_next_x, node_next_y, node.steps+1, node.cost)
            node_list.append(new_node)
            looked_set.add("{}/{}/{}/{}".format(node_next_x,node_next_y,node.x,node.y))
    
part_a=True # False for part b
        
node_list = []
looked_set = set()
if part_a:
    start = Node(0,20,0,0)
    goal = -28
    pre_goal_height = 25
else:
    start = Node(40,20,0,0)
    goal = 0
    pre_goal_height = 1
node_list.append(start)
index = 0
while True:
    if len(node_list) == 0:
        print("Nothing found")
        break
    node = node_list.pop()
    if index%1000 == 0:
        print("here", node.steps, len(node_list))
    if node.height == pre_goal_height:
        if goal in [lines[node.y+1][node.x],lines[node.y-1][node.x],lines[node.y][node.x+1],lines[node.y][node.x-1]]:
            print("Found! Steps:", node.steps+1)
            break
    check_neighbours(node.x+1, node.y, node, True, not part_a)
    check_neighbours(node.x-1, node.y, node, True, not part_a)
    check_neighbours(node.x, node.y+1, node, False, not part_a)
    check_neighbours(node.x, node.y-1, node, False, not part_a)
    node_list.sort(key=lambda n: n.cost, reverse=True)
    index += 1

const grd: string[][] 
  = fs.readFileSync(process.argv[2], 'utf-8').split('\n').map(l => l.split(''));
const hgt: number[][]
  = grd.map(r => r.map(ch => (ch==='S' ? 'a' : ch==='E' ? 'z' : ch).charCodeAt(0)));
const dst: number[][] 
  = grd.map(r => r.map(() => 0));

type Cell = {r: number, c: number};
let next: Cell[] = [];
let cur: Cell[] = [];
let step = 0;

// find start setup
grd.forEach((row, r) => {
  const c = row.findIndex(ch => ch==='E')
  if (c !== -1) next = [{r:r, c:c}];
})
hgt[next[0].r][next[0].c] = 'z'.charCodeAt(0);
dst[next[0].r][next[0].c] = -1;

// bfs
while (next.length) {
  step++; cur = next; next = [];
  for (let cell of cur) {
    [ [cell.r-1,cell.c],
      [cell.r+1,cell.c],
      [cell.r,cell.c-1],
      [cell.r,cell.c+1]
    ].forEach(([r,c]) => {
      // out of bounds
      if (r < 0 || grd.length-1 < r
        || c < 0 || grd[r].length-1 < c) return;
      // already visited || too big diff in height
      if (dst[r][c] 
        || hgt[cell.r][cell.c] - hgt[r][c] > 1 ) return;
      // push to next
      dst[r][c] = step;
      next.push({r,c});
    })
  }
};

grd.forEach((row, r) => {
  const c = row.findIndex(ch => ch==='S')
  if (c !== -1) console.log(dst[r][c]);
})
console.log(
  dst.flatMap((row, r) => row.filter((d, c) => d && grd[r][c] === 'a')).sort((a,b) => a-b)[0]
)

No one in this hellbent day and age is going to Heaven anyways. Do whatever you want before eternal darnation where God will punish everyone for all of eternity. No amount of repentance can forgive it because the Quran makes clear people who pray just to avoid Heck are seen as disingenuous and the prayer is null. Martyrs get Heaven at least. The only chance my soul has is a holy war breaking out which is a long cry from realistic. But they say Allah is the most merciful so maybe trying as hard as possible to be good is good enough. Else he would have killed us all already. Or maybe I am making excuses because I am scared for judgement day

[[[ Packets ]]]] edit this is day 13, wtf where is day 13 thread