DEV Community

Cover image for AoC Day 1: Chronal Calibration
Ryan Palo
Ryan Palo

Posted on • Updated on

AoC Day 1: Chronal Calibration

Overview

After my post last night, @aspittel suggested that we start a daily discussion post chain for these challenges. I think that's a neat idea, and significantly more efficient than everyone saying "Hey check out my git repo!"

I'm excited about this year's Advent mission, time traveling to save Christmas! This will be a place for discussing today's problem, Chronal Calibration. We're tasked with calibrating our time travel device by adding up sequential integers.

On a side note, if you get some extra time, it's probably a good idea to set up some infrastructure for reading input text from a file, because almost all of last year's challenges gave a few simpler examples (good for writing some basic tests) and then a huge-ish input given as a multiline plaintext file.

If you haven't solved today's puzzle yet, stop reading now, because I'm going to post my solution here. If you have finished a solution, post it in the comments! Also feel free to give (loving, instructional, nice) feedback to others' solutions to help them read better or run faster. I've seen a few people that are using this opportunity to learn a new language, so if you see something that works but isn't idiomatic to your favorite language, go ahead and offer suggestions! This includes me, since I'm just learning Rust, so I'm sure it's going to be a mixture of poorly translated Python-isms and gobbledygook.

My Solution

// day1.rs

/// Given a bunch of integers (changes in frequency), one per line,
/// calculate the final sum
pub fn final_frequency(text: &str) -> i32 {
    text.lines()
        .map(|value: &str| -> i32 {value.parse().expect("Not a number")})
        .sum()
}

/// Given a bunch of integers (changes in frequency), one per line,
/// calculate the running sum until you hit a cumulative sum that you've
/// seen before.  Return that first repeated cumulative sum.
pub fn first_duplicate_frequency(text: &str) -> i32 {
    let mut history = vec![0];
    let mut total = 0;
    for line in text.lines().cycle() {
        let value: i32 = line.parse().expect("Not a number.");
        total += value;
        if history.contains(&total) {
            return total;
        }
        history.push(total);
    }
    return 0;
}

#[cfg(test)]
mod tests {
    use super::final_frequency;
    use super::first_duplicate_frequency;

    #[test]
    fn final_all_positives() {
        assert_eq!(3, final_frequency("+1\n+1\n+1"));
    }

    // More tests...
Enter fullscreen mode Exit fullscreen mode
// main.rs

// This file will change day to day as I just use it to exercise each day's module.

use std::fs::File;
use std::io::prelude::*;

mod day1;

fn main() {

    let mut input = File::open("data/day1.txt").expect("File not found.");

    let mut contents = String::new();
    input.read_to_string(&mut contents).expect("Couldn't read file.");
    println!("{}", day1::first_duplicate_frequency(&contents));
}
Enter fullscreen mode Exit fullscreen mode

DEV Leaderboards

Lastly, I created a "private" leaderboard for DEV.to, in case anyone's interested. Apparently, they only hold 200 people per leaderboard, though, so first-come-first serve. Obviously, there are waaaay more than 200 people in the DEV family, so if you get there and the room is full, feel free to create your own on the Advent of Code site and post your room code in the comments. If I see somebody post a room code, I'll do my best to edit my post and copy it below, but read through the comments just in case I miss it.

Happy-- I mean, Merry Coding! I'm excited to see what people think.

@rpalo: 224198-25048a19

Latest comments (73)

Collapse
 
ash1eyish profile image
Ashley Maria

Pt 2 JS/Node Solution:

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;
}
Collapse
 
arjunrajkumar profile image
Arjun Rajkumar • Edited

Hi Ryan.. Just starting on the #adventofcode series.

Just curious how you are reading the inputs. E.g. first problem says the input is on adventofcode.com/2018/day/1/input

Do you parse the page to get the inputs?
Or copy/paste and store it as a file? Sorry if this sounds dumb.. But am wondering how you are downloading the file?

Thanks

Collapse
 
rpalo profile image
Ryan Palo

