AoC Day 14: Chocolate Charts

Hi! Day 14 is here. Unfortunately, I'm falling behind, but I'll catch back up this weekend. And I'm excited to get caught up because then I can look at everybody else's solutions.

Today, we encounter a couple of elves making some hot chocolate with different recipes. Much like the marbles a few days ago, it's looking like we're looping over some scores and adding in some new ones.

Good luck!

Comments

[Javid Asgarov]

Javascript Solution. It all probably can be done easier, I don't know, it works. Don't kick me :).

(function() {
  function getNewRecipe(recipes, index1, index2) {
    let sum = recipes[index1] + recipes[index2];
    return sum
      .toString()
      .split('')
      .map(item => +item);
  }

  function getNextPosition(elf, recipes) {
    let steps = recipes[elf.current] + 1;
    let index = elf.current;
    for (let i = 0; i < steps; i++) {
      index += 1;
      if (index > recipes.length - 1) {
        index = 0;
      }
    }
    return index;
  }

  function findAnswer(limit) {
    let recipes = [3, 7];
    let firstElf = { current: 0 };
    let secondElf = { current: 1 };
    let meScore = limit.toString();
    let firstAnswer;
    let secondAnswer;
    for (let i = 0; i < 5800000 * 5; i++) {
      {
        firstElf.current = getNextPosition(firstElf, recipes);
        secondElf.current = getNextPosition(secondElf, recipes);
        recipes.push(
          ...getNewRecipe(recipes, firstElf.current, secondElf.current)
        );
      }
      if (
        recipes
          .slice(recipes.length - meScore.length, recipes.length)
          .join('') === meScore
      ) {
        i = Infinity;
        secondAnswer = recipes.length - meScore.length;
      } else if (
        recipes
          .slice(recipes.length - meScore.length - 1, recipes.length - 1)
          .join('') === meScore
      ) {
        i = Infinity;
        secondAnswer = recipes.length - meScore.length - 1;
      }

      if (recipes.length >= limit + 10 && firstAnswer === undefined) {
        firstAnswer = recipes.slice(limit, limit + 10).join('');
      }
    }
    console.log('FINISHED!', firstAnswer, secondAnswer);
    return { firstAnswer, secondAnswer };
  }
  const answer = findAnswer(765071); // your puzzle input
})();

[Neil Gall]

Today's is a low-level one. Might be interesting to do it in assembly language, if I could remember any. The key insight is you're going to eventually need a very large array but we only ever append to it, so preallocating the buffer is a sensible idea for performance. I decided to forego all the high-level modelling and implement it C-style.

Part 1

First make a big buffer and initialise all the state we need.

val recipies = CharArray(make + 20) { '0' }
recipies[0] = '3'
recipies[1] = '7'
var length: Int = 2
var elf1: Int = 0
var elf2: Int = 1

I'm storing the values as the ASCII characters for the digits, so one high-level language comfort is a helper function to pull out the values.

fun recipe(i: Int) = (recipies[i] - '0').toInt()

Then run the algorithm until we have enough data in the buffer:

while (length < make + 10) {
    var new = (recipe(elf1) + recipe(elf2)).toString().toCharArray()
    new.forEachIndexed { i, c -> recipies[length + i] = c }
    length += new.size
    elf1 = (elf1 + 1 + recipe(elf1)) % length
    elf2 = (elf2 + 1 + recipe(elf2)) % length
}

And extract the answer:

return recipies.slice(make..make+9).joinToString("")

Part 2

Part 2 makes the problem slightly harder in that we don't know the eventual size of the buffer. A classic approach is to start with some sensible number (let's say 1024) and reallocate it twice the size each time we hit the end. The number of copies is therefore limited to log2(N).

if (length + new.size >= recipies.size) {
    recipies += CharArray(recipies.size) { '0' }
}

The other tricky part is that we don't know how many digits are added to the array each iteration, so we can't assume the target string is right at the end. We know it is near the end though, so I therefore search for the target string from 5 characters before the old end to the new end of the array.

if (oldLength >= 5) {
    val index = recipies.slice(oldLength-5..length-1).joinToString("").indexOf(input)
    if (index > -1) {
        return oldLength-5+index
    }
}

Full code here

[Mustafa Haddara]

The other tricky part is that we don't know how many digits are added to the array each iteration, so we can't assume the target string is right at the end. We know it is near the end though, so I therefore search for the target string from 5 characters before the old end to the new end of the array.

This bit me too at first, but then I realized you only ever need to check the very end or offset by one character. This is because you can only ever add 1 or 2 digits to the end of the array!

