Apr 03, 2017

(I think) this level was all about math operations. It was very entertaining and I definitely learned something new about JavaScript, memoization. Want to codefight?

Least Factorial (300/300)

Given an integer n, find the minimal k such that

  • k = m! (where m! = 1 * 2 * ... * m) for some integer m;
  • k >= n.

In other words, find the smallest factorial which is not less than n.

JavaScript

function leastFactorial(n) {
    var result = -1;
    var counter = 1;
    while(result < 0 ){
       var k = factorial_namespace.factorial(counter);
        ++counter;
        if(k>=n)
            result = k;
    }
    return result;    
}

var factorial_namespace = { 

    f : [], // memoization ... https://en.wikipedia.org/wiki/Memoization
            // store recursive result in variable to speed up the function
    factorial : function (n) {
                  if (n == 0 || n == 1)
                    return 1;
                  if (factorial_namespace.f[n] > 0)
                    return factorial_namespace.f[n];
                  return factorial_namespace.f[n] = factorial_namespace.factorial(n-1) * n;
                } 

};

Count Sum of Two Representations 2 (300/300)

Given integers nl and r, find the number of ways to represent n as a sum of two integers A and B such that l ≤ A ≤ B ≤ r.

JavaScript

function countSumOfTwoRepresentations2(n, l, r) {
    var representations = 0;
    //Only travel the loop until n/2 , because l+r will never equal n
    // if l or r > n/2
    var limit = Math.floor(n/2);
    for(var i=l; i<=r && i<=limit; ++i){
        for(var j=i;j<=r;++j){ 
            if(i+j == n){
                ++representations;
                break; 
            }
        }
    }
    return representations;
}

Magical Well (300/300)

You are standing at a magical well. It has two positive integers written on it: a and b. Each time you cast a magic marble into the well, it gives you a * b dollars and then both a and bincrease by 1. You have n magic marbles. How much money will you make?

function magicalWell(a, b, n) {
    var money = 0;
    while(n>0){
        money += a*b;
        ++a, ++b;
        --n;
    }
    return money;
}

Lineup (300/300)

To prepare his students for an upcoming game, the sports coach decides to try some new training drills. To begin with, he lines them up and starts with the following warm-up exercise: when the coach says 'L', he instructs the students to turn to the left. Alternatively, when he says 'R', they should turn to the right. Finally, when the coach says 'A', the students should turn around.

Unfortunately some students (not all of them, but at least one) can't tell left from right, meaning they always turn right when they hear 'L' and left when they hear 'R'. The coach wants to know how many times the students end up facing the same direction.

Given the list of commands the coach has given, count the number of such commands after which the students will be facing the same direction.

JavaScript

function lineUp(commands) {
    var cmds = {L: -1, R: 1, A:0}; //Command numerical values
    var limit = commands.length;
    var everyone = confused = cmds.A; //Everyone starts at the same position
    var matches = 0;
    for(var i=0; i<limit; ++i){
        var command = commands[i];
        everyone = (everyone + cmds[command]) % 2;
        confused = ( confused + (cmds[command]*-1) ) % 2; //Confused does the opposite by *-1
        if(everyone == confused)
            ++matches;
    }
    return matches;
}

Addition Without Carrying (300/300)

A little boy is studying arithmetics. He has just learned how to add two integers, written one below another, column by column. But he always forgets about the important part - carrying.

Given two integers, find the result which the little boy will get.

Note: the boy used this site as the source of knowledge, feel free to check it out too if you are not familiar with column addition.

JavaScript

function additionWithoutCarrying(param1, param2) {
    var max_min = getMaxMin(param1, param2);
    param1 = max_min.max;
    param2 = max_min.min;
    var result = '';
   
    while(param2 > 0){
        //Pop last digits and add, if > 10, pop last digit again
        result = ( (param1%10 + param2%10) % 10 ) + result; 
        param1 = Math.floor(param1/10);
        param2 = Math.floor(param2/10);
    }

    if(param1>0)
        result = param1 + result;
    
    if(result == '') //param1==param2==0
        result = 0;
    
    return parseInt(result);
}

function getMaxMin(a,b){
    return {max: Math.max(a,b) , min: Math.min(a,b)};
}

Apple Boxes (300/300)

There're k square apple boxes full of apples. If a box is of size m, then it contains m × mapples. You noticed two interesting properties about the boxes:

  1. The smallest box is of size 1, the next one is of size 2,..., all the way up to size k.
  2. Boxes that have an odd size contain only yellow apples. Boxes that have an even size contain only red apples.

Your task is to calculate the difference between the number of red apples and the number of yellow apples.

