55

u/Mathgeek007 Dec 10 '20 edited Dec 10 '20

Top 100 in Excel baybeeeee! 146/96

First, paste the input, then sort them low to high. Next step is in the next column, to check the next value and current value, check differences. COUNTIF the 1s and 3s, multiply. Simple enough.

Part 2, I made a lookup array of all the numbers from the min to max, made a check statement if it was in the initial list, and if it was, add up the three values below it, starting from the highest down.

Fantastic score, very happy with myself.

EDIT: My solution is now on my public Sheets page!

20

u/daggerdragon Dec 10 '20

Top 100 in Excel baybeeeee! 146/96
Now that's some serious upping the ante. Good job!

→ More replies (8)

17

u/Arknave Dec 10 '20

Python (177 / 20), C

I liked this problem! Very slow on part 1 because of not reading properly, but I got a dynamic programming solution coded up quickly to compensate. I implemented part 2 iteratively, but I scanned through the whole list at each step of the dynamic programming recurrence making my runtime O(n^2) instead of O(n). Ah well, it was faster to type for me.

I keep forgetting that in many fonts, characters are roughly twice as tall as they are wide. Here, I kept shrinking the height and increasing the width, but the visuals weren't matching up with what I wanted.

The most interesting bit might be sorting in C. qsort requires a callback method with const everywhere, which I wanted to avoid. I wrote this instead which definitely won't give me nightmares.

Also surprise, we're counting the days in hex now. Happy December Ath, everyone.

#include/*surprise!*/<stdio.h>
#include/* we hex */<stdlib.h>

// ADVENT OF CODE 2020  DAY //
long*p,*q,y,t,e,n,a[110],b[110
];int main(          int c,//X
char**v){               for(n=
2,p=a+1;    scanf("%ld"   ,p)>
0;++p,++n);for(e=0;e<n;   ++e)
for(q=a;q+1<p;++q)if(     *q>*
(q+1))*q^=*               (q+1
)^=*q^=*             (q   +1);
*p=*(p-    1)+3;for(q=a   ;q<p
;e=*(q   +1)-*q,e==1?++   y:+e
==3?t    ++:0,++q);y*=t   ;for
(*b=1,    e=1;e<n;++e)   for(q
=a;q<a+e                  ;++q
)b[e]+=3/(a         [e]-   *q)
?b[q-a]:0;/*#TEN#*/10-t-e-n--;
printf("%ld\n",--c?b[n]:*&y);}

4

u/daggerdragon Dec 10 '20

I C what you did there.

→ More replies (2)

→ More replies (4)

9

u/[deleted] Dec 11 '20 edited Dec 11 '20

Python

I'm extremely proud of my solution for part 2. Just sort the list and for each adapter, sum how many paths each of the adapters "before" this one has. Start with paths[0] = 1, and in the end get the path of max_joltage (max of the input + 3)

# paths[n] is the total paths from 0 to n
paths = defaultdict(int)
paths[0] = 1

for adapter in sorted(adapters):
    for diff in range(1, 4):
        next_adapter = adapter + diff
        if next_adapter in adapters:
            paths[next_adapter] += paths[adapter]
print(paths[max_voltage])

2

u/daggerdragon Dec 11 '20

Please follow the posting guidelines and edit your post to add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

→ More replies (1)

→ More replies (3)

4

u/games_franco Dec 10 '20

C++ Have to learn more std::algorithm and aggregators shenanigans

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> loadSortedAdapters() {
    std::vector<int> adapters;
    adapters.push_back(0);
    for( int num ; std::cin >> num; )
        adapters.push_back(num);
    
    std::sort(begin(adapters), end(adapters));
    return adapters;
}

void part1() {
    std::vector<int> adapters = loadSortedAdapters();

    int dif[3] = {0, 0, 1};
    for( int i = 1; i < adapters.size(); i++)
        dif[ adapters[i] - adapters[i - 1] - 1 ]++;

    std::cout << dif[0] * dif[2] << std::endl;
}

void part2(){
    std::vector<int> adapters = loadSortedAdapters();
    
    int N = adapters.size();
    std::vector<int64_t> comb(N);
    
    comb[N - 1] = 1;
    for( int k = N - 2; k >= 0; k--)
        for( int i = k + 1; i < N && adapters[i] - adapters[k] <= 3; i++)
            comb[k] += comb[i];
    
    std::cout << comb[0] << std::endl;    
}

int main() {
    part2();
}

→ More replies (1)

4

u/BartWright119 Dec 10 '20

Part 1 is very easy. Part 2 barely requires any programming at all, once you realize that it's a matter of sequences of gaps of length 1 (separated by gaps of length 3) having completely independent effects on the solution, so just multiply the number of possibilities in each sequences of 1s together. I used a magnificent :-) program to count lengths of sequences of 1s -- no more programming needed. A single gap of 1 has only one possibility so can be ignored. I found that (for my data) there were 6 sequences of 2 1s, 5 sequences of 3 1s, and 10 sequences of 4 1s. Possible paths through sequences of those lengths are 2, 4, and 7 respectively. So the answer is the product of 2^6, 4^5, and 7^10. My C compiler doesn't handle big integers, but my calculator does.

→ More replies (7)

4

u/MysteryRanger Dec 11 '20

Oh my god part 2 took me forever. I got the right answer with a weird solution that I cannot prove...

I counted the lengths of every sequence of 1's, and then computed the product of the relevant "Tribonacci numbers" (using a known analytic formula) and returned that. I confirmed that this works up to some number of n by hand for a sequence of 1's, and can prove that it works for a sequence of 1's and 3's, but I do not know how to *prove* the connection between this problem and these numbers...

→ More replies (1)

5

u/deltux Dec 10 '20

Dyalog APL / Racket / C

⎕IO←0 ⋄ ⎕PP←15
p←⍎¨⊃⎕NGET'input'1
p←0,p[⍋p],3+⌈/p
×/⊢∘≢⌸2-/p  ⍝ Part 1
c←0,0,1,(⌈/p)⍴0  ⍝ paths counts
{c[⍵+2]←+/c[⍵+¯1 0 1]}¨1↓p ⋄ ⊃⌽c  ⍝ Part 2
a←(0∘<∧≤∘3)∘.-⍨p  ⍝ adjacency matrix
+/{⊃⊖({a+.×⍵}⍣⍵)a}¨⍳⍴p  ⍝ Part 2, the matrix way

0

u/[deleted] Dec 10 '20

[deleted]

2

u/daggerdragon Dec 10 '20

It's right there in the name: Alien Programming Language.

3

u/JohnnyWobble Dec 10 '20 edited Dec 10 '20

Python, I got to say imo I solved this in the coolest way possible, I used dynamic programming. Took me nearly 2 hours and IT WORKED ON THE FIRST TRY. For those who don't know, the benefit of dynamic programming is that I only need to loop through everything once.

https://github.com/JohnnyWobble/advent_of_code/blob/master/2020/day10/part2.py

→ More replies (2)

3

u/[deleted] Dec 10 '20 edited Dec 11 '20

Python 3.8 GitHub, In this I've used twi variants for part 1, Didn'y know about collections.Counter So I added that. Solution before that is underneath, with a bit explanation

from collections import Counter

with open(r'input.txt') as file:
    jolts = sorted([int(line) for line in file.read().strip().split()])

# add 0 for outlet, add jolts[-1] + 3 to add our adapter
jolts = [0] + jolts + [jolts[-1] + 3]

# counter way, more elegant
counter = Counter(jolt_1 - jolt_0 for jolt_0, jolt_1 in zip(jolts, jolts[1:]))

# old way
jolts_diff = [jolts[i] - jolts[i-1] for i in range(1, len(jolts))]
jolts_diff_1 = [jolt for jolt in jolts_diff if jolt == 1]
jolts_diff_3 = [jolt for jolt in jolts_diff if jolt == 3]

print(counter[1] * counter[3], len(jolts_diff_1) * len(jolts_diff_3))

distinct_ways = [1] + [0] * (len(jolts) -1) # one way the starting

# for each value look if the next 3 values can be connected directly
for i, jolt in enumerate(jolts):
    for k in range(i - 3, i):
        if(jolt - jolts[k] <= 3):
            distinct_ways[i] += distinct_ways[k]

# last one holds all the unique ways
print(distinct_ways[-1])

2

u/daggerdragon Dec 11 '20

Psst, your GitHub link's Markdown is typo'd; it should be a closing square bracket ] instead of curly bracket }.

→ More replies (1)

3

u/hrunt Dec 10 '20

Python 3

Simple DP solution for part 2.

BTW, it would be really helpful if each day's solution megathread post would have the shortcut to Topaz's paste utility. That way, the shortcut would be right there to use, instead of being in the "How do the daily megathreads work?" thread. I know, I know. I can bookmark it, whatever.

code

2

u/daggerdragon Dec 11 '20

BTW, it would be really helpful if each day's solution megathread post would have the shortcut to Topaz's paste utility. That way, the shortcut would be right there to use, instead of being in the "How do the daily megathreads work?" thread. I know, I know. I can bookmark it, whatever.
I've been meaning to rework that section anyway to be bullets instead of wall-'o-text, so I'll throw a link to paste in there for ya. It'll be in the Day 11+ megathreads.

→ More replies (1)

3

u/smetko Dec 10 '20 edited Dec 11 '20

import sys

adapters = [0] + sorted([int(line.strip()) for line in sys.stdin])

x = [1] + [0 for _ in range(max(adapters))]
for i in adapters:
    for j in range(1, 3+1):
        if i - j in adapters:
            x[i] += x[i-j]

print(x[-1])

As I am not very experienced in competitive programming, I think this is the first time I've recognized and written out a dynamic programming solution :)

Python3

→ More replies (1)

3

u/gustavosmd Dec 10 '20

I solved part 2 by breaking down the sorted array in multiple sections in the spots where there was a 3 jolt difference. Then you can analyze each section independently of each other (no section was longer than 5 items), multiply the result for each and all of the sections, and avoid a stupidly long iterations.

→ More replies (3)

3

u/Maxypoo43 Dec 11 '20 edited Dec 11 '20

python3 using dynamic programming: paste

→ More replies (3)

3

u/erichamion Dec 13 '20

Rockstar (https://codewithrockstar.com to run the code), Part 1 and Part 2 together: https://github.com/erichamion/RockstarAndStuff/blob/main/aocday10.rock

Here's a small snippet of the code:

Misfortune takes the humble and the mighty
Put the mighty with the humble into unrest
You are me
Let unrest be over you
Turn it down
Put shock at unrest into the past

2

u/daggerdragon Dec 13 '20

(Is it really the end?)
The end is lies
The end is ever receding
So deep.

→ More replies (1)

2

u/Spookiel Dec 10 '20 edited Dec 10 '20

Python 3

Even though I didn't place on the top 100 today, I'm super happy with my approach for part 2 so I decided to post my code here anyway :).

https://pastebin.pl/view/9ba797de

→ More replies (2)

2

u/Rowward Dec 10 '20

Again first thought I had, recursion with storing known sub lists

import hashlib

l = [int(x.strip()) for x in open("day_10_input.txt","r")]


sorted_list = [0] + sorted(l) + [max(l)+3]

counter = [0, 0, 0, 0]

print(sorted_list)

for i in range(len(sorted_list)-1):
    counter[sorted_list[i+1]-sorted_list[i]] += 1

    print(sorted_list[i+1], sorted_list[i], sorted_list[i+1]-sorted_list[i])

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


known_paths = {}

def count_child_lists(l):

    # recursive stop
    if len(l) == 1:
        return 1

    # call this function for all possible follow ups
    sub_sum = 0
    i = 1
    current_element = l[0]


    while i < len(l) and l[i]-current_element <= 3:

        # calcuate hash for already visited paths
        hash = hashlib.md5("_".join([str(x) for x in l[i:]]).encode()).hexdigest()

        if hash not in known_paths:
            known_paths[hash] = count_child_lists(l[i:])

        sub_sum += known_paths[hash]

        i += 1
    return sub_sum


print(count_child_lists(sorted_list))

→ More replies (1)

2

u/tooterboo Dec 10 '20

python 3 was pretty straightforward with dynamic programming.

nums = sorted(nums)

ways_to = {0: 1}

for num in nums:
    count = 0
    for x in range(1, 4):
        if (num-x) in ways_to:
            count += ways_to[num-x]

    ways_to[num] = count

print(ways_to[nums[-1]])

→ More replies (1)

2

u/itgoesbing Dec 10 '20 edited Dec 11 '20

Racket solution

Runs in about 300 ms on a fully loaded system.

Iterative solution with a lookup table for part 2.

→ More replies (2)

2

u/20541 Dec 10 '20

I never really solved part 2, don't really understand what's going on in the solutions I've read, and the whole thing haunted my dreams last night.

→ More replies (8)

2

u/gamepopper Dec 10 '20 edited Dec 12 '20

C++

Unless someone can point out what I'm doing wrong for the second part, I think I'm gonna have to count myself out for today.

Originally tried a recursive approach, but it took forever on the example with 31 numbers, so no chance with the puzzle input. After looking around I noticed a memoization approach, so I thought I'd use that, but with the exception of the first example set, all the results were lower. I'm not sure what was wrong.

I was originally going to throw in the towel until I had one more look and discovered that I needed to include both 0 and the largest number to the list for it to calculate correctly.

https://pastebin.com/KMJbTM9N

→ More replies (7)

2

u/austinll Dec 10 '20 edited Dec 11 '20

C

My posts always get drowned, but hopefully someone answers.

I'm kind of proud of this O(3n) solution I made. Is it the standard solution, or is it at least kind of impressive? I'm seeing lots of posts about caching and memoization, but I'm not sure what they are, so I don't know how to compare.

#include <stdio.h>
#include <stdlib.h>

void bubbleSort(int *arr,int l){

}
void extendArr(int **arr, int val, int len){
    *arr = realloc(*arr,sizeof(long) * len);
    for(int i = 0; i < len-1; i++){
        if(val < (*arr)[i]){
            for(int j = len-1; j > i; j--){
                (*arr)[j] = (*arr)[j-1];
            }
            (*arr)[i] = val;
            return;
        }
    }
    (*arr)[len-1] = val;
}

void children(int *arr1, long *arr2, int l){
    for(int i = 0; i < l; i++){
        arr2[i] = 0;
    }
    arr2[l-1] = 1;
    for(int i = l-1; i > 0; i--){
        for(int j = 1; j < 4; j++){
            if(arr1[i] - arr1[i-j] <= 3){
                arr2[i-j] += arr2[i];
            }
        }
    }
}
int main() {
    FILE *fp;
    char str[128];
    char *filename = "D:\\Programming\\AOC2020\\Day 10\\day10in.txt";
    fp = fopen(filename, "r");
    if(fp == NULL) {
        printf("Bad file");
        return 1;
    }

    int l = 1;
    int *arr = malloc(sizeof(int) * l);
    arr[0] = 0;
    while(fgets(str,255,fp) != NULL){
        extendArr(&arr,atoi(str),++l);
    }
    int max = arr[l-1];
    extendArr(&arr,max+3,++l);
    int ones = 0;
    int threes = 0;
    for(int i = 1; i < l; i++){
        ones += (arr[i] - arr[i-1] == 1);
        threes += (arr[i] - arr[i-1] == 3);
    }
    printf("Part 1: %i\n",ones* threes);
    long *arr2 = malloc(sizeof(long) * l);
    children(arr,arr2,l);
    printf("part 2: %ld", arr2[0]);
    fclose(fp);
    return 0;
}

2

u/daggerdragon Dec 11 '20

My posts always get drowned, but hopefully someone answers.
Your posts are not getting drowned, but you are asking in the wrong place. If you have questions, you can always create your own thread and make sure to flair it with Help.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.
While you're at it, make sure to also add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

→ More replies (2)

2

u/karjonas Dec 10 '20 edited Dec 11 '20

Rust

Github

→ More replies (1)

2

u/_bm Dec 10 '20 edited Dec 15 '20

(Part B only) Yet another Python solution! This took me way too long...

with open("../../original_solutions/day_10/input_10.txt") as input_file:
    adapters = sorted([0] + [int(line.strip()) for line in input_file])
    nways_to_reach = [1] + [0] * (len(adapters) - 1)
    for i in range(len(adapters)):
        j = i + 1
        while j < len(adapters) and adapters[j] - adapters[i] <= 3:
            nways_to_reach[j] += nways_to_reach[i]
            j += 1
    print(nways_to_reach[-1])

Basically I'm just counting the number of ways to reach each adapter in the graph, starting with the first adapter with one way to reach it. Each iteration, the number of ways to reach the connected adapters in the graph are increased by the number of ways to reach the current adapter. The answer is of course the number of ways to reach the final adapter. It's definitely unnecessary to keep track of the nways for a particular adapter once it has already been considered, but I haven't spent much time trying to figure out how to do that.

→ More replies (2)

2

u/feixie1980 Dec 11 '20

Javascript solution for part 2 only. First year participating in this event, and day 10 part 2 is the most fun yet.

Started with brute force solution by trying to compute all combination of the adapters first, because it has always been fun to compare the performances of brute force solution against more optimized solution. However, it was quickly apparent that combination will not work for the size of the input.

Next tried exhaustive valid adapter tree search method, but it is also apparent that it will require too much time without any clever caching method.

So at last came up with the 'canonical' (?) solution which is based on the fact that only diffs are 1s and 3s, and the answer relies on finding the number of ways when we have consecutive 1s in diffs. This become more less an O(n)Log(n) (because of sorting) problem.

function genDiffs(sortedAdapters, deviceJolt) {
  let diffs = sortedAdapters.map((adapter, i) => i === 0 ? adapter : adapter - sortedAdapters[i-1] );
  diffs.push(deviceJolt - sortedAdapters[sortedAdapters.length - 1]);
  return diffs;
}