[Neil Gall]

You're right. So I could have optimised a tiny bit more by starting at oldLength-4.

Anyway I quite enjoyed today's low-level one after aiming to do them all in a mostly functional style up to now. Takes me back to my years doing embedded C and Linux device drivers.

[Juan Manuel Gimeno]

A python solution using a generator.

def scoreboards(recipe0, recipe1):
    recipes = [recipe0, recipe1]
    elf0 = 0
    elf1 = 1
    yield recipes
    while True:
        recipe0 = recipes[elf0]
        recipe1 = recipes[elf1]
        sum_recipes = recipe0 + recipe1
        if sum_recipes > 9:
            recipes.append(sum_recipes // 10)
            yield recipes
        recipes.append(sum_recipes % 10)
        yield recipes
        elf0 = (elf0 + recipe0 + 1 ) % len(recipes)
        elf1 = (elf1 + recipe1 + 1 ) % len(recipes)

def part1(number):
    scoreboard_gen = scoreboards(3, 7)
    scoreboard = next(scoreboard_gen)
    while len(scoreboard) < number + 12:
        scoreboard = next(scoreboard_gen)
    return "".join(map(str, scoreboard[number:number+10]))

def part2(pattern):
    lpattern = [int(r) for r in pattern]
    for scoreboard in scoreboards(3, 7):
        if scoreboard[-len(pattern):] == lpattern:
            break
    return len(scoreboard) - len(pattern)

def test_part1():
    assert "0124515891" == part1(5)
    assert "5158916779" == part1(9)
    assert "9251071085" == part1(18)
    assert "5941429882" == part1(2018)

def test_part2():
    assert 5 == part2("01245")
    assert 9 == part2("51589")
    assert 18 == part2("92510")
    assert 2018 == part2("59414")

if __name__ == "__main__":
    print("Part1:   ", part1(30121))
    print("Part2:   ", part2("030121"))

[Juan Manuel Gimeno]

A translation of the python solution with generators to C++.

It works but my C++ is very, very limited.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Scoreboards {
    vector<int> recipes;
    int elf0;
    int elf1;
    int recipe0;
    int recipe1;
    int next_recipe;

    public: 

    Scoreboards(int recipe0, int recipe1) {
        recipes.push_back(recipe0);
        recipes.push_back(recipe1);
        elf0 = 0;
        elf1 = 1;
        next_recipe = -1;
    }

    const vector<int>& next() {
        if (next_recipe == -1) {
            recipe0 = recipes[elf0];
            recipe1 = recipes[elf1];
            int sum_recipes = recipe0 + recipe1;
            if (sum_recipes > 9) {
                recipes.push_back(sum_recipes / 10);
                next_recipe = sum_recipes % 10;
            } else {
                recipes.push_back(sum_recipes);
                elf0 = (elf0 + recipe0 + 1) % recipes.size();
                elf1 = (elf1 + recipe1 + 1) % recipes.size();
            }
        } else {
            recipes.push_back(next_recipe);
            next_recipe = -1;
            elf0 = (elf0 + recipe0 + 1) % recipes.size();
            elf1 = (elf1 + recipe1 + 1) % recipes.size();
        }
        return recipes;
    }
};

string stringuify(const vector<int>& v, int begin, int end) {
    string s;
    for (int i = begin; i < end; i++) {
        s.push_back(v[i] + '0');
    }
    return s;
}

void print(vector<int>& v) {
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

string part1(int number) {
    Scoreboards scoreboards(3, 7);
    const vector<int>& scoreboard = scoreboards.next();
    do {
        scoreboards.next();
    } while (scoreboard.size() < number + 12);
    return stringuify(scoreboard, number, number+10);
}

vector<int> vectorify(string s) {
    vector<int> v;
    for (int i = 0; i < s.size(); i++) {
        v.push_back(s[i] - '0');
    }
    return v;
}

bool has_suffix(const vector<int>& scoreboard, const vector<int>& suffix) {
    if (scoreboard.size() < suffix.size()) {
        return false;
    }
    for (int i = 0; i < suffix.size(); i++) {
        if (scoreboard[scoreboard.size()-suffix.size()+i] != suffix[i]) {
            return false;
        }
    }
    return true;
}

int part2(string pattern) {
    const vector<int> vpattern = vectorify(pattern);
    Scoreboards scoreboards(3, 7);
    const vector<int>& scoreboard = scoreboards.next();
    do {
        scoreboards.next();
    } while (!has_suffix(scoreboard, vpattern));
    return scoreboard.size() - vpattern.size();
}

void test_part1() {
    assert("0124515891" == part1(5));
    assert("5158916779" == part1(9));
    assert("9251071085" == part1(18));
    assert("5941429882" == part1(2018));
}

void test_part2() {
    assert(5 == part2("01245"));
    assert(9 == part2("51589"));
    assert(18 == part2("92510"));
    assert(2018 == part2("59414"));
}

int main() {
    //test_part1();
    //test_part2();
    cout << "Part1: " << part1(30121) << endl;
    cout << "Part2: " << part2("030121") << endl;
}

[Viktors Jenovs]

Part 1 was rather easy - just generate an array of numbers.
Part 2 took a while to figure out why test cases pass, but my input gave me "out of memory" error. Very sneaky :)

<?php
$input = 236021;

function calcNextPos($pos, $steps, $arrLen) {
  $newPos = $pos + $steps + 1;
  while($newPos >= $arrLen) {
    $newPos = $newPos % ($arrLen);
  }
  return $newPos;
}

function findNextTen($input) {
  $recipes = [3, 7];
  $elf1Pos = 0;
  $elf2Pos = 1;

  while(count($recipes) < $input + 10) {
    $elf1Recipe = $recipes[$elf1Pos];
    $elf2Recipe = $recipes[$elf2Pos];

    $newRecipe = $elf1Recipe + $elf2Recipe;
    if ($newRecipe > 9) {
      $recipes[] = 1;
    }
    $recipes[] = $newRecipe % 10;

    $elf1Pos = calcNextPos($elf1Pos, $elf1Recipe, count($recipes));
    $elf2Pos = calcNextPos($elf2Pos, $elf2Recipe, count($recipes));
  }
  return join(array_slice($recipes, $input, 10));
}

function countRecipesOnLeft($input) {
  $recipes = [3, 7];
  $elf1Pos = 0;
  $elf2Pos = 1;
  $str = join($recipes);

  while(true) {
    $elf1Recipe = $recipes[$elf1Pos];
    $elf2Recipe = $recipes[$elf2Pos];

    $newRecipe = $elf1Recipe + $elf2Recipe;

    if ($newRecipe > 9) {
      $recipes[] = 1;
      $str = $str . 1;

      strlen($str) > strlen($input) && $str = substr($str, strlen($str) - strlen($input));
      if ($str == $input) {
        return count($recipes) - strlen($input);
      }
    }
    $recipes[] = $newRecipe % 10;
    $str = $str . ($newRecipe % 10);

    strlen($str) > strlen($input) && $str = substr($str, strlen($str) - strlen($input));
    if ($str == $input) {
      return count($recipes) - strlen($input);
    }

    $elf1Pos = calcNextPos($elf1Pos, $elf1Recipe, count($recipes));
    $elf2Pos = calcNextPos($elf2Pos, $elf2Recipe, count($recipes));
  }
}

echo findNextTen($input) . "\n";
echo countRecipesOnLeft($input) . "\n";
?>

[E. Choroba]

The part 1 was super easy: I just pushed new elements to an array.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

chomp( my $input = <> );

my @scores = (3, 7);
my @elves = (0, 1);
while (@scores < 11 + $input) {
    my $new = $scores[ $elves[0] ] + $scores[ $elves[1] ];
    push @scores, split //, $new;
    $elves[$_] += 1 + $scores[ $elves[$_] ], $elves[$_] %= @scores
        for 0, 1;
}
say @scores[$input .. 9 + $input];

When I adapted the algorithm for the part 2, it took almost a minute to get the answer. To optimize it, I used strings instead of arrays of numbers (strings are not arrays in Perl).

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

chomp( my $input = <> );

my $score = '37';
my @elves = (0, 1);
while (length $score < length $input
       || -1 == rindex substr($score, -12), $input
) {
    my $new = substr($score, $elves[0], 1) + substr $score, $elves[1], 1;
    $score .= $new;
    $elves[$_] += 1 + substr($score, $elves[$_], 1),
        $elves[$_] %= length $score
        for 0, 1;
}
say rindex $score, $input;

[Phil Nash]

Part two of this really needed some performance work to finish. The next_recipes method does the work of moving the elves from their current scores to the next. Then the loops are built differently to return the final result.

This is my attempt in Crystal:

class Recipe
  def self.next_ten(after : String)
    after = after.to_i
    recipe_list = [3, 7]

    elf1 = 0
    elf2 = 1

    while recipe_list.size < after + 10
      recipe_list, elf1, elf2 = next_recipes(recipe_list, elf1, elf2)
    end
    return recipe_list[after...after+10].join("")
  end

  def self.how_many_to_score(score : String)
    pattern = score.split("").map(&.to_i)
    size = pattern.size
    recipe_list = [3, 7]
    elf1 = 0
    elf2 = 1

    while recipe_list.size < size+1
      recipe_list, elf1, elf2 = next_recipes(recipe_list, elf1, elf2)
    end
    while recipe_list[-size..-1] != pattern && recipe_list[-(size+1)..-2] != pattern
      recipe_list, elf1, elf2 = next_recipes(recipe_list, elf1, elf2)
    end
    recipe_string = recipe_list.join("")
    return recipe_string.index(score)
  end

  def self.next_recipes(list, elf1, elf2)
    combine = list[elf1] + list[elf2]
    if combine < 10
      list.push(combine)
    else
      list.push(combine / 10 % 10).push(combine % 10)
    end
    elf1 = (elf1 + list[elf1] + 1) % list.size
    elf2 = (elf2 + list[elf2] + 1) % list.size
    {list, elf1, elf2}
  end
end

puts "--- Day 14: Chocolate Charts ---"
input = File.read("./14/input.txt")
puts "The next 10 scores after #{input} are: #{Recipe.next_ten(input)}"
puts "The position for the pattern #{input} is #{Recipe.how_many_to_score(input)}"

[Florian Rohrer]

Python

n = 293801
# Part 1
q = [3,7]
e1, e2 = 0, 1
n_created = 0

while n_created < n+10:
    r1, r2 = q[e1], q[e2]
    for c in str(r1+r2):
        q.append(int(c))
        n_created += 1
    e1 = (e1 + 1 + r1) % len(q)
    e2 = (e2 + 1 + r2) % len(q)

print("".join(str(i) for i in q[n:n+10]))

# Part 2
ns = str(n)
def match(haystack):
    for nc, h in zip(reversed(ns), reversed(haystack)):
        if nc != str(h): return False
    return True

q = [3,7]
e1, e2 = 0, 1

while True:
    r1, r2 = q[e1], q[e2]
    for c in str(r1+r2):
        q.append(int(c))
        if match(q):
            print(len(q)-len(str(n)))
            break
    else:
        e1 = (e1 + 1 + r1) % len(q)
        e2 = (e2 + 1 + r2) % len(q)
        continue
    break

[Ali Spittel]

Python!

vals = [3, 7]
a_idx, b_idx = 0, 1

INPUT_SCORE = 894501

def get_new_score(a, b):
    return [int(i) for i in str(a + b)]

def increase_idx(idx):
    return (idx + int(vals[idx]) + 1) % len(vals)

# Part 1
for _ in range(10 + INPUT_SCORE):
    vals += get_new_score(vals[a_idx], vals[b_idx])
    a_idx, b_idx = increase_idx(a_idx), increase_idx(b_idx)

print(''.join(str(val) for val in vals)[INPUT_SCORE:INPUT_SCORE+10])


INPUT_SCORE = str(INPUT_SCORE)

# Part 2
while True:
    vals += get_new_score(vals[a_idx], vals[b_idx])
    p1, p2 = ''.join(str(i) for i in vals[-len(INPUT_SCORE):]), ''.join(str(i) for i in vals[-len(INPUT_SCORE) - 1: -1])
    if INPUT_SCORE == p1 or INPUT_SCORE == p2:
        to_s = ''.join(str(i) for i in vals)
        print(to_s.find(INPUT_SCORE))
        break
    a_idx, b_idx = increase_idx(a_idx), increase_idx(b_idx)

[Jon Bristow]

Kotlin Solution

Part 1

Another tailrec solution for the books. I had some issue with how long this took. After a few frustrating minutes, I figured out that .takeLast() was not as efficient as the .get() or array access notation.

private fun answer1(input: Int): Any? {
    val elf1 = 0
    val elf2 = 1
    val recipes = mutableListOf(3, 7)
    return findRecipes(2, elf1, elf2, recipes, input)
}

private tailrec fun findRecipes(
    n: Int,
    elf1: Int,
    elf2: Int,
    recipes: MutableList<Int>,
    limit: Int
): String {
    if (n > limit + 10) {
        return recipes.drop(limit).take(10).joinToString("")
    }
    val re1 = recipes[elf1]
    val re2 = recipes[elf2]
    val newRecipes = when {
        re1 + re2 > 9 -> mutableListOf(1, (re1 + re2) % 10)
        else -> mutableListOf((re1 + re2) % 10)
    }
    val nextN = n + newRecipes.count()

    recipes.addAll(newRecipes)
    return findRecipes(
        nextN,
        (elf1 + re1 + 1) % nextN,
        (elf2 + re2 + 1) % nextN,
        recipes,
        limit
    )
}

Part 2

This one threw me, since the solution was so much farther out than I expected...

private fun answer2(input: Int): Any? {
  val elf1 = 0
  val elf2 = 1
  val recipes = mutableListOf(3, 7)
  return findRecipes2( 2, elf1, elf2, recipes, input.toString().map { it.toDigit() })
}
private tailrec fun findRecipes2(
    n: Int,
    elf1: Int,
    elf2: Int,
    recipes: MutableList<Int>,
    check: List<Int>
): Int {
    val ccount = check.count()
    if ((n > ccount) && (n - ccount until n).map { recipes[it] } == check) {
        return n - ccount
    } else if ((n > ccount) && (n - ccount until n).map { recipes[it - 1] } == check) {
        return n - ccount - 1
    }

    val re1 = recipes[elf1]
    val re2 = recipes[elf2]

    val newRecipes = when {
        re1 + re2 > 9 -> mutableListOf(1, (re1 + re2) % 10)
        else -> mutableListOf((re1 + re2) % 10)
    }
    val nextN = n + newRecipes.count()
    recipes.addAll(newRecipes)
    return findRecipes2(
        nextN,
        (elf1 + re1 + 1) % nextN,
        (elf2 + re2 + 1) % nextN,
        recipes,
        check
    )
}

[Ryan Palo]

OK, I'm caving. I'm going to be doing these in Python from here on out, I think. They're getting tough enough that I don't need to be fighting with Rust's borrow checker and the challenge itself. It feels like trying to win a debate on foreign policy in Mandarin. Also, Python is way more fun. And it's Christmas, so Merry Christmas to me and Python. 😬

Anyways, enough whining from me. Here's my solution from day 14.

"""Day 14: Chocolate Charts

Figuring out scores for hot chocolate through iterative process.
"""

from typing import List


class Board:
    """Keeps track of hot chocolate recipe scores"""

    def __init__(self, elf1_score, elf2_score):
        self.scores = [elf1_score, elf2_score]
        self.elf1 = 0
        self.elf2 = 1

    def generate_new_recipes(self):
        """Generates one or two new recipes by combining the current ones"""
        new_score = self.scores[self.elf1] + self.scores[self.elf2]
        self.scores.extend(Board.digits(new_score))

    @staticmethod
    def digits(number: int) -> List[int]:
        """Given a number, returns a list of its digits"""
        return [int(digit) for digit in str(number)]

    def select_new_recipes(self):
        """Each elf selects a new recipe based on their current one"""
        self.elf1 = (self.elf1 + self.scores[self.elf1] + 1) % len(self.scores)
        self.elf2 = (self.elf2 + self.scores[self.elf2] + 1) % len(self.scores)

    def tick(self):
        """One iteration cycle of creating recipes"""
        self.generate_new_recipes()
        self.select_new_recipes()

    def generate_n_scores(self, n: int) -> List[int]:
        """Adds *at least* n scores to the board (may be one extra)"""
        current_scores = len(self.scores)
        while len(self.scores) < current_scores + n:
            self.tick()

        return self.scores[current_scores:current_scores + n]

    def get_scores(self, start: int, count: int) -> List[int]:
        """Returns the scores on the board.  1-based counting"""
        return self.scores[start - 1:start - 1 + count]

    def find_numbers(self, num: str) -> int:
        """Find the start index of a given string of digits"""
        digits = Board.digits(num)

        if len(self.scores) < len(digits):
            self.generate_n_scores(len(digits) - len(self.scores))

        last_len = len(digits)
        while True:
            self.tick()
            if len(self.scores) == last_len + 2:
                if self.scores[-len(digits) - 1: -1] == digits:
                    return len(self.scores) - len(digits) - 1
            if self.scores[-len(digits):] == digits:
                return len(self.scores) - len(digits)

            last_len = len(self.scores)


if __name__ == "__main__":
    # Part 1
    board = Board(3, 7)
    board.generate_n_scores(440231 + 10)
    print("".join(str(i) for i in board.get_scores(440231 + 1, 10)))

    # Part 2
    board = Board(3, 7)
    print(board.find_numbers("440231"))