3.md

Day 3: Crossed Wires

The problem statement can be found here. Since C++ is a bit more verbose than the previous languages, I left out some parts of the code. Check the git repo for the full source.

Part 1

Two wires are connected to a central port and extend outward on a grid. The wires twist and turn, but the two wires occasionally cross paths. You need to find the intersection point closest to the central port.

On first sight, you may be tempted to create a 2d array to represent the grid. However, after looking at the input it becomes clear that the inputs are too large. Instead I opted to save all point in a map, along with the number of steps it took to get there (see part 2).

Data structures

• overlaps: a list of arrays with information about the overlap ([x, y, steps1, steps2],)
• grid: a map where the key is the coordinate and the values contain the number of steps and the symbol of the wire.
• wire: a list of wire directions ("L12", "U4", ...)

The below code populates the grid and records overlaps as they occur.

int lay_wire(map<string, tuple<char, int>>* grid, list<string>* wire, char symbol, list<array<int, 4>>* overlaps) {
	int ix = 0;
	int iy = 0;
	int wire_step = 0;
	// For direction code in wire
	for (string w : *wire) {
		int dx = 0;
		int dy = 0;
		switch(w.front()) {
			case 'L': dx = -1;
				  break;
			case 'R': dx = 1;
				  break;
			case 'U': dy = -1;
				  break;
			case 'D': dy = 1;
				  break;
		}
		int amount = stoi(w.substr(1));
		for (int i = 0; i < amount; i++) {
			ix = ix + dx;
			iy = iy + dy;
			wire_step++;
			// No intersection at origin
			if (ix == 0 and iy == 0) continue;
			// Create keys as "x|y"
			stringstream stream;
			stream << ix << "|" << iy;
			string key = stream.str();
			auto elem = grid->find(key);
			// If no wire here yet...
			if (elem == grid->end()) {
				tuple<char, int> value = {symbol, wire_step};
				grid->insert({key, value});
			// If there is a wire, check if its the other one.
			} else {
				char cur_symbol = get<0>(elem->second);
				int cur_steps = get<1>(elem->second);
				if (symbol == cur_symbol) continue;
				array<int, 4> overlap = {ix, iy, wire_step, cur_steps};
				overlaps->push_front(overlap);
			}
		}
	}
	return 0;
}

Now all that is left to do is to create a function to calculate the distance to the closest overlap.

int print_closest_overlap(list<array<int, 4>>* overlaps) {
	int d = 9999999;
	for (const auto& overlap : *overlaps) {
		int this_d = abs(overlap[0]) + abs(overlap[1]);
		if (this_d < d) {
			d = this_d;
		}
	}
	cout << "closest overlap: ";
	cout << d;
	cout << "\n";
	return 0;
}

Part 2

calculate the number of steps each wire takes to reach each intersection; choose the intersection where the sum of both wires' steps is lowest.

The number of steps for both wires are also recorded in overlaps, so this is fairly straight forward.

int print_earliest_overlap(list<array<int, 4>>* overlaps) {
	int d = 9999999;
	for (const auto& overlap : *overlaps) {
		int this_d = overlap[2] +overlap[3];
		if (this_d < d) {
			d = this_d;
		}
	}
	cout << "earliest overlap: ";
	cout << d;
	cout << "\n";
	return 0;
}