Skip to content

Instantly share code, notes, and snippets.

@xpqz

xpqz/balance.py

Created Apr 8, 2021
Embed
What would you like to do?
Python attempt at Problem 8, Phase II of the Dyalog APL Problem Solving Competition, 2020
import timeit
from itertools import chain, combinations
from collections import Counter
def balance(data):
total = sum(data)
if total % 2:
return None
target = total // 2
for subset in chain.from_iterable(combinations(data, r) for r in range(len(data) + 1)):
if sum(subset) == target:
return [list(subset), list((Counter(data) - Counter(subset)).elements())]
return None
def f():
return balance([10, 81, 98, 27, 28, 5, 1, 46, 63, 99, 25, 39, 84, 87, 76, 85, 78, 64, 41, 93])
print(timeit.timeit(f, number=3))
@xpqz

This comment has been minimized.

Copy link
Owner Author

@xpqz xpqz commented Apr 8, 2021

Runs in 40-50ms on my machine.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment