Project Euler

p12.js

function divisibleTriangleNumber(n) {
  let start = 1;
  let inc = 2;

  function numOfDivisors(x) {
    if (x == 1) return 1;
    let res = 0;
    for (var i = 1; i <= Math.sqrt(x); i++) {
      if (x % i == 0 && x / i !== i) {
        res += 2;
      } else if (x % i == 0) {
        res += 1;
      }
    }
    return res; //这行一开始写到上面的 for 里面了，导致出问题
  }

  let d = numOfDivisors(start);
  while (d < n) {
    start += inc;
    inc++;
    //console.log([start, inc]);
    d = numOfDivisors(start);
  }

  return start;
}

p13.js

function largeSum(arr) {
  function firstN(n, str) {
    return str.slice(0,n);
  }
  function first13(str) {
    return firstN(13, str);
  }

  let shortArr = arr.map((e) => {return first13(e);});
  let res = shortArr.map((e) => {return Number(e);}).reduce((acc, cur) => {return acc + cur;});
  
  return Number(String(res).slice(0,10));
}

p14.js

function longestCollatzSequence(limit) {
  let s = 1;
  let mem = {'1': 1};
  let longest = [1, 1]

  function getCollatzSequenceLength(n, m, c = 0, b = 0) {
    // for a number n, return the length of its Collatz Sequence
    if (n == 1) return c + 1;
    if (c == 0) b = n;

    let step;
    if (n % 2 == 0) {
      step = n / 2;
    } else {
      step = n * 3 + 1;
    }
    c++;

    if (m[String(step)] != undefined) {
      m[String(b)] = c + m[String(step)];
      return c + m[String(step)];
    } else {
      return getCollatzSequenceLength(step, m, c, b);
    }
  }

  while (s <= limit) {
    let l = getCollatzSequenceLength(s, mem);
    if (l >= longest[1]) {
      longest[0] = s;
      longest[1] = l;
    }
    s++;
  }
  return longest[0];
}

p15.js

function latticePaths(gridSize) {
  function factorial (n, acc = 1) {
    if (n == 1) return acc;
    return factorial(n - 1, acc * n);
  }

  function permutation (n, r) {
    return factorial(n) / factorial(n-r);
  }
  
  let steps = gridSize * 2;
  
  return Math.trunc(permutation(steps, gridSize) / factorial(gridSize));
}

p16.js

function powerDigitSum(exponent) {
  function stringDouble(s) {
    let digits = s.split('');
    let inc = 0;
    let res = '';
    for (let i = digits.length - 1; i >= 0; i--) {
      let sum = Number(digits[i]) * 2 + inc;
      if (sum >= 10) {
        inc = 1;
      } else {
        inc = 0;
      }
      res = String(sum % 10) + res;
    }
    return String(inc) + res;
  }

  let longnum = '1';
  for (let i = 0; i < exponent; i++) {
    longnum = stringDouble(longnum);
  }

  let arr = longnum.split('');
  return arr.reduce((acc, cur) => {return acc + Number(cur);},0);
}

p17.js

function numberLetterCounts(limit) {
  function numToString(n) {
    let tillTwenty = ['', 'one', 'two', 'three', 'four', 'five',
    'six', 'seven', 'eight', 'nine', 'ten', 'eleven', 'twelve',
    'thirteen', 'fourteen', 'fifteen', 'sixteen', 'seventeen',
    'eighteen', 'nineteen'];
    let tees = ['', '', 'twenty', 'thirty', 'forty', 'fifty',
       'sixty', 'seventy', 'eighty', 'ninety'];
    let thousands = Math.trunc(n / 1000);
    let hundreds = Math.trunc((n - 1000 * thousands) / 100);
    let scores = n % 100;
    let res = ""

    if (thousands > 0) res += tillTwenty[thousands] + "thousand";
    if (hundreds > 0) res += tillTwenty[hundreds] + "hundred";
    if (scores > 0 && scores <= 19) {
      if (hundreds > 0) {
        res += "and" + tillTwenty[scores];
      } else {
        res += tillTwenty[scores];
      }
    } else if (scores > 0) {
      let tens = (scores - scores % 10) / 10;
      let ones = Math.trunc(scores - tens * 10)
      if (hundreds > 0) {
        res += "and" + tees[tens] + tillTwenty[ones];
      } else  {
        res += tees[tens] + tillTwenty[ones];
      }
    }
    console.log(res);
    return res.length;
  }

  let t = 0;
  let i = 1;
  while (i <= limit) {
    t += numToString(i);
    i++;
  }
  
  return t;
}

