Can You Sum Some Cards?

This Week's Fiddler

Et tu, Brute? Busy weekend for me but am looking forward to the smarter solution :)

We can just recursively search through all sequences until we find the longest one that isn't slappable!

from typing import Sequence


def is_not_slapped(seq: Sequence[int]):
    for p in range(0, len(seq) - 1):
        for q in range(p + 1, len(seq)):
            left = sum(seq[p:q])
            right = sum(seq[q:])
            if left == right:
                return False
    return True


def find_longest(n: int, seq: tuple[int, ...] = ()) -> tuple[int, ...]:
    best = seq
    for i in range(1, n + 1):
        next_seq = (*seq, i)
        if is_not_slapped(next_seq):
            cand = find_longest(n, next_seq)
            if len(cand) > len(best):
                best = cand
    return best


print(find_longest(4))

Output:

(1, 4, 3, 4, 2, 4, 3, 4, 1)

Answer: 9

Extra Credit

Took a bit for N = 6 and took a while for N = 7, but it works!

# Continue from above
...

print(find_longest(5))
print(find_longest(6))
print(find_longest(7))

Output:

(1, 3, 2, 4, 5, 3, 4, 5, 1, 3, 2, 4, 5, 3, 4)
(3, 5, 4, 6, 4, 3, 5, 4, 6, 5, 6, 2, 6, 5, 6, 1, 3, 5, 6, 1, 6)
(1, 7, 6, 7, 5, 7, 6, 4, 3, 4, 6, 7, 5, 7, 6, 7, 1, 7, 6, 7, 5, 7, 6, 4, 3, 4, 6, 7, 5, 7, 6)

There is probably some optimization that can be done with the sequence-checking. Maybe some sort of memory of prefixes as to what sums were already hit on the left side?

Answer: 15 (N = 5); 21 (N = 6); 31 (N = 7)