JavaScript

function appleBoxes(k) {
    var red_apples = Math.floor(k/2);
    var yellow_apples = Math.ceil(k/2);
    return sumEvenSquares(red_apples) - sumOddSquares(yellow_apples);
}

// sum of even squares: 2n(n+1)(2n+1) / 3
// n = total number of evens to add
function sumEvenSquares(n){
    return ( 2*n*(n+1)*(2*n+1) ) / 3;
}

// sum of odd squares: n(2n-1)(2n+1) / 3
// n = total number of odds to add
function sumOddSquares(n){
    return ( n*(2*n-1)*(2*n+1) ) / 3;
}

Increase Number Roundness(300/300)

Define an integer's roundness as the number of trailing zeroes in it.

Given an integer n, check if it's possible to increase n's roundness by swapping some pair of its digits.

/*
    Hindsight: I am obtaning way more information than necessary to solve the problem. All that was eally needed was to find the first 0 from left to right, and then figure out if there was a digit != 0 after that found digit. This could easily be done with a regex expression.
*/
function increaseNumberRoundness(n) {
    n = n+'';
    var limit = n.length;
    var middle = Math.ceil((limit-1)/2); // Middle must be -1 from limit, because in aray pos it goes from
    var roundness = 0;                  // 0 ... (n-1)
    // Loop from middle to 0 with l_i
    // when swapable digit found then loop from middle to limit with r_i for 
    // swapable pair    
    for(var l_i = middle, r_i = middle+1; l_i >= 0 && r_i < limit; --l_i){
        if(n[l_i] == 0){ //Swapable digit found
            for( /*no need to set r_i*/; r_i < limit;++r_i){
                if(n[r_i] != 0){ //Swapable pair found
                    ++roundness;
                    break;
                }
            }
        }
    }
    return roundness > 0;
}

Rounders (300/300)

We want to turn the given integer into a number that has only one non-zero digit using a tail rounding approach. This means that at each step we take the last non 0 digit of the number and round it to 0 or to 10. If it's less than 5 we round it to 0 if it's larger than or equal to 5we round it to 10 (rounding to 10 means increasing the next significant digit by 1). The process stops immediately once there is only one non-zero digit left.

JavaScript

function rounders(value) {
    var pop, current_pop, carry, digit, value_diff;
    pop = 10;
    current_pop = pop/10; //Because current digi is #0, which is pop minus a 0
    carry = 0;
    
    while(value%pop != value){ //Reached the first digit of value
        // To get the digit one must remove the trailing 0's which are pop minus a 0 (pop/10)
        digit = (value % pop) / current_pop;
        carry = digit + carry >= 5 ? 1 : 0;
        //Update current value from popped digits. The digit must correspond to its decimal position
        value -= digit*current_pop;
        pop*=10;
        current_pop = pop/10;
    }
    
    return value + (carry*current_pop);
}

 

Candles (300/300)

When a candle finishes burning it leaves a leftover. makeNew leftovers can be combined to make a new candle, which, when burning down, will in turn leave another leftover.

You have candlesNumber candles in your possession. What's the total number of candles you can burn, assuming that you create new candles as soon as you have enough leftovers?

JavaScript

function candles(candlesNumber, makeNew) {
    var burnt = to_burn = leftovers = candlesNumber;
    while(leftovers>=makeNew){
        to_burn = Math.floor(leftovers/makeNew);
        burnt += to_burn;
        leftovers = to_burn +(leftovers - to_burn*makeNew);
    }
    return burnt;
}

Count Black Cells (300/300)

Imagine a white rectangular grid of n rows and m columns divided into two parts by a diagonal line running from the upper left to the lower right corner. Now let's paint the grid in two colors according to the following rules:

  • A cell is painted black if it has at least one point in common with the diagonal;
  • Otherwise, a cell is painted white.

Count the number of cells painted black.

JavaScript

function countBlackCells(n, m) { 
   // Formula from: http://math.stackexchange.com/questions/1121541/number-of-unit-squares-that-meet-a-given-diagonal-line-segment-in-more-than-one
   // have to add (gcd(m,n)-1)*2 b/c codefight counts a point of intersection as the two squares that
   // meet on that point
   // formula --> m + n - gcd(m,n) + (gcd(m,n)-1)*2
   // now simplify it
   return m + n + gcd(m,n) - 2;
}

//greatest common divisor
function gcd(a, b){
    var limit = Math.max(a,b);
    var current_div = divisor = 1;
    while(current_div <= limit){
        ++current_div;
        if(a%current_div == 0 && b%current_div == 0)
            divisor = current_div;
    }
    return divisor;
}