feat(typescript): 2020 day 16 solved

AlexAegis · Dec 16, 2020 · 1631ebd · 1631ebd
1 parent 2829698
commit 1631ebd
Show file tree

Hide file tree

Showing 11 changed files with 205 additions and 3 deletions.
diff --git a/.github/badges/2020.json b/.github/badges/2020.json
@@ -1,6  1,6 @@
 {
 	"schemaVersion": 1,
 	"label": "AoC 2020",
-	"message": "15/25",
 	"message": "16/25",
 	"color": "orange"
 }
diff --git a/readme.md b/readme.md
@@ -41,7  41,7 @@
 | [Day 13](./src/2020/day13/) | [0.22ms](./src/2020/day13/typescript/part_one.ts) |      | [0.4ms](./src/2020/day13/typescript/part_two.ts)     |      |
 | [Day 14](./src/2020/day14/) | [1.22ms](./src/2020/day14/typescript/part_one.ts) |      | [78.17ms](./src/2020/day14/typescript/part_two.ts)   |      |
 | [Day 15](./src/2020/day15/) | [0.08ms](./src/2020/day15/typescript/part_one.ts) |      | [4932.26ms](./src/2020/day15/typescript/part_two.ts) |      |
-| Day 16                      |                                                   |      |                                                      |      |
 | [Day 16](./src/2020/day16/) | [0.60ms](./src/2020/day16/typescript/part_one.ts) |      | [1.79ms](./src/2020/day16/typescript/part_two.ts)    |      |
 | Day 17                      |                                                   |      |                                                      |      |
 | Day 18                      |                                                   |      |                                                      |      |
 | Day 19                      |                                                   |      |                                                      |      |

diff --git a/src/2020/day16/typescript/bench.ts b/src/2020/day16/typescript/bench.ts
@@ -0,0  1,18 @@
 import { read } from '@lib';
 import { defaultBench } from '@lib/benchmark';
 import { add } from 'benny';
 import { day, year } from '.';
 import { runner as partOneRunner } from './part_one';
 import { runner as partTwoRunner } from './part_two';
 
 defaultBench(
 	'2020 - Day 16',
 	add('Part One', async () => {
 		const input = (await read(year, day)()).input;
 		return () => partOneRunner(input);
 	}),
 	add('Part Two', async () => {
 		const input = (await read(year, day)()).input;
 		return () => partTwoRunner(input);
 	})
 );
diff --git a/src/2020/day16/typescript/index.ts b/src/2020/day16/typescript/index.ts
@@ -0,0  1,2 @@
 export const year = 2020;
 export const day = 16;
diff --git a/src/2020/day16/typescript/parse.function.ts b/src/2020/day16/typescript/parse.function.ts
@@ -0,0  1,36 @@
 import { Range, split } from '@lib';
 
 export type Ticket = number[];
 
 export interface TicketObservation {
 	fieldRanges: Map<string, Range[]>;
 	myTicket: number[];
 	nearbyTickets: number[][];
 }
 
 export const parse = (input: string): TicketObservation => {
 	const lines = split(input);
 	const fieldRanges = new Map<string, Range[]>();
 	let myTicket: Ticket = [];
 	const nearbyTickets: Ticket[] = [];
 	let currentSection: undefined | string;
 	for (const line of lines) {
 		if (line.endsWith(':')) {
 			currentSection = line;
 			continue;
 		}
 		if (currentSection === undefined) {
 			const [category, value] = line.split(': ');
 			const ranges = value.split(' or ').map((rawRange) => {
 				const [low, high] = rawRange.split('-');
 				return { low: parseInt(low, 10), high: parseInt(high) } as Range;
 			});
 			fieldRanges.set(category, ranges);
 		} else if (currentSection === 'your ticket:') {
 			myTicket = line.split(',').map((v) => parseInt(v, 10));
 		} else if (currentSection === 'nearby tickets:') {
 			nearbyTickets.push(line.split(',').map((v) => parseInt(v, 10)));
 		}
 	}
 	return { fieldRanges, myTicket, nearbyTickets };
 };
diff --git a/src/2020/day16/typescript/part_one.spec.ts b/src/2020/day16/typescript/part_one.spec.ts
@@ -0,0  1,14 @@
 import { read } from '@lib';
 import { expect } from 'chai';
 import { day, year } from '.';
 import { runner } from './part_one';
 
 describe('2020 - Day 16 - Part One', () => {
 	it('should solve for the input', async () => {
 		expect(await runner((await read(year, day)()).input)).to.equal(27870);
 	});
 
 	it('should solve for the first example', async () => {
 		expect(await runner((await read(year, day, 'example.1.txt')()).input)).to.equal(71);
 	});
 });
diff --git a/src/2020/day16/typescript/part_one.ts b/src/2020/day16/typescript/part_one.ts
@@ -0,0  1,24 @@
 import { bench, Range, read } from '@lib';
 import { sum } from '@lib/math';
 import { day, year } from '.';
 import { parse } from './parse.function';
 
 export const checkField = (ticketField: number, categoryRanges: Range[][]): boolean => {
 	return categoryRanges.some((ranges) =>
 		ranges.some((range) => range.high >= ticketField && range.low <= ticketField)
 	);
 };
 
 export const invalidFields = (ticket: number[], rangeMap: Map<string, Range[]>): number[] => {
 	const ranges = [...rangeMap.values()];
 	return ticket.filter((field) => !checkField(field, ranges));
 };
 
 export const runner = (input: string): number => {
 	const { fieldRanges: categoryRanges, nearbyTickets } = parse(input);
 	return nearbyTickets.flatMap((ticket) => invalidFields(ticket, categoryRanges)).reduce(sum);
 };
 
 if (require.main === module) {
 	(async () => console.log(`Result: ${await bench(read(year, day), runner)}`))(); // 27870 ~0.60ms
 }
