AoC Day 1: Chronal Calibration

• Overview
• My Solution
• DEV Leaderboards

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...

// 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));
}

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

Comments

[Ali Spittel]

So excited about this 🙌🏻!

Python

Part 1

data = open('input.txt', 'r')
total = 0
for line in data:
    total += int(line)
print(total)

Part 2

data = [int(i) for i in open('input.txt', 'r')]

def get_first_duplicate_total(data):
    total = 0
    prev_totals = set([0])
    while True:
        for i in data:
            total += i
            if total in prev_totals:
                return total
            prev_totals.add(total)
    return total

print(get_first_duplicate_total(data))

I also learned about itertools.cycle through reading the Reddit solutions, that would make it so that I don't need the while True:

[Ryan Palo]

Ah! So good. The clean-ness of Python never stops making me happy!

Using a set was a good idea. I didn't think of that, but it would be a lot faster for checking whether or not an item was present.

I'm going to offer unsolicited suggestions, but feel free to totally ignore them if you already knew about them (probable) or don't like them, since your solution already looks really nice.

1. For part one, generator expressions could be your friend:

data = open('input.txt', 'r')
total = sum(int(line) for line in data)
print(total)

1. For the second part, check out itertools.cycle.

[Ali Spittel]

Awesome! Yes, thank you! Found out about itertools.cycle this morning -- feels super niche but still really cool.

Part one could also be a one-liner!

print(sum(int(line for line in open('input.txt', 'r'))))

[Florian Rohrer]

I'd also suggest to use a context manager (the with keyword) for clean opening and closing of files.

Part 1:

with open("input.txt") as f:
    freq = sum(int(i.strip()) for i in f)
freq

Part 2:

from itertools import cycle

with open("input.txt") as f:
    freqs = [int(i.strip()) for i in f]

seen = set()
current = 0
for f in cycle(freqs):
    if current in seen:
        print(current)
        break
    else:
        seen.add(current)
        current += f

Also: "Hey checkout my Github Repo!"

[Ali Spittel]

True! Always forget to do that since I really only do file handling for code challenges at this point.

[Yordi Verkroost]

Awesome, this is a nice place to discuss the solutions! This is mine, in Elixir:

Common code (used by both part 1 and part 2):

defmodule AoC.DayOne.Common do
  def read_input(path) do
    File.stream!(path)
    |> Stream.map(&String.trim/1)
    |> Stream.filter(fn x -> x != "" end)
    |> Stream.map(&String.trim_trailing/1)
    |> Stream.map(&String.to_integer/1)
    |> Enum.to_list()
  end
end

Part 1

defmodule AoC.DayOne.PartOne do
  alias AoC.DayOne.Common

  def main() do
    Common.read_input("lib/day1/input.txt")
    |> calculate_sum()
    |> IO.puts()
  end

  def calculate_sum(numbers) do
    Enum.sum(numbers)
  end
end

Part 2

defmodule AoC.DayOne.PartTwo do
  alias AoC.DayOne.Common

  def main() do
    Common.read_input("lib/day1/input.txt")
    |> calculate_result()
    |> IO.puts()
  end

  def calculate_result(numbers, frequencies \\ [], base \\ 0, index \\ 0)

  def calculate_result(numbers, frequencies, base, index) when index == length(numbers) do
    calculate_result(numbers, frequencies, base, 0)
  end

  def calculate_result(numbers, frequencies, base, index) do
    base = base + Enum.at(numbers, index)
    if (Enum.member?(frequencies, base)) do
      base
    else
      frequencies = [base | frequencies]
      calculate_result(numbers, frequencies, base, index + 1)
    end
  end
end

If you want, you could check out my full repo on GitHub.

[Ben Lovy]

F# - this is my first brush with F# and .NET in general, so pointers are more'n welcome!

Common code:

let getFrequencies fileName =
  let lines = IO.File.ReadLines(fileName)
  lines
    |> Seq.map Convert.ToInt32
    |> Seq.toList

Part 1:

