MILP solver for n1vm

milp-solver.py

#!/usr/bin/env python3
from pulp import LpProblem, LpVariable, lpSum, LpBinary, LpMinimize, PULP_CBC_CMD

A = [int(x, 16) for x in """35e, 60, 203, 73, 23e, 19f, 2f9, 79, 3a6, 26a, 348, 3b6, 45, 286, fe, 2b1,
231, 1a0, 22d, 1f7, 37c, 16e, 3e1, 2ab, 22, 19b, 5a, 6, 191, 52, 383, 98, 8e, 1f1, 19c, 3d, 215,
11, 338, 61, 88, 22a, 115, 222, 224, 1c1, 2, 2fc, 1ab, 3c5, cf, 3bd, 37a, 1ef, 1da, 2e8, dd, 198,
20a, 205, 81, 2b3, 2bd, 233, 173, 2c3, 1de, 140, 144, 18c, f4, 32f, d8, 1e5, 4c, 341, 27f, 33, 211,
18f, 2c6, 382, 8a, 2ef, 2e1, ab, 29d, de, e1, 31a, 390, 3de, 1ca, 368, 276, 234, 132, 2b6, 10d, 80,
3c2, a4, 3da, 3b0, 21e, 379, 78, 21a, 3cd, 34b, 384, 342, 204, f0, 19e, 11c, d9, 2ae, 3cc, 1e7, 74,
2c1, 87, 3bb, 2f, 369, 20b, 7, 372, 114, 30c, 189, 2b9, 18b, 39a, 23b, 127, 24, 57, 261, 3e7, 259,
2d5, 39e, 1a3, 3c3, 2fa, 13d, b1, 3e5, 27e, 21, 2e2, 3b1, 334, 305, 10b, 3a4, a1, 17c, 27d, 251,
187, f7, 37b, 346, 1d1, 1a1, 180, 2d6, 13e, 330, 2d4, 9, 3cb, 170, b9, 298, 6e, a7, 1fe, 2de, 25d,
34a, 9e, 175, 93, 3ce, 30e, 1c2, 2e3, 12a, 2d, 2f2, 2e9, 1a8, 13c, 3c9, 8d, 36e, 27c, 26e, 337,
393, 280, 26f, eb, 387, 121, 26b, 183, 16f, 65, 16a, 92, 6a, 36f, 14e, 1fc, ae, 169, 31f, 18e, d4,
295, 99, 14b, 109, 134, a0, ed, 1ea, 2d9, 111, 333, 263, 2e6, 188, 55, 2f8, 117, 1db, 1af, e7, 296,
2a7, 2f1, 18, 154, 5d, 17e, da, 2a9, fc, cd, 289,""".split(',') if x.strip()]
B = [int(x, 16) for x in """2f0, 328, 21b, 392, ba, 371, 4e, 99, 61, 380, e9, 1f3, 33c, 18, 20e, 33, 28, aa, 158, 188,
381, 331, 2e, 40, 1e4, 11, 1ed, 1e1, 14f, 204, 24c, 1df, 32b, 1cf, 271, 2ad, 25f, bf, fe, 306, 11a,
19a, 1b0, 399, 33f, f1, 2bb, fa, 3a4, 385, 6b, 164, 2f6, 7f, 51, 223, 173, 12b, 3ad, 86, 106, 27d,
390, 201, 1ab, 1b7, 3c9, 303, 25a, 2b1, 2a0, 288, 142, b0, 1f5, 72, 3e0, 37f, 3c4, 285, 35f, 293,
2d4, 2a8, 15, f6, 3b6, 34b, 171, 2c3, 27b, 28d, 38c, 137, 3b0, 5e, 329, 265, 11c, 9d, 2de, 24, f3,
34f, 246, 266, 133, 3a, 8e, 273, 279, 33e, 9c, 2f8, 107, 1af, 222, 1a3, 323, 2ff, 234, 2af, f, 1fa,
3d7, 120, 344, 3c8, 149, 25d, 36d, 1a, 160, 221, 5b, 75, 197, 275, 1b9, 31e, 2bc, 34c, 143, 3d0, 302,
103, 30f, 378, 32e, 1bb, 2ee, 2e6, 1c6, b6, 280, 348, 2fd, 3b3, 3a1, 1cc, 352, 128, 38b, 155, 354,
1c3, 1e8, 242, 244, 139, 30c, 1d6, 3bd, 12, b2, 23c, 1b8, 2fc, 281, 1d5, 36e, 77, 5f, 3da, 17e, 5c,
3b8, 2f4, c0, ab, b7, 3ca, 335, 2e0, 9f, 30a, 1a8, 16f, 39b, 25c, 1b, 105, fb, 393, 257, 224, 109,
cb, 3ba, 264, a3, 30d, 114, 3e7, eb, c5, 9a, 1ad, 2c1, 4c, 94, 2ce, 210, 330, 3ce, 1c0, 8, 26a, 6c,
2ae, 1, 156, 2a2, 29c, 1c1, 1d0, 388, 20f, 11f, 364, 389, 68, 58, 11e, 163, 373, 132, 296, 368, 45,
111, 5d, 231, 168, 1ec, 1a7,""".split(',') if x.strip()]

TARGET_A = 0x7b82
MAX_B = 0x1770

model = LpProblem("subset", LpMinimize)

x = [LpVariable(f"x{i}", cat=LpBinary) for i in range(256)]

# Constraints
model += lpSum(A[i] * x[i] for i in range(256)) == TARGET_A
model += lpSum(B[i] * x[i] for i in range(256)) <= MAX_B

solver = PULP_CBC_CMD(msg=False)
status = model.solve(solver)

selected = [i for i in range(256) if x[i].value() > 0.5]
print("Selected indices:", selected)
print("A-sum:", sum(A[i] for i in selected))
print("B-sum:", sum(B[i] for i in selected))

masks = [0, 0, 0, 0]
for i in selected:
    masks[i // 64] |= 1 << (i % 64)
for j, m in enumerate(masks):
    print(f"mask[{j}] = {m} (hex {hex(m)})")