Skip to content

Instantly share code, notes, and snippets.

@joeyciechanowicz
Created February 27, 2025 12:21
Show Gist options
  • Save joeyciechanowicz/9819f8c1d5d8362ca70d606360092cc7 to your computer and use it in GitHub Desktop.
Save joeyciechanowicz/9819f8c1d5d8362ca70d606360092cc7 to your computer and use it in GitHub Desktop.
Rolling ship plate calculator
function closestSubsetSum(nums, target, maxIterations, prices) {
let closest = 0;
let cheapest = 100_000_000_000;
let closestSubset = [];
let found = false;
let count = 0;
nums.sort((a, b) => b - a); // Sort in descending order for better pruning
function findSubset(index, currentSubset, currentSum) {
count++;
if (count > 100_000_000) {
return;
}
if (currentSum > target || currentSubset.length > 7) return;
if (Math.abs(target - currentSum) <= Math.abs(target - closest)) {
closest = currentSum;
closestSubset = [...currentSubset];
if (closest === target) {
found = true;
const price = closestSubset.map(x => prices[x].price).reduce((sum, curr) => sum + curr);
if (price < cheapest) {
cheapest = price;
console.log(`Cheapest perfect solution found ${price.toLocaleString()}:`, closestSubset.map(x => prices[x].name));
}
}
}
for (let i = index; i < nums.length; i++) {
if (currentSum + nums[i] <= target || currentSubset.length < 7) {
findSubset(i + 1, [...currentSubset, nums[i]], currentSum + nums[i]);
}
}
}
findSubset(0, [], 0);
if (!found) {
console.log("Numbers used for closest sum:", closestSubset.map(x => x.toLocaleString()));
console.log("Closest ", closest.toLocaleString());
console.log("Target ", target.toLocaleString());
}
}
const m = (name, price) => ({ name, price });
const prices = {
// 100mm
20_000: m('100mm Fed Navy', 1_480_000),
25_000: m('100mm Citadella', 20_000),
32_500: m('100mm Cristalline', 28_200),
35_000: m('100mm Rolled Tungsten', 27_300),
// 37_500: m('100mm T2', 420_000),
90_000: m('200mm Fed Navy', 8_100_000),
100_000: m('200mm Syndicate', 73_100_000),
120_000: m('200mm Crystalline', 109_000),
140_000: m('200mm Rolled Tungsten', 107_000),
// 150_000: m('200mm T2', 1_280_000),
225_000: m('400mm Fed Navy', 14_400_000),
250_000: m('400mm Syndicate', 73_700_000),
300_000: m('400mm Crystalline', 224_000),
350_000: m('400mm Rolled Tungsten', 236_000),
// 375_000: m('400mm T2', 1_120_000),
900_000: m('800mm Fed Navy', 17_900_000),
1_000_000: m('800mm Syndicate', 84_700_000),
1_200_000: m('800mm Crystalline', 641_000),
1_350_000: m('800mm Rolled Tungsten', 649_000),
// 1_450_000: m('800mm T2', 4_840_000),
2_250_000: m('1600mm Fed Navy', 33_900_000),
2_500_000: m('1600mm Syndicate', 95_600_000),
3_000_000: m('1600mm Crystalline', 1_100_000),
3_500_000: m('1600mm Rolled Tungsten', 1_140_000),
// 3_750_000: m('1600mm T2', 9_910_000),
};
const numbers = Object.keys(prices).map(x => Array(7).fill(Number(x))).flat();
const shipWeight = 87_000_000;
const target = 100_000_000;
const toBeFilled = target - shipWeight;
const maxIterationsToSearch = 500_000_000;
closestSubsetSum(numbers, toBeFilled, maxIterationsToSearch, prices);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment