////////// Exercice 1 ////////// ////////// Exercice 2 ////////// ////////// Exercice 3 ////////// ////////// Exercice 4 ////////// // file list.impl.js // Functions on pointed pairs function cons(aCar, aCdr) { return { car: aCar, cdr: aCdr }; } const nil = {}; 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)}]`; } // Module exports export { cons, nil, head, tail, isEmpty, listToString, }; // file stack.impl.js import * as L from "./list.impl.js"; // Creates an empty stack function stackCreateEmpty() { return L.nil; } // Checks if the stack `s` is empty function stackIsEmpty(s) { return L.isEmpty(s); } // Returns a new stack where the element `e` has been pushed on top of the stack `s` function stackPush(e, s) { return L.cons(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) { if (L.isEmpty(s)) throw new Error('stackPop: popping an empty stack') else return L.tail(s); } // Returns the element at the top of the stack `s` // Throws an error if `s` is empty function stackPeek(s) { if (L.isEmpty(s)) throw new Error('stackPeek: peeking an empty stack') else return L.head(s); } // Returns a string representing the contents of the stack `s` function stackToString(s) { return L.listToString(s); } // exports export { stackCreateEmpty, stackIsEmpty, stackPush, stackPop, stackPeek, stackToString, }; // file stack.test.js import * as S from "./stack.impl.js" describe('Stack test suite', () => { test('Empty stack should be empty', () => { const s = S.stackCreateEmpty(); expect(S.stackIsEmpty(s)).toBe(true); }); test('Adding an element at the top, then peeking', () => { const s = S.stackPush(20, S.stackPush(10, S.stackCreateEmpty())); expect(S.stackPeek(s)).toBe(20); }); test('Pushing then popping elements', () => { const s = S.stackPop( S.stackPop( S.stackPush(30, S.stackPush(20, S.stackPush(10, S.stackCreateEmpty()))))); expect(S.stackPeek(s)).toBe(10); }); test('Display the empty stack', () => { const s = S.stackCreateEmpty(); expect(S.stackToString(s)).toBe('[]'); }); test('Display a non-empty stack', () => { const s = S.stackPush(30, S.stackPush(20, S.stackPush(10, S.stackCreateEmpty()))); expect(S.stackToString(s)).toBe('[30,20,10]'); }); test('Raise error when popping empty stack', () => { const s = S.stackPop( S.stackPush(10, S.stackCreateEmpty())); expect(() => { S.stackPop(s); }).toThrow(Error); }); test('Raise error when peeking empty stack', () => { const s = S.stackCreateEmpty(); expect(() => { S.stackPeek(s); }).toThrow(Error); }); }); // file hanoi.js import * as S from "./stack.impl.js"; // 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 S.stackCreateEmpty(); else return S.stackPush(m, createStack(m+1)); } return [ createStack(1), S.stackCreateEmpty(), S.stackCreateEmpty() ]; } // Returns a string representing the state of a Hanoi tower game `h` function stringHanoi(h) { return `${S.stackToString(h[0])}` + ` ${S.stackToString(h[1])}` + ` ${S.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 otherPit(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 = S.stackPeek(h[fr]); console.log(`Moving ${toMove} from ${fr} to ${to}`); h[fr] = S.stackPop(h[fr]); h[to] = S.stackPush(toMove, h[to]); } else { let tmp = otherPit(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)); // file list.impl.ts // Type for pointed pairs type PointedPair = { car: T; cdr: U; }; // Functions on pointed pairs function cons(_car: T, _cdr: U) : PointedPair { return { car: _car, cdr: _cdr }; } function car(aCons: PointedPair) : T { return aCons['car']; } function cdr(aCons: PointedPair) : U { return aCons['cdr']; } // Type for lists type List = undefined | { car: T, cdr: List }; function isEmpty(aList : List): boolean { return aList === nil; } // Functions on lists const nil : undefined = undefined; function head(aList : List) : T { if (isEmpty(aList)) throw new Error("head: empty list"); else return car(aList as PointedPair>); } function tail(aList: List) : List { if (isEmpty(aList)) throw new Error("tail: empty list"); else return cdr(aList as PointedPair>); } // Computes a string displaying the contents of the list `l` function listToString(l: List) : string { function listToStringRec(l: List) : string { if (isEmpty(l)) return ""; else if (isEmpty(tail(l))) return `${head(l)}`; else return `${head(l)},${listToStringRec(tail(l))}`; } return `[${listToStringRec(l)}]`; } // Some examples of lists const aNumberList : List = cons(1, cons(2, nil)); const aStringList : List = cons("a", cons("b", nil)); const aMixedList : List = cons("one", cons(2, nil)); const aMixedListMorePreciselyTyped : List = cons("one", cons(2, nil)); // A list that does not type // let anErroneousList : List = cons("true", nil); export { cons, nil, head, tail, isEmpty, listToString }; // possible to add List export type { List }; // file stack.impl.ts import * as L from "#src/Atd/list.impl.js"; // necessary to use this form for typescript //type List=L.List // possible to use to avoid L.List anywhere import type { List } from "#src/Atd/list.impl.js"; // smarter version //import * as L from "./list.impl.js"; type Stack = List ; // Returns an empty stack function stackCreateEmpty() : Stack { return L.nil; } //Checks if the stack `s` is empty function stackIsEmpty(s : Stack) : boolean { return L.isEmpty(s); } // Returns a new stack where the element `e` has been pushed on top of the stack `s` function stackPush(e: T, s: Stack) : Stack { return L.cons(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: Stack) : Stack { if (stackIsEmpty(s)) throw new Error("Error: stack is empty, can not be poped"); else return L.tail(s); } // Returns the element at the top of the stack `s` // Throws an error if `s` is empty function stackPeek(s: Stack) : T { if (stackIsEmpty(s)) throw new Error("Error: stack is empty, can not be peeked"); else return L.head(s); } // Returns a string representing the contents of the stack `s` function stackToString(s : Stack) : string { return L.listToString(s); } export { stackCreateEmpty, stackIsEmpty, stackPush, stackPop, stackPeek, stackToString }; export type { Stack }; // file stack.test.ts import * as S from "#src/Atd/stack.impl.js"; import type {Stack} from "#src/Atd/stack.impl.js"; describe('Stack test suite', () => { test('Empty stack should be empty', () => { const s : Stack = S.stackCreateEmpty(); expect(S.stackIsEmpty(s)).toBe(true); }); test('Adding an element at the top, then peeking', () => { const s : Stack = S.stackPush(20, S.stackPush(10, S.stackCreateEmpty() )); expect(S.stackPeek(s)).toBe(20); }); test('Pushing then popping elements', () => { const s : Stack = S.stackPop( S.stackPop( S.stackPush(30, S.stackPush(20, S.stackPush(10, S.stackCreateEmpty() ))))); expect(S.stackPeek(s)).toBe(10); }); test('Display the empty stack', () => { const s : Stack = S.stackCreateEmpty(); expect(S.stackToString(s)).toBe('[]'); }); test('Display a non-empty stack', () => { const s : Stack = S.stackPush(30, S.stackPush(20, S.stackPush(10, S.stackCreateEmpty() ))); expect(S.stackToString(s)).toBe('[30,20,10]'); }); test('Raise error when popping empty stack', () => { const s : Stack = S.stackPop( S.stackPush(10, S.stackCreateEmpty() )); expect(() => { S.stackPop(s); }).toThrow(Error); }); test('Raise error when peeking empty stack', () => { const s : Stack = S.stackCreateEmpty(); expect(() => { S.stackPeek(s); }).toThrow(Error); }); }); // file hanoi.ts import { stackCreateEmpty, stackIsEmpty, stackPush, stackPop, stackPeek, stackToString } from "#src/Atd/stack.impl.js"; import type {Stack} from "#src/Atd/stack.impl.js"; type Array3NumStacks = [Stack, Stack, Stack]; type HanoiState = Array3NumStacks; // 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: number) : HanoiState { function createStack(m : number) : Stack { 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 : HanoiState) : string { 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 : number, to : number) : number { const 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: HanoiState, fr: number, to: number, depth: number) { // no return type if (depth === 1) { const toMove = stackPeek(h[fr]); console.log(`Moving ${toMove} from ${fr} to ${to}`); h[fr] = stackPop(h[fr]); h[to] = stackPush(toMove, h[to]); } else { const 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 : number = 5; const hState : HanoiState = createStartHanoi(size); console.log(stringHanoi(hState)); moveHanoi(hState, 0, 2, size); console.log(stringHanoi(hState));