# SPDX-License-Identifier: MIT

# computing — check codes, and calculate information and algorithms.
#
# Two halves that share nothing but the subject.
#
# STRUCTURE. You supply one kind of record as facts.
#
# A binary code (`computing.Code`) as its words, each a string of 0 and 1.
# `code()` writes the code, a record for each word, and a record for each
# ordered pair of them. The rules conclude the Kraft sum of the code, whether
# a pair has one word as the beginning of the other, and whether the code is
# prefix-free, so that a received string can be read without a separator. They
# also conclude whether the lengths could belong to any uniquely decodable
# code at all:
#
#     import computing
#     computing.code("good", ["0", "10", "110", "111"])
#     computing.code("bad", ["0", "01", "11"])
#     print(computing.prefix_free_codes(), computing.kraft_sum("good"))
#     print(computing.breaking_pairs("bad"), computing.kraft_sum("bad"))
#
# A Kraft sum of 1 is necessary and not sufficient: both codes above have 1,
# and only the first is prefix-free. The conclusion answers `why`, and
# `why_not` names the pair of words that breaks it. A corrected word withdraws
# what rested on it. Where two sources disagree about a fact, both values are
# reasoned about, and `unsettled()` names what they disagree about.
#
# The Kraft sum is the exception, since a sum adds every value it reads, and a
# word's weight is written as data: a word whose weight a second source writes,
# even the same weight, would be counted twice, a sum no source gives. So while
# a word is bound to its code twice, as a second weight binds it, the code is
# `disputed`: no Kraft sum, `complete` or `oversubscribed` is concluded for it,
# `disputed_codes()` names it, `kraft_sum()` refuses it, and `why_not` on its
# Kraft sum names the dispute. Forgetting the claim that is not to stand
# settles it. A word whose code two sources disagree on counts in each code a
# value names, so each of those Kraft sums is one source's. No other query
# refuses.
#
# CALCULATION. Value scripts that return a value and write nothing: the CRC-32
# and Adler-32 checksums, the Luhn and ISBN-13 checks, numbers in any base
# from 2 to 36 and back, the Hamming(7,4) code with its single-error
# correction and the Hamming distance, Shannon's entropy, Huffman code lengths,
# binary search and Dijkstra's shortest paths.
#
# DKE Python has no `while`, so every loop here is a `for` over a bound large
# enough for any input the script accepts, and a `break`. A bound is stated in
# the comment of the script it limits. A list holds one type, so Huffman's
# merging keeps its weights and its members in lists of their own. An `int` is
# 64 bits: the checksums fit, and a 64-bit hash that wraps would not.
#
# Sources, fetched 2026-11-08:
#   - CRC-32/ISO-HDLC has the check value 0xcbf43926 for the string 123456789
#     (https://reveng.sourceforge.io/crc-catalogue/17plus.htm). Cyclic codes
#     for error detection were first proposed by W. Wesley Peterson in 1961
#     (https://en.wikipedia.org/wiki/Cyclic_redundancy_check).
#   - Adler-32 is Mark Adler's of 1995: A starts at 1 and B at 0, both modulo
#     65521, and the result is B·65536 + A; "Wikipedia" gives 0x11E60398
#     (https://en.wikipedia.org/wiki/Adler-32).
#   - Luhn's check was patented by Hans Peter Luhn of IBM, granted in 1960;
#     17893729974 is the article's example of a valid number
#     (https://en.wikipedia.org/wiki/Luhn_algorithm).
#   - ISBN-13 weights its digits 1 and 3 alternately and the sum is a multiple
#     of 10; 978-0-306-40615-7 is the article's example
#     (https://en.wikipedia.org/wiki/ISBN).
#   - Hamming published his code in 1950 at Bell Labs; Hamming(7,4) adds three
#     parity bits to four data bits and corrects any single-bit error
#     (https://en.wikipedia.org/wiki/Hamming_code).
#   - Shannon's entropy is H = −Σ p log2 p, in bits, from his paper of 1948
#     (https://en.wikipedia.org/wiki/Entropy_(information_theory)).
#   - Huffman invented his code in 1951 as a student at MIT and published it in
#     1952 (https://en.wikipedia.org/wiki/Huffman_coding).
#   - The Kraft inequality, Σ 2^(−length) <= 1, is necessary and sufficient for
#     a prefix code of those lengths to exist (Kraft, 1949) and holds for every
#     uniquely decodable code (McMillan, 1956)
#     (https://en.wikipedia.org/wiki/Kraft%E2%80%93McMillan_inequality).
#   - Dijkstra conceived his algorithm in 1956 and published it in 1959; it
#     requires non-negative edge weights
#     (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm).
#
# `math.log2` returns the correctly rounded value, so an entropy agrees with
# CPython wherever CPython's own answer is right.