let rec addFreq acc s =
  match s with
    | [] -> acc
    | freq::freqs -> addFreq (acc + freq) freqs

let day1Part1 fileName =
  getFrequencies fileName |> addFreq 0

part 2:

let rec addFreqWithState acc visited whole remaining =
  match remaining with
    | [] -> addFreqWithState acc visited whole whole
    | head::tail ->
      let newval = acc + head
      if Array.contains newval visited then
        newval
      else
        addFreqWithState newval (Array.append visited [| newval |]) whole tail

let day1Part2 fileName =
  let freqs = getFrequencies fileName
  addFreqWithState 0 [| |] freqs freqs

Entry point:

open System
open Library

[<EntryPoint>]
let main argv =
    day1Part1 argv.[0] |> printfn "Part 1 result: %i"
    day1Part2 argv.[0] |> printfn "Part 2 result: %i"

    0 // return an integer exit code

Part 2 is sloooow. How would you optimize this?

[Ali Spittel]

Nice!! For optimizing part 2, I would use a set! O(1) to check if an item is in it!

[Ben Lovy]

Aha! Thanks so much, it's blazingly fast now:

let rec addFreqWithState acc visited whole remaining =
  match remaining with
    | [] -> addFreqWithState acc visited whole whole
    | head::tail ->
      let newval = acc + head
      if Set.contains newval visited then
        newval
      else
        addFreqWithState newval (Set.add newval visited) whole tail

let day1Part2 fileName =
  let freqs = getFrequencies fileName
  addFreqWithState 0 (new Set<int> (Seq.empty)) freqs freqs

I guess the Tour of F# page shouldn't be my only learning resource :)

[Shritesh Bhattarai]

I'm doing AoC with Rust too and the solution I came up with looks almost exactly like yours.

Part 1

pub fn callibrate(input: &[&str]) -> i32 {
    input.iter().map(|s| s.parse::<i32>().unwrap()).sum()
}

Part 2: I used a HashSet

pub fn twice(input: &[&str]) -> i32 {
    let mut numbers = input.iter().map(|s| s.parse::<i32>().unwrap()).cycle();

    let mut seen_results = HashSet::new();
    seen_results.insert(0);

    let mut sum = 0;

    loop {
        let num = numbers.next().unwrap();
        sum += num;

        if seen_results.contains(&sum) {
            return sum;
        } else {
            seen_results.insert(sum);
        }
    }
}

Instead of changing the main.rs file every day, I'll suggest creating a separate file for each day inside src/bin directory. That way, you can execute them using cargo run --bin day_1. Small but well thought out features like this is why I love Rust so much. For example, you can look at my repo at github.com/shritesh/advent-of-code

I hope to get through all of the challenges this year and learn from everyone here.

[Ryan Palo]

Oooh! Good idea! I’m definitely doing that. Thanks!

[Dāvis Namsons]

That's a good idea !

Ruby

Part 1

input = File.open('./freqs.in').read

frequency = 0

input.each_line do |line|
  frequency += line.to_i
end

puts frequency

Part 2

input = File.open('./freqs.in').read

frequency_changes = input.scan(/[-+]\d+/).collect! &:to_i

frequency = 0
frequencies = []
i = 0

until frequencies.include?(frequency)
  frequencies << frequency
  frequency += frequency_changes[i]
  i == frequency_changes.length - 1 ? i = 0 : i += 1
end

puts frequency

[Arjun Rajkumar]

Hi Davis.. 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

Will you be using Nokigiri or something similar to read the URL and parse the page to get the inputs?
Sorry if this sounds dumb.. But am wondering how you going to download the file?

Thanks

[Harriet]

I wanted to solve these ones in bash, which I've been focussing on learning lately. First challenge was great, found a simple oneliner:

echo $(( 0$(tr -d '\n' < ./day1/input.txt) ))

But part 2 was a nightmare. Super slow. Ended up using JS in the end, but would still love to know anyone's thoughts on how this could be optimised. Wasn't watching the clock but think it took >20 mins to run!