No problem! That would be slick to have it download the page for me, but I just go to the link and copy the text. I've got a directory in my project called data, and each day's input as day1.txt, day2.txt, etc. Then I just change the filename that I'm reading.

Let me know if this helps or if you have other questions :)

Collapse
 
arjunrajkumar profile image
Arjun Rajkumar

Thanks. The data folder makes sense.

Collapse
 
wuz profile image
Conlin Durbin

A little late to starting on this, but I am excited to get going!

JS

Part 1 (A little bit trolly)

var fs = require('fs');

fs.readFile('./numbers.txt', 'utf8', function(err, contents) {
  console.log(eval(contents));
});

Part 2 (could probably use some optimizations)

var fs = require('fs');

const hash = {};

fs.readFile('./numbers.txt', 'utf8', function(err, contents) {
  const lines = contents.split('\n');
  let current = 0;
  let i = 0;
  while(true) {
    if(i === lines.length-1) {
      i = 0;
    }
    const line = lines[i];
    const old = current;
    const num = Number(line)
    current += num;
    if(hash[current]) {
      console.log(current);
      break;
    }
    hash[current] = true;
    console.log(old, '+', num, '->', current);
    i++;
  }
});

Collapse
 
ikirker profile image
Ian Kirker

This seemed easiest to do in awk:

Part 1
BEGIN {
    f = 0
}

{
    f += $1
}

END {
    print f
}
awk -f 1.1.awk 1.1.input
Part 2

awk's arrays are basically hashes/associative arrays, so you can just use the frequencies as keys much like the Python dictionary solutions. Because awk is really focused on processing a list of files, this uses a hack on the built-in variable that tracks where on that list awk has gotten to, so it only stops once it's found the duplicate.

BEGIN {
    f = 0
    a[0] = 1
}

{
    f += $1
    if (f in a) {
        a[f] += 1
    } else {
        a[f] = 1
    }
    if (a[f] == 2) {
        print(f)
        exit 0
    }
    # Resets what file is the next to process
    ARGIND=0
}
awk -f 1.2.awk 1.2.input
Collapse
 
alankyeung profile image
ɓunǝ⅄ uɐl∀

I just wanted to confess that Day 1 Part 1 I just used a spreadsheet. That got the answer, but then I used my program to proceed.

Collapse
 
rpalo profile image
Ryan Palo

Honestly, you could argue that Excel is a highly parallel GUI-based programming tool. I’d say that’s fair. 😀

Collapse
 
roeekl profile image
roeekl • Edited

C#

Part 1

Console.WriteLine(File.ReadAllLines(@".\day1_input.txt").Sum(s => int.Parse(s)));

Part 2

int[] input = File.ReadAllLines(@".\day1_input.txt").Select(s => int.Parse(s)).ToArray();
HashSet<int> set = new HashSet<int>();
int freq = 0;
for (int i = 0; set.Add(freq = freq + input[i % input.Length]); i++) ;
Console.WriteLine(freq);
Collapse
 
macshome profile image
Josh Wisenbaker

Hmm... I just took the input and stuck it in an array rather than reading it from disk. That's not hard to do in Swift though, maybe I'll go back and add in the file loading.

In any case, here is what I did in my Playground!

Swift

Part 1

This one was super easy in Swift via it's reduce(_:_:) function. Given that I had the Ints in an Array, it was a one liner. I added some context to the output because why not?

print("The final calculated frequency is: \(frequencyInput.reduce(0,+))")

For those of you new to Swift, this version of reduce has two inputs. The first one is the starting value for the accumulator and the second is the closure of what to do with the values from the collection. This is simply a shorthand syntax for adding all the values in a collection together and returning it. The long version looks like this:

let frequency = frequencyInput.reduce(0, { x, y in
    x + y
})
Part 2

This part was a bit tougher and my first attempt had all kinds of bad smells like breaking to function labels and such. Eventually I wrapped it all up in a closure that takes an Array of Int values and then returns a single Int with the first repeated number.

