An Interest In:
Web News this Week
- April 27, 2024
- April 26, 2024
- April 25, 2024
- April 24, 2024
- April 23, 2024
- April 22, 2024
- April 21, 2024
Advent of PBT 2021 - Day 15 - Solution
Our algorithm was: racePodium.
Go to the subject itself for more details
CodeSandbox with a possible set of properties you may have come with: https://codesandbox.io/s/advent-of-pbt-day-15-solution-e328q?file=/src/index.spec.ts&previewwindow=tests
Property 1: should predict the right podium
for any candidates
it should predict the right podium
Written with fast-check:
it("should predict the right podium", () => { fc.assert( fc.property( fc.array(fc.nat(), { minLength: 25, maxLength: 25 }), (speeds) => { // Arrange const compareParticipants = (pa: number, pb: number) => { if (speeds[pa] !== speeds[pb]) return speeds[pb] - speeds[pa]; else return pa - pb; }; const runRace = ( ...participants: RaceParticipants ): RaceParticipants => { return participants.sort(compareParticipants); }; // Act const podium = racePodium(runRace); // Assert const rankedParticipants = [...Array(25)] .map((_, i) => i) .sort(compareParticipants); const expectedPodium = rankedParticipants.slice(0, 3); expect(podium).toEqual(expectedPodium); } ) );});
While this property ensures that we always compute the right podium it does not make sure that we do it in an efficient way as it never checks if we make unneeded races.
Property 2: should insert all the selected tabs before the move position
for any candidates
it should at most do 7 races
Written with fast-check:
it("should never do more than 7 races", () => { fc.assert( fc.property( fc.array(fc.nat(), { minLength: 25, maxLength: 25 }), (speeds) => { // Arrange const compareParticipants = (pa: number, pb: number) => { if (speeds[pa] !== speeds[pb]) return speeds[pb] - speeds[pa]; else return pa - pb; }; const runRace = jest.fn( (...participants: RaceParticipants): RaceParticipants => { return participants.sort(compareParticipants); } ); // Act racePodium(runRace); // Assert expect(runRace.mock.calls.length).toBeLessThanOrEqual(7); } ) );});
One of the key characteristics of this problem is that we have a known upper bound for the number of races. Requesting for more than 7 races means that we planned our races in a sub-optimal way leading for extra races to be executed.
Back to "Advent of PBT 2021" to see topics covered during the other days and their solutions.
More about this serie on @ndubien or with the hashtag #AdventOfPBT.
Original Link: https://dev.to/dubzzz/advent-of-pbt-2021-day-15-solution-5ako
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To