[Advent of Code] Day 1: Chronal Calibration

[lpatmo]

https://adventofcode.com/2018/day/1

"We've detected some temporal anomalies," one of Santa's Elves at the Temporal Anomaly Research and Detection Instrument Station tells you. She sounded pretty worried when she called you down here. "At 500-year intervals into the past, someone has been changing Santa's history!"

"The good news is that the changes won't propagate to our time stream for another 25 days, and we have a device" - she attaches something to your wrist - "that will let you fix the changes with no such propagation delay. It's configured to send you 500 years further into the past every few days; that was the best we could do on such short notice."

"The bad news is that we are detecting roughly fifty anomalies throughout time; the device will indicate fixed anomalies with stars. The other bad news is that we only have one device and you're the best person for the job! Good lu--" She taps a button on the device and you suddenly feel like you're falling. To save Christmas, you need to get all fifty stars by December 25th.

Collect stars by solving puzzles. Two puzzles will be made available on each day in the advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

After feeling like you've been falling for a few minutes, you look at the device's tiny screen. "Error: Device must be calibrated before first use. Frequency drift detected. Cannot maintain destination lock." Below the message, the device shows a sequence of changes in frequency (your puzzle input). A value like +6 means the current frequency increases by 6; a value like -3 means the current frequency decreases by 3.

For example, if the device displays frequency changes of +1, -2, +3, +1, then starting from a frequency of zero, the following changes would occur:

Current frequency 0, change of +1; resulting frequency 1. Current frequency 1, change of -2; resulting frequency -1. Current frequency -1, change of +3; resulting frequency 2. Current frequency 2, change of +1; resulting frequency 3. In this example, the resulting frequency is 3.

Here are other example situations:

+1, +1, +1 results in 3 +1, +1, -2 results in 0 -1, -2, -3 results in -6 Starting with a frequency of zero, what is the resulting frequency after all of the changes in frequency have been applied?

[billglover]

My solution: github.com/billglover/aoc/tree/master/2018/01

• solution takes an io.Reader interface rather than a file to enable testing
• I started off trying to avoid reading everything into memory at once, hence bufio.Scanner in part 1
• part 2 requires the sequence of adjustments to be held in memory, hence ioutil.ReadAll

What I learned: bufio.Scanner provides a simple interface for scanning through an io.Reader line by line. It trips up if you need the ability to seek through the contents or adjust your position in the underlying data.

[ISPOL]

https://repl.it/@ISPOL/AdventOfCode2018 Python solution(takes a filepath as input)

[gauravchl]

javaScript Solution:

const fs = require('fs');
const input = fs.readFileSync('./day1.input', {encoding : 'utf8'});

function getResultingFrequency(input) {
  const frequencies = input.trim().split('\n');
  return frequencies.reduce((a, b) => (parseInt(a) + parseInt(b)))
};

console.log('Resulting Frequency:', getResultingFrequency(input));

https://github.com/gauravchl/sourcecode/blob/master/adventofcode/day1.js

[gauravchl]

Part 2 solution in JS:

function getFirstRepeatingFrequency(input) {
  const frequencies = input.trim().split('\n');

  const frequencyRecord = [0];
  let currentFrequency = 0;
  let index = 0;

  while(1) {
    currentFrequency = currentFrequency + parseInt(frequencies[index]);
    if (frequencyRecord.indexOf(currentFrequency) > -1) {
      break;
    }
    frequencyRecord.push(currentFrequency);
    index = index === frequencies.length - 1 ? 0 : index + 1;
  }
  return currentFrequency;
}

[gauravchl]

The JS solution above for part 2 is taking about 12 seconds to calculate the answer, wondering the performance of other solutions posted above 🤔

[billglover]

I’m getting 0.037s for both parts combined when run against the puzzle input.

[billglover]

When testing to see if something exists in an array, your code has to search through every item in the array. As you store all frequencies seen, this looks like it might be O(n!).

My understanding of O notation is limited so corrections welcome.

[ZoranPandovski]

Check the solution in Assembly :) https://github.com/natemago/adventofcode2018/tree/master/day1-chronal-calibration

[billglover]

Nice work.

What assembly is this? i.e can I run it?

What do the square brackets do in a statement like this: MOV r14 [RDX]

[ZoranPandovski]

@billglover To be honest, I am not very familiar with assembly. This guy is my friend, and he will solve all of the 25 days in 25 different languages :)

[gauravchl]

@billglover You are right! I was using an array to keep the record of old frequencies and searching in an array using indexOf was super expensive!

I replaced the array with javascript Set() and performance improved like a rocket! From 12 seconds to 0.036.

updated solution:

function getFirstRepeatingFrequency(input) {
  const frequencies = input.trim().split('\n');
  const frequencyRecord = new Set([0]);
  let currentFrequency = 0;
  let index = 0;

  while(1) {
    currentFrequency = currentFrequency + parseInt(frequencies[index]);
    if (frequencyRecord.has(currentFrequency)) {
      break;
    }
    frequencyRecord.add(currentFrequency);
    index = index === frequencies.length - 1 ? 0 : index + 1;
  }
  return currentFrequency;
}

[lalaithan]

This was my Day 1, Pt 2 in Js/Node:

const fs = require('fs');

const datas = fs.readFileSync('input.txt', 'utf-8');
let currFrequency = new Set();

const changes = datas.split(/\n|\r/m)
    .map(Number);

let frequency = 0;
let i = 0;

while (true) {
    frequency += changes[i];
    if (currFrequency.has(frequency)) {
        console.log(frequency);
        break;
    }
    currFrequency.add(frequency);
    i = i === changes.length - 1 ? 0 : i + 1;
}