All of the scripts for contracts in Bitburner.
Last active
March 31, 2024 20:08
-
-
Save OrangeDrangon/8a08d2d7d425fddd2558e1c0c5fae78b to your computer and use it in GitHub Desktop.
BitBurner Contract Solvers
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
import { getAllServers } from "getServers.js"; | |
export function main(ns) { | |
const contracts = getAllServers(ns, "home").flatMap((server) => { | |
const onServer = ns.ls(server, ".cct").map((contract) => { | |
const type = ns.codingcontract.getContractType(contract, server); | |
const data = ns.codingcontract.getData(contract, server); | |
const didSolve = solve(type, data, server, contract, ns); | |
return `${server} - ${contract} - ${type} - ${didSolve || "FAILED!"}`; | |
}); | |
return onServer; | |
}); | |
ns.tprint(`Found ${contracts.length} contracts`); | |
contracts.forEach((contract) => void ns.tprint(contract)); | |
} | |
function solve(type, data, server, contract, ns) { | |
let solution = ""; | |
ns.tprint(type); | |
switch (type) { | |
case "Algorithmic Stock Trader I": | |
solution = maxProfit([1, data]); | |
break; | |
case "Algorithmic Stock Trader II": | |
solution = maxProfit([Math.ceil(data.length / 2), data]); | |
break; | |
case "Algorithmic Stock Trader III": | |
solution = maxProfit([2, data]); | |
break; | |
case "Algorithmic Stock Trader IV": | |
solution = maxProfit(data); | |
break; | |
case "Minimum Path Sum in a Triangle": | |
solution = solveTriangleSum(data, ns); | |
break; | |
case "Unique Paths in a Grid I": | |
solution = uniquePathsI(data); | |
break; | |
case "Unique Paths in a Grid II": | |
solution = uniquePathsII(data); | |
break; | |
case "Generate IP Addresses": | |
solution = generateIps(data); | |
break; | |
case "Find Largest Prime Factor": | |
solution = factor(data); | |
break; | |
case "Spiralize Matrix": | |
solution = spiral(data); | |
break; | |
case "Merge Overlapping Intervals": | |
solution = mergeOverlap(data); | |
break; | |
} | |
return (solution != "") ? ns.codingcontract.attempt(solution, contract, server, [true]) : ""; | |
} | |
//ALGORITHMIC STOCK TRADER | |
function maxProfit(arrayData) { | |
let i, j, k; | |
let maxTrades = arrayData[0]; | |
let stockPrices = arrayData[1]; | |
// WHY? | |
let tempStr = "[0"; | |
for (i = 0; i < stockPrices.length; i++) { | |
tempStr += ",0"; | |
} | |
tempStr += "]"; | |
let tempArr = "[" + tempStr; | |
for (i = 0; i < maxTrades - 1; i++) { | |
tempArr += "," + tempStr; | |
} | |
tempArr += "]"; | |
let highestProfit = JSON.parse(tempArr); | |
for (i = 0; i < maxTrades; i++) { | |
for (j = 0; j < stockPrices.length; j++) { // Buy / Start | |
for (k = j; k < stockPrices.length; k++) { // Sell / End | |
if (i > 0 && j > 0 && k > 0) { | |
highestProfit[i][k] = Math.max(highestProfit[i][k], highestProfit[i - 1][k], highestProfit[i][k - 1], highestProfit[i - 1][j - 1] + stockPrices[k] - stockPrices[j]); | |
} else if (i > 0 && j > 0) { | |
highestProfit[i][k] = Math.max(highestProfit[i][k], highestProfit[i - 1][k], highestProfit[i - 1][j - 1] + stockPrices[k] - stockPrices[j]); | |
} else if (i > 0 && k > 0) { | |
highestProfit[i][k] = Math.max(highestProfit[i][k], highestProfit[i - 1][k], highestProfit[i][k - 1], stockPrices[k] - stockPrices[j]); | |
} else if (j > 0 && k > 0) { | |
highestProfit[i][k] = Math.max(highestProfit[i][k], highestProfit[i][k - 1], stockPrices[k] - stockPrices[j]); | |
} else { | |
highestProfit[i][k] = Math.max(highestProfit[i][k], stockPrices[k] - stockPrices[j]); | |
} | |
} | |
} | |
} | |
return highestProfit[maxTrades - 1][stockPrices.length - 1]; | |
} | |
//SMALLEST TRIANGLE SUM | |
function solveTriangleSum(arrayData, ns) { | |
let triangle = arrayData; | |
let nextArray; | |
let previousArray = triangle[0]; | |
for (let i = 1; i < triangle.length; i++) { | |
nextArray = []; | |
for (let j = 0; j < triangle[i].length; j++) { | |
if (j == 0) { | |
nextArray.push(previousArray[j] + triangle[i][j]); | |
} else if (j == triangle[i].length - 1) { | |
nextArray.push(previousArray[j - 1] + triangle[i][j]); | |
} else { | |
nextArray.push(Math.min(previousArray[j], previousArray[j - 1]) + triangle[i][j]); | |
} | |
} | |
previousArray = nextArray; | |
} | |
return Math.min.apply(null, nextArray); | |
} | |
//UNIQUE PATHS IN A GRID | |
function uniquePathsI(grid) { | |
const rightMoves = grid[0] - 1; | |
const downMoves = grid[1] - 1; | |
return Math.round(factorialDivision(rightMoves + downMoves, rightMoves) / (factorial(downMoves))); | |
} | |
function factorial(n) { | |
return factorialDivision(n, 1); | |
} | |
function factorialDivision(n, d) { | |
if (n == 0 || n == 1 || n == d) | |
return 1; | |
return factorialDivision(n - 1, d) * n; | |
} | |
function uniquePathsII(grid, ignoreFirst = false, ignoreLast = false) { | |
const rightMoves = grid[0].length - 1; | |
const downMoves = grid.length - 1; | |
let totalPossiblePaths = Math.round(factorialDivision(rightMoves + downMoves, rightMoves) / (factorial(downMoves))); | |
for (let i = 0; i < grid.length; i++) { | |
for (let j = 0; j < grid[i].length; j++) { | |
if (grid[i][j] == 1 && (!ignoreFirst || (i != 0 || j != 0)) && (!ignoreLast || (i != grid.length - 1 || j != grid[i].length - 1))) { | |
const newArray = []; | |
for (let k = i; k < grid.length; k++) { | |
newArray.push(grid[k].slice(j, grid[i].length)); | |
} | |
let removedPaths = uniquePathsII(newArray, true, ignoreLast); | |
removedPaths *= uniquePathsI([i + 1, j + 1]); | |
totalPossiblePaths -= removedPaths; | |
} | |
} | |
} | |
return totalPossiblePaths; | |
} | |
//GENERATE IP ADDRESSES | |
function generateIps(num) { | |
num = num.toString(); | |
const length = num.length; | |
const ips = []; | |
for (let i = 1; i < length - 2; i++) { | |
for (let j = i + 1; j < length - 1; j++) { | |
for (let k = j + 1; k < length; k++) { | |
const ip = [ | |
num.slice(0, i), | |
num.slice(i, j), | |
num.slice(j, k), | |
num.slice(k, num.length) | |
]; | |
let isValid = true; | |
ip.forEach(seg => { | |
isValid = isValid && isValidIpSegment(seg); | |
}); | |
if (isValid) ips.push(ip.join(".")); | |
} | |
} | |
} | |
return ips; | |
} | |
function isValidIpSegment(segment) { | |
if (segment[0] == "0" && segment != "0") return false; | |
segment = Number(segment); | |
if (segment < 0 || segment > 255) return false; | |
return true; | |
} | |
//GREATEST FACTOR | |
function factor(num) { | |
for (let div = 2; div <= Math.sqrt(num); div++) { | |
if (num % div != 0) { | |
continue; | |
} | |
num = num / div; | |
div = 2; | |
} | |
return num; | |
} | |
//SPIRALIZE Matrix | |
function spiral(arr, accum = []) { | |
if (arr.length === 0 || arr[0].length === 0) { | |
return accum; | |
} | |
accum = accum.concat(arr.shift()); | |
if (arr.length === 0 || arr[0].length === 0) { | |
return accum; | |
} | |
accum = accum.concat(column(arr, arr[0].length - 1)); | |
if (arr.length === 0 || arr[0].length === 0) { | |
return accum; | |
} | |
accum = accum.concat(arr.pop().reverse()); | |
if (arr.length === 0 || arr[0].length === 0) { | |
return accum; | |
} | |
accum = accum.concat(column(arr, 0).reverse()); | |
if (arr.length === 0 || arr[0].length === 0) { | |
return accum; | |
} | |
return spiral(arr, accum); | |
} | |
function column(arr, index) { | |
const res = []; | |
for (let i = 0; i < arr.length; i++) { | |
const elm = arr[i].splice(index, 1)[0]; | |
if (elm) { | |
res.push(elm); | |
} | |
} | |
return res; | |
} | |
// Merge Overlapping Intervals | |
function mergeOverlap(intervals) { | |
intervals.sort(([minA], [minB]) => minA - minB); | |
for (let i = 0; i < intervals.length; i++) { | |
for (let j = i + 1; j < intervals.length; j++) { | |
const [min, max] = intervals[i]; | |
const [laterMin, laterMax] = intervals[j]; | |
if (laterMin <= max) { | |
const newMax = laterMax > max ? laterMax : max; | |
const newInterval = [min, newMax]; | |
intervals[i] = newInterval; | |
intervals.splice(j, 1); | |
j = i; | |
} | |
} | |
} | |
return intervals; | |
} |
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
// Generate IP Addresses | |
function generateIps(num) { | |
num = num.toString(); | |
const length = num.length; | |
const ips = []; | |
for (let i = 1; i < length - 2; i++) { | |
for (let j = i + 1; j < length - 1; j++) { | |
for (let k = j + 1; k < length; k++) { | |
const ip = [ | |
num.slice(0, i), | |
num.slice(i, j), | |
num.slice(j, k), | |
num.slice(k, num.length) | |
]; | |
let isValid = true; | |
ip.forEach(seg => { | |
isValid = isValid && isValidIpSegment(seg); | |
}); | |
if (isValid) ips.push(ip.join(".")); | |
} | |
} | |
} | |
return ips; | |
} | |
function isValidIpSegment(segment) { | |
if (segment[0] == "0" && segment != "0") return false; | |
segment = Number(segment); | |
if (segment < 0 || segment > 255) return false; | |
return true; | |
} |
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
// Find Largest Prime Factor | |
export function factor(num) { | |
for (let div = 2; div <= Math.sqrt(num); div++) { | |
if (num % div != 0) { | |
continue; | |
} | |
num = num / div; | |
div = 1; | |
} | |
return num; | |
} |
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
// Merge Overlapping Intervals | |
export function mergeOverlap(intervals) { | |
intervals.sort(([minA], [minB]) => minA - minB); | |
for (let i = 0; i < intervals.length; i++) { | |
for (let j = i + 1; j < intervals.length; j++) { | |
const [min, max] = intervals[i]; | |
const [laterMin, laterMax] = intervals[j]; | |
if (laterMin <= max) { | |
const newMax = laterMax > max ? laterMax : max; | |
const newInterval = [min, newMax]; | |
intervals[i] = newInterval; | |
intervals.splice(j, 1); | |
j = i; | |
} | |
} | |
} | |
return intervals; | |
} |
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
// Minimum Path Sum in a Triangle | |
export function solveTriangleSum(arrayData) { | |
let triangle = arrayData; | |
let nextArray; | |
let previousArray = triangle[0]; | |
for (let i = 1; i < triangle.length; i++) { | |
nextArray = []; | |
for (let j = 0; j < triangle[i].length; i++) { | |
if (j == 0) { | |
nextArray.push(previousArray[j] + triangle[i][j]); | |
} else if (j == triangle[i].length - 1) { | |
nextArray.push(Math.min(previousArray[j], previousArray[j - 1]) + triangle[i][j]); | |
} else { | |
nextArray.push(previousArray[j - 1] + triangle[i][j]); | |
} | |
} | |
previousArray = nextArray; | |
} | |
return Math.min(nextArray); | |
} |
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
// Spiralize Matrix | |
export function spiral(arr, accum = []) { | |
if (arr.length === 0 || arr[0].length === 0) { | |
return accum; | |
} | |
accum = accum.concat(arr.shift()); | |
if (arr.length === 0 || arr[0].length === 0) { | |
return accum; | |
} | |
accum = accum.concat(column(arr, arr[0].length - 1)); | |
if (arr.length === 0 || arr[0].length === 0) { | |
return accum; | |
} | |
accum = accum.concat(arr.pop().reverse()); | |
if (arr.length === 0 || arr[0].length === 0) { | |
return accum; | |
} | |
accum = accum.concat(column(arr, 0).reverse()); | |
if (arr.length === 0 || arr[0].length === 0) { | |
return accum; | |
} | |
return spiral(arr, accum); | |
} | |
function column(arr, index) { | |
const res = []; | |
for (let i = 0; i < arr.length; i++) { | |
const elm = arr[i].splice(index, 1)[0]; | |
if (elm) { | |
res.push(elm); | |
} | |
} | |
return res; | |
} | |
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
// Algorithmic Stock Trader I | |
// Algorithmic Stock Trader II | |
// Algorithmic Stock Trader III | |
// Algorithmic Stock Trader IV | |
export function maxProfit(arrayData) { | |
let i, j, k; | |
let maxTrades = arrayData[0]; | |
let stockPrices = arrayData[1]; | |
// WHY? | |
let tempStr = "[0"; | |
for (i = 0; i < stockPrices.length; i++) { | |
tempStr += ",0"; | |
} | |
tempStr += "]"; | |
let tempArr = "[" + tempStr; | |
for (i = 0; i < maxTrades - 1; i++) { | |
tempArr += "," + tempStr; | |
} | |
tempArr += "]"; | |
let highestProfit = JSON.parse(tempArr); | |
for (i = 0; i < maxTrades; i++) { | |
for (j = 0; j < stockPrices.length; j++) { // Buy / Start | |
for (k = j; k < stockPrices.length; k++) { // Sell / End | |
if (i > 0 && j > 0 && k > 0) { | |
highestProfit[i][k] = Math.max(highestProfit[i][k], highestProfit[i - 1][k], highestProfit[i][k - 1], highestProfit[i - 1][j - 1] + stockPrices[k] - stockPrices[j]); | |
} else if (i > 0 && j > 0) { | |
highestProfit[i][k] = Math.max(highestProfit[i][k], highestProfit[i - 1][k], highestProfit[i - 1][j - 1] + stockPrices[k] - stockPrices[j]); | |
} else if (i > 0 && k > 0) { | |
highestProfit[i][k] = Math.max(highestProfit[i][k], highestProfit[i - 1][k], highestProfit[i][k - 1], stockPrices[k] - stockPrices[j]); | |
} else if (j > 0 && k > 0) { | |
highestProfit[i][k] = Math.max(highestProfit[i][k], highestProfit[i][k - 1], stockPrices[k] - stockPrices[j]); | |
} else { | |
highestProfit[i][k] = Math.max(highestProfit[i][k], stockPrices[k] - stockPrices[j]); | |
} | |
} | |
} | |
} | |
return highestProfit[maxTrades - 1][stockPrices.length - 1]; | |
} |
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
// Unique Paths in a Grid I | |
// Unique Paths in a Grid II | |
export function uniquePathsI(grid) { | |
const rightMoves = grid[0] - 1; | |
const downMoves = grid[1] - 1; | |
return Math.round(factorialDivision(rightMoves + downMoves, rightMoves) / (factorial(downMoves))); | |
} | |
function factorial(n) { | |
return factorialDivision(n, 1); | |
} | |
function factorialDivision(n, d) { | |
if (n == 0 || n == 1 || n == d) | |
return 1; | |
return factorialDivision(n - 1, d) * n; | |
} | |
export function uniquePathsII(grid, ignoreFirst = false, ignoreLast = false) { | |
const rightMoves = grid[0].length - 1; | |
const downMoves = grid.length - 1; | |
let totalPossiblePaths = Math.round(factorialDivision(rightMoves + downMoves, rightMoves) / (factorial(downMoves))); | |
for (let i = 0; i < grid.length; i++) { | |
for (let j = 0; j < grid[i].length; j++) { | |
if (grid[i][j] == 1 && (!ignoreFirst || (i != 0 || j != 0))&& (!ignoreLast || (i != grid.length - 1 || j != grid[i].length - 1))) { | |
const newArray = []; | |
for (let k = i; k < grid.length; k++) { | |
newArray.push(grid[k].slice(j, grid[i].length)); | |
} | |
let removedPaths = uniquePathsII(newArray, true, ignoreLast); | |
removedPaths *= uniquePathsI([i+1, j+1]); | |
totalPossiblePaths -= removedPaths; | |
} | |
} | |
} | |
return totalPossiblePaths; | |
} |
patryk29511's solution is a function. You'll need to call it from your main, or just rewrite the function as a main. Try copying one of the following into a .js file and running it.
Method 1: Call from main, same script
/** @param {NS} ns */
export async function main(ns) {
ns.tprint(getAllServers(ns, 'home'))
}
/** @type {NS} ns **/
export function getAllServers(ns, rootHost = 'home') {
ns.disableLog('scan')
let pendingScan = [rootHost]
const list = new Set(pendingScan)
while (pendingScan.length) {
const hostname = pendingScan.shift()
list.add(hostname)
pendingScan.push(...ns.scan(hostname))
pendingScan = pendingScan.filter(host => !list.has(host))
}
return [...list]
}
Method 2: Rewrite as main
/** @type {NS} ns **/
export async function main(ns) {
let rootHost = 'home'
ns.disableLog('scan')
let pendingScan = [rootHost]
const list = new Set(pendingScan)
while (pendingScan.length) {
const hostname = pendingScan.shift()
list.add(hostname)
pendingScan.push(...ns.scan(hostname))
pendingScan = pendingScan.filter(host => !list.has(host))
}
ns.tprint([...list])
}
Hi together,
Here is a a very simple Solution and single function valid for Unique Paths in a Grid I + II
(if you delete my comments it will be very less code ;)
/** this solution works for Unique Paths in a Grid I and II */
/** so there can be an obstacle in the grid or none, the calculation will work for both inputs */
/** input argument must be in form of ex.: [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]] or [[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,1],[0,0,0,1,0,0,0,0],[0,1,0,0,1,0,0,0]] */
export function UniquePathinGridInII(ns, InputData) {
for (let i = 0; i < InputData.length; i++) { // foreach row
for (let j = 0; j < InputData[0].length; j++) { // and foreach col in this array
// First Step: Fill all the obstacles (1) with an unused char -> here I just use a "x", which I'll need later
if (InputData[i][j] == 1) {
InputData[i][j]="x";
// BugFix 1: imagine if the very left colum or very upper row containing an obstacle, the path would never pass behind it,
// so let all the following cells behind act like there would be an obstable, too.
// In the current iteration it's just a forecast, it will be replace with the placeholder "x" in the next iteration, as well.
if (i == 0 && j < InputData[i].length - 1) InputData[i][j+1] = 1;
if (j == 0 && i < InputData.length - 1) InputData[i+1][j] = 1;
}
// Second Step: If we are at the very first row or the very first column, then we fill that cell with 1, which means this is our initial first path
else if (j == 0 || i == 0) InputData[i][j] = 1;
// At last: Calculate everything else ->
// We store the possible paths directly into the cells, thats why the first row and column are filled with 1 ;)
// The calculation itself is quite simple:
// 1. The current possible pathes to this particular current cell in this interation will be the sum of the previous uper cell and the left cell
// (because we are walking from topleft to bottomright)
// 2. If the upper or the left cell containing our obstacle-replacement-char (x), then it will just count as 0 (no path will go through an obstacle)
else InputData[i][j] = (InputData[i-1][j] == "x" ? 0 : InputData[i-1][j]) + (InputData[i][j-1] == "x" ? 0 : InputData[i][j-1]);
}
}
// for debug check print out how the grid array looks like at the end
// ns.tprintf(data);
// At the end we have a grid where all cell containing the sum of possible paths to its own position in itself
// We just need to read out the last cell (bottom/right) and that's it
// ns.tprintf("Unique pathways: " + data[data.length-1][data[0].length-1]);
return InputData[InputData.length-1][InputData[0].length-1];
}
If you are getting a fail on GenerateIPS then
replace return ips;
with return ips.toString();
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I'm using NS2 since it's likely to give me the best real world knowledge (says the developers...) and I have to admit, I don't understand the solution given by patryk29511. i copied it into a getservers.js and failed to work lol. Has an update to the game broken the script?