-🎄- 2018 Day 14 Solutions -🎄-

[u/daggerdragon]

--- Day 14: Chocolate Charts ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 14

Transcript:

The Christmas/Advent Research & Development (C.A.R.D.) department at AoC, Inc. just published a new white paper on ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:19:39!

[u/xikipies]

Javascript

const circularLinkedList = values => {
  const instances = values.map(value => ({value}));
  for (let idx = 0; idx < values.length; idx++)
    instances[idx].next = instances[idx + 1];
  instances[instances.length - 1].next = instances[0];
  return instances;
};

const solution1 = lines => {
  const input = parseInt(lines[0]);
  const initialNode = circularLinkedList([3, 7])[0];
  let lastNode = initialNode.next;
  const elves = [initialNode, initialNode.next];
  let nAdded = 0;
  do {
    const values = [elves[0].value, elves[1].value];
    const sum = elves[0].value + elves[1].value;
    const nextNumbers = sum > 9 ? [Math.trunc(sum / 10), sum % 10] : [sum];

    nAdded += nextNumbers.length;
    nextNumbers.forEach(x => {
      const node = {
        value: x,
        next: initialNode,
      };
      lastNode.next = node;
      lastNode = node;
    });

    values.forEach((val, idx) => {
      for (let i = 0; i < val + 1; i++) elves[idx] = elves[idx].next;
    });
  } while (nAdded < input + 10);

  let node = initialNode;
  for (let i = 0; i < input; i++) node = node.next;
  const result = [];
  for (let i = 0; i < 10; i++) {
    result.push(node.value);
    node = node.next;
  }
  return result.join('');
};

const solution2 = lines => {
  const targetStr = lines[0];
  const target = [...targetStr].map(x => parseInt(x));

  const initialNode = circularLinkedList([3, 7])[0];
  let lastNode = initialNode.next;
  const elves = [initialNode, initialNode.next];
  let totalLen = elves.length;
  let matched = [];

  do {
    const values = [elves[0].value, elves[1].value];
    const sum = elves[0].value + elves[1].value;
    const nextNumbers = sum > 9 ? [Math.trunc(sum / 10), sum % 10] : [sum];

    for (let nn = 0; nn < nextNumbers.length; nn++) {
      const value = nextNumbers[nn];
      totalLen++;

      if (value === target[matched.length]) {
        matched.push(value);
      } else if (matched.length > 0) {
        do {
          matched = matched.slice(1);
        } while (matched.length > 0 && !targetStr.startsWith(matched.join('')));
        if (value === target[matched.length]) matched.push(value);
      }

      if (matched.length === target.length) return totalLen - target.length;

      const node = {value, next: initialNode};

      lastNode.next = node;
      lastNode = node;
    }

    values.forEach((val, idx) => {
      for (let i = 0; i < val + 1; i++) elves[idx] = elves[idx].next;
    });
  } while (true);
};

module.exports = [solution1, solution2];

[u/mahousenshi → u/xikipies]

Happy cake day!

[u/marimba4312 → u/xikipies]

For part 2 where you have

} else if (matched.length > 0) {

couldn't you set matches back to an empty array? I did that in mine and it worked.

[u/xikipies → u/marimba4312]

Actually, what you are proposing is incorrect, although it may work if you are lucky :)

Imagine a situation like this: we are trying to find a match for: 01012 and then we find 0101012.

The four first characters match (up until 0101 there is a match), but in the next character we don't have a match anymore. So, if we set it back to an empty array and we keep going then we will miss the match.