# File to be executed using python3 in the same folder as "results.json"
import json
import math
mmax = 50
with open('results.json') as f:
data = json.load(f)
pairs = [ [] ] * (mmax+1)
for x in data:
res = dict()
res['ratio'] = x[0]
n = res['n'] = x[1][1][0]
m = res['m'] = x[1][2]
res['bags'] = sorted(x[2])
res['allocations'] = x[5]
res['makespans'] = x[6]
res['opt'] = x[7]
# k = opt on m machines
k = math.ceil(n/float(m))
# the file contains solutions for 2 to m machines working
assert (m-1 == len(res['opt']) and m-1 == len(res['makespans']) and m-1 == len(res['allocations']))
# enough jobs are packed into bags
assert(sum(res['bags']) >= n)
# the number of bags is at most m
assert(len(res['bags']) <= m)
# for each number of working machines
for i in range(m-1):
mw = 2+i # number of working machines
makespan = res['makespans'][i]
allocation = res['allocations'][i]
opt = res['opt'][i]
# the makespan claimed respects the 4/3 bound
assert(makespan * 3 <= opt * 4 and opt == math.ceil(n / float(mw)))
# the allocation respects the makespan claimed
for machine in allocation:
assert(sum(machine) <= makespan)
# the allocation contains all bags
bags_placed = [b for machine in allocation for b in machine]
assert(res['bags'] == sorted(bags_placed))
# add the instance (m bags, n jobs) to the list of certified instances
pairs[m].append(n)
# check that all relevant pairs m*k-h for:
# 2<=k<=8 and m <=50
# k=9 and m <= 37
# k=10 and m <= 30
for m in range(3,mmax+1):
for k in range(2,10+1):
if ((k==9 and m>40) or (k==10 and m>30)):
continue
for h in range(0, min(k,m)):
assert( m*k-h in pairs[m])
print("All relevant numbers of bags and unit-size jobs certified:\n\
2<=k<=8 and m <= 50\n\
k=9 and m <= 40\n\
k=10 and m <= 30\n\
")