fork download
copy 
  1. import hashlib
  2. import random
  3. import string
  4. from contextlib import contextmanager
  5.  
  6. # Работаем с избыточностью
  7. # Берём биты необходимые для N значений, они есть полезная нагрузка
  8. # Избыточные биты это контрольная сумма для предыдущих
  9.  
  10.  
  11. class Spreader:
  12.     def __init__(self, n, k, secret):
  13.         self.N = n
  14.         self.K = k
  15.         self.secret = secret
  16.         self.mul = k // n
  17.         assert self.mul > 1
  18.  
  19.     def value_hash(self, value):
  20.         bitlen = value.bit_length()
  21.         bytelen = bitlen // 8
  22.         if bitlen % 8:
  23.             bytelen += 1
  24.  
  25.         m = hashlib.sha1()
  26.         m.update(value.to_bytes(bytelen, 'little'))
  27.         m.update(self.secret)
  28.         return int.from_bytes(m.digest(), 'little') % self.mul
  29.  
  30.     def spread(self, value):
  31.         assert 0 <= value < self.N
  32.  
  33.         return value * self.mul + self.value_hash(value)
  34.  
  35.     def unspread(self, value):
  36.         assert 0 <= value < self.K
  37.  
  38.         h = value % self.mul
  39.         value //= self.mul
  40.  
  41.         if self.value_hash(value) != h:
  42.             raise ValueError
  43.  
  44.         return value
  45.  
  46.  
  47. def test_spreader():
  48.     s = Spreader(10, 100, b'a cat is fine too')
  49.  
  50.     # Значения не повторяются
  51.     assert len({s.spread(i) for i in range(10)}) == 10
  52.  
  53.     # Расшифровываются обратно
  54.     for i in range(10):
  55.         enc = s.spread(i)
  56.         assert s.unspread(enc) == i
  57.  
  58.     # Плохие значения падают
  59.     bads = 0
  60.     for i in range(100):
  61.         try:
  62.             s.unspread(i)
  63.         except ValueError:
  64.             bads += 1
  65.     assert bads == 90
  66.  
  67.  
  68. test_spreader()
  69.  
  70.  
  71. # Делаем набор случайных перестановок в коде купона
  72.  
  73.  
  74. @contextmanager
  75. def unaffect_random(rand_seed):
  76.     rstate = random.getstate()
  77.     random.seed(rand_seed)
  78.     yield
  79.     random.setstate(rstate)
  80.  
  81.  
  82. class Shuffler:
  83.     def __init__(self, slen, rand_seed=None):
  84.         self.slen = slen
  85.         len_range = list(range(slen))
  86.         with unaffect_random(rand_seed):
  87.             self.sequence = tuple(random.sample(len_range, 2) for _ in range(self.slen))
  88.  
  89.     @staticmethod
  90.     def switch(string, a, b):
  91.         av = string[a]
  92.         bv = string[b]
  93.         string = string[:a] + bv + string[a + 1:]
  94.         string = string[:b] + av + string[b + 1:]
  95.         return string
  96.  
  97.     def forward(self, string):
  98.         for a, b in self.sequence:
  99.             string = self.switch(string, a, b)
  100.         return string
  101.  
  102.     def reverse(self, string):
  103.         for a, b in reversed(self.sequence):
  104.             string = self.switch(string, a, b)
  105.         return string
  106.  
  107.  
  108. def test_shuffler():
  109.     assert Shuffler.switch('ABCD', 0, 2) == 'CBAD'
  110.     s = Shuffler(8, 3387434)
  111.     assert s.reverse(s.forward('12345678')) == '12345678'
  112.  
  113.  
  114. test_shuffler()
  115.  
  116.  
  117. # Далее собственно генерируем купоны
  118.  
  119.  
  120. class CouponGenerator:
  121.     def __init__(self, coupon_count, token_length, token_chars, secret, rand_seed):
  122.         self.spreader = Spreader(coupon_count, len(token_chars) ** token_length, secret)
  123.         self.shuffler = Shuffler(token_length, rand_seed)
  124.         self.coupon_count = coupon_count
  125.         self.token_length = token_length
  126.         self.token_chars = token_chars
  127.         self.base = len(token_chars)
  128.  
  129.     def int_to_code(self, n):
  130.         code = []
  131.         for i in range(self.token_length):
  132.             code.append(self.token_chars[n % self.base])
  133.             n //= self.base
  134.         return ''.join(reversed(code))
  135.  
  136.     def code_to_int(self, code):
  137.         m = 1
  138.         n = 0
  139.         for char in reversed(code):
  140.             n += m * self.token_chars.index(char)
  141.             m *= self.base
  142.         return n
  143.  
  144.     def __iter__(self):
  145.         for i in range(self.coupon_count):
  146.             value = self.spreader.spread(i)
  147.             yield self.shuffler.forward(self.int_to_code(value))
  148.  
  149.     def recognize(self, code):
  150.         value = self.code_to_int(self.shuffler.reverse(code))
  151.         return self.spreader.unspread(value)
  152.  
  153.  
  154. cg = CouponGenerator(100, 10, string.ascii_uppercase, b'a cat is fine too', 3387434)
  155. assert cg.int_to_code(0) == 'AAAAAAAAAA'
  156. assert cg.int_to_code(1) == 'AAAAAAAAAB'
  157. assert cg.int_to_code(2) == 'AAAAAAAAAC'
  158. assert cg.code_to_int('AAAAAAAAAA') == 0
  159. assert cg.code_to_int('AAAAAAAAAB') == 1
  160. assert cg.code_to_int('AAAAAAAAAC') == 2
  161. assert cg.code_to_int('AAAAAAAABA') == len(string.ascii_uppercase)
  162.  
  163. for code_id, code in enumerate(cg):
  164.     print(code)
  165.     assert cg.recognize(code) == code_id
  166.  
  167. # SXAEJJNDDT
  168. # VCAHJAMKRA
  169. # DNAJKTHRZA
  170. # OSBZDVGALY
  171. # ZOBOIXYBSF
  172. # HBBTCRKOCK
  173. # HIBAGUEUDM
  174. # QSCIYMQBSG
  175. # ALCGIYAEAQ
  176. # NWCDRNNOHZ
  177. # NLCJVGJUMF
  178. # RFDTGMHCPB
  179. # UQDITQUGWP
  180. # LBDDOSCPUP
  181. # QGDGLSWVAR
  182. # PMDAPDXXZM
  183. # QHEOBGJKJT
  184. # DQENBQQLXI
  185. # TDEJRTHTYM
  186. # RRFNJDEBWX
  187. # ...
  188.  
  189. cg.recognize('AAAAAAAAAA')  # ValueError
  190.  
