Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.