RoboRackers™ - Riddle by FiveThirtyEight - Solved with Javacript

Solution to the FiveThirtyEight riddle RoboRackers™ in Javascript.

The FiveThirtyEight riddle RoboRackers™ is stated as follows.

You own a start-up, RoboRackers™, that makes robots that can rack pool balls. To operate the robot, you give it a template, such as the one shown below. The template only recognizes the differences among stripes, solids and the eight ball. None of the other numbers matters.

      0        <-- Template       
     1 0                   
    0 8 1      0 = Solids     
   1 0 1 0     1 = Striped    
  0 1 1 0 1    8 = Eightball          

First, the robot randomly corrals all of the balls into the wooden triangle. From there, the robot can either swap the location of two balls or rotate the entire rack 120 degrees in either direction. The robot continues performing these operations until the balls’ formation matches the template, and it always uses the fewest number of operations possible to do so.

Using the template given above — a correct rack for a standard game of eight-ball — what is the maximum number of operations the robot would perform? What starting position would yield this? How about the average number of operations?

FiveThirtyEight, The Robot Invasion Has Come For Our Pool Halls

// [X]  1. Generate all possible start formations.
// [X]  2. Count template and start formation differences.
//         Operations = Rotations + ⌈differences /2⌉
// [X]  3. Find start formation that needs most operations.
// [X]  4. Calculate average operations / start formation.

// The template is used both as target formation and source.
const template = [
  0,
  1, 0,
  0, 8, 1,
  1, 0, 1, 0,
  0, 1, 1, 0, 1
];

// Rack rotation functions
const rotateLeft = r => [r[14], r[9], r[13], r[5], r[8], r[12], r[2], r[4], r[7], r[11], r[0], r[1], r[3], r[6], r[10]];
const rotateRight = r => [r[10], r[11], r[6], r[12], r[7], r[3], r[13], r[8], r[4], r[1], r[14], r[9], r[5], r[2], r[0]];

// Create two extra rotated templates.
// (instead of rotating every permutation)
const templates = [
  {template, rotations: 0},
  {template: rotateLeft(template), rotations: 1},
  {template: rotateRight(template), rotations: 1}
];

// Use a next lexicographical permutation algorithm to
// generate all possible start formations.
function* generatePermutations(array) {
  // Nayuki has an amazing explanation this algo.
  // https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

  let next = Array.from(array).sort();

  const nextPermutation = (array) => {

    // Reverse array to make identifying pivot
    // and successor easier.
    const reversedArray = [...array].reverse();

    // Find longest non-increasing suffix.
    const i = reversedArray.findIndex((item, index, collection) =>
        collection[index] < collection[index - 1]);

    // Exit if we are at the last permutation.
    if (i <= 0) {
      return false;
    }

    // Identify pivot.
    const pivot = reversedArray[i];

    // Find rightmost successor to pivot the suffix.
    const j = reversedArray.findIndex(item => item > pivot);

    // Identify successor and swap places.
    reversedArray[i] = reversedArray[j];
    reversedArray[j] = pivot;

    // Reverse suffix.
    const prefix = reversedArray.splice(i);
    return [...prefix.reverse(), ...reversedArray];

  };

  do {
    yield next;
    next = nextPermutation(next);
  } while (next);

}

const permutations = Array.from(generatePermutations(template));
console.log(`There are ${permutations.length} unique start formations.`);
// > There are 51480 unique start formations.


const getDifferences = (a, b) => a.reduce((memo, _, i) => {
  return memo + (b[i] !== a[i] ? 1 : 0);
}, 0);

const data = permutations.map(state => {
  // Minimum required operations is rotations + number of differences
  // between the state and the template divided by 2.
  const operations = templates.map(item =>
      Math.ceil(getDifferences(item.template, state) / 2) + item.rotations);

  return {
    // ...and it always uses the fewest number of operations possible to do so...
    operations: Math.min.apply(Math, operations),
    state
  }

});

const sorted = data.sort((a, b) => b.operations - a.operations);
const worst = sorted[0];

console.log(`Maxium required operations is ${worst.operations}.`);
// > Maxium required operations is 6.

console.log(`One of the worst starting states is ${worst.state}.`);
// > One of the worst starting states is 0,0,1,1,1,0,1,1,0,0,8,0,0,1,1.

const getAverage = (arr, key) => arr.reduce((memo, item) => memo + item[key], 0) / arr.length;
const average = getAverage(data, 'operations');

console.log(`There average required operations is ${average}.`);
// > There average required operations is 4.016860916860917.

Project Euler Problem 17 - Number Letter Counts - solved with R

Solution to the 17th Project Euler Problem - Number Letter Counts - coded and visualised with R.

The 17th Project Euler problem - Number Letter Counts - is stated as follows. If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total. If all the numbers from 1 to 1000 were written out in words, how many letters would be used?

Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

nchars.singles = nchar(c("one", "two", "three", "four", "five", "six", "seven", "eight", "nine"))
nchars.teens = nchar(c("ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"))
nchars.tens =  nchar(c("twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"))

# One, two, three...nine.
nchars.001.009 <- sum(nchars.singles)

# Ten, eleven, twelve...ninteen.
nchars.010.019 <- sum(nchars.teens)

# Twentyone, twentytwo...nintynine.
nchars.020.099 <- 10*sum(nchars.tens) + 8 * nchars.001.009

# One, two, three...ninetynine.
nchars.001.099 <- nchars.001.009 + nchars.010.019 + nchars.020.099

# When counting from 1 - 999 we will say 1-9 a hundred times each
# while quantifying hundreds.
# ONE hundred, ONE hundred and one, ONE hundred and two.
a <- nchars.001.009 * 100

# When counting from 1 - 999 we will count from 1-99 ten times.
b <- nchars.001.099 * 10

# Nine of the numbers will include just "hundred"
# One hundred, two hundred, three hundred...nine hundred.
c <- length(nchars.singles) * nchar("hundred")

# 891 (99*9) of the numbers will include "hundred and".
# One hundred and one, one hundred and two... nine hundred and ninety nine.
d <- 891 * nchar("hundredand")

# ...and finnish with One Thousand.
e <- sum(nchar("onethousand"))

sum <- a+b+c+d+e;
sprintf("Number of letters: %s", sum)

Project Euler Problem 16 - Power Digit Sum - solved with Javascript

Solution to the 16th Project Euler Problem - Power Digit Sum - in Javascript.

The 16th Project Euler problem - Power Digit Sum - is stated as follows. 215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the sum of the digits of the number 21000?

function addIntegerArrays(a = [], b = [], memo = '', carry = 0) {

    if (a.length + b.length + carry === 0) {
        return memo
    }

    // Get current number from the end of both
    const currentNumberA = a[a.length - 1] || 0;
    const currentNumberB = b[b.length - 1] || 0;

    // Sum the carry and the last digits or default to 0
    const sum = carry + currentNumberA + currentNumberB;

    const nextNumber = sum % 10;
    const nextCarry = sum > 9 ? 1 : 0;
    const nextA = a.slice(0, a.length - 1);
    const nextB = b.slice(0, b.length - 1);

    const result = `${nextNumber}${memo}`;

    return addIntegerArrays(nextA, nextB, result, nextCarry);

}

function addStrings(a, b) {
    // Convert strings to arrays.
    const preparedA = a.split('')
        .map(v => parseInt(v, 10));

    const preparedB = b.split('')
        .map(v => parseInt(v, 10));

    return addIntegerArrays(preparedA, preparedB);
}

// Create a range of length N - 1.
const result = new Array(1000 - 1).fill(0)
    // Starting at 2, hence N-1, double the value for every step.
    .reduce(memo => addStrings(memo, memo), "2")
    // Split the result into single chars.
    .split('')
    // Convert the chars to integers.
    .map(str => parseInt(str))
    // Sum the integers.
    .reduce((memo, item) => memo + item);

Project Euler Problem 15 - Lattice Paths - solved with R

Solution to the 15th Project Euler Problem coded and visualised with R.

The 15th Project Euler problem - Lattice Paths - is stated as follows. Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid?

Chinese Salty Egg

countRoutes <- function(grid.size){
  # Get the binomial coefficient i.e. the number of ways
  # of picking k unordered outcomes from n possibilities.
  k <- grid.size
  n <- k*2
  result <- factorial(n) / (factorial(k)*factorial(n-k))
  return(result)
}

# Call the device driver.
png(file="graph.png",width=1080,height=1080,res=120)

# Set margins.
par(mar=c(5,3,3,3))

# Create a range from 1 to 20 for the x axis.
x <- c(1:20)

# Map the range using the countRoutes function.
y <- countRoutes(x)

# Plot the graph without axes and annotations.
plot(y, type="o", col="blue", axes=FALSE, ann=FALSE, pch=16)

# Draw a box around the plot.
box()

# Add gridd lines.
abline(h=tail(y,3), v=x, col="gray", lty=3)

# Add labels for the last three markers.
text(tail(x,3),tail(y,3),labels=tail(y,3), pos=2)

# Add the X axis.
axis(1, at=x)

# Add a title for the x axis.
title(xlab= "Lattice Grid Size")

# End call to device driver.
dev.off()

Finding the 10001st prime with R

Solution to the seventh Project Euler problem – 10001st prime - in R.

The seventh Project Euler problem - 10001st prime - is stated as follows. By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?

isPrime <- function(n) {
  if (n == 2 || n == 3) {
    # Handle the edge cases 2 and 3.
    return(TRUE)
  } else if (n < 2 || n %% 2 == 0) {
    # Check if n is less than 2 or equal to a multiple of 2.
    return(FALSE)
  } else {
    # Factors come in pairs and one of the factors has
    # to be smaller than the square root of N.
    upper.limit <- floor(sqrt(n))
    range <- seq(3, upper.limit)

    # Check if N is divisible
    d <- n %% (range)

    # PRIME = Nothing in range is divisble by N.
    # NOT PRIME = Something in range is divisible by N.
    return(! 0%in%d)
  }
}

# Init target prime, a counter and an empty vector.
target <- 10001
current <- 1
primes <- c()

# Find primes untill we have TARGET primes.
while (length(primes) < target) {
  primes = if (isPrime(current)) c(primes, current) else primes
  current = current + 1
}

# Print the prime we are looking for.
sprintf("The %sth prime is %s", target, primes[target])