Problem 891: Ambiguous Clock

Problem 891 source code

C++

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

namespace {

constexpr std::int64_t kCycleSeconds = 43200;

std::int64_t extended_gcd(std::int64_t a, std::int64_t b, std::int64_t& x,
                          std::int64_t& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    std::int64_t x1 = 0;
    std::int64_t y1 = 0;
    std::int64_t g = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

}  // namespace

int main() {
    const std::int64_t speeds[3] = {1, 12, 720};
    std::array<int, 3> idx = {0, 1, 2};

    std::vector<std::pair<std::int64_t, std::int64_t>> moments;
    moments.reserve(2100000);

    // For each non-identity permutation, eliminate rotation via differences to
    // get a linear congruence system: t = 43200*n/|det| and n' = C*n (mod |det|).
    do {
        if (idx[0] == 0 && idx[1] == 1 && idx[2] == 2) {
            continue;
        }
        std::int64_t pa = speeds[idx[0]];
        std::int64_t pb = speeds[idx[1]];
        std::int64_t pc = speeds[idx[2]];

        std::int64_t A = pb - pa;
        std::int64_t B = pc - pa;
        std::int64_t det = 719 * A - 11 * B;
        if (det == 0) {
            continue;
        }
        std::int64_t D = det > 0 ? det : -det;

        std::int64_t absA = A >= 0 ? A : -A;
        std::int64_t absB = B >= 0 ? B : -B;
        std::int64_t x = 0;
        std::int64_t y = 0;
        std::int64_t g = extended_gcd(absB, absA, x, y);
        if (g != 1) {
            std::cerr << "Unexpected gcd value.\n";
            return 1;
        }
        std::int64_t u = x * (B < 0 ? -1 : 1);
        std::int64_t v = y * (A < 0 ? -1 : 1);

        std::int64_t C = (11 * v + 719 * u) % D;
        if (C < 0) {
            C += D;
        }

        std::int64_t g1 = std::gcd<std::int64_t>(kCycleSeconds, D);
        std::int64_t num_base = kCycleSeconds / g1;
        std::int64_t den_base = D / g1;

        for (std::int64_t n = 0; n < D; ++n) {
            std::int64_t n2 = static_cast<std::int64_t>((__int128)n * C % D);
            if (n2 == n) {
                continue;
            }
            std::int64_t g2 = std::gcd<std::int64_t>(n, den_base);
            std::int64_t num = num_base * (n / g2);
            std::int64_t den = den_base / g2;
            moments.emplace_back(num, den);
        }
    } while (std::next_permutation(idx.begin(), idx.end()));

    std::sort(moments.begin(), moments.end());
    moments.erase(std::unique(moments.begin(), moments.end()), moments.end());

    std::cout << moments.size() << '\n';
    return 0;
}

Python

import math

def solve():
    CYCLE = 43200; speeds = [1, 12, 720]
    from itertools import permutations

    def egcd(a, b):
        if b == 0: return a, 1, 0
        g, x1, y1 = egcd(b, a%b)
        return g, y1, x1-(a//b)*y1

    moments = set()
    for perm in permutations([0,1,2]):
        if list(perm) == [0,1,2]: continue
        pa, pb, pc = speeds[perm[0]], speeds[perm[1]], speeds[perm[2]]
        A = pb-pa; B = pc-pa; det = 719*A - 11*B
        if det == 0: continue
        D = abs(det)
        absA, absB = abs(A), abs(B)
        g, x, y = egcd(absB, absA)
        u = x*(1 if B>=0 else -1); v = y*(1 if A>=0 else -1)
        C = (11*v + 719*u) % D
        if C < 0: C += D
        g1 = math.gcd(CYCLE, D); nb = CYCLE//g1; db = D//g1
        for n in range(D):
            n2 = n*C%D
            if n2 == n: continue
            g2 = math.gcd(n, db)
            num = nb*(n//g2); den = db//g2
            moments.add((num, den))

    return str(len(moments))

if __name__ == '__main__':
    print(solve())

Java

import java.util.HashSet;
import java.util.Objects;

public class Euler891 {
    static final long kCycleSeconds = 43200;

    static class GCDResult {
        long g, x, y;

        GCDResult(long g, long x, long y) {
            this.g = g;
            this.x = x;
            this.y = y;
        }
    }

    static GCDResult extendedGCD(long a, long b) {
        if (b == 0) {
            return new GCDResult(a, 1, 0);
        }
        GCDResult res = extendedGCD(b, a % b);
        long x = res.y;
        long y = res.x - (a / b) * res.y;
        return new GCDResult(res.g, x, y);
    }

    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static class Fraction {
        long num, den;

        Fraction(long num, long den) {
            this.num = num;
            this.den = den;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Fraction fraction = (Fraction) o;
            return num == fraction.num && den == fraction.den;
        }

        @Override
        public int hashCode() {
            return Objects.hash(num, den);
        }
    }

    public static String solve() {
        long[] speeds = { 1, 12, 720 };
        int[][] permutations = {
                { 0, 2, 1 }, { 1, 0, 2 }, { 1, 2, 0 }, { 2, 0, 1 }, { 2, 1, 0 }
        };

        HashSet<Fraction> moments = new HashSet<>();

        for (int[] idx : permutations) {
            long pa = speeds[idx[0]];
            long pb = speeds[idx[1]];
            long pc = speeds[idx[2]];

            long A = pb - pa;
            long B = pc - pa;
            long det = 719 * A - 11 * B;
            if (det == 0)
                continue;

            long D = Math.abs(det);
            long absA = Math.abs(A);
            long absB = Math.abs(B);

            GCDResult res = extendedGCD(absB, absA);
            long u = res.x * (B < 0 ? -1 : 1);
            long v = res.y * (A < 0 ? -1 : 1);

            long C = (11 * v + 719 * u) % D;
            if (C < 0)
                C += D;

            long g1 = gcd(kCycleSeconds, D);
            long numBase = kCycleSeconds / g1;
            long denBase = D / g1;

            for (long n = 0; n < D; ++n) {
                long n2 = (n * C) % D;
                if (n2 == n)
                    continue;

                long g2 = gcd(n, denBase);
                long num = numBase * (n / g2);
                long den = denBase / g2;
                moments.add(new Fraction(num, den));
            }
        }

        return Integer.toString(moments.size());
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}