from collections import Counter import os import sys from typing import Literal pad_num = (sys.argv[1:] or ["0"])[0] # 0-255 or "1st" xor_right_shift_amount = int((sys.argv[2:] or [0])[0]) # 0-... search_width = int((sys.argv[3:] or [3])[0]) # >0 search_depth = int((sys.argv[4:] or [3])[0]) # >0 ################################################################################ type BitIndex = int type BitString = str with open("stations.txt", "rb") as f: names = f.readlines() names = [n[:-1] for n in names] bits: list[BitString] = [ # low index -> LSB "".join( # reverse bit repr for string so lsb is index 0 f"{c:08b}"[::-1] for c in s ) for s in names ] max_bits_for_name = max(len(b) for b in bits) # returns bitstring to concatenate (as padding) def mk_padding(orig_bitstring: BitString) -> BitString: pad_bits = ( f"{int(pad_num):08b}" if pad_num != "1st" else ( (orig_bitstring[0:] or "0" * 24)[0:8] ) ) return pad_bits[::-1] * (max_bits_for_name // 8) padded: list[BitString] = [ # .ljust(max_bits_for_name, "0") # (b + ("0" * 300))[0:max_bits_for_name] for b in bits # (b + ("101" * 300))[0:max_bits_for_name] for b in bits # !!!, 16b hash across 8 bytes (highest 68) # (b + ("10001011" * 300))[0:max_bits_for_name] for b in bits # (b + (b[0:8] * 300))[0:max_bits_for_name] for b in bits # !!!, results in a 15b hash across 8 bytes (+ start byte) # (b + (b[9:16] * 300))[0:max_bits_for_name] for b in bits # !!!, results in a 15b hash across 10 bytes # (b + (f"{len(b) // 8:0b}" * 300))[0:max_bits_for_name] for b in bits # 16b across 8 bytes # (b + ((f"{int(pad_num):08b}" if pad_num != "1st" else b[0:8]) * 300))[0:max_bits_for_name] for b in bits # pad each name to len.. (b + mk_padding(b))[0:max_bits_for_name] for b in bits ] # shift and xor each name, if requested: def xor_shift(b: BitString, bit_shift_right: int) -> BitString: rhs = b[bit_shift_right:] out = ''.join('1' if l != r else '0' for (l, r) in zip(b, rhs)) return out BITS_PER_NAME = max_bits_for_name - xor_right_shift_amount if xor_right_shift_amount != 0: padded = [ xor_shift(b, xor_right_shift_amount) for b in padded ] else: xor_right_shift_amount = "N/A" # print(len(padded)) # print(len(set(padded))) # from collections import defaultdict # x = defaultdict(list) # for i, n in enumerate(names): # x[padded[i][0:64]].append(str(n, encoding="utf-8")) # for l in x.values(): # if len(l) > 1: # print(l) # raise "f" # Alexandra # Alexandria type Bucket = list[BitString] def split_bucket(bucket: Bucket, bit_idx: BitIndex) -> tuple[Bucket, Bucket]: return ( [n for n in bucket if n[bit_idx] == "0"], [n for n in bucket if n[bit_idx] == "1"] ) def split_buckets(buckets: list[Bucket], idx: BitIndex) -> list[Bucket]: out: list[Bucket] = [] for bkt in buckets: out.extend(b for b in split_bucket(bkt, idx) if b != []) return out def score_next_splits(buckets: list[Bucket]) -> list[tuple[BitIndex, float]]: ''' for now, the heuristic of choice is how close to even a particular bit splits a bucket by we calculate the sum of abs difference of the lengths of the "left"/"right" buckets -- where the bit in being used to split is 0 and 1 respectively -- from half the length of the original bucket we then sum this value across all the buckets given to us to calculate a particular bit's score (lower is better) a bit that, if split on, results in every bucket having 0 or 1 item should have a score of 0 (perfect) ''' """ TODO: for scoring splits, maybe prefer indexes that give larger buckets a more even split? (see below) 413 206 207 103 103 103 104 413 300 113 150 150 56 57 perfect 160 140 48 65 158 142 46 69 prefer this one because: larger buckets are further away from "finishing" so we want them to have the more even split to potentially save an iteration down the road """ search = BITS_PER_NAME # 80 scores = [0. for _ in range(search)] not_stuck = False for split_idx in range(0, search): score = 0 for bkt in buckets: if len(bkt) <= 1: continue # already perfect (0/1 elem); shouldn't increase score non_zero_for_idx = sum(n[split_idx] != "0" for n in bkt) score += abs(non_zero_for_idx - len(bkt) / 2) * len(bkt) not_stuck = True scores[split_idx] = score if not not_stuck: raise Exception(f"uh-oh, stuck at: {buckets}") return sorted(enumerate(scores), key=lambda t: t[1]) # idx, score # objective: find the fewest number of `BitIndex`es to retain from each name # such that each name is in its own bucket def tree_search(buckets: list[Bucket], width: int = 1, depth: int = 1) -> list[BitIndex]: deepest = 0 # each resumable search generator yields `depth` score results; past that # it just picks the best child and drives it to completion # # depth must be >= 1 def tree_search_resumable( buckets: list[Bucket], _bit_idx: BitIndex, _score: float, width: int, depth: int, l: int, ): # if we're finished, don't bother expanding the tree (no children) if all(len(bkt) <= 1 for bkt in buckets): # instead just yield 0 scores (best) for all of `depth` and then # return our bit index yield 0 # depth 0 for _ in range(depth): yield 0 yield 0 return [_bit_idx] # otherwise... nonlocal deepest if l > deepest: deepest = l if l > (17 + depth): print(f"hit depth {l}, giving up", file=sys.stderr) sys.exit(1) # print(f"depth: {l}") # depth = 0 yield _score # set up children, use them as an indicator: splits_to_try = score_next_splits(buckets)[0:width] children = [ tree_search_resumable( split_buckets(buckets, split_idx), split_idx, score, width, depth, l + 1, ) for (split_idx, score) in splits_to_try ] for _ in range(depth): # TODO: maybe we should sum? weighted? not sure child_scores = [next(c) for c in children] yield min(child_scores) # pick the best child (and drop other children to save memory); then # use the best child to find a solution: child_idx = min(enumerate(child_scores), key=lambda t: t[1])[0] best_child = children[child_idx] del children # return the child's best solution, with our bit tacked on ret = yield from best_child return ret + [_bit_idx] sentinel = 999999 gen = tree_search_resumable(buckets, sentinel, 0.0, width, depth, 0) ret = None def get_ret(g): nonlocal ret ret = yield from g for score in get_ret(gen): # print(score) pass assert ret is not None assert ret[-1] == sentinel return ret[0:-1] def print_bit_indexes(indices: list[BitIndex]): indices.sort() def do_hash(bitstring): out = 0 for i in reversed(indices): out = out << 1 | (bitstring[i] == "1") return out empty_bitstring = mk_padding("") # how often is each bit in `indices` 0 or 1? bit_heat: list[Counter[Literal['1', '0']]] = [Counter() for _ in indices] for bitstring in padded: for (i, bit_idx) in enumerate(indices): bit = bitstring[bit_idx] bit_heat[i].update([bit]) lines: list[str] = [] seen = set[int]() for name, bitstring in zip(names + [b""], padded + [empty_bitstring]): hash_val = do_hash(bitstring) seen.add(hash_val) lines.append(f"0x{hash_val:08x} " + str(name, encoding="utf-8")) if "PRINT_HASHES" in os.environ: for ln in sorted(lines): print(ln) print() if "PRINT_HEAT" in os.environ: print("Selected Bit Frequency:") for (b, heat) in zip(indices, bit_heat): print(f" - {b:2}: {heat}") print() print("Heatmap:") # each cell covers a range of 16 addrs (4 bits) # 32 cols (another 5 bits) # rows determined by num remaining bits num_rows = 2 ** (len(indices) - 5 - 4) rows = [[0 for _ in range(32)] for _ in range(num_rows)] for hash_val in seen: col_idx = (hash_val >> 4) & (0b11111) row_idx = (hash_val >> 9) rows[row_idx][col_idx] += 1 # scale heat and display: hottest = max(c for row in rows for c in row) bg = lambda r, g=0, b=0: f"\x1b[48;2;{r};{g};{b}m" reset = "\x1b[0m" print(bg(0), end='') print('–'*(len(rows[0]) + 2)) for row in rows: print(f'{bg(0)}|', end='') for cell in row: if cell == 0: print(f'{reset} {bg(0)}', end='') continue scaled = (cell * 255) // hottest print(f'{bg(scaled)} {bg(0)}', end='') print(f'|{reset}') print(bg(0), end='') print('–'*(len(rows[0]) + 2), end='') print(reset) print() assert len(seen) == len(padded) or len(seen) == len(padded) + 1 empty_string_collides = len(seen) == len(padded) empty_coll = f"empty string {'collides' if empty_string_collides else '[DOES NOT COLLIDE]'}" mask = 0 bytes = [0 for _ in range(0, BITS_PER_NAME // 8)] for i in indices: mask |= 1 << i bytes[i // 8] += 1 num_bytes = sum(c != 0 for c in bytes) print(f"mask {mask:#X}; bits ({len(indices)}) across {num_bytes} bytes; {empty_coll};", indices) print_bit_indexes(tree_search([padded], search_width, search_depth)) print(f"PAD: {pad_num}; XOR w/right shift: {xor_right_shift_amount}; search {search_width}w {search_depth}d") print() # TODO: consider incorporating len to the hash? (more than just bit extraction) # TODO: try to use only bits in first 8 bytes; can use `PEXT` (x86) # TODO: try weirder stuff like xors? # - or variable rotates like https://www.officedaytime.com/simd512e/simdimg/binopv5.php?f=vprolvd # - or indexing from the _end_ of the strings rather than the start # - or using carryless multiplication on the inputs? (PCLMULQDQ) # want to minimize range of bit indices (pext) # # but also want to minimize number of bits (size of table) # # NOTE: constant pads are nice (easy to implement); bonus if the hash derived # entirely from constant pads doesn't conflict with any of the entries # 0X10100020000800204040586800C0; (15 bits) # A99 88 77 6655443322 11 # 0X880001404060383000E8; (16 bits) # # mask 0X14C010A0A060602800; bits (15) across 8 bytes [11, 13, 21, 22, 29, 30, 37, 39, 45, 47, 52, 62, 63, 66, 68] # WITH: pad w/b[0:8] # mask 0X100008283090D028E0; bits (16) across 8 bytes [5, 6, 7, 11, 13, 20, 22, 23, 28, 31, 36, 37, 43, 45, 51, 68] # WITH: pad w/010 repeating? (hard...) # want to prefer answers where fewer bytes are relevant