addie

I know - thank you, though, good to know it's not just me. Not the first puzzle that I've solved using GraphViz, either.

Some of them do depend on some unstated property of the input that can only be discerned by inspecting it - I don't feel too bad about that kind of 'cheat', as long as it goes from "the input" -> "your code" -> "the output".

Some of them - and I'm thinking another that ludicrous "line up the hailstones" one from day 24 from last year - are the kind where you parse the input so you can output it in the right format for Wolfram Alpha. Most unsatisfying as a coding puzzle.

Every "pair" of bits has the same pattern of AND and XOR, and the previous "carry bit" is passed into the same OR / (XOR + AND) combo to produce an output bit and the next "carry bit". The "whole chain" is nearly right - otherwise your 44 bit inputs wouldn't give a 45 bit output - it's just a few are swapped over. (In my case, anyway - haven't seen any others.) All my swaps were either in the "same column" of GraphViz output, or the next column.

So, yeah. Either "random swaps" with "nearby" outputs, because it's nearly right and you don't need to check further away; or use the fact that this is the well-known pattern for adding two numbers in a CPU's ALU to generate the "correct" sequence, identify which ones are wrong, and output them in alphabetical order.. The answer you need doesn't even require you to pair them up.

Yeah - dumped out the input into GraphViz, and then inspected it 'by eye' to get the swaps. Nearly finished in the top 100 in the world, too. Feels like a really bad way to get the solution, though.

If you add eg. 1111 and 1111 and expect 11110, then you'll get an output like 11010 if there's a mistake in "bit 2". Can try all the swaps between x2 / y2 / z2 until you get the "right answer", and then continue. There's only about five different ops for each "bit" of the input, so trying all of them won't take too long.

The ho-meow-ner, at that.

Bear in mind as well that the Scottish government rejected a lot of the privatisation that the remainder of the UK went through, so 'government' doesn't just mean civil servants in offices, it means things like Scottish Forestry and Scottish Water as well. Need to manage small teams of people over very large areas who are frequently out of mobile phone contact, as well as sharing information with subcontractors who will frequently be one-man-band operators who may just have a van and a mobile phone; no laptop, no IT team.

So 'convenient', but also 'almost nothing else would be practicable'.

I see Luigi, I vote it up.

C++ / Boost

Ah, cunning - my favourite one so far this year, I think. Nothing too special compared to the other solutions - floods the map using Dijkstra, then checks "every pair" for how much of a time saver it is. 0.3s on my laptop; it iterates through every pair twice since it does part 1 and part 2 separately, which could easily be improved upon.

#include <boost/log/trivial.hpp>
#include <boost/unordered/unordered_flat_map.hpp>
#include <boost/unordered/unordered_flat_set.hpp>
#include <cstddef>
#include <fstream>
#include <limits>
#include <queue>
#include <stdexcept>

namespace {

using Loc = std::pair<int, int>;
using Dir = std::pair<int, int>;
template <class T>
using Score = std::pair<size_t, T>;
template <class T>
using MinHeap = std::priority_queue<Score<T>, std::vector<Score<T>>, std::greater<Score<T>>>;
using Map = boost::unordered_flat_set<Loc>;

auto operator+(const Loc &l, const Dir &d) {
  return Loc{l.first + d.first, l.second + d.second};
}

auto manhattan(const Loc &a, const Loc &b) {
  return std::abs(a.first - b.first) + std::abs(a.second - b.second);
}

auto dirs = std::vector<Dir>{
    {0,  -1},
    {0,  1 },
    {-1, 0 },
    {1,  0 }
};

struct Maze {
  Map map;
  Loc start;
  Loc end;
};

auto parse() {
  auto rval = Maze{};
  auto line = std::string{};
  auto ih = std::ifstream{"input/20"};
  auto row = 0;
  while (std::getline(ih, line)) {
    for (auto col = 0; col < int(line.size()); ++col) {
      auto t = line.at(col);
      switch (t) {
      case 'S':
        rval.start = Loc{col, row};
        rval.map.insert(Loc{col, row});
        break;
      case 'E':
        rval.end = Loc{col, row};
        rval.map.insert(Loc{col, row});
        break;
      case '.':
        rval.map.insert(Loc{col, row});
        break;
      case '#':
        break;
      default:
        throw std::runtime_error{"oops"};
      }
    }
    ++row;
  }
  return rval;
}

auto dijkstra(const Maze &m) {
  auto unvisited = MinHeap<Loc>{};
  auto visited = boost::unordered_flat_map<Loc, size_t>{};

  for (const auto &e : m.map)
    visited[e] = std::numeric_limits<size_t>::max();

  visited[m.start] = 0;
  unvisited.push({0, {m.start}});

  while (!unvisited.empty()) {
    auto next = unvisited.top();
    unvisited.pop();

    if (visited.at(next.second) < next.first)
      continue;

    for (const auto &dir : dirs) {
      auto prospective = Loc{next.second + dir};
      if (!visited.contains(prospective))
        continue;
      auto pscore = next.first + 1;
      if (visited.at(prospective) > pscore) {
        visited[prospective] = pscore;
        unvisited.push({pscore, prospective});
      }
    }
  }

  return visited;
}

using Walk = decltype(dijkstra(Maze{}));

constexpr auto GOOD_CHEAT = 100;

auto evaluate_cheats(const Walk &walk, int skip) {
  auto rval = size_t{};
  for (auto &start : walk) {
    for (auto &end : walk) {
      auto distance = manhattan(start.first, end.first);
      if (distance <= skip && end.second > start.second) {
        auto improvement = int(end.second) - int(start.second) - distance;
        if (improvement >= GOOD_CHEAT)
          ++rval;
      }
    }
  }
  return rval;
}

} // namespace

auto main() -> int {
  auto p = parse();
  auto walk = dijkstra(p);
  BOOST_LOG_TRIVIAL(info) << "01: " << evaluate_cheats(walk, 2);
  BOOST_LOG_TRIVIAL(info) << "02: " << evaluate_cheats(walk, 20);
}

Cruelly overlooked: getting Tremors 1, 2, 3 and Highlander 1, 2, 3 onto this chart.

Yang Tengbo; "businessman" rather than anyone particularly public.

Can't believe she'd be so shellfish. You need to mullet over before doing something like that.

Good news is that it's such a bastard to program efficiently that most games don't make full use of it and you can get away with a certain amount of approximation in its behaviour for speed. Nice work, Sony.

Compare that with z80 or 6502 based machines, where you need to be beyond cycle perfect in some cases. Need to simulate every rising and falling edge for the CPU and its coprocessors in a SNES if you want to avoid every edge case, for instance.

Thought they were running GPT on a Playstation3 cluster, there. Sure, get the PS3 for cheap, but spare parts will be a bastard.