import hashlib
import random
import string
from contextlib import contextmanager
# Работаем с избыточностью
# Берём биты необходимые для N значений, они есть полезная нагрузка
# Избыточные биты это контрольная сумма для предыдущих
class Spreader:
def __init__(self, n, k, secret):
self.N = n
self.K = k
self.secret = secret
self.mul = k // n
def value_hash(self, value):
bitlen = value.bit_length()
bytelen = bitlen // 8
if bitlen % 8:
bytelen += 1
m = hashlib.sha1()
m.update(value.to_bytes(bytelen, 'little'))
m.update(self.secret)
return int.from_bytes(m.digest(), 'little') % self.mul
def spread(self, value):
return value * self.mul + self.value_hash(value)
def unspread(self, value):
h = value % self.mul
value //= self.mul
if self.value_hash(value) != h:
return value
def test_spreader():
s = Spreader(10, 100, b'a cat is fine too')
# Значения не повторяются
assert len
({s.
spread(i
) for i in range
(10)}) == 10
# Расшифровываются обратно
for i in range(10):
enc = s.spread(i)
# Плохие значения падают
bads = 0
for i in range(100):
try:
s.unspread(i)
except ValueError:
bads += 1
test_spreader()
# Делаем набор случайных перестановок в коде купона
@contextmanager
def unaffect_random(rand_seed):
rstate = random.getstate()
random.seed(rand_seed)
yield
random.setstate(rstate)
class Shuffler:
def __init__(self, slen, rand_seed=None):
self.slen = slen
len_range = list(range(slen))
with unaffect_random(rand_seed):
self.sequence = tuple(random.sample(len_range, 2) for _ in range(self.slen))
@staticmethod
def switch(string, a, b):
av = string[a]
bv = string[b]
string = string[:a] + bv + string[a + 1:]
string = string[:b] + av + string[b + 1:]
return string
def forward(self, string):
for a, b in self.sequence:
string = self.switch(string, a, b)
return string
def reverse(self, string):
for a, b in reversed(self.sequence):
string = self.switch(string, a, b)
return string
def test_shuffler():
assert Shuffler.
switch('ABCD', 0, 2) == 'CBAD' s = Shuffler(8, 3387434)
assert s.
reverse(s.
forward('12345678')) == '12345678'
test_shuffler()
# Далее собственно генерируем купоны
class CouponGenerator:
def __init__(self, coupon_count, token_length, token_chars, secret, rand_seed):
self.spreader = Spreader(coupon_count, len(token_chars) ** token_length, secret)
self.shuffler = Shuffler(token_length, rand_seed)
self.coupon_count = coupon_count
self.token_length = token_length
self.token_chars = token_chars
self.base = len(token_chars)
def int_to_code(self, n):
code = []
for i in range(self.token_length):
code.append(self.token_chars[n % self.base])
n //= self.base
return ''.join(reversed(code))
def code_to_int(self, code):
m = 1
n = 0
for char in reversed(code):
n += m * self.token_chars.index(char)
m *= self.base
return n
def __iter__(self):
for i in range(self.coupon_count):
value = self.spreader.spread(i)
yield self.shuffler.forward(self.int_to_code(value))
def recognize(self, code):
value = self.code_to_int(self.shuffler.reverse(code))
return self.spreader.unspread(value)
cg = CouponGenerator(100, 10, string.ascii_uppercase, b'a cat is fine too', 3387434)
assert cg.
int_to_code(0) == 'AAAAAAAAAA' assert cg.
int_to_code(1) == 'AAAAAAAAAB' assert cg.
int_to_code(2) == 'AAAAAAAAAC' assert cg.
code_to_int('AAAAAAAAAA') == 0 assert cg.
code_to_int('AAAAAAAAAB') == 1 assert cg.
code_to_int('AAAAAAAAAC') == 2 assert cg.
code_to_int('AAAAAAAABA') == len
(string.
ascii_uppercase)
for code_id, code in enumerate(cg):
print(code)
assert cg.
recognize(code
) == code_id
# SXAEJJNDDT
# VCAHJAMKRA
# DNAJKTHRZA
# OSBZDVGALY
# ZOBOIXYBSF
# HBBTCRKOCK
# HIBAGUEUDM
# QSCIYMQBSG
# ALCGIYAEAQ
# NWCDRNNOHZ
# NLCJVGJUMF
# RFDTGMHCPB
# UQDITQUGWP
# LBDDOSCPUP
# QGDGLSWVAR
# PMDAPDXXZM
# QHEOBGJKJT
# DQENBQQLXI
# TDEJRTHTYM
# RRFNJDEBWX
# ...
cg.recognize('AAAAAAAAAA') # ValueError
aW1wb3J0IGhhc2hsaWIKaW1wb3J0IHJhbmRvbQppbXBvcnQgc3RyaW5nCmZyb20gY29udGV4dGxpYiBpbXBvcnQgY29udGV4dG1hbmFnZXIKCiMg0KDQsNCx0L7RgtCw0LXQvCDRgSDQuNC30LHRi9GC0L7Rh9C90L7RgdGC0YzRjgojINCR0LXRgNGR0Lwg0LHQuNGC0Ysg0L3QtdC+0LHRhdC+0LTQuNC80YvQtSDQtNC70Y8gTiDQt9C90LDRh9C10L3QuNC5LCDQvtC90Lgg0LXRgdGC0Ywg0L/QvtC70LXQt9C90LDRjyDQvdCw0LPRgNGD0LfQutCwCiMg0JjQt9Cx0YvRgtC+0YfQvdGL0LUg0LHQuNGC0Ysg0Y3RgtC+INC60L7QvdGC0YDQvtC70YzQvdCw0Y8g0YHRg9C80LzQsCDQtNC70Y8g0L/RgNC10LTRi9C00YPRidC40YUKCgpjbGFzcyBTcHJlYWRlcjoKICAgIGRlZiBfX2luaXRfXyhzZWxmLCBuLCBrLCBzZWNyZXQpOgogICAgICAgIHNlbGYuTiA9IG4KICAgICAgICBzZWxmLksgPSBrCiAgICAgICAgc2VsZi5zZWNyZXQgPSBzZWNyZXQKICAgICAgICBzZWxmLm11bCA9IGsgLy8gbgogICAgICAgIGFzc2VydCBzZWxmLm11bCA+IDEKCiAgICBkZWYgdmFsdWVfaGFzaChzZWxmLCB2YWx1ZSk6CiAgICAgICAgYml0bGVuID0gdmFsdWUuYml0X2xlbmd0aCgpCiAgICAgICAgYnl0ZWxlbiA9IGJpdGxlbiAvLyA4CiAgICAgICAgaWYgYml0bGVuICUgODoKICAgICAgICAgICAgYnl0ZWxlbiArPSAxCgogICAgICAgIG0gPSBoYXNobGliLnNoYTEoKQogICAgICAgIG0udXBkYXRlKHZhbHVlLnRvX2J5dGVzKGJ5dGVsZW4sICdsaXR0bGUnKSkKICAgICAgICBtLnVwZGF0ZShzZWxmLnNlY3JldCkKICAgICAgICByZXR1cm4gaW50LmZyb21fYnl0ZXMobS5kaWdlc3QoKSwgJ2xpdHRsZScpICUgc2VsZi5tdWwKCiAgICBkZWYgc3ByZWFkKHNlbGYsIHZhbHVlKToKICAgICAgICBhc3NlcnQgMCA8PSB2YWx1ZSA8IHNlbGYuTgoKICAgICAgICByZXR1cm4gdmFsdWUgKiBzZWxmLm11bCArIHNlbGYudmFsdWVfaGFzaCh2YWx1ZSkKCiAgICBkZWYgdW5zcHJlYWQoc2VsZiwgdmFsdWUpOgogICAgICAgIGFzc2VydCAwIDw9IHZhbHVlIDwgc2VsZi5LCgogICAgICAgIGggPSB2YWx1ZSAlIHNlbGYubXVsCiAgICAgICAgdmFsdWUgLy89IHNlbGYubXVsCgogICAgICAgIGlmIHNlbGYudmFsdWVfaGFzaCh2YWx1ZSkgIT0gaDoKICAgICAgICAgICAgcmFpc2UgVmFsdWVFcnJvcgoKICAgICAgICByZXR1cm4gdmFsdWUKCgpkZWYgdGVzdF9zcHJlYWRlcigpOgogICAgcyA9IFNwcmVhZGVyKDEwLCAxMDAsIGInYSBjYXQgaXMgZmluZSB0b28nKQoKICAgICMg0JfQvdCw0YfQtdC90LjRjyDQvdC1INC/0L7QstGC0L7RgNGP0Y7RgtGB0Y8KICAgIGFzc2VydCBsZW4oe3Muc3ByZWFkKGkpIGZvciBpIGluIHJhbmdlKDEwKX0pID09IDEwCgogICAgIyDQoNCw0YHRiNC40YTRgNC+0LLRi9Cy0LDRjtGC0YHRjyDQvtCx0YDQsNGC0L3QvgogICAgZm9yIGkgaW4gcmFuZ2UoMTApOgogICAgICAgIGVuYyA9IHMuc3ByZWFkKGkpCiAgICAgICAgYXNzZXJ0IHMudW5zcHJlYWQoZW5jKSA9PSBpCgogICAgIyDQn9C70L7RhdC40LUg0LfQvdCw0YfQtdC90LjRjyDQv9Cw0LTQsNGO0YIKICAgIGJhZHMgPSAwCiAgICBmb3IgaSBpbiByYW5nZSgxMDApOgogICAgICAgIHRyeToKICAgICAgICAgICAgcy51bnNwcmVhZChpKQogICAgICAgIGV4Y2VwdCBWYWx1ZUVycm9yOgogICAgICAgICAgICBiYWRzICs9IDEKICAgIGFzc2VydCBiYWRzID09IDkwCgoKdGVzdF9zcHJlYWRlcigpCgoKIyDQlNC10LvQsNC10Lwg0L3QsNCx0L7RgCDRgdC70YPRh9Cw0LnQvdGL0YUg0L/QtdGA0LXRgdGC0LDQvdC+0LLQvtC6INCyINC60L7QtNC1INC60YPQv9C+0L3QsAoKCkBjb250ZXh0bWFuYWdlcgpkZWYgdW5hZmZlY3RfcmFuZG9tKHJhbmRfc2VlZCk6CiAgICByc3RhdGUgPSByYW5kb20uZ2V0c3RhdGUoKQogICAgcmFuZG9tLnNlZWQocmFuZF9zZWVkKQogICAgeWllbGQKICAgIHJhbmRvbS5zZXRzdGF0ZShyc3RhdGUpCgoKY2xhc3MgU2h1ZmZsZXI6CiAgICBkZWYgX19pbml0X18oc2VsZiwgc2xlbiwgcmFuZF9zZWVkPU5vbmUpOgogICAgICAgIHNlbGYuc2xlbiA9IHNsZW4KICAgICAgICBsZW5fcmFuZ2UgPSBsaXN0KHJhbmdlKHNsZW4pKQogICAgICAgIHdpdGggdW5hZmZlY3RfcmFuZG9tKHJhbmRfc2VlZCk6CiAgICAgICAgICAgIHNlbGYuc2VxdWVuY2UgPSB0dXBsZShyYW5kb20uc2FtcGxlKGxlbl9yYW5nZSwgMikgZm9yIF8gaW4gcmFuZ2Uoc2VsZi5zbGVuKSkKCiAgICBAc3RhdGljbWV0aG9kCiAgICBkZWYgc3dpdGNoKHN0cmluZywgYSwgYik6CiAgICAgICAgYXYgPSBzdHJpbmdbYV0KICAgICAgICBidiA9IHN0cmluZ1tiXQogICAgICAgIHN0cmluZyA9IHN0cmluZ1s6YV0gKyBidiArIHN0cmluZ1thICsgMTpdCiAgICAgICAgc3RyaW5nID0gc3RyaW5nWzpiXSArIGF2ICsgc3RyaW5nW2IgKyAxOl0KICAgICAgICByZXR1cm4gc3RyaW5nCgogICAgZGVmIGZvcndhcmQoc2VsZiwgc3RyaW5nKToKICAgICAgICBmb3IgYSwgYiBpbiBzZWxmLnNlcXVlbmNlOgogICAgICAgICAgICBzdHJpbmcgPSBzZWxmLnN3aXRjaChzdHJpbmcsIGEsIGIpCiAgICAgICAgcmV0dXJuIHN0cmluZwoKICAgIGRlZiByZXZlcnNlKHNlbGYsIHN0cmluZyk6CiAgICAgICAgZm9yIGEsIGIgaW4gcmV2ZXJzZWQoc2VsZi5zZXF1ZW5jZSk6CiAgICAgICAgICAgIHN0cmluZyA9IHNlbGYuc3dpdGNoKHN0cmluZywgYSwgYikKICAgICAgICByZXR1cm4gc3RyaW5nCgoKZGVmIHRlc3Rfc2h1ZmZsZXIoKToKICAgIGFzc2VydCBTaHVmZmxlci5zd2l0Y2goJ0FCQ0QnLCAwLCAyKSA9PSAnQ0JBRCcKICAgIHMgPSBTaHVmZmxlcig4LCAzMzg3NDM0KQogICAgYXNzZXJ0IHMucmV2ZXJzZShzLmZvcndhcmQoJzEyMzQ1Njc4JykpID09ICcxMjM0NTY3OCcKCgp0ZXN0X3NodWZmbGVyKCkKCgojINCU0LDQu9C10LUg0YHQvtCx0YHRgtCy0LXQvdC90L4g0LPQtdC90LXRgNC40YDRg9C10Lwg0LrRg9C/0L7QvdGLCgoKY2xhc3MgQ291cG9uR2VuZXJhdG9yOgogICAgZGVmIF9faW5pdF9fKHNlbGYsIGNvdXBvbl9jb3VudCwgdG9rZW5fbGVuZ3RoLCB0b2tlbl9jaGFycywgc2VjcmV0LCByYW5kX3NlZWQpOgogICAgICAgIHNlbGYuc3ByZWFkZXIgPSBTcHJlYWRlcihjb3Vwb25fY291bnQsIGxlbih0b2tlbl9jaGFycykgKiogdG9rZW5fbGVuZ3RoLCBzZWNyZXQpCiAgICAgICAgc2VsZi5zaHVmZmxlciA9IFNodWZmbGVyKHRva2VuX2xlbmd0aCwgcmFuZF9zZWVkKQogICAgICAgIHNlbGYuY291cG9uX2NvdW50ID0gY291cG9uX2NvdW50CiAgICAgICAgc2VsZi50b2tlbl9sZW5ndGggPSB0b2tlbl9sZW5ndGgKICAgICAgICBzZWxmLnRva2VuX2NoYXJzID0gdG9rZW5fY2hhcnMKICAgICAgICBzZWxmLmJhc2UgPSBsZW4odG9rZW5fY2hhcnMpCgogICAgZGVmIGludF90b19jb2RlKHNlbGYsIG4pOgogICAgICAgIGNvZGUgPSBbXQogICAgICAgIGZvciBpIGluIHJhbmdlKHNlbGYudG9rZW5fbGVuZ3RoKToKICAgICAgICAgICAgY29kZS5hcHBlbmQoc2VsZi50b2tlbl9jaGFyc1tuICUgc2VsZi5iYXNlXSkKICAgICAgICAgICAgbiAvLz0gc2VsZi5iYXNlCiAgICAgICAgcmV0dXJuICcnLmpvaW4ocmV2ZXJzZWQoY29kZSkpCgogICAgZGVmIGNvZGVfdG9faW50KHNlbGYsIGNvZGUpOgogICAgICAgIG0gPSAxCiAgICAgICAgbiA9IDAKICAgICAgICBmb3IgY2hhciBpbiByZXZlcnNlZChjb2RlKToKICAgICAgICAgICAgbiArPSBtICogc2VsZi50b2tlbl9jaGFycy5pbmRleChjaGFyKQogICAgICAgICAgICBtICo9IHNlbGYuYmFzZQogICAgICAgIHJldHVybiBuCgogICAgZGVmIF9faXRlcl9fKHNlbGYpOgogICAgICAgIGZvciBpIGluIHJhbmdlKHNlbGYuY291cG9uX2NvdW50KToKICAgICAgICAgICAgdmFsdWUgPSBzZWxmLnNwcmVhZGVyLnNwcmVhZChpKQogICAgICAgICAgICB5aWVsZCBzZWxmLnNodWZmbGVyLmZvcndhcmQoc2VsZi5pbnRfdG9fY29kZSh2YWx1ZSkpCgogICAgZGVmIHJlY29nbml6ZShzZWxmLCBjb2RlKToKICAgICAgICB2YWx1ZSA9IHNlbGYuY29kZV90b19pbnQoc2VsZi5zaHVmZmxlci5yZXZlcnNlKGNvZGUpKQogICAgICAgIHJldHVybiBzZWxmLnNwcmVhZGVyLnVuc3ByZWFkKHZhbHVlKQoKCmNnID0gQ291cG9uR2VuZXJhdG9yKDEwMCwgMTAsIHN0cmluZy5hc2NpaV91cHBlcmNhc2UsIGInYSBjYXQgaXMgZmluZSB0b28nLCAzMzg3NDM0KQphc3NlcnQgY2cuaW50X3RvX2NvZGUoMCkgPT0gJ0FBQUFBQUFBQUEnCmFzc2VydCBjZy5pbnRfdG9fY29kZSgxKSA9PSAnQUFBQUFBQUFBQicKYXNzZXJ0IGNnLmludF90b19jb2RlKDIpID09ICdBQUFBQUFBQUFDJwphc3NlcnQgY2cuY29kZV90b19pbnQoJ0FBQUFBQUFBQUEnKSA9PSAwCmFzc2VydCBjZy5jb2RlX3RvX2ludCgnQUFBQUFBQUFBQicpID09IDEKYXNzZXJ0IGNnLmNvZGVfdG9faW50KCdBQUFBQUFBQUFDJykgPT0gMgphc3NlcnQgY2cuY29kZV90b19pbnQoJ0FBQUFBQUFBQkEnKSA9PSBsZW4oc3RyaW5nLmFzY2lpX3VwcGVyY2FzZSkKCmZvciBjb2RlX2lkLCBjb2RlIGluIGVudW1lcmF0ZShjZyk6CiAgICBwcmludChjb2RlKQogICAgYXNzZXJ0IGNnLnJlY29nbml6ZShjb2RlKSA9PSBjb2RlX2lkCgojIFNYQUVKSk5ERFQKIyBWQ0FISkFNS1JBCiMgRE5BSktUSFJaQQojIE9TQlpEVkdBTFkKIyBaT0JPSVhZQlNGCiMgSEJCVENSS09DSwojIEhJQkFHVUVVRE0KIyBRU0NJWU1RQlNHCiMgQUxDR0lZQUVBUQojIE5XQ0RSTk5PSFoKIyBOTENKVkdKVU1GCiMgUkZEVEdNSENQQgojIFVRRElUUVVHV1AKIyBMQkRET1NDUFVQCiMgUUdER0xTV1ZBUgojIFBNREFQRFhYWk0KIyBRSEVPQkdKS0pUCiMgRFFFTkJRUUxYSQojIFRERUpSVEhUWU0KIyBSUkZOSkRFQldYCiMgLi4uCgpjZy5yZWNvZ25pemUoJ0FBQUFBQUFBQUEnKSAgIyBWYWx1ZUVycm9yCg==