Day 10: Adapter Array

    ratings = set([int(r) for r in data.split('\n')])
    max_rating = max(ratings)
    builtin_rating = max_rating + 3

    @functools.lru_cache
    def find_next_adapter(current):
        if current == max_rating:
            return 1
        count = 0
        for difference in (1, 2, 3):
            if (current + difference) in ratings:
                count += find_next_adapter(current + difference)
        return count

    print(find_next_adapter(0))

def find_adapter(available, target)
  available
    .map { |x| [x - target, x] }
    .sort
    .first
end

def compute_p1(input)
  adapters = input.lines.map(&:to_i).sort
  adapters << adapters.max + 3

  target = 0
  diff_counts = Hash.new(0)
  while ! adapters.empty?
    diff, a = find_adapter(adapters, target)
    #puts "%i -> %i (%i)" % [target, a, diff]
    diff_counts[diff] += 1
    adapters.delete(a)
    target = a
  end

  #puts diff_counts
  return diff_counts[1] * diff_counts[3]
end

Put generally we have: 0 -> 1 (n/a no action); 1 -> 1 (not removable); 2 -> 2 (you can remove either); 3 -> 4 (remove any or all); 4 -> 7 (remove any, all, or two sets of three). This was enough to build out the rest of the sequence, with each new number being the sum of the last three. I ended up pre-computing the first 10 numbers in the sequence, but I'm pretty sure these inputs only actually need the values for 1-4.

def compute_p2(input)
  input = input.lines.map(&:to_i)
  adapters = [0] + input.sort + [input.max + 3]

  groups = adapters[...-1].zip(adapters[1...])
             .reduce([]) { |steps, pair| steps << pair[1]-pair[0] }
             .reduce([]) do |groups, n|
               if groups.last && groups.last.last == n
                 groups.last << n
               else
                 groups << [n]
               end
               groups
             end

  group_counts = groups
                   .find_all { |g| g.first == 1 }
                   .map { |g| g.size }
                   .each_with_object(Hash.new(0)) { |count, h| h[count] += 1 }

  # options per group size scale with sum of previous 3, so we precompute table of options per group size
  table = [1, 1, 2]
  while table.size < 10
    table << table[-3..].sum
  end

  return group_counts.reduce(1) { |product, kv| product * table[kv[0]] ** kv[1] }
end