p18.js

function maximumPathSumI(triangle) {
  let triangleCopy = triangle.map((row) => {return [...row]});

  for (let i = triangle.length - 2; i >= 0; i--) {
    for (let j = 0; j < i + 1; j++) {
      triangleCopy[i][j] += Math.max(triangleCopy[i+1][j], 
      triangleCopy[i+1][j+1]);
    }
  }
  console.log(triangleCopy);
  return triangleCopy[0][0];
}

p19.js

// pass on 2nd try after trivial editing :smirk:

function countingSundays(firstYear, lastYear) {
  function daysSinceFirstSunday (year) {
    let years = year - 1900;
    let res = 0;
    if (years == 0) return res;
    if (years == 1) return 359;
    for (let i = 2; i <= years; i++) {
      if (i % 4 != 0) {
        res += 365;
      } else {
        res += 366;
      }
    }
    res += 359;
    return res;
  };

  function firsts (fy, ly) {
    let res = [];
    let last = 0;
    for (let i = fy; i <= ly; i++) {
      if (res.length == 0) {
        last = 0;
      } else {
        last = res[res.length - 1] + 31;
      }
      if (i % 4 != 0) {
        var yearFirsts = [0,31,59,90,120,151,181,212,243,273,304,334].map((e) => {return e + last;});
      } else {
        yearFirsts = [0,31,60,91,121,152,182,213,244,274,305,335].map((e) => {return e + last;});
      }
      res = res.concat(yearFirsts);
    }
    return res;
  }

  let jan1stDay = daysSinceFirstSunday(firstYear) % 7;
  let sundaysOnFirsts = firsts(firstYear, lastYear).filter((e) => {return (e + jan1stDay) % 7 == 0;}); 

  return sundaysOnFirsts.length;
}

p20.js

function sumFactorialDigits(n) {
  let digits = ['1'];
  let arrayTimesN = (arr, x) => {
    let res = [];
    let tens = 0;
    while (arr.length > 0) {
      let product = Number(arr.pop()) * x;
      res.unshift(String(product + tens)[String(product + tens).length - 1]);
      if (String(product + tens).length > 1) {
        tens = Number(String(product + tens)[0]);
      } else {
        tens = 0;
      }
    }
    if (tens != 0) res.unshift(String(tens));
    return res;
  }

  let arrayCascade = (... arrs) => {
    let padding = [];
    let tens = 0;
    // 整理数列，加上必要的‘0’
    for (let i = arrs.length - 1; i >= 0; i--) {
      arrs[i] = arrs[i].concat(padding);
      padding.push('0');
    }

    let longest = Math.max(...arrs.map((e) => { return e.length }));
    for (let i = 0; i < arrs.length; i++) {
      if (arrs[i].length < longest) {
        arrs[i] = Array(longest - arrs[i].length).fill('0').concat(arrs[i]);
      }
    }
    // console.log("arrs:", arrs)

    // 逐位相加，再逐数列相加
    for (let i = arrs.length - 1; i > 0; i--) {
      for (let j = arrs[i].length - 1; j >= 0; j--) {
        let a = Number(arrs[i][j]);
        let b;
        if (arrs[i-1][j] != undefined) {
          b = Number(arrs[i-1][j]);
        } else {
          b = 0;
        }
        let sum = String(tens + a + b);
        // console.log("tens:", tens, "i:", i, "j:", j, "a:", a, "b:", b, "sum:", sum);
        if (sum.length > 1) {
          tens = Number(sum[0]);
          arrs[i-1][j] = sum[1];
        } else {
          tens = 0;
          arrs[i-1][j] = sum[0];
        }
      }
      if (tens != 0) {
        arrs[i-1].unshift(String(tens));
      }
    }
    // console.log("arrs[0]:", arrs[0]);
    return arrs[0];
  }

  for (let i = 2; i <= n; i++) {
    let m = [];
    for (let j = 0; j < String(i).length; j++) {
      m[j] = digits.map((e) => { return e; });
    }
    //console.log("m:", m);
    digits = arrayCascade(... String(i).split('').map((e, ind) => {
      return arrayTimesN(m[ind], Number(e));
    }));
  }

  return digits.reduce((acc, cur) => { return acc + Number(cur); }, 0);
}

