////////// Exercice 1 ////////// function makeSecretCypher(key) { function encode(str) { return cypherCaesar(str, key); // in fact, we return hiddenCypher of previous question } return encode; } const enc1 = makeSecretCypher(7); console.log(`enc1('hello world') = ${enc1('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 cypherCaesar(str, key); } function decode(str) { return cypherCaesar(str, -key); } return [encode, decode]; } let [enc2, dec2] = makeCypher(7); console.log(`enc2('hello world') = ${enc2('hello world')}`); // -> 'olssv dvysk' console.log(`dec2('olssv dvysk') = ${dec2('olssv dvysk')}`); // -> 'hello world' ////////// Exercice 2 ////////// // Computes the greatest common divisor of `a` and `b` // Precond : `a` and `b` are non-negative function pgcd (a, b) { if (b === 0) return a; else return pgcd (b, a % b); } console.log(`pgcd(32, 24) = ${pgcd(32, 24)}`); // -> 8 console.log(`pgcd(4, 2) = ${pgcd(4, 2)}`); // -> 2 console.log(`pgcd(2, 4) = ${pgcd(2, 4)}`); // -> 2 ////////// Exercice 3 ////////// // Computes the sum of the integers ranging from `a` to `b` // Precond : `a` and `b` are non negative function sumInteger(a, b) { if (b < a) return 0; else return a + sumInteger(a + 1, b); } console.log(`sumInteger(1, 5) = ${sumInteger(1, 5)}`); // -> 15 console.log(`sumInteger(5, 1) = ${sumInteger(5, 1)}`); // -> 0 // Computes the sum of the squares ranging from `a` to `b` // Precond : `a` and `b` are non negative function sumSquares(a, b) { if (b < a) return 0; else return a * a + sumSquares(a + 1, b); } console.log(`sumSquares(1, 5) = ${sumSquares(1, 5)}`); // -> 55 console.log(`sumSquares(5, 1) = ${sumSquares(5, 1)}`); // -> 0 // Computes the sum of the f(x) for x ranging from `a` to `b` // Precond : `a` and `b` are non negative 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; } const res1 = sumGeneric(1, 5, square); console.log(`sumGeneric(1, 5, square) = ${res1}`); // -> 55 // With an anonymous function const res2 = sumGeneric(1, 500, (x) => 1 / (x*x)); console.log(`sumGeneric(1, 500, (x) => 1 / (x*x)) = ${res2}`); // -> 1.64293 ////////// Exercice 4 ////////// // Computes x^n // Precond : `n` is a non-negative integer function powerLinear(x, n) { if (n === 0) return 1; else return x * powerLinear (x, n - 1); } console.log(`powerLinear(2, 3) = ${powerLinear(2, 3)}`); // -> 8 // computes x^n using log approach // Precond : `n` is a non-negative integer 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) = ${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(`First 4 values of syracuse : ${[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(`First 4 values of syracuseTR : ${[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(0, 2) = ${convert2Base(0, 2)}`); // '' console.log(`convert2Base(666, 2) = ${convert2Base(666, 2)}`); // '1010011010' console.log(`convert2Base(666, 3) = ${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(0, 2) = ${convert2BaseFull(0, 2)}`); // '' console.log(`convert2BaseFull(666, 2) = ${convert2BaseFull(666, 2)}`); // '1010011010' console.log(`convert2BaseFull(666, 16) = ${convert2BaseFull(666, 16)}`); // '29A' // 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) = ${convert2Int('1010011010', 2)}`); // 666 console.log(`convert2Int('220200', 3) = ${convert2Int('220200', 3)}`); // 666 // Check that the functions are inverse from each other [ [ 1234, 9 ], [ 123456, 3 ], ].forEach((params) => { console.log(`convert2Int(convert2Base(${params[0]}, ${params[1]}), ${params[1]}) = ` + `${convert2Int(convert2Base(params[0], params[1]), params[1])}`); }); ////////// Exercice 7 ////////// // Computes a boolean telling if `str` is a palindrome // ('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))); } // Some tests [ '', 'a', 'abba', 'able was I,I saw elba', 'not a palindrome?' ].forEach((aStr) => { console.log(`isPalindrome('${aStr}') = ${isPalindrome(aStr)}`); }); // 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); } } // Some tests [ ['', ''], ['','OK'], ['OK',''], ['abcdde','abcdd'], ['algorithme','logarithme'], ['abcdde','ddcbae'], ['imaginer','migraine'], ['c est quoi','une anagramme au fait?'], ].forEach((aPair) => { console.log(`isAnagram('${aPair[0]}', '${aPair[1]}') = ${isAnagram(aPair[0], aPair[1])}`); });