Skip to content

Instantly share code, notes, and snippets.

@william-silversmith
Last active January 31, 2018 04:51
Show Gist options
  • Save william-silversmith/509a27531138e496745b0533ab31557f to your computer and use it in GitHub Desktop.
Save william-silversmith/509a27531138e496745b0533ab31557f to your computer and use it in GitHub Desktop.
The first generalization of COUNTLESS 2D.
from itertools import combinations
from functools import reduce
def countless5(a,b,c,d,e):
"""First stage of generalizing from countless2d.
You have five slots: A, B, C, D, E
You can decide if something is the winner by first checking for
matches of three, then matches of two, then picking just one if
the other two tries fail. In countless2d, you just check for matches
of two and then pick one of them otherwise.
Unfortunately, you need to check ABC, ABD, ABE, BCD, BDE, & CDE.
Then you need to check AB, AC, AD, BC, BD
We skip checking E because if none of these match, we pick E. We can
skip checking AE, BE, CE, DE since if any of those match, E is our boy
so it's redundant.
Countless grows cominatorially in complexity.
"""
sections = [ a, b, c, d, e ]
p2 = lambda q,r: q * (q == r) # q if p == q else 0
p3 = lambda q,r,s: q * ( (q == r) & (r == s) ) # q if q == r == s else 0
lor = lambda x,y: x + (x == 0) * y # logical OR
# important to use generator expressions here to reduce peak memory usage
results3 = ( p3(x,y,z) for x,y,z in combinations(sections, 3) )
results3 = reduce(lor, results3)
results2 = ( p2(x,y) for x,y in combinations(sections[:-1], 2) )
results2 = reduce(lor, results2)
return reduce(lor, ( results3, results2, e ))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment