All of the scripts for contracts in Bitburner.
-
-
Save OrangeDrangon/8a08d2d7d425fddd2558e1c0c5fae78b to your computer and use it in GitHub Desktop.
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; | |
} |
// 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; | |
} |
// 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; | |
} |
// 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; | |
} |
// 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); | |
} |
// 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; | |
} |
// 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]; | |
} |
// 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; | |
} |
I would also like to know where to find getServers.js
getServers.js
/** @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]
}
Just a note on the primeFactor function:
export function factor(num) {
for (let div = 2; div <= Math.sqrt(num); div++) {
if (num % div != 0) {
continue;
}
num = num / div;
div = 2;
}
return num;
}
Setting div to 2 near the end restarts the loop at three instead of two. So for answers that need to check for 2 more than once (example: 685704772) it generates an incorrect answer. Setting div to 1 instead of 2 solves this issue.
Otherwise, LOVE this script. Thanks!
Good catch
Is there a solution available for the Array Jumping Game or the Subarray with Maximum Sum?
@cullumar here you go
Jumping game
// Array jumping game solver
/** @param {NS} ns **/
export async function main(ns) {
// const data = [] // false
// const data = [0] // false
// const data = [1] // true
// const data = [1,0,1] // false
// const data = [1,1,1] // true
// const data = [1,2,0,3]; // true
// const data = [0,9,6,6,5,5,5,5,0,0,3,1,5,5,9,0,8,5,0,8,8,2,0]
// const data = [0,9,0,7,4,0]
const data = [1,0,7,4,8,8,0,0,8,0,4,0,10,10,0,0,9,6,0,6,6,0,3,0]
ns.tprint(JSON.stringify(solveJump(ns, data)));
}
export function solveJump(ns, data) {
// ns.tprint(JSON.stringify(data))
for(let i=data[0]-1;i>-1;i--) {
if (i+1 >= data.length) return true;
return solveJump(data.slice(i+1))
}
return false;
}
Greatest sum of subarray
// maximum subarray sum solution
/** @param {NS} ns **/
export async function main(ns) {
//const array = [-7,3,-9,6,8,-8,-10,9,5,6,-10,-3,-2,10,-2,1,-6,-4,0,9,3,3,4,-7,-2,-8,4,4,3,-9,2];
const array = [7,4,3,10,-5,9,1,-1,6,-4,6,-7,3,-2,3,10];
// const array = [-9,7,-1,6,7];
ns.tprint(`maxsum: ${solveSum(ns, array)}`);
}
export function solveSum(ns, data) {
const arrLength = data.length;
let maxSum = -Infinity;
for (let i=0; i<arrLength; i++) {
const sub = data.slice(0, i+1);
for (let j = 0; j < sub.length; j++) {
const sub2 = sub.slice(j, sub.length);
// ns.tprint(`i ${i} j ${j} ${JSON.stringify(sub)} ${JSON.stringify(sub2)}`);
const sum = sub2.reduce((prev, cur) => prev += cur, 0);
if ( sum > maxSum ) maxSum = sum;
// ns.tprint(`${sum}: ${sub2}`);
}
}
return maxSum;
}
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?
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();
Maybe a stupid question but where do I find getServers.js??