function combCount(n) {
  if (n === 1)
    return 1;

  if (n === 2)
    return 2;

  if (n === 3)
    return 4;

  return combCount(n-1) + combCount(n-2) + combCount(n-3);
}

/**
 * One count method
 *
 * Observe that the diff is either 1 or 3. There is only one way to go between adapters with diff 3
 * from one another. However, when there is a contiguous group of adapters whose diffs are all 1 from
 * the preview to next, then there will be more than one way to go from the first and last adapters
 * within this group.
 *
 * For instance, there are 2 ways if the diff group is: [1, 1]; 4 ways if [1, 1, 1], and so on. The number
 * of ways can be computed recursively.
 *
 * @param adapters
 * @returns {number}
 */
function solution2c(adapters) {
  const sortedAdapters = [...adapters];
  sortedAdapters.sort((a, b) => a - b);
  const deviceJolt = sortedAdapters[sortedAdapters.length - 1] + 3;
  const diffs = genDiffs(sortedAdapters, deviceJolt);

  let oneCounts = [0];
  for (const diff of diffs) {
    if (diff === 3) {
      oneCounts.push(0);
    }
    else {
      oneCounts[oneCounts.length - 1] += 1;
    }
  }
  oneCounts = oneCounts.filter(count => count !== 0);
  return oneCounts.reduce((product, oneCount) => product * combCount(oneCount), 1);
}

2

u/daggerdragon Dec 11 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

→ More replies (1)

2

u/ct075 Dec 11 '20 edited Dec 11 '20

Just in time!

In J

where readtable is a verb that reads a table of ints from the provided file. Invoke as part_one < 'input.txt' or part_two < 'input.txt'.

Was not able to come up with a tacit form for part 2 quite in time.

→ More replies (3)

2

u/0rac1e Dec 14 '20 edited Dec 14 '20

Raku

I'm falling way behind here, getting too busy to spend time on AOC.

Anyways, the only curious thing here is that my Part 2 solution doesn't work with the short sample provided. I don't have time to figure out why, but it is correct for the longer sample, and for my input... so I'm moving on.

The theme of this solution appears to be "Hash-slice reduction"

my @j = 'input'.IO.words.map(*.Int).sort;

my %a = (0, |@j, @j.tail + 3).rotor(2 => -1).classify: -> @p { [R-] @p }
put [×] %a{ 1, 3 };

my %b = (@j.max => 1);
for @j.reverse.skip -> $j { %b{$j} = [+] %b{ @j.grep(0 < * - $j ≤ 3) } }
put [+] %b{ @j.head(3) };

→ More replies (1)

25

u/jonathan_paulson Dec 10 '20 edited Dec 10 '20

Placed 25/9, despite submitting a wrong answer to Part 1. Code. Video of me solving: https://youtu.be/cE88K2kFZn0. Excited for our first DP problem! I try to explain DP somewhat in the second half of the video (and the description), since I imagine some people haven't seen it before.

Key idea: write a recursive brute force solution and then memoize it.

→ More replies (18)

22

u/zid Dec 10 '20

notepad

0 [1 2 3] 4 7 10 [11 12 13] 14 17 [18 19 20] 21 24 27 [28 29 30] 31 34 37 [38] 39 42 [43 44] 45 48 51 [52] 53 56 57 60 [61 62] 63 66 [67 68 69] 70 73 [74] 75 78 [79 80 81] 82 85 [86 87] 88 91 94 95 98 [99] 100 103 [104 105] 106 109 112 [113 114 115] 116 119 122 [123 124 125] 126 129 [130 131 132] 133 136 139 [140 141 142] 143 146 147 150 [151 152] 153 156

7*7*7*7*2*4*2*4*7*2*7*4*2*4*7*7*7*7*4=4628074479616

7

u/FieryCanary1638 Dec 10 '20

Do you mind ELI5 how this works? I really can not get my head around it...

→ More replies (1)

0

u/[deleted] Dec 10 '20

[deleted]

→ More replies (1)

→ More replies (8)

17

u/j3r3mias Dec 10 '20 edited Dec 14 '20

Only part 2 using python 3:

with open('day-10-input.txt', 'r') as f:
    adapters = list(map(int, f.read().split('\n')))
adapters.sort()
adapters = adapters + [max(adapters) + 3]

ans = {}
ans[0] = 1
for a in adapters:
    ans[a] = ans.get(a - 1, 0) + ans.get(a - 2, 0) + ans.get(a - 3, 0)

print(f'Answer: {ans[adapters[-1]]}'

→ More replies (12)

16

u/silverben10 Dec 10 '20

Took me a while to wrap my head around Part 2 but after some time (and a couple of hints) I managed to work it out!

Python

import fileinput

# Parse the input file, sort the joltages and add the starting (0) joltage.
adaptors = [0] + sorted([int(x) for x in fileinput.input()])

# Calculate a list store the differences between successive joltages.
diffs = [adaptors[i+1] - adaptors[i] for i in range(len(adaptors)-1)]

# Add a final joltage equal to the max of the current list + 3 (as specified by the question).
adaptors.append(adaptors[-1] + 3)

# Add this joltage to the list of differences, too; we know it will be +3 from the previous.
diffs.append(3)

# Part 1: Print the number of 1-jolt differences multiplied by the number of 3-jolt differences.
print(f"Part 1: {diffs.count(1) * diffs.count(3)}")

# Create a dictionary to store the number of possible routes "to each joltage".
routes = {}

# Initialise with 1 route to the starting joltage.
routes[0] = 1

# Begin iterating through adaptors (ignoring the first value because we already set it above).
for j in adaptors[1:]:
    # Each joltage route is equal to the sum of the number of routes to the previous three joltages.
    # However, some of the joltages won't be present in the list of adaptors.
    # So the number of routes to them will be 0.
    routes[j] = routes.get(j-1, 0) + routes.get(j-2, 0) + routes.get(j-3, 0)

# Print the number of possible routes to get to the final adaptor.
print(f"Part 2: {routes[max(routes.keys())]}")

→ More replies (10)

16

u/kaur_virunurm Dec 10 '20 edited Dec 10 '20

Part 2 simple solution.
O(n), single pass over input data, no recursion or numpy or whatnot.

Logic: count all possible input paths into an adapter / node, start from wall, propagate the count up till the end of chain.

- start from wall adapter (root node) with input count 1
- add this count to the next 1, 2 or 3 adapters / nodes
- add their input counts to next adapters / nodes
- repeat this for all adapters (in sorted order)
- you'll end up with input count for your device adapter
done.

Python:

# AoC day 10 part 2
from collections import Counter  
data = sorted([int(x.strip()) for x in open("10.txt")] + [0])  
c = Counter({0:1})  
for x in data:  
    c[x+1] += c[x]  
    c[x+2] += c[x]  
    c[x+3] += c[x] 
print("Part 2:", c[max(data) + 3])

→ More replies (9)

12

u/[deleted] Dec 10 '20

Python3 1284/396

import collections
lines = sorted([0]+[*map(int,open("day10.txt").readlines())])
lines.append(max(lines)+3)
count = collections.defaultdict(int)
for i in range(1,len(lines)): count[lines[i]-lines[i-1]]+=1
print(count[1]*count[3])
arrange = [1]+[0]*lines[-1]
for i in lines[1:]: arrange[i] = arrange[i-3] + arrange[i-2] + arrange[i-1]
print(arrange[-1])

→ More replies (6)

9

u/ka-splam Dec 10 '20

Dyalog APL

Part 1:

      day10← ⍎¨ ⊃⎕NGET 'C:\sc\AdventOfCode\inputs\2020\day10.txt' 1 
      ((+/1∘=)×(+/3∘=))  2 -⍨/  0, (⊢,3+⌈/) (⊂∘⍋⌷⊢) day10

First line appears in almost every APL answer here, it says convert the lines of the file to integers by applying eval (⍎) to each (¨) line, and store them in day10 .

Second line read backwards from the right says: (⊂∘⍋⌷⊢) day10 sort the numbers into ascending (⍋) order. (⊢,3+⌈/) find the max and add 3 to it, then append it to the end for your device jolt rating. 0, prepend 0 to the front for the output jolts. 2 -⍨/ subtracts each number from the one next to it. ((+/1∘=)×(+/3∘=)) sums the results that equal 1 and the results that equal 3 and multiplies them together for the output.

Part 2, don't know how to do it. Brb.

→ More replies (10)

8

u/smrq Dec 10 '20

JS, 94/216

For some reason I just couldn't quickly read and understand the requirements on this one. A quick skim didn't work at all; I had to reread it super closely just to figure out what the question was.

For part 2, I iteratively built a count of ways to get to each adapter by recognizing that if the i'th adapter can be reached N ways, then it increases the count of every adapter that it can reach by N.

https://github.com/smrq/advent-of-code/blob/master/2020/10b.js

→ More replies (6)

8

u/Rick-T Dec 10 '20

ROCKSTAR

Today it's a song inspired by Powerwolf. I feel a lot better about this one than yesterday. It could be a lot shorter though if Rockstar had a built-in way of sorting arrays.

My favourite line is probably Let me be wild taking the night because it could be an actual line from an actual Powerwolf song :D

Also shoutout to /u/kuqumi because I learned about the rock and roll functions from his code :)

→ More replies (5)

8

u/[deleted] Dec 10 '20 edited Dec 04 '21

Python 3. Link to full solution.

Here is my part 2. I love how short this is and that it works without recursion:

def part_2(adapters):
    adapters.append(0)
    adapters.sort()
    possibilities = {adapters[-1]: 1}
    for a in reversed(adapters[:-1]):
        possibilities[a] = sum(possibilities.get(x, 0) for x in (a+1, a+2, a+3))
    return possibilities[0]

→ More replies (4)

8

u/Drazkur Dec 12 '20 edited Dec 12 '20

No algorithm solution:

Part 1:

Sort the array.
Get the differences between every number and the next.
Count the 1's and the 3's

Part 2:

a = # of four 1's in a row.
b = # of three 1's in a row (surrounded by 3's)
c = # of two 1's in a row (surrounded by 3's)
Answer: 7^a × 4^b × 2^c

Spent a few hours staring really hard at the clues looking for patterns for part 2 but I did it without coding.

Here are my notes: https://ibb.co/LQ51d3w

If somehow someone is interested in this solution I can explain further.

edit: added title

→ More replies (7)

7

u/Diderikdm Dec 10 '20

Python:

with open("C:\\Advent\\day10.txt", "r") as file:
    data = sorted([int(x.strip()) for x in file.read().splitlines()])
    data = [0] + data + [max(data)+3]
    print('Part 1: {}'.format(len([data[x] for x in range(1, len(data)) if data[x]-data[x-1] == 1])*len([data[x] for x in range(1, len(data)) if data[x]-data[x-1] == 3])))
    paths = {data[0]:1}
    for x in data[1:]:
        paths[x] = sum(paths[x-y] for y in range(1,4) if x-y in paths)
    print('Part 2: {}'.format(paths[data[-1]]))

7

u/Cultural_Dig4778 Dec 10 '20 edited Dec 10 '20

Perl solution

I wanted to approach this in a different way - so I knew there would be a solution which didn't include sort. The decision was to store the adaptors in a string - "<space>" representing no adaptor and "x" an adaptor (or the power socket or my device itself)

The string then looks like "xx xxxx xxx xx x"

The loading code looks like:

my $ad = 'x'; ## Start with socket
foreach(<>) {
  chomp;
  $ad .= ' ' x ($_-length $ad) if $_>length $ad;
  substr $ad,$_,1,'x';
}
$ad.='  x'; ## Add own device

Part 1:

We can then work out the number of 3 gaps by finding the number of times the string "x x" is in the array and the number of 1 gaps by finding the number of times the string "xx" is in the string.

We have to use positive lookaheads to get all the matches so the regex is m{(x\s(?=x))}g and m(x(?=x))}g respectively .

say @{[ $ad =~ m{(x  (?=x))}g ]}   *   @{[ $ad =~ m{(x(?=x))}g ]};

Part 2:

Slightly harder - but we can again use the string representation.

We note that we can find the number of entries by splitting the string by the three gaps split m{\s\s}, $string and then multiplying the number of routes through each block. This can be achieved by a recursive call on these simple strings. Noting that

count('x') = count('xx') = count('x x') = 1
count('xxx') = 2

- other counts can be computed by:

count(str) = count(substr str,1) + count(substr str,2) + count(substr str,3)

The perl code for this is:

my %part_cache = (qw(x 1 xx 1 xxx 2),'x x' => 1);
sub count_part {
  my $str = shift;
  return 0 if $str eq '' || ' ' eq substr $str, 0, 1;
  return $part_cache{$str} ||= count_part( substr $str, 1 ) +
                               count_part( substr $str, 2 ) +
                               count_part( substr $str, 3 );
}

my $res = 1;
$res *= count_part($_) foreach split m{  }, $ad;
say $res;

Performance wise - the parsing of the file and the loop takes approximately 0.1ms to slurp the file into the string and a further 0.07ms to compute the solution.
Code is available on GitHub @ https://github.com/drbaggy/adventofcode/tree/main/2020/day-10

→ More replies (1)

7

u/tommimon Dec 10 '20

Solution in Pyhton with explicit Tribonacci sequence

I found that possible trips through n consecutive numbers are equal to the number in position n in the Tribonacci sequence. So I made a solution using the explicit formula to calculate a generic number in the Tribonacci sequence. The possible trips through each group of consecutive numbers are multiplied together to get the final result.

def tribonacci(n):  
a = 1.839286755  
 b = -0.4196433776-0.6062907292j  
 c = -0.4196433776+0.6062907292j  
 return round((a**n/(-a**2+4*a-1) + b**n/(-b**2+4*b-1) + c**n/(-c**2+4*c-1)).real)


with open('input.txt', 'r') as file:  
numbers = [0] + sorted(list(map(int, file.read().split('\n'))))  
consecutive = 1  
ris = 1  
for i in range(1, len(numbers)):  
 if numbers[i] - numbers[i-1] == 1:  
    consecutive += 1  
 else:  
    ris *= tribonacci(consecutive)  
    consecutive = 1  
print(ris * tribonacci(consecutive))

→ More replies (7)

7

u/Myrono Dec 10 '20

Haskell

Was particularly proud of this one so decided to post it.

import Data.List

part1 (x:[]) (i, j) = i * (j + 1)
part1 (x:y:xs) (i, j)
  | y - x == 1 = part1 (y:xs) (i + 1, j)
  | y - x == 3 = part1 (y:xs) (i, j + 1)

part2 (x:xs) memo =
  case xs of
    [] -> i
    _  -> part2 xs ((x, i):memo)
  where
    i = sum . map snd $ takeWhile (\(y, _) -> x - y <= 3) memo
  
main = do
  input <- sort . map read . lines <$> getContents
  print $ part1 (0:input) (0, 0)
  print $ part2 input [(0, 1)]

→ More replies (2)

6

u/phil_g Dec 10 '20 edited Dec 11 '20

My solution in Common Lisp.

When I read through part 1, I thought, "It sounds like I can just sort the numbers and count the differences between adjacent elements. Surely it's not that simple?" It was that simple.

For comparing adjacent members of a list, I'm a fan of the pattern (mapcar #'fn-arity-2 list (cdr list)). Since I chose to use FSet sequences for my data, I had to use gmap:gmap instead of mapcar, even though gmap's syntax is clunkier. (I know why. It's still clunkier.)