It's collecting previously computed frequencies in an array, and checking for the frequency in the array each time a new frequency is computed. Is it the maths that's likely to be so slow, or the looping, or both?

declare -i total=0
seen=()
found=

array_contains () {
  for i in "${seen[@]}"; do
    if [[ "$i" == "$1" ]]; then
      return 0
    fi
  done
  return 1
}

while [[ ! $found ]]; do
  for line in $(cat $1); do
    total=$(( ${total}${line} ))

    if array_contains "$total"; then
      echo "FOUND " $total
      found=1
      break
    else
      echo 'not found'
    fi

    seen+=($total)
  done
done

# ./main.sh input.txt

[Ryan Palo]

Woah, this is awesome! Yeah the second parts always seem to need some fancier algorithmic trick to speed them up.

You might look into using an associative array, as those provide a much faster lookup time and you don’t have to loop through every value each time? I don’t know if that will be enough though.

[Paula Gearon]

Unfortunately, associative arrays only appeared in Bash4. That's fine for Linux, but doesn't appear on Macs unless you manually install it (boo!).

[Ryan Palo]

Good caveat to note, thanks!

P.S. Getting Bash 4 on MacOS is a very good idea 😬

[Christopher Kruse]

Ali's tweet and the Advent of Code project inspired me to update a long-latent blog, and make my first actual post on DEV! Thanks to both of you for the inspiration, and here's a not-quite-fully successful implementation in Clojure w/ write-up: dev.to/ballpointcarrot/advent-of-c...

[Jon Bristow]

Kotlin Solution!

Part 1

Please exuse my tricked out kotlin, I've added some personal extension functions to let me think about list comprehensions more simply.

private fun String.parseN() = let { (head, tail) ->
    when (head) {
        '+' -> 1
        '-' -> -1
        else -> throw Exception("Illegal input!")
    } * tail.toInt()
}

fun answer1(input: List<String>) = input.sumBy(String::parseN)

Part 2

I made a silly mistake, and lost about an hour trying to figure out where I went wrong. I should set up my test runners ahead of day 2 so I don't end up with this same kind of typo.

fun answer2(input: List<String>): Int {
    val ns = input.map(String::parseN).scan(Int::plus)
    val ending = ns.last
    return (sequenceOf(listOf(0)) + generateSequence(ns) {
        it.map(ending::plus)
    }).findFirstDupe(emptySet())
}


tailrec fun Sequence<List<Int>>.findFirstDupe(seen: Set<Int>): Int {
    val (head, tail) = this
    val intersections = head intersect seen
    return when {
        intersections.isNotEmpty() -> head.find { it in intersections }!!
        else -> tail.findFirstDupe(seen + head)
    }
}

/**
 * My prewritten `scan` function... it's just a `fold` that keeps every step.
 */
fun <A, B> Sequence<A>.scan(initial: B, operation: (B, A) -> B) =
        fold(sequenceOf(initial)) { scanList, curr ->
            scanList + operation(scanList.last(), curr)
        }

Part 2 is "slow", but it's still under a minute 5 seconds to brute force through 150 iterations (or so) of the cycle.

[rhymes]

Is it normal that part 2 is killing my CPU :D ? It's been running for minutes in Elixir but nada.

Anyhow, I've tried day 1 with all three languages which is not a great idea!

I just googled the parts of the various languages I needed

Clojure

part 1

