I'm not the only one up late thinking about this, then? Have some Python code. I represent these vectors of Y and N as integers (ie bit vectors), so findbest(5, 5) means find what scores are possible for the challenge YNYNN and all suffixes. Given that, it's an easy bit of dynamic programming to generate all the sequences that have a given score. I've tested it by comparison to brute force up to 11-bit sequences and it seems to be correct.
# findbest(l, challenge)[i][b] & (1 << s) != 0
# means: there is a solution to challenge >> (l-i) of length i
# starting with b, which scores s
def findbest(l, challenge):
if l == 0:
return [(1L, 1L)]
allbits = findbest(l-1, challenge >> 1)
down = allbits[-1]
bit = challenge & 1
res = [None, None]
res[bit] = down[bit] << 1
res[bit ^ 1] = down[0] | down[1]
allbits.append(tuple(res))
return allbits
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2005-11-02 01:04 am (UTC)# findbest(l, challenge)[i][b] & (1 << s) != 0 # means: there is a solution to challenge >> (l-i) of length i # starting with b, which scores s def findbest(l, challenge): if l == 0: return [(1L, 1L)] allbits = findbest(l-1, challenge >> 1) down = allbits[-1] bit = challenge & 1 res = [None, None] res[bit] = down[bit] << 1 res[bit ^ 1] = down[0] | down[1] allbits.append(tuple(res)) return allbits