p21.js

function sumAmicableNum(n) {
  let res = 0;
  for (let i = 1; i <= n; i++) {
    let am = findAmicableNum(i);
    if (am != 0) {
      res += i + am; 
    }
  }
  return res;
}

function findDivisors(x) {
  let res = [];
  for (let i = 2; i <= Math.sqrt(x); i++) {
    if (x % i == 0) {
      res.push(i);
      res.push(x / i);
    }
  }
  res.unshift(1);
  return res;
}

function findAmicableNum(x) {
  let dx = findDivisors(x).reduce((acc, cur) => {return acc + cur;});
  if (x == findDivisors(dx).reduce(
    (acc, cur) => { return acc + cur;}) && dx > x) {
    return dx;
  } else {
    return 0;
  }
}

p22.js

function namesScores(arr) {
  let ns = arr.sort().map((str) => {
    let val = 0;
    for (let i = 0; i < str.length; i++) {
      val += str.charCodeAt(i) - 64;
    }
    return val;
  });

  let res = ns.reduce((acc, cur, index) => {
    return acc + cur * (index + 1);
  });

  return res;
}

// Only change code above this line
const test1 = ['THIS', 'IS', 'ONLY', 'A', 'TEST'];
const test2 = ['I', 'REPEAT', 'THIS', 'IS', 'ONLY', 'A', 'TEST'];

namesScores(test1);

p23.js

function sumOfNonAbundantNumbers(n) {
  let aN = abundantNums(n);
  let nANum = Array(n).fill(0).map((_, ind) => {return ind + 1;});
  for (let i = 0; i < aN.length; i++) {
    for (let j = 0; j < aN.length; j++) {
      let sANum = aN[i] + aN[j];
      if (sANum <= n) {
        nANum[sANum - 1] = 0;
      }
    }
  }

  console.log(nANum);
  let sum = nANum.reduce((cur, acc) => {return cur + acc;});
  
  return sum;
}

function isAbundant(n) {
  let sum = 0;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0) {
      sum += i;
      if (i * i != n) {
        sum += (n / i);
      }
    }
  }
  sum += 1;
  return sum > n;
}

function abundantNums(n) {
  return Array(n).fill(0).map((_, ind) => {return ind + 1;}).filter((e) => isAbundant(e));  
}

p24.js

function lexicographicPermutations(n) {
  let nsOfPermutations = [362880,40320,5040,720,120,24,6,2,1];
  let resArray = [];
  let digits = [0,1,2,3,4,5,6,7,8,9]

  for (let i = 0; i < 10; i++) {
    let digit = digits[Math.floor(n / nsOfPermutations[i])] || digits[0];
    resArray.push(digit);
    digits = knockoutFromArray(digits, digit);
    n = n % nsOfPermutations[i];
  }
  
  return Number(resArray.join(''));
}

function knockoutFromArray(ns, n) {
  let ind = ns.indexOf(n);
  return ns.toSpliced(ind, 1);
}

p25.js

var m = [];

function digitAdd(n1, n2) {
  let res = [];
  let overflow = 0;

  let diffLen = n1.length - n2.length;
  if (diffLen < 0) n1 = Array(diffLen).fill('0').concat(n1);
  if (diffLen > 0) n2 = Array(diffLen).fill('0').concat(n2);

  let len = n1.length;
  for (let i = len - 1; i >= 0; i--) {
    let sum = Number(n1[i]) + Number(n2[i]) + overflow;
    overflow = Math.floor(sum / 10);
    res.unshift(String(sum % 10));
  };

  if (overflow != 0) res.unshift(String(overflow));
  return res;
}

function digitFib(n, m) {
  if (m[n] !== undefined) return m[n];
  if (n == 1) {
    m[n] = '1';
    return '1';
  } else if (n == 0) {
    m[n] = '0';
    return '0';
  } else {
    m[n] = digitAdd(digitFib(n-1,m), digitFib(n-2,m));
    return m[n]
  };
};

function digitFibonacci(n) {
  let a = 1;
  while (true) {
    let ds = digitFib(a, m);
    if (ds.length == n) break;
    a++;
  }

  return a;
}