////////// Exercice 1 ////////// // Functions on pointed pairs function cons(_car, _cdr) { return { car: _car, cdr: _cdr }; } const nil = {}; function car(cons) { return cons['car']; } function cdr(cons) { return cons['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 listDisp(l) { function listDispRec(l) { if (isEmpty(l)) return ""; else if (isEmpty(tail(l))) return `${head(l)}`; else return `${head(l)},${listDispRec(tail(l))}`; } return `[${listDispRec(l)}]`; } /-------------------------------/ // Returns an empty stack function stackCreateEmpty() {} // Checks that 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 content of the stack `s` function stackDisplay(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() ]; } // Display a state for the Hanoi tower game function dispHanoi(h) { return `${stackDisplay(h[0])}` + ` ${stackDisplay(h[1])}` + ` ${stackDisplay(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 tha 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(dispHanoi(hState)); moveHanoi(hState, 0, 2, size); console.log(dispHanoi(hState)); /-------------------------------/ // Example of Jest test // // describe('Stack test suite', () => { // // test('Empty stack should be empty', () => { // let s = S.stackCreateEmpty(); // expect(S.stackIsEmpty(s)).toBe(true); // }); // // test('Raise error when peeking empty stack', () => { // let s = S.stackCreateEmpty(); // expect(() => { // S.stackPeek(s); // }).toThrow(Error) // }); // // });