(def numbers-as-strings (clojure.string/split (slurp "input.txt") #"\n"))
(def numbers (map read-string numbers-as-strings))
(defn sum [coll] (reduce + coll))
(println (sum numbers))

I kind of hated it, I still don't have syntax highlighting nor formatting for some reason in VSCode and the REPL is quite slow to start (I didn't try with ClojureScript)

part 2

(def repeated-numbers (cycle numbers))

(loop
    [known-totals (set nil), total 0]
    (if (contains? known-totals total)
        (println total)
        (recur (conj known-totals total) (+ total (first (take 1 repeated-numbers))))))

I'm not sure it's correct, I had to kill it because it was hogging the CPU

Elixir

part 1

numbers_as_strings = String.split(String.trim(File.read!("input.txt")), "\n")
numbers = Enum.map(numbers_as_strings, fn x -> String.to_integer(x) end)
IO.puts(Enum.sum(numbers))

Well, this was the easiest one

part 2

defmodule Part2 do
    def find_total(repeated_numbers, totals, sum) do
        unless MapSet.member?(totals, sum) do
            MapSet.put(totals, sum)
            sum = sum + hd(Enum.take(repeated_numbers, 1))
            find_total(repeated_numbers, totals, sum)
        end

        IO.puts sum
    end
end

Part2.find_total(Stream.cycle(numbers), MapSet.new, 0)

Again, I'm not sure it's correct, it just kills my computer

Rust

part 1

use std::fs;

fn main() {
    let data = fs::read_to_string("input.txt").expect("Unable to read file");
    let numbers_as_strings = data.split("\n").collect::<Vec<&str>>();
    let numbers = numbers_as_strings.iter().filter_map(|n| n.parse::<i32>().ok()).collect::<Vec<i32>>();
    let sum: i32 = numbers.iter().sum();
    println!("{}", sum);
}

There's a bit of fiddling with types and syntax but the compiler it's quite helpful when you type stuff that doesn't make sense. It can get in the way of me doing the excercises :D

part 2

Well, this ran for half a second a produced the correct answer

use std::fs;
use std::collections::HashSet;

fn main() {
    // part 1
    let data = fs::read_to_string("input.txt").expect("Unable to read file");
    let numbers_as_strings = data.split("\n").collect::<Vec<&str>>();
    let numbers = numbers_as_strings.iter().filter_map(|n| n.parse::<i32>().ok()).collect::<Vec<i32>>();
    let sum: i32 = numbers.iter().sum();
    println!("{}", sum);

    // part 2
    let mut totals: HashSet<i32> = HashSet::new();
    let repeated_numbers = numbers.iter().cycle();
    let mut repeated_sum: i32 = 0;
    for num in repeated_numbers {
        if totals.contains(&repeated_sum) {
            println!("{}", repeated_sum);
            break;
        }
        totals.insert(repeated_sum);
        repeated_sum += num
    }
}

What am I doing wrong with Clojure and Elixir :D ?

I've put Day 1 on Github: github.com/rhymes/aoc2018/tree/mas...

[Max Cerrina]

I totally thought my elixir one was dead at first too, so I kept killing it. Only about a 15 second run time though I'm just impatient. lemme look at yours!

[rhymes]

Please do, I found a solution at the end, using reduce_while, instead of recursion:

repeated_numbers = Stream.cycle(numbers)
repeated_sum = Enum.reduce_while(repeated_numbers, {0, MapSet.new([0])}, fn i, {current, totals} ->
  sum = current + i

  if MapSet.member?(totals, sum) do
    {:halt, sum}
  else
    {:cont, {sum, MapSet.put(totals, sum)}}
  end
end)
IO.puts(repeated_sum)

I feel like I should get through the tutorial at least :D

[Ryan Will]

At a glance, in the Elixir part two solution it looks like the list of numbers is just being passed through as is. So, it is never moving on to the rest of the numbers and instead the sum is just adding the first number in the list over and over.

Because repeated_numbers is never reassigned the recursive call find_total(repeated_numbers, totals, sum) is passing the unchanged list of all the numbers through to the next iteration.

[rhymes]

At a glance, in the Elixir part two solution it looks like the list of numbers is just being passed through as is. So, it is never moving on to the rest of the numbers and instead the sum is just adding the first number in the list over and over.

That's probably it, I thought that:

hd(Enum.take(repeated_numbers, 1))

would take 1 number (and hence move the cursor).

[Ryan Will]

It does, but because Elixir is immutable it returns a new list with the first element from repeated_numbers instead of mutating (changing in place) repeating_numbers

Also, this line hd(Enum.take(repeated_numbers, 1)) could be rewritten as hd(repeated_numbers) to get the same functionality. The more "Elixir way to write that would be to use pattern matching. Something like [head | tail] = repeated_numbers Here is some more info on pattern matching, if you're interested. I think it is super cool!

[rhymes]

Thank you! :-)

