////////// Exercice 1 ////////// function makeSecretCypher(key) { function encode(str) { return cypher(str, key); // in fact, we return hiddenCypher of previous question } return encode; } const enc = makeSecretCypher(7); console.log(enc('hello world')); // -> 'olssv dvysk' // computes a pair of functions [encode, decode] that // are parameterized by `key`, serve to encode and // decode strings, and are inverse of each other function makeCypher(key) { function encode(str) { return cypher(str, key); } function decode(str) { return cypher(str, -key); } return [encode, decode]; } let [enc, dec] = makeCypher(7); console.log(enc('hello world')); // -> 'olssv dvysk' console.log(dec('olssv dvysk')); // -> 'hello world' ////////// Exercice 2 ////////// // computes the greatest common divisor of a and b // pre: a and b are positive or zero function pgcd (a, b) { if (b === 0) return a; else return pgcd (b, a % b); } console.log(pgcd(32, 24)); // -> 8 console.log(pgcd(4, 2)); // -> 2 console.log(pgcd(2, 4)); // -> 2 ////////// Exercice 3 ////////// // Computes the sum of the integers ranging from a to b // pre: a and positive or zero function sumInteger(a, b) { if (b < a) return 0; else return a + sumInteger(a + 1, b); } console.log(sumInteger(1, 5)); // -> 15 console.log(sumInteger(5, 1)); // -> 0 // Computes the sum of the squares ranging from a to b // pre: a and positive or zero function sumSquares(a, b) { if (b < a) return 0; else return a * a + sumSquares(a + 1, b); } console.log(sumSquares(1, 5)); // -> 55 console.log(sumSquares(5, 1)); // -> 0 function sumGeneric(a, b, f) { if (b < a) return 0; else return f(a) + sumGeneric(a + 1, b, f); } // With a named function function square(x) { return x*x; } console.log(sumGeneric(1, 5, square)); // -> 55 // With an anonymous function console.log(sumGeneric(1, 500, function(x){return 1 / (x*x);})); // -> 1.64293 ////////// Exercice 4 ////////// // computes x^n // pre: n integer positive or zero function powerLinear(x, n) { if (n === 0) return 1; else return x * powerLinear (x, n - 1); } console.log(powerLinear(2, 3)); // -> 8 // computes x^n using log approach // pre: n integer positive or zero function powerLogarithmic(x, n) { if (n === 0) { return 1; } else if (n % 2 === 0) { // n is even let val = powerLogarithmic (x, n / 2); return val * val; } else // n is odd return x * powerLogarithmic (x, n - 1); } console.log(powerLogarithmic(2, 5)); // -> 32 ////////// Exercice 5 ////////// // computes the length of the Syracuses's sequence function syracuse(n) { if (n === 1) return 0 else if (n%2 === 0) return 1 + syracuse(n/2); else return 1 + syracuse(1+3*n); } console.log(`syracuse(${7}) : ${syracuse(7)}`); // --> 16 console.log(`The first 4 lengths : ${[1,2,3,4].map(syracuse)}`); // -> [ 0, 1, 7, 2 ] // the same function in a tail-recursive manner (as an example) function syracuseTailRec(n) { function syracuseInternal(p, acc) { if (p === 1) return acc else if (p%2 === 0) return syracuseInternal(p/2, acc+1); else return syracuseInternal(1 + 3*p, acc+1); } return syracuseInternal(n, 0); } console.log(`syracuseTailRec(${7}) : ${syracuseTailRec(7)}`); // --> 16 console.log(`The first 4 lengths : ${[1,2,3,4].map(syracuseTailRec)}`); // -> [ 0, 1, 7, 2 ] ////////// Exercice 6 ////////// // converts the integer `num` as a string in base `base` // (version until base 9, recursive) function convert2Base (num, base) { if (num === 0) return ''; else { const head = convert2Base(Math.floor(num / base), base); const tail = `${num % base}`; return head + tail; } } console.log(convert2Base(666, 2)); // 1010011010 console.log(convert2Base(666, 3)); // 220200 // converts the integer `num` as a string in base `base` // (version until base 35, recursive) function convert2BaseFull (num, base) { if (num === 0) return ''; else { const head = convert2BaseFull(Math.floor(num / base), base); const digit = (num % base); let tail = ''; const initCode = 'A'.charCodeAt(0); // shift to reach the correct code value if (digit < 10) tail = digit.toString(); else tail = String.fromCharCode(digit - 10 + initCode); return head + tail; } } console.log(convert2BaseFull(666, 2)); // 1010011010 console.log(convert2BaseFull(666, 16)); // 666 = 2*16^2 + 9*16+10 = 29A in base 16 // converts the string `nums` in base `base` into a base-10 integer function convert2Int (nums, base) { const len = nums.length; if (len === 0) return 0; else return parseInt(nums.substring(len - 1, len), base) + convert2Int(nums.substring(0, len - 1), base) * base; } console.log(convert2Int('1010011010', 2)); // 666 console.log(convert2Int('220200', 3)); // 666 // check that the functions are inverse from each other console.log(convert2Int(convert2Base(123456, 3), 3)); // 123456 (identity) ////////// Exercice 7 ////////// // computes a boolean telling if `str` is a palindrome // (indeed, with an 'e' at the end) function isPalindrome(str) { const len = str.length; if (len <= 1) return true; else return (str[0] === str[len - 1]) && (isPalindrome(str.substring(1, len - 1))); } console.log(isPalindrome('')); // -> true console.log(isPalindrome('a')); // -> true console.log(isPalindrome('abba')); // -> true console.log(isPalindrome('able was I,I saw elba')); // -> true console.log(!isPalindrome('not a palindrome?')); // -> true // computes a boolean telling if `str1` is an anagram // (without an 'e' at the end this time) of `str2` function isAnagram( str1, str2) { if (str1.length !== str2.length) return false; else if (str1.length === 0) return true; else { const headStr1 = str1[0]; const tailStr1 = str1.substring(1, str1.length); const remainStr2 = str2.replace(headStr1,''); return str2.includes(headStr1) && isAnagram(tailStr1, remainStr2); } } console.log(isAnagram('','')); // -> true console.log(!isAnagram('','OK')); // -> true console.log(!isAnagram('OK','')); // -> true console.log(!isAnagram('abcdde','abcdd')); // -> true console.log(isAnagram('algorithme','logarithme')); // -> true console.log(isAnagram('abcdde','ddcbae')); // -> true console.log(!isAnagram('abcdde','abcdee')); // -> true console.log(isAnagram('imaginer','migraine')); // -> true console.log(!isAnagram('c est quoi','une anagramme au fait?')); // -> true