(define (get-lines parse-line f)
  (with-input-from-file f
    (lambda ()
      (let loop ((line (read-line))
                 (lines '()))
        (if (eof-object? line)
            (reverse lines)
            (loop (read-line)
                  (cons (parse-line line) lines)))))))

(define (one adapters)
  (let loop ((3-count 1)
             (1-count 0)
             (prev 0)
             (remaining adapters))
    (if (null? remaining) (* 3-count 1-count)
        (let* ((x (car remaining))
               (remaining (cdr remaining))
               (diff (- x prev)))
          (case diff
            ((1) (loop 3-count (+ 1-count 1) x remaining))
            ((3) (loop (+ 3-count 1) 1-count x remaining))
            (else (loop 3-count 1-count x remaining)))))))

(define (cdr-n l n)
  (if (= n 0) l
      (cdr-n (cdr l) (- n 1))))

(define (sum lst)
  (fold + 0 lst))

(define (two adapters)
  (let loop ((adapters adapters)
             ;; List of the amount of paths for the last 3 adapters
             (prev-list '(0 0 1))
             (prev-val 0))
    (if (null? adapters)
        ;; The plug is 3 away so the answer is the last item in the list
        (caddr prev-list)
        (let* ((x (car adapters))
               (shift-val (- x prev-val 1))
               (prev-list (cdr-n prev-list shift-val))
               (x-val (sum prev-list)))
          (loop (cdr adapters)
                (append (cdr prev-list)
                        (iota shift-val 0 0)
                        (list x-val))
                x)))))

(define (run lines)
  (let ((lines (sort lines <)))
    (display "One: ") (display (one lines)) (newline)
    (display "Two: ") (display (two lines)) (newline)))

(run (get-lines string->number "input"))

This was relatively straightforward once I understood it. Simply sort the adapters (including the 0 port and the max(adapters) + 3 device port) and then count the differences between each adapter.

import collections
import sys

# Functions

def count_differences(adapters):
    return collections.Counter(
        adapters[i] - adapters[i - 1] for i in range(1, len(adapters))
    )

# Main Execution

def main():
    adapters    = [int(a) for a in sys.stdin]
    adapters    = sorted([0] + adapters + [max(adapters) + 3])
    differences = count_differences(adapters)

    print(differences[1] * differences[3])

if __name__ == '__main__':
    main()

This took me a bit longer because I didn't want to simply brute-force it. I knew there was a dynamic programming solution, but I had to draw it out on a piece of paper before I saw the appropriate relationship.

The idea is that for each adapter, you simply need to look backwards and consider how many ways you could have arrived at that joltage. So the recurrence relationship is: counts(adapter) = sum(counts(adapter - d) where d is 1, 2, or 3).

import sys

# Functions

def count_arrangements(adapters):
    counts = {0: 1}

    for adapter in adapters[1:]:
        counts[adapter] = sum(counts.get(adapter - d, 0) for d in (1, 2, 3))

    return counts

# Main Execution

def main():
    adapters     = [int(a) for a in sys.stdin]
    adapters     = sorted([0] + adapters + [max(adapters) + 3])
    arrangements = count_arrangements(adapters)

    print(arrangements[max(adapters)])

if __name__ == '__main__':
    main()

defmodule AdventOfCode.Day10 do
  def part1(args) do
    args
    |> parse_adapters()
    |> Enum.chunk_every(2, 1, :discard)
    |> Enum.frequencies_by(fn [a, b] -> b - a end)
    |> Map.take([1, 3])
    |> Map.values()
    |> Enum.reduce(&Kernel.*/2)
  end

  def part2(args) do
    args
    |> parse_adapters()
    # Skip the 0-jolt outlet and just init the accumulator with its (known)
    # result since it would require a special case in the reducer function.
    |> Enum.drop(1)
    |> Enum.reduce({1, %{0 => 1}}, fn n, {_, prev_counts} ->
      path_count =
        prev_counts
        |> Map.take([n - 3, n - 2, n - 1])
        |> Map.values()
        |> Enum.sum()

      {path_count, Map.put(prev_counts, n, path_count)}
    end)
    |> elem(0)
  end

  defp parse_adapters(input) do
    input
    |> String.split()
    |> Enum.map(&String.to_integer/1)
    |> add_outlet_and_builtin()
    |> Enum.sort()
  end

  defp add_outlet_and_builtin(adapters) do
    [0, Enum.max(adapters) + 3 | adapters]
  end
end

function main()

    adapters = []
    open("Day10/input.txt") do fp
        adapters = parse.(Int, readlines(fp))
    end

    # Is this as easy as I think it is?
    adapters = [0, adapters..., maximum(adapters) + 3]
    sort!(adapters)
    differences = diff(adapters)
    numOnes = count(differences .== 1)
    numThrees = count(differences .== 3)

    result_1 = numOnes * numThrees

    # It is
    println("Result 1 is ", result_1)

end

main()

@@ -1,3 +1,5 @@
+using Memoize
+
 function main()
 
     adapters = []
@@ -17,6 +19,29 @@ function main()
     # It is
     println("Result 1 is ", result_1)
 
+    result_2 = arrange_adapters(Tuple(adapters))
+
+    println("Result 2 is ", result_2)
+
 end
 
-main()
\ No newline at end of file
+# Just do this recursively and cache, math is hard
+@memoize function arrange_adapters(adapters)
+    if length(adapters) == 1
+        return 1
+    elseif length(adapters) < 4
+        num_ways = 0
+        next_steps = sum(adapters[2:end] .<= adapters[1] + 3)
+        for idx = (1:next_steps) .+ 1
+            num_ways += arrange_adapters(adapters[idx:end])
+        end
+        return num_ways
+    else
+        num_ways = 0
+        next_steps = sum(adapters[2:4] .<= adapters[1] + 3)
+        for idx = (1:next_steps) .+ 1
+            num_ways += arrange_adapters(adapters[idx:end])
+        end
+        return num_ways
+    end
+end

#!/usr/bin/env python3

import sys

def find_jolts(nums):
    diff_1 = 0
    diff_3 = 1  # for last-to built-in joltage
    start = 0

    while nums:
        curr = nums.pop(0)
        if start + 1 == curr:
            diff_1 += 1
            start = curr
        elif start + 3 == curr:
            diff_3 += 1
            start = curr

    return diff_1 * diff_3


def main():
    nums = []
    for num in sys.stdin:
        nums.append(int(num))

    nums.sort()
    print(find_jolts(nums))

if __name__ == '__main__':
    main()

#!/usr/bin/env python3

import sys

def count_seq(n, nums):
    mem = [0] * (n + 1)
    mem[0] = 1

    for i in nums:
        mem[i] = mem[i - 1] + mem[i - 2] + mem[i - 3]

    return mem[n]

def main():
    nums = []
    for num in sys.stdin:
        nums.append(int(num))

    nums.sort()
    print(count_seq(max(nums), nums))

if __name__ == '__main__':
    main()

=ARRAYFORMULA(
   COUNTIF(
    {MIN(A1:A)-0;
     IF(ISBLANK(INDIRECT("A1:A"&MAX(FILTER(ROW(A1:A),A1:A<>"")))),,
     SORT({FILTER(A1:A,A1:A<>MIN(A1:A));MAX(A1:A)+3})-
     SORT({A1:A;MAX(A1:A)+3}))},1)*
   COUNTIF({MIN(A1:A)-0;
    IF(ISBLANK(A1:A109),,
    SORT({FILTER(A1:A,A1:A<>MIN(A1:A));MAX(A1:A)+3})-
    SORT({A1:A;MAX(A1:A)+3}))},3))

With this part, I have `={0;SORT(A:A)}` in G1:G -- not the prettiest.

Then over in H I run this from 4 on, taking off one piece each for the previous rows

=IF(G4-G3<=3,H3,0)+
IF(G4-G2<=3,H2,0)+
IF(G4-G1<=3,H1,0)

</details>

I really wanted to do the second with one formula, but I just couldn't swing it. I have a feeling I could do it with something like MMULT --- but I'm not certain of it. 

var input = new List<int>();
using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input10))
{
	string line;
	while ((line = fs.ReadLine()) != null)
	{
		input.Add(int.Parse(line));
	}
}
input.Add(0);
input.Sort();
input.Add(input.Last() + 3);

var processed = new List<int>();
for (int i = 1; i < input.Count; i++)
{
	processed.Add(input[i] - input[i - 1]);
}
var ones = processed.Count(i => i == 1);
var threes = processed.Count(i => i == 3);

return $"{ones} ones and {threes} threes = {ones * threes}";

Pretty boilerplate - not even super necessary to actually build the diffs array, but it means I can just throw LINQ at it and type faster.

var input = new List<int>();
using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input10))
{
	string line;
	while ((line = fs.ReadLine()) != null)
	{
		input.Add(int.Parse(line));
	}
}
input.Add(0);
input.Sort();
input.Add(input.Last() + 3);
input.Reverse();

var partials = new long[input.Count];
partials[0] = 1;

for (int i = 1; i < input.Count; i++)
{
	bool valid1back = i - 1 >= 0 && input[i - 1] - input[i] <= 3;
	bool valid2back = i - 2 >= 0 && input[i - 2] - input[i] <= 3;
	bool valid3back = i - 3 >= 0 && input[i - 3] - input[i] <= 3;

	partials[i] = (valid1back ? partials[i - 1] : 0) + (valid2back ? partials[i - 2] : 0) + (valid3back ? partials[i - 3] : 0);
}

return $"{partials.Last()} possible connections";

I believe this was my first use of dynamic programming since my algorithms class. This was a satisfying one - I'm pretty sure it was 10 minutes of thinking/whiteboard-sketching, then 5 minutes of typing and watching it work first time.

Part 1 seemed suspiciously easy, you could just sort the numbers and measure the gaps (the length of the explanation, suggesting something horribly complicated, was a bit mean, though). I'm pretty sure it was supposed to be a "hint" for part 2 and a rather good one. The moment I read "trillions" I knew the name of the game: looking for ways to cut the problem into smaller parts.

I noticed that all 3-gaps had to be traversed since you couldn't fill them with alternate routes. Further, there seemed to be no gaps of 2 and no sequences of 1-gaps longer than 4. Also a single 1-gap between two 3-gaps (or the start or the end of your list) didn't allow any alternative routes, either.