import math

# ── Codes as facts ───────────────────────────────────────────────────────────

class Code:
    # A binary code, by a name you choose. `kraft` is the Kraft sum, the sum of
    # 2 to the minus the length of each word, concluded by the rules from the
    # words. Computed from it: `complete`, True where it is exactly 1, and
    # `oversubscribed`, True where it is over 1 and no uniquely decodable code
    # has such lengths. `prefix_free` is True where no word begins another
    # (a word repeated counts as beginning itself). The rules also conclude
    # `claims` and `words`, which `disputed` compares: a word bound to the code
    # twice makes the code `disputed`, and then no Kraft sum is concluded.
    label: string
    claims: int
    words: int
    disputed: bool
    kraft: float
    complete: bool
    oversubscribed: bool = kraft > 1.0
    prefix_free: bool

class Word:
    # One word of the code named `code`, named `<code>_<bits>`: `bits` is the
    # string of 0 and 1, and `weight` is 2 to the minus its length, which
    # `code()` writes as data because a computed field cannot take a power.
    code: string
    bits: string
    weight: float

class Pair:
    # Two words of a code in order, named `<code>_<first>_<second>`: `first`
    # and `second` are the words, and `prefix` is True where the first is the
    # beginning of the second, or the same word. The rule `prefix_free`
    # needs none to be True.
    code: string
    first: string
    second: string
    prefix: bool

@rule
def code_claims():
    for c in Code, w in Word:
        if w.code == c and w.weight > -1.0e300:
            c.claims = count(w)

@rule
def code_words():
    for c in Code, w in Word:
        if w.code == c and w.weight > -1.0e300:
            c.words = distinct(w)

@rule
def code_disputed():
    # A sum adds every value it reads, so a word bound to the code twice
    # would be counted twice, which no source gives.
    for c in Code:
        if c.claims > c.words:
            c.disputed = True

@rule
def kraft_of_words():
    for c in Code, w in Word:
        if w.code == c and absent(c.disputed):
            c.kraft = sum(w.weight)

@rule
def complete():
    for c in Code:
        if c.kraft == 1.0:
            c.complete = True

@rule
def prefix_free():
    for c in Code:
        if none(p in Pair: p.code == c and p.prefix == True):
            c.prefix_free = True

# ── Writing facts ────────────────────────────────────────────────────────────

def code(name: string, words: list<string>):
    # A code from its words. It writes a record for each word and for each
    # ordered pair of different positions, so n words write n² pairs.
    update(Code(name).label, name, "code")
    for w in words:
        wn = name + "_" + w
        update(Word(wn).code, name, "code")
        update(Word(wn).bits, w, "code")
        update(Word(wn).weight, 0.5 ** len(w), "code")
    for i in range(len(words)):
        for j in range(len(words)):
            if i != j:
                a = words[i]
                b = words[j]
                hit = b.startswith(a)
                pn = name + "_" + a + "_" + b
                update(Pair(pn).code, name, "code")
                update(Pair(pn).first, a, "code")
                update(Pair(pn).second, b, "code")
                update(Pair(pn).prefix, hit, "code")

# ── Reading what the rules concluded ─────────────────────────────────────────
#
# Each reader reads every value in force, so a fact two sources disagree
# about is reported with both values rather than refused; only a reader of a
# disputed sum refuses (above).

def prefix_free_codes() -> list<string>:
    # The codes in which no word begins another, sorted.
    out = []
    vs = list_values(Code.prefix_free)
    for v in vs:
        parts = v.path.split(".")
        x = parts[len(parts) - 2]
        if v.value == True and x not in out:
            out = out + [x]
    return sorted(out)

def kraft_sum(name: string) -> float:
    # The Kraft sum of a code, 0.0 before its words are written. It refuses a
    # disputed code, which has none until the dispute is settled.
    if name in disputed_codes():
        raise ValueError("code " + name + " is disputed: a word of it is bound to it twice; forget the claim that is not to stand")
    k = current(Code.name.kraft)
    match k:
        case active_claim:
            match k.value:
                case real as x:
                    return x
                case default:
                    pass
        case empty:
            pass
    return 0.0

def disputed_codes() -> list<string>:
    # The codes a word is bound to twice, whose Kraft sum waits until one of
    # its values is forgotten, sorted.
    out = []
    vs = list_values(Code.disputed)
    for v in vs:
        parts = v.path.split(".")
        x = parts[len(parts) - 2]
        if v.value == True and x not in out:
            out = out + [x]
    return sorted(out)

