dfriedenberger
: dfriedenberger
Table of Contents
- dfriedenberger
- About me
- Day 00: typescript
- Day 01: typescript
- Day 02: typescript
- Day 03: typescript
- Day 04: typescript
- Day 05: typescript
- Day 06: typescript
- Day 07: typescript
- Day 08: typescript
- Day 09: typescript
- Day 10: typescript
- Day 11: typescript
- Day 12: typescript
- Day 13: typescript
- Day 14: typescript
- Day 15: typescript
- Day 16: typescript
- Day 17: typescript
- Day 18: typescript
- Day 19: typescript
- Day 20: typescript
- Day 21: typescript
- Day 22: typescript
- Day 23: typescript
- Day 24: typescript
- Day 25: typescript
dfriedenberger
Day 00: typescript
Hello World
The solutions are written in Typescript. To compile Typescript to Javascript you can use gulp runner. For running you can use node
npm install gulp node dist/solution1.js
Why Typescript?
"TypeScript is a typed superset of JavaScript that compiles to plain JavaScript.""
class Hello
{
getGreetings(name : string) : string
{
return "Hello "+name+"!";
}
}
let hello : Hello = new Hello();
console.log(hello.getGreetings("World"));Day 01: typescript
The Tyranny of the Rocket Equation
This solution is written in Typescript. I decided for Typescript because want write better Javascript.
npm install gulp node dist/solution1.js node dist/solution1.js
Need some classes - Modul - Spacecraft
For each solution implement own calculator service
import { Spacecraft } from "./Spacecraft";
import { Modul } from "./Modul";
class CalculateFuelService {
calculateRequiredFuelForSpacecraft(spacecraft : Spacecraft) : number
{
let fuel = 0;
for (var modul of spacecraft.getModules())
fuel += this.calculateRequiredFuelForModul(modul);
return fuel;
}
calculateRequiredFuelForModul(modul : Modul) : number
{
return Math.floor(modul.getMass() / 3) - 2;
}
}
export { CalculateFuelService };import { Spacecraft } from "./Spacecraft";
import { Modul } from "./Modul";
class CalculateFuelWithFuelService {
calculateRequiredFuelForSpacecraft(spacecraft : Spacecraft) : number
{
let fuel = 0;
for (var modul of spacecraft.getModules())
fuel += this.calculateRequiredFuelForModul(modul);
return fuel;
}
calculateRequiredFuelForModul(modul : Modul) : number
{
var complete = 0;
var currentMass = modul.getMass();
while(true)
{
let currentFuel = Math.floor(currentMass / 3) - 2;
if(currentFuel <= 0) break;
complete += currentFuel;
currentMass = currentFuel;
}
return complete;
}
}
export { CalculateFuelWithFuelService };First Star
The solution is quite straight forward.
import { Spacecraft } from "./Spacecraft";
import { CalculateFuelService } from "./CalculateFuelService";
let calculateFuelService = new CalculateFuelService();
let spacecraft = new Spacecraft();
spacecraft.loadModules("input1.txt");
console.log("My puzzle answer is " + calculateFuelService.calculateRequiredFuelForSpacecraft(spacecraft));Second Star
import { Spacecraft } from "./Spacecraft";
import { CalculateFuelWithFuelService } from "./CalculateFuelWithFuelService";
let calculateFuelService = new CalculateFuelWithFuelService();
let spacecraft = new Spacecraft();
spacecraft.loadModules("input1.txt");
console.log("My puzzle answer is " + calculateFuelService.calculateRequiredFuelForSpacecraft(spacecraft));Day 02: typescript
1202 Program Alarm
This solution is written in Typescript.
npm install gulp node dist/solution1.js node dist/solution1.js
First Star
Solved solution one by implementing the computer and the rules
import { Program } from "./Program";
class Computer {
run(program : Program) : boolean
{
switch(program.getOpCode())
{
case 1:
var input1 = program.getInput1();
var input2 = program.getInput2();
program.setResult(input1 + input2);
break;
case 2:
var input1 = program.getInput1();
var input2 = program.getInput2();
program.setResult(input1 * input2);
break;
case 99:
return false;
default:
throw new Error();
}
program.next();
return true;
}
}
export { Computer };Second Star
Second solution solved through brute force.
import { Computer } from "./Computer";
import { Program } from "./Program";
let computer = new Computer();
for(let noun = 0;noun <= 99;noun++)
{
for(let verb = 0;verb <= 99;verb++)
{
let program = new Program([1,0,0,3,1,1,2,3,1,3,4,3,1,5,0,3,2,6,1,19,1,19,10,23,2,13,23,27,1,5,27,31,2,6,31,35,1,6,35,39,2,39,9,43,1,5,43,47,1,13,47,51,1,10,51,55,2,55,10,59,2,10,59,63,1,9,63,67,2,67,13,71,1,71,6,75,2,6,75,79,1,5,79,83,2,83,9,87,1,6,87,91,2,91,6,95,1,95,6,99,2,99,13,103,1,6,103,107,1,2,107,111,1,111,9,0,99,2,14,0,0]);
program.set(1,noun);
program.set(2,verb);
while(computer.run(program));
if(program.get(0) == 19690720)
{
console.log("My puzzle answer is " + (noun * 100 + verb));
process.exit(-1);
}
}
}Day 03: typescript
Crossed Wires
This solution is written in Typescript.
npm install gulp node dist/solution1.js node dist/solution1.js
First implementing the Wire class. It’s handle convertion from path to x,y-Coordinates in constructor
constructor(pathDefinition : string)
{
let pathes : Array<string> = pathDefinition.split(",");
let x = 0;
let y = 0;
let l = 0;
for (let path of pathes) {
let direction = path.substr(0,1);
let steps = parseInt(path.substr(1));
let dy = 0;
let dx = 0;
switch(direction)
{
case "R": dx = 1; break;
case "U": dy = 1; break;
case "L": dx = -1; break;
case "D": dy = -1; break;
}
for(let i = 0;i < steps;i++)
{
x = x + dx;
y = y + dy;
l = l + 1;
let coordinate = new Coordinate(x,y)
this.coordinates.add(new Coordinate(x,y));
this.distances[coordinate.key()] = l;
}
}
}and find crosses by comparing the coordinates
cross(wire : Wire) : CoordinateSet
{
let crosses = new CoordinateSet();
for(let coordinate of this.coordinates)
{
if(wire.contains(coordinate.x,coordinate.y))
{
crosses.add(coordinate);
}
}
return crosses;
}First Star
This was solved by implementing ManhattanDistance (here first time uses interfaces in Typescript)
distance(coordinate: Coordinate): number {
return Math.abs(coordinate.x) + Math.abs(coordinate.y);
}and find the minimum of the distances.
import { CoordinateSet } from "./CoordinateSet";
import { Distance } from "./Distance";
class ShortestDistance {
distance : Distance;
constructor(pDistance : Distance)
{
this.distance = pDistance;
}
min(coordinates : CoordinateSet) : number
{
let minDistance = -1;
for(let k in coordinates.map)
{
let coordinate = coordinates.map[k];
let distance = this.distance.distance(coordinate);
if(minDistance == -1 || distance < minDistance)
{
minDistance = distance;
}
}
return minDistance;
}
}
export { ShortestDistance };Second Star
Second solution solved by replacing the Implementation of Distance from ManhattanDistance to SignalDelayDistance
let distance = new ShortestDistance(new ManhattanDistance());let distance = new ShortestDistance(new SignalDelayDistance([wire1.distances,wire2.distances]));SignalDelayDistance uses map of distances created during Wire construction
import { Coordinate } from "./Coordinate";
import { Distance } from "./Distance";
import { Wire } from "./Wire";
class SignalDelayDistance implements Distance {
wires : any;
constructor(pWires : any)
{
this.wires = pWires;
}
distance(coordinate: Coordinate): number {
let d = 0;
for(let map of this.wires)
{
let k = coordinate.key();
if(k in map)
{
d += map[''+k];
}
}
return d;
}
}
export { SignalDelayDistance };Day 04: typescript
Secure Container
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
First Star
First, I thought about how to solve it mathematically. But it’s a little bit complicated, because the input range.
A few basic considerations:
-
six-digit number ⇒ 900.000 numbers
-
353096-843212 ⇒ 490.117 numbers
-
adjacent digits ⇒ 900.000 - 9 * 8 * 7 * 6 * 5 (possibilities with unique numbers) = 884880
-
digits never decrease ⇒ ???
But was is the intersection?
I decieded to solve it with brute force. Programmers are the laziest people on the planet. Algorithm only has a runtime complexity of O(n). And N is maximum 1 million.
Solved this by implementing creation of digits and validating the resulting number.
Generating Digits
Use recursive function which add a digit an each call. Start with value for next digit which is greater or equals.
digit({ digits, sumprev, pos, start }:
{ digits: any; sumprev: number; pos: number; start: number; }) : void
{
//Going from left to right, the digits never decrease.
for(let i = start;i <= 9;i++)
{
digits[pos] = i;
let sum = sumprev * 10 + i;
//start is set to current digit
this.digit({ digits, sumprev: sum, pos: pos + 1, start: i });
}
}To check the input range, validate each number when reach last digit
if(pos == 5)
{
//The value is within the range given in your puzzle input.
if(sum < this.min) continue;
if(sum > this.max) continue;
if(!this.passwordDigitValidator.validate(digits)) continue;
this.cnt++;
continue;
}
Then start it with first call.
/* It is a six-digit number. => Starts Digit 1 */
this.digit({ digits: [0, 0, 0, 0, 0, 0], sumprev: 0, pos: 0, start: 1 });
Validating Digits
For checking adjacent digits use own class.
import { PasswordDigitValidator } from "./PasswordDigitValidator";
class PasswordDigitValidatorAdjacentDigits implements PasswordDigitValidator {
validate(digits : Array<number>) : boolean
{
//Two adjacent digits are the same (like 22 in 122345).
for(let x = 1;x < 6;x++)
{
if(digits[x-1] == digits[x])
return true;
}
return false;
}
}
export { PasswordDigitValidatorAdjacentDigits };
Finally run generator to count the numbers
import { PasswordDigitValidatorAdjacentDigits } from "./PasswordDigitValidatorAdjacentDigits";
import { PasswordDigitGenerator } from "./PasswordDigitGenerator";
let generator = new PasswordDigitGenerator(353096,843212,new PasswordDigitValidatorAdjacentDigits());
generator.gen();
console.log("My puzzle answer is " + generator.getCnt());
Second Star
Replaced the Validator class.
import { PasswordDigitValidator } from "./PasswordDigitValidator";
class PasswordDigitValidatorAdjacentDigitsInGroup implements PasswordDigitValidator {
validate(digits : Array<number>) : boolean
{
//Two adjacent digits are the same (like 22 in 122345).
for(let x = 1;x < 6;x++)
{
if((x > 1) && (digits[x-2] == digits[x])) continue;
if((x < 5) && (digits[x+1] == digits[x])) continue;
if(digits[x-1] == digits[x])
return true;
}
return false;
}
}
export { PasswordDigitValidatorAdjacentDigitsInGroup };
Day 05: typescript
Sunny with a Chance of Asteroids
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
Nothing spectacular. Only extended the classes. It took a little time to find a bug in the jump obcode processing. I did this using the classic way with console.log
First and Second Star
Solved both solution by extending the computer and the rules.
import { Program } from "./Program";
class Computer {
output : Array<number> = [];
input : number;
setInput(val : number) : void
{
this.input = val;
}
getOutput() : Array<number>
{
return this.output;
}
run(program : Program) : boolean
{
let abcde = '00000' + program.getOpCode();
let l = abcde.length;
let de = parseInt(abcde.substring(l-2,l));
let c = parseInt(abcde.substring(l-3,l-2));
let b = parseInt(abcde.substring(l-4,l-3));
let a = parseInt(abcde.substring(l-5,l-4));
switch(de)
{
case 1:
var input1 = program.getInput1(c);
var input2 = program.getInput2(b);
program.setResult(a,input1 + input2);
program.next(4);
break;
case 2:
var input1 = program.getInput1(c);
var input2 = program.getInput2(b);
program.setResult(a,input1 * input2);
program.next(4);
break;
case 3:
//Todo
program.setInput(c,this.input);
program.next(2);
break;
case 4:
var input1 = program.getInput1(c);
console.log("Output "+input1);
this.output.push(input1);
program.next(2);
break;
case 5: //jump-if-true
var input1 = program.getInput1(c);
var input2 = program.getInput2(b);
if(input1 != 0)
{
program.setPosition(input2);
}
else
{
program.next(3);
}
break;
case 6: //jump-if-false
var input1 = program.getInput1(c);
var input2 = program.getInput2(b);
if(input1 == 0)
{
program.setPosition(input2);
}
else{
program.next(3);
}
break;
case 7: //less
var input1 = program.getInput1(c);
var input2 = program.getInput2(b);
if(input1 < input2)
{
program.setResult(a,1);
}
else
{
program.setResult(a,0);
}
program.next(4);
break;
case 8: //equals
var input1 = program.getInput1(c);
var input2 = program.getInput2(b);
if(input1 == input2)
{
program.setResult(a,1);
}
else
{
program.setResult(a,0);
}
program.next(4);
break;
case 99:
return false;
default:
throw new Error();
}
return true;
}
}
export { Computer };Day 06: typescript
Universal Orbit Map
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
First Star
First implementing Orbit container class and add each connection to a map with array of his direct adjacents.
add(key : string, adj : string)
{
if(!(key in this.map))
this.map[key] = [];
this.map[key].push(adj);
}Solving counting with recursive function
count(key : string,deep : number) : number {
let c = deep;
var keyList = this.map[key];
if(keyList)
{
for(let k of keyList)
{
c += this.count(k,deep + 1);
}
}
return c;
}
Second Star
Second solution solved through modified recursive function. Searching for the YOU and SAN nodes and the connecting node.
find(key : string,list : any) : number {
let sum = 0;
if(key == "YOU") return 1;
if(key == "SAN") return 1;
var keyList = this.map[key];
let cnt = 0;
if(keyList)
{
for(let k of keyList)
{
let c = this.find(k,list);
if(c > 0)
{
cnt++;
sum += c + 1;
}
}
}
switch(cnt)
{
case 0: //nothing
return 0;
case 1:
console.log("on the way "+sum);
return sum;
case 2:
console.log("found "+(sum - 4));
return 0;
default:
throw new Error();
}
}Day 07: typescript
Amplification Circuit
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
Extend the Computer class with state. Stop’s if is in state Done and also if it is waiting for Input. Implement AmplifierSeries which gets output value from one amplifier and put it to next. Can used for both solution
run(inputs: Array<number>) : number {
let lastOutput : number= 0
let computers : Array<Computer> = [];
for(let inst of inputs)
{
let program = new Program([...this.code]);
let computer = new Computer(program);
computer.setInput(inst);
computers.push(computer);
}
while(!computers[4].isDone())
{
for(let i = 0;i < 5;i++)
{
computers[i].setInput(lastOutput);
while(computers[i].run());
lastOutput = computers[i].getLastOutput();
}
}
return lastOutput;
}
First and Second Star
Difference between solution 1 and 2 is the used permutation.
let permutations : Permutation = new Permutation([5,6,7,8,9]);
for(let permutation of permutations)
{
let output = series.run(permutation);
if(output > max) max = output;
}Day 08: typescript
Space Image Format
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
First Star
Create Layers from input data
load(code : string) : void
{
let size = this.wide * this.tall;
let length = code.length;
for(let i = 0;i < length;i += size)
{
let layer : Layer = new Layer(this.wide,this.tall);
layer.set(code.substr(i,size));
this.layers.push(layer);
}
}and select this layer with fewest '0' digets.
selectWithFewestDigits(digit : string) :Layer
{
let minLayer : Layer = undefined;
this.layers.forEach(layer => {
if((minLayer == undefined) || (layer.count(digit) < minLayer.count(digit)))
{
minLayer = layer;
}
});
return minLayer;
}
For solution calculate the product of '1' and '2' digits.
let layer : Layer = layerManager.selectWithFewestDigits('0');
var result = layer.count('1') * layer.count('2');
Second Star
For second solution joined the layers
joinLayers() : Layer
{
let code : string = "";
for(let t = 0;t < this.tall;t++)
{
for(let w = 0;w < this.wide;w++)
{
//get code for Layer first non 2 wins
let c;
for(let i = 0;i < this.layers.length;i++)
{
c = this.layers[i].get(w,t);
if(c != '2') break;
}
code += c;
}
}
let layer : Layer = new Layer(this.wide,this.tall);
layer.set(code);
return layer;
}
and dump it as ASCII image.
let layer : Layer = layerManager.joinLayers();
for(let t = 0;t < 6;t++)
{
let line = "";
for(let w = 0;w < 25;w++)
{
let c = layer.get(w,t);
line += (c == '1')?"*":" ";
}
console.log(line);
}*** ** *** **** *** * * * * * * * * * *** * * * * *** * * * *** * * * * * * * * * * * *** ** * **** ***
Day 09: typescript
Sensor Boost
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
Extension of classes was easy, only add relative parameter mode
getIndex(mode : number, parameter : number)
{
switch(mode)
{
case 0: //position mode
return this.code[this.ix+parameter];
case 1: //immediate mode
return this.ix+parameter;
case 2: //relative mode
return this.code[this.ix+parameter] + this.relativeBase;
}
throw new Error("Mode "+mode+" is not supported yet");
}
and handling for opcode 9.
case 9:
var input1 = this.program.getInput1(c);
this.program.incrRelativeBase(input1);
this.program.next(2);
break;
Extending other capabilities was not necessary. Large numbers are supported from number object in Typescript and array is automaticly extended if write a value to new index. Only return 0 if index not exists was added.
getInput1(mode : number) : number
{
let i = this.getIndex(mode,1);
//check if index in code exists
if ( this.code[i] !== void 0 )
return this.code[i];
return 0;
}
Furthermore wrote my first static function in TypeScript.
static load(filename : string) : Computer
{
let data : string = fs.readFileSync(filename).toString('utf-8');
let code : Array<number> = data.split(',').map(c => parseInt(c));
return new Computer(new Program(code));
}
Day 10: typescript
Monitoring Station
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
Implement AsteroidMap with document first, so I was thinking implementing the following functions:
-
add row (calculate width and high)
-
is an asteroid at x,y
-
cnt asteroids in diagonal
-
cnt reachable asteroids from x,y
-
find best position
for vaporization i would sort arrays by angle and distance.
class AsteroidMap
{
width: number = 0;
height: number = 0;
map : any = {};
candidates : any = [];
add(x : number,y : number) : void
{
this.map[x+","+y] = 0;
}
is(x : number,y : number) : boolean
{
return ((x+","+y) in this.map);
}
addRow(line : string)
{
let c = line.split('');
if(this.height == 0)
this.width = c.length;
else if(this.width != c.length)
throw new Error(this.width +" != "+ c.length);
for(let x = 0;x < this.width;x++)
{
switch(c[x])
{
case '#': //asteroid
this.add(x,this.height);
break;
case '.': //space
//ignore
break;
default:
throw new Error("Unknown "+ c[x]);
}
}
this.height++;
}
count() : number {
return Object.keys(this.map).length;
}
diagonale(x0 : number,y0 : number,xoff : number,yoff : number) : number
{
let c = 0;
let x = x0;
let y = y0;
while(true)
{
x += xoff;
y += yoff;
if(x < 0) break;
if(x >= this.width) break;
if(y < 0) break;
if(y >= this.height) break;
if(this.is(x,y))
c+= 1;
}
return c;
}
createCandidates() : void {
if(this.candidates.length > 0) return;
let deep = this.width > this.height ? this.width : this.height;
//console.log("deep = "+deep);
for(let j = deep * -1; j <= deep;j++)
for(let i = deep * -1; i <= deep;i++)
{
if(i == 0 && j == 0) continue;
//is vielfaches
let ignore = false;
for(let f = 2;f <= deep;f++)
{
if(i % f == 0 && j % f == 0) ignore = true;
}
if(ignore) continue;
this.candidates.push([j,i]);
}
}
countxy(x : number,y : number) : number
{
this.createCandidates();
let s = this.count() -1; //myself
for(let i = 0;i < this.candidates.length;i++)
{
let candidate = this.candidates[i];
let c = this.diagonale(x,y,candidate[0],candidate[1]);
if(c > 1)
s -= c - 1;
}
return s;
}
findmaxcountxy() : object {
let found = {
max : 0,
x : -1,
y : -2
};
for(let x = 0;x < this.width;x++)
for(let y = 0;y < this.height;y++)
{
if(!this.is(x,y)) continue;
let c = this.countxy(x,y);
if(c > found.max)
{
found.max = c;
found.x = x;
found.y = y;
}
}
return found;
}
angle(v1 : any , v2 : any)
{
//cos y = v1 * v2 / |v1| * |v2|
let a = Math.sqrt(v1[0] * v1[0] + v1[1] * v1[1]);
let b = Math.sqrt(v2[0] * v2[0] + v2[1] * v2[1]);
let c = (v1[0] * v2[0] + v1[1] * v2[1]);
let d= c / (a * b);
let w = Math.acos(d);
if(v2[0] < 0)
return 6.3 - w;
return w;
}
distance(x : any , y : any) : number
{
return Math.sqrt(x * x + y * y);
}
factor(x : any , y : any) :number
{
let factor = 1;
for(let f = 2;f <= Math.max(x,y);f++)
{
if(x % f == 0 && y % f == 0)
factor = f;
}
return factor;
}
vaporizationOrder(xl : number,yl :number) : any
{
let list : any = [];
for(let x = 0;x < this.width;x++)
for(let y = 0;y < this.height;y++)
{
if(x == xl && y == yl) continue;
if(!this.is(x,y)) continue;
var xr = x -xl;
var yr = y -yl;
let f = this.factor(xr,yr);
list.push({
x : x,
y : y,
a : this.angle([0,-1], [xr/f,yr/f]),
d : this.distance(x - xl,y - yl),
k : x * 100 + y
});
}
let list2 : any = [];
var sorted = list.sort(function(a :any , b : any) {
if(a.a == b.a)
return (a.d - b.d);
return a.a - b.a;
});
while(sorted.length > 0)
{
var last = -1;
var rest = [];
while(sorted.length > 0)
{
var e = sorted[0];
sorted.splice(0,1);
if(e.a == last)
{
rest.push(e);
}
else
{
last = e.a;
list2.push(e);
}
}
sorted = rest;
}
return list2;
}
}
export { AsteroidMap };
First Start
var find : any = map.findmaxcountxy();
console.log("My puzzle answer is " + find.max);Second Star
var find : any = map.findmaxcountxy();
let a = map.vaporizationOrder(find.x,find.y);
console.log("My puzzle answer is " + a[199].k);Day 11: typescript
Space Police
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
Implement Panel class and reused unmodified Computer.
class Panel
{
x : number = 0;
y : number = 0;
degree : number = 0;
colors : any = {};
minx : number = 0;
maxx : number = 0;
miny : number = 0;
maxy : number = 0;
getColor() : number
{
let k = this.x+","+this.y;
if(k in this.colors)
return this.colors[k];
return 0;
}
getColorXY(x : number,y : number) : number
{
let k = x+","+y;
if(k in this.colors)
return this.colors[k];
return 0;
}
setColor(c : number) : void
{
let k = this.x+","+this.y;
this.colors[k] = c;
}
turn(dir : number) : void
{
//0 means it should turn left 90 degrees, and 1 means it should turn right 90 degrees.
if(dir == 0)
this.degree = (this.degree + 270)%360;
else
this.degree = (this.degree + 90)%360;
}
moveForward() :void
{
switch(this.degree)
{
case 0:
this.y--;
break;
case 90:
this.x++;
break;
case 180:
this.y++;
break;
case 270:
this.x--;
break;
}
this.minx = Math.min(this.minx,this.x);
this.maxx = Math.max(this.maxx,this.x);
this.miny = Math.min(this.miny,this.y);
this.maxy = Math.max(this.maxy,this.y);
}
countPanels() : number
{
return Object.keys(this.colors).length;
}
dump() : void
{
for(let y = this.miny;y <= this.maxy;y++)
{
let line = "";
for(let x = this.minx;x <= this.maxx;x++)
{
line += this.getColorXY(x,y) == 0? ".":"#";
}
console.log(line);
}
}
}
export { Panel }
First Start
import { Computer } from "./Computer";
import { Panel } from "./Panel";
let computer = Computer.load("input.txt");
let panel = new Panel();
let x = 0;
while(!computer.isDone())
{
let c = panel.getColor();
computer.setInput(c);
while(computer.run());
let output = computer.getOutput();
console.log(output[x]+","+output[x+1]);
panel.setColor(output[x++]);
panel.turn(output[x++]);
panel.moveForward();
}
console.log("My puzzle answer is "+panel.countPanels());Second Star
import { Computer } from "./Computer";
import { Panel } from "./Panel";
let computer = Computer.load("input.txt");
let panel = new Panel();
panel.setColor(1);
let x = 0;
while(!computer.isDone())
{
let c = panel.getColor();
computer.setInput(c);
while(computer.run());
let output = computer.getOutput();
console.log(output[x]+","+output[x+1]);
panel.setColor(output[x++]);
panel.turn(output[x++]);
panel.moveForward();
}
//dump
panel.dump();
console.log("My puzzle answer is (see image)");Day 12: typescript
The N-Body Problem
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
First Star
Solved solution one by implementing Space and Moon.
class Moon
{
x : Array<number> = [];
v : Array<number> = [0,0,0];
constructor({ x, y, z }: { x: number; y: number; z: number; })
{
this.x[0] = x;
this.x[1] = y;
this.x[2] = z;
}
private caclulateEnergy(a : Array<number>) : number {
let e = 0;
for(let i = 0;i < 3;i++)
e += Math.abs(a[i]);
return e;
}
getPotentialEnergy() : number {
return this.caclulateEnergy(this.x);
}
getKineticEnergy() : number {
return this.caclulateEnergy(this.v);
}
}
export { Moon }import { Moon } from './Moon';
class Space
{
moons : Array<Moon> = [];
add(moon : Moon)
{
this.moons.push(moon);
}
timeStep() : void
{
//update velocity by gravity
let l = this.moons.length;
let velocityChange = (x: number, y: number): number => {
if(x == y) return 0;
return (x < y) ? 1 : -1;
}
for(let i = 0;i < l;i++)
for(let j = i+1;j < l;j++)
{
let m1 : Moon = this.moons[i];
let m2 : Moon = this.moons[j];
//foreach Coordinate
for(let k = 0;k < 3;k++)
{
m1.v[k] += velocityChange(m1.x[k],m2.x[k]);
m2.v[k] += velocityChange(m2.x[k],m1.x[k]);
}
}
//update position
for(let i = 0;i < l;i++)
{
let m : Moon = this.moons[i];
for(let k = 0;k < 3;k++)
{
m.x[k] += m.v[k];
}
}
}
getEnergy() :number {
let energy = 0;
let l = this.moons.length;
for(let i = 0;i < l;i++)
{
let m1 : Moon = this.moons[i];
energy += m1.getPotentialEnergy() * m1.getKineticEnergy();
}
return energy;
}
getDataSet(x : number) : Array<number>
{
let a = [];
let l = this.moons.length;
for(let i = 0;i < l;i++)
{
let m : Moon = this.moons[i];
a.push(m.x[x]);
a.push(m.v[x]);
}
return a;
}
}
export {Space }
Then run 1000 time steps
let space : Space = new Space();
space.add(new Moon({ x: 3, y: 3, z: 0 }));
space.add(new Moon({ x: 4, y: -16, z: 2 }));
space.add(new Moon({ x: -10, y: -6, z: 5 }));
space.add(new Moon({ x: -3, y: 0, z: -13 }));
for(let i = 0;i < 1000;i++)
space.timeStep();
console.log("My puzzle answer is " + space.getEnergy());
Second Star
Second solution tried by brute force. As expected would need very long time before repeating. So I tried with success calculating cycle for each index (because indexes are independent)
let ds0 : any = [];
for(let x = 0;x < 3;x++)
{
ds0[x] = space.getDataSet(x);
}
let i = 0;
let f = 0;
let cycle : Array<number> = [];
while(f < 3)
{
space.timeStep();
i++;
for(let x = 0;x < 3;x++)
{
let ds = space.getDataSet(x);
//compare Arrays in JS simply with JSON.stringify
if(JSON.stringify(ds) == JSON.stringify(ds0[x]))
{
f++;
console.log("found cycle for "+x+" = "+i);
cycle[x] = i;
ds0[x] = []; //clear
}
}
}Furthermore hat to take the divisors into consideration, so I calculated ggt (copied from internet)
/* calculate ggt */
function ggt(a : number,b : number) : number
{
var r : number;
do
{
r = a % b;
a=b;
b=r;
}
while (r>0);
return a;
}
console.log("ggt("+cycle[0]+","+cycle[1]+") = "+ggt(cycle[0],cycle[1]));
console.log("ggt("+cycle[0]+","+cycle[2]+") = "+ggt(cycle[0],cycle[2]));
console.log("ggt("+cycle[2]+","+cycle[1]+") = "+ggt(cycle[2],cycle[1]));
The result I calculated with calctool.de
Day 13: typescript
Care Package
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
First Start
Solved by creating game from IntCode and count the blocks.
import { Computer } from "./Computer";
import { Panel } from "./Panel";
let computer = Computer.load("input.txt");
let panel = new Panel();
while(computer.run());
let output = computer.getOutput();
panel.load(output);
panel.dump();
panel.createImage("images/test",1,"png");
console.log("My puzzle answer is "+panel.count(2));Second Star
Solved by playing the game. Moving the panel synchron to the ball.
import { Computer } from "./Computer";
import { Panel } from "./Panel";
let computer = Computer.load("input.txt");
computer.setMemory(0,2);
let panel = new Panel();
while(computer.run());
let output = computer.getOutput();
computer.clearOutput();
panel.load(output);
panel.dump();
console.log("blocks "+panel.count(2));
for(let x = 0;x < 10000;x++)
{
let b = panel.getBallPosition();
let j = panel.getPadlePosition();
let d = 0;
if(b.x < j.x)
d = -1;
if(b.x > j.x)
d = 1;
computer.setInput(d);
while(computer.run());
let output2 = computer.getOutput();
computer.clearOutput();
panel.load(output2);
panel.dump()
console.log("blocks "+panel.count(2));
console.log("Score "+panel.score);
if(panel.count(2) == 0)
break;
}
console.log("My puzzle answer is "+panel.score);Day 14: typescript
Space Stoichiometry
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
The core algorithm is recursice function wich calculate the consumed ore. Furthermore has a set of leftover chemicals which can used by the following reactions.
calculateOre(cnt : number,chemical : string,rest : ChemicalSet) : number
{
let minore : number = -1;
for(let r of this.reactions[chemical])
{
let ore = 0;
var produce = r.result.cnt;
var factor = 1;
while(produce < cnt)
{
factor++;
produce += r.result.cnt;
}
for(let c of r.inputs)
{
var needCnt = factor * c.cnt;
if(c.name == "ORE")
ore += needCnt;
else
{
let re : number = rest.getCnt(c.name);
if(re >= needCnt)
{
rest.delete(needCnt,c.name);
continue;
}
rest.delete(re,c.name);
ore += this.calculateOre(needCnt - re,c.name,rest);
}
}
if((produce - cnt) > 0)
rest.add(produce -cnt,chemical);
if(minore == -1 || ore < minore)
{
minore = ore;
}
}
//console.log(minore +" ore produce "+cnt+" "+chemical+" zuviel: "+JSON.stringify(rest.count));
return minore;
}First Star
Solved by calling calculateOre
import { NanoFactory} from './NanoFactory';
import { ChemicalSet} from './ChemicalSet';
let factory : NanoFactory = NanoFactory.load("input.txt");
console.log("My puzzle answer is " + factory.calculateOre(1,"FUEL",new ChemicalSet()));Second Star
Second solution solved through finding how much FUEL consumes maximal 1 trillion ORE. Searched with binary search.
import { NanoFactory} from './NanoFactory';
import { ChemicalSet} from './ChemicalSet';
let factory : NanoFactory = NanoFactory.load("input.txt");
let min = 2690379; //Math.round(1000000000000 / 371695);
let max = 5525109;
while(min <= max)
{
let cnt = Math.round((min + max) / 2);
let ore = factory.calculateOre(cnt,"FUEL",new ChemicalSet());
console.log(cnt + " needs "+ore);
console.log(" min "+min);
console.log(" max "+max);
if(ore > 1000000000000)
{
max = cnt - 1;
}
else
{
min = cnt + 1;
}
}
console.log("My puzzle answer is last result");Day 15: typescript
Oxygen System
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
The core Algorithmus is starting from given position and get candidates which are not visited
getCandidates(x : number, y : number,way : Array<number>,visited : any) : Array<any>
{
let candidates : Array<any> = [];
for(let i = 0;i < 4;i++)
{
let direction = this.directions[i];
let xn = x + direction.x;
let yn = y + direction.y;
let k = xn+","+yn;
if(k in visited) continue;
visited[k] = true;
let t = this.getXY(xn,yn);
candidates.push({
x: xn,
y: yn,
w: way.concat([direction.d]),
d: xn * xn + yn * yn,
t : t
});
}
//console.log("get "+x+","+y+" => "+JSON.stringify(candidates));
return candidates;
}With candidates that are not walls search for next candidates.
coordinates = candidates
.filter(item => item.t == 1)
.map((o : any ) => {return { x : o.x, y : o.y , w : o.w }});First Start
Solved by finding nearest (from 0,0) unvisited field und tile computer return 2. Then get length of shortest path from this point to 0,0
Second Star
Solved by create map until no "no visited" filed exists. Then calculate maximal length from oxygen system to each point in the map.
Day 16: typescript
Flawed Frequency Transmission
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
First Star
Implementing algorithm for calulate next sequence straight forward.
next(sequence: number[]) {
let l = sequence.length;
let next: number[] = new Array<number>(sequence.length);
for(let i = 0;i < l;i++)
{
let pattern: Pattern = new Pattern(i+1);
let sum = 0;
let x = 0;
while(x < l)
{
var cmd = pattern.next();
switch(cmd.factor)
{
case 0:
x += cmd.length;
if(x >= l) x = l;
break;
case 1:
for(let j = 0;j < cmd.length && x < l;j++)
sum += sequence[x++];
break;
case -1:
for(let j = 0;j < cmd.length && x < l;j++)
sum -= sequence[x++];
break;
}
}
let n = Math.abs(sum) % 10;
next[i] = n;
}
return next;
}And run it 100 times for given input data.
var fs = require('fs');
import { Calculator } from './Calculator';
let data : string = fs.readFileSync("input.txt").toString('utf-8');
var sequence = data.split("").map(i => parseInt(i));
let calculator : Calculator = new Calculator();
for(let i = 0;i < 100;i++)
sequence = calculator.next(sequence);
console.log("My puzzle answer is " + sequence.join('').substr(0,8));Second Star
When I started algorithm with input repeated 10000 times I quickly realized that the runtime complexity is O(n2) with a real runtime over an hour only called once. Found out that the last numbers only are sum of successors. So implemented optimized algorithm with runtime complexity O(n)
nextOptimized(sequence: number[],offset : number) {
let l = sequence.length;
let next: number[] = new Array<number>(sequence.length);
let sum = 0;
for(let i = l - 1;i >= offset;i--)
{
sum += sequence[i];
let n = Math.abs(sum) % 10;
next[i] = n;
}
return next;
}This I could run 100 times in short time. A good example for showing difference between runtime complexity O(n) and O(n2)
var fs = require('fs');
import { Pattern } from './Pattern';
import { Calculator } from './Calculator';
//6500000;
//5977269;
let data : string = fs.readFileSync("input.txt").toString('utf-8');
var presequence = data.split("").map(i => parseInt(i));
let l = presequence.length;
var sequence = new Array<number>(l * 10000);
for(let i = 0;i < l * 10000;i++)
sequence[i] = presequence[i % l];
let calculator : Calculator = new Calculator();
for(let i = 0;i < 100;i++)
sequence = calculator.nextOptimized(sequence,5977269);
console.log("My puzzle answer is " + sequence.slice(5977269,5977300).join('').substr(0,8));Day 17: typescript
Set and Forget
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution1find.js node dist/solution2.js
First Start
Implement Panel class for load output to x-y-field data structure and calulate alignment.
load(input: number[]) {
let x = 0;
let y = 0;
for(let c of input)
{
if(c == 10)
{
this.width = Math.max(x,this.width);
x = 0;
y++;
continue;
}
if(c != 35 && c != 46)
{
console.log(x+","+y+" = "+c);
}
this.setColorXY(x,y,c);
x++;
}
this.height = y;
}
getIntersectionAlignmentSum() {
let sum = 0;
for(let y = 0;y <= this.height;y++)
{
for(let x = 0;x <= this.width;x++)
{
if(this.isIntersection(x,y))
sum += x * y;
}
}
return sum;
}Second Star
First resolved path along the scaffold under the assumption, the robot would always run straight on for as long as possible.
getPath(): string {
let cmd :string = "L";
let d = { x : -1, y : 0 }
let x = 46;
let y = 50;
while(true)
{
//go forward
let l = 0;
while(this.is(x + d.x, y +d.y,35))
{
x += d.x;
y += d.y;
l++;
}
cmd += ","+l;
//get possible direction from this position
let vd = [];
if(this.is(x + 1,y,35))
vd.push({ x : 1, y : 0 });
if(this.is(x - 1,y,35))
vd.push({ x : -1, y : 0 });
if(this.is(x,y+1,35))
vd.push( {x : 0, y : 1 });
if(this.is(x,y-1,35))
vd.push({ x : 0, y : -1 });
//Ende
if(vd.length == 1)
{
console.log("End found");
break;
}
if(vd.length != 2)
throw Error(JSON.stringify(vd));
vd = vd.filter(i => Math.abs(d.x + i.x) == 1 && Math.abs(d.y + i.y) == 1);
if(vd.length != 1)
throw Error(JSON.stringify(vd));
let nd = vd[0];
if(d.x == -1 && nd.y == -1) cmd +=",R";
if(d.x == -1 && nd.y == 1) cmd +=",L";
if(d.x == 1 && nd.y == -1) cmd +=",L";
if(d.x == 1 && nd.y == 1) cmd +=",R";
if(d.y == -1 && nd.x == -1) cmd +=",L";
if(d.y == -1 && nd.x == 1) cmd +=",R";
if(d.y == 1 && nd.x == -1) cmd +=",R";
if(d.y == 1 && nd.x == 1) cmd +=",L";
d = nd;
}
return cmd;
}Result tested manually for pattern and noticed that’a a possible solution.
L,8,R,10,L,8,R,8, L,12,R,8,R,8, L,8,R,10,L,8,R,8, L,8,R,6,R,6,R,10,L,8, L,8,R,6,R,6,R,10,L,8,L,8,R,10,L,8,R,8, L,12,R,8,R,8, L,8,R,6,R,6,R,10,L,8, L,12,R,8,R,8, L,12,R,8,R,8
which could be split into submodules
A,B,A,C,C,A,B,C,B,B
This used for computer input
let computer = Computer.load("input.txt");
computer.program.set(0,2);
let command = "A,B,A,C,C,A,B,C,B,B\n";
command += "L,8,R,10,L,8,R,8\n";
command += "L,12,R,8,R,8\n";
command += "L,8,R,6,R,6,R,10,L,8\n";
command += "n\n"; //y/n
for(let i = 0;i < command.length;i++)
computer.setInput(command.charCodeAt(i));
while(computer.run());
console.log("My puzzle answer is "+computer.getLastOutput());Day 18: typescript
Many-Worlds Interpretation
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
I found an approach to search shortest path from start position, by iterate over each reachable key from a node. But this approach has runtime of O(n!). So had to cheat a little bit and found optimation with cache.
The combinations after passing through the three nodes a,b,c and from node c are the same
@ → a → b → c
@ → b → a → c
let cacheK = n + "-" +visited.sort().join(",");
if(cacheK in this.cache)
{
return this.cache[cacheK];
}With this approach found solution within seconds.
First Star
Solved by searching shortest path with all nodes.
Second Star
Second solution solved by search for path in each separate sections assuming that the missing keys for doors collected by the others robots.
Day 19: typescript
Tractor Beam
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
First Start
Simple run for the 50x50 grid and count the digits "1".
import { Computer } from "./Computer";
import { Panel } from "./Panel";
let panel = new Panel();
let one = 0;
let zeros = 0;
for(let y = 0;y < 50;y++)
for(let x = 0;x < 50;x++)
{
let computer = Computer.load("input.txt");
computer.setInput(x);
computer.setInput(y);
while(computer.run());
let output = computer.getLastOutput();
if(output == 1)
one++;
panel.setXY(x,y,output)
}
panel.dump();
console.log("My puzzle answer is "+one);Second Star
Scanned for each line the width of tractor and the x Positions. Then check if square fits.
import { Computer } from "./Computer";
import { Panel } from "./Panel";
import { SIGUSR1 } from "constants";
let panel = new Panel();
function scan(x : number,y : number) : number {
let computer = Computer.load("input.txt");
computer.setInput(x);
computer.setInput(y);
while(computer.run());
return computer.getLastOutput();
}
function scanWidth(x : number,y : number) : any {
let x0 : number = x;
let x1 : number = x;
while(scan(x0 -1,y) == 1) x0--;
while(scan(x1 +1,y) == 1) x1++;
//..xxx..
//0123456 x0 = 2 , x1 = 4
return {
x0 : x0,
x1 : x1,
w: x1 - x0 + 1,
}
}
let y = 1700;
while(true)
{
y+= 1;
let x = Math.round(y/100 * 61);
let o = scan(x,y);
if(o != 1)
{
throw new Error("out of tractor");
}
let s = scanWidth(x,y);
let x2 = Math.round((y+99)/100 * 61);
let s2 = scanWidth(x2,y+99);
let w = s.x1 - s2.x0 + 1;
console.log(x+","+y+" "+x2+","+(y+99)+" w:"+w+" h:"+(y +99 -y +1)+" "+JSON.stringify(s)+"/"+JSON.stringify(s2));
if(w >= 100)
{
console.log(s2.x0+","+y);
console.log("My puzzle answer is "+(s2.x0 * 10000 + y));
break;
}
}Day 20: typescript
Donut Maze
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
First Star
Created Maze and searched shortest path with BFS. Created function getNext for next reachable filed with distance 1.
getNext(u: { x: number; y: number; }): { x: number; y: number; }[] {
let next : { x: number; y: number; }[] = [];
for(let d of [{ x : 0, y: 1} , { x : 0, y: -1},{ x : 1, y: 0},{ x : -1, y: 0}])
{
let v = { x: u.x + d.x , y: u.y + d.y};
let vk = v.x +","+ v.y;
let vp = this.portals[vk];
if(vp)
{
//Partner - Portal
let p2 : any = Object.values(this.portals)
.filter((p : any) => p.portal == vp.portal
&& ((p.coords[0].x != vp.coords[0].x) || (p.coords[0].y != vp.coords[0].y)))[0];
if(p2)
{
//hat ein Partner Portal
console.log(JSON.stringify(vp) +" => "+JSON.stringify(p2));
for(let coords of p2.coords)
{
let c = { x: coords.x , y: coords.y };
for(let d2 of [{ x : 0, y: 1} , { x : 0, y: -1},{ x : 1, y: 0},{ x : -1, y: 0}])
{
let v2 = { x: c.x + d2.x , y: c.y + d2.y};
let v2k = v2.x +","+ v2.y;
let v2p = this.portals[v2k];
if(v2p) continue;
next.push(v2);
}
}
//ignore ist schon erreicht
continue;
}
}
next.push(v);
}
return next;
}Second Star
Created recursive Maze and searched shortest path with BFS. Changed getNext for this Maze.
getNext(u: { x: number; y: number; l:number;}): {x: number; y: number; l:number;}[] {
let next : { x: number; y: number;l:number; }[] = [];
for(let d of [{ x : 0, y: 1} , { x : 0, y: -1},{ x : 1, y: 0},{ x : -1, y: 0}])
{
let v = { x: u.x + d.x , y: u.y + d.y, l: u.l};
let vk = v.x +","+ v.y;
let vp = this.portals[vk];
if(this.exists(vp,u.l))
{
let nextLevel = vp.inside ? u.l + 1 : u.l - 1;
//Partner - Portal
let p2 : any = Object.values(this.portals)
.filter((p : any) => p.portal == vp.portal
&& ((p.coords[0].x != vp.coords[0].x) || (p.coords[0].y != vp.coords[0].y)))[0];
if(this.exists(p2,nextLevel))
{
//hat ein Partner Portal
//console.log(JSON.stringify(vp) +" => "+JSON.stringify(p2));
for(let coords of p2.coords)
{
let c = { x: coords.x , y: coords.y };
for(let d2 of [{ x : 0, y: 1} , { x : 0, y: -1},{ x : 1, y: 0},{ x : -1, y: 0}])
{
let v2 = { x: c.x + d2.x , y: c.y + d2.y, l: nextLevel };
let v2k = v2.x +","+ v2.y;
let v2p = this.portals[v2k];
if(v2p) continue;
next.push(v2);
}
}
//ignore ist schon erreicht
continue;
}
}
next.push(v);
}
return next;
}Day 21: typescript
Springdroid Adventure
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution1find.js node dist/solution2.js
First I programmed the Aft Scaffolding Control and Information Interface, hoping that it might be used again
import { Computer } from "./Computer";
class ASCII
{
computer: Computer;
constructor(computer : Computer)
{
this.computer = computer;
}
sendCommand(command: string) {
for(let i = 0;i < command.length;i++) {
this.computer.setInput(command.charCodeAt(i));
}
this.computer.setInput(10); // \n
}
step() {
while(this.computer.run());
let output = this.computer.getOutput();
//Print
let line : string = "";
for(let c of output)
{
if(c > 256)
{
console.log("Big number "+c);
}
if(c == 10)
{
console.log(line);
line = "";
continue;
}
line += String.fromCharCode(c);
}
}
}
export { ASCII }
First Start
I thought about the solution theoretically on the drive to IKEA. After returning home, it also worked.
import { Computer } from "./Computer";
import { ASCII } from "./ASCII";
let computer = Computer.load("input.txt");
let ascii = new ASCII(computer);
/*
T, the temporary value register
J, the jump register
one tile away (A)
two tiles away (B)
three tiles away (C)
four tiles away (D)
@ABCD
#xxx# (jump if D == 1 and A or B or C == 0)
(!A || !B || !C) && D
*/
// !A || !B
ascii.sendCommand("NOT A J");
ascii.sendCommand("NOT B T");
ascii.sendCommand("OR T J");
// !C || J
ascii.sendCommand("NOT C T");
ascii.sendCommand("OR T J");
// !!D && J
ascii.sendCommand("NOT D T");
ascii.sendCommand("NOT T T");
ascii.sendCommand("AND T J");
ascii.sendCommand("WALK");
ascii.step();
console.log("My puzzle answer is the big number");Second Star
Same approach as solution one. I tried a bit to find the cases and derived the logical form. I had to shorten this one a little bit because there was not enough memory.
import { Computer } from "./Computer";
import { ASCII } from "./ASCII";
let computer = Computer.load("input.txt");
let ascii = new ASCII(computer);
/*
T, the temporary value register
J, the jump register
one tile to nine tiles away (A) -> (I)
0123456789
@ABCDEFGHI
#xxx######
#xxx#xxx##
#xxx##xxx#
#xxx###xxx
(!A || !B || !C) && D && (H || (E && I) || (E && F)) => To long
(!A || !B || !C) && D && (H || (E && (I || F))
*/
// !A || !B
ascii.sendCommand("NOT A J");
ascii.sendCommand("NOT B T");
ascii.sendCommand("OR T J");
// !C || J
ascii.sendCommand("NOT C T");
ascii.sendCommand("OR T J");
// !!D && J
ascii.sendCommand("NOT D T");
ascii.sendCommand("NOT T T");
ascii.sendCommand("AND T J");
//(I || F)
ascii.sendCommand("NOT I T");
ascii.sendCommand("NOT T T");
ascii.sendCommand("OR F T");
// && E
ascii.sendCommand("AND E T");
// || H
ascii.sendCommand("OR H T");
ascii.sendCommand("AND T J");
ascii.sendCommand("RUN");
ascii.step();
console.log("My puzzle answer is the big number");Day 22: typescript
Slam Shuffle
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
First Star
Solved by implementing the shuffle service and searching for 2019.
import { SpaceCards } from './SpaceCards';
class ShuffleService
{
newStack(cards: SpaceCards): SpaceCards {
let ncards: SpaceCards = new SpaceCards(cards.size);
for(let i = 0;i < cards.size;i++)
{
ncards.cards[cards.size -1 - i] = cards.cards[i];
}
return ncards;
}
cut(cards: SpaceCards, n: number) : SpaceCards {
//console.log("cut "+n);
let ncards: SpaceCards = new SpaceCards(cards.size);
for(let i = 0;i < cards.size;i++)
{
ncards.cards[(cards.size - n + i) % cards.size] = cards.cards[i];
}
return ncards;
}
increment(cards: SpaceCards, incr: number): SpaceCards {
//console.log("deal with increment "+incr);
let ncards: SpaceCards = new SpaceCards(cards.size);
for(let i = 0;i < cards.size;i++)
{
ncards.cards[(i * incr) % cards.size] = cards.cards[i];
}
return ncards;
}
shuffle(cards: SpaceCards, commands: string[]): SpaceCards {
for(let cmd of commands)
{
let p : string[] = cmd.split(" ");
if(p[3] == "stack")
cards = this.newStack(cards);
if(p[0] == "cut")
cards = this.cut(cards,parseInt(p[1]));
if(p[2] == "increment")
cards = this.increment(cards,parseInt(p[3]));
}
return cards;
}
}
export { ShuffleService }Second Star
I knew that 119315717514047 space cards shuffling 101741582076661 times is not solvable with the solution for star 1. I realized that the transformation of one shuffling process could used for for each loop. Furthermore, it is not necessary to calculate the whole array to determine the position. But I not found an approach for reduce loop count. So I had to cheat again. I’ve found an approch and will explain it here.
All three transformations are invertible and composition of all inverted transformation is posible. We calculate the mapping for one inverted shuffle process.
let a : number = 1;
let b : number = 0;
for(let i = input.length - 1;i >= 0;i--)
{
let p : string[] = input[i].split(" ");
if(p[3] == "stack")
{
// pos = N - pos
a = (N - a) % N;
b = (N + N - b - 1) % N;
}
if(p[0] == "cut")
{
let cut = parseInt(p[1]);
b = ((b + cut) %N + N )% N;
}
if(p[2] == "increment")
{
let incr = parseInt(p[3]);
a = modDiv(a, incr, N);
b = modDiv(b, incr, N);
}
};Than calculate result with fast exponentiation.
while (rep) {
if (rep % 2) x = (mulMod(x,a,N) + b) % N;
let a1 = mulMod(a,a,N);
b = (mulMod(a,b,N) + b) % N;
a = a1;
rep = Math.floor(rep / 2);
}
return x;Day 23: typescript
Category Six
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
First Start
Straight forward programming of Network.
import { Computer } from "./Computer";
//init computers and queues
let queues : any = {};
let computers = [];
for(let c = 0;c < 50;c++)
{
computers[c] = Computer.load("input.txt");
computers[c].setInput(c); //Set network adresee
queues[c] = [[c, -1,-1]];
}
queues[255] = [];
while(true)
{
for(let c = 0;c < 50;c++)
{
let computer = computers[c];
//Send packets or -1
if(queues[c].length > 0)
{
let p = queues[c].shift();
computer.setInput(p[1]);
computer.setInput(p[2]);
}
else
{
computer.setInput(-1);
}
while(computer.run());
//Receive packets
let output = computer.getOutput();
for(let x = 0;x < output.length;x+=3)
{
let p = [ output[x] , output[x+1],output[x+2]];
let a = p[0];
queues[a].push(p);
}
computer.clearOutput();
}
if(queues[255].length > 0)
{
console.log("My puzzle answer is "+queues[255][0][2]);
break;
}
}Second Star
“What is the first Y value delivered by the NAT to the computer at address 0 twice in a row?”
After I understood that it is about the sent and not received packets, the solution was also simple. :-)
import { Computer } from "./Computer";
let queues : any = {};
let computers = [];
for(let c = 0;c < 50;c++)
{
computers[c] = Computer.load("input.txt");
computers[c].setInput(c); //Set network adresee
queues[c] = [[c, -1,-1]];
}
queues[255] = [];
let lastNaty = -1;
while(true)
{
for(let c = 0;c < 50;c++)
{
let computer = computers[c];
if(queues[c].length > 0)
{
let p = queues[c].shift();
computer.setInput(p[1]);
computer.setInput(p[2]);
}
else
{
computer.setInput(-1);
}
while(computer.run());
let output = computer.getOutput();
for(let x = 0;x < output.length;x+=3)
{
let p = [ output[x] , output[x+1],output[x+2]];
let a = p[0];
queues[a].push(p);
}
computer.clearOutput();
}
let packets = 0;
for(let k of Object.keys(queues))
{
if(k == '255') continue;
packets += queues[k].length;
}
if(packets == 0)
{
let i = queues[255].length - 1;
if(queues[255][i][2] == lastNaty)
{
console.log("My puzzle answer is "+lastNaty);
break;
}
queues[0].push([ 0 , queues[255][i][1],queues[255][i][2]]);
lastNaty = queues[255][i][2];
}
}Day 24: typescript
Planet of Discord
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js node dist/solution2.js
First Star
Implemented Eris.
class Eris {
height: number;
width: number;
grid: any = {};
load(rows : string[]) : void
{
this.height = rows.length;
this.width = rows[0].length;
for(let y = 0;y < this.height;y++)
{
let cells : string[] = rows[y].split('');
for(let x = 0;x < this.width;x++)
{
this.set(x,y,cells[x]);
}
}
}
set(x: number, y: number, t: string) {
this.grid[x+","+y] = t;
}
next(): Eris {
let next : Eris = new Eris();
next.width = this.width;
next.height = this.height;
for(let y = 0;y < this.height;y++)
{
for(let x = 0;x < this.width;x++)
{
let bugs : number = this.countBugs(x,y);
if(this.isBug(x,y))
{
if(bugs != 1) //bug dies
next.set(x,y,".");
else
next.set(x,y,"#");
}
else
{
if(bugs == 1 || bugs == 2) //becomes infested
next.set(x,y,"#");
else
next.set(x,y,".");
}
}
}
return next;
}
isBug(x: number, y: number) : boolean {
let k : string = x+","+y;
return ((k in this.grid) && (this.grid[k] == '#'));
}
countBugs(x: number, y: number): number {
let bugs = 0;
for(let d of [{ x: 1, y : 0 },{ x: -1, y : 0 },{ x: 0, y : 1 },{ x: 0, y : -1 }])
{
if(this.isBug(x + d.x,y + d.y))
bugs++;
}
return bugs;
}
biodiversity(): number {
let b = 0;
let i = 0;
for(let y = 0;y < this.height;y++)
{
for(let x = 0;x < this.width;x++)
{
if(this.isBug(x,y))
{
b += Math.pow(2,i);
}
i++;
}
}
return b;
}
dump() : void
{
for(let y = 0;y < this.height;y++)
{
let line = "";
for(let x = 0;x < this.width;x++)
{
line += this.grid[x+","+y];
}
console.log(line);
}
}
}
export {Eris }For finding first layout that appears twice used biodiversity rating because is unique for each layout.
import { Eris } from './Eris';
let eris : Eris = new Eris();
eris.load([
"#.###",
".....",
"#..#.",
"##.##",
"..#.#"]);
let cache : any = {};
while(true)
{
let b : number = eris.biodiversity();
if(b in cache)
{
eris.dump();
console.log("My puzzle answer is " + b);
break;
}
cache[b] = true;
eris = eris.next();
}
Second Star
Implemented RecursiveEris.
class Eris {
height: number;
width: number;
grid: any = {};
load(rows : string[]) : void
{
this.height = rows.length;
this.width = rows[0].length;
for(let y = 0;y < this.height;y++)
{
let cells : string[] = rows[y].split('');
for(let x = 0;x < this.width;x++)
{
this.set(x,y,cells[x]);
}
}
}
set(x: number, y: number, t: string) {
this.grid[x+","+y] = t;
}
next(): Eris {
let next : Eris = new Eris();
next.width = this.width;
next.height = this.height;
for(let y = 0;y < this.height;y++)
{
for(let x = 0;x < this.width;x++)
{
let bugs : number = this.countBugs(x,y);
if(this.isBug(x,y))
{
if(bugs != 1) //bug dies
next.set(x,y,".");
else
next.set(x,y,"#");
}
else
{
if(bugs == 1 || bugs == 2) //becomes infested
next.set(x,y,"#");
else
next.set(x,y,".");
}
}
}
return next;
}
isBug(x: number, y: number) : boolean {
let k : string = x+","+y;
return ((k in this.grid) && (this.grid[k] == '#'));
}
countBugs(x: number, y: number): number {
let bugs = 0;
for(let d of [{ x: 1, y : 0 },{ x: -1, y : 0 },{ x: 0, y : 1 },{ x: 0, y : -1 }])
{
if(this.isBug(x + d.x,y + d.y))
bugs++;
}
return bugs;
}
biodiversity(): number {
let b = 0;
let i = 0;
for(let y = 0;y < this.height;y++)
{
for(let x = 0;x < this.width;x++)
{
if(this.isBug(x,y))
{
b += Math.pow(2,i);
}
i++;
}
}
return b;
}
dump() : void
{
for(let y = 0;y < this.height;y++)
{
let line = "";
for(let x = 0;x < this.width;x++)
{
line += this.grid[x+","+y];
}
console.log(line);
}
}
}
export {Eris }Run it 200 times and count bugs.
import { RecursiveEris } from './RecursiveEris';
let eris : RecursiveEris = new RecursiveEris();
eris.load([
"#.###",
".....",
"#..#.",
"##.##",
"..#.#"]);
for(let i = 0;i < 200;i++)
eris = eris.next();
console.log("My puzzle answer is " + eris.countAllBugs());Day 25: typescript
Cryostasis
The solutions are written in Typescript. To run them use the following commands.
npm install gulp node dist/solution1.js
First Start
First I explored the ship and take the items. Don’t take all, especially not the infinity loop.
for(let xx = 0;xx < 100;xx++)
{
let explore : any[] = ascii.step();
map.explore(explore);
for(let item of map.getItems())
{
if(item == "infinite loop") continue;
if(item == "giant electromagnet") continue;
if(item == "escape pod") continue;
if(item == "photons") continue;
if(item == "molten lava") continue;
ascii.sendCommand("take "+item);
let explore : any[] = ascii.step();
console.log("take "+item+" "+JSON.stringify(explore));
}
//Move
let direction = map.nextUnexplored();
console.log("go to "+direction);
if(direction == undefined)
{
break;
}
ascii.sendCommand(direction);
}Than go to the "Security Checkpoint".
let path = map.getPathTo("Security Checkpoint");
for(let dir of path)
{
ascii.sendCommand(dir);
let explore : any[] = ascii.step();
map.explore(explore);
}And test all combinations of items to pass.
let items = ["pointer" ,"hypercube","cake","tambourine","monolith","mouse","coin","mug" ];
//drop all items
for(let i = 0;i < items.length;i++)
{
ascii.sendCommand("drop "+items[i]);
ascii.step();
}
let l = Math.pow(2,items.length);
for(let c = 0;c < l;c++)
{
let testitems = [];
for (var j=0;j<items.length;j++) {
if ((c & Math.pow(2,j))){
testitems.push(items[j]);
}
}
console.log(c+" test with "+testitems);
//take
for(let i = 0;i < testitems.length;i++)
{
ascii.sendCommand("take "+testitems[i]);
ascii.step();
}
ascii.sendCommand("north");
let explore : any[] = ascii.step();
map.explore(explore);
if(map.room != "Security Checkpoint") break;
//drop
for(let i = 0;i < testitems.length;i++)
{
ascii.sendCommand("drop "+testitems[i]);
ascii.step();
}
}Second Star
Nothing to do. :-)