AoC 2023 Day 17 cc

day17.cc

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <map>

using namespace std;

vector<string> contents(const string filename) {
	ifstream f;
	string line;
	vector<string> out;
	f.open(filename);
	if (f.is_open()) {
		while (getline(f, line)) {
			out.push_back(line);
		}
	}
	f.close();
	return out;
}

class Vector2 {
	public:
	int y;
	int x;
	
	
	Vector2(int y, int x) : y(y), x(x) {
	}
	
	Vector2 operator+(const Vector2 & other) const {
		return Vector2(x + other.x, y + other.y);
	}
	
	Vector2 * operator+=(const Vector2 & other) {
		x += other.x;
		y += other.y;
		return this;
	}
	
	bool operator<(const Vector2 & other) const {
		if (x < other.x) return true;
		if (x > other.x) return false;
		if (y < other.y) return true;
		return false;
	}
};


Vector2 U = {-1,0}, D = {1,0}, R = {0,1}, L = {0,-1};

vector<Vector2> horiz_dirs = {L, R};
vector<Vector2> vert_dirs = {U, D};


int problem_dijk(vector<string> & lines, int part) {
	int height = lines.size();
	int width = lines[0].size();

	vector<vector<int>> grid;

	// load problem heat grid
	for (int y = 0; y < height; y++) {
		grid.push_back(vector<int>());
		for (int x = 0; x < width; x++) {
			auto ch = lines[y][x];
			int dig = ch - '0';
			grid[y].push_back(dig);
		}
	}
	
	int min_moves;
	int max_moves;

	if (part == 1) {
		min_moves = 1;
		max_moves = 3;
	} else {
		min_moves = 4;
		max_moves = 10;
	}
	
	typedef tuple<int, Vector2, bool> pq_entry_t;
	
	priority_queue<pq_entry_t, vector<pq_entry_t>, greater<pq_entry_t>> pq;
	
	
	//map<pair<Vector2, bool>, int> shortest_paths;
	
	int maxval = (height + width) * 9; // max digit
	
	vector<vector<vector<int>>> shortest_paths;
	
	for (int horiz = 0; horiz < 2; horiz++) {
		shortest_paths.push_back(vector<vector<int>>());
		for (int y = 0; y < height; y++) {
			shortest_paths[horiz].push_back(vector<int>());
			for (int x = 0; x < width; x++) {
				shortest_paths[horiz][y].push_back(maxval);
			}
		}
	}
	
	//shortest_paths.insert({{Vector2(0,0), true}, 0});
	shortest_paths[true][0][0] = 0;
	pq.push({0, Vector2(0,0), true});
	//shortest_paths.insert({{Vector2(0,0), false}, 0});
	shortest_paths[false][0][0] = 0;
	pq.push({0, Vector2(0,0), false});	
	
	while (!pq.empty()) {
		auto pq_entry = pq.top();
		pq.pop();
		
		int weight = get<0>(pq_entry);
		Vector2 pos = get<1>(pq_entry);
		bool cur_horiz = get<2>(pq_entry);
		
		vector<Vector2> & cur_directions = cur_horiz? horiz_dirs : vert_dirs;
		
		for (Vector2 cur_dir : cur_directions) {
			int new_weight = weight;
			Vector2 cur_step_pos = pos;
			for (int num_moves = 1; num_moves <= max_moves; num_moves++) {
				cur_step_pos += cur_dir;
				
				// if we went out of bounds just stop processing this direction
				if (cur_step_pos.x < 0) break;				
				if (cur_step_pos.y < 0) break;
				if (cur_step_pos.x >= width) break;
				if (cur_step_pos.y >= height) break;
				
				new_weight += grid[cur_step_pos.y][cur_step_pos.x];
				
				if (num_moves < min_moves) continue;
				
				bool other_horiz = !cur_horiz;
				/*
				pair<Vector2, bool> key = {cur_step_pos, other_horiz};
				auto shortest_paths_iterator = shortest_paths.find(key);
				if ((shortest_paths_iterator == shortest_paths.end()) || shortest_paths_iterator->second > new_weight) {
					if (shortest_paths_iterator == shortest_paths.end()) {
						shortest_paths.insert({key, new_weight});
					} else {
						shortest_paths_iterator->second = new_weight;
					}
					pq.push({new_weight, cur_step_pos, other_horiz});
				}
				*/
				if (shortest_paths[other_horiz][cur_step_pos.y][cur_step_pos.x] > new_weight) {
					shortest_paths[other_horiz][cur_step_pos.y][cur_step_pos.x] = new_weight;
					pq.push({new_weight, cur_step_pos, other_horiz});
				}
			}
		}
		
	}
	
	/*
	int out = -1;
	for (bool horiz: {true, false}) {
		auto it = shortest_paths.find({Vector2(height-1,width-1),horiz});
		if (it != shortest_paths.end()) {
			int val = it->second;
			if (out == -1 || val < out) {
				out = val;
			}
		}
	}
	
	return out;
	*/
	return min(shortest_paths[0][height-1][width-1], shortest_paths[1][height-1][width-1]);
}


