////////// Exercice 1 ////////// // Functions on pointed pairs function cons(aCar, aCdr) { return { car: aCar, cdr: aCdr }; } const nil = undefined; function car(aCons) { return aCons['car']; } function cdr(aCons) { return aCons['cdr']; } // Functions on lists function head(l) { return car(l); } function tail(l) { return cdr(l); } function isEmpty(l) { return l === nil; } // Computes a string displaying the contents of the list `l` function listToString(l) { function listToStringRec(l) { if (isEmpty(l)) return ""; else if (isEmpty(tail(l))) return `${head(l)}`; else return `${head(l)},${listToStringRec(tail(l))}`; } return `[${listToStringRec(l)}]`; } /* ------------------------------- */ // Returns an empty stack function stackCreateEmpty() {} // Checks if the stack `s` is empty function stackIsEmpty(s) {} // Returns a new stack where the element `e` has been pushed on top of the stack `s` function stackPush(e, s) {} // Returns a new stack where the top of the stack `s` has been popped // Throws an error if `s` is empty function stackPop(s) {} // Returns the element at the top of the stack `s` // Throws an error if `s` is empty function stackPeek(s) {} // Returns a string representing the contents of the stack `s` function stackToString(s) {} /* ------------------------------- */ // Create a starting state for the Hanoi tower game // The state has 3 stacks, the first containing `n` disks // and the other two being empty function createStartHanoi(n) { function createStack(m) { if (m === n+1) return stackCreateEmpty(); else return stackPush(m, createStack(m+1)); } return [ createStack(1), stackCreateEmpty(), stackCreateEmpty() ]; } // Returns a string representing the state of a Hanoi tower game `h` function stringHanoi(h) { return `${stackToString(h[0])}` + ` ${stackToString(h[1])}` + ` ${stackToString(h[2])}`; } // Given a source index `fr` and a destination index `to`, returns the last // of the three available indices different from `fr` and `to`. function findFreeDestination(fr, to) { let arr = [Math.min(fr, to), Math.max(fr, to)]; return (arr[0] === 0) ? ((arr[1] === 1) ? 2 : 1) : 0; } // Play the Hanoi game on the state `h`, moving a stack of height `depth` // from the rod `fr` to the rod `to`. function moveHanoi(h, fr, to, depth) { if (depth === 1) { let toMove = stackPeek(h[fr]); console.log(`Moving ${toMove} from ${fr} to ${to}`); h[fr] = stackPop(h[fr]); h[to] = stackPush(toMove, h[to]); } else { let tmp = findFreeDestination(fr, to); moveHanoi(h, fr, tmp, depth-1); moveHanoi(h, fr, to, 1); moveHanoi(h, tmp, to, depth-1); } } //////////////////////////////////////////////////////////////// // Play the Hanoi game const size = 5; let hState = createStartHanoi(size); console.log(stringHanoi(hState)); moveHanoi(hState, 0, 2, size); console.log(stringHanoi(hState)); ////////// Exercice 2 ////////// ////////// Exercice 3 ////////// /* ------------------------------- */ // Example of Jest test // // describe('Stack test suite', () => { // // test('Empty stack should be empty', () => { // const s = S.stackCreateEmpty(); // expect(S.stackIsEmpty(s)).toBe(true); // }); // // test('Raise error when peeking empty stack', () => { // const s = S.stackCreateEmpty(); // expect(() => { // S.stackPeek(s); // }).toThrow(Error); // }); // // }); ////////// Exercice 4 //////////