# AoC Day 14: Chocolate Charts

### Ryan Palo twitter logo github logo Dec 14 '18・1 min read

Advent of Code (26 Part Series)

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!

DISCUSS (15) 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;
}

let recipes = [3, 7];
let firstElf = { current: 0 };
let secondElf = { current: 1 };
let meScore = limit.toString();
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;
} 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('');
}
}
}
})();

``````

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 = '3'
recipies = '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
}
``````

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

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!

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"))
``````

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;
}
``````

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";
?>
``````

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)
``````

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

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 ] + \$scores[ \$elves ];
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, 1) + substr \$score, \$elves, 1;
\$score .= \$new;
\$elves[\$_] += 1 + substr(\$score, \$elves[\$_], 1),
\$elves[\$_] %= length \$score
for 0, 1;
}
say rindex \$score, \$input;
``````

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 ---"
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)}"
``````

### 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()

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()
return findRecipes2(
nextN,
(elf1 + re1 + 1) % nextN,
(elf2 + re2 + 1) % nextN,
recipes,
check
)
}
``````

I liked this one quite a bit too!

``````#!/usr/bin/env python

NUM_RECIPES = '170641'

def run(check_success, grab_info):
recipes = '37'
elf_one = 0
elf_two = 1

while True:
elf_one_score = int(recipes[elf_one])
elf_two_score = int(recipes[elf_two])

recipes += str(elf_one_score + elf_two_score)
num_recipes = len(recipes)
elf_one += 1 + elf_one_score
elf_one %= num_recipes
elf_two += 1 + elf_two_score
elf_two %= num_recipes

if check_success(recipes):
print(grab_info(recipes))
break

if __name__ == '__main__':
# Part 1
run(
lambda recipes: len(recipes) >= 10 + int(NUM_RECIPES),
lambda recipes: recipes[int(NUM_RECIPES):int(NUM_RECIPES) + 10],
)

# Part 2
run(
lambda recipes: NUM_RECIPES in recipes[-len(NUM_RECIPES) - 10:],
lambda recipes: recipes.index(NUM_RECIPES),
)
``````

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"))
``````

## JavaScript solution

I did Part 1 using arrays and I attempted Part 2 using indexOf to locate the input inside the array.

I was getting memory errors, so I wrote an algorithm that would always attempt to find the input as the last N elements of the scorecard, backwards. With a few optimizations, it runs in 5 seconds!

#### 14a.js

``````const getScoreBoard = input => {
const scoreboard = [3, 7];
let elf1 = 0;
let elf2 = 1;

while (scoreboard.length < input + 10) {
const scoreElf1 = scoreboard[elf1];
const scoreElf2 = scoreboard[elf2];
const newRecipes = (scoreElf1 + scoreElf2).toString().split('').map(i => +i);
scoreboard.push(...newRecipes);

const { length } = scoreboard;
elf1 = (elf1 + scoreElf1 + 1) % length;
elf2 = (elf2 + scoreElf2 + 1) % length;
}

return scoreboard;
};

(() => {
const input = 880751;
const scoreboard = getScoreBoard(input);
const scores = scoreboard.slice(input, input + 10).join('');

console.log(`The scores of the ten recipes immediately after the given number of recipes is \${scores}`);
})();
``````

#### 14b.js

``````const numberOfRecipes = input => {
const scoreboard = [3, 7];
let elf1 = 0;
let elf2 = 1;

input = input.split('').map(i => +i);
const n = input.length;
let m = scoreboard.length;

let number;
while (!number) {
const scoreElf1 = scoreboard[elf1];
const scoreElf2 = scoreboard[elf2];

const newRecipes = (scoreElf1 + scoreElf2).toString().split('').map(i => +i);
scoreboard.push(...newRecipes);
m += newRecipes.length;

const { length } = scoreboard;
elf1 = (elf1 + scoreElf1 + 1) % length;
elf2 = (elf2 + scoreElf2 + 1) % length;

let foundInput = false;
for (let tries = 0; !foundInput && tries < newRecipes.length; tries++) {
let hasNotFoundInputYet = false;
for (let i = 1; !hasNotFoundInputYet && i <= n; i++) {
if (scoreboard[m-i-tries] !== input[n-i]) {
hasNotFoundInputYet = true;
}
}
foundInput = !hasNotFoundInputYet;
}

if (foundInput) {
number = m - n;
}
}

return number;
};

(() => {
const input = '880751';
const number = numberOfRecipes(input);

console.log(`The number of recipes which appear on the scoreboard to the left of input is \${number}`);
})();
``````
Classic DEV Post from Jun 6 '19

## What programming best practice do you disagree with? Ryan is a mechanical engineer in the East SF Bay Area with a focus on dynamic languages like Ruby & Python. Goal: learn a ton and become a physics, math, and programming teacher. Message me on DEV.TO  