int problem(vector<string> & lines, int part) {
	int height = lines.size();
	int width = lines[0].size();
	
	vector<vector<int>> grid;
	vector<vector<vector<int>>> shortest_paths;
	vector<vector<vector<bool>>> updates;
	
	for (int horiz = 0; horiz < 2; horiz++) {
		shortest_paths.push_back(vector<vector<int>>());
		updates.push_back(vector<vector<bool>>());
	}
	
	int maxval = (height + width) * 9; // max digit
	
	for (int y = 0; y < height; y++) {
		grid.push_back(vector<int>());

		for (int horiz = 0; horiz < 2; horiz++) {
			shortest_paths[horiz].push_back(vector<int>());
			updates[horiz].push_back(vector<bool>());
		}

		for (int x = 0; x < width; x++) {
			auto ch = lines[y][x];
			int dig = ch - '0';
			grid[y].push_back(dig);
		
			for (int horiz = 0; horiz < 2; horiz++) {		
				updates[horiz][y].push_back(false);
				shortest_paths[horiz][y].push_back(maxval);
			}
		}
	}
	
	for (int horiz = 0; horiz < 2; horiz++) {
		shortest_paths[horiz][0][0] = 0;
		updates[horiz][0][0] = 1;
	}
	
	int min_moves;
	int max_moves;

	if (part == 1) {
		min_moves = 1;
		max_moves = 3;
	} else {
		min_moves = 4;
		max_moves = 10;
	}

	
	bool processing_updates = true;
	while (processing_updates) {
		processing_updates = false;
		
		for (int horiz = 0; horiz < 2; horiz++) {
			for (int y = 0; y < height; y++) {
				for (int x = 0; x < width; x++) {
					if (!updates[horiz][y][x]) continue;
					updates[horiz][y][x] = false;
					
					processing_updates = true;
					
					int cur_heat = shortest_paths[horiz][y][x];
					
					vector<Vector2> & next_dirs = horiz? horiz_dirs : vert_dirs;
					for (Vector2 next_dir: next_dirs) {
						int move_heat = cur_heat;
						Vector2 update_pos(y, x);
						
						for (int num_moved = 1; num_moved <= max_moves; num_moved ++) {
							update_pos += next_dir;
							if (update_pos.y < 0) break;
							if (update_pos.y >= height) break;
							if (update_pos.x < 0) break;
							if (update_pos.x >= width) break;
							move_heat += grid[update_pos.y][update_pos.x];
							
							if (num_moved >= min_moves) {
								int other = horiz? 0 : 1;
								int prev_heat = shortest_paths[other][update_pos.y][update_pos.x];
								if (move_heat < prev_heat) {
									// update
									shortest_paths[other][update_pos.y][update_pos.x] = move_heat;
									updates[other][update_pos.y][update_pos.x] = true;
								}
							}
						}
						
					}
				}
			}
		}
	}
	
	return min(shortest_paths[0][height-1][width-1], shortest_paths[1][height-1][width-1]);

}


int main() {

	vector<string> lines = contents("input17.txt");

	//cout << problem_dijk(lines, 1) << endl;
	//cout << problem(lines, 2) << endl;
	cout << problem_dijk(lines, 2) << endl;

	return 0;
}