I have to get used again to immutability and transformation instead of mutability and assignment :D

[Pavel Gurkov]

On the Clojure pt 2, you're effectively running an endless loop. You always take the first element from the cycled number collection, so you'll never hit the exit condition.
To avoid this while using the approach you chose, add a third numbers binding to the loop, and pass (rest numbers) when recuring, while computing total using (first numbers).

[rhymes]

Thanks! I then solved it thanks to this post

Advent of Code 2018 - Day 1

Christopher Kruse

#clojure#challenges#adventofcode

exactly like you said. You can see my version here github.com/rhymes/aoc2018/blob/mas...

[Ryan Will]

Thanks for making this post and sharing your solutions!

Here are my solutions in Elixir and JavaScript.

To start a couple functions to parse the input.

def parse(input) do
  input
  |> String.split("\n")
  |> Enum.map(&(String.trim(&1)
    |> String.to_integer())
  )
end

function parse() {
  return input()
    .split('\n')
    .map(Number);
}

Part one's solutions.

def part_1 do
  input() 
  |> parse() 
  |> Enum.sum()
end

function partOne() {
  return parse()
    .reduce((total, current) => total + current, 0);
}

Part two's solutions.

This solution takes advantage of Elixir's recursion, pattern matching, and multiple function clauses.

def part_2 do
 input() 
 |> parse() 
 |> part_2(0, %{})
end

def part_2([current | rest] = _frequencies, total, record) do
  total = current + total
  record = Map.update(record, total, 1, &(&1 + 1))

  case record[total] do
    n when n > 1 ->
      total

    _ ->
      part_2(rest, total, record)
  end
end

def part_2([], total, record) do
  input()
  |> parse()
  |> part_2(total, record)
end

I made two solutions to part two in JavaScript the first uses a more imperative approach, and the second was meant to mimic the Elixir solution using recursion. The issue with that is JavaScript not being tail call optimized. In order to get around that I used a trampoline function and a while loop. Though, that approach is insanely slow.

function partTwoImperative() {
  let record = {};
  let frequency = 0;
  let index = 0;
  let frequencyList = parse();
  let totalLoops = 0;

  const found = (record, frequency) => 
    (record[frequency] || 0) > 1;
  const getFrequencyRecordValue = (record, frequency) =>
    (record[frequency] || 0) + 1;

  while (!found(record, frequency)) {
    if (index === frequencyList.length) index = 0;

    frequency += frequencyList[index];
    record[frequency] = getFrequencyRecordValue(record, frequency);
    index += 1;
    totalLoops += 1;
  }

  return [frequency, totalLoops];
}

function partTwoTrampoline() {
  const found = (record, frequency) => (record[frequency] || 0) > 1;

  const getFrequencyRecordValue = (record, frequency) =>
    (record[frequency] || 0) + 1;

  const partTwoRecursive = ([current, ...rest], total, record) => {
    const newTotal = total + current;

    const newRecord = {
      ...record,
      [newTotal]: getFrequencyRecordValue(record, newTotal)
    };

    return !found(newRecord, newTotal)
      ? () =>
          partTwoRecursive(
            rest.length ? rest : [3, 3, 4, -2, -4],
            newTotal,
            newRecord
          )
      : newTotal;
  };

  let ret = partTwoRecursive([3, 3, 4, -2, -4], 0, {});

  while (typeof ret === 'function') {
    ret = ret();
  }

  return ret;
}

[Andre Myrick]

Wow, this is really cool! I completed day one too, but my code is nowhere near that clean. Could you recommend any resources that helped you get into Elixir?

[Ryan Will]

Thanks! This sounds like a cop-out answer but the Elixir docs are a great resource. elixir-lang.org/

I'd also be happy to answer any questions you have.