So this came down to counting the number of possible routes within those 2, 3 and 4-sequences of 1-gaps, which just happened to be (I counted manually) 2, 4 and 7. A sequence of two 1-gaps followed by a sequence four 1-gaps would allow 2 * 7 different routes and so on. All I had to do was count all those sequences and multiply by the amount of different routes each of them allows.

with open("input.txt") as inputFile:
    adapters = list(map(int, inputFile.read().split("\n")))


def diffList(adapters):
    adapters.sort()
    diffs = []
    last = 0
    for adapter in adapters:
        diffs.append(adapter - last)
        last = adapter
    diffs.append(3)
    return diffs


def testAdapters(adapters):
    diffs = diffList(adapters)
    print("1-jolt differences * 3-jolt differences: ",
          diffs.count(1) * diffs.count(3))


def combinations(adapters):
    diffs = diffList(adapters)
    repeats = 0
    factors = [1, 1, 2, 4, 7]
    combinationsCount = 1
    for diff in diffs:
        if diff == 1:
            repeats += 1
        else:
            combinationsCount *= factors[repeats]
            repeats = 0
    print("Possible combination count:", combinationsCount)


testAdapters(adapters)
combinations(adapters)

use std::env;
use std::io::{prelude::*, BufReader};
use std::fs::File;

#[macro_use] extern crate lazy_static;
lazy_static! {
    static ref ADAPTERS: Vec<i64> = {
        let args: Vec<String> = env::args().collect();
        let file = File::open(&args[1]).expect("Input file not found.");
        let reader = BufReader::new(file);
        let input: Vec<_> = match reader.lines().collect() {
            Err(err) => panic!("Unknown error reading input: {}", err),
            Ok(result) => result,
        };
    
        let mut adapters: Vec<_> = input.iter().map(|x| x.parse::<i64>().unwrap()).collect();
        adapters.sort();
        adapters.insert(0,0);
        adapters.push(adapters.iter().max().unwrap()+3);
        adapters
    };
}

use cached::proc_macro::cached;
#[cached]
fn num_configurations(adapters: &'static [i64], from: i64, to: i64) -> i64 {
    let mut sum = 0;
    for next in &[from+1, from+2, from+3] {
        if next == &to { 
            sum += 1;
        } else if adapters.iter().filter(|x| x == &next).count() == 1 {
            sum += num_configurations(&adapters, *next, to);
        }
    }
    sum
}

fn main() {

    // Part 1
    let diffs1jolt = &ADAPTERS.windows(2)
        .filter(|pair| pair[1]-pair[0] == 1)
        .count();
    let diffs3jolt = &ADAPTERS.windows(2)
        .filter(|pair| pair[1]-pair[0] == 3)
        .count();
    println!("Part 1: {}", diffs1jolt * diffs3jolt); // 1836

    // Part 2
    let plug = &ADAPTERS.iter().max().unwrap();
    println!("Part 2: {}", num_configurations(&ADAPTERS, 0, **plug)); // 43406276662336
}

const fs = require('fs');
const readline = require('readline');

let adapterArray = []

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		adapterArray.push(line);
	}
}

function joltDifference(array, index) {
	let currentAdapter = array[index];
	let nextAdapter = array[index+1];
	return nextAdapter - currentAdapter;
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	// sort into ascending order, to make sure no adapters are skipped
	adapterArray.sort((a,b) => { return a - b; });
	let differences = [];
	let tempIndex = 0;
	// outlet -> first adapter
	differences.push(1);
	// calculate differences
	for (; tempIndex < (adapterArray.length - 1); tempIndex++) {
		differences.push(joltDifference(adapterArray, tempIndex));
	}
	// last adapter -> device's adapter
	differences.push(3);
	// separate the two types of differences
	let oneJolt = differences.filter(element => element == 1);
	let threeJolt = differences.filter(element => element == 3);
	console.log("Found it! Multiplying " + oneJolt.length + " by " + threeJolt.length + " is " + (oneJolt.length * threeJolt.length));
})();

