3-SUM-by-views created by realazthat - https://repl.it/MgQL/1787

generators.py

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

main.py

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'))

tests.py

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)

three_sum_bisect.py

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
  

three_sum_indexed.py

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)

three_sum_view.py

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
  
  

tsum_util.py

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)

view.py

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: