325 lines
7.4 KiB
C++
325 lines
7.4 KiB
C++
#include <algorithm>
|
|
#include <iostream>
|
|
#include <map>
|
|
#include <set>
|
|
#include <tuple>
|
|
#include <utility>
|
|
#include <vector>
|
|
#include <sstream>
|
|
|
|
#include <aocpp/Startup.hpp>
|
|
#include <intcode/intcode.hpp>
|
|
|
|
using namespace intcode;
|
|
|
|
namespace {
|
|
|
|
auto OffByOne (
|
|
std::string const& x,
|
|
std::string const& y
|
|
) -> std::size_t
|
|
{
|
|
auto const [it_x, it_y] = std::mismatch(x.begin(), x.end(), y.begin());
|
|
return
|
|
(it_x != x.end() &&
|
|
*it_x == '.' &&
|
|
*it_y == '#' &&
|
|
std::equal(it_x+1, x.end(), it_y+1))
|
|
? std::distance(x.begin(), it_x)
|
|
: std::string::npos;
|
|
}
|
|
|
|
auto CountOnes(std::string const& key) -> std::size_t {
|
|
return std::count_if(key.begin(), key.end(), [](auto c) { return c == '#'; });
|
|
}
|
|
|
|
auto QuineMcCluskey(
|
|
bool const polarity,
|
|
std::size_t const vars,
|
|
std::map<std::string, bool> const& behavior
|
|
) {
|
|
std::set<std::string> done;
|
|
std::vector<std::set<std::string>> current;
|
|
current.resize(vars+1);
|
|
bool working = true;
|
|
|
|
for (std::size_t i = 0; i < (std::size_t(1)<<vars); i++) {
|
|
std::string key;
|
|
for (std::size_t j = 0; j < vars; j++) {
|
|
key += (i & (1ULL<<j)) ? '#' : '.';
|
|
}
|
|
auto it = behavior.find(key);
|
|
if (it == behavior.end()) {
|
|
current[CountOnes(key)].insert(key);
|
|
} else if (polarity == it->second) {
|
|
done.insert(key);
|
|
current[CountOnes(key)].insert(key);
|
|
}
|
|
}
|
|
|
|
while (working) {
|
|
working = false;
|
|
std::vector<std::set<std::string>> nextbatch;
|
|
nextbatch.resize(current.size()-1);
|
|
|
|
for (std::size_t ones = 0; ones+1 < current.size(); ones++) {
|
|
if (!current[ones+1].empty()) {
|
|
for (auto const& t1 : current[ones]) {
|
|
for (auto const& t2 : current[ones+1]) {
|
|
if (auto ix = OffByOne(t1, t2); ix != std::string::npos) {
|
|
auto d1 = done.erase(t1);
|
|
auto d2 = done.erase(t2);
|
|
|
|
auto key = t1;
|
|
key[ix] = '-';
|
|
nextbatch[ones].insert(key);
|
|
working = true;
|
|
|
|
if (d1 || d2) done.insert(key);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
current = nextbatch;
|
|
}
|
|
|
|
return done;
|
|
}
|
|
|
|
auto RunStream(
|
|
Machine m,
|
|
std::istream & in,
|
|
std::ostream & out
|
|
) -> ValueType
|
|
{
|
|
ValueType answer {};
|
|
Run(m,
|
|
[&]() -> ValueType { return in.get(); },
|
|
[&](ValueType o) {
|
|
if (o < 256) out << char(o); else answer = o; });
|
|
return answer;
|
|
}
|
|
|
|
auto GetCounterExample(std::istream & in) -> std::string {
|
|
std::string line1, line2, line3, line4;
|
|
|
|
// Skip lines until the counter example starts
|
|
while(std::getline(in, line1)) {
|
|
if (line1 == "Didn't make it across:") {
|
|
break;
|
|
}
|
|
}
|
|
|
|
std::string result;
|
|
|
|
while (std::getline(in, line1)) { // whitespace
|
|
std::getline(in, line1); // air
|
|
std::getline(in, line2); // air
|
|
std::getline(in, line3); // air
|
|
std::getline(in, line4); // platform
|
|
|
|
std::size_t at_index;
|
|
if ((at_index = line1.find('@')) != std::string::npos) {
|
|
result += line4[at_index];
|
|
} else if ((at_index = line2.find('@')) != std::string::npos) {
|
|
result += line4[at_index];
|
|
} else if ((at_index = line3.find('@')) != std::string::npos) {
|
|
result += line4[at_index];
|
|
if (line4[at_index] == '.') {
|
|
result += line4.substr(at_index+1);
|
|
return result;
|
|
}
|
|
} else {
|
|
at_index = line4.find('@');
|
|
result += '.';
|
|
result += line4.substr(at_index+1);
|
|
return result;
|
|
}
|
|
}
|
|
|
|
return "";
|
|
}
|
|
|
|
auto LearnExample(
|
|
std::vector<std::size_t> const& window,
|
|
std::map<std::string, bool> & behavior,
|
|
std::string::const_iterator begin,
|
|
std::string::const_iterator const end,
|
|
auto on_success
|
|
) -> void
|
|
{
|
|
top:
|
|
// Standing on a hole; game over
|
|
if (*begin == '.') return;
|
|
|
|
// Reached the end of the platform, report success
|
|
if (std::all_of(begin, end, [](auto c) { return c == '#'; })) {
|
|
on_success(); return;
|
|
}
|
|
|
|
// Compute the sensor values
|
|
std::string key;
|
|
std::size_t tail = std::distance(begin, end);
|
|
for (auto i : window) {
|
|
key += i < tail ? begin[i] : '#';
|
|
}
|
|
|
|
auto [it, added] = behavior.try_emplace(std::move(key), false);
|
|
if (!added) {
|
|
// We've seen this sensor value before, do the same thing as last time
|
|
begin += it->second ? 4 : 1;
|
|
goto top;
|
|
} else {
|
|
LearnExample(window, behavior, begin + 1, end, on_success);
|
|
it->second = true;
|
|
LearnExample(window, behavior, begin + 4, end, on_success);
|
|
behavior.erase(it);
|
|
}
|
|
}
|
|
|
|
auto LearnAll(
|
|
std::vector<std::size_t> const& window,
|
|
std::map<std::string, bool> & behavior,
|
|
std::vector<std::string>::const_iterator const example,
|
|
std::vector<std::string>::const_iterator const end,
|
|
auto k
|
|
) -> void
|
|
{
|
|
if (example == end) {
|
|
k();
|
|
} else {
|
|
LearnExample(
|
|
window, behavior,
|
|
example->begin(),
|
|
example->end(),
|
|
[&]() {
|
|
LearnAll(window, behavior, std::next(example), end, k);
|
|
});
|
|
}
|
|
|
|
}
|
|
|
|
auto EnhanceSensors(
|
|
std::size_t const n,
|
|
std::vector<std::vector<std::size_t>> const& previous
|
|
) {
|
|
std::vector<std::vector<std::size_t>> result;
|
|
|
|
for (auto const& v : previous) {
|
|
auto const start = v.empty() ? 1 : v.back() + 1;
|
|
for (std::size_t i = start; i <= n; i++) {
|
|
result.push_back(v);
|
|
result.back().push_back(i);
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
auto Compute(
|
|
Machine machine,
|
|
std::size_t const maxsensors,
|
|
std::vector<std::string> const& examples,
|
|
char const* const input
|
|
) {
|
|
|
|
std::istringstream in {input};
|
|
std::stringstream out;
|
|
auto const output = RunStream(machine, in, out);
|
|
|
|
if (output > 0) {
|
|
out << "Hull damage: " << output << std::endl;
|
|
} else {
|
|
out << "Learned " << GetCounterExample(out) << std::endl;
|
|
}
|
|
|
|
std::vector<std::vector<std::size_t>> sensors {{}};
|
|
bool searching = true;
|
|
while(searching && !sensors.empty()) {
|
|
for (auto const& sensor : sensors) {
|
|
std::map<std::string, bool> cases;
|
|
LearnAll(sensor, cases, examples.begin(), examples.end(), [&]() {
|
|
searching = false;
|
|
for (bool const p : {true,false}) {
|
|
auto const terms = QuineMcCluskey(p, sensor.size(), cases);
|
|
out << (p ? "\nTRUE\n" : "\nFALSE\n");
|
|
for (auto const s : sensor) {
|
|
out << char('A'+s-1);
|
|
}
|
|
out << std::endl;
|
|
for (auto const& term : terms) {
|
|
out << term << std::endl;
|
|
}
|
|
}
|
|
});
|
|
}
|
|
if (searching) {
|
|
sensors = EnhanceSensors(maxsensors, sensors);
|
|
}
|
|
}
|
|
}
|
|
|
|
} // namespace
|
|
|
|
auto Main(std::istream & in, std::ostream & out) -> void
|
|
{
|
|
Machine machine {ParseStream(in)};
|
|
|
|
Compute(machine, 4,
|
|
{ "#####.###########",
|
|
"#####.##.########",
|
|
"#####.#.#########",
|
|
"#####.#..########"
|
|
"#####..#.########",
|
|
"#####...#########",
|
|
},
|
|
"OR A J\n"
|
|
"AND C J\n"
|
|
"NOT J J\n"
|
|
"AND D J\n"
|
|
"WALK\n"
|
|
);
|
|
// FALSE
|
|
// BDE
|
|
// ##-
|
|
// --.
|
|
// n(AC or nD)
|
|
// n(AC) and D
|
|
|
|
Compute(std::move(machine), 9,
|
|
{ "#####.############",
|
|
"#####.###...#.####",
|
|
"#####.##.#########",
|
|
"#####.##.##...####",
|
|
"#####.#.##########",
|
|
"#####.#.##..#.####",
|
|
"#####.#.##...#####",
|
|
"#####.#.#.##..####",
|
|
"#####.#..#########",
|
|
"#####..###.#..####",
|
|
"#####..##.#.######",
|
|
"#####..#.#########",
|
|
"#####..#.###.#####",
|
|
"#####...##########",
|
|
"#####...####..####",
|
|
},
|
|
"NOT H J\n"
|
|
"OR C J\n"
|
|
"AND B J\n"
|
|
"AND A J\n"
|
|
"NOT J J\n"
|
|
"AND D J\n"
|
|
"RUN\n"
|
|
);
|
|
// FALSE
|
|
// 3
|
|
// ABCDH
|
|
// ###--
|
|
// ##--.
|
|
// ---.-
|
|
//
|
|
// n(ABC or ABnH or nD)
|
|
// n(AB(C or nH) or nD)
|
|
// n(AB(C or nH)) and D
|
|
}
|