/// A closure that takes an `Array` of `Int` values and adds them together in a loop. Upon finding the first repeated
/// value it breaks and returns.
let findRepeatedFrequency = {(_ inputArray: [Int]) -> Int in
    var accumilated = 0
    var frequencies = Set<Int>()
    while true {
        for skew in inputArray {
            accumilated += skew
            if frequencies.contains(accumilated) {
                return accumilated
            }
            frequencies.insert(accumilated)
        }
    }
}

print("The first repeated frequency is: \(findRepeatedFrequency(frequencyInput))")

Essentially this is a for-loop version of the reduce operation, but then I also maintain a history of the values in a Set and check to see if this is a value we've run into before.

I solved the second one with a closure instead of a regular function because I've been teaching myself more about them lately.

Collapse
 
rpalo profile image
Ryan Palo

Thanks! The explanations are really interesting too!

Collapse
 
trueneu profile image
Pavel Gurkov • Edited

Clojure:

(utils/read-file just slurps and splits by newlines)

Part 1:

(->>
  (utils/read-file (str utils/resources-path "day1.txt"))
  (map #(Integer. ^String %))
  (apply +))

Part 2:

(->>
   (utils/read-file (str utils/resources-path "day1.txt"))
   (map #(Integer. ^String %))
   (cycle)
   (reduce
     (fn [{:keys [freq seen]} freq-change]
       (if (seen freq)
         (reduced freq)
         {:freq (+ freq freq-change) :seen (conj seen freq)}))
     {:freq 0 :seen #{}}))
Collapse
 
particleflux profile image
Stefan Linke • Edited

Three different PHP solutions - two of them code-golfed: particleflux.codes/post/2018/adven...

TLDR:

<?=array_sum(file('input'));
Collapse
 
neilgall profile image
Neil Gall

I'm enjoying reading everyone's solutions. After doing last year's in Haskell I'm using Kotlin to try to improve my knowledge of the language and libraries. I'm also avoiding using an IDE, as auto-suggest and magic building don't teach you what's really going on under the hood.

package adventofcode2018.day1

import java.io.File

/** Infinitely repeat a sequence */
fun <T> Sequence<T>.repeat() = generateSequence { asIterable() }.flatten()

/** Like fold() but returns a sequence of all the accumulator values,
 *  not just the last one. `seq.scanl(i, f).last() == seq.fold(i, f)` */
fun <T, U> Sequence<T>.scanl(initial: U, f: (U, T) -> U): Sequence<U> {
    var acc: U = initial
    return map { x -> acc = f(acc, x); acc }
}

fun main(args: Array<String>) {
    val input: List<Int> = File("input.txt").readLines().map(String::toInt)

    // part 1
    val result = input.sum()
    println("Part 1 result: ${result}")

    // part 2
    val repeatedInput = input.asSequence().repeat()
    val accumulatedInput = repeatedInput.scanl(0, Int::plus)
    val unconsumed = accumulatedInput.dropWhile(mutableSetOf<Int>()::add)
    println("Part 2 result: ${unconsumed.first()}")
}

I know the idea is to avoid everyone's github but I'm writing notes on my solutions at github.com/neilgall/adventofcode2018

Collapse
 
magicleon94 profile image
Antonello Galipò • Edited

Hi there!
I've used Javascript.
Here's my part one solution:

const fs = require('fs');

// Read the input
let contents = fs.readFileSync('frequenciesDiff.txt','utf8');

// Parse to a int array
let diffs = contents.split("\n").map(item => parseInt(item));

// Reduce
let result = diffs.reduce((a,b) => a+b);


// Profit!
console.log(result);

I just read the input from file, parsed to a int array and used the reduce function.

Talking about the second part, I've user a dictionary to store frequencies and retrieve them quickly (access is O(1)), cycling in a circular manner through the provided diffs:

const fs = require('fs');

function duplicateFinder(diffs) {
    // Init an empty memo. We'll store here frequency values for easy retrieval
    let memo = {};

    let currentFrequency = 0;
    let i = 0;

    // Loop until currentFrequency is already in the memo.
    // When the loop breaks, it will be because currentFrequency got a value that had before. 
    // This means it's the second time it appears
    while (!(currentFrequency in memo)) {
        memo[currentFrequency] = currentFrequency.toString();

        currentFrequency += diffs[i];
        i = ++i % diffs.length
    }
    return currentFrequency;
}

// Read the input
let contents = fs.readFileSync('frequenciesDiff.txt', 'utf8');

// Parse to a int array
let diffs = contents.split("\n").map(item => parseInt(item));

// Do the work
let result = duplicateFinder(diffs);

// Profit!
console.log(result);

I'm planning to do this in Go too, since I'd love to practice this language, but I haven't much time for now :(

Collapse
 
cloudyhug profile image
cloudyhug

I'm doing this in C++ this year, but as we are proposing original solutions with very expressive languages, I'll show a solution in OCaml :)

OCaml

Part 1

let rec f freq ic =
  try f (freq + int_of_string (input_line ic)) ic
  with End_of_file -> freq

let () = Printf.printf "%d\n" (f 0 stdin)

Part 2

let rec read_changes changes ic =
  let next_line = try Some (input_line ic) with End_of_file -> None in
  match next_line with
  | None -> List.rev changes
  | Some c -> read_changes (int_of_string c :: changes) ic

let rec f freq freqs changes_done = function
  | [] -> f freq freqs [] (List.rev changes_done)
  | c :: r ->
    let freq' = freq + c in
    if List.mem freq' freqs then freq'
    else f freq' (freq' :: freqs) (c :: changes_done) r

let () = Printf.printf "%d\n" (f 0 [0] [] (read_changes [] stdin))

Using lists is not very efficient but the code is quite short, that is nice.

Collapse
 
herrfugbaum profile image
Pascal

1.1

A bit overcomplicated. Didn't know parseInt parses signs too 😅

const data = document.querySelector('pre').innerText

const frequencies = data.split('\n')

function getFrequency (freqs) {
  return freqs.reduce((acc, val) => {
    const sign = val[0] === '+' ? 1 : -1
    const number = val.substring(1)

    return acc + sign * number
  }, 0)
}

const result = getFrequency(frequencies)
console.log(result)

1.2

The first result is the solution, not quite sure why it prints so many other results after that even if I set matchFound = true though 🤔

const data = document.querySelector('pre').innerText

const frequencies = data.split('\n')
let sums = []

function getFrequency (freqs, acc=0, callback) {
  return freqs.reduce((acc, val) => {
    const sign = val[0] === '+' ? 1 : -1
    const number = val.substring(1)
    const current = acc + sign * number
    callback(current)
    return current
  }, acc)
}

let startFreq = getFrequency(frequencies, 0, current => sums.push(current))

function isMatch (arr, el) {
  return arr.find(element => element === el)
}

function findMatch () {
    let matchFound = false

    while(!matchFound) {
    startFreq = getFrequency(frequencies, startFreq, current => {
      if (isMatch(sums, current)) {
        matchFound = true
        console.log('The match is', current)
      }
    })
    }
}

findMatch()
Collapse
 
philnash profile image
Phil Nash

Thanks for this Ryan! I've joined the leaderboard. Good luck to everyone!

Here's my solution in Crystal, both parts are included as one class:

class Device
  getter frequency : Int32
  getter duplicate : Int32 | Nil

  def initialize
    @frequency = 0
    @duplicate = nil
    @frequencies = Set{@frequency}
  end

  def update(input : Array(String))
    @frequency = input.map { |string| string.to_i }.reduce(@frequency) do |acc, i|
      frequency = acc + i
      @duplicate = frequency if @frequencies.includes?(frequency) && @duplicate.nil?
      @frequencies.add(frequency)
      frequency
    end
  end

  def find_duplicate(input : Array(String))
    while @duplicate.nil?
      update(input)
    end
  end
end


puts "--- Day 1: Chronal Calibration ---"
input = File.read_lines("./01/input.txt")
device = Device.new
device.update(input)
puts "Frequency result: #{device.frequency}"
device.find_duplicate(input)
puts "Frequency first duplicates at: #{device.duplicate}"

There are also tests here.

Collapse
 
lschultebraucks profile image
Lasse Schultebraucks

Super cool idea! Just joined the private leaderboard!