BitBurner Contract Solvers

README.md

All of the scripts for contracts in Bitburner.

autoSolver.js

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;
}

generateIps.js

// 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;
} 

greatestPrimeFactor.js

// 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;
}

mergeOverlap.js

// 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;
}

solveTriangleSum.js

// 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);
}

spiral.js

// 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;
}

stockSolver.js

// 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];
}

uniquePaths.js

// 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;
}

Maybe a stupid question but where do I find getServers.js??

I would also like to know where to find getServers.js

That code is long lost but all it did was recursively find every server it could. Get Outlook for Android<https://aka.ms/AAb9ysg>

…

________________________________ From: Aaron Burton ***@***.***> Sent: Tuesday, December 28, 2021 9:02:29 AM To: OrangeDrangon ***@***.***> Cc: Kyle Rosenberg ***@***.***>; Author ***@***.***> Subject: Re: OrangeDrangon/README.md @AaronABurton1 commented on this gist.

________________________________ I would also like to know where to find getServers.js — Reply to this email directly, view it on GitHub<https://gist.github.com/8a08d2d7d425fddd2558e1c0c5fae78b#gistcomment-4009854>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AGB2A7LXHOHEEX532IGIGL3UTG7PLANCNFSM5KUV5OYA>. You are receiving this because you authored the thread.Message ID: ***@***.***>

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();