diff --git a/src/2020/day16/typescript/part_two.spec.ts b/src/2020/day16/typescript/part_two.spec.ts
@@ -0,0  1,22 @@
 import { read } from '@lib';
 import { expect } from 'chai';
 import { day, year } from '.';
 import { getMyClarifiedTicket, runner } from './part_two';
 
 describe('2020 - Day 16 - Part Two', () => {
 	it('should solve the input', async () => {
 		expect(runner((await read(year, day)()).input)).to.equal(3173135507987);
 	});
 
 	it('should solve the first example', async () => {
 		const input = (await read(year, day, 'example.2.txt')()).input;
 		expect(
 			getMyClarifiedTicket(input).every(
 				(field) =>
 					(field.fieldName === 'class' && field.value === 12) ||
 					(field.fieldName === 'row' && field.value === 11) ||
 					(field.fieldName === 'seat' && field.value === 13)
 			)
 		).to.be.true;
 	});
 });
diff --git a/src/2020/day16/typescript/part_two.ts b/src/2020/day16/typescript/part_two.ts
@@ -0,0  1,75 @@
 import { bench, Range, read } from '@lib';
 import { mult } from '@lib/math';
 import { day, year } from '.';
 import { parse, Ticket } from './parse.function';
 import { invalidFields } from './part_one';
 
 export interface CertainField {
 	index: number;
 	value: number;
 	fieldName: string;
 }
 
 export interface UncertainField extends Omit<CertainField, 'fieldName'> {
 	possibleFieldNames: string[];
 	fieldName?: string;
 }
 
 export type ClarifiedTicket = CertainField[];
 
 export const clarifyFields = (
 	ticket: Ticket,
 	otherTickets: Ticket[],
 	fieldRanges: Map<string, Range[]>
 ): ClarifiedTicket => {
 	const categoryRangeEntries = [...fieldRanges.entries()];
 	const myFields = ticket.map((value, index) => {
 		const otherTicketsFields = otherTickets.map((ticket) => ticket[index]);
 		const possibleFieldNames = categoryRangeEntries
 			.filter(([, ranges]) =>
 				otherTicketsFields.every((ticketField) =>
 					ranges.some((range) => range.high >= ticketField && range.low <= ticketField)
 				)
 			)
 			.map((p) => p[0]);
 		return { index, value, possibleFieldNames } as UncertainField;
 	});
 
 	// Finding which field is which
 	const certainFields = new Set<string>();
 	// While there are uncertain fields
 	while (myFields.some((field) => field.possibleFieldNames.length)) {
 		// Those that are certain, collect
 		for (const myField of myFields.filter((field) => field.possibleFieldNames.length === 1)) {
 			myField.fieldName = myField.possibleFieldNames[0];
 			certainFields.add(myField.fieldName);
 		}
 
 		// And take out from other field name considerations
 		for (const field of myFields) {
 			field.possibleFieldNames = field.possibleFieldNames.filter(
 				(possibleFieldName) => !certainFields.has(possibleFieldName)
 			);
 		}
 	}
 
 	return myFields as ClarifiedTicket;
 };
 
 export const getMyClarifiedTicket = (input: string): ClarifiedTicket => {
 	const { myTicket, fieldRanges, nearbyTickets } = parse(input);
 	const validTickets = nearbyTickets.filter(
 		(ticket) => invalidFields(ticket, fieldRanges).length === 0
 	);
 	return clarifyFields(myTicket, validTickets, fieldRanges);
 };
 
 export const runner = (input: string): number =>
 	getMyClarifiedTicket(input)
 		.filter((p) => p.fieldName?.startsWith('departure'))
 		.map((p) => p.value)
 		.reduce(mult, 1);
 
 if (require.main === module) {
 	(async () => console.log(`Result: ${await bench(read(year, day), runner)}`))(); // 3173135507987 ~1.79ms
 }
diff --git a/src/lib/typescript/benchmark/benny.utils.ts b/src/lib/typescript/benchmark/benny.utils.ts
@@ -24,6  24,7 @@ export const defaultBench = (
 		cycleTime(),
 		complete(),
 		save({ file: 'reduce', version: '1.0.0', format: 'table.html' }),
-		save({ file: 'reduce', format: 'chart.html' })
 		save({ file: 'reduce', format: 'chart.html' }),
 		save({ file: 'reduce', format: 'json' })
 	);
 };
diff --git a/src/lib/typescript/polyfills/math.polyfill.ts b/src/lib/typescript/polyfills/math.polyfill.ts
@@ -8,6  8,11 @@ import {
 	posModBigInt,
 } from '@lib/math';
 
 export interface Range<T = number> {
 	low: T;
 	high: T;
 }
 
 declare global {
 	interface Number {
 		/**
@@ -16,6  21,7 @@ declare global {
 		 */
 		posMod(m: number): number;
 		isBetween(l: number, h: number): boolean;
 		isBetweenRange(range: Range<number>): boolean;
 		invMod(n: number): number;
 		modExp(b: number, n: number): number;
 	}
@@ -48,6  54,10 @@ Number.prototype.isBetween = function (this: number, l: number, h: number): bool
 	return isBetween(this, l, h);
 };
 
 Number.prototype.isBetweenRange = function (this: number, range: Range<number>): boolean {
 	return isBetween(this, range.low, range.high);
 };
 
 BigInt.prototype.isBetween = function (this: bigint, l: bigint, h: bigint): boolean {
 	return isBetween(this, l, h);
 };
Original file line number	Diff line number	Diff line change
		@@ -0,0 1,2 @@
		export const year = 2020;
		export const day = 16;