writeups/2020/rgbctf/insert-creative-algo-chall-name

[insert creative algo chall name]

writeup by 5225225 for BLÅHAJ

Misc 449 points 67 solves

Find the total number of unique combinations for input values of x = 4 and n = 12

There exists a set of values, r, with values binary increasing (2^0, 2^1, ... 2^(n-1))

A combination is a set of x values where each value is generated by creating x subsets of r with all values within a subset being summed

The x subsets should use all values in r exactly once.

(full challenge text in challenge.txt)

Writeup

This is fairly simple stuff, easily translated into python. I installed more-itertools (https://more-itertools.readthedocs.io/en/stable/) for set_partitions, which makes this problem trivial.

import more_itertools

x = 4
n = 12

r = [2**i for i in range(n)]

parts = more_itertools.set_partitions(r, k = x)

summed = []
for p in parts:
    o = set()
    for i in p:
        o.add(sum(i))
    summed.append(o)

print(len(summed))