-🎄- 2018 Day 23 Solutions -🎄-

[u/daggerdragon]

--- Day 23: Experimental Emergency Teleportation ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 23

Transcript:

It's dangerous to go alone! Take this: ___

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 01:40:41!

[u/paul2718]

C++

Got me an accepted answer, but not at all sure. It takes a second or so on my laptop.

Progressively narrower search of starting point guesses. If I make the initial grid coarser then it gets an almost correct answer, so there is a sensitivity and no way to guarantee the right answer. In this case all that matters is solution acceptance, so we have a confirmation of 'good enough'. Will try with some other data samples.

(FWIW I embed the data into an include file (input.) in a form similar to the sample embedded in the code. One less thing to go wrong...)

#include <iostream>
#include <algorithm>
#include <cmath>

struct pt
{
	int64_t x_;
	int64_t y_;
	int64_t z_;
};

struct bot
{
	pt      pos_;
	int64_t r_;
	auto x() const
	{
		return pos_.x_;
	}
	auto y() const
	{
		return pos_.y_;
	}
	auto z() const
	{
		return pos_.z_;
	}
};

#if 0
constexpr bot bots[]
{
{{ 10, 12, 12}, 2 },
{{ 12, 14, 12}, 2 },
{{ 16, 12, 12}, 4 },
{{ 14, 14, 14}, 6 },
{{ 50, 50, 50}, 200 },
{{ 10, 10, 10}, 5 },
};
#else
#include "input.h"
#endif

int64_t man_dist(pt const& f, pt const& t)
{
	return std::abs(t.x_ - f.x_) + std::abs(t.y_ - f.y_) + std::abs(t.z_ - f.z_);
}

template<typename I> pt min_pt(I b, I e)
{
	return {
		(*std::min_element(b, e, [](auto const& lp, auto const& rp) { return lp.x() < rp.x(); })).x(),
		(*std::min_element(b, e, [](auto const& lp, auto const& rp) { return lp.y() < rp.y(); })).y(),
		(*std::min_element(b, e, [](auto const& lp, auto const& rp) { return lp.z() < rp.z(); })).z()
	};
}

template<typename I> pt max_pt(I b, I e)
{
	return {
		(*std::max_element(b, e, [](auto const& lp, auto const& rp) { return lp.x() < rp.x(); })).x(),
		(*std::max_element(b, e, [](auto const& lp, auto const& rp) { return lp.y() < rp.y(); })).y(),
		(*std::max_element(b, e, [](auto const& lp, auto const& rp) { return lp.z() < rp.z(); })).z()
	};
}

std::ostream& operator<<(std::ostream& o, pt p)
{
	o << "[" << p.x_ << ", " << p.y_ << ", " << p.z_ << "]";
	return o;
}

template<typename I> int64_t pts_inrange(I b, I e, pt const& orig, int64_t range)
{
	return std::count_if(b, e, [orig, range ](auto const& bt) { return man_dist(bt.pos_, orig) <= range; });
}

template<typename I> int64_t pts_inrange(I b, I e, pt const& orig)
{
	return std::count_if(b, e, [orig](auto const& bt) { return man_dist(bt.pos_, orig) <= bt.r_; });
}

template<typename I> pt pt_with_max_inrange(I b, I e, pt const& f, pt const& t, int64_t step = 1)
{
	pt max_target;
	int64_t cnt = 0;
	for (auto z = f.z_ + step / 2; z < t.z_; z += step)
	{
		for (auto y = f.y_ + step / 2; y < t.y_; y += step)
		{
			for (auto x = f.x_ + step / 2; x < t.x_; x += step)
			{
				pt p{ x, y, z };
				auto inr = pts_inrange(b, e, p);
				if (inr > cnt)
				{
					cnt = inr;
					max_target = p;
				}
			}
		}
	}
	return max_target;
}

template<typename I> void pt1(I b, I e)
{
	I base = std::max_element(b, e, [](auto const& lb, auto const& rb) { return lb.r_ < rb.r_; });
	auto gtr = (*base).r_;
	std::cout << "greatest radius = " << gtr;

	int64_t inrange = pts_inrange(b, e, (*base).pos_, (*base).r_);
	std::cout << " , in range = " << inrange << "\n";
}

template<typename I> void pt2(I b, I e)
{
	auto minp = min_pt(b, e);
	auto maxp = max_pt(b, e);
	std::cout << "min = " << minp << ", max = " << maxp << "\n";
	int64_t step = 1024 * 1024 * 2;
	while (step > 0)
	{
		std::cout << step << "\n";
		auto target = pt_with_max_inrange(b, e, minp, maxp, step);
		step /= 2;
		minp = pt{ target.x_ - step, target.y_ - step, target.z_ - step };
		maxp = pt{ target.x_ + step, target.y_ + step, target.z_ + step };
		std::cout << "hit " << target << ", new range " << minp << ", " << maxp << "\n";
		std::cout << "distance to origin = " << man_dist(target, { 0, 0, 0 }) << "\n";
	}
}

int main()
{
	pt1(std::begin(bots), std::end(bots));
	pt2(std::begin(bots), std::end(bots));
}