ModuloMathDictionary.py

gistfile1.txt

# rings.py
# module with ring arithmetic and multiplication and powers
# Did this a while ago on another machine? And made a github gist
from itertools import islice, cycle, tee
import random
from typing import Any

# from https://gist.github.com/mfm24/eac71574014a30ff0d3b662f947dd77e
# wrapped in class with `val` property
# This class is unnecessary for functionality, but helpful for debugging
# basically calls make_additive_ring but returns a dictionary s.t.
# d[n].val == n
# eg
# > d = MMDict.create(7)
# > [x.val for x in d[4].values()]
#   [4, 5, 6, 0, 1, 2, 3]
class MMDict(dict):
    lookup = {}
    @classmethod
    def create(kls, n):
        ret = make_additive_ring(n, kls)
        for k, v in ret.items():
            kls.lookup[id(v)] = k
        return ret

    @property
    def val(self):
        return self.lookup[id(self)]

# Make a self-referential dict where d[a][b] is d[a+b%n]
def make_additive_ring(n, dict_class=dict):
    dicts = [dict_class() for __ in range(n)]
    dicts_c = cycle(dicts)
    for d in dicts:
        d.update(dict(enumerate(islice(dicts_c, n))))
        ret = next(dicts_c)
    return ret

# alternative, slightly more cryptic
# def make_additive_ring(n, dict_class=dict):
#    a, b = tee(cycle(dict_class() for __ in range(n)))
#    for d in islice(a, n):
#        d.update(dict(enumerate(islice(b, n))))
#        ret = next(b)
#    return ret
    
d = MMDict.create(10)
assert d[3][5][7] is d[5]
assert d[3][5][7].val == 5
# note that any element of d behaves identically to d
#d = d[4]
assert d[3][5][7] is d[5]

d = MMDict.create(100)

# dict class that handles any type by using id(k) as key
# (Can use dicts as keys, but will only work for one singletons)
class IdDict(dict):
    def __getitem__(self, __key):
        return dict.__getitem__(self, id(__key))

    def __setitem__(self, __key, __value):
        dict.__setitem__(self, id(__key), __value)

class Multiplicative(IdDict):
    def __init__(self, base_dict):
        # unlike addition, in multiplication absolute values matter
        # we map addition rings dicts to multiplicative rings
        # because dictionaries aren't hashable, we use id(dict) instead
        # start at all 0s
        curr = {k: base_dict[0] for k in base_dict.keys()}
        for d in base_dict.values():
            self[d] = curr
            # add k to each v
            curr = {k: v[k] for k, v in curr.items()}

class Mapper(IdDict):
    def __init__(self, base_dict, init_val, next_val_f):
        # Start with init_val, and call next_val_f for each item
        curr = {k: init_val for k in base_dict.keys()}
        for d in base_dict.values():
            self[d] = curr
            # add k to each v
            curr = {k: next_val_f(k, v) for k, v in curr.items()}


# Multiplicative(d) is the same as Mapper(d, d[0], lambda k, v: v[k])
# Start with 0, add at each step
m = Mapper(d, d[0], lambda k, v: v[k])
# can we do powers?
# Start with 1, and multiply for each step
power = Mapper(d, d[1], lambda k, v: m[v][k])
# 0*3 = 0
assert m[d[0]][3] is d[0]
# 1*3 is 3
assert m[d[1]][3] is d[3]
# 2**3 is 8 (note operands are flipped, power[d[3]] is all cubes and power[d[3]][2] is second cube == 2**3)
assert power[d[3]][2] is d[8]

# can we do byte arithmetic?
b = make_additive_ring(256)
mb = Multiplicative(b)

# 7 * 8 = 56
assert 7*8 == 56
assert mb[b[7]][8] is b[56]
# 7 * 8 * 9 % 256 is 248
assert 7*8*9 % 256 == 248
assert mb[mb[b[7]][8]][9] is b[248]

d = MMDict.create(10)
d[0][0][0][0][0][0][0][0].val
d[9][9].val