const fs = require('fs');
const readline = require('readline');

let adapterArray = []

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		adapterArray.push(line);
	}
}

function joltDifference(array, index) {
	let currentAdapter = array[index];
	let nextAdapter = array[index+1];
	return nextAdapter - currentAdapter;
}

function possibleAdapters(array, voltage) {
	let eligibleAdapters = [];
	for (const adapter of array) {
		let difference = (adapter - voltage);
		if (difference <= 3 && difference > 0) {
			eligibleAdapters.push(adapter);
		}
	}
	return eligibleAdapters;
}

// returning sequences as an int total, rather than an array of arrays, to save memory?
function findSequences2(array, voltage, sequences = 0, currentSequence = []) {
	// copy the current sequence so we don't add the new values by reference when we recurse
	// ^^ this is what had me stuck for a few hours ^^
	let tempSequence = currentSequence.slice();
	// break condition
	if (array.length == 1) {
		tempSequence.push(voltage);
		sequences++;
		if (sequences % 100000 == 0) {
			console.log("Found sequence " + sequences);
		}
		return sequences;
	} else {
		// find possible next branches
		let possibilities = possibleAdapters(array, voltage);
		// if any branches exist to go to
		if (possibilities.length >= 1) {
			// push the current branch onto the stack and recurse over them
			tempSequence.push(voltage);
			for (const possibility of possibilities) {
				// trim remaining array to save processing time by eliminating elements that won't matter
				let trimmedArray = array.slice(array.indexOf(possibility));
				sequences = findSequences2(trimmedArray, possibility, sequences, tempSequence);
			}
		}
		return sequences;
	}
}

// this works, but runs out of memory
function findSequences(array, voltage, sequences = [], currentSequence = []) {
	// copy the current sequence so we don't add the new values by reference when we recurse
	// ^^ this is what had me stuck for a few hours ^^
	let tempSequence = currentSequence.slice();
	// break condition
	if (array.length == 1) {
		tempSequence.push(voltage);
		sequences.push(tempSequence);
		if ((sequences.length + 1) % 10000 == 0) {
			console.log("Found sequence " + (sequences.length + 1));
		}
		return sequences;
	} else {
		// find possible next branches
		let possibilities = possibleAdapters(array, voltage);
		// if any branches exist to go to
		if (possibilities.length >= 1) {
			// push the current branch onto the stack and recurse over them
			tempSequence.push(voltage);
			for (const possibility of possibilities) {
				// trim remaining array to save processing time by eliminating elements that won't matter
				let trimmedArray = array.slice(array.indexOf(possibility));
				sequences = findSequences(trimmedArray, possibility, sequences, tempSequence);
			}
		}
		return sequences;
	}
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	// adding the outlet voltage
	adapterArray.push(0);
	// adding the device voltage
	adapterArray.push(adapterArray.reduce((a,b) => { return Math.max(a,b); }) + 3);
	// sort into ascending order, to make sure no adapters are skipped
	adapterArray.sort((a,b) => { return a - b; });
	// vv This works, but runs out of memory vv
	//let result = findSequences(adapterArray, adapterArray[0]);
	//console.log("Distinct arrangements: " + result.length);
	// vv This works, but runs out of time vv
	//let result = findSequences2(adapterArray, adapterArray[0]);
	//console.log("Distinct arrangements: " + result);
	
	// Credit to PapaNachos and nothis on Tildes for tips and solutions that led me to this code, which I probably never would have figured out alone...
	let differences = [];
	let sequenceMultiplier = [1,1,2,4,7];
	let sequenceIndex = 0;
	let total = 1;
	let problemString = "";
	for (let i = 0; i < (adapterArray.length - 1); i++) {
		differences.push(joltDifference(adapterArray, i));
	}
	for (const difference of differences) {
		if (difference == 1) {
			sequenceIndex++;
		} else {
			problemString += "*" + sequenceMultiplier[sequenceIndex];
			total *= sequenceMultiplier[sequenceIndex];
			sequenceIndex = 0;
		}
	}
	console.log(problemString);
	console.log("Total combinations: " + total);
})();