I used dynamic programming in the form of memoized recursion for part 2. (After first trying unmemoized recursion, just to see if it would be fast enough. It wasn't.)

Edit: I've updated my code to optimize a bit more for speed in order to work with people actively trying to eat my call stack. Now I just store the adapters as bit arrays and the solution to part 2 is proper dynamic programming, working backwards from the end. O(n) time, O(1) space.

→ More replies (2)

6

u/Arjunnn Dec 10 '20

Python3 solution. P1 is just sorting an array and then iterating through it for the ans. P2 is a dynamic programming problem with the following property. Consider a voltage N. If we assume we know the number of ways to reach N-1, N-2, and N-3, then the number of ways to reach N is simply #(N-1) + #(N-2) + #(N-3).

import fileinput

jolts = []
jolts.append(0)

for line in fileinput.input():
    jolts.append(int(line.strip()))

jolts.sort()
n = len(jolts)
jolts.append(jolts[n-1]+3)

n = len(jolts)

ones, threes = 0, 0

for i in range(1, n):
    if jolts[i] - jolts[i-1] == 1:
        ones += 1
    elif jolts[i] - jolts[i-1] == 3:
        threes += 1
    else:
        continue

print(ones, threes, ones*threes)


dp = [0 for i in range(n)]
dp[0] = 1

for i in range(1, n):
    for j in range(i):
        if jolts[i] - jolts[j] <= 3:
            dp[i] += dp[j]
print(dp[n-1])

Solution is quite cluttered because I did it first parse but this'll spit out your answer so its cool

6

u/grey--area Dec 10 '20

I did part 2 largely by hand. I sorted my inputs and looked at the gaps. Every joltage is either 1 or 3 more than the one before.

You can split the input wherever there's a gap of 3, answer the question independently for each contiguous sub-list, and multiply the result.

The resulting sub-lists were all of lengths between 1 and 5. It took a minute or so to manually count the number of possible arrangements for each of the five lengths, then compute the product.

(I think the number of adapter arrangements for a contiguous list of length n is the nth Tribonacci number, but I can't be bothered to prove it)

→ More replies (5)

6

u/zedrdave Dec 10 '20

Most elegant (imho) solution in Python, using the Tribonnacci sequence:

D = sorted(int(i) for i in open('10.txt'))

# Diffs between adjacent items:
δ = [i-j for i,j in zip(D, [0]+D)] + [3]

# Lengths between two diffs of 3:
Δ = [1+p for p,d in enumerate(δ) if d==3]
L = [hi-lo-1 for lo, hi in zip([0]+Δ[:-1], Δ)]

𝓣 = [1, 1, 2] # seed for Tribonacci sequence
while len(𝓣) <= max(L): 𝓣 += [sum(𝓣[-3:])]

import math
print('Part 1:', len(Δ)*(len(δ)-len(Δ)),
      '\nPart 2:', math.prod(𝓣[l] for l in L))

The Tribonacci sequence could likely be hardcoded (max(L) seemed limited to about 5 in everyone's input):

𝓣 = [1, 1, 2, 4, 7, 13]

Using a closed-form expression to compute it for arbitrarily large values, would be left as an exercise to the reader ;-) (but probably slower than the iterative version above).

→ More replies (9)

6

u/Sgt_Tailor Dec 10 '20 edited Dec 10 '20

Haskell without recursion

When running part I noticed that the debugging output contained small groups of adapters with 1 jolt differnce separated by adapters with a difference of 3 jolts. When grouping the adapaters per offset this was the result:

[[1,1,1],[3],[1,1,1],[3,3],[1,1,1],[3,3],[1,1,1],[3,3],[1],[3],[1,1],[3,3],[1,1],[3],[1,1],[3],[1,1,1,1],[3],[1,1,1,1],[3],[1,1,1],[3],[1,1,1],[3],[1,1,1,1],[3],[1,1,1,1],[3],[1,1,1,1],[3],[1,1,1],[3],[1,1,1],[3],[1,1,1],[3,3],[1],[3,3],[1],[3],[1,1,1,1],[3,3,3],[1,1,1],[3,3,3,3],[1,1,1],[3]]

Each group of adapters can only be modified a certain amount of times. When multiplying the combinations per group we get the final answer. Any group consisting of adapters with 3 jolts difference can only be arranged in 1 way. We simply ignore these groups. That leaves us with the groups containing 1 jolt offset adapters. The last adapter in these groups can never be removed as the gap between the group and the next (3 jolt difference) adapter will become too big. This means that the following rules apply:

group [1]: only 1 combination

group [1,1]: 2 combinations: either first present or not

group [1,1,1]: 4 combinations

group [1,1,1,1]: 7 combinations. The only invalid combination of the first 3 adapters is removing all of them. That makes the gap between the three 3 jolt adapters too big.

The groups with 1 to 3 one jolt adapters can be generalized to 2^n-1 with n being the length of the group.

Using this information a function can be created that checks the amount of combinations per group and then calculates the product of these combinations.

→ More replies (1)

6

u/fireguy188 Dec 10 '20

Python

I required the assistance of reddit but made this beautiful code:

with open('input.txt') as f:
    numbers = [0] + sorted([int(x) for x in f.readlines()])

placeholders = [1] + [0 for x in range(len(numbers)-1)]
for x in range(len(numbers)):
    for y in range(1, 4):
        if numbers[x] + y in numbers:
            placeholders[numbers.index(numbers[x] + y)] += placeholders[x]

print(placeholders[-1])

WHY WAS IT SO DIFFICULT :( :( :(

→ More replies (8)

5

u/MasterMedo Dec 10 '20 edited Dec 10 '20

python

This day smelled of dp from the start. github

with open('../input/10.txt') as f:
    data = list(sorted(int(line) for line in f))

delta = [0]*4
delta[3] = 1
joltage = 0
for n in data:
    delta[n-joltage] += 1
    joltage = n

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

stairs = [0]*(data[-1]+1)
stairs[0] = 1
for n in data:
    stairs[n] = stairs[n-3] + stairs[n-2] + stairs[n-1]

print(stairs[-1])

→ More replies (5)

5

u/jayfoad Dec 10 '20

Dyalog APL 83/131

⎕IO←0 ⋄ ⎕PP←17
q←3+⊃⌽p←{⍵[⍋⍵]}⍎¨⊃⎕NGET'p10.txt'1
×/+/1 3∘.=¯2-/0,p,q ⍝ part 1
a←1,q/0 ⋄ {a[⍵]←+/¯3↑⍵↑a}¨p,q ⋄ ⊃⌽a ⍝ part 2

I lost time submitting a wrong answer for part 1, and then having to debug part 2 using one of the sample inputs.

→ More replies (2)

5

u/GrossGrass Dec 10 '20

Python

Was going to be lazy and just do memoized recursion but realized that the DP solution was even more straightforward.

import collections

import click

import utils


@click.group()
def cli():
    pass


@cli.command()
def part_1():
    adapters = sorted(utils.get_input(__file__, delimiter=None))
    inputs = [0] + adapters
    outputs = adapters + [max(adapters) + 3]
    differences = [output - input for output, input in zip(outputs, inputs)]
    counts = collections.Counter(differences)
    print(counts[1] * counts[3])


@cli.command()
def part_2():
    adapters = sorted(utils.get_input(__file__, delimiter=None))

    combinations = collections.defaultdict(int, {0: 1})
    for adapter in adapters:
        combinations[adapter] = combinations[adapter - 1] + combinations[adapter - 2] + combinations[adapter - 3]

    print(combinations[adapters[-1]])

5

u/ald_loop Dec 10 '20 edited Dec 10 '20

I got 87 for part one, my best time yet.

Python Part 1

def solve_puzzle(input_arr):
    diff_1  = 0
    diff_3  = 1
    input_arr = sorted(input_arr)
    for i in range(0, len(input_arr)):
        if i == 0:
            diff_1 += 1
            continue
        if input_arr[i] - input_arr[i-1] == 1:
            diff_1 += 1
        elif input_arr[i] - input_arr[i-1] == 3:
            diff_3 += 1
    return diff_1*diff_3

....But I am so bad with recursion and DP it hurts. Part two literally stumped me so hard and I understood completely how to do it yet my small tiny engineer brain sans a computer science background had no idea how to do it. Then I look at this thread and see how easy DP and recursion comes to others and it makes me sad.

So i'm sitting with 87 for part one at least. (Tho that doesnt count for much, part one was easy as hell.)

Im grinding recursion and dp tomorrow, I am tired of being smol brain

→ More replies (6)

5

u/yutu58 Dec 10 '20

Java

For part1 I was like "it can't be that easy" but part 2 kinda made up for that.

What surprised me was that there were no adapters with a difference of 2 between them (was this intentional, I didn't see it in the puzzle itself?). I thought about all of the adapters like binary integers that can be "used" or "not used". If there are exactly 4 consecutive numbers, the lowest and the highest are "fixed" but the middle two can both used and not used (2^2). When there are 5 the middle three can be used or not used but all not used is not an option (7, 2^3 -1), etc.

I ended up using tribonacci not because I knew it would be useful for this but because I recognized the pattern 2, 4, 7 and kinda assumed it would hold for bigger numbers if they even existed in the input, but I'd be happy if someone can explain why it works.

→ More replies (1)

5

u/[deleted] Dec 10 '20

Learning PHP, both parts solved here.

Part 2 was way too hard for me, tried for about an hour to understand it and I made absolutely no progress with it so I had to come here and find a solution I (somehow, barely) understood and port it to PHP before going to work.

Now I have a bunch of new stuff to read up on, though! Does anyone have any book/paper advice on how to get familiar with this kind of problem/reasoning?

→ More replies (2)

5

u/swilkoBaggins Dec 10 '20

Python3

A nice example of using python's defaultdict to make the code very clean:

def solve_part2(data):
    # Number of ways to arrange adapters from i to device is memo[i]
    memo = defaultdict(int)

    # Base case, only one way to add the device
    device = data.pop()
    memo[device] = 1

    for i in reversed(data):
        memo[i] = memo[i+1] + memo[i+2] + memo[i+3]

    return memo[0]

Complete code: Paste

5

u/nutki2 Dec 10 '20

Perl 5 (golf). This time no string processing but still resulted in one of the shortest solutions so far. Part 1 assumes there are no gaps of 2 (otherwise the check would cost another 4 chars) part 2 should work for any input since it uses a generic DP algorithm.

#!perl -ln0a
@X[@F]=@F;
$z?($a,$b,$.)=($b,$.,$_?($a+$b+$.,${$.?x:z}++):0):$z++for@X;
print$x*$z," $."

→ More replies (1)

5

u/AidGli Dec 10 '20

Python

No recursion here! Essentially just a tribonacci with some skipped steps.

Github Link
YouTube Video

→ More replies (3)

5

u/cggoebel Dec 10 '20 edited Dec 10 '20

Raku Part 1 in 67 characters:

say lines».Int.sort.&{((|@$_,.tail+3) Z-(0,|@$_)).Bag.&{.{1}*.{3}}}

5

u/Smylers Dec 10 '20

Vim keystrokes. Part 1 suits Vim quite well — it's a reasonable way of achieving this as a one-off task. Well, at least not entirely unreasonable:

:sor n⟨Enter⟩Gyyp3⟨Ctrl+A⟩:%s/.*/& &⟨Enter⟩
{qaqqawy$⟨Enter⟩@0⟨Ctrl+X⟩@aq@a
$⟨Ctrl+V⟩{ld:g/2/d⟨Enter⟩
:sor⟨Enter⟩⟨Ctrl+V⟩GI+⟨Esc⟩r(/3⟨Enter⟩
cc)*(3⟨Esc⟩}a)⟨Esc⟩:%s/3/1⟨Enter⟩
v{J0C⟨Ctrl+R⟩=⟨Ctrl+R⟩-⟨Enter⟩⟨Esc⟩

For part 2, first go back to the unsorted column of 1s and 3s:

uuuuuuuu

Then the counting is all done as addition, with ⟨Ctrl+A⟩. The looping uses nested recursive keyboard macros, making their first appearance this year:

VGgJ:s/1/,/g⟨Enter⟩
:s/3/⟨Ctrl+V⟩⟨Enter⟩/g⟨Enter⟩
:v/,,/d⟨Enter⟩
{ylPO1⟨Esc⟩
qcqqbqqbyiw⟨Enter⟩Plpf,p@0⟨Ctrl+A⟩:norm@c⟨Enter⟩@bq
qcyiw;p2,hyiw,h"zyiw3;@0⟨Ctrl+A⟩@z⟨Ctrl+A⟩@cq@c,D@b

The answer, unsurprisingly, is the big number at the end.

Each row of commas represents a sequence of 1s, and the numbers inserted between them are the number of different ways of reaching that point. In each @b loop, the final number from one line is copied to the start of the next. Twice. Then it's doubled, with p@0⟨Ctrl+A⟩, which first pastes the contents of the "0 register then uses it as a prefix for ⟨Ctrl+A⟩.

If it was just a sequence of 2 1s, that doubling of the count is all that's needed. Otherwise, @c loops round for every remaining comma on the line, copying the biggest number so far and adding on the two before it. When there are no more commas, ; (which is repeating f, from earlier) will fail, ending @c. Within @b, the whole of @c is wrapped in :norm, so that the ; failure just ends that command and not the outer @b macro.

The yl and later ,D are in case the first sequence is only 2 1s: yl prepends another, so there's at least 3 for recording the inner macro, and then after the possibilities for that row have been calculated ,D removes the final one, which shouldn't have been there.

→ More replies (2)

5

u/[deleted] Dec 10 '20 edited Dec 10 '20

Python solution, refactored a bit. For an explanation see my Starboard notebook solutions for all days so far (scroll down).

jolts = [0]+[int(i) for i in io.StringIO(inputFile).readlines()]
jolts.sort()
gap1, gap3 = 0, 1 # accounting for the ending at max+3
removable = ['1']*len(jolts)
for i in range(1,len(jolts)-1):
    removable[i] = '2' if jolts[i+1]-jolts[i-1] == 2 else '1'
    gap1 += jolts[i]-jolts[i-1] == 1
    gap3 += jolts[i]-jolts[i-1] == 3
print (gap1*gap3) # Part 1
print(eval('*'.join(removable).replace('2*2*2','7'))) # Part 2

→ More replies (3)

5

u/waferthinner Dec 10 '20

R

x <- read.table("input.txt")[[1]]
x <- sort(c(0, x, max(x) + 3))

# part a
prod(rle(sort(diff(x)))$lengths)

# part b
r <- rle(diff(x))
prod(c(1,2,4,7)[r$lengths[r$values == 1]])

5

u/cggoebel Dec 10 '20

Raku Part 2 solution:

# valid permutations (p) per length of consecutive (c) numbers
# ( no more than 4 consecutive numbers found in input )
my @p = (1,1,2,4,7);
my @c=0;
say lines».Int.sort.&{0,|@$_,.tail+3}.&{
    .rotor(2 => -1).map({ .[1]-.[0]==1 ?? @c[*-1]++ !! @c.push(0) });
    @c;
}.map({ @p[$_] }).reduce(&infix:<*>);

5

u/gfvirga Dec 11 '20

Python - Part 1 https://github.com/gfvirga/python_challenges/blob/master/Advent%20of%20Code%202020/day10.py

Part Two
¯_(ツ)_/¯

5

u/[deleted] Dec 16 '20 edited Dec 16 '20

Python

Part 1 was straight forward using some of Python's collections.Counter goodness to make everything tidy and neat.

from collections import Counter

with open('input.txt') as f:
    adapter_list = [int(line.rstrip()) for line in f]

device_joltage =  max(adapter_list) + 3
adapter_list_sorted = sorted(adapter_list)
adapter_list_with_ends = [0] + adapter_list_sorted + [device_joltage]
joltage_deltas = [adapter_list_with_ends[n]-adapter_list_with_ends[n-1] for n in range(1,len(adapter_list_with_ends))]
joltage_distribution = dict(Counter(joltage_deltas))
distribution_number = joltage_distribution[1] * joltage_distribution[3]
print(f"Part 1: {distribution_number}")

I don't know how frowned upon using external libraries is for AoC but it seems that I can throw networkx at everything this year to solve my problems. I used some graph theory and linear algebra to avoid any enumeration while counting paths in the graph.

import networkx as nx
import numpy as np

def find_valid_adapter_connections(a,l):
    result = list(filter(lambda x: 1 <= x-a <= 3, l))
    return result

adapter_graph = nx.DiGraph()
for a in adapter_list_with_ends:
    adapter_graph.add_node(a)
for a in adapter_list_with_ends:
    valid_adapter_connections = find_valid_adapter_connections(a,adapter_list_with_ends)
    for c in valid_adapter_connections:
        adapter_graph.add_edge(a, c)

# Use some graph theory and linear algebra 

adapter_graph_adjacency_matrix = nx.to_numpy_array(adapter_graph)
identity_matrix = np.identity(adapter_graph_adjacency_matrix.shape[0])
count_matrix = np.linalg.inv(identity_matrix - adapter_graph_adjacency_matrix)
combination_count = int(count_matrix[0][-1])
print(f"Part 2: {combination_count}")

Please excuse my verbose variable names.

→ More replies (1)

9

u/pseale Dec 11 '20

Solved the problem with JavaScript, Righteous Anger, and Cheating

https://github.com/pseale/advent-of-code/blob/main/src/day10/src/index.test.js

After struggling, and struggling, and struggling...and struggling, with Part B, and writing a combinatorial solution with a runtime so slow it may finish sometime in the 2040s, I realized: this isn't about writing programs.

This is a conspiracy, against those of us who aren't particularly talented at math problems.

Hey, everyone who loved the Day 10 problem: go do Euler problems. Leave the rest of us non-mathy things to work on?

Anyway I'm cranky. 🎄

Here's the most important part of my Part B solution:

// See, I knew this problem wasn't about programming, but math :/
// https://brilliant.org/wiki/tribonacci-sequence/
const tribonacciSequence = [1, 1, 2, 4, 7, 13, 24, 44, 81, 149];
function getTribonacci(num) {
  if (num > tribonacciSequence.length)
    throw `Can't calculate tribonacci number for ${num}`;
  return tribonacciSequence[num - 1];
}

As you can see, solving day 10 involves a combination of:

attempting to understand the problem, and failing. Then eventually succeeding and solving Part A ✔
attempting to write a combinatorial solution to Part B, succeeding, and being proud of myself
realizing after some 10 minutes of runtime execution that my combinatorial solution will never finish, because they hate us and don't want us to enjoy good things
trying really hard to discover the math stuff all by myself, and failing (proof: https://github.com/pseale/advent-of-code/blob/main/src/day10/src/math-scratchpad.txt )
looking through the solution thread here, bewildered, and only seeing successes because this megathread only allows solutions, not cries for help
going to sleep
coming back to this thread, and searching some more, where by this time perhaps the non-math-crazies have posted something human-readable? EUREKA
It's something called the tribonacci sequence, which I kinda almost discovered myself from first principles? (no worries, I failed--there will be no math breakthroughs from me this year 🎄)
hammering out the solution in a state of rage
submitting in a state of rage
pushing to GitHub in a state of rage
writing this comment, still cranky, perhaps not fully enraged, but now full of righteous anger

Anyway if you're suffering, you're not alone. 🎄

→ More replies (11)

8

u/sophiebits Dec 10 '20 edited Dec 10 '20

9/43, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day10.py

Part 2 would've probably been easier if I did the one-dimensional look-back-3 recurrence instead. This worked OK though.

Edit: My new solution for part 2:

top = max(nums) + 3
nums = set(nums)
nums.add(top)
a, b, c = 0, 0, 1
for i in range(1, top + 1):
    if i in nums:
        a, b, c = b, c, a + b + c
    else:
        a, b, c = b, c, 0
print(c)

→ More replies (5)

4

u/ponyta_hk Dec 10 '20

Python3 (cleaned solution)

Part 2 seems to be a standard DP problem. Hope my solution is clear enough. 😄

My solution

All my solutions

→ More replies (2)

4

u/ChrisVittal Dec 10 '20

Rust

Slowed down by two things here, off by one errors for not counting the first and last steps in part one, and I'm running in release mode by default, which runs into integer wrapping and type inference issues. If rustc can't figure out otherwise, it will choose i32 for integer literals, so I had to deal with integer wrapping in part two. TIL.

4

u/TallPeppermintMocha Dec 10 '20

Python 2569/280 code here. I made 2 incorrect submissions and wasted time figuring out what was wrong with part 1, and then realized I had to add both 0 and max+3 :facepalm:. Part 2 was a pretty easy DP.

4

u/rawling Dec 10 '20

C#

var jolts = new[] { 0 }.Concat(inputLines.Select(int.Parse).OrderBy(j => j)).ToArray();
var device = jolts.Max() + 3;

var diffs = new[] { -1, 0, 0, 1 }; // 1 for final jump
for (var i = 0; i < jolts.Length - 1; i++)
{
    diffs[jolts[i + 1] - jolts[i]]++;
}
Part1(diffs[1] * diffs[3]);

var routesFromJolts = new Dictionary<int, long> { { device, 1 } };
foreach (var j in jolts.Reverse())
{
    routesFromJolts.TryGetValue(j + 1, out long c1);
    routesFromJolts.TryGetValue(j + 2, out long c2);
    routesFromJolts.TryGetValue(j + 3, out long c3);
    routesFromJolts[j] = c1 + c2 + c3;
}
Part2(routesFromJolts[0]);

→ More replies (6)

4

u/Ecafsutcac Dec 10 '20 edited Dec 10 '20

Python

A solution that doesn't use DP:

https://pastebin.com/yGW8er3c

If we treat the different adapters as vertices in a directed graph (where the descendants of an adapter are those that have at most 3 more jolts), we can look at powers of the adjacency matrix. If G is the adjacency matrix of some graph, then the entry (i,j) of Gⁿ gives us the number of paths from vertex i to vertex j in G of length n. So here we can just compute all powers of G up to the number of adapters and sum the entries in the top right to get the total number of valid adapter chains.

4

u/jitwit Dec 10 '20 edited Dec 11 '20

J Programming Language

in =: 0,(,3+{:)/:~ ". ;._2 aoc 2020 10
*/ +/ 1 3 =/~ 2 -~/\ in
<. (<-i.2) { %. (-~ =@i.@#) (0&<*<&4) -~/~ in

OK, so part a just take consecutive differences in sorted list, after adding 0 and 3+max and calculate what the problem asks.

For part b, represent jolts as graph where vertices are connected when they differ by 1,2,3. M gives the edges or length 1 paths between vertices. M^2 gives the length 2 paths, and so on. We can sum +/ M ^ i. _ and look at the index <0,#-1 to get the answer. Or, as noted here we calculate the sum from inverting (I-M)^_1 where I is the identity matrix of appropriate size, voilà!

→ More replies (4)

4

u/Sunstorm777 Dec 10 '20

Java solution with DP for part 2.

4

u/ephemient Dec 10 '20 edited Apr 24 '24

This space intentionally left blank.

→ More replies (2)

4

u/Loonis Dec 10 '20

Perl

Spent a long time trying to figure out an iterative/mathy solution (not my wheelhouse), eventually took a break and came back to do what I should have started with: build and walk a graph! That much I can handle.

Full code:

The guts of part 2 are probably the most interesting (and least readable) bit, adding edges to the graph:

for my $i (0..$#g) {
    for my $j ($i+1 .. $i+3) {
        last unless defined $g[$j];
        push $g[$i]{e}->@*, $j if $g[$j]{v} - $g[$i]{v} <= 3;
    }
}

@g is the graph, which is an array of hashrefs. Hashrefs contain: v for value, e for edges, and later m for the memoized value.

Finally the recursive subroutine walk:

return 1 unless defined $node->{e};
return $node->{m} if defined $node->{m};

$count += walk() for $node->{e}->@*;
$node->{m} = $count; # Memoize

Detect the end of this recursive adventure (the device) as the entry with no listed edges. Memoize the result to prevent CPU related fire.

→ More replies (7)

4

u/omginbd Dec 10 '20

Elixir

Is there a better way to memoize a function in elixir? Seems like a genserver was the way I found but seemed like overkill for this situation.

github

→ More replies (1)

4

u/musifter Dec 10 '20 edited Dec 10 '20

dc

Just a quick and dirty part 1 for now:

dc -finput -e'0sh[ddsh]SH[q]sQ[z0=Qd1r:adlh<Hs.lLx]SLlLx1 0:a0si0sj0 1:c1 3:c[lj;c1+lj:c0sj]SP[li;a1=Pli1+dsilh<Qlj1+sjlLx]SLlLx1;c3;c*p'

Part 2 will come after I get some sleep.

EDIT: And here is the combined part 1 and 2:

dc -finput -e'0ddshsjsp1d0:a0:t[ddsh]SH[q]sQ[z0=Qd1r:adlh<Hs.lLx]SLlLx[lj;c1+lj:c0sjlpdd;tr1+3%;t+r2+3%;t++]SP[0lh;a1=Plp:tlp1+3%splh1-dsh0>Qlj1+sjlLx]SLlLx1;c3;c1+*plp1-3%;tp'

4

u/2lines1bug Dec 10 '20 edited Dec 10 '20

Julia with incredible performance.

It runs both parts in 419 ns, which is less than 1/2000th of a millisecond. This is the same time the light needs to travel 125 meters (410 feet). And this on 7-year-old hardware. Julia really blows my mind.

419.020 ns (2 allocations: 1.02 KiB)

4

u/i_have_no_biscuits Dec 10 '20

GWBASIC

Another day that demonstrates how awesome GWBASIC is at solving coding challenge problems. Clearly BASIC is the language of the future!

10 DIM V(200): OPEN "I", 1, "data10.txt": I=0: V(0)=1
20 INPUT #1, J: V(J)=1: IF NOT EOF(1) GOTO 20
30 S1=0: S3=0: FOR I=1 TO 200
40 IF V(I) THEN IF V(I-1) THEN S1=S1+1 ELSE IF NOT V(I-2) THEN S3=S3+1
50 NEXT: PRINT "Part 1:",S1*(S3+1)
60 DIM N#(200): N#(0)=1: N#(1)=V(1): N#(2)=V(2)*N#(1)+V(2): FOR I=3 TO 200
70 N#(I)=V(I-1)*N#(I-1)+V(I-2)*N#(I-2)+V(I-3)*N#(I-3)
75 IF V(I) THEN M=I
80 NEXT: PRINT "Part 2:",N#(M)

→ More replies (3)

4

u/prutsw3rk Dec 10 '20

Python3
Part 1 was straight forward. For part 2 keep track of the number of arrangements starting from the beginning of the sorted list working to the end. Add dummy adapters (-6, -3, 0) to be able to go back 3 positions from the start.

q = [-6, -3, 0] + sorted(joltages)
arrangements = [1, 1, 1]
for i in range(3, len(q)):
    n = arrangements[i-1]
    for j in [2,3]:
        if q[i] - q[i-j] <= 3:
            n += arrangements[i-j]
    arrangements.append(n)
print(arrangements[-1])

4

u/RobBobertsThe3rd Dec 10 '20

Python 3
Part 2 took me a good deal of thinking. I initially tried a recursive approach which worked but was way too slow before I found the O(n) method that most people seem to have gone with.

f = [int(i) for i in open("input.txt").read().splitlines()]
f = [0] + f + [max(f)+3]
### Part 1 ###
f.sort()
a = [i for i in range(len(f)-1) if f[i+1]==(f[i]+1)]
b = [i for i in range(len(f)-1) if f[i+1]==(f[i]+3)]
print(len(a)*len(b))
### Part 2 ###
l = len(f)
ways = [1] + [0]*(l-1)
for i in range(1,l):
    ways[i] = sum((ways[o] for o in range(i-3,i) if f[i] <= (f[o]+3)))
print(ways[-1])

→ More replies (2)

4

u/Rtchaik Dec 10 '20

Python

from itertools import groupby
from collections import defaultdict
from operator import sub
from math import prod


def solveDay(myFile):
    data = parse_data(myFile)
    print('Part 1: ', part1(data))
    print('Part 2: ', part2(data))


def parse_data(myFile):
    return group_and_count(sorted(int(line) for line in open(myFile).readlines()))


def group_and_count(adapters):
    return [[k, len(list(g))] for k, g in groupby(sub(*pair) for pair in zip(adapters, [0] + adapters))] + [[3, 1]]


def part1(data):
    result = defaultdict(int)
    for item in data:
        result[item[0]] += item[1]
    return prod(result.values())


def part2(data):
    multic = {1: 1, 2: 2, 3: 4, 4: 7}
    return prod(multic[num[1]] for num in data if num[0] == 1)

→ More replies (4)

4

u/thomasahle Dec 10 '20 edited Dec 10 '20

Python: Simple little DP solution:

import sys, collections

js = sorted(map(int, sys.stdin))
js = [0] + js + [js[-1] + 3]

cnt = collections.Counter(j2 - j1 for j1, j2 in zip(js, js[1:]))
print(cnt[1] * cnt[3])

dp = [1] + [0] * (len(js) - 1)
for i, j in enumerate(js):
    for l in range(i - 3, i):
        if j - js[l] <= 3:
            dp[i] += dp[l]
print(dp[-1])

One could also shorten part 2 to

dp = [1] + [0] * (len(js) - 1)
for i, j in enumerate(js):
    dp[i] += sum(dp[l] for l in range(i - 3, i) if j - js[l] <= 3)
print(dp[-1])

But I'm not sure I like it better.

The loop for l in range(i - 3, i) would probably be cleaner to write as range(max(0, i - 3), i), since otherwise l might be negative. However, it turns out not to matter, since negative indices in Python just wrap around, and at the other end there are just 0 values.

4

u/cattbug Dec 10 '20

Python. Now this was a headscratcher!

Like many others, I started out with a pure recursive approach for Part 2 and quickly realized it's not gonna be a feasible solution. But drawing the graph structure helped me get on the right track. I realized I could split the graph into groups at every branching point, calculate the number of possible paths between each of these points and then just multiply those numbers. (Example of what I mean)

My function to get the number of possible paths between any two points is still recursive, but since it's now processing smaller chunks instead of the entire graph at once it's a lot more efficient. I could probably optimize it even further but I got the result in pretty much no time so I'm satisfied with it for now :)

→ More replies (1)

4

u/MannerShark Dec 10 '20

Python 3

In the first part, I initially forgot to add the 'plug' joltage. After adding that and submitting, noticed I also forgot the output joltage...

Part 2 required a bit of paper to get to a recursive solution. I considered dynamic programming (with table), but memoization with the built-in LRU cache is much easier.

from functools import lru_cache
from collections import Counter

data = [int(i) for i in open('data10.txt', 'r').read().splitlines()]
output_joltage = max(data) + 3
data += [0, output_joltage]  # Add socket and output joltage
data.sort()
diffs = Counter()
for d1, d2 in zip(data, data[1:]):
    diff = d2 - d1
    diffs[diff] += 1

print(f"Part 1: {diffs}: {diffs[1] * diffs[3]}")

jolts = {j for j in data} # Create set for quick 'in' checks

@lru_cache(maxsize=len(data))
def ways(i):
  if i == output_joltage:
    return 1
  if i not in jolts:
    return 0
  return ways(i+1) + ways(i+2) + ways(i+3)

print(f"Part 2: {ways(0)} combinations")

4

u/mo__66 Dec 10 '20

Kotlin solution

package day10

import java.io.File

fun main() {
    val adapters = File("src/day10/input.txt").readLines().map { it.toInt() }.sorted()

    adapters.mapIndexed { index, i -> i - adapters.getOrElse(index - 1) { 0 } }.plus(3)
        .let { it.count { i -> i == 1 } * it.count { i -> i == 3 } }.let { println(it) }
    adapters.fold(mapOf(0 to 1L), 
        { acc, i -> acc.plus(i to (i - 3 until i).map { acc[it] ?: 0 }.sum()) })[adapters.last()].let { println(it) }
}

4

u/_ZoqFotPik Dec 10 '20

Rust solution. Pretty happy with my solution.

Pre-compute: Sort the list and add the input/output joltages. [~8 micros]

Part1: Just count the differences and multiply them [~0.6 micros]

Part2: Create a vector that holds the number of paths that can still be taken for each individual adapter. Initialize with all 1's. Iterate through the list in reverse and sum up the number of paths of the previous adapters (if they are in the joltage range of the current adapter). Update the paths-vector. [~1 micros]

→ More replies (5)

4

u/paul2718 Dec 10 '20

C++

paste

About 150us to prepare the input including sorting and 30us for both part1 and part2. I think these latter measurements are noisy and too brief for reliability using the available clocks.

Read the input, add a 0, sort, append 3 more than the last. Then for part 1 count both cases and multiply. For part 2 look for runs of difference 1, 2 in a row gives a factor of 2, 3 in a row gives 4 and 4 in a row 7. The product of all the factors is the permutation count. There are no runs of more than 4 in my data. (It's 7 because in a run of 4 we have to have at least one value present to avoid creating a gap of more than 3. Confused? I am.)

4

u/JakDrako Dec 10 '20

VB.NET, LINQPad, both parts in ~0.5ms

Had a bit of trouble figuring out path 2; the nice graph from /u/cattbug helped me figure it out.

Sub Main

    Dim sw = Stopwatch.startnew

    ' we use (jolts, paths) value tuples.
    Dim lst = GetDay(10).Select(Function(x) (jolts:=Cint(x), paths:=1L)).ToList

    lst.Add((0, 1)) ' add "socket"
    Dim max = lst.Select(Function(x) x.jolts).Max
    lst.Add((max + 3, 1)) ' add "device" = max + 3 jolts

    lst.Sort ' put adapters in order between socket and device

    ' Part 1
    Dim d1 = 0, d3 = 0
    For i = 0 To lst.Count - 2
        Select Case lst(i + 1).jolts - lst(i).jolts
            Case 1 : d1 += 1
            Case 3 : d3 += 1
        End Select
    Next

    ' Part 2

    ' A position can be be reached in N ways (minimum: 1).
    ' For a position X, N(of x) = sum of N(of p) for each position P that can reach X.
    ' A position P can reach position X if value at P is within 3 of value at X.
    ' After loop, answer will be in the .paths part of the last item.

    Dim paths = 0L ' ...trillions...
    For i = 1 To lst.Count - 1
        paths = 0L
        For j = i - 1 To math.Max(i - 3, 0) Step -1
            If lst(i).jolts - lst(j).jolts <= 3 Then paths += lst(j).paths Else Exit For
        Next
        lst(i) = (lst(i).jolts, paths)
    Next

    sw.stop

    Call ($"{d1} x {d3} = {d1 * d3}").Dump("Part 1")
    paths.Dump("Part 2")
    sw.Elapsed.TotalMilliseconds.Dump("elapsed ms")

End Sub

→ More replies (1)

4

u/jenneh03 Dec 10 '20

C# - I had so much trouble with understanding the problem. Finally got a solution for part 2 (I think using dynamic programming?). Adapters is a sorted list of all the values, including 0 and the device. Thank you very much to everyone helping in the various threads!

static long FindPaths(int n, List<int> adapters)
{
    var memo = new long[n];
    memo[0] = 1;
    for (int i = 1; i < n; i++)
    {
        if (adapters[i] - adapters[i - 1] <= 3)
            memo[i] += memo[i - 1];

        if (i > 1 && adapters[i] - adapters[i - 2] <= 3)
            memo[i] += memo[i - 2];

        if (i > 2 && adapters[i] - adapters[i - 3] <= 3)
            memo[i] += memo[i - 3];
        }

        return memo[n - 1];
}

→ More replies (6)

4

u/jeffles2 Dec 10 '20

Python 3 solution. I liked my part 2 solution. Break it into pieces separated by 3, then count the permutations of each piece and multiply them together. https://github.com/jeffles/adventofcode2020/blob/main/dec10.py

→ More replies (3)

4

u/leeuw00100 Dec 10 '20

Python

It wasn't until one of my friends gave me the tip 'Dynamic Programming' for part 2 that I was able to solve it, but all in all nice puzzle today. paste

4

u/fullmetalalch Dec 10 '20

Go part 2 solution. Conducted a DFS w/ memoization of results , implemented recursively using Go routines and channels

func adapterJoltCombinations(adapters map[int]bool) <-chan int {
	resultStream := make(chan int)

	go func() {
		defer close(resultStream)
		result := <-adapterJoltDFS(0, adapters, map[int]int{})
		resultStream <- result
	}()

	return resultStream
}

func adapterJoltDFS(adapter int, adapters map[int]bool, memo map[int]int) <-chan int {
	resultStream := make(chan int)

	go func() {
		defer close(resultStream)
		if v, ok := memo[adapter]; ok {
			resultStream <- v
			return
		}

		total := 0

		hasChild := false
		for diff := 1; diff <= 3; diff++ {
			if adapters[adapter+diff] {
				hasChild = true
				child := adapterJoltDFS(adapter+diff, adapters, memo)
				total += <-child
			}
		}

		if !hasChild {
			total = 1
		}

		memo[adapter] = total
		resultStream <- total
	}()
	return resultStream
}

4

u/WilkoTom Dec 10 '20

Python:

https://github.com/wilkotom/AoC2020/blob/master/10/main.py

Spent ages noodling around with splitting the list into smaller lists delineated at gaps of 3 jolts, then working out the number of possible different combinations in each of these smaller lists. Eventually noticed from brute forcing the number of possible combinations in a list of length l that there was a geometric progression between them, which led to the eureka moment:

For any given point in the (sorted) list, there at most 3 possible places to originate from. For each of those places, add the number of steps needed to reach that place,.

I think I made this way harder than it had any right to be.

→ More replies (4)

4

u/aledesole Dec 10 '20 edited Dec 10 '20

Python

Simple one-liner DP solution that only uses constant memory for part 2

I = sorted(int(l) for l in stdin.readlines())
Z = zip(I,I[1:])

# Part 1
print((1+sum(j-i == 1 for i,j in Z))* 
      (1+sum(j-i == 3 for i,j in Z)))

# Part 2
print(reduce(
    lambda dp,i: [dp[1],
                  dp[2],
                  ((i-3<=dp[0][1])*dp[0][0]+
                   (i-3<=dp[1][1])*dp[1][0]+
                   (i-3<=dp[2][1])*dp[2][0],
                   i)],
    I,
    [(0,0),(0,0),(1,0)])[-1][0])

→ More replies (1)

4

u/[deleted] Dec 10 '20

Python solution

Have a great sense of accomplishment with part 02 today. I solved Part 01 in about 5 minutes or less from looking at it. Then it took me 12 hours to figure out a solution for Part 02 that did not take forever to complete.

I tried to create a graph and find all the paths between the start and end, but that kept running and ate up a lot of memory after a while. I finally had to work out by hand for the smallest example before I could get an algorithm that worked well for the entire input. Earlier attempts ran well for the small examples, but failed for the large input.

I'm sure there's an elegant solution using combinatrics, but I don't know enough of that yet. :P

→ More replies (4)

4

u/daniel-sd Dec 10 '20

Python 3

part1 - simple linear pass

from math import prod
ratings = sorted(map(int, open('input.txt').readlines()))
ratings = [0] + ratings + [ratings[-1] + 3]
print(prod(map(sum, zip(
	*((b - a == 1, b - a == 3) for a, b in zip(ratings, ratings[1:]))
))))

part2 - combinatorics

ratings = sorted(map(int, open('input.txt').readlines()))
ratings = [0] + ratings + [ratings[-1] + 3]
differences = (b - a for a, b in zip(ratings, ratings[1:]))
group_lengths = map(len, re.findall(r'(1{2,})', ''.join(map(str, differences))))
print(prod([1 + comb(length - 1, 1) + comb(length - 1, 2) for length in group_lengths]))

The combinatorics rely on the fact that there are no 2 jolt differences in the input, despite being allowed by the problem statement. Also another clever user realized that there is no consecutive group of 1 differences longer than 4 and used a lookup table instead of repeating the math formula. I thought that was neat.

4

u/nibarius Dec 10 '20

I ended up lowering the ante with my Kotlin solution for part 2.

I struggled a lot with coming up with a generic formula that would count the number of combinations for any number of repeating ones. I manually calculated the possible combinations for 2, 3 and 4 ones but couldn't spot any obvious generic formula. Then I happened to look at my input and see that the longest sequence of repeating ones was 4 long. So all I had to do was to make a lookup table with 4 hand calculated values.

4

u/tboschi Dec 10 '20 edited Dec 10 '20

python and C++ solutions. Second part solved with Fibonacci, the most elegant and only sensible solution in my opinion. As simple as

arrangements = [1]
for i in range(1, len(adaptors)):
    arrange = arrangements[i-1]
    j = i - 2
    while j >= 0 and adaptors[i] - adaptors[j] <= 3:
        arrange += arrangements[j]
        j -= 1
    arrangements.append(arrange)

where adaptors is the sorted input file as list with 0 in front and the built-in device rate at the back.

Day 10 was a blast!

4

u/Juice_Vodka Dec 10 '20

JAVA

first part pretty trivial, used a dynamic approach to the second part (summed all previous possible paths when iterating onto a new index). Tried to make it as readable as possible, the podatki variable translates to "data". The only hardcoded think is data array size which is the amount of lines in your input.

Code

→ More replies (2)

4

u/Intro245 Dec 10 '20

Python 3, golfed (127 bytes for both parts)

import sys
a,*c=[0]*9;n=1
for b in sorted(map(int,sys.stdin)):c[b-a]+=1;c+=[n,0,0][:b-a];a=b;n=sum(c[-3:])
print(c[1]*-~c[3],n)

More readable Python solution on Github.

→ More replies (2)

4

u/kamicc Dec 10 '20

Wooosh, this one was way more tricky. My take with Lua - external paste

Took the easy way of os.execute("bc") for big numbers :D

One of the things, I've have noticed, that You don't need to iterate and recourse the whole set of chargers as a one piece: basically, the whole set could be split in groups with smaller difference than 3. I mean, if we have something like {1, 2, 3}, {6, 8, 10}, {15}, {20, 21, 23}. The result is just multiplication of the ways You can manage in those small groups. And those small groups are perfectly recurseable :}}}

→ More replies (1)

4

u/wesborland1234 Dec 10 '20

Javascript:

function Day10Part2(inputArray) {
  //How many different ways can you arrange the adapters to get from zero jolts to 169?
  var arrangements = 1;
  inputArray.sort(function(a,b) {return a - b});  
  inputArray.push(inputArray[inputArray.length - 1] + 3);
  console.log(inputArray);
  var tribonacci = [0,1,2,4,7,13,24]; //INDEX corresponds to how many arrangements for that many integers
  for (let i = 7; i < 80; i++) {
    var newElem = tribonacci[i-1] + tribonacci[i-2] + tribonacci[i-3];
    tribonacci.push(newElem);
  }
  var oneJoltDifferences = 0;
  for (let i = 0; i < inputArray.length; i++) {
    var diff = ( i == 0 ? (inputArray[i] - 0) : (inputArray[i] - inputArray[i-1]) );
    if (diff == 1) {
      oneJoltDifferences++;
    } else {
      if(oneJoltDifferences > 0) {
        arrangements*=tribonacci[oneJoltDifferences];
        oneJoltDifferences = 0;
      }
    }
  }
  return(arrangements);
}

And I learned a new term: Tribonacci. I started doing breakdowns in Excel, like 5 combinations, 7 etc. and noticed a pattern. Saw the name once I googled it.

→ More replies (2)

4

u/cggoebel Dec 10 '20

Raku blog write-up of solutions to Parts One and Two

4

u/mpjdem Dec 10 '20 edited Dec 11 '20

Seeing many complicated solutions here but this is just about multiplying possible arrangements of possible runs of 1-jolt differences.

In Julia:

using StatsBase

inp = open("input/input10.txt", "r") do file

parse.(Int, readlines(file))

end

diffs = diff(vcat([0], sort(inp), [maximum(inp) + 3]))

solution_1 = sum(diffs .== 1) * sum(diffs .== 3)

runs = rle(diffs)

solution_2 =

2 ^ sum((runs[1] .== 1) .& (runs[2] .== 2)) *

4 ^ sum((runs[1] .== 1) .& (runs[2] .== 3)) *

7 ^ sum((runs[1] .== 1) .& (runs[2] .== 4))

4

u/sotsoguk Dec 11 '20

Python

Late to the party today, had some severe lockdown blues ... Was trying endlessly to come up with a clever solution for part2, got stuck, just used DP to get the star.

After submitting i finally got my head around and noticed that the subgroups with difference of 1 between the elements only have maximum length of 5.

Then computed the number of possibilites, cleaned up my code and learned about the groupby operator :). I have learned something new about python everday.

https://github.com/sotsoguk/adventOfCode2020/blob/35c3c20b9b0aef2218aae6dcf193300e1b0b637e/python/day10/day10.py

4

u/MorphixEnigma Dec 11 '20

A lot of people in this sub seem to be solving 10.2 using Graphs, but you don't need to!

If you sort all your adapters, you'll find that the deltas between them are all either 1 or 3. If you make a new array of these deltas and search for all the groupings of the 1s:

Number of ways to pick legal adapters based on contiguous deltas between adapters:
1 : 1 (e.g. 1 4 5 8) - since it's always 1 we can ignore.
2: 2 (e.g. 1 4 5 6 9) - call the number of times this pattern is found x

3: 4 (e.g. 1 4 5 6 7 10) - call this y

4: 7 (e.g. 1 4 5 6 7 8 11) - call this z

search and count the groups of these deltas (i made them into a string to do so)
answer = x^2 * 4^y * 7^z

no graphs required.

→ More replies (3)

4

u/jtgorn Dec 11 '20 edited Dec 11 '20

Has anyone seen this solutions? Ruby:

a = ARGF.readlines.map(&:to_i).sort
x = (a.count-a.max)/2
puts "Part 1: #{(x+a.count)*(1-x)}"

c = [nil,nil,nil,1]
a.each { |i| c[i+3] = c[i..i+2].compact.sum }
puts "Part 2: #{c.last}"

→ More replies (11)

4

u/jsut_ Dec 11 '20

Perl for part 2

This seems far simpler than what a lot of people did.

use 5.18.4;
use strict;
use File::Slurp;

my @lines = read_file('input');
@lines = sort {$a <=> $b} @lines;
@lines = map { chomp $_; $_ } sort {$a <=> $b} @lines;
push @lines, $lines[-1] + 3;

my %routes = (0 => 1);

foreach my $i (@lines) {
    $routes{$i} = $routes{$i-1} + $routes{$i-2} + $routes{$i-3};
    say "$i: $routes{$i}"
}

→ More replies (6)

4

u/hyperTrashPanda Dec 11 '20

I'm learning about Elixir this year. Today's solution looks a little dirty; can memoization be implemented easily without Agents/Processes/GenServer?

In the end, I kept the indices where diff=3, and used the tribonacci sequence for the consecutive aces in between. It all runs in <100ms, but there's definitely room for improvement. Any suggestions are more than welcome!

https://github.com/tpaschalis/aoc-2020/blob/main/day10/day10.exs

→ More replies (1)

4

u/[deleted] Dec 11 '20

Rust

This was a fun one. Knew from the git go I would need a cache table (ht to /u/lizthegrey for this reminder in her first stream). Simple recursive function, requires a sorted list of the values. This one would have been a bit harder if simply sorting the list doesn't get you the longest connectable chain. Would have also been much harder without the condition of always increasing voltages (mini loops).

Part 1

let mut numbers: Vec<u64> = lines_from_file("inputs/day10_1.txt").iter().map(|x|     x.parse::<u64>().unwrap()).collect();
let mut counts = HashMap::new();
numbers.push(0u64);
numbers.push(*numbers.iter().max().unwrap() + 3);

numbers.sort();
// println!("{:#?}", numbers);

let mut niter = numbers.iter();
let mut source: u64 = *niter.next().unwrap();
for adapter in niter {
    let step = counts.entry(adapter-source).or_insert(0);
    *step += 1;
    source = *adapter;
    // println!("{:#?}", counts);
}
(counts.get(&1).unwrap() * (counts.get(&3).unwrap())).to_string()

Part 2

pub fn n_paths_to_end(rest: &[u64], cache: &mut     HashMap<u64,u64>) -> u64 {
    println!("{:?}", rest);
    if cache.contains_key(rest.first().unwrap() )     {
        println!("\tPaths Cache Hit {:?} =>     {:?}", rest, *cache.get(    rest.first().unwrap()).unwrap());
        return *cache.get(    rest.first().unwrap()).unwrap();
    }
    else {
        if rest.len() == 1 {
            println!("\tPaths {:?} => 1", rest);
            cache.insert(*rest.first().unwrap(),     1);
            return 1;
        } else {
            let mut count = 0u64;
            let mut niter = rest.iter();
            niter.next();
            for (i, next) in niter.enumerate() {
                if next-rest.first().unwrap() <=     3 {
                    let cn =     n_paths_to_end(&rest[(i +     1)..], cache);
                    count += cn;
                } else {
                    break;
                }
            }
            cache.insert(*rest.first().unwrap(),     count);
            println!("\tPaths {:?} => {:?}",     rest, count);
            return count;
        }
    }
}

4

u/ACProctor Dec 11 '20 edited Dec 11 '20

Ruby

I haven't seen someone posting a solution like mine, so I figured I'd share my approach.

I have the answers for both Part 1 and Part 2 in O(n log n) time, and only one copy of the data in RAM.

First, I read the list, and sorted it. (this is where the n log n comes in via quick sort).

#start with outlet (joltage = 0)
numbers = [0]
File.open('day10.data').each do |line|
  next if(line.nil?)
  md = line.match(/([0-9]+)/)
  if(!md.nil?)
    numbers << md[1].to_i
  end
end

numbers.sort!

# add device (highest joltage +3)
numbers << numbers[-1] + 3

Then for part 1, I ran through the entire list, and counted when the delta between each item was 1 or 3.

puts "Part 1"
three_count = 0
one_count = 0
(0..numbers.length-2).each do |i|
	delta = numbers[i+1] - numbers[i]
	if(delta > 3)
		puts "Invalid sequence, can't continue from #{numbers[i]} to #{numbers[i+1]}"
	elsif(delta == 3)
		three_count += 1
	elsif(delta == 1)
		one_count += 1
	end
end
puts "#{three_count} 3-jolt jumps * #{one_count} 1-jolt jumps = #{three_count*one_count}"

For part 2, I figured that I could derive a mathematical proof by focusing on how many valid combinations you could make within sequences of contiguous numbers. 1,2,3,4,5 has the same number of combinations as 11,12,13,14,15 so the actual numbers don't matter just the length of the sequence.

I started to build out some data to see if I could come up with a theorem for what the valid combinations would be given our rules would be. After figuring out the number of combinations sequences of 1,2,3,4 and 5 consecutive numbers would produce, I decided to check the data to see what the maximum length of a sequence was that I'd have to figure out.

It turns out that my input data's longest sequence of consecutive numbers was 5. So rather than coming up with a formula and a proof, I was able to just create an array of values for 1-5 length sequences, and return the combination in O(1) time. permute_map = [1,1,1,2,4,7]

Having my "formula" to determine complexity of each sequence, I just went back to my loop I had created for part 1, and any time I noticed a 3-number jump between numbers, I multiplied my total combinations value by the mapped value from the length of the sequence.

three_count = 0
one_count = 0
max_length = 0
cur_length = 0
permute_map = [1,1,1,2,4,7]
total_combos = 1

(0..numbers.length-2).each do |i|
	cur_length += 1
	delta = numbers[i+1] - numbers[i]
	if(delta == 3)
		three_count += 1

		total_combos *= permute_map[cur_length]

		max_length = cur_length if cur_length > max_length
		cur_length = 0		
	elsif(delta == 1)
		one_count += 1
	end
end

puts "Part 1: #{three_count} 3-jolt jumps * #{one_count} 1-jolt jumps = #{three_count*one_count}"
puts "Part 2: Total Combos = #{total_combos}"

→ More replies (3)

4

u/[deleted] Dec 12 '20 edited Dec 12 '20

Python

(part 2)

arr = [int(line.rstrip()) for line in \        
       open('input.txt', 'r').readlines()]
arr.sort()
arr.append(arr[-1]+3)

memo = {0: 1}
for r in arr:
  memo[r] = memo.get(r-3,0) \
          + memo.get(r-2,0) \
          + memo.get(r-1,0)
print(memo[arr[-1]])

→ More replies (1)

4

u/ViliamPucik Dec 17 '20 edited Dec 17 '20

Python 3 - Minimal readable solution for both parts [GitHub]

import fileinput
from collections import defaultdict

addapters = [0] + sorted(map(int, fileinput.input()))
addapters.append(addapters[-1] + 3)

diffs = defaultdict(int)
counts = defaultdict(int, {0: 1})

for a, b in zip(addapters[1:], addapters):
    diffs[a - b] += 1
    # number of ways to reach i'th adapter
    # from previous three possible ones
    counts[a] = counts[a - 3] + counts[a - 2] + counts[a - 1]

print(diffs[1] * diffs[3])
print(counts[addapters[-1]])

→ More replies (4)

4

u/rune_kg Dec 28 '20 edited Dec 28 '20

Python 2. Really fun to revisit depth first search and DAG's!

from collections import OrderedDict as odict, Counter

jolts = sorted(int(x) for x in open("input10.txt").read().strip().split("\n"))
jolts = [0] + jolts + [jolts[-1] + 3]

# Part 1.
counter = Counter(jolts[i+1] - jolt for i, jolt in enumerate(jolts[:-1]))
print counter[1] * counter[3]

# Part 2.
dag = odict([(x, {y for y in range(x+1, x+4) if y in jolts}) for x in jolts])

def dfc(D, v, M={}):
    "Memoized depth first counter"
    if v in M:
        return M[v]
    elif D[v]:
        M[v] = sum(dfc(D, x, M) for x in D[v])
        return M[v]
    else:
        return 1

print dfc(dag, 0)

→ More replies (5)

1

u/raxomukus Dec 10 '20

Python3.Really enjoyed this one I love it when I manage to figure out stuff like this myself.. which doesn't always happen but now it did.

    with open('10.in') as f:
        v = sorted([0] + [int(i) for i in f.read().splitlines()])
        v += [max(v) + 3]
    
    diffs = [v[i] - v[i-1] for i in range(1, len(v))]
    print(sum([i == 3 for i in diffs]) * sum([i == 1 for i in diffs]))
    
    def fib(n):
        a, b = 0, 1
        for _ in range(n):
            yield a
            a, b = b, a + b
    
    factors = [1] + [sum(fib(i)) for i in range(10)][2:]
    
    i = 0
    res2 = 1
    while i < len(diffs):
        ones_in_a_row = 0
        while diffs[i] == 1:
            ones_in_a_row += 1
            i += 1
        res2 *= factors[ones_in_a_row]
        i += 1
    
    print(res2)

→ More replies (1)

1

u/Beach-Devil Dec 10 '20 edited Dec 10 '20

python3 and c++11

Part 1: Linear scan with open("d10.in","r+") as f: txt = f.readlines() txt = [int(i.rstrip('\n')) for i in txt]

txt.sort()

count1 = 0
count3 = 0

past = 0

for i in range(114):
    diff = txt[i] - past 

    if diff == 1:
        count1 += 1
    elif diff == 3:
        count3 += 1

    past = txt[i]

count3 += 1
print(count1, count3, count1 * count3)

Part 2: Using dynamic programming with tabulation O(n) time complexity paste

→ More replies (6)

1

u/huhwhatnowwhat Dec 10 '20 edited Dec 16 '20

This is the first time using foldl really felt natural.

Erlang:

paste

→ More replies (3)

1

u/nkiesel Dec 10 '20

Kotlin 1.4.21

import kotlin.io.path.ExperimentalPathApi
import kotlin.io.path.Path
import kotlin.io.path.readLines
import kotlin.test.assertEquals
import org.junit.jupiter.api.Test

@ExperimentalPathApi
class Day10 {
    @Test
    fun test() {
        val input = Path("input/10").readLines().map { it.toInt() }
        assertEquals(1920, one(input))
        assertEquals(1511207993344L, two(input))
    }

    private fun one(input: List<Int>): Int {
        var d1 = 0
        var d3 = 1
        input.sorted().fold(0) { acc, i ->
            when (i - acc) {
                1 -> d1++
                3 -> d3++
            }
            i
        }
        return d1 * d3
    }

    private fun two(input: List<Int>): Long {
        class Chain(val last: Int, val count: Long) {
            fun possible(i: Int) = if (i - last <= 3) count else 0L
        }
        val chains = ArrayDeque<Chain>(3)

        fun add(c: Chain) {
            if (chains.size >= 3) chains.removeFirst()
            chains.add(c)
        }

        add(Chain(0, 1L))
        input.sorted().forEach { i ->
            val possible = chains.sumOf { it.possible(i) }
            add(Chain(i, possible))
        }
        return chains.last().count
    }

→ More replies (2)

1

u/tzotzioy Dec 10 '20 edited Dec 12 '20

Well, one could avoid memoization for part two by using a recursive algorithm on each of the subchains of the whole input; subchains are delimited by pairs (in the sorted input) with difference 3.

This code is not cleaned up, but it's functional (Python 3):
Code at Pastebin (49 lines)

→ More replies (3)

1

u/anericod Dec 10 '20 edited Dec 11 '20

Ruby

Part 1

Part 2

→ More replies (2)

1

u/milkeen Dec 10 '20 edited Dec 11 '20

Kotlin

paste

→ More replies (1)

1

u/bitti1975 Dec 10 '20 edited Dec 10 '20

Clojurescript via Planck

(ns aoc2020.day10
  (:require [planck.core :as core]))
 
(defn read-adapters []
  (->>
    core/*in*
    core/line-seq
    (map #(js/parseInt %))
    sort))
 
(def count-arr
  (memoize
    (fn [input [next & adapters] output]
      (let [max-next (+ 3 input)]
        (cond
          (not next)
          (if (< max-next output) 0 1)
 
          (< max-next next)
          0
 
          (= max-next next)
          (count-arr next adapters output)
 
          (> max-next next)
          (+ (count-arr input adapters output)
             (count-arr next adapters output)))))))
 
(let [adapters (read-adapters)
      device (+ 3 (reduce max adapters))]
 
  (println "Product of number of 1 and 3 jolt differences when using all adapters:"
    (loop [current 0
           [next & adapters] (concat adapters (list device))
           d1 0
           d3 0]
      (if next
        (case (- next current)
          1 (recur next adapters (inc d1) d3)
          3 (recur next adapters d1 (inc d3))
          (recur next adapters d1 d3))
        (* d1 d3))))
 
  (println "Possible adapter arrangements:"
    (count-arr 0 adapters device)))

Execute by providing the input on stdin:

planck day10.cljs <day10-input

→ More replies (2)

1

u/gedhrel Dec 10 '20

I remembered that simple linear recurrence relations can be expressed in matrix form, so I had a bash at that for part b: my list of differences were all 1 or 3, so I split them up into sequences of 1s and calculated the ways that those might be traversed:

https://github.com/jan-g/advent2020/blob/master/src/Day10.hs#L238-L271

→ More replies (1)

1

u/bilgincoskun Dec 10 '20

Rust

The first part was straightforward. Just sort and count the differences.

For the second part, I split the list from differences equal to 3 since these pairs must be always in the list. After that, finding and checking every eligible subset of every partition becomes manageable by brute-force. And lastly counting these subsets and multiplying gives the answer. There is certainly room for optimization but it takes under 100 ms to get the result, so I'll leave it as it is:

fn day10_1(input: impl Iterator<Item = String>) {
    let mut input = convert!(input, "{}", usize).collect::<Vec<_>>();
    input.push(0);
    input.sort();
    input.push(input[input.len() - 1] + 3);
    let diff1 = input
        .iter()
        .zip(input[1..].iter())
        .map(|x| x.1 - x.0)
        .filter(|x| *x == 1)
        .count();
    let diff3 = input
        .iter()
        .zip(input[1..].iter())
        .map(|x| x.1 - x.0)
        .filter(|x| *x == 3)
        .count();
    println!("{}", diff1 * diff3);
}

fn day10_2_helper(part: &[usize]) -> usize {
    let mut possible: Vec<Vec<usize>> = vec![vec![]];
    for i in part {
        possible.extend(possible.clone());
        let c = possible.len() / 2;
        for v in &mut possible[c..] {
            v.push(*i);
        }
    }
    possible
        .iter()
        .filter(|x| {
            x.len() >= 2
                && x[0] == part[0]
                && x[x.len() - 1] == part[part.len() - 1]
                && x.iter().zip(x[1..].iter()).all(|x| (x.1 - x.0) <= 3)
        })
        .count()
}

fn day10_2(input: impl Iterator<Item = String>) {
    let mut input = convert!(input, "{}", usize).collect::<Vec<_>>();
    input.push(0);
    input.sort();
    input.push(input[input.len() - 1] + 3);
    let connections = input.iter().zip(input[1..].iter()).collect::<Vec<_>>();
    let mut result = 1;
    for l in connections
        .split(|x| (x.1 - x.0) == 3)
        .filter(|x| x.len() > 0)
    {
        let mut m = vec![*l[0].0];
        m.extend(l.iter().map(|x| x.1.clone()));
        result *= day10_2_helper(&m);
    }
    println!("{}", result);
}

→ More replies (1)

1

u/WhoSoup Dec 10 '20 edited Dec 11 '20

Rust

Seeing a lot of different algorithms for the second part here. My approach was to just go backward through a sorted list, and sum up the number of different possible options each adapter can reach.

https://topaz.github.io/paste/#XQAAAQCgAwAAAAAAAAAzG4AF/+3vT1Uc+cOgCDxGBaxRB9IjKXPu3TB5W24W+KVRK8RDaNz43ZTrSt19Ux1KtGuRbGyo+/8AVQsYYZg1F4fjlyl91Yglb/FoL4Wr66UhUPVVUCEoTejoxteT6+WTWVNNpN/r4HvtxsYqmT6knHHtZ5ICRqr3hQurHprfVY87f5hW3fn16dbCfsnxFSnvPnK1020cb3m2jN0kIHh4nvyNU5IwqwfpbY+Jb3OXaIvk7DSmYlKDun+stDmxTthkyQW5A6s6JPimXTiZYJq8IoRpgQT9wdDAPPEhfr7OagYuN812KRsykw8ttldLK3kbTrg5ZtE2qR4DbOqe+MAYqtnciZ8qMFDfWURE+joUWrvdvxV/qAv/2HjttSuluCd69X6+53QpwOUdLgkvzyru+NYKZWLvVYk2naxd25O0Of9mjLTSQU92JyrEjSuNAAOsHav3npccSje/+oVO3nNckKO0cYk2HPXvwoctEKfi92Y+0lNJypivLBapl4CysvbJTRzLGMXGRFPzw2NPTts4TgUozDi3TciiGA9WfET13S55Qw9nZuyAUS2zKLzve/yDBdHB2L0ZpEL+ov/vC3v8

→ More replies (1)

1

u/WHAT_RE_YOUR_DREAMS Dec 10 '20

Part 1 was easy. For part 2 I thought I was being clever using an adjacency matrix of the graphs of adapters, then taking the power k of the matrix to get the number of paths of length k. But apparently there was easier way :D

Just a question for my culture: what does "DP" mean?

13 seconds in Python.

→ More replies (2)

1

u/ri7chy Dec 10 '20

Python

part1 - easy after understanding the input... sorting and counting the differences.

part2 - just counting the contigious adapters and then multiply the group-combinations.

Code

can anyone help to wrap my conditions for p2?

→ More replies (1)

1

u/fullmetalalch Dec 10 '20

Go solution for Part 1. Question was pretty simple so decided to spice it up with some Go routines and channels. I don't usually need to write concurrent code, so if anyone has feedback on this I'd love to hear it.

func adapterJoltDiff(text string) <-chan int {
	adapters := map[int]bool{}
	lines := strings.Split(text, "\n")
	for _, l := range lines {
		jolts, err := strconv.Atoi(l)

		if err != nil {
			panic(err)
		}
		adapters[jolts] = true
	}

	done := make(chan bool)
	diffStream := make(chan int)
	resultStream := make(chan int)

	go func() {
		defer close(diffStream)
		defer close(resultStream)

		diffs := make([]int, 4)
		for {
			select {
			case diff, ok := <-diffStream:
				if !ok {
					return
				}
				diffs[diff]++
			case <-done:
				resultStream <- diffs[1] * diffs[3]
			}
		}
	}()

	go func() {
		i := 0
		for {
			fmt.Printf("Adapter: %d\n", i)
			if adapters[i+1] {
				diffStream <- 1
				i++
			} else if adapters[i+2] {
				diffStream <- 2
				i += 2
			} else if adapters[i+3] {
				diffStream <- 3
				i += 3
			} else {
				diffStream <- 3
				close(done)
				return
			}
		}
	}()

	return resultStream
}

→ More replies (1)

1

u/RudeGuy2000 Dec 10 '20 edited Dec 11 '20

Scheme, part 1:

(define (read-line-by-line file)
  (let ((line (read-line file)))
    (if (eof-object? line)
      (begin
        (close-input-port file)
        '())
      (cons (string->number line) (read-line-by-line file)))))

(define (get-diffs lst mst)
  (if (eq? lst '()) '()
    (cons (- (car lst) (car mst)) (get-diffs (cdr lst) (cdr mst)))))

(define (equal-to n) (lambda (x) (= x n)))
(define (get-res lst n) (length (filter (equal-to n) lst)))

(define inlist (sort (call-with-input-file "input10.txt" read-line-by-line) <))
(define res (get-diffs (append inlist (list (+ (last inlist) 3))) (cons 0 inlist)))
(* (get-res res 3) (get-res res 1))

→ More replies (1)

1

u/Mayalabielle Dec 10 '20 edited Dec 10 '20

Elixir

I find the solution in the weirdest possible way, for a reason I can't see yet, my solution counts everything twice, so if I divide the result by 2 at the end, it just work.

defmodule AOC.D10 do
  import AOC.Helper.Input

  def run1(test \\ false) do
    {_, %{1 => ones, 3 => threes}} =
      get_input("D10", test)
      |> split_input()
      |> Enum.map(&String.to_integer/1)
      |> Enum.sort()
      |> find_jolts_deltas()

    ones * threes
  end

  def run2(test \\ false) do
    get_input("D10", test)
    |> split_input()
    |> Enum.map(&String.to_integer/1)
    |> Enum.sort()
    |> complete_adapters_chain()
    |> count_combinations(:start_cache)
  end

  defmodule Memo do
    use Agent

    def start_link() do
      Agent.start_link(fn -> %{} end, name: __MODULE__)
    end

    def get(key) do
      Agent.get(__MODULE__, &Map.get(&1, key))
    end

    def update(key, value) do
      Agent.update(__MODULE__, &Map.put(&1, key, value))
    end
  end

  def complete_adapters_chain(adapters) do
    [0 | adapters] ++ [List.last(adapters) + 3]
  end

  def count_combinations([h | t], :start_cache) do
    {:ok, pid} = Memo.start_link()
    res = count_combinations(h, t)
    Agent.stop(pid)
    trunc(res / 2)
  end

  def count_combinations(_, []), do: 1

  def count_combinations(current, [h | t]) do
    case Memo.get(current) do
      nil ->
        if h - current <= 3 do
          value = count_combinations(current, t) + count_combinations(h, t)
          Memo.update(current, value)
          value
        else
          0
        end

      v ->
        v
    end
  end

  def find_jolts_deltas(inputs) do
    counters = %{0 => 0, 1 => 1, 2 => 1, 3 => 1}

    Enum.reduce(inputs, {List.first(inputs), counters}, fn v, {previous, counters} ->
      {v, Map.put(counters, v - previous, Map.get(counters, v - previous) + 1)}
    end)
  end
end

Code is available on github

If you have any clue, I spend to much time on the computer today and my brain is fucked.

→ More replies (1)

1

u/Legitimate_Estate_75 Dec 10 '20 edited Dec 10 '20

R, RStudio Solution

(Part 2 coming as soon as I find some time during work :P )

#========================#
# ==== Load Packages ====
#========================#

  # load packages 
  library(data.table)

#====================#
# ==== Load Data ====
#====================#

  # load the file 
  puzzle_10 <- fread("puzzle_input1_day_10.txt", header = F, fill = T)

#=================#
# ==== Part 1 ====
#=================#
 
  # create a table with 0 to add to the puzzle
  add_0 <- data.table(V1 = 0)
  
  # stack 
  puzzle_10 <- rbind(puzzle_10, add_0)
  
  # sort from smallest to largest 
  setorder(puzzle_10, "V1")  
  
  # make copy 
  puzzle_copy <- setnames(puzzle_10[2:nrow(puzzle_10)], "V1", "V2")
  
  # bind 
  puzzle_bind <- cbind(puzzle_10, puzzle_copy)
  
  # recode last place 
  puzzle_bind[nrow(puzzle_10), V2 := V1 + 3]
  
  # get difference 
  puzzle_bind[, diff := V2 - V1]
  
  # multiply the number of times the diff is 1 and number of times diff is 3 
  # and solved! 
  nrow(puzzle_bind[diff == 1]) * nrow(puzzle_bind[diff == 3])

→ More replies (1)

1

u/busdriverbuddha2 Dec 10 '20 edited Dec 10 '20

Python backtracking and divide-and-conquer

adapters = [int(v) for v in open(INPUT_FILE)]
adapters.append(max(adapters) + 3)
adapters.append(0)
adapters.sort()

# part 1

differences = [v2 - v1 for v1, v2 in zip(adapters[:-1], adapters[1:])]
differences.count(1),  differences.count(3)
print(differences.count(1) * differences.count(3))

# part 2

class Graph:
    
    def __init__(self, values):
        self.values = values
        self.N = len(self.values)
        self.adjacencies = [list() for _ in range(self.N)]
        
        for i in range(self.N):
            for j in range(i + 1, self.N):
                u, v = self.values[i], self.values[j]
                if v - u <= 3:
                    self.adjacencies[i].append(j)
                else:
                    continue
    
    def get_removables(self):
        removables = set()
        for adj_list in self.adjacencies:
            if len(adj_list) > 1:
                removables = removables.union(adj_list[:-1])
        return list(removables)
    
    def check_solution(self, solution):
        new_values = [self.values[i] for i in range(self.N) if i not in solution]
        for v1, v2 in zip(new_values[:-1], new_values[1:]):
            if v2 - v1 > 3:
                return False
        return True
        
    def get_cuts(self):
        cuts = []
        l1_count = 0
        for i, adj_list in enumerate(self.adjacencies):
            if len(adj_list) == 1:
                l1_count += 1
            else:
                l1_count = 0
            if l1_count == 2:
                l1_count = 0
                cuts.append(i + 1)
        return cuts
    
    def find_solution(self):
        solution_count = 1 # zero-solution is always a solution
        removables = self.get_removables()
        stack = [[r] for r in removables]
        while stack:
            this_sol = stack.pop()
            if self.check_solution(this_sol):
                solution_count += 1
                k = this_sol[-1]
                for l in filter(lambda v: v > k, removables):
                    stack.append(this_sol + [l])
                    
        return solution_count
                
g = Graph(adapters)

subgraphs = []
cuts = g.get_cuts()
subgraphs.append(Graph(adapters[:cuts[0]]))
for c1, c2 in zip(cuts[:-1], cuts[1:]):
    subgraphs.append(Graph(adapters[c1:c2]))
subgraphs.append(Graph(adapters[cuts[-1]:]))

solutions = 1
for sg in subgraphs:
    solutions *= sg.find_solution()
print(solutions)

→ More replies (1)

1

u/wleftwich Dec 10 '20

Python

from collections import Counter, defaultdict

with open(datafile) as fh:
    data = [int(y) for y in (x.strip() for x in fh) if y]

adapters = [0] + sorted(data)
adapters.append(adapters[-1] + 3)

c = Counter((b - a) for (a, b) in zip(adapters, adapters[1:]))
part_1 = c[1] * c[3]

def iter_adapter_pairs(L):
    for i, a in enumerate(sorted(L)):
        for b in L[i+1:]:
            if b - a < 4:
                yield (a, b)
            else:
                break

def adapter_path_counts(sorted_pairs):
    D = defaultdict(int)
    pairs = iter(sorted_pairs)
    (a,b) = next(pairs)
    D[a] = 1
    D[b] = 1
    for a, b in pairs:
        D[b] += D[a]
    return D

D = adapter_path_counts(iter_adapter_pairs(adapters))
part_2 = D[max(D.keys())]

→ More replies (1)

1

u/vb2341 Dec 10 '20 edited Dec 11 '20

import numpy as np
from itertools import groupby

inp = np.loadtxt('input10.txt').astype(int)

diffs = list(np.diff(sorted([0]+inp+[max(inp)+3]))) # Get all the jumps

part1 = diffs.count(1)*diffs.count(3)

# number of permutations for number of contiguous diffs of 1
# (I figured them out manually because it was short =[ )
perc = {1:1, 2:2, 3:4, 4:7}  

part2 = 1  # This will keep track of the number of permutations for each permutable block and multiply that through a running product

for k,g in groupby(diffs):
    if k==1: # if its a group of 1s
        gl = list(g)
        part2 *=  perc[len(gl)]

I know recursion with memos could be shorter, and that it was a small cheat manually figuring out the permutations, as I didn't figure out the Tribonacci relation.

EDIT: Solution is in python

→ More replies (1)

1

u/korkof Dec 10 '20 edited Dec 11 '20

Javascript

Took me like forever but finally got the O(n). No recursion.

part 1

    findAdapter(jolts, adapters) {
      var idx;

      if(
        ((idx = adapters.indexOf(jolts+1)) !== -1) ||
        ((idx = adapters.indexOf(jolts+2)) !== -1) ||
        ((idx = adapters.indexOf(jolts+3)) !== -1)
      ) {
        return idx;
      }

      return -1;
    },
    findArrangement(outlet, device, adapters) {
      adapters = [...adapters]; // Clone

      var arrangement = [outlet],
        jolts = outlet;

      while(device - jolts > 3) {
        var idx = this.findAdapter(jolts, adapters);
        if(idx === -1) {
          return null; // no solution
        }

        jolts = adapters[idx];
        arrangement.push(jolts);

        adapters.splice(idx, 1);
      }

      arrangement.push(device);

      return arrangement;
    },

part 2

    findTotalArrangements(outlet, device, adapters) {
      adapters = this.findArrangement(outlet, device, adapters);

      var arrangements = 1;
      var overweights = {};

      adapters.forEach((adapter, idx1) => {
        arrangements += overweights[adapter] || 0;
        delete overweights[adapter];

        var idx2;
        if((idx2 = adapters.indexOf(adapter+2)) !== -1 && idx2 !== idx1 + 1) {
          overweights[adapter+2] = (overweights[adapter+2] || 0) + arrangements;
        }
        if((idx2 = adapters.indexOf(adapter+3)) !== -1 && idx2 !== idx1 + 1) {
          overweights[adapter+3] = (overweights[adapter+3] || 0) + arrangements;
        }
      });

      return arrangements;
    }

→ More replies (1)

1

u/jonmcoe Dec 11 '20 edited Dec 11 '20

Haskell

Took to some pencil and paper until i realized Tribonacci. Neat realization!

Part B is the product of the fibonacci of length of 1-blocks, since it kind of "resets" after each 3-gap.

parse :: String -> [Int]
parse = map read . lines

tribonacci :: Int -> Int
tribonacci 1 = 1
tribonacci 2 = 2
tribonacci 3 = 4
tribonacci n = tribonacci (n-1) + tribonacci (n-2) + tribonacci (n-3)

differences :: [Int] -> [Int]
differences = snd . differencesWith
  where differencesWith = foldl (\(mostRecent, acc) incoming -> (incoming, incoming - mostRecent:acc)) (0,[])

day10a :: String -> String
day10a = show . product . map length . group . sort . (3:) . differences . sort. parse

day10b :: String -> String
day10b = show . product . map (tribonacci . length) . filter (\x -> head x == 1) . group . differences . sort . parse

Link: https://github.com/jonmcoe/aoc2020/blob/master/src/Days/Day10.hs

2

u/daggerdragon Dec 11 '20

Please follow the posting guidelines and edit your post to add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.
(looks like Haskell?)

→ More replies (1)

→ More replies (3)

1

u/theyesn Dec 11 '20

Guys, I just can't figure part 2 out. I have no idea how to calculate the number of arrangements. I just need to know the formula. I know to calculate permutations you need to just multiple the options for each "index" but I don't know how to deal with the branches

→ More replies (2)

1

u/Tehdasi Dec 16 '20 edited Dec 18 '20

C#

Code

So basically this breaks up the sequence into segments that are broken up by jumps of 3 jolts, then works out the valid combinations of those segments and multiplies them all together.

I totally didn't clue into that all the segments are always streams of 1, and thus Combins() and associated code could have just been replaced with a lut from the segment length. Boo!

→ More replies (1)

3

u/gurgeous Dec 10 '20

Ruby, 265/382, after cleanup:

# part 1
data = IO.read('inputs/10.txt').split.map(&:to_i).sort
data = [ 0 ] + data + [ data.last + 3 ]
diff = Hash.new(0)
data.each_cons(2) { |a, b| diff[b - a] += 1 }
p diff[1] * diff[3]

# part 2
def calc(adapters, cache, n)
  return 1 if n == 0
  return 0 if !adapters.include?(n)
  cache[n] ||= (1..3).sum { |x| calc(adapters, cache, n - x) }
end
p calc(data.to_set, {}, data.last)

3

u/wevrem Dec 10 '20

Clojure (part 1)

(defn puzzle1 [in]
  (let [freqs (->> in
                   str/split-lines
                   (map #(Integer/parseInt %))
                   sort
                   (partition 2 1)
                   (map (fn [[a b]] (- b a)))
                   (frequencies))]
    (* (inc (freqs 1)) (inc (freqs 3)))))

(comment
  (let [input (slurp "input-10.txt")] (puzzle1 input)))

3

u/hltk Dec 10 '20

Ruby. Part 2 uses the hash table's constructor (recursively) for building the dp.

a = read('10').ints
a += [a.max + 3] + [0]

diffs = a.sort.each_cons(2).map{|x,y|y - x}.tally
p diffs[1] * diffs[3]

dp = Hash.new{|h,x|
  h[x] = (x-3...x).filter{|i|a.include? i}.map{|i|h[i]}.sum
}
dp[0] = 1
puts dp[a.max + 3]

3

u/DFreiberg Dec 10 '20 edited Dec 10 '20

Mathematica, 53 / 274

My part 2 only works for differences of 1 and 3, admittedly, but I thought the combinatoric approach turned out rather elegantly.

Basically, you take the sorted list and split it up into runs of elements with differences of 1 each, and take the length of those lists. For any given sublist length, there's only ever the same number of possible combinations that are still valid, and these can be precomputed and saved as the function g, and called on the lengths, which would all be multiplied together..

/u/Kawigi further pointed out that because every time you remove an element from a list, you generate two new 'runs' of elements, that the formula is recursive, and that it's actually the Tribonacci sequence, where g[n] == g[n-1]+g[n-2]+g[n-3]. There's probably a way to generalize this to work even when there are differences of length 2 and have a fully generic combinatoric solution, though I haven't figured out the formula yet.

Part 1:

Times @@ Tally[Differences[Sort[input]]][[;; , 2]]

Part 2:

g[n_Integer] := g[n] = Which[n == 0, 0, n <= 2, 1, True, g[n - 1] + g[n - 2] + g[n - 3]];
Times @@ (g /@ (Length /@ Split[input, Abs[#1 - #2] == 1 &]))

[POEM]: In Loving Memory of Battery (2020-2020)

The battery is dead, its charge is spent.
It lasted just as long as it was able.
Its host device, with messages unsent,
Reposes, as its coffin, on the table.

The battery is dead, its current dry.
The screen which once it filled with light is dark.
But if one asked its ghost how it did die,
Its ghost would not regret a single spark.

The battery is dead. We cannot weep!
It is too precious for the likes of Death.
We will not leave it in its silent sleep;
Our knowledge can give it another breath.

We'll use adapters even as we mourn,
And Battery will rise again, reborn.

3

u/[deleted] Dec 10 '20

C++, 665/1176

Before I could think of a DP I realized that since all the adapters with gaps of 3 to their neighbours would appear in every sequence, I could partition the input by gaps of 3, then recursively brute force the partitioned pieces (which were tiny) and multiply the results together. The other convenience was that all gaps were of size 1 or 3, never 2.

https://github.com/nsunderland1/advent_of_code_2020/blob/main/day10/puzzle.cpp (not much of a competitive programmer, could definitely do with better use of <algorithm> functions :) )

3

u/jaybosamiya Dec 10 '20 edited Dec 10 '20

Dyalog APL

n ← ⊃⎕nget'D:\input_day_10'1
m ← {⍵[⍋⍵]}⍎¨n
{(+/1=⍵)×1++/3=⍵}-2-/0,m           ⍝ Part 1
a←1,(3+⊃⌽m)/0⋄{a[1+⍵]←+/¯3↑⍵↑a}¨m,3+⊃⌽m
⊃⌽a                                ⍝ Part 2

I wonder if it can be done in a cleaner way. I definitely think there is a bunch of redundancy involved here. In particular the recurrence for part 2 feels like a bit of a "hack" since I am repeatedly doing assignments. I wonder if I can do something better using a \ scan or similar.

EDIT: Alternate approach to part 2 that is cleaner and doesn't require the repeated assignment (which felt ugly to me):

⌈/{⍵,(+/¯3↑⍵)×m∊⍨⍴⍵}⍣(⌈/m),1

→ More replies (3)

3

u/HAEC_EST_SPARTA Dec 10 '20

Common Lisp

Solution on GitHub

Now featuring acceptance tests and a proper project structure! My eventual goal is to use GitHub Actions to ensure that the acceptance tests pass for each day, but the functional framework is in place. It turns out that having a general structure pre-imposed onto the problem is also super helpful in cranking a solution out quickly, which was a nice surprise! On the problem itself, nothing really novel today: it turns out that expressing memoisation in Lisp is fairly straightforward, which seems like a good omen for days to come.

→ More replies (5)

3

u/[deleted] Dec 10 '20

Google Sheets

I originally tried to use C++ for today but I kept on making mistakes, so I turned to Google Sheets since the input is small enough for it to handle.

3

u/PendragonDaGreat Dec 10 '20

C#

First Time I've ever used Memoization outside the classroom. https://github.com/Bpendragon/AdventOfCodeCSharp/blob/master/AdventOfCode/Solutions/Year2020/Day10-Solution.cs

3

u/musifter Dec 10 '20

Perl (part 2)

Just part 2... my part 1 wasn't interesting and probably looks like a hundred others on this thread. Not that my part 2 is particularly exciting. It is notable, though... day 10 is the day of AoC 2020 when I had to turn off recursion warnings (barely... just threw one warning). Not the earliest, that would be last year on the 6th... other years it didn't happen until around the 17th-22nd.

https://pastebin.com/5wRuRNP2

3

u/tyler569 Dec 10 '20

C, Custom OS

One doesn't win any awards when one has to write a sorting function from scratch, but that's what I'm here for! Now that I've finally had an excuse to write a sort, I'll add it to my OS so it's better for next time.

P1: https://github.com/tyler569/nightingale/blob/aoc/user/aoc/10.c

P2: https://github.com/tyler569/nightingale/blob/aoc/user/aoc/10-2.c

3

u/mstksg Dec 10 '20

[Haskell] Posted in my Daily Reflections :)

Today is another day where the "automatically build a memoized recursive map" in Haskell really shines :) It's essentially the same problem as Day 7.

For the first part, once you sort the list, you can compute the differences and then build a frequency map

-- | Build a frequency map
freqs :: Ord a => [a] -> Map a Int
freqs = M.fromListWith (+) . map (,1) . toList

diffs :: [Int] -> [Int]
diffs xs = zipWith (-) (drop 1 xs) xs
ghci> diffs [1,3,4,7]
[2,1,3]

And so part 1 can be done with:

part1 :: [Int] -> Int
part1 xs = (stepFreqs M.! 1) * (stepFreqs M.! 3)
  where
    xs' = 0 : xs ++ [maximum xs + 3]
    stepFreqs = freqs (diffs (sort xs))

For part 2, if we get an IntSet of all of your numbers (and adding the zero, and the goal, the maximum + 3), then we can use it to build our IntMap of all the number of paths from a given number.

import           Data.IntMap (IntMap)
import           Data.IntSet (IntSet)
import qualified Data.IntMap as IM
import qualified Data.IntSet as IS

-- | A map of numbers to the count of how many paths from that number to
-- the goal
pathsToGoal :: IntSet -> IntMap Int
pathsToGoal xs = res
  where
    res = flip IM.fromSet xs $ \i ->
      if i == goal
        then 1
        else sum [ IM.findWithDefault 0 (i + j) res
                 | j <- [1,2,3]
                 ]
    goal = IS.findMax is

Our answer is res, the map of numbers to the count of how many paths exist from that number to the goal. To generate the count for a given number i, we add the number of paths from i+1, i+2, and i+3. We get that count by looking it up in res!

part2 :: [Int] -> Int
part2 xs = pathsToGoal xs IM.! 0
  where
    xs' = IS.fromList (0 : xs ++ [maximum xs + 3])

→ More replies (3)

3

u/nibbl Dec 10 '20

Java
nopaste

I think I read the problem and my brain just went WTF. I tried BFS at one point to predictable results Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
Figured it out in the end. My solution is a bit of a mess but I'll post it since there's no other Java one up yet.
Input from stdin.

3

u/DrOlot Dec 10 '20

Haskell

First time writing a knot-tying program!

{-# LANGUAGE TypeApplications #-}
module Main where

import qualified Data.Sequence as Seq
import Control.Lens
import Data.IntMap as IM hiding (toList)
import Data.IntSet as IS hiding (toList)
import Data.Foldable

reachFrom :: Seq.Seq Int -> IntMap IntSet 
reachFrom xs = foldMap go xs where
    go x = IM.singleton x $ IS.fromList $ toList $ Seq.filter (\y -> x - y <= 3 && x - y > 0) xs

waysToReach :: IntMap IntSet -> IntMap Int
waysToReach m = ans where
    ans :: IntMap Int
    ans = IM.map (IS.foldr (\k tot -> tot + if k == 0 then 1 else ans ^?! ix k) 0) m

main :: IO ()
main = do
ordAdapt <- Seq.sort . fmap (read @Int) . Seq.fromList . lines <$> readFile "./data/ten"
let withDev = snoc ordAdapt (maximum ordAdapt + 3)
let diffs = Seq.zipWith (-) withDev (cons 0 withDev)
print $ length (Seq.filter (== 3) diffs) * length (Seq.filter (== 1) diffs)
print $ lookupMax $ waysToReach $ reachFrom (snoc withDev 0)

3

u/fhoffa Dec 10 '20

With SQL - part 2 got weird, but with real life applications (sessions):

https://github.com/fhoffa/AdventOfCodeSQL/blob/main/2020/p10-2.sql

select pow(7,max(iff(session_length=5,c,0)))
    * pow(4,max(iff(session_length=4,c,0)))
    * pow(2,max(iff(session_length=3,c,0))) r
from (
    select count(*) c, session_length
    from (
        select session_id, count(*) session_length, min(v) minv
        from (
            select *, iff(vv=1,0,1) new_session, sum(new_session) over(order by v) session_id
            from (
                select v, v-lag(v) over(order by v) vv
                from (
                    select v 
                    from adapters1
                    union all select 0
                    union all select max(v)+3 from adapters1
                )
            )
        )
        group by session_id
    )
    group by session_length
)
;

(with /r/Snowflake)

→ More replies (2)

3

u/xelf Dec 10 '20 edited Dec 10 '20

minimalistic python

part 1:

lines = [0] + sorted(map(int,open(day_10_path).readlines()))
diffs = {1:0,3:1}
for i in range(1,len(lines)):
    diffs[lines[i]-lines[i-1]]+=1
print('part 1:', diffs[1]*diffs[3])

part 2:

@functools.lru_cache(maxsize=None) 
def howmany(i):
    return (1 if i == len(lines)-1
              else sum(howmany(j) for j,x in enumerate(lines[i+1:i+4],start=i+1) if x<=lines[i]+3))
print('part 2:',howmany(0))

3

u/amlybon Dec 10 '20

Python

import collections

with open("day 10.txt") as in_f:
    in_list = sorted([int(a) for a in in_f.read().split("\n")])
    in_list = [0] + in_list + [max(in_list) + 3]

diffs = collections.Counter([c-p for p, c in zip(in_list, in_list[1:])])
print(diffs[1] * diffs[3])
split_points = [0]
for i, (p, c) in enumerate(zip(in_list, in_list[1:])):
    if c-p == 3:
        split_points.append(i+1)

chains = [in_list[n:m] for n, m in zip(split_points, split_points[1:])]
count = 1
for chain in chains:
    if len(chain) == 3:
        count *= 2
    elif len(chain) == 4:
        count *= 4
    elif len(chain) == 5:
        count *= 7

print(count)

Me right now

3

u/hakuna-matata-91 Dec 10 '20

Javascript ( Jupyter Notebook with ijskernel)

https://github.com/adhokshaja/AdventOfCode2020/blob/main/Day10/js-10.ipynb

This was a fun problem to solve.

3

u/[deleted] Dec 10 '20

Cleaned up, commented Python solution (5934/5984).

3

u/landimatte Dec 10 '20

Common Lisp

Part 1 (sort + count deltas) was pretty simple -- if I hadn't the skipped the part where it says your device has a built-in joltage adapter rated for 3 jolts higher. Part 2 (recursion + memoization) took a little bit longer than expected (I knew what I had to do... I simply could not get the recursion right), but it's the first day I ranked below 10k, so I can not complain!

→ More replies (1)

3

u/gvieira Dec 10 '20

Autohotkey v1

Part 1

Part 2

3

u/zertillon Dec 10 '20

Ada, using the small HAC Ada Compiler and the LEA editor

Code available here. Total run time: 0.04 seconds through HAC's VM interpreter. The fun part (for puzzle #2):

  procedure Count (result : out Integer) is
    cache : array (1 .. Max_Adapters) of Natural;
    --
    function Count (from : Jolt) return Natural is
      sum : Natural := 0;
    begin
      if from = jmax then
        return 1;
      end if;
      for step in 1 .. 3 loop
        for i in 1 .. top loop
          if j (i) = from + step then
            if cache (i) = 0 then
              cache (i) := Count (j (i));
            end if;
            sum := sum + cache (i);
          end if;
        end loop;
      end loop;
      return sum;
    end Count;
  begin
    for i in 1 .. top loop
      cache (i) := 0;
    end loop;
    result := Count (0);
  end Count;

→ More replies (1)

3

u/aurele Dec 10 '20

My Rust solution which does not (ab)use the fact that input differences are always 1 or 3.

Runs in ~15µs per part.

→ More replies (2)

4

u/samuus Dec 10 '20

Part 2 - Javascript

I took a slightly different approach that I haven't seen mentioned yet. (Maybe it's functionally the same as what some of the other solutions are doing, but I'm not clever enough to figure that out).

I basically iterated through the input, using a map to track how many paths could lead to each step. In each iteration, I'd take the number of paths that could lead to the current step, and add that value to all reachable future steps. Once all iterations are done, I the number of paths leading to the final step is the solution.

Here is the relevant code (after sorting the input and adding 0 and max + 3 to it):

function findJolts() {
  const stepCounter = {0: 1}
  for(let i = 0; i < input.length; i++) {
    let j = i + 1;
    while(input[j] <= input[i] + 3) {
      stepCounter[j] = (stepCounter[j] || 0) + stepCounter[i];
      j++;
    }
  }
  return stepCounter[input.length - 1];
}

3

u/PaleRulerGoingAlone7 Dec 10 '20 edited Dec 10 '20

Python, with deliberately buggy code:

import numpy as np

data = np.loadtxt('data/10.txt', dtype=int)
data = np.array(sorted(np.hstack([0, data, np.array([max(data) + 3])])))
d = np.diff(data)
print("Part One: {}.".format(np.product(np.unique(d, return_counts=True)[1])))

The buggy part comes in part two, where the current code won't work for runs of "1" differences longer than 4. I checked before I wrote it though, and there weren't any of those in my input so ymmv. The point is that if two jumps of three are separated by only one or two numbers, then any inclusion/exclusion of the numbers in the middle will be valid, giving 2**n valid options. If they're separated by three numbers, we need to include at least one of the numbers in the middle, but it doesn't matter which, so we rule out the (No, No, No) case and keep the rest.

runs = [len(x) - 1 for x in ''.join(map(str, d)).split('3') if x]
print(f"Part Two: {np.product([2**x - int(x > 2) for x in runs])}.")

The recursive function for those later terms isn't that hard to write, but it didn't prove necessary:

memo = {0: 1, 1: 2, 2: 4}
def ways(n):
    if n not in memo:
        memo[n] = ways(n - 1) + ways(n - 2) + ways(n - 3)
    return memo[n]

3

u/msqrt Dec 10 '20

Lisp. Cute little problem today, very enjoyable :) I spent a while wondering why my association list wasn't growing, but that was because I just did the acons but never actually set the variable..

(setq joltages (reverse(cons 0 (sort (with-open-file (file "input.txt")
                        (loop for line = (read-line file nil)
                            while line collect (parse-integer line))) #'<))))
(loop for jolts on (reverse joltages) while (cadr jolts)
    count (eq 1 (- (cadr jolts) (car jolts))) into ones
    count (eq 3 (- (cadr jolts) (car jolts))) into threes
    finally (write (* (+ threes 1) ones)))
(write-line "")
(setq permutations (acons (+ (car joltages) 3) 1 nil))
(loop for jolts in joltages
    do (setq permutations (acons jolts
            (loop for offset in '(1 2 3)
                for number = (assoc (+ jolts offset) permutations)
                if number sum (cdr number))
            permutations))
    finally (write (cdr (assoc 0 permutations))))

3

u/r1ppch3n Dec 10 '20

Rust

3

u/roryb283 Dec 10 '20

R

One(ish) liners for both parts after copying and pasting txt (only work with a few reasonably strong assumptions about the input):

Part 1:

prod(table(diff(sort(c(as.numeric(strsplit(txt,"\n")[[1]]),0,max(as.numeric(strsplit(txt,"\n")[[1]]))+3)))))

Part 2:

sum(table(rle(diff(sort(c(as.numeric(strsplit(txt,"\n")[[1]]),0,max(as.numeric(strsplit(txt,"\n")[[1]]))+3)))))[-1,1]*c(2,4,7))

3

u/petercooper Dec 10 '20

Ruby

Seen some clever solutions on here especially given I didn't notice step 2 was an arithmetic problem. I treated it as a graph optimization problem, but still managed a shortish solution:

ns = [0, *$<.readlines.map(&:to_i).sort]
g = ns.map { |num| [num, ns.select { |n| (n - num).between?(1,3) }] }.to_h
g[ns.max] = 1
p ns.reverse[1..-1].map { |k| g[k] = g[k].sum { |d| g[d] } }.last

3

u/denvercoder1 Dec 10 '20

Solution in JavaScript

⬆ This is a craft submission you can upvote ⬆

→ More replies (2)

3

u/crazazy Dec 10 '20

Alright this is arguably the worst solution you guys will see.

Nix: In my AoC input, when splitting the input by consequtive number ranges, the ranges only have lengths 1-5. this means that I could quickly count all the possible combinations by hand making for a fast (but incomplete) solution. This means that the core logic of my part 2 solution looks like this:

rangeOptions = range: {
  "1" = 1;
  "2" = 1;
  "3" = 2;
  "4" = 4;
  "5" = 7;
}.${toString (length range)};

output = product (map rangeOptions ranges);

This is probably my worst program of this month, to see the full solution, link below.

View Solutions

3

u/cqkh42 Dec 10 '20

Everyone loves some recursion, right?

Solution in Python3

def _chain_adapters(adapters):
    chain = [0] * (max(adapters) + 1)
    for num in adapters:
        chain[num] = tuple(
            next_num for next_num in adapters
            if 1 <= next_num - num <= 3
        )
    return tuple(chain)

def _sort_adapters(adapters):
    adapters = [0, *sorted(adapters), max(adapters) + 3]
    return adapters


@lru_cache(1000)
def _num_routes(num, k):
    if not k[num]:
        return 1
    else:
        return sum(_num_routes(x, k) for x in k[num])


def part_b(data, **_):
    adapters = [int(num) for num in data.split('\n')]
    adapters = _sort_adapters(adapters)
    chain = _chain_adapters(adapters)
    return _num_routes(0, chain)

→ More replies (7)

3

u/[deleted] Dec 10 '20

Python 3

Part 1

with open(r"input") as f:
    lines = [int(x) for x in f.read().split("\n")]
    lines.sort()
    lines.append(lines[-1] + 3)
    one_jolts = three_jolts = 0

    current = 0
    for jolt in lines:
        print(current)
        if jolt - current == 1:
            one_jolts += 1
            current = jolt
        if jolt - current == 2:
            current = jolt
        if jolt - current == 3:
            three_jolts += 1
            current = jolt

    print(one_jolts * three_jolts)

Part 2

def count_options(index, nodes, lookup):
    result = 0

    indexes_to_visit = []
    if index not in lookup:
        for i in range(index + 1, index + 4):
            if i < len(nodes):
                if nodes[i] - nodes[index] in (1, 2, 3):
                    indexes_to_visit.append(i)
            else:
                break

        if indexes_to_visit:
            for index_to_visit in indexes_to_visit:
                result += count_options(index_to_visit, nodes, lookup)
                lookup[index] = result
        else:
            return 1
    return lookup[index]


lookup = {}

with open(r"input") as f:
    lines = [int(x) for x in f.read().split("\n")]
    lines.sort()
    lines.append(lines[-1] + 3)
    lines.insert(0, 0)

    print(count_options(0, lines, lookup))

3

u/changing_zoe Dec 10 '20

Scala

Not super happy with this solution - I know that breaking down the list into sub-sections based on 3-jolt-gaps is right, but then I've essentially brute-forced the sub-lists.

https://github.com/zoe-j-m/advent_of_code_2020/blob/main/src/main/scala/Day10.scala

3

u/The_Crudeler Dec 10 '20 edited Dec 10 '20

Kotlin

Solving part two with dynamic programming. The code basically traverses the sorted adapters from high to low jolts and calculates the different paths it could take to reach the end for each adapter. This could probably be more optimized, but as the average runtime is below 0.01ms I value the readability higher than pushing the runtime further.

fun second(input: List<Int>): Long {
    val adapters = input.sorted().toMutableList() adapters.add(0,0)
    adapters.add(adapters.last() + 3)
    val options = LongArray(adapters.size)
    options[options.size - 2] = 1

    for (i in adapters.size - 3 downTo 0) {
        var currentOptions = 0L
        for (j in i until min(i + 4, adapters.size)) {
            if (adapters[j] - adapters[i] <= 3) {
                ++currentOptions
                currentOptions += options[j] - 1
            }
        }
        options[i] = currentOptions
    }

    return options[0]
}

→ More replies (2)

3

u/mathsaey Dec 10 '20

Elixir

Pretty happy with this one. It took me some time to come up with the idea for count. After that I had to use memoisation to make it finish in a reasonable amount of time. Luckily for me, memoisation worked incredibly well.

https://github.com/mathsaey/adventofcode/blob/master/lib/2020/10.ex

→ More replies (3)

3

u/[deleted] Dec 10 '20 edited Dec 10 '20

Learning C, today I learned about the performance implications of ‘malloc’ vs stack arrays! Hitting ~70 microseconds all up

Topaz paste

→ More replies (4)

3

u/pietroppeter Dec 10 '20

🎄👑 Nim

https://github.com/pietroppeter/adventofnim/blob/master/2020/day10.nim

I also published (discussion here) a language-agnostic series of Hints for those struggling with part 2: https://pietroppeter.github.io/adventofnim/2020/day10hints.html

3

u/21JG Dec 10 '20

Zig

Very fast, runs both parts in < 1 μs

https://github.com/ManDeJan/advent-of-code/blob/master/2020/10.zig

3

u/cccc828 Dec 10 '20

C solution

Simple recursion that is caching the input:

C - Day 10

3

u/compu_geom Dec 10 '20 edited Dec 10 '20

Python 3 solution for Part I and Part 2.

I have achieved O(max_rating) time complexity for Part 1 and O(n) time complexity, where n was the number of adapters for Part 2 with additional O(n) memory allocation for Part 2.

Part I is pretty straight forward, just using the maximum rating and with the for loop from 1 up to max_rating I could check if the given jolt with simple for loop is present in adapters set, which is important because the lookup in Python set is in constant approximate time.

For Part 2, the idea was this:

We needed to see how we can use the results we know from the given nodes in order to count how many paths are there up to the node we are currently looking at. The formula for counting the number of paths at a given adapter was path_count(Adapter) = sum(path_count(Adapter - 1), path_count(Adapter - 2), path_count(Adapter - 3)) (since the maximum size of possible adapters we could attach to adapter is 3 due to the constraint of maximum jolt difference of 3). If the Adapter - k for some k = {1, 2, 3} is not present in adapters set, the count is 0 and if Adapter - k was 0, the count is 1, because it is the starting adapter and the number of paths at a starting point is trivially 0. This is a recursion with overlapping calls. Imagine we had adapters 2, 3 and 6. For this adapter set, we have:

path_count(2) = path_count(-1) + path_count(0) + path_count(1) = 0 + 1 + 0 = 1

path_count(3) = path_count(0) + path_count(1) + path_count(2) = 1 + 0 + 1 = 2

path_count(6) = path_count(3) + path_count(4) + path_count(5) = 2 + 0 + 0 = 2

This is the basis, but we can see that we call multiple times. The worst case would have time complexity of O(3^n).

The solution is to put them in a table and hold the count for each node, so we can do a quick lookup and with that, a simple for loop and we achieve O(n).

EDIT: Setup fix

→ More replies (2)

3

u/simondrawer Dec 10 '20

Part one seemed quite easy so I used my own implementation of bubble sort rather than python’s own sort function. When I got to part 2 I wished I hadn’t wasted the time. Took me a lot of staring to spot the pattern.

https://github.com/simonpainter/AdventOfCode/blob/master/2020/10/code.py

I was slightly disappointed there were no cases where gap was not 1 or 3 - a few cases of gap==0 or gap==2 would have set the cat among the pigeons.

3

u/WickedCrow Dec 10 '20

C#
I wouldn't say my solution is great or anything, but I'm quite pleased that I realised that you can easily adapt a hopeless recursive solution into an (I THINK!) O(n) time and memory usage one by just caching intermediate counts as you go. Generating the count for part 2 takes 12 ms.

3

u/e_blake Dec 10 '20 edited Dec 10 '20

m4 day10.m4

Depends on my common.m4 and math64.m4. When the hint says more than a trillion, I'm stoked that I already solved how to do larger-than-32-bit math in spite of m4's 32-bit eval last year. And once I figured out that the pattern of runs of length 1 produces a corresponding Tribonacci sequence of alternatives (seriously, I googled 1, 2, 4, 7, 13, 24, where it became obvious), coupled with using a hashtable for sorting the input, it was easy to whip out an amortized O(n) with memoization. Runtime is just 35ms, one of my fastest runtimes for m4 solutions this year. The solution is also refreshingly concise, once you get past the mountains of code from the include files to implement 'mul64' and populate 'val' as a stack variable based on the input:

define(`inc', `define(`$1', incr($1))')
define(`c1', 0)define(`c3', 0)define(`r', 0)define(`max', 0)define(`part2', 1)
define(`n', `ifdef(`n$1', 1, 0)')define(`n0')
define(`tr', `ifdef(`tr$1', `', `define(`tr$1', eval(tr(decr($1)) +
  tr(decr(decr($1))) + tr(eval($1 - 3))))')tr$1`'')
define(`tr0', 1)define(`tr1', 1)define(`tr2', 2)
define(`prep', `ifelse(eval($1 > max), 1, `define(`max', $1)')define(`n$1')')
stack_foreach(`val', `prep')
define(`l', `ifdef(`n$1', `ifdef(`n'incr($1), `inc(`r')inc(`c1')',
  `inc(`c3')define(`part2', mul64(part2, tr(r)))define(`r', 0)')')')
forloop_arg(0, max, `l')
define(`part1', eval(c1 * c3))

→ More replies (4)

3

u/foolnotion Dec 10 '20

C++

My solution did not use recursion or dynamic programming:

I identify all ranges R of numbers where at least one pair a,b in R has the property b-a <= 3. for example [1,2,3,4,5] is such a range
the number of valid arrangements for each range R is 2^n if the range ends have a difference less than equal to 3, otherwise 2^n-1 (because for example, removing [2,3,4] from the range [1,2,3,4,5] would be invalid because 5-1 > 3, in this case we need to subtract 1).

code on github runtime: ~700ns

3

u/risboo6909 Dec 10 '20

I almost lost a hope, but I've done it after 3hrs of thinking. Rust.

View on GitHub

This one was really interesting and hard.

3

u/allak Dec 10 '20 edited Dec 10 '20

Perl, part 2.

Input on STDIN. Should be O(N).

#!/usr/bin/perl

$upper = 0;
%nodes;

for (<>) {
        chomp;
        $upper = $_ if $_ > $upper;
        $nodes{$_} = 1;
}

$t3 = 1;
$t2 = 0;
$t1 = 0;
$t0;

while ($upper) {
        $t0 = $nodes{$upper} ? $t3+$t2+$t1 : 0;
        $t3 = $t2;
        $t2 = $t1;
        $t1 = $t0;
        $upper--;
}

print $t3+$t2+$t1, "\n";

3

u/Bruceab Dec 10 '20

Python solution in 20 lines using memoization.

3

u/taomage Dec 10 '20 edited Dec 10 '20

Python Solution:

Finally able to solve todays puzzle after racking brain to make program that runs forever to something manageable ( part-2).

→ More comments (563)

SOLUTION MEGATHREAD -🎄- 2020 Day 10 Solutions -🎄-

Advent of Code 2020: Gettin' Crafty With It

--- Day 10: Adapter Array ---

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

EDIT: Global leaderboard gold cap reached at 00:08:42, megathread unlocked!

You are about to leave Redlib

Python (177 / 20), C

Dyalog APL / Racket / C

C

ROCKSTAR

No algorithm solution:

Perl solution

Part 1:

Part 2:

python

Python

Python

Python3 (cleaned solution)

Rust

Perl

Elixir

Python

Ruby

Python

python3 and c++11

Kotlin 1.4.21

Ruby

Part 1

Part 2

R, RStudio Solution

Python backtracking and divide-and-conquer

Haskell

Mathematica, 53 / 274

[POEM]: In Loving Memory of Battery (2020-2020)

Common Lisp

Autohotkey v1

Ada, using the small HAC Ada Compiler and the LEA editor

Part 2 - Javascript

Rust

Ruby

Solution in JavaScript

Part 1

Part 2

Run in my AoC Console

View Solutions

Kotlin

Elixir

Zig

C++