def breaking_pairs(name: string) -> list<string>:
    # Every pair "first second" of a code in which the first word begins the
    # second, sorted. Empty for a prefix-free code.
    out = []
    vs = list_values(Pair.prefix)
    for v in vs:
        parts = v.path.split(".")
        c = parts[len(parts) - 2]
        if v.value == True and c.startswith(name + "_"):
            ab = c[len(name) + 1:].split("_")
            s = ab[0] + " " + ab[1]
            if s not in out:
                out = out + [s]
    return sorted(out)

def unsettled() -> list<string>:
    # Each word and pair that holds two different values for a fact you
    # write, as "word x bits" and so on, sorted.
    out = []
    for f in ["bits", "weight", "first", "second", "prefix"]:
        if f == "bits":
            vs = list_values(Word.bits)
            label = "word "
        elif f == "weight":
            vs = list_values(Word.weight)
            label = "word "
        elif f == "first":
            vs = list_values(Pair.first)
            label = "pair "
        elif f == "second":
            vs = list_values(Pair.second)
            label = "pair "
        else:
            vs = list_values(Pair.prefix)
            label = "pair "
        seen = {}
        for v in vs:
            parts = v.path.split(".")
            s = label + parts[len(parts) - 2] + " " + parts[len(parts) - 1]
            x = str(v.value)
            if s in seen and seen[s] != x and s not in out:
                out = out + [s]
            seen[s] = x
    return sorted(out)

# ── Calculation: checksums and check digits ──────────────────────────────────

def crc32(data: string) -> int:
    # CRC-32/ISO-HDLC, bit by bit, of a string whose characters have codes
    # from 0 to 255, each taken as a byte: "123456789" gives 3421780262, which
    # is 0xcbf43926.
    crc = 4294967295
    for ch in data:
        crc = crc ^ ord(ch)
        for k in range(8):
            if crc & 1 == 1:
                crc = (crc >> 1) ^ 3988292384
            else:
                crc = crc >> 1
    return crc ^ 4294967295

def adler32(data: string) -> int:
    # Adler-32 of a string whose characters have codes from 0 to 255:
    # "Wikipedia" gives 300286872, which is 0x11e60398.
    a = 1
    b = 0
    for ch in data:
        a = (a + ord(ch)) % 65521
        b = (b + a) % 65521
    return b * 65536 + a

def luhn_valid(digits: string) -> bool:
    # Whether a string of digits passes Luhn's check: double every second
    # digit from the right, subtract 9 from any above 9, and the sum is a
    # multiple of 10.
    total = 0
    alt = False
    for i in range(len(digits)):
        d = int(digits[len(digits) - 1 - i])
        if alt:
            d = d * 2
            if d > 9:
                d = d - 9
        total = total + d
        alt = not alt
    return total % 10 == 0

def isbn13_valid(digits: string) -> bool:
    # Whether a string of exactly 13 digits, hyphens removed, passes the
    # ISBN-13 check: weights 1 and 3 alternately, the sum a multiple of 10.
    total = 0
    for i in range(13):
        d = int(digits[i])
        if i % 2 == 0:
            total = total + d
        else:
            total = total + 3 * d
    return total % 10 == 0

# ── Calculation: numbers and bits ────────────────────────────────────────────

def to_base(n: int, base: int) -> string:
    # n, at least 0, written in a base from 2 to 36 with the digits 0-9 and
    # a-z. An int has at most 63 binary digits, so the loop is bounded by 64.
    if n == 0:
        return "0"
    out = ""
    for step in range(64):
        if n == 0:
            break
        out = "0123456789abcdefghijklmnopqrstuvwxyz"[n % base] + out
        n = n // base
    return out

def from_base(text: string, base: int) -> int:
    # A number written in a base from 2 to 36, with lower-case digits, no
    # longer than the 63 binary digits an int holds.
    digits = "0123456789abcdefghijklmnopqrstuvwxyz"
    n = 0
    for ch in text:
        n = n * base + digits.index(ch)
    return n

def hamming_distance(a: int, b: int) -> int:
    # How many bits differ between a and b, both at least 0.
    x = a ^ b
    n = 0
    for step in range(64):
        if x == 0:
            break
        n = n + (x & 1)
        x = x >> 1
    return n

def hamming_encode(d: int) -> int:
    # Hamming(7,4): four data bits, d from 0 to 15, as a seven-bit word whose
    # bits from the left are p1 p2 d1 p3 d2 d3 d4. Eleven encodes as 51.
    d1 = (d >> 3) & 1
    d2 = (d >> 2) & 1
    d3 = (d >> 1) & 1
    d4 = d & 1
    p1 = d1 ^ d2 ^ d4
    p2 = d1 ^ d3 ^ d4
    p3 = d2 ^ d3 ^ d4
    return p1 * 64 + p2 * 32 + d1 * 16 + p3 * 8 + d2 * 4 + d3 * 2 + d4