Runtime error #stdin #stdout #stderr 0.06s 12340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
SXAEJJNDDT
VCAHJAMKRA
DNAJKTHRZA
OSBZDVGALY
ZOBOIXYBSF
HBBTCRKOCK
HIBAGUEUDM
QSCIYMQBSG
ALCGIYAEAQ
NWCDRNNOHZ
NLCJVGJUMF
RFDTGMHCPB
UQDITQUGWP
LBDDOSCPUP
QGDGLSWVAR
PMDAPDXXZM
QHEOBGJKJT
DQENBQQLXI
TDEJRTHTYM
RRFNJDEBWX
FMFDKDSLND
XMFIWQLPWQ
ZHFWREGYIA
VDGKFBPEJV
XVGCYRELXO
EDGWMIORAN
VVGDGAHYJD
RWHZGPKCBX
IUHILTFJKC
ZOHQHTIQCL
GDITGALBME
KVIQQZEHZQ
YYIKVHYLEE
HJILDRJQGG
VHIQZZXZLR
PGJRFNXDRR
NZJGEVLOEW
CGJEFHVTCQ
BYJGUPTXLG
CXKCFPNEKY
UJKHNRNPYZ
QBKDJTUXHV
ESKQXSOYUA
GELIPGBJCO
UELGNVHMLG
VTLUMVRVLJ
QQMKVEQBJV
LRMWYIDGII
EOMFVTMRHE
ACMOSYGWSP
EPNOXHFDZP
RNNPXULNMB
HVNGPNGSGD
MCNVXEOYEX
VFOKHHQFHD
UOOHHOIIZP
EIOHUKZQGX
FXORCQHXKU
AFPXDSGCJM
TNPRXXKOHZ
UEPNXBLRFT
IFQQECWAMN
WWQILBYHEH
YDQYINIMWD
VHQCJPESYI
RHQFEHMZWS
BGRROLTERY
PBRNQAZLPL
ECRDMRXXPX
JSRUFFMYMY
IVSMUCLFLA
GISKLIEQXO
ACSSBRMYGA
WVTBOKIDSZ
EDTWROOJJL
IETVJHVRUA
ZFTQDESYYE
KSUCBXQBHC
CEUKKQJLYL
PAUINRSRLI
WWVOMLHAWP
UZVCLBBEXF
JDVSBINNWZ
ROVEBCHTFA
XOWMUYHBTF
IAWWYXGGHE
YBWKAYRKDO
GKWUMBWVYD
PHWQCHHZKG
CQXOTMNHNS
RQXYNYDKVZ
ZXXPZVHVGY
IYXBUREXYN
ORYKZEJIOJ
VSYVOSZNPF
DLYVFMAXLW
OOZUMEFFOJ
VRZQYILJQF
FWZMXUNNAY
YDZMBSBYGR
stderr
copy 
Traceback (most recent call last):
  File "./prog.py", line 189, in <module>
    cg.recognize('AAAAAAAAAA')  # ValueError
  File "./prog.py", line 151, in recognize
    return self.spreader.unspread(value)
  File "./prog.py", line 42, in unspread
    raise ValueError
ValueError
https://ideone.com/UFYCbC
language:
Python 3 nbc (python 3.7.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!