Created
February 27, 2025 12:21
-
-
Save joeyciechanowicz/9819f8c1d5d8362ca70d606360092cc7 to your computer and use it in GitHub Desktop.
Rolling ship plate calculator
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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