def hamming_decode(w: int) -> int:
    # The four data bits of a Hamming(7,4) word, w from 0 to 127, after
    # correcting any single flipped bit. Two flipped bits are decoded
    # wrongly; the code cannot tell.
    b1 = (w >> 6) & 1
    b2 = (w >> 5) & 1
    b3 = (w >> 4) & 1
    b4 = (w >> 3) & 1
    b5 = (w >> 2) & 1
    b6 = (w >> 1) & 1
    b7 = w & 1
    s1 = b1 ^ b3 ^ b5 ^ b7
    s2 = b2 ^ b3 ^ b6 ^ b7
    s3 = b4 ^ b5 ^ b6 ^ b7
    pos = s1 + 2 * s2 + 4 * s3
    if pos > 0:
        w = w ^ (1 << (7 - pos))
    return ((w >> 4) & 1) * 8 + ((w >> 2) & 1) * 4 + ((w >> 1) & 1) * 2 + (w & 1)

# ── Calculation: information and algorithms ──────────────────────────────────

def entropy(counts: list<int>) -> float:
    # Shannon's entropy in bits of a source whose symbols occurred counts[i]
    # times: −Σ p log2 p. Two equal counts give 1.0, four give 2.0.
    n = 0
    for c in counts:
        n = n + c
    h = 0.0
    for c in counts:
        if c > 0:
            p = c / n
            h = h - p * math.log2(p)
    return h

def huffman_lengths(freqs: list<int>) -> list<int>:
    # The length of each symbol's codeword in a Huffman code for symbols that
    # occurred freqs[i] times, merging the two lightest groups at each step
    # (the lower index first on a tie). Frequencies 45, 13, 12, 16, 9 and 5
    # give 1, 3, 3, 3, 4 and 4. There are at most len(freqs) − 1 merges.
    weights = []
    members = []
    for i in range(len(freqs)):
        weights = weights + [freqs[i]]
        members = members + [[i]]
    depth = [0] * len(freqs)
    for step in range(len(freqs)):
        if len(weights) < 2:
            break
        lo = 0
        for i in range(len(weights)):
            if weights[i] < weights[lo]:
                lo = i
        hi = -1
        for i in range(len(weights)):
            if i != lo and (hi < 0 or weights[i] < weights[hi]):
                hi = i
        for leaf in members[lo]:
            depth[leaf] = depth[leaf] + 1
        for leaf in members[hi]:
            depth[leaf] = depth[leaf] + 1
        w = weights[lo] + weights[hi]
        m = members[lo] + members[hi]
        nw = []
        nm = []
        for i in range(len(weights)):
            if i != lo and i != hi:
                nw = nw + [weights[i]]
                nm = nm + [members[i]]
        weights = nw + [w]
        members = nm + [m]
    return depth

def binary_search(items: list<int>, target: int) -> int:
    # The index of target in a list sorted ascending, or −1. At most 64
    # halvings, which any list of an int's length needs.
    lo = 0
    hi = len(items) - 1
    for step in range(64):
        if lo > hi:
            break
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

def binary_search_steps(n: int, target: int) -> int:
    # How many probes a binary search of the indexes 0 to n − 1 makes to find
    # the index target: 9 for the first of 1,000 and 20 for the last of
    # 1,000,000. When the target is outside, how many it makes before it
    # gives up.
    lo = 0
    hi = n - 1
    steps = 0
    for step in range(64):
        if lo > hi:
            break
        steps = steps + 1
        mid = (lo + hi) // 2
        if mid == target:
            return steps
        if mid < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return steps

def dijkstra(n: int, edges: list<list<int>>, src: int) -> list<int>:
    # The shortest distance from node src to each of nodes 0 to n − 1, over
    # directed edges [from, to, weight] with weights from 0 up. A node not
    # reached keeps 1000000, so a path is shorter than that. It makes n
    # rounds of settling the nearest node.
    inf = 1000000
    dist = [inf] * n
    dist[src] = 0
    done = [False] * n
    for step in range(n):
        u = -1
        best = inf
        for i in range(n):
            if not done[i] and dist[i] < best:
                best = dist[i]
                u = i
        if u < 0:
            break
        done[u] = True
        for e in edges:
            if e[0] == u and dist[u] + e[2] < dist[e[1]]:
                dist[e[1]] = dist[u] + e[2]
    return dist