Problem 993: Banana Beaver

Problem 993 source code

C++

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;

constexpr u64 TARGET_N = 1'000'000'000'000'000'000ULL;
constexpr int CYCLE_START = 512;
constexpr int CYCLE_BANANAS = 71;
constexpr int CYCLE_SHIFT = 118;
constexpr int CHECK_LIMIT = 10'000;

struct Simulator {
    explicit Simulator(const int max_target)
        : offset(20 * max_target + 10'000),
          occupied(static_cast<std::size_t>(2 * offset + 10), 0) {}

    std::vector<i64> first_positions(const int max_target) {
        std::vector<i64> first(static_cast<std::size_t>(max_target + 1), 0);
        int filled = -1;

        while (filled < max_target) {
            const bool here = has(x);
            const bool next = has(x + 1);

            if (here && next) {
                clear(x + 1);
                --x;
            } else if (here) {
                clear(x);
                x += 2;
            } else if (next) {
                clear(x + 1);
                set(x);
                x += 2;
            } else {
                while (filled < std::min(line_count, max_target)) {
                    first[static_cast<std::size_t>(++filled)] = x;
                }

                assert(!has(x - 1) && !has(x) && !has(x + 1));
                set(x - 1);
                set(x);
                set(x + 1);
                x -= 2;
            }
        }

        return first;
    }

private:
    int offset;
    std::vector<unsigned char> occupied;
    i64 x = 0;
    int line_count = 0;

    std::size_t index(const i64 position) const {
        const i64 idx = position + static_cast<i64>(offset);
        assert(0 <= idx && idx < static_cast<i64>(occupied.size()));
        return static_cast<std::size_t>(idx);
    }

    bool has(const i64 position) const {
        return occupied[index(position)] != 0;
    }

    void set(const i64 position) {
        unsigned char& cell = occupied[index(position)];
        assert(cell == 0);
        cell = 1;
        ++line_count;
    }

    void clear(const i64 position) {
        unsigned char& cell = occupied[index(position)];
        assert(cell != 0);
        cell = 0;
        --line_count;
    }
};

std::string to_string_i128(i128 value) {
    if (value == 0) {
        return "0";
    }

    bool negative = false;
    if (value < 0) {
        negative = true;
        value = -value;
    }

    std::string result;
    while (value > 0) {
        result.push_back(static_cast<char>('0' + value % 10));
        value /= 10;
    }
    if (negative) {
        result.push_back('-');
    }
    std::reverse(result.begin(), result.end());
    return result;
}

i128 bb(const u64 n, const std::vector<i64>& first) {
    const u64 target = n <= 2 ? 0 : n - 2;
    if (target < first.size()) {
        return first[static_cast<std::size_t>(target)];
    }

    const u64 cycles = (target - CYCLE_START) / CYCLE_BANANAS;
    const int residue = CYCLE_START + static_cast<int>((target - CYCLE_START) % CYCLE_BANANAS);
    return static_cast<i128>(first[static_cast<std::size_t>(residue)]) +
           static_cast<i128>(cycles) * CYCLE_SHIFT;
}

void run_checkpoints(const std::vector<i64>& first) {
    assert(bb(0, first) == 0);
    assert(bb(1, first) == 0);
    assert(bb(2, first) == 0);
    assert(bb(3, first) == 1);
    assert(bb(5, first) == -1);
    assert(bb(1000, first) == 1499);

    for (int m = CYCLE_START; m + CYCLE_BANANAS <= CHECK_LIMIT; ++m) {
        assert(first[static_cast<std::size_t>(m + CYCLE_BANANAS)] ==
               first[static_cast<std::size_t>(m)] + CYCLE_SHIFT);
    }
}

}  // namespace

int main() {
    Simulator simulator(CHECK_LIMIT);
    const std::vector<i64> first = simulator.first_positions(CHECK_LIMIT);
    run_checkpoints(first);

    std::cout << to_string_i128(bb(TARGET_N, first)) << '\n';
    return 0;
}

Python

import sys

TARGET_N = 1_000_000_000_000_000_000
CYCLE_START = 512
CYCLE_BANANAS = 71
CYCLE_SHIFT = 118
CHECK_LIMIT = 10_000


class Simulator:
    def __init__(self, max_target):
        self.offset = 20 * max_target + 10_000
        self.occupied = [False] * (2 * self.offset + 10)
        self.x = 0
        self.line_count = 0

    def _index(self, position):
        idx = position + self.offset
        assert 0 <= idx < len(self.occupied)
        return idx

    def _has(self, position):
        return self.occupied[self._index(position)]

    def _set(self, position):
        idx = self._index(position)
        assert not self.occupied[idx]
        self.occupied[idx] = True
        self.line_count += 1

    def _clear(self, position):
        idx = self._index(position)
        assert self.occupied[idx]
        self.occupied[idx] = False
        self.line_count -= 1

    def first_positions(self, max_target):
        first = [0] * (max_target + 1)
        filled = -1

        while filled < max_target:
            here = self._has(self.x)
            nxt = self._has(self.x + 1)

            if here and nxt:
                self._clear(self.x + 1)
                self.x -= 1
            elif here:
                self._clear(self.x)
                self.x += 2
            elif nxt:
                self._clear(self.x + 1)
                self._set(self.x)
                self.x += 2
            else:
                stop = min(self.line_count, max_target)
                while filled < stop:
                    filled += 1
                    first[filled] = self.x

                assert not self._has(self.x - 1)
                assert not self._has(self.x)
                assert not self._has(self.x + 1)
                self._set(self.x - 1)
                self._set(self.x)
                self._set(self.x + 1)
                self.x -= 2

        return first


def bb(n, first):
    target = 0 if n <= 2 else n - 2
    if target < len(first):
        return first[target]

    cycles = (target - CYCLE_START) // CYCLE_BANANAS
    residue = CYCLE_START + (target - CYCLE_START) % CYCLE_BANANAS
    return first[residue] + cycles * CYCLE_SHIFT


def run_checkpoints(first):
    assert bb(0, first) == 0
    assert bb(1, first) == 0
    assert bb(2, first) == 0
    assert bb(3, first) == 1
    assert bb(5, first) == -1
    assert bb(1000, first) == 1499

    for m in range(CYCLE_START, CHECK_LIMIT - CYCLE_BANANAS + 1):
        assert first[m + CYCLE_BANANAS] == first[m] + CYCLE_SHIFT


def main(argv=None):
    argv = sys.argv if argv is None else argv
    should_run_checkpoints = True

    for arg in argv[1:]:
        if arg == "--skip-checkpoints":
            should_run_checkpoints = False
            continue
        print(f"Unknown argument: {arg}", file=sys.stderr)
        return 1

    simulator = Simulator(CHECK_LIMIT)
    first = simulator.first_positions(CHECK_LIMIT)

    if should_run_checkpoints:
        run_checkpoints(first)

    print(bb(TARGET_N, first))
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Java

public class Euler993 {
    private static final long TARGET_N = 1_000_000_000_000_000_000L;
    private static final int CYCLE_START = 512;
    private static final int CYCLE_BANANAS = 71;
    private static final int CYCLE_SHIFT = 118;
    private static final int CHECK_LIMIT = 10_000;

    private static final class Simulator {
        private final int offset;
        private final boolean[] occupied;
        private long x = 0L;
        private int lineCount = 0;

        private Simulator(int maxTarget) {
            offset = 20 * maxTarget + 10_000;
            occupied = new boolean[2 * offset + 10];
        }

        private int index(long position) {
            long idx = position + offset;
            if (idx < 0L || idx >= occupied.length) {
                throw new IllegalStateException("Position outside simulation window: " + position);
            }
            return (int) idx;
        }

        private boolean has(long position) {
            return occupied[index(position)];
        }

        private void set(long position) {
            int idx = index(position);
            if (occupied[idx]) {
                throw new IllegalStateException("Cell already occupied: " + position);
            }
            occupied[idx] = true;
            lineCount += 1;
        }

        private void clear(long position) {
            int idx = index(position);
            if (!occupied[idx]) {
                throw new IllegalStateException("Cell already empty: " + position);
            }
            occupied[idx] = false;
            lineCount -= 1;
        }

        private long[] firstPositions(int maxTarget) {
            long[] first = new long[maxTarget + 1];
            int filled = -1;

            while (filled < maxTarget) {
                boolean here = has(x);
                boolean next = has(x + 1);

                if (here && next) {
                    clear(x + 1);
                    x -= 1;
                } else if (here) {
                    clear(x);
                    x += 2;
                } else if (next) {
                    clear(x + 1);
                    set(x);
                    x += 2;
                } else {
                    int stop = Math.min(lineCount, maxTarget);
                    while (filled < stop) {
                        filled += 1;
                        first[filled] = x;
                    }

                    if (has(x - 1) || has(x) || has(x + 1)) {
                        throw new IllegalStateException("Drop cells are not empty");
                    }
                    set(x - 1);
                    set(x);
                    set(x + 1);
                    x -= 2;
                }
            }

            return first;
        }
    }

    private static long bb(long n, long[] first) {
        long target = n <= 2L ? 0L : n - 2L;
        if (target < first.length) {
            return first[(int) target];
        }

        long cycles = (target - CYCLE_START) / CYCLE_BANANAS;
        int residue = CYCLE_START + (int) ((target - CYCLE_START) % CYCLE_BANANAS);
        return first[residue] + cycles * CYCLE_SHIFT;
    }

    private static void require(boolean condition, String message) {
        if (!condition) {
            throw new IllegalStateException(message);
        }
    }

    private static void runCheckpoints(long[] first) {
        require(bb(0L, first) == 0L, "Checkpoint failed for BB(0)");
        require(bb(1L, first) == 0L, "Checkpoint failed for BB(1)");
        require(bb(2L, first) == 0L, "Checkpoint failed for BB(2)");
        require(bb(3L, first) == 1L, "Checkpoint failed for BB(3)");
        require(bb(5L, first) == -1L, "Checkpoint failed for BB(5)");
        require(bb(1000L, first) == 1499L, "Checkpoint failed for BB(1000)");

        for (int m = CYCLE_START; m + CYCLE_BANANAS <= CHECK_LIMIT; ++m) {
            require(first[m + CYCLE_BANANAS] == first[m] + CYCLE_SHIFT, "Cycle checkpoint failed at " + m);
        }
    }

    public static void main(String[] args) {
        boolean shouldRunCheckpoints = true;

        for (String arg : args) {
            if ("--skip-checkpoints".equals(arg)) {
                shouldRunCheckpoints = false;
                continue;
            }
            System.err.println("Unknown argument: " + arg);
            System.exit(1);
        }

        Simulator simulator = new Simulator(CHECK_LIMIT);
        long[] first = simulator.firstPositions(CHECK_LIMIT);

        if (shouldRunCheckpoints) {
            runCheckpoints(first);
        }

        System.out.println(bb(TARGET_N, first));
    }
}