Instantly share code, notes, and snippets.

# realazthat/generators.py Created Oct 19, 2017

3-SUM-by-views created by realazthat - https://repl.it/MgQL/1787
 import random def pathological_generator(Nbits,n,certify): if n == 0: assert not certify return (None,[]) chunk_bits = 4 chunk_N = (1 << chunk_bits) - 1 assert chunk_N == 0b1111 result = [0 for _ in range(n)] def add_some_bits(current_result, chunk_bits): new_result = [(x << chunk_bits) + random.randint(0,chunk_N) for x in current_result] k = random.randint(1, 4) for i in range(1,k+1): new_result += [random.choice(new_result) + random.choice(new_result) + i for _ in range(n // k)] new_result = random.sample(new_result,min(n,len(new_result))) return new_result steps = Nbits // chunk_bits remaining_bits = Nbits-(steps*chunk_bits) for step in range(steps): result = add_some_bits(result, chunk_bits) result = add_some_bits(result, chunk_bits=remaining_bits) if not certify: return (None, result) if n == 1: return ((0,0,0),[0]) ivalue = result[1] jvalue = result[min([n-1,2])] kvalue = ivalue + jvalue result[0] = kvalue random.shuffle(result) i = result.index(ivalue) j = result.index(jvalue) k = result.index(kvalue) triplet = i,j,k return triplet,result
 import time import sys import random import tests import unittest import three_sum_bisect from generators import pathological_generator from three_sum_view import solve_views from three_sum_indexed import solve_brute from view import to_view import tsum_util from functools import partial def measure_complexity(f,g,n,K,t=None, p=tsum_util.print_null): times = [] for n in range(1, 1000): p('testing K=%s trials with n=%s' % (K,n,)) t0 = time.time() for _ in range(K): certification, problem = g(n) solution = f(problem) if t: assert t(solution) dt = time.time() - t0 ddt = (dt-times[-1]) if len(times) > 0 else dt p('tested K trials with n=%s, K=%s, dt=%.4fs, dt/K=%.4fs, ddt=%.4fs' % (n,K,dt,dt/K, ddt)) times.append(dt) return times def bisect_main(): random.seed(1) numeric_max_bits = 8 sample_count = 1000 sample_length = 10 samples = [ pathological_generator( Nbits=numeric_max_bits, n=sample_length, certify=random.random() > 0.5) for _ in range(sample_count) ] # samples = [ #((0, 2, 1), [29, 41, 12]), # (None, [37, 17, 37]), # ((1, 0, 2), [50, 216, 266]) # ((1, 0, 0), [31, 0, 31]) # ] outfile = open('outfile.txt', 'w') heavy = True fancy = True p = tsum_util.print_null p = partial(print,file=outfile) for sample_index,(triplet, I) in enumerate(samples): print ('-') print ('sample index:',sample_index) print ('triplet, I:', repr((triplet, I))) certify = triplet is not None I,J,K = I,I,I if certify: i,j,k = triplet ivalue, jvalue, kvalue = I[i], J[j], K[k] assert ivalue + jvalue == kvalue triplets = three_sum_bisect.solve(I,J,K,p=p,heavy=heavy,choose='largest') print ('I:', I) print ('certify:', certify) print ('triplet:', triplet) print ('triplets:', triplets) print ('resolve(triplets):', tsum_util.resolve(I,J,K, triplets)) print ('len(triplets):', len(triplets)) print ('triplets:', triplets) if heavy: expected_triplets = solve_brute(I,J,K) print ('expected_triplets:', expected_triplets) print ('resolve(expected_triplets):', tsum_util.resolve(I,J,K, expected_triplets)) assert expected_triplets == triplets assert tsum_util.resolve(I,J,K, expected_triplets) == tsum_util.resolve(I,J,K, triplets) if certify: assert triplet in triplets triplets = tsum_util.resolve(I,J,K, triplets) for ivalue,jvalue,kvalue in triplets: assert ivalue + jvalue == kvalue def bisect_complexity_main(): random.seed(1) heavy = False p = tsum_util.print_null def f(problem): I,J,K = problem solution = three_sum_bisect.solve(I,J,K,p=p,heavy=heavy,choose='largest') return solution numeric_max_bits = 8 def g(n): certification,V = pathological_generator( Nbits=numeric_max_bits, n=n, certify=random.random() > 0.5) I,J,K = V,V,V problem = I,J,K return (certification,problem) times = measure_complexity(f,g,n=100,K=100,p=print) print (times) # bisect_main() bisect_complexity_main() def views_main(): random.seed(1) numeric_max_bits = 64 sample_count = 1 sample_length = 100 samples = [ pathological_generator( Nbits=numeric_max_bits, n=sample_length, certify=random.random() > 0.5) for _ in range(sample_count) ] # samples = [ # ( # (2, 4, 3), # [4079209076, 3965891272, 3648514451, 7266853563, 3618339112] # ), # (None, [8, 3, 25, 24, 19]), # ((1, 0, 2), [2, 18, 20, 29, 7]), # ((0, 8, 6), [7912, 46315, 7913, 1191, 38166, 47604, 28381, 20061, 20469, 7911]) # ((4, 6, 8), [35632, 33120, 113244, 113242, 8549, 113243, 13162, 51739, 21711, 57736]) # ((0, 2, 3), [6, 12, 22, 28]), # ((0, 0, 1), [14, 28, 15, 14]), # ((4, 7, 6), [22, 0, 69, 72, 226, 174, 296, 70]), # ] # unittest.main(module='tests') outfile = open('outfile.txt', 'w') heavy = True fancy = True p = tsum_util.print_null p = partial(print,file=outfile) for sample_index,(triplet, I) in enumerate(samples): print ('-') print ('sample index:',sample_index) print ('triplet, I:', repr((triplet, I))) certify = triplet is not None I,J,K = I,I,I if certify: i,j,k = triplet ivalue, jvalue, kvalue = I[i], J[j], K[k] assert ivalue + jvalue == kvalue # print (to_view(I,heavy=heavy).all_str()) # break; print ('I:',I) print ('to_view(I).collect():',to_view(I,heavy=heavy).collect()) print ('index(I):',tsum_util.index(I)) assert (to_view(I,heavy=heavy).collect() == tsum_util.index(I)) triplets = solve_views(to_view(I,heavy=heavy), to_view(J,heavy=heavy), to_view(K,heavy=heavy), heavy=heavy, p=p, expected_case='mmm', fancy=fancy) print ('I:', I) print ('certify:', certify) print ('triplet:', triplet) print ('resolve(triplet):', tsum_util.resolve(I,J,K, triplets)) print ('len(triplets):', len(triplets)) print ('triplets:', triplets) if heavy: expected_triplets = solve_brute(I,J,K) print ('resolve(expected_triplets):', tsum_util.resolve(I,J,K, expected_triplets)) assert expected_triplets == triplets assert tsum_util.resolve(I,J,K, expected_triplets) == tsum_util.resolve(I,J,K, triplets) if certify: assert triplet in triplets triplets = tsum_util.resolve(I,J,K, triplets) for ivalue,jvalue,kvalue in triplets: assert ivalue + jvalue == kvalue # random.seed(0) # N = 1 << 24 # M = 50 # I = ([random.randint(1, N) for _ in range(M)]) # N_I = max([x.bit_length() for x in I]) # I_str = list(map(lambda x: bin(x)[2:].zfill(N_I), I)) # I_str = list(map(lambda x: x[::-1], sorted(map(lambda x: x[::-1], I_str)))) # print ('\n'.join(I_str)) # print (numpy.zeros(shape=(50,50), dtype='bool'))
 import unittest from view import ViewCollection, to_view, div2, sub1 from three_sum_view import solve_views, solve_views_brute import util class ViewRegressionTests(unittest.TestCase): def test_even_div2(self): K = to_view([(4, 1), (8, 2)], heavy=True) # print (sub1(div2(K)).collect()) self.assertEqual(div2(K).collect(), [(2,1), (4,2)]) self.assertEqual(sub1(div2(K)).collect(), [(1,1), (3,2)]) def test_odd_sub1_div2(self): K = to_view([(5, 1), (9, 2)], heavy=True) # print (sub1(div2(sub1(K))).collect()) self.assertEqual(div2(sub1(K)).collect(), [(2,1), (4,2)]) self.assertEqual(sub1(div2(sub1(K))).collect(), [(1,1), (3,2)]) def test_sanity_001(self): I = to_view([8, 3, 25, 24, 19], heavy=True) self.assertEqual([x for x,_ in I.collect()], [8, 3, 25, 24, 19]) def do_test_solve_views(self,Is,Js,K): p = util.print_null heavy = True Is = [to_view(I,heavy=heavy) for I in Is] Is = ViewCollection.from_views(views=Is) Js = [to_view(J,heavy=heavy) for J in Js] Js = ViewCollection.from_views(views=Js) K = to_view(K,heavy=heavy) triplets = solve_views(Is,Js,K, heavy=heavy, p=p, expected_case='mmm',fancy=True) expected_triplets = solve_views_brute(Is, Js, K, indent=0,p=p,heavy=heavy) self.assertEqual(triplets, expected_triplets) def test_sample_001(self): Is = [ [(17816, 0), (16560, 1), (56622, 2), (28868, 9)], [(56620, 5), (25868, 7), (10854, 8)], ] Js = [ [(56620, 5), (25868, 7), (10854, 8)], [(17816, 0), (16560, 1), (56622, 2), (28868, 9)], ] K = [(56620, 5), (25868, 7), (10854, 8)] self.do_test_solve_views(Is,Js,K) def test_sanity_002(self): Is = [ [(17816, 0), (16560, 1), (56622, 2), (28868, 9)], [(4274, 4)], [(56620, 3), (6580, 6)], [(56620, 5), (25868, 7), (10854, 8)], ] Js = [ [(56620, 5), (25868, 7), (10854, 8)], [(56620, 3), (6580, 6)], [(4274, 4)], [(17816, 0), (16560, 1), (56622, 2), (28868, 9)], ] K = [(56620, 5), (25868, 7), (10854, 8)] self.do_test_solve_views(Is,Js,K)
 import statistics import tsum_util import three_sum_indexed import collections def bisect(V): median = statistics.median([x for (x,_) in V]) LHS = [(x,idx) for (x,idx) in V if x < median] RHS = [(x,idx) for (x,idx) in V if not (x < median)] return RHS,LHS def create_map(V): Vmap = collections.defaultdict(set) for x,idx in V: Vmap[x].add(idx) return Vmap def solve(I,J,K,*,choose,heavy,p): I = tsum_util.index(I) J = tsum_util.index(J) K = tsum_util.index(K) I0map = create_map(I) J0map = create_map(J) K0map = create_map(K) IJK = tsum_util.index(I+J+K) I = IJK[:len(I)] J = IJK[len(I):len(I)+len(J)] K = IJK[len(I)+len(J):] I,J,K = [tsum_util.dedupe(V) for V in [I,J,K]] Kmap = create_map(K) triplets = _solve(I,J,K,Kmap=Kmap,choose=choose,heavy=heavy,p=p,indent=0) results = [] for (ip,jp,kp) in triplets: ivalue,_ = IJK[ip] jvalue,_ = IJK[jp] kvalue,_ = IJK[kp] assert ivalue + jvalue == kvalue for i in I0map[ivalue]: for j in J0map[jvalue]: for k in K0map[kvalue]: results += [(i,j,k)] return tsum_util.normalize_triplets(results) def _solve(I,J,K,*, Kmap, choose, heavy, indent, p): idt = ' ' + ' '*indent p(idt, '-') p(idt, 'I:',I) p(idt, 'J:',J) p(idt, 'K:',K) p(idt, 'Kmap:',Kmap) p(idt, '|I|:',len(I)) p(idt, '|J|:',len(J)) p(idt, '|K|:',len(K)) if len(I) > len(J): I,J = J,I if len(J) < 2: assert len(I) <= len(J) results = three_sum_indexed.solve_brute_kmap(I,J,Kmap=Kmap, indent=indent+1, p=p) results = tsum_util.normalize_triplets(results) p(idt,'solving via brute force.') p(idt, 'results:',results) if heavy: expected_results = three_sum_indexed.solve_brute(I,J,K, indent=indent+1, p=p) expected_results = tsum_util.normalize_triplets(expected_results) assert results == expected_results return results if choose == 'largest': if len(I) < len(J): I,J = J,I elif choose == 'smallest': if len(I) > len(J): I,J = J,I else: assert False, "Impossible" p(idt,'median:',statistics.median([x for (x,_) in I])) LHS,RHS = bisect(I) results = [] results += _solve(LHS, J, K, Kmap=Kmap, choose=choose, heavy=heavy, indent=indent+1, p=p) results += _solve(RHS, J, K, Kmap=Kmap, choose=choose, heavy=heavy, indent=indent+1, p=p) results = tsum_util.normalize_triplets(results) p(idt, 'results:',results) if heavy: expected_results = three_sum_indexed.solve_brute(I,J,K, indent=indent+1, p=p) expected_results = tsum_util.normalize_triplets(expected_results) assert results == expected_results return results
 import tsum_util def solve_brute_kmap(I,J,Kmap, indent=0,p=tsum_util.print_null): assert tsum_util.is_indexed(I) assert tsum_util.is_indexed(J) results = [] for ivalue,i in I: for jvalue,j in J: kvalue = ivalue + jvalue if kvalue in Kmap: for k in Kmap[kvalue]: results += [(i,j,k)] return tsum_util.normalize_triplets(results) def solve_brute(I,J,K, indent=0,p=tsum_util.print_null): I = tsum_util.index(I) J = tsum_util.index(J) K = tsum_util.index(K) results = [] for ivalue,i in I: for jvalue,j in J: for kvalue,k in K: if ivalue + jvalue == kvalue: results += [(i,j,k)] return tsum_util.normalize_triplets(results)
 from view import DeltafiableView, ViewCollection, compute_case, fdiv2, div2, sub1, E, D, to_view from three_sum_indexed import solve_brute from tsum_util import print_null def solve_view_brute(I,J,K, *, indent,p,heavy): idt = ' ' + ' ' * indent # idt2 = ' ' + ' ' * (indent+1) assert isinstance(I, DeltafiableView) assert isinstance(J, DeltafiableView) assert isinstance(K, DeltafiableView) p(idt, 'solving via brute force.') p(idt, 'I:', I.collect()) p(idt, 'J:', J.collect()) p(idt, 'K:', K.collect()) results = solve_brute(I.collect(), J.collect(), K.collect(), indent,p) p(idt, 'results:', results) return results def _solve_and_filter_base_cases(*,Is,Js,K,indent,p,results,heavy): assert isinstance(Is, ViewCollection) assert isinstance(Js, ViewCollection) assert isinstance(K, DeltafiableView) assert K.size() > 0 Is_p = ViewCollection.from_views(views=[]) Js_p = ViewCollection.from_views(views=[]) for view_index in range(len(Is.views)): I = Is.views[view_index] J = Js.views[view_index] if I.size() == 0 or J.size() == 0: continue if I.size() == 1 or J.size() == 1: results += solve_view_brute(I,J,K,indent=indent+1,p=p,heavy=heavy) continue if I.is_zero_width() or J.is_zero_width(): I_p,J_p = I,J if I_p.is_zero_width(): I_p = to_view([0], heavy=heavy) if J_p.is_zero_width(): J_p = to_view([0], heavy=heavy) subresults = solve_view_brute(I_p,J_p,K,indent=indent+1,p=p,heavy=heavy) for (i_p,j_p,k) in subresults: i_originals = [] j_originals = [] if I.is_zero_width(): i_originals = [i for (_,i) in I.collect()] else: i_originals = [i_p] if J.is_zero_width(): j_originals = [j for (_,j) in J.collect()] else: j_originals = [j_p] for i in i_originals: for j in j_originals: results += [(i,j,k)] continue Is_p.views.append(I) Js_p.views.append(J) return (Is_p, Js_p, K) def solve_views_brute(Is,Js,K,indent,p, heavy): if isinstance(Is, DeltafiableView): Is = ViewCollection.from_views(views=[Is]) if isinstance(Js, DeltafiableView): Js = ViewCollection.from_views(views=[Js]) assert isinstance(Is, ViewCollection), Is assert isinstance(Js, ViewCollection) assert isinstance(K, DeltafiableView) Is.assert_sanity() Js.assert_sanity() K.assert_sanity() assert len(Is.views) == len(Js.views) results = [] for I,J in zip(Is.views,Js.views): results += solve_view_brute(I,J,K,indent=indent+1,p=p,heavy=heavy) return list(sorted(results)) def solve_views(Is,Js,K,*,expected_case,heavy,fancy,indent=0,p=print_null): idt = ' ' + ' ' * indent idt2 = ' ' + ' ' * (indent+1) if isinstance(Is, DeltafiableView): Is = ViewCollection.from_views(views=[Is]) if isinstance(Js, DeltafiableView): Js = ViewCollection.from_views(views=[Js]) assert isinstance(Is, ViewCollection), Is assert isinstance(Js, ViewCollection) assert isinstance(K, DeltafiableView) Is.assert_sanity() Js.assert_sanity() K.assert_sanity() assert len(Is.views) == len(Js.views) results = [] if K.size() == 0: results = sorted(results) assert results == solve_views_brute(Is, Js, K, indent=indent+1,p=p,heavy=heavy) return results # Store the original paramaters before modifying them. (Is0,Js0,K0) = Is,Js,K case = compute_case(Is) + compute_case(Js) + compute_case(K) p (idt,'case:',case) p (idt,'expected_case:',expected_case) p (idt,'Is:') p (idt2, ('\n' + idt2).join([str(I.collect()) for I in Is.views])) p (idt,'Js:') p (idt2, ('\n' + idt2).join([str(J.collect()) for J in Js.views])) p (idt,'K:',K.collect()) p (idt, '|Is|:',len(Is.views)) p (idt, '|Js|:',len(Js.views)) p (idt, 'Is total numbers:',Is.total_size()) p (idt, 'Js total numbers:',Js.total_size()) p (idt, 'K total numbers:',K.size()) p (idt, 'Is bits:',sum([I.bits() for I in Is.views])) p (idt, 'Js bits:',sum([J.bits() for J in Js.views])) p (idt, 'K bits:',K.bits()) (Is,Js,K) = _solve_and_filter_base_cases(Is=Is,Js=Js,K=K, p=p,indent=indent+1,results=results,heavy=heavy) assert len(Is.views) == len(Js.views) for I,J in zip(Is.views,Js.views): assert I.size() > 1 assert J.size() > 1 p(idt) p(idt, '- filtered -') p (idt,'Is:') p (idt2, ('\n' + idt2).join([str(I.collect()) for I in Is.views])) p (idt,'Js:') p (idt2, ('\n' + idt2).join([str(J.collect()) for J in Js.views])) p (idt,'K:',K.collect()) if len(Is.views) == 0 or len(Js.views) == 0: p (idt, 'all Is and Js were filtered out, so exiting early with current results') results = sorted(results) if heavy: expected_results = solve_views_brute(Is0, Js0, K0, indent=indent+1,p=p,heavy=heavy) p (idt, 'results:',results) p (idt, 'expected_results:',expected_results) assert results == expected_results return results for u in range(len(case)): assert expected_case[u] == 'm' or expected_case[u] == case[u] if expected_case == 'eee': p (idt, 'evens / 2 + evens / 2 = evens / 2') eee_results = solve_views(div2(Is),div2(Js),div2(K), indent=indent+1,p=p,heavy=heavy,expected_case='mmm',fancy=fancy) results += eee_results if heavy: expected_eee_results = solve_views_brute(div2(Is), div2(Js), div2(K), indent=indent+1,p=p,heavy=heavy) p (idt, 'eee_results:',eee_results) p (idt, 'expected_eee_results:',expected_eee_results) assert expected_eee_results == eee_results results = sorted(results) if heavy: expected_results = solve_views_brute(Is0, Js0, K0, indent=indent+1,p=p,heavy=heavy) p (idt, 'results:',results) p (idt, 'expected_results:',expected_results) assert expected_results == results return results # if expected_case == 'mme': # p (idt, 'evens / 2 + evens / 2 = evens / 2') # results += solve_views(div2(Is),div2(Js),div2(K), indent=indent+1,p=p,heavy=heavy,expected_case='mmm') # results = sorted(results) # if heavy: # expected_results = solve_views_brute(div2(Is), div2(Js), div2(K), indent=indent+1,p=p,heavy=heavy) # assert expected_results == results # assert results == solve_views_brute(Is0, Js0, K0, indent=indent+1,p=p,heavy=heavy) # return results #########SCAFOLDING################# ## ## # p (idt, 'evens/2 + evens/2 = evens/2') # results += solve_views(div2(E(Is)),div2(E(Js)),div2(E(K)), # indent=indent+1,p=p,heavy=heavy,expected_case='mmm',fancy=fancy) # p (idt, 'odds // 2 + odds // 2 = even // 2 - 1') # results += solve_views(fdiv2(D(Is)),fdiv2(D(Js)),sub1(div2(E(K))), # indent=indent+1,p=p,heavy=heavy,expected_case='mmm',fancy=fancy) ## ## #################################### if not fancy: p (idt, 'evens + odds - 1 = odds - 1') assert E(Is).total_size() == 0 or E(Is).is_all_even() results += solve_views(E(Is),sub1(D(Js)),sub1(D(K)), indent=indent+1,p=p,heavy=heavy,expected_case='eee',fancy=fancy) p (idt, 'odds - 1 + evens = odds - 1') results += solve_views(sub1(D(Is)),E(Js),sub1(D(K)), indent=indent+1,p=p,heavy=heavy,expected_case='eee',fancy=fancy) #########SCAFOLDING################# ## ## p (idt, 'evens/2 + evens/2 = evens/2') results += solve_views(div2(E(Is)),div2(E(Js)),div2(E(K)), indent=indent+1,p=p,heavy=heavy,expected_case='mmm',fancy=fancy) p (idt, 'odds // 2 + odds // 2 = even // 2 - 1') results += solve_views(fdiv2(D(Is)),fdiv2(D(Js)),sub1(div2(E(K))), indent=indent+1,p=p,heavy=heavy,expected_case='mmm',fancy=fancy) ## ## #################################### if fancy: Is_p = E(Is)|sub1(D(Is)) Js_p = sub1(D(Js))|E(Js) K_p = sub1(D(K)) assert Is_p.total_size() == 0 or Is_p.is_all_even() assert Js_p.total_size() == 0 or Js_p.is_all_even() assert K_p.size() == 0 or K_p.is_all_even(), D(K).collect() p(idt, 'evens|(odds-1) + (odds-1)|evens = odds-1') combined_results = solve_views(Is_p,Js_p,K_p, indent=indent+1,p=p,heavy=heavy,expected_case='eee',fancy=fancy) if heavy: edd_results = solve_views(E(Is),sub1(D(Js)),sub1(D(K)), indent=indent+1,p=p,heavy=heavy,expected_case='eee',fancy=fancy) ded_results = solve_views(sub1(D(Is)),E(Js),sub1(D(K)), indent=indent+1,p=p,heavy=heavy,expected_case='eee',fancy=fancy) expected_combined_results = sorted(edd_results + ded_results) assert combined_results == expected_combined_results results += combined_results #########SCAFOLDING################# ## ## # p (idt, 'evens/2 + evens/2 = evens/2') # results += solve_views(div2(E(Is)),div2(E(Js)),div2(E(K)), # indent=indent+1,p=p,heavy=heavy,expected_case='mmm',fancy=fancy) # p (idt, 'odds // 2 + odds // 2 = even // 2 - 1') # results += solve_views(fdiv2(D(Is)),fdiv2(D(Js)),sub1(div2(E(K))), # indent=indent+1,p=p,heavy=heavy,expected_case='mmm',fancy=fancy) Is_p = sub1(div2(E(Is)))|fdiv2(D(Is)) Js_p = div2(E(Js)) |fdiv2(D(Js)) K_p = sub1(div2(E(K))) p(idt, '(evens/2)|(odds//2) + (evens/2 - 1)|(odds//2) = evens//2 - 1') combined_results = solve_views(Is_p,Js_p,K_p, indent=indent+1,p=p,heavy=heavy,expected_case='mmm',fancy=fancy) if heavy: edd_results = solve_views(E(Is),sub1(D(Js)),sub1(D(K)), indent=indent+1,p=p,heavy=heavy,expected_case='eee',fancy=fancy) ded_results = solve_views(sub1(D(Is)),E(Js),sub1(D(K)), indent=indent+1,p=p,heavy=heavy,expected_case='eee',fancy=fancy) expected_combined_results = sorted(edd_results + ded_results) assert combined_results == expected_combined_results results += combined_results ## ## #################################### results = sorted(results) if heavy: expected_results = solve_views_brute(Is0, Js0, K0, indent=indent+1,p=p,heavy=heavy) p (idt, 'results:',results) p (idt, 'expected_results:',expected_results) assert results == expected_results return results
 def index(V): results = [] for i,element in enumerate(V): if isinstance(element,tuple): results.append(element) else: results.append((element,i)) return results def indices(V): assert is_indexed(V) return [idx for (_,idx) in V] def dedupe(V): assert is_indexed(V) seen = set() result = [] for (x,idx) in V: if x in seen: continue seen.add(x) result.append((x,idx)) return result def is_indexed(V): for _,element in enumerate(V): if isinstance(element,tuple): pass else: return False return True def print_null (*args,**kwargs): pass def resolve(I,J,K, triplets): I = index(I) J = index(J) K = index(K) results = [] for (i,j,k) in triplets: ivalue,_ = I[i] jvalue,_ = J[j] kvalue,_ = K[k] results += [ (ivalue,jvalue,kvalue) ] return results def normalize(V): results = list(sorted(V, key=lambda value_idx: value_idx[1])) return results def normalize_triplets(triplets): triplets = set(triplets) triplets = list(triplets) + [(j,i,k) for (i,j,k) in triplets] return sorted(triplets)
 import util import numpy as np class View: def __init__(self): self.heavy = None self.data = None self.indices = None self.x = None self.y = None self.w = None self.h = None @classmethod def from_np_data(cls, *, data, indices, heavy): obj = cls() obj.data = data obj.indices = indices obj.x = 0 obj.y = 0 obj.w = data.shape[0] obj.h = data.shape[1] obj.heavy = heavy return obj.assert_sanity() def _lsb_bit_col_idx(self): assert self.w > 0 return self.x + self.w - 1 def find_split(self): assert self.h > 0 if self.is_all_even(): assert self.get_low_bit(self.h - 1) == 0 return self.h if self.is_all_odd(): assert self.get_low_bit(0) == 1 return 0 low = 1 high = self.h - 1 # print (self.all_str()) # print (self.lsb_bits_str()) while high > low: mid = (low + high) // 2 prev_sample = self.get_low_bit(mid-1) sample = self.get_low_bit(mid) # print ('low:',low) # print ('high:',high) # print ('mid:',mid) # print ('sample:',sample) # print ('-') if prev_sample == 0 and sample == 1: low = mid high = mid break if self.get_low_bit(mid) == 1: high = mid - 1 continue if self.get_low_bit(mid) == 0: low = mid + 1 continue # print ('low:',low) # print ('high:',high) # print ('-') assert low == high offset = low assert offset <= self.h if offset < self.h: assert self.get_low_bit(offset) == 1 if offset > 0: assert self.get_low_bit(offset-1) == 0 return offset ############################################################################## ## Getters ############################################################################## # # def get_low_bit(self, idx): self.assert_sanity() assert not self.is_zero_width() assert 0 <= idx < self.h lsb_bit_col_idx = self._lsb_bit_col_idx() return 1 if self.data[lsb_bit_col_idx, self.y + idx] else 0 def size(self): self.assert_sanity() return self.h def is_zero_width(self): self.assert_sanity() if self.size() == 0: return False return self.w == 0 def is_mixed(self): self.assert_sanity() if self.size() == 0: return False if self.is_zero_width(): return False return self.is_any_even() and self.is_any_odd() def is_all_even(self): self.assert_sanity() if self.size() == 0: return False if self.is_zero_width(): return True return self.get_low_bit(self.h-1) == 0 def is_all_odd(self): self.assert_sanity() if self.size() == 0: return False if self.is_zero_width(): return False return self.get_low_bit(0) == 1 def is_any_even(self): self.assert_sanity() if self.size() == 0: return False if self.is_zero_width(): return True return self.get_low_bit(0) == 0 def is_any_odd(self): self.assert_sanity() if self.size() == 0: return False if self.is_zero_width(): return False return self.get_low_bit(self.h-1) == 1 # # ############################################################################## ############################################################################## ## Modifiers ## ############################################################################## # # @classmethod def make_clone(cls, old): old.assert_sanity() obj = cls() obj.data = old.data obj.indices = old.indices obj.x = old.x obj.y = old.y obj.w = old.w obj.h = old.h obj.heavy = old.heavy return obj.assert_sanity() def evens(self): self.assert_sanity() if self.size() == 0: return self.empty() if self.w == 0: return self offset = self.find_split() result = View.make_clone(self).assert_sanity() result.h = offset assert result.size() == 0 or result.is_all_even() if self.heavy: assert [x for (x,_) in result.collect()] == [x for (x,_) in self.collect() if (x % 2) == 0] return result.assert_sanity() def odds(self): self.assert_sanity() if self.w == 0 and self.size() == 0: return self.empty() offset = self.find_split() result = View.make_clone(self).assert_sanity() result.y += offset result.h -= offset assert result.size() == 0 or result.is_all_odd() if self.heavy: assert [x for (x,_) in result.collect()] == [x for (x,_) in self.collect() if (x % 2) == 1] return result.assert_sanity() def div2(self): if self.size() == 0: return self.empty() if self.w == 0: return self assert self.is_all_even() return self.fdiv2().assert_sanity() def fdiv2(self): self.assert_sanity() if self.size() == 0: return self.empty() if self.w == 0: return self assert self.is_all_even() or self.is_all_odd() result = View.make_clone(self).assert_sanity() result.w = max([0, result.w-1]) if self.heavy: assert [x // 2 for (x,_) in self.collect()] == [x for (x,_) in result.collect()] return result.assert_sanity() def empty(self): result = View.make_clone(self).assert_sanity() result.h = 0 assert result.size() == 0 assert result.w == self.w if self.heavy: assert result.collect() == [] return result.assert_sanity() # # ############################################################################## ############################################################################## ## Misc. ## ############################################################################## # # def lsb_bits(self): lsb_bit_col_idx = self._lsb_bit_col_idx() column = self.data[lsb_bit_col_idx:lsb_bit_col_idx+1, self.y:self.y+self.h] return column.reshape(self.h) def lsb_bits_str(self): data = self.lsb_bits() return ''.join('1' if x else '0' for x in data) def as_str(self): lines = [] for y in range(self.y, self.y + self.h): line = [] for x in range(self.x, self.x + self.w): line.append('1' if self.data[x,y] else '0') line = ''.join(line) lines.append(line) return '\n'.join(lines) def all_str(self): lines = [] for y in range(self.data.shape[1]): line = [] for x in range(self.data.shape[0]): line.append('1' if self.data[x,y] else '0') line = ''.join(line) lines.append(line) return '\n'.join(lines) def collect(self): results = [] for y in range(self.y,self.y + self.h): value = ['0'] for x in range(self.x, self.x + self.w): value.append('1' if self.data[x,y] else '0') value = int(''.join(value), 2) # The original index is stored in a column (list) self.indices. # We can use y to obtain the original. idx = self.indices[y] results += [(value, idx)] return util.normalize(results) def assert_sanity(self): assert isinstance(self.x, (int,)) assert isinstance(self.y, (int,)) assert isinstance(self.w, (int,)) assert isinstance(self.h, (int,)) assert isinstance(self.heavy, (bool)) assert 0 <= self.x <= self.data.shape[0] assert 0 <= self.y <= self.data.shape[1] assert 0 <= self.w <= self.data.shape[0] assert 0 <= self.h <= self.data.shape[1] assert 0 <= self.x+self.w <= self.data.shape[0] assert 0 <= self.y+self.h <= self.data.shape[1] if self.heavy: assert self.w == 0 or \ list(sorted(self.lsb_bits_str())) == list(self.lsb_bits_str()) return self # # ############################################################################## class DeltafiableView: def __init__(self): self._view = None self._delta = None @classmethod def from_np_data(cls,*,data,indices,heavy): obj = cls() obj._view = View.from_np_data(data=data,indices=indices,heavy=heavy) obj._delta = 0 obj.heavy = heavy return obj ############################################################################## ## Getters ############################################################################## def size(self): self.assert_sanity() return self._view.size() def is_all_even(self): self.assert_sanity() if self.size() == 0: return False if self._delta % 2 == 0: return self._view.is_all_even() return self._view.is_all_odd() def is_any_even(self): self.assert_sanity() if self.size() == 0: return False if self._delta % 2 == 0: return self._view.is_any_even() return self._view.is_any_odd() def is_all_odd(self): self.assert_sanity() if self.size() == 0: return False if self._delta % 2 == 0: return self._view.is_all_odd() return self._view.is_all_even() def is_any_odd(self): self.assert_sanity() if self.size() == 0: return False if self._delta % 2 == 0: return self._view.is_any_odd() return self._view.is_any_even() def is_mixed(self): self.assert_sanity() if self.size() == 0: return False return self._view.is_mixed() def is_zero_width(self): self.assert_sanity() return self._view.is_zero_width() and self._delta == 0 def bits(self): self.assert_sanity() return self._view.w * self._view.h # # ############################################################################## ############################################################################## ## Modifiers ############################################################################## # # @classmethod def make_clone(cls, old): old.assert_sanity() obj = cls() obj._view = View.make_clone(old._view) obj._delta = old._delta obj.heavy = old.heavy return obj.assert_sanity() def div2(self): self.assert_sanity() if self.size() == 0: return self.empty() assert self.is_all_even() return self.fdiv2() def fdiv2(self): self.assert_sanity() if self.size() == 0: return self.empty() # In this case, there is no good way to divide and keep the # same delta. The view must be split into evens and odds before dividing. # See https://repl.it/MoSN/48 . assert not (self._view.is_mixed() and self._delta % 2 == 1) result = DeltafiableView.make_clone(self).assert_sanity() result._view = result._view.fdiv2() result._delta >>= 1 if self._view.is_all_odd() and self._delta % 2 == 1: result._delta += 1 if self.heavy: assert [x // 2 for (x,_) in self.collect()] == [x for (x,_) in result.collect()] return result.assert_sanity() def sub1(self): self.assert_sanity() result = DeltafiableView.make_clone(self).assert_sanity() result._delta -= 1 if self.heavy: assert [x - 1 for (x,_) in self.collect()] == [x for (x,_) in result.collect()] return result.assert_sanity() def empty(self): result = DeltafiableView.make_clone(self).assert_sanity() result._view = result._view.empty() result._delta = 0 if self.heavy: assert [] == [x for (x,_) in result.collect()] return result.assert_sanity() def odds(self): self.assert_sanity() result = DeltafiableView.make_clone(self).assert_sanity() if self._delta % 2 == 0: result._view = result._view.odds() elif self._delta % 2 == 1: result._view = result._view.evens() if self.heavy: assert [x for (x,_) in self.collect() if x % 2 == 1] == [x for (x,_) in result.collect()] return result.assert_sanity() def evens(self): self.assert_sanity() result = DeltafiableView.make_clone(self).assert_sanity() if self._delta % 2 == 0: result._view = result._view.evens() elif self._delta % 2 == 1: result._view = result._view.odds() if self.heavy: assert [x for (x,_) in self.collect() if x % 2 == 0] == [x for (x,_) in result.collect()] return result.assert_sanity() # # ############################################################################## def assert_sanity(self): assert isinstance(self._delta, (int,)) assert isinstance(self._view, View) assert isinstance(self.heavy, (bool)) self._view.assert_sanity() return self def collect(self): V = self._view.collect() # Add in the delta. V = [(x + self._delta,idx) for (x,idx) in V] return V def all_str(self): return self._view.all_str() def dump(self): print ('x:', self._view.x, 'y:', self._view.y, 'w:', self._view.w, 'h:', self._view.h, 'd:', self._delta) print (self._view.as_str()) class ViewCollection: def __init__(self): self.views = None @classmethod def from_views(cls, views): obj = cls() obj.views = [DeltafiableView.make_clone(view) for view in views] return obj.assert_sanity() @classmethod def make_clone(cls, old): obj = cls() obj.views = [DeltafiableView.make_clone(view) for view in old.views] return obj.assert_sanity() def assert_sanity(self): assert isinstance(self.views, list) for view in self.views: assert isinstance(view, DeltafiableView) view.assert_sanity() return self def _apply(self,f): result = ViewCollection.from_views(views=[]) for view in self.views: result.views.append(f(view)) result.assert_sanity() return result def div2(self): self.assert_sanity() assert self.total_size() == 0 or self.is_all_even() return self._apply(lambda view: view.div2()).assert_sanity() def fdiv2(self): self.assert_sanity() return self._apply(lambda view: view.fdiv2()).assert_sanity() def sub1(self): self.assert_sanity() # assert self.total_size() == 0 or self.is_all_odd() return self._apply(lambda view: view.sub1()).assert_sanity() def evens(self): self.assert_sanity() return self._apply(lambda view: view.evens()).assert_sanity() def odds(self): self.assert_sanity() return self._apply(lambda view: view.odds()).assert_sanity() def is_all_odd(self): self.assert_sanity() return self.total_size() > 0 \ and all([view.size() == 0 or view.is_all_odd() for view in self.views]) def is_any_odd(self): self.assert_sanity() return self.total_size() > 0 \ and any([view.size() == 0 or view.is_any_odd() for view in self.views]) def is_all_even(self): self.assert_sanity() return self.total_size() > 0 \ and all([view.size() == 0 or view.is_all_even() for view in self.views]) def is_any_even(self): self.assert_sanity() return self.total_size() > 0 \ and any([view.size() == 0 or view.is_any_even() for view in self.views]) def is_mixed(self): self.assert_sanity() if self.total_size() == 0: return False if any([view.is_mixed() for view in self.views if view.size() != 0 ]): return True if self.is_any_odd() and self.is_any_even(): return True return False def total_size(self): self.assert_sanity() return sum([view.size() for view in self.views]) def collect(self): result = [] for view in self.views: result.append(view.collect()) return result def __or__(self, other): self.assert_sanity() other.assert_sanity() result = ViewCollection.make_clone(self).assert_sanity() result.views += [DeltafiableView.make_clone(view) for view in other.views] return result.assert_sanity() def to_view(V,*, heavy): n = len(V) V = util.index(V) # V = [x for (x,_) in V] # number of bits required to represent the largest entry in V. Nbits = max([x.bit_length() for (x,_) in V]) + 1 # A version of V with strings containing the binary representation # of the values. Vbin = [(bin(x)[2:], i) for (x,i) in V] # Pad them with leading 0s to Nbits. Vbin = [(x.zfill(Nbits), i) for (x,i) in Vbin] # Now reverse the strings temporarily, Vbin = [(x[::-1], i) for (x,i) in Vbin] # Sort Vbin by string-reversed-value. Vbin = list(sorted(Vbin)) # Reverse it again back to normal. Vbin = [(x[::-1], i) for (x,i) in Vbin] V_array = np.zeros(shape=(Nbits,n), dtype=bool) indices = [] for y,(bits,idx) in enumerate(Vbin): indices.append(idx) for x,xbit in enumerate(bits): V_array[x,y] = int(xbit) return DeltafiableView.from_np_data(data=V_array, indices=indices,heavy=heavy) def div2(Vs): assert isinstance(Vs, (DeltafiableView,ViewCollection)) return Vs.div2() def fdiv2(Vs): assert isinstance(Vs, (DeltafiableView,ViewCollection)) return Vs.fdiv2() def sub1(Vs): assert isinstance(Vs, (DeltafiableView,ViewCollection)) return Vs.sub1() def E(Vs): assert isinstance(Vs, (DeltafiableView,ViewCollection)) result = Vs.evens() result.assert_sanity() if isinstance(result, DeltafiableView): assert result.size() == 0 or result.is_all_even() else: assert result.total_size() == 0 or result.is_all_even() return result def D(Vs): assert isinstance(Vs, (DeltafiableView,ViewCollection)) result = Vs.odds() result.assert_sanity() if isinstance(result, DeltafiableView): assert result.size() == 0 or result.is_all_odd() else: assert result.total_size() == 0 or result.is_all_odd() return result def compute_case(Vs): assert isinstance(Vs, (DeltafiableView,ViewCollection)) if isinstance(Vs, (DeltafiableView)): V = Vs if V.size() == 0 or V.is_mixed(): return 'm' elif V.is_all_even(): return 'e' elif V.is_all_odd(): return 'd' else: print ('V.size():',V.size()) print ('V._view.w:',V._view.w) print ('V._view.is_zero_width():',V._view.is_zero_width()) print ('V.is_all_even():',V.is_all_even()) print ('V._view.is_all_even():',V._view.is_all_even()) print ('V.is_all_odd():',V.is_all_odd()) print ('V._view.is_all_odd():',V._view.is_all_odd()) print ('V.is_mixed():',V.is_mixed()) print ('V.collect():',V.collect()) assert False, "Impossible" if isinstance(Vs, (ViewCollection)): if Vs.total_size() == 0: return 'm' if Vs.is_all_even(): return 'e' elif Vs.is_all_odd(): return 'd' elif Vs.is_mixed(): return 'm' else: print ('Vs.collect():',Vs.collect()) print (([view.is_mixed() for view in Vs.views if view.size() != 0 ])) assert False, "Impossible" # if all([V.size() == 0 or V.is_all_even() for V in Vs.views]): # return 'e' # elif all([V.size() == 0 or V.is_all_odd() for V in Vs.views]): # return 'd' # elif any([V.size() > 0 and V.is_mixed() for V in Vs.views]): # return 'm' # else: