Last active
January 31, 2018 04:51
-
-
Save william-silversmith/509a27531138e496745b0533ab31557f to your computer and use it in GitHub Desktop.
The first generalization of COUNTLESS 2D.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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