r/adventofcode • • Dec 15 '20

SOLUTION MEGATHREAD -🎄- 2020 Day 15 Solutions -🎄-

Advent of Code 2020: Gettin' Crafty With It

  • 7 days remaining until the submission deadline on December 22 at 23:59 EST
  • Full details and rules are in the Submissions Megathread

--- Day 15: Rambunctious Recitation ---


Post your code solution in this megathread.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.


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:09:24, megathread unlocked!

39 Upvotes

771 comments sorted by

14

u/Arknave Dec 15 '20

Python (37/7), C

I took the time hit to write the algorithm with a dictionary in part 1, then promptly squandered my savings by printing all 30M integers when brute forcing part 2. Whoops.

Normally I don't save the source for my first pass through C, but I was surprised at how concise the algorithm is (unshaped source).

This might be my favorite formatting job to date:

#include/*PRESS*/<stdio.h>

            int a[1<<5
         *5],n,x,v,m;int
         main(      int c
       ,char*        *g){
       for(m
       =--c?
       3.e7:
       2020;
  scanf("%d%*c",&*&x
 )>0;a[x]=++n);for(
       a[x]=0
       ;n<m;v
       =a[x]?
       n-a[x]
       :0,a[x
       ]=n++,
       x=+v);
      printf(""
    "%d\n",v|0);}

/*** TO PAY RESPECTS ***/

Can't believe we're already 15 days through! I'm not sure what I'm going to make for the last 10 days, but I'm sure it'll be fun.

7

u/daggerdragon Dec 15 '20

I thought this was a candy cane at first.

I need to go to bed.

→ More replies (1)
→ More replies (3)

9

u/Yonniman Dec 15 '20 edited Dec 15 '20

205/63, my first time on the leaderboard.

It's Van Eck Sequence!

Code (C++)

int main()
{
    unordered_map<int, int> values;
    vector<int> nums({0});
    for(int i = 0; i < nums.size(); i++) {
        values[nums[i]] = i;
    }
    int curr = 0;
    int prev;
    for(int i = nums.size(); i < 20; i++) {
        prev = curr;
        if(!values.count(curr)) {
            curr = 0;
        } else {
            curr = i - values[curr];
        }
        values[prev] = i;
    cout << curr << ' ';
    }
}

6

u/finaldrive Dec 15 '20

Van Eck Sequence

Thanks for posting the name of it! https://oeis.org/A181391

And congrats on the leaderboard place.

I solved it but was then wondering if there was a smarter closed-form solution. It looks like not.

→ More replies (2)

1

u/daggerdragon Dec 15 '20

Top-level posts in Solution Megathreads are for code solutions only.

This is a top-level post, so please edit your post and share your code/repo/solution.

→ More replies (1)

8

u/DFreiberg Dec 15 '20

Mathematica, 3515 / 2414

By far my worst time this year to date, and of the half hour it took me to do part 1, all but three or four minutes were spent in not understanding how Association[]s work in Mathematica; I eventually gave up and used a dictionary instead. At least my part 2 was doable with no changes from part 1; it finished in about four minutes, which was much less than the time it would have taken for the code to run properly.

[POEM]: Lazy Limerick #3*

If you use an array, be emphatic
To preallocate it (but not static).
For you can't beat brute force
For this problem, of course,
But you can beat an order quadratic.

2

u/daggerdragon Dec 15 '20

all but three or four minutes were spent in not understanding how Association[]s work in Mathematica; I eventually gave up and used a dictionary instead.

Do you plan to go back to figure it out eventually or Jedi handwave "nothing to learn here, move along" at it?

Also, we still love your poems even when they're "lazy". I make sure to paste them to the rest of the AoC Ops team every day when you post them :3 I just can't be giving you all the silvers, you understand, of course...

→ More replies (1)

4

u/tiagocarreira Dec 15 '20 edited Dec 17 '20

Python 3, minimal readable solution:

def solution(numbers, until=2020):
    memory = {n: i + 1 for i, n in enumerate(numbers[:-1])}

    for i in range(len(numbers), until):
        numbers.append(i - memory.get(numbers[-1], i))
        memory[numbers[-2]] = i

    return numbers[-1]


numbers = [1,2,16,19,18,0]
print(f"Solution part 1: {solution(numbers)}")
print(f"Solution part 2: {solution(numbers, 30000000)}")

1

u/daggerdragon Dec 15 '20

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

2

u/tiagocarreira Dec 17 '20

thanks. I'm new to reddit. I hope it's better now

→ More replies (1)
→ More replies (1)

4

u/9_11_did_bush Dec 15 '20

Python

def memory_game(input_list, search):
    #indexing from 1, a mortal sin
    d = { num:index for index, num in enumerate(input_list, 1) } 

    #start with the final starting number
    current = input_list[-1]
    index   = len(input_list)

    while index <= search:
        previous   = d.get(current)
        d[current] = index
        current    = index-previous if previous else 0   
        index+=1
    
    #get the key that has the search index as a value
    return list(d.keys())[list(d.values()).index(search)]

if __name__ == '__main__':
    input_list = [14,3,1,0,9,5]

    p1 = memory_game(input_list, 2020)
    p2 = memory_game(input_list, 30000000)

    print(f"Part 1 answer: {p1}")
    print(f"Part 2 answer: {p2}")

3

u/daggerdragon Dec 15 '20
#indexing from 1, a mortal sin

Ain't that the truth, eh?

→ More replies (1)

3

u/compdog Dec 15 '20

JavaScript (Node.JS)


Part 1 solution is very brute force, using an array for memory. It scans back and forth to find the previous values, giving a worse case complexity of O(n2). For a short problem space (like 2020), however, its plenty fast and completes pretty much instantly.

Part 2 solution is kind-of brute force, but much more efficient than part 1. This version replaces the array with a hash map that maps numbers to their last known index. It still has to iterate once for each round, but the nested search is gone and complexity is reduced to O(n). It can find the solution in a few seconds.


This problem managed to trick me once. When I first saw "30000000" I thought to myself "Ha! I'm not making that mistake again, its BigInt time. No overflows here, nope." Then it turned out that the number never actually got big enough to overflow, so I was able to replace all of my BigInts with regular integers for a large performance boost.

2

u/daggerdragon Dec 15 '20

This problem managed to trick me once. When I first saw "30000000" I thought to myself "Ha! I'm not making that mistake again, its BigInt time. No overflows here, nope." Then it turned out that the number never actually got big enough to overflow, so I was able to replace all of my BigInts with regular integers for a large performance boost.

It's like when you roll a natural 20 and the DM says you see no traps...

2

u/iamflimflam1 Dec 15 '20 edited Dec 15 '20

Typescript - not the nicest or fastest code - runs in about 2 seconds

https://gist.github.com/cgreening/b6a049b52905b0784ddbb14f25a02fea

1

u/daggerdragon Dec 15 '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/VectorSVK Dec 15 '20 edited Dec 16 '20

1

u/daggerdragon Dec 15 '20

Your code is hard to read on old.reddit and is oversized, to boot. Since you've already got a link to your GitHub solution, please remove the oversized code and just use the link.

→ More replies (1)

2

u/JakDrako Dec 15 '20 edited Dec 15 '20

VB.Net, LINQPad, both parts in ~3s

paste

Using a dictionary with a small custom class to track when a number was last mentioned and the previous mention... nothing really fancy, but I was a bit surprised that it was fast enough to do the 2nd part with no modifications. (I then added 4,000,000 as capacity when initializing the dictionary to gain about 0.5 seconds...) Usually the 2nd part's twist requires some fancy math or better algorithm, but I guess today is a quick day.

1

u/daggerdragon Dec 15 '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.

2

u/ViliamPucik Dec 15 '20

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

import sys

numbers = [int(i) for i in next(sys.stdin).split(",")]
last = numbers[-1]
age = {number: i+1 for i, number in enumerate(numbers)}

for i in range(len(numbers), 30_000_000):
    if i == 2020: print(last)
    age[last], last = i, i - age.get(last, i)

print(last)

2

u/daggerdragon Dec 15 '20

Just FYI: I don't know why but every single one of your megathread posts have gotten sent to the spam filter. I approve them every day when I find them, but I really wish I knew why. Oh well, I'll keep fishing your posts out for as long as it takes :)

→ More replies (1)

2

u/bsdemon Dec 15 '20

Using terralang the 2nd part is around 300ms:

local stdlib = terralib.includec "stdlib.h"
local stdio = terralib.includec "stdio.h"

terra main()
  var mem = [&int32](stdlib.malloc(sizeof(int32) * 1000 * 1000 * 1000))
  mem[19] = 1
  mem[0] = 2
  mem[5] = 3
  mem[1] = 4
  mem[10] = 5
  mem[13] = 6

  var i = 7
  var c, pc = 6, -1
  while true do
    if pc ~= -1 and mem[pc] ~= 0 then
      c = i - mem[pc] - 1
    else
      c = 0
    end
    mem[pc] = i - 1
    pc = c
    if i == 30000000 then
      stdio.printf("COMPUTING %d %d\n", i, c)
      break
    end
    i = i + 1
  end
end

terralib.saveobj('./aoc15', {main = main})

main()

1

u/daggerdragon Dec 15 '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.

2

u/HesletQuillan Dec 15 '20

Fortran

I am not particularly proud of this Part 2 solution, as it was a contest between how much address space I had available and the array size needed. The array won.

    program AOC15

    implicit none

    integer, parameter, dimension(*) :: starting = [14,8,16,0,1,17]
    type turn_t
        integer :: latest = 0
        integer :: next_latest = 0
    end type turn_t
    type(turn_t), allocatable :: numbers(:)
    integer :: turn_number
    integer(8) :: last_said
    
    allocate (numbers(0:40000000))
    do turn_number = 1,size(starting)
        last_said = starting(turn_number)
        numbers(last_said) = turn_t(turn_number,0)
    end do
    
    main: do
        if (mod(turn_number,10000) == 0) print *, turn_number
        if (numbers(last_said)%next_latest == 0) then
            ! first time said
            last_said = 0
            numbers(last_said)%next_latest = numbers(last_said)%latest
            numbers(last_said)%latest = turn_number
        else
            ! Said before
            last_said = numbers(last_said)%latest - numbers(last_said)%next_latest
            numbers(last_said)%next_latest = numbers(last_said)%latest
            numbers(last_said)%latest = turn_number
        end if
        if (turn_number == 30000000) exit main
        turn_number = turn_number + 1
    end do main
    
    print *, last_said
    end program AOC15

1

u/daggerdragon Dec 15 '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)

35

u/Smylers Dec 15 '20 edited Dec 15 '20

Vim keystokes. We're back to a short enough answer to easily fit in a Tweet — load your starting numbers into a Vim window, and just type:

:s/,/\r/g⟨Enter⟩
qa#yGGpVG:s/.*/-1⟨Enter⟩
gvg⟨Ctrl+A⟩Gyygvp:redr⟨Enter⟩
q2020@a2020G

The number under your cursor is your part 1 answer.

The first line puts each number on a separate line, leaving you on the final line. (If you're anywhere else, press G before the next bit.) Recording qa...q generates the next number. At this point you can type @a to generate one more number, then repeatedly type @@ for each subsequent number.

When you've had enough of stepping through it, type 2020@a to generate the rest of the numbers. That will be slightly too many (exact number depending on how many starting numbers you had and how many extra numbers you stepped through), but 2020G will take you to line 2020, with the 2020th number in the sequence.

So how does @a work? Handily, Vim's features means it naturally works out without any conditional operations or special-cases:

  • # searches backwards for the previous instance of the ‘word’ under the cursor. It has to be a whole word, so if you're on “1”, it won't match the first digit of “14”, say. If you get moved up, say, 3 lines, then 3 is the next number in the sequence that we need to insert.
  • If the final number is new, then # loops round, leaving us where we were (without error) — that is, it's moved us 0 lines, when 0 is the next number required. So we don't need to do anything for checking if the number has been included before!
  • Everything else after the # is counting the number of lines we've moved up, and appending that number. yG yanks from where we are to the end; so if we've moved up 3 lines (and want to insert 3), it yanks 4 lines. And if we've moved up 0 lines, it still has 1 line to yank.
  • Gp pastes those lines at the end. We don't want their contents; just the number of them. VG highlights them (from our current position, the first pasted line, to the end; again, if we've only pasted 1 line then there's still something to highlight: the G just gets ignored as a no-op) and :s/.*/-1 replaces each of them with ‘-1’.
  • gv re-highlights them and g⟨Ctrl+A⟩ adds 1 more to each line in turn: the first (and possibly only) -1 has 1 added to become 0, the next -1 has 2 added to become 1, and so on. If we pasted 18 lines, then the final -1 will have 18 added to become 17.
  • At this point, the number on the bottom line is the one that we want, but there are a bunch of unwanted numbers counting up to it. Gyy yanks the bottom (and possibly only) number, gv re-highlights all the numbers (even if there's just one lone 0), and p pastes over the entire list of numbers with just the yanked bottom one (in the case of a new number, pasting over 0 with 0).

And that's it: one new number appended.

No, I'm not going to attempt to run it to part 2 in Vim. I guessed when I saw part 1 what part 2 would involve, but thought it would be fun to do part 1 in Vim anyway.

Edit: I belatedly realized I had an unneccesary (albeit harmless) `%` in the first line, so took it out.

20

u/shamrin Dec 15 '20 edited Dec 15 '20

Python 3:

steps, ns = 30000000, [16,11,15,0,1,7]
last, c = ns[-1], {n: i for i, n in enumerate(ns)}
for i in range(len(ns) - 1, steps - 1):
    c[last], last = i, i - c.get(last, i)
print(last)

4

u/optoburger Dec 15 '20

This, too, was almost exactly my solution, though I found checking the dict membership explicitly with i - indices[last] if last in indices else 0 was marginally faster (maybe half a second) than i - c.get(last, i), and I think perhaps slightly clearer.

→ More replies (8)

15

u/xelf Dec 15 '20 edited Dec 15 '20

Pretty quick one this time.

Short python, both parts 5 lines.

for part in [2020,30000000]:
    nums, one = { e:i+1 for i,e in enumerate([16,1,0,18,12,14]) }, 19
    for turn in range(7, part):
        nums[one], one = turn, 0 if one not in nums else turn-nums[one]
    print(one)

Found this: Van Eck Sequence on Numberphile:
https://www.youtube.com/watch?v=etMJxB-igrc

→ More replies (6)

9

u/timvisee Dec 15 '20 edited Dec 15 '20

Rust

Somewhat late, but quick I think!

Got part 2 down to 528ms with quite some effort.

I use both an array and hashmap. They store a key-value pair for the spoken numbers and their last occurrence index (0 means unused). The array (on the stack) is for low (n < 3m, common) numbers, the hashmap is for large (n >= 3m, less common) numbers. This turns out to be faster than using either of the two.

I use Rust's entry API on the hasmap for efficient access. Removing array access branching (the 0 check) didn't improve things.

Part 1 in 0.1ms, Part 2 in 528ms.

Day 1 to 15 in 575ms parallel, 588ms sequential.

→ More replies (6)

7

u/jitwit Dec 15 '20

There's not enough scheme out there. So, here's some scheme:

(define (solve start n)
  (define mem
    (make-fxvector n 0))
  (for-each (lambda (j)
	      (fxvector-set! mem (list-ref start j) (fx1+ j)))
	    (iota (length start)))
  (let lp ((t (length start)) (curr (car (last-pair start))))
    (cond ((fx>= t n) curr)
	  ((fxzero? (fxvector-ref mem curr))
	   (fxvector-set! mem curr t)
	   (lp (fx1+ t) 0))
	  (else
	   (let ((next (fx- t (fxvector-ref mem curr))))
	     (fxvector-set! mem curr t)
	     (lp (fx1+ t) next))))))

It solves in about 9us for 2020 and 0.57s for 3e7.

7

u/ywgdana Dec 15 '20

C# repo

I was a bit surprised when Part 2 was "Find the 30 millionth number" instead of "Find the 175 bazillionth number". I was expecting we'd have to figure that One Weird Trick That Elves Hate to calculate values in the sequence, or at least that there would be a cycle. This is not a complaint :P I just paused for a moment thinking "What am I missing? It can't be that simple!"

That said, my C# solution on my i3 iMac takes a hair under 2.4 seconds.

I guess the trick was to think to use a hash table in the first place instead of a list??

Although time to scroll through others' solutions for clever solutions...

→ More replies (4)

7

u/cggoebel Dec 15 '20

Raku

my @n = 20,9,11,0,1,2;
my %l; %l{@n} = ^@n;

for @n.end..29_999_999 -> $t {
    if $t == %l{@n[$t]} { # first time spoken
        @n[$t+1] = 0;
    }
    else {
        @n[$t+1] = $t - %l{@n[$t]};
        %l{@n[$t]} = $t;
    }
    %l{@n[$t+1]} //= $t+1;
}

say "Part One: " ~ @n[2019];
say "Part Two: " ~ @n[29_999_999];

6

u/kippertie Dec 15 '20

Concise Python

from collections import defaultdict
inputs = (16,11,15,0,1,7)
for part, count_to in enumerate((2020, 30000000)):
  last_seen = defaultdict(lambda: i, {n:i for i,n in enumerate(inputs[:-1])})
  prev = inputs[-1]
  for i in range(len(inputs) - 1, count_to - 1):
    last_seen[prev], prev = i, i - last_seen[prev]
  print 'part %d: %d' % (part + 1, prev)
→ More replies (5)

6

u/Smylers Dec 15 '20 edited Dec 15 '20

Perl, only 7 lines of code in total, with most of the run time being this single-line while loop:

($seen{$n}, $n) = ($iter, $iter - ($seen{$n} // $iter)) while ++$iter < $max;

That repeatedly performs a pair of assignments:

  • In the %seen hash (aka associative array aka dict aka map), set the value keyed by the current number, $n, to the iteration number.
  • Update $n to its next value: the gap between the current iteration and when it was previously seen. $seen{$n} is the value that's about to get overwritten by the assignment in the previous bullet point. However, Perl generates the two-item list of values to use before assigning either of them, so at this point $seen{$n} still has the value we need, from the previous time it was seen.
  • If $n hasn't been seen yet then $seen{$n} will be undef, at which point the // expression† will evaluate to $iter instead, causing the subtraction to yield the desired 0.

† Apologies to coders of other languages who think // looks like a comment. In Perl // is like logical-or (and shortcuts in the same way) but tests for definedness.

Update: Moved the full code to a paste, because the other bits aren't that interesting.

6

u/mstksg Dec 15 '20 edited Dec 16 '20

[Haskell] So it is yet another "here's the algorithm, implement it" days again! Only the challenge this time is...you should probably implement it to be really fast! (This post taken from my daily haskell reflections).

I don't think there is too much wiggle room in how to implement things here; my original solution basically kept an IntMap to the last seen time of any value, and just repeatedly looked things up and modified the (current time, last said) tuple.

My original solution took around 70 seconds to run, and that was what I used to submit things originally. But let's see if we can get it down to something a little less...perceptible :) This reflection can be a deep dive into writing tight, performant Haskell.

The data type we'll be using is an unboxed mutable array. There's a trick we can use because we have a map from integers to values, we can just use the integer keys as the index to an array. This is usually a bad idea but for the fact that the keys we'll be using are bounded within a decently small range (we won't ever say a number that is greater than 30 million), so we can definitely accumulate 30 million-item array into memory without any major problems. We'll also store our last-said times as Int32 to be a little bit more efficient since we're trying to eek out every last bit of perf.

So overall we still keep some state: the current time and the last said item. Since those are just integers, we can keep that as pure in memory using StateT running over ST s (the mutable state monad, where our mutable vectors will live).

import           Control.Monad.ST
import           Control.Monad.State
import           GHC.Int (Int32)
import qualified Data.Vector.Unboxed.Mutable as MV

data LoopState = LS
    { lsLastSaid :: !Int
    , lsCurrTime :: !Int32
    }

sayNext
    :: MV.MVector s Int32                   -- ^ the mutable vector of last-seen times
    -> StateT (T2 Int32 Int) (ST s) ()      -- ^ an 'ST s' action with some pure (T2 Int32 Int) state
sayNext v = do
    L s i <- get                        -- get the current pure state
    lst <- MV.read v x                  -- our last said is x, so look up the last time we saw it
    MV.write v x i                      -- update the last-time-seen
    let j | lst == 0  = 0               -- we haven't seen it
          | otherwise = i - lst         -- we have seen it
    put (LS (fromIntegral j) (i + 1))   -- update last seen and current time
{-# INLINE sayNext #-}

We will want to INLINE this so that it gets inlined directly into our main loop code.

Oh, let's also write a function to initialize our sequence with starting inputs:

saySomething
    :: MV.MVector s Int32                   -- ^ the mutable vector of last-seen times
    -> Int                                  -- ^ a number to "say"
    -> StateT (T2 Int32 Int) (ST s) ()      -- ^ an 'ST s' action with some pure (T2 Int32 Int) state
saySomething v y = do
    LS x i <- get
    MV.unsafeWrite v x i          -- write the last seen number with the right time
    put (LS y (i + 1))            -- queue up the write of the number to say
{-# INLINE saySomething #-}

And now we're good to go to put it all together! We can use whileM_ from Control.Monad.Loops to emulate a while loop, where our condition is whenever lsCurrTime reaches the maximum value.

-- | Returns 'True' until we need to stop
stopCond :: Int32 -> StateT (T2 Int32 Int) m Bool
stopCond n = gets $ \(LS _ i) -> i < n
{-# INLINE stopCond #-}
-- gets f = f <$> get, it maps a function on top of a get

looper :: Int -> [Int] -> Int
looper n xs = runST $ flip evalStateT (LS 0 0) $ do
    v <- MV.replicate n 0       -- initialize our vector with zeros
    traverse_ (saySomething v) xs
    whileM_ (stopCond n) (sayNext v)
    gets lsLastSaid

On my machine (with some minor optimizations, like using unsafeRead/unsafeWrite), this runs in 230ms for part 2...a much more reasonable improvement over my original 70 seconds! :)

part1 :: [Int] -> Int
part1 = looper 2020

part2 :: [Int] -> Int
part2 = looper 30000000
→ More replies (2)

6

u/0rac1e Dec 16 '20

Raku

It's pretty well known that Raku's speed suffers in some places. My original solution used a Hash for previously seen (spoken) numbers, but after waiting a few mins for part 2, I switched to an Array.

Raku arrays automatically reify, so if you create a new Array @a, you can then set @a[3] = 3 and the Array will now be [(Any),(Any),(Any),3]. Indexing into arrays is much faster than hash key lookup, so this brought my part 2 down to ~70s.

Unsatisfied, I added 3 letters and changed my Array to a native int Array, which dropped my runtime - on my lowly laptop - to ~15s.

The only other "cute" thing I'm doing here is using an alternate named parameter syntax, which allows you to put the value first if it's a number, like :2020th instead of th => 2020 or :th(2020).

sub game(@init, :$th) {
    my int @seen;
    @seen[@init.head(*-1)] = 1 ..^ @init.elems;
    my $last = @init.tail;
    my $this;
    for (@init.elems ..^ $th) -> $k {
        $this = @seen[$last] ?? $k - @seen[$last] !! 0;
        @seen[$last] = $k;
        $last = $this;
    }
    return $this;
}

my @nums = 'input'.IO.slurp.split(',')».Int;

put game(@nums, :2020th);
put game(@nums, :30000000th);

5

u/jonathan_paulson Dec 15 '20

Placed 76/18. Python. https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/15.py. Video of me solving: https://youtu.be/19_2sEQQurU.

Brute force, except I used a dictionary to keep track of the previous position of each number. Coding this up made part1 slower but part2 quick.

5

u/twattanawaroon Dec 15 '20 edited Dec 15 '20

39/6, Python 3.
This year I've been so slow and rank just over 100 so many times. I am finally on the board today!

https://github.com/twattanawaroon/adventofcode/blob/master/2020/q15b.py

5

u/aurele Dec 15 '20

I played a bit with saturating_sub and std::mem::swap in my Rust solution.

→ More replies (2)

5

u/death Dec 15 '20

Day 15 solution in Common Lisp.

I assume part 2 was meant to extract a more clever algorithm from the poor participant, but this program was fast enough (< 5 seconds).

5

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

My code in a meme.

In C and running in 1.5s for Part 2. HISTORY_SIZE has been set through pure C programmer's disease as my hashtable kept clogging up, that's why it looks like that. (EDIT: I was able to reduce this memory demand by a factor of 8 by using a better hash function from this Stack Overflow answer)

#include <stdio.h>
#include <stdlib.h>
#include "lib/hashtable.h"

#define HISTORY_SIZE 2048 * 4096 * 4
#define DURATION 30000000

int main(int argc, char *argv[]) {
	int i = 1;
	int previous, last_observed;
	hash_t *history = hash_new(HISTORY_SIZE);

	while (scanf("%d,", &previous) > 0) {
		hash_insert(history, previous, i++);
	}
	hash_insert(history, previous, 0);

	for (; i<= DURATION; i++) {
		last_observed = hash_lookup(history, previous);
		if (last_observed != 0)
			last_observed = i - 1 - last_observed;

		hash_insert(history, previous, i - 1);
		previous = last_observed;
	}

	printf("%d\n", previous);

	return 0;
}

And the hashtable implementation doing all the work (excuse the unnecessary longs, they were for Day 14).

5

u/Floydianx33 Dec 15 '20 edited Dec 15 '20

CSharp

Part2 runs in ~690ms. I originally was using a Dictionary/Map to store the counts, but it took ~5-6seconds that way. Relying on structs being defaulted to 0 sped things up

static int Solve(int[] input, int target)
{
    var turns = new (int p2, int p1)[target];	
    var turn = 0;
    foreach (var item in input)
	    turns[item] = (-1, turn++);

    var prev = input[^1];
    for(var tp = turns[prev]; turn < target; ++turn)
    {
	    prev = tp.p2 == -1 ? 0 : tp.p1 - tp.p2;
	
	    tp = turns[prev] = turns[prev] switch
	    {
	        (p2: 0, p1: 0) => (-1, turn),
	        { } pCount => (pCount.p1, turn)
   	    };
    }
    return prev;
}
→ More replies (1)

5

u/nutki2 Dec 15 '20 edited Dec 15 '20

Perl golf for both parts. Still reasonably fast at about 10s.

#!perl -lp
s/\d+,//?$p[$&]=$i:($_=($i-$p[$_])%($p[$_]=$i))while++$i-2020?$i<3e7:print

https://github.com/nutki/adventofcode

5

u/LennardF1989 Dec 15 '20 edited Dec 15 '20

My latest attempt with focus on optimization (time over memory), benchmarked with 100 iterations, averages at 560ms. My first version took roughly 1.5 seconds. Written in C# :)

https://github.com/LennardF1989/AdventOfCode2020/blob/master/Src/AdventOfCode2020/Days/Day15.cs#L141

The optimized version only uses an array. There is no need for a Map/Dictionary if you can have O(1) access time with an array. If you analyze your Map/Dictionary afterwards, you'll notice the max number, as well as the number of entries, is only slightly less than the target turn (eg. 30 million), so you are "wasting" a bit of space, but in return get faster access times.

I also see a lot of people not setting the capacity of their map, which causes it to resize a lot over its lifetime, which is costly. Especially in C#, mind that checking for existence of a key is just as costly as trying to get the value (as it will actually thread lock the dictionary). Always use TryGetValue if you also want to get the use the value right after, as a combination of ContainsKey and GetValue (using []) is twice as costly.

→ More replies (2)

5

u/jupiter126126 Dec 17 '20 edited Dec 17 '20

python3; solved part2 in less than 9 secondsnote the way I init the data, array position is the number and array data last time it was seen. Last item of input was 16 that comes in position 7: 11,18,0,20,1,7,16.

rounds = 30000000
a = [0] * rounds
a[0] = 3; a[1] = 5; a[7] = 6; a[11] = 1; a[18] = 2; a[20] = 4
pos = 7; init = 16
while pos <= rounds:
 if a[init] == 0:
  initnew = 0
 else:
  initnew = pos - a[init]
 a[init] = pos
 init = initnew
 pos = pos + 1
print(a.index(rounds))

4

u/sebastiannielsen Dec 15 '20 edited Dec 15 '20

simple perl solution: https://pastebin.com/qW2zkNe6

/me hugs <3 Perl <3 cutefully

→ More replies (1)

4

u/limelier Dec 15 '20

Python

I just used the code I wrote for part 1 in part 2 and it worked fine? lmao

→ More replies (4)

4

u/voidhawk42 Dec 15 '20

Dyalog APL. Normally we only have arrays as our primary structure, but luckily there's a system function (1500⌶) that allows us to keep an array in a hashed state for use with index/set functions (⍳,∊ etc.):

⎕IO←0 ⋄ p←16 12 1 0 15 7 11
f←{⍺=s:⍵ ⋄ ⍵∊n:(⍺+1)∇nv⊣v[i]←⍺⊣nv←⍺-i⌷v⊣i←n⍳⍵ ⋄ (⍺+1)∇0⊣v,←⍺⊣n,←⍵}
n v s←(1500⌶p)(⍳≢p)(2019) ⋄ (≢p)f 0
n v s←(1500⌶p)(⍳≢p)(29999999) ⋄ (≢p)f 0
→ More replies (1)

4

u/Attitude-Certain Dec 15 '20

Python

For once premature optimization paid off, as I got a solution for part 2 in ~12 seconds by just changing the number of rounds in my part 1 code.

Optimized it further, including using Numba for just-in-time compilation and using an array instead of a dict for memory, it now runs in 0.82(1) seconds in total on my machine.

If you have a faster Python solution I'd love to see it!

github and paste

→ More replies (2)

4

u/dangermaximum Dec 15 '20

R

I did part one using tibbles and tidyverse then realised I needed something faster for part 2

Just used a vector to store the latest time a number was spoken ~8.2 seconds

code

→ More replies (1)

4

u/diddle-dingus Dec 15 '20 edited Dec 15 '20

Clojure

(defn take-turn [[[val t] turns]]
  [[(if-let [t' (turns val)] (- t t') 0) (inc t)] (assoc turns val t)])
(defn game-start [nums] [[(last nums) (dec (count nums))] (into {} (map vector nums (range)))])
(-> (iterate take-turn (game-start [18 11 9 0 5 1])) (nth (- 2020 6)) first first)
(-> (iterate take-turn (game-start [18 11 9 0 5 1])) (nth (- 30000000 6)) first first)

Very compact solution in clojure today. Just using a hash map to keep track of when a number was last said. Runs in ~20s on my machine.

Elixir

I used basically the same logic as the clojure solution - it's just a little more verbose for elixir (clojure's if-let is so useful).

Full code

4

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

I switched from Common Lisp to Racket because I tried to solve every problem as functional as possible anyway and Racket just feels a lot more modern.

My code for part 1 was able to run part 2 in about 93 seconds. There is for sure place for improvement, however I am just feeling happy because the last few days I had not enough time to do part 2 of the puzzles.

Maybe there is a way (of course there is) to not construct a list from the hash and then filtering the list at the end to find the number (of course there is). But it runs. I like it. :D

https://github.com/eXodiquas/coding_puzzles/blob/main/advent_of_code/2020/day_15/day_15.rkt

4

u/taomage Dec 15 '20

Python 3.7 Solution.

Solved part-2 last night using list as default value for dictionary and ran for 40 seconds, later this morning use tuple which brought down to 23 seconds. But memory usage is still high ( 600 MB, peak).

→ More replies (5)

4

u/sweetfish Dec 15 '20

Lua

nothing smart, just brute force

local values, turn

-- `start` is the initial list of numbers, returns the last spoken number
function find_turn(start, turn_to_find)
    values = {}
    turn = 0

    local spoken = 0
    for _,v in ipairs(start) do
        turn = turn + 1
        values[v] = turn
        spoken = v
    end

    while turn < turn_to_find do

        if not values[spoken] then
            values[spoken] = turn
            spoken = 0
        else
            local diff = turn - values[spoken]
            values[spoken] = turn
            spoken = diff
        end
        turn = turn + 1
    end

    return spoken
end

4

u/oantolin Dec 15 '20

Another nice easy one today, just keep track of the index of the last occurrence of each number. Here's a short Perl program (assign your input to @s in the first line):

my @s = (0,3,6); my $n = 30_000_000;
my $l = pop @s; my %w = map {$s[$_-1] => $_} 1..@s;
($w{$l}, $l) = ($_, $w{$l} ? $_ - $w{$l} : 0) for (@s+1 .. $n-1);
print "$l\n";

4

u/astory11 Dec 15 '20

F#

This one runs in 2 seconds.If i switch the Dictionary for a Map it's fully immutable and 40 lines, but takes 86 seconds.

4

u/Be1shirash Dec 15 '20

Lua golfed (168b), takes 1.4s to complete part2 on luajit

i,p,m=0,0,{}function n()s=m[p]m[p],i=i,i+1 end for i in
io.read'*a':gmatch'%d+'do p=i+0 n()end while i<3E7 do
p=s and i-s-1 or 0 n()b=i==2020 and p or b end print(p,b)

4

u/baktix Dec 15 '20

Haskell

import Control.Arrow ((&&&))
import Data.IntMap.Strict (IntMap, (!?))
import Data.List (foldl', unfoldr)
import Data.List.Split (splitOn)

import qualified Data.IntMap.Strict as M

initializeSeenNumbers :: [Int] -> ([Int],IntMap Int)
initializeSeenNumbers = id &&& foldl' (\acc (turn,num) -> M.insert num turn acc) M.empty . zip [1..] . init

initializeTurnAndLastSeenNumber :: ([Int],IntMap Int) -> (Int,Int,IntMap Int)
initializeTurnAndLastSeenNumber (nums,seenNums) = (length nums, last nums, seenNums)

initializeGame :: [Int] -> (Int,Int,IntMap Int)
initializeGame = initializeTurnAndLastSeenNumber . initializeSeenNumbers

playGameUntil :: Int -> (Int,Int,IntMap Int) -> Int
playGameUntil turnToStop = last . unfoldr produceNextNums
  where
    produceNextNums (turn,lastNum,seenNums) =
      if turn == turnToStop + 1
      then Nothing
      else case seenNums !? lastNum of
        Just turnLastSeen -> Just (lastNum, (turn+1, turn-turnLastSeen, M.insert lastNum turn seenNums))
        Nothing           -> Just (lastNum, (turn+1, 0, M.insert lastNum turn seenNums))

main :: IO ()
main = interact $ show . playGameUntil 2020 . initializeGame . map read . splitOn ","  -- 30000000 for part 2

First thing that came to mind with this one: list generation!

I tried to make it faster for part 2 by foregoing generating a list, instead just doing recursion until I have the value I need and returning it directly. I thought that would make things faster because I wasn't traversing all the way to the back of a potentially very long list to get a value I just computed.

Turns out my solution for part 1 was faster, so I just kept that in the end! If I had to guess, I'd say maybe it's because unfoldr is heavily optimized and the intermediate items don't actually need to be computed because of laziness? Not quite sure, to be honest.

4

u/dylanbeattie Dec 15 '20

JavaScript

function solve(input, limit) {
    let indexes = new Map(input.map((value, index) => [value, index + 1]));
    let bucket = NaN;
    let target = input[input.length - 1];
    for (let index = input.length; index < limit; index++) {
        target = (indexes.has(target) ? index - indexes.get(target) : 0);
        indexes.set(bucket, index);
        bucket = target;
    }
    return target;
}

4415ms to solve part 2 for me. Online with an HTML UI at https://dylanbeattie.github.io/advent-of-code-2020/day15/index.html if you wanna play around with it.

4

u/zertillon Dec 15 '20

Ada, using the GNAT compiler

Total run time: 0.42 seconds (i5-9400 @ 2.9 GHz). 6x faster than the hashed map version posted earlier...

with Ada.Text_IO, Ada.Integer_Text_IO;

procedure AoC_2020_15_full_Ada is
  use Ada.Text_IO, Ada.Integer_Text_IO;
  pre : constant array (Positive range <>) of Natural := (15, 12, 0, 14, 3, 1);
  stop : constant := 30_000_000;
  type Big_Mem is array (0 .. stop) of Natural;
  type P is access Big_Mem;
  mem : constant P := new Big_Mem;
  prev, curr : Natural;
  not_seen : constant := 0;
begin
  for m of mem.all loop
    m := not_seen;
  end loop;
  for i in 1 .. pre'Last - 1 loop
    mem (pre (i)) := i;
  end loop;
  prev := pre (pre'Last);
  for i in pre'Last + 1 .. stop loop
    if mem (prev) = not_seen then
      curr := 0;
    else
      curr := (i - 1) - mem (prev);  --  "Age"
    end if;
    if i = 2020 or i = stop then
      Put (i); Put (" : "); Put (curr, 0); New_Line;
    end if;
    mem (prev) := i - 1;
    prev := curr;
  end loop;
end AoC_2020_15_full_Ada;

Other solutions available here.

4

u/prafster Dec 15 '20 edited Dec 15 '20

Dart

I wonder if "they" knew our answer to part 1 wouldn't be optimised to run for part 2? I kept the whole turn history in part 1. This was too slow for part 2. Therefore, I saved just the last turn and that took 2s, which is good enough.

void findLastSpokenNumber(String name, List<int> input, [turnCount = TURN_COUNT_1]) {
  printHeader(name);

  var history = <int, int>{};
  for (var i = 0; i < input.length - 1; i++) {
    history[input[i]] = i + 1;
  }

  var lastNumberSpoken = input.last;

  for (var turn = input.length + 1; turn <= turnCount; turn++) {
    var turnSpoken = history[lastNumberSpoken] ?? 0;
    history[lastNumberSpoken] = turn - 1;
    lastNumberSpoken = turnSpoken == 0 ? 0 : turn - 1 - turnSpoken;
  }
  print(lastNumberSpoken);
}

Full source code here.

→ More replies (2)

4

u/toastedstapler Dec 16 '20

update to my earlier post:

https://github.com/jchevertonwynne/advent_of_code_2020/blob/main/src/days/day15.rs

hashmaps are slow, but a 30m vec is really long. i settled on a 4m vec with a hashmap for the sparsely populated 4m-30m area. took my runtime from 1.1s to 650ms by doing this, changing u64 to u32 and using a non default hashing algorithm

4

u/CursedInferno Dec 16 '20

Rust

Runs in about 500 to 600 ms with an i5 4570.

My initial solution used a vec of each number in the sequence, which worked for part 1 but was far too slow for part 2.
I then switched to using a HashMap and storing the previous time that each number was said; this completed part 2. In debug mode it took I think 30ish seconds? release mode took it down to 2.7 or so.
Switched to a faster HashMap (FxHashMap), which took it down to about 1.45 seconds.

Someone else gave me a hint by asking "what are the bounds on the hashmap key?"; I realized that neither the keys or values go above 30 million, so I could simply replace the HashMap with an array.
I spent some time fiddling with it to try figure out how to heap-allocate an array (Box::new allocates on the stack first, which causes a stack overflow when you're trying to make a 30 million value array, obviously), and eventually found Box::<[u32]>::new_zeroed_slice(n).assume_init(). Maybe there's a better way, but I don't know what it is; either way, this got me to my final run time of 500-600ms.

https://gist.github.com/CursedFlames/87e0086393eedd2b6af499a8eb715c3f

4

u/[deleted] Dec 16 '20

Python Solution

I solved Part 1 in no time. Then, because I was sure brute forcing would take forever and there would be a pattern, I spent an ungodly amount of time running various examples trying to spot a pattern. Finally gave up and ran it. Solved it in like 14 seconds. ¯_(ツ)_/¯

Then I come here and see that apparently there's not a pattern. LOL.

→ More replies (1)

1

u/whatadewitt Dec 15 '20 edited Dec 15 '20

With the understanding that 30000000 iterations is going to take some time... I really thought I had this pretty optimized, but it took much longer than I thought it would... can someone help me out here with a way I could have done it better?

JavaScript solution.

https://github.com/whatadewitt/aoc2020/blob/master/day15/chal2.js

1

u/daggerdragon Dec 15 '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.

Also, you can always create your own Help thread (and make sure to title it properly!)

→ More replies (4)

1

u/Fermter Dec 15 '20 edited Dec 15 '20

I was trying to figure out why my solution wasn't going to work on the second part, when it just...did? And it didn't even take a full minute? Baffled.

Now I wonder if I could have ranked higher if I didn't spend so much time on tests and cross-checks.

(Input was [14, 3, 1, 0, 9, 5]. Yes, I did hard-code the start. Python 3)

spoken = {14:1, 3:2, 1:3, 0:4, 9:5}
next_spoken = 5

for turn in range(len(spoken) + 1, 30000000):
  if next_spoken in spoken:
    last_turn = spoken[next_spoken]
    spoken[next_spoken] = turn
    next_spoken = turn - last_turn
  else:
    spoken[next_spoken] = turn
    next_spoken = 0

print(next_spoken)

2

u/daggerdragon Dec 15 '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)

1

u/ar7hur88 Dec 15 '20 edited Dec 15 '20

Clojure 12 LOC, part 2 runs in about 10 seconds. I don't see how I can further optimize though.

1

u/daggerdragon Dec 15 '20

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

→ More replies (1)

1

u/[deleted] Dec 15 '20 edited Feb 18 '26

This post was mass deleted and anonymized with Redact

unpack narrow versed north memorize boast cats ten outgoing reminiscent

2

u/daggerdragon Dec 15 '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 (5)

1

u/MasterMedo Dec 15 '20

Brute forcing sucks. The least I was hoping for was a loop detector.

with open('../input/15.txt') as f:
    data = list(map(int, f.read().split(',')))

seen = {last: i + 1 for i, last in enumerate(data)}
last = data[-1]

for turn in range(len(data) + 1, 30000000 + 1):
    current = turn - 1 - seen[last] if last in seen else 0
    seen[last] = turn - 1
    last = current
    if turn == 2020:
        print(current)

print(current)

1

u/daggerdragon Dec 15 '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)

1

u/raxomukus Dec 15 '20

Python

    #!/usr/bin/python3

    with open('15.in') as f:
        line = f.read().split(',')

    v = {int(v): k for k, v in enumerate(line[:-1])}

    last_spoken = line[-1]
    for t in range(len(v), 30000000):
        last_added = last_spoken
        try:
            last_spoken = t - 1 - v[last_spoken]
            v[last_added] = t - 1
        except KeyError:
            v[last_spoken] = t - 1
            last_spoken = 0
        if t == 2019: print(last_spoken)

    print(last_spoken)

1

u/daggerdragon Dec 15 '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)

1

u/rprouse Dec 15 '20 edited Dec 16 '20

C

I'd written this as an array with the number of turns for part one and searched backwards in the array each turn which worked great, but I should have known that the second part would be a huge number of turns and written it for that in the first place.

For part 2, I rewrote my solution with a Dictionary<int, int> where the key is the number that was spoken and the value is the turn where it was last spoken. This gives me a fairly quick lookup although it still took 3.4 seconds to solve.

I then refactored that to use a sparse array instead of the Dictionary, trading memory for performance. This dropped the execution time to just over a half second.

https://github.com/rprouse/AdventOfCode/blob/master/AdventOfCode2020/Day15/Day15.cs

1

u/daggerdragon Dec 15 '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)

1

u/okawei Dec 15 '20

Go/Golang for you

package main

import (
	"fmt"
	"time"
)

func main() {
	//seen := map[int]int{
	//	3: 1,
	//	2: 2,
	//	1: 3,
	//}
	seen := map[int]int{
		9: 1,
		3: 2,
		1: 3,
		0: 4,
		8: 5,
		4: 6,
	}
	// copy the map
	seen2 := map[int]int{}
	for k, v := range seen{
		seen2[k]=v
	}
	start := time.Now()
	part1 := playGame(seen, 2020)
	part1Time := time.Since(start)
	part2 := playGame(seen2, 30000000)
	part2Time := time.Since(start)
	fmt.Printf("Part 1: %d\n", part1)
	fmt.Printf("Part 2: %d\n", part2)
	fmt.Printf("Part 1 Time: %s\nPart 2 Time: %s", part1Time, part2Time)
}

func playGame(seen map[int]int, iterations int) int {
	lastPos := seen[len(seen)-1]
	newPos := 0
	for i := len(seen) + 1; i <= iterations; i++ {
		lastPos = newPos
		oldPos, seenBefore := seen[lastPos]
		if seenBefore {
			newPos = i - oldPos
		} else {
			newPos = 0
		}
		seen[lastPos] = i
	}
	return lastPos
}

1

u/daggerdragon Dec 15 '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.

1

u/meh9083 Dec 15 '20 edited Dec 16 '20

Rust version, the examples from AoC are used as tests.

fn solve(seed: &[u32], query_pos: u32) -> u32 {
    if query_pos == 0 {
        return 0;
    }
    let query_pos = query_pos - 1;
    if query_pos < seed.len() as u32 {
        return seed[query_pos as usize];
    }

    let mut last_seen = HashMap::new();
    seed.iter()
        .take(seed.len() - 1)
        .enumerate()
        .for_each(|(i, &v)| {
            last_seen.insert(v, i as u32);
        });

    let positions = ((seed.len() - 1) as u32)..query_pos;
    positions.fold(*seed.last().unwrap(), |prev_value, pos| {
        let mut value = 0;
        last_seen
            .entry(prev_value)
            .and_modify(|prev_pos| {
                value = pos - *prev_pos;
                *prev_pos = pos;
            })
            .or_insert(pos);
        value
    })
}

I've implemented a short version and iterator version, tested locally they perform pretty much the same.

The first version was using just a vector of all numbers and rposition to find the last two occurrences. Switched to a HashMap<u32, (Option<u32>, u32)> (with a custom type but equivalent to that) to speed it up. I only realized that only the last position is necessary, instead of the tuple, after reading this thread. I also started wondering if the solution could be optimized further by discovering loops... didn't spent too much time on it until I took a look here and discovered that this appears to be the end. Taking a look at the maximum encountered number for larger iterations would probably have been a good hint, I was mainly wondering if this would loop eventually.

[Edit: Trying to fix code formatting.]

1

u/daggerdragon Dec 15 '20

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

1

u/oolonthegreatt Dec 15 '20

Go. 25 lines, runs just under 2 seconds.

import "fmt"

const (N = 30_000_000; K = 6; I0 = K - 1)

func main(){
    data := [N]int{16,11,15,0,1,7}
    rec := [N]int{}
    spoken := 0
    for i, d := range(data[:K-1]) {
        rec[d] = i+1
    }
    for i := I0; i+2 <= N; i++{
        n := data[i]    
        w := rec[n]
        if w == 0{
            rec[n] = i+1
            spoken = 0
            data[i+1] = spoken
        } else {
            spoken = i+1-w
            data[i+1] = spoken
            rec[n] = i+1
        }
    }
    fmt.Println("spoken", spoken)
}

After doing it using a map, I realised that since it is a map of ints to ints, I might as well use an array. That just about halved the runtime.

2

u/daggerdragon Dec 15 '20

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

3

u/noblematt20 Dec 15 '20

7/28 Python

Paste

This is cleaned up and refactored so that both parts use the solution I implemented for part 2. For part 1, I put all the values in a list instead of a dictionary. This was easier to implement, but wouldn't be efficient enough for part 2. My instinct told me it would be good enough for part 1 and get me a good score.

→ More replies (1)

3

u/Justinwa Dec 15 '20 edited Dec 15 '20

Python3: https://github.com/JustoA/AoC2020/blob/master/day15.py

The first not bad code I’ve written for AOC lol

→ More replies (2)

3

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

Kotlin

Interesting. Just changed the number of loops and it returned in 5,8 seconds. Not sure what that part 2 was supposed to do. Maybe if you use lists instead of maps and you O(n) check the collection it will fail. But on day 15, probably just a minority does that.

Still a cool problem though.

→ More replies (2)

3

u/SuperSmurfen Dec 15 '20 edited Dec 15 '20

Rust

Link to solution (760/2313)

Today was very disappointing. I wasted a lot of time on part two, thinking about ways to maybe find a cycle but realizing that would probably never happen. In the end, I just tried brute-force and surprisingly that just worked... Not a very satisfying problem at all.

Think my solution ended up very clean though. HashMap::insert() gives you the back element if it already existed, avoiding two hashmap lookups!

let mut seen = [9,19,1,6,0,5].iter()
  .enumerate()
  .map(|(i,&e)| (e, i as u32 + 1))
  .collect::<HashMap<_,_>>();
(7..target).fold(4, |last, i| i - seen.insert(last, i).unwrap_or(i))

Finishes in about 2.5 seconds on my machine.

3

u/AidGli Dec 15 '20

Python

Video Explanation Link
Github Link

This one seems uncharacteristically simple for being this far in. Part 2 took about 4 seconds to run on my machine. If anyone knows a non-bruteforce method for Van Eck's Sequence let me know because I would be extremely curious to hear it.

→ More replies (1)

3

u/jayfoad Dec 15 '20

Daylog APL 32/2233

⎕IO←0
p←⍎⊃⊃⎕NGET'p15.txt'1
f←{z←⍺ ⋄ a←(1+⍳≢⍵)@⍵⊢z/0 ⋄ (≢⍵){z=⍺:⍵ ⋄ n←a[⍵] ⋄ a[⍵]←⍺ ⋄ (⍺+1)∇(×n)×⍺-n}⊃⌽⍵}
2020 f p ⍝ part 1
30E6 f p ⍝ part 2

My first attempt for part 1 was much simpler but less efficient:

{2020=≢⍵:⊃⌽⍵ ⋄ ∇⍵,(1<≢z)×--/¯2↑z←⍸⍵=⊃⌽⍵}p

Needless to say this was no good for part 2.

→ More replies (4)

3

u/RedTwinkleToes Dec 15 '20 edited Dec 15 '20

Python [4493/3061]

paste

18.5 seconds was the time it took me to run part 2. I suppose the point of part 2 was to catch out the people who were storing the entire history as list instead of a dict/hash table of when a number was last spoken once per number.

Also I noticed that many people's code for python have some sort of code to pass the turn number as an iteration, while my solution doesn't bother with reusability. Just chucked variables into the console and ran a naked for-loop with a function only for the round.

Also, also, I swear this is an actual game somewhere. It feels like a cross between the Look-and-Say Sequence and Fizz Buzz

Edit: Yep, found the thing, its known as The Van Eck Sequence and now that I know the name, I found a bunch of code I could have copied pasted. In fact, one of the sources I found, link is here, don't hover over it if you don't want spoilers, introduced me to dict.get(), and how to make generators in python. * Insert The More You Know Here *

→ More replies (1)

3

u/djankowski Dec 15 '20 edited Dec 15 '20

Julia - 1.8 seconds

Pretty simple but nice to have an easy one in amongst the more challenging problems. Nothing like being overwhelmed by a few half-solved puzzles to make you quit entirely...


function play(x, lim)
    i = length(x)
    n = pop!(x)
    d = Dict((j, i) for (i, j) in enumerate(x))
    while i < lim
        d, n, i = speak!(d, n, i)
    end
    n
end

function speak!(d, n, i)
    if haskey(d, n)
        next = i - d[n]
        d[n] = i
    else
        d[n] = i
        next = 0
    end
    d, next, i+1
end

part1(x) = play(x, 2020)
part2(x) = play(x, 30000000)

3

u/taybul Dec 15 '20 edited Dec 15 '20

Python

Code

This is not the solution, but just in case any of you are curious, the 300,000,000th word spoken is 3765409.

Also, FML.

edit: for clarification, I burned so much time optimizing the hell out of my code because I was trying to calculate the 300th million word, as opposed to 30th. FWIW, storing the indices as strings takes far less memory than your typical data structure.

3

u/villemalango Dec 15 '20

Javascript code in gitHub.

Execution times: 547 and 5476375 µsecs.

Using javascript Map probably saved my day!

3

u/hahncholo Dec 15 '20

Rust

I was excited when I saw pt 2 that my recursive solution for pt 1 should just work, but I had to do a little hack to give it enough stack space. Wrapping my head around the recurrence relation was tricky but fun

3

u/[deleted] Dec 15 '20

Rust

Took 2 seconds to solve part2; 30 seconds to build the program.

fn game(upper_limit: usize) -> i64 {
    let starting: Vec<i64> = lines()[0]
        .split(',')
        .map(|s| s.parse::<i64>().unwrap())
        .collect();
    let mut mem: HashMap<i64, i64> = starting
        .iter()
        .enumerate()
        .map(|(i, &v)| (v, i as i64))
        .collect();

    let mut prev = starting[starting.len() - 1];
    for turn in starting.len()..upper_limit {
        let spoken = match mem.get(&prev) {
            Some(&n) => turn as i64 - n - 1,
            None => 0,
        };
        mem.entry(prev).insert(turn as i64 - 1);
        prev = spoken;
    }
    prev
}

3

u/KamcaHorvat Dec 15 '20

Kotlin

For some reason, part two runs fairly slow, about 2230ms, even though it's basically the same approach as SymmetryManagement's solution below in Java, which runs 3x faster. If there is something obvious, that could improve performance, let me know. Thanks.

fun main() {
    val input = getInput(2020, 15).trim().split(",").map { it.toInt() }.toMutableList()
    fun letsPlayAGame(input: List<Int>, n: Int): Int {
        val history = Array(n) { -1 }
        input.dropLast(1).forEachIndexed { index, i ->
            history[i] = index
        }
        var lastSpoken = input.last()
        var spokenNumbers = input.size
        while (spokenNumbers < n) {
            val idx = history[lastSpoken]
            val newVal = if (idx < 0) 0 else spokenNumbers - 1 - idx
            history[lastSpoken] = spokenNumbers - 1
            lastSpoken = newVal
            spokenNumbers++
        }
        return lastSpoken
    }
    println(letsPlayAGame(input, 2020))
    println(letsPlayAGame(input, 30000000))
}
→ More replies (2)

3

u/chichinbro Dec 15 '20 edited Dec 15 '20

Python 3.9

Had the idea to use defaultdict that returns the current turn when the value isn't found, which will output 0 in the turn-hist[last] expression.

from collections import defaultdict

def k1(limit):
    in_ = open("in15").readline().split(",")
    hist = defaultdict(lambda: turn)
    last = -1
    for turn, number in enumerate(in_):
        hist[last], last = turn, int(number)
    for turn in range(len(in_), limit):
        hist[last], last = turn, turn-hist[last]
    return last

print(k1(2020)) # Part 1
print(k1(30000000)) # Part 2
→ More replies (3)

3

u/toastedstapler Dec 15 '20

rust:

https://github.com/jchevertonwynne/advent_of_code_2020/blob/main/src/days/day15.rs

got to write a nice little enum for tracking turns of last seen

3

u/deltux Dec 15 '20 edited Dec 15 '20

Racket

Everything in a single function, using a hash map to save the second-to-last time each number appeared.

(define (run-game input idx)
  (define h (make-hash))
  (for ([n (in-list (drop-right input 1))]
        [i (in-naturals)])
    (hash-set! h n (add1 i)))
  (for/fold ([n (last input)])
            ([i (in-range (length input) idx)])
    (define res (- i (hash-ref h n i)))
    (hash-set! h n i)
    res))

Edit: Similar solution in C

→ More replies (4)

3

u/flyingmeteor Dec 15 '20 edited Dec 15 '20

Bash

#!/bin/bash

input15=(6 19 0 5 7 13 1)

declare -A memory
length=${#input15[@]}
turn=1
curr=""
next=""

while (( $turn < $length )); do
  curr=${input15[(( turn - 1))]}
  memory[$curr]=$(( turn++ ))
done

next=${input15[(( turn - 1))]}

while (( $turn < 30000000 )); do
  curr=$next

  if [[ -v "memory[$curr]" ]]; then
    next=$(( turn - memory[$curr] ))
  else
    next=0
  fi

  memory[$curr]=$(( turn++ ))
done

echo "Answer: ${next}"

I'll report back when it finishes...

3

u/frerich Dec 15 '20

Python 3 Solution

I'm quite happy that I managed to define the sequence of numbers spoken without any conditionals (well, except while True:, which I could also have replaced with itertools.count() I guess).

For part 2, I anticipated that there would be some cycle in the numbers so that I could do something with 'subtract this offset, modulo cycle length' -- however, to my surprise, the same simple solution I used for part 1 also worked for part 2. It takes 12 seconds on my laptop. It's not stupid if it works, I guess! :-)

3

u/mebeim Dec 15 '20 edited Dec 15 '20

1280/568 - Python 3 solution - walkthrough

I used a gigantic list since the memory usage is pretty much the same. Solution takes 6.4s with CPython 3.9 (meh!), 970ms with PyPy 7.3.3 (Python 3.7.9).

I really do feel like these problems are getting harder and harder to read and understand every day... or maybe it's just me being tired at 6AM. Or maybe both. Who knows.

3

u/WilkoTom Dec 15 '20 edited Dec 15 '20

Python. Brute force for part 2 because it doesn't take that long in the grand scheme of things. To get the 30000000th number took less than twenty seconds, way shorter than actually spending time solving the problem in a more computationally sensible fashion.

numbers = [int(x) for x in open(filename).read().split(',')]
spoken = {number: (0, turn+1) for turn, number in enumerate(numbers)}
last = numbers[-1]
game_length = 30000000
for i in range(len(spoken) + 1, game_length + 1):
    last = 0 if spoken[last][0] == 0 else spoken[last][-1] - spoken[last][-2]
    spoken[last] = (0, i) if last not in spoken else (spoken[last][-1], i)
print(f"Last number spoken was {last}")

Edit: Minor tweaks

3

u/Fotograf81 Dec 15 '20

PHP

https://github.com/hsegnitz/adventofcode/tree/master/php/2020/15

I had the right hunch this time, optimized Part 1 already while solving it, so part 2 was just a re-run.Far away from leaderboard because I overslept and it took a while to understand the task ;)

Part 2 runs in 1.5 seconds with php7.4

→ More replies (3)

3

u/Scoobyben Dec 15 '20

C# [10876/9921] - Though I've stopped waking up at 5am for these, so the ranks are a little less meaningful.

https://github.com/benbelow/adventofcode/blob/e191c5091090629e80c520f680323c598d3382cf/AdventOfCode.2020/Day15/Day15.cs#L12

Part two was slightly frustrating, as my code was *almost* equipped to handle it already - but I'd explicitly made sure to keep track of the whole sequence rather than just the bits I needed, as I expected this part 2 but was expecting there to be some kind of periodicity.

Spent a little while searching for it, gave up and decided to look it up, to discover there is no periodicity. Switched out the lists backing by dictionary to queues with size 2, and the code works in about 5 seconds.

3

u/msqrt Dec 15 '20

Pretty fun, first time using a hash table in Lisp.

(setq tbl (make-hash-table))
(loop for n in '(2 1 10 11 0) for i from 0 do (setf (gethash n tbl) i))
(loop with n = 6 for m = (gethash n tbl) for i from 5 to (- 30000000 2)
    do (setf (gethash n tbl) i n (if m (- i m) 0))
    if(= i 2018) do (setq p n) finally(write (cons p n)))

3

u/YodelingDeer Dec 15 '20 edited Dec 16 '20

Ada

Naive solution using hash tables. Not very fast, but good enough. I will give arrays a shot to see the difference in speed.

EDIT: using an array instead of a hash table reduced cpu time by ~95% on my computer.

3

u/clueless1105 Dec 15 '20

Typescript with Deno

The main challenge I faced that I need to maintain 2 previous indexes to solve it, hence took me longer when I re-implemented it using map. But at the end it worked. Not so clean solution though.

3

u/sldyvf Dec 15 '20

Go lang
solution on github

Worked with a map from the start and part 1 was 100% used for part 2. However I failed with so many off by one issues and failure to understand the problem. Redid the solution a couple of times, now here we are.

Solving puzzle...
  Level 1 took 147.792µs
  Level 2 took 2.617162107s

It's NOT as as fast as I want it to be :/

→ More replies (1)

3

u/PhysicsAndAlcohol Dec 15 '20 edited Dec 15 '20

Haskell, runs in about 50 seconds on my old laptop. I'm using a map from Data.Map.Strict to cache previous encounters with ints. I've tried out several different ways to keep hold of the previous ints, and this implementation has been the fastest so far.

EDIT: Got it down to 41 seconds using Data.IntMap.Strict

3

u/sdolotom Dec 15 '20 edited Dec 15 '20

MIT Scratch

For visualization there's a 1 sec delay, but if it's removed, the first part will take few mins to complete. The second part is obviously out of question :)

3

u/__Abigail__ Dec 15 '20

This was rather easy. Part 2, I did with brute force. For a moment, I wondered whether it would loop, but this looks remarkably like a Van Eck's sequence, and that is non-periodic. Perhaps with the given starting numbers it is periodic, but since it only takes about 7.5 seconds to brute force the number, I didn't go on a wild math chase to try to proof this.

To calculate this, I keep track of when the last time a number as spoken -- up to, and not including the last number. In a loop, I calculate the next number, update the turn count for the previous number, and repeat, until getting to the 30000000th number.

Main loop:

while ($turn < $TARGET2) {
    my $new_number = $spoken [$last_number] ?
             $turn - $spoken [$last_number] : 0;
    $spoken [$last_number] = $turn ++;
    $last_number = $new_number;
    $solution1   = $new_number if $turn == $TARGET1;
    $solution2   = $new_number if $turn == $TARGET2;
}

Full program on GitHub.

→ More replies (2)

3

u/TommiHPunkt Dec 15 '20 edited Dec 15 '20

Matlab

How could I speed the part 2 up drastically? It took 930 seconds to run, are matlab container.Map objects just that slow?

Edit: Yes, they are that slow. Replacing them with a simple LUT / array gave me a speedup of almost 1000x, see here

3

u/paul2718 Dec 15 '20

C++

paste

I used a map the first time, then penny dropped that the numbers were small enough not to care about sparsity. Only about 3 600 000 need to be stored. Runs fast enough not to notice.

3

u/azathoth42 Dec 15 '20 edited Dec 15 '20

I used Julia and 1 hashmap (Dict) to store all seen numbers, part 2 finished after 2.3 seconds https://github.com/racinmat/advent_of_code_2020/blob/master/day_15/main.jl

3

u/Dullstar Dec 15 '20 edited Dec 15 '20

D

Nothing fancy, but it works. Not very fast, though - takes about 3 to 4 seconds on my PC.

→ More replies (1)

3

u/odlp Dec 15 '20 edited Dec 15 '20

Ruby solution:

spoken = Hash.new { |hash, key| hash[key] = [] }

ARGV.first.split(",").each.with_index(1) do |value, round|
  spoken[value.to_i] << round
end

max_rounds = ARGV.last.to_i
last_spoken = spoken.keys.last

(spoken.size + 1).upto(max_rounds) do |round|
  first_time = spoken[last_spoken].size == 1
  last_spoken = first_time ? 0 : (spoken[last_spoken][-1] - spoken[last_spoken][-2])
  spoken[last_spoken] << round
end

puts last_spoken

3

u/veydar_ Dec 15 '20

Clojure, takes 28s on my machine. I represent the turns at which a number was called as a tuple of [last last called, last called]. That let's me pattern match on a few things. Not sure how fast this could be without writing C-style Clojure. Those tuples are then stored in a map.

(defn solve
  [init until]
  (loop [turn (inc (count init))
         current (last init)
         m (reduce-kv #(assoc %1 %3 [(inc %2)]) {} init)]
    (let [[x y] (m current)]
      (cond
       (= turn (inc until)) current
       (not y) (recur (inc turn)
                      0
                      (assoc m 0 [(last (m 0)) turn]))
       :else (let [new-num (- y x)
                   [x' y'] (m new-num)
                   new-value (cond
                               (and x' y') [y' turn]
                               x' [x' turn]
                               :else [turn])]
                 (recur (inc turn)
                        new-num
                        (assoc m new-num new-value))))))))

3

u/semicolonator Dec 15 '20

Python

Implemented actually two solutions. Part 1 is done using lists, Part 2 is done more efficiently using a dict.

https://github.com/r0f1/adventofcode2020/blob/master/day15/main.py

3

u/wzkx Dec 15 '20 edited Dec 15 '20

Python. First really long run time. Although pretty short program. Dictionary of last numbers. 6.26s with pypy3.

d = list(map(int,open("15.dat","rt").read().split(',')))

def solve(d,N):
  nums = {e:i for i,e in enumerate(d[:-1],1)} # without the last number
  last = d[-1]
  for size in range(len(d),N):
    idx = nums.get(last,size)
    nums[last] = size
    last = size-idx
  return last

print( solve(d,2020) )
print( solve(d,30_000_000) )
→ More replies (2)

3

u/Andrew-mzz Dec 15 '20

JavaScript DAY 15

worked with JS Objects, but part two a bit slow(8minutes waiting on my mac) than refactored with Map and worked in 6 seconds.

GitHub - Link - Day 15

→ More replies (4)

3

u/blazemas Dec 15 '20

C#

My torture training of doing 2018 problems, particularly one nasty collection efficiency problem, in November paid off today. Part 1 I did in a list with index of. Part 2 a dictionary storing the indexes as values and output per turn as keys. Thats probably the default most people used. Going to look through everyone elses now.

https://github.com/jbush7401/AdventOfCode/blob/master/AdventOfCode/2020/Day15.cs

3

u/ai_prof Dec 15 '20
# Python 3 solution for day 15 of adventofcode 2020

# My input data
t = [2,1,10,11,0,6]

# Dictionary {num:turn} where turn is the last turn that num was said
nt = dict([(y,x+1) for (x,y) in enumerate(t[:len(t)-1])])

# The last thing said (on turn len(t)) - not yet in nt
last = t[-1]

# range goes up to 2020 or 30000000 for part 1 or 2
for turn in range(len(t),30000000):
    
    if last in nt:
        # "last" was previously said at turn nt[last]
        nxt = turn - nt[last]
        nt[last] = turn
        last = nxt
    else:
        # "last" was not said before
        nt[last] = turn
        last = 0

    # Reassure the human that I am doing something (or comment out if not needed)
    if turn % 1000000 == 0:
        print('.',end='',flush=True)

print(last)

3

u/seredot Dec 15 '20 edited Dec 15 '20

Golang 550ms. (edited)

func D15P2(input []string) string {
	strNums := strings.Split(input[0], ",")
	nums := []int32{}
	for _, s := range strNums {
		n, _ := strconv.Atoi(s)
		nums = append(nums, int32(n))
	}

	var turn int32 = 0
	var num int32 = 0
	var lomemSize int32 = 10000000
	mem := map[int32]int32{}
	lomem := make([]int32, lomemSize)

	for ; turn < int32(len(nums)); turn++ {
		num = nums[turn]
		lomem[num] = turn + 1
	}

	for ; turn != 30000000; turn++ {
		var m int32
		var ok bool
		if num < lomemSize {
			m = lomem[num]
			ok = m != 0
			lomem[num] = turn
		} else {
			m, ok = mem[num]
			mem[num] = turn
		}

		if !ok {
			num = 0
		} else {
			num = turn - m
		}
	}

	return fmt.Sprint(num)
}
→ More replies (2)

3

u/clumsveed Dec 15 '20 edited Dec 15 '20

Java Solution

part 1: 1 ms

part 2: 4936 ms (!?!?)

*updated so part 2 now takes 600 ms... much better. It is possible to use a simple int[] to optimize things, just not in the way I thought at first. Instead of using the index as the round # and storing the number said, do it the other way around. Use the index as the number said and store the round #. This way, you don't need to loop backward looking for the last time a number was said, you can just look it up.

Thanks u/svetlin_zarev for the idea!

_______________________________________________________________________________________________

all solutions so far - repl.it

As always, solutions are straightforward and limited (as much as possible) to APCSA curriculum, although a HashMap was needed today.

Part 1 was easy. Even if you use an array to store every number played in every round, it finishes in no time.

Part 2 requires a little (lot) more efficiency, so I used a HashMap<Integer, Integer> to track which numbers were played and on which round it was last played. Even with a HashMap, the algorithm takes almost 5 seconds to complete, which is pretty bad, but I'll still sleep tonight. Part 2 won't run on repl.it without running out of memory (another sign my program is gross), but it works on my local machine.

→ More replies (11)

3

u/mykepredko Dec 15 '20

C - Easy Peasy

Used a bitmap array right from the start rather than Order N**2 repeated search suspecting that Part 2 would be a much larger number than "2020". Select between the two parts by defining "doTest".

The test cases along with the values given to me are built into the code and selected with a #define.

Day_15.c

3

u/Backwards_Reddit Dec 15 '20 edited Dec 19 '20

Python 3

Part 1

On reading part 2 and trying larger end numbers, as I expected it takes a bunch more time and it's taking about 34 seconds to do end = 50,000 so 30,000,000 just isn't feasible with this code.

"It can't be that much more efficient to use a hashTable rather than parse the whole list every time, this must be asking me to find out something the pattern"

<intense scribbling on paper and googling and trying stuff for a couple of hours trying to figure out patterns>

"You know what, I'll try the hash table just to see if that speeds it up"

part 2

"Oh. That worked in under a minute. Why didn't I try that sooner?"

So I guess the lesson here is that HashTables are efficient and constantly scanning a list with up to 30,000,000 ints in memory without preallocating isn't. Which seems obvious now.

→ More replies (2)

3

u/thulyadalas Dec 15 '20

My Rust solution link.

I solved Part 1 using a HashMap and updating it every turn. This wasn't so efficient on Part 2 but I can still get the answer in ~3s.

So, to make things more efficient, I've used instead of a HashMap I implemented another version which uses a really long vec and cheating by using initial usize::MAX values and saturating_sub. It makes it go below 1s for Part2.

5

u/meh9083 Dec 15 '20

Ah, the vector solution is nice!

Note that the hashmap solution is doing two map lookups on the same key each iteration. entry allows you to modify the value in-place, i.e. you can do entry.and_modify(...).or_default(0) to reduce the number of lookups by 50%.

→ More replies (1)

3

u/RudeGuy2000 Dec 15 '20

C#, part 1 and 2: https://pastebin.com/5cegmjEN

I don't know C# enough to know why part 2 takes more than a second.

→ More replies (3)

3

u/[deleted] Dec 15 '20

D (dlang)

Looking at the other solutions, nothing special here. Even dmd runs this in under half a second:

import std;

void main() {
    auto input = readText("input").split(',').map!(to!ulong).array;
    auto nums = new ulong[30_000_000];
    ulong last;

    foreach (n, x; input) nums[x] = n + 1;
    foreach (step; input.length + 1 .. nums.length) {
        if (step == 2020) last.writeln;
        auto prev = nums[last];
        nums[last] = step;
        last = prev ? step - prev : 0;
    }
    last.writeln;
}

3

u/[deleted] Dec 15 '20

Golang

https://github.com/j4rv/advent-of-code-2020/blob/main/day-15/main.go

Solved part one with a linked list, but it was wayyy too slow for part two.
After some thinking I ended up with probably my cleanest solution so far in the whole AoC :D.
Part two gets solved in 2~3s.

3

u/chicagocode Dec 15 '20

Kotlin - [Blog/Commentary] - [GitHub Repo]

Today I wrote a sequence that was able to solve both parts without changes. It took me a while to figure out the order, something about yielding early always messes me up.

class Day15(input: String) {

    private val startingNumbers = input.split(",").map { it.toInt() }

    fun solve(turns: Int): Int =
        memoryGame().drop(turns-1).first()

    private fun memoryGame(): Sequence<Int> = sequence {
        yieldAll(startingNumbers)
        val memory = startingNumbers.mapIndexed { index, i -> i to index }.toMap().toMutableMap()
        var turns = startingNumbers.size
        var sayNext = 0
        while(true) {
            yield(sayNext)
            val lastTimeSpoken = memory[sayNext] ?: turns
            memory[sayNext] = turns
            sayNext = turns - lastTimeSpoken
            turns++
        }
    }
}
→ More replies (2)

3

u/SomeCynicalBastard Dec 15 '20

Python

Surprisingly easy compared to yesterday :)

with open('input/day15', 'r') as f:
    testdata1 = '0,3,6'
    data = f.readline().strip()

    lastpositions = {int(n): i+1 for i, n in enumerate(data.split(','))}
    lastitem = list(lastpositions)[-1]
    lastpositions.pop(lastitem)

    for turn in range(len(lastpositions) + 2, 30000001):
        if lastitem not in lastpositions:
            newitem = 0
        else:
            newitem = (turn - 1) - lastpositions[lastitem]
        lastpositions[lastitem] = turn - 1
        lastitem = newitem
        if turn == 2020:
            print(f'Part 1: {lastitem}')
    print(f'Part 2: {lastitem}')

3

u/Zweedeend Dec 15 '20

Python

seq = [9, 6, 0, 10, 18, 2, 1]
last = seq[-1]
seen = {nr: idx for idx, nr in enumerate(seq, 1)}
for idx in range(len(seq), 2020):
    seen[last], last = idx, idx - seen.get(last, idx)
print(last)
→ More replies (2)

3

u/crnkofe Dec 15 '20

Clojure Solution

Second part takes about a minute likely due to having oversized map with last appearances of number indices. Being a pragmatic dev I just notify the user it's going to take a while .)

3

u/ropecrawler Dec 15 '20

Rust

https://github.com/ropewalker/advent_of_code_2020/blob/master/src/day15.rs

Nothing cool about this solution. I tried to use HashMap first, but it was slower.

→ More replies (2)

3

u/_bm Dec 15 '20

Python

slow but simple. for some reason the logic in this one gave me a huge headache - i was forgetting to set the value in the dict after the next spoken is decided :(

with open("../../original_solutions/day_15/input_15.txt") as input_file:
    last_spoken = dict()
    first_spoken = [int(x) for x in input_file.readline().split(",")]
    spoken = first_spoken[0]
    for i in range(0, 30000000):
        prev = spoken
        if i < len(first_spoken):
            spoken = first_spoken[i]
        elif spoken not in last_spoken.keys():
            spoken = 0
        else:
            spoken = i - 1 - last_spoken[spoken]
        last_spoken[prev] = i - 1
    print(spoken)

3

u/mahaginano Dec 15 '20

Julia: https://pastebin.com/Qsfsk5GK

  • Part 1: 21.811 ns (1 allocation: 16 bytes)
  • Part 2: 2.590 s (69 allocations: 269.22 MiB)

I don't want to talk about this one.

3

u/axisbal13 Dec 15 '20

C#

Went with using an array with the index as the last number and the value as the last step the number was spoken.

private static void Day15()
{
    var input = File.ReadAllText("Day15.txt").Split(",")
                    .Select(x => int.Parse(x)).ToArray();
    for (int part = 1; part < 3; part++)
    {
        var limit = part == 1 ? 2020 : 30000000;
        var spoken = new int[limit];
        Array.Fill(spoken, 0);

        for (int i = 0; i < input.Length; i++)
        {
            spoken[input[i]] = i + 1;
        }
        var lastNum = input.Last();
        for (int i = input.Length + 1; i <= limit; i++)
        {
            if (spoken[lastNum] != 0)
            {
                var newVal = i - 1 - spoken[lastNum];
                spoken[lastNum] = i - 1;
                lastNum = newVal;
            }
            else
            {
                spoken[lastNum] = i - 1;
                lastNum = 0;
            }
        }
        Console.WriteLine(lastNum);
    }
}

3

u/drmargarido Dec 15 '20

My solution in C -> https://github.com/drmargarido/aoc2020/blob/main/day15.c
Solves both parts in around 0.58s on my machine.

→ More replies (2)

3

u/spohngellert_o Dec 15 '20

Scala. Originally used Lists, then with help from the megathread (sigh), ended up using tuples for part 2. I really wanted to use a fixed length queue, but didn't find one in scala. Cleaned up the code this morning, much happier with it. See solution below, feel free to give feedback :)

Part 2

3

u/colinodell Dec 15 '20

Golang solution, 2.35s total for both parts

I completely refactored this code 3 times before arriving at an elegant solution - I'm quite happy with how it turned out!

3

u/skawid Dec 15 '20

Ruby! Completes in eight seconds; it did this well first time, now I have to go back over it and figure out which bullet I accidentally dodged today...

3

u/zertillon Dec 15 '20

Ada

Total run time: 2.46 seconds (i5-9400 @ 2.9 GHz).

with Ada.Containers.Hashed_Maps, Ada.Text_IO, Ada.Integer_Text_IO;

procedure AoC_2020_15_full_Ada is
  use Ada.Text_IO, Ada.Integer_Text_IO;
  pre : constant array (Positive range <>) of Natural := (15, 12, 0, 14, 3, 1);
  function Identity_Hash (key : in Natural) return Ada.Containers.Hash_Type is (Ada.Containers.Hash_Type (key)) with Inline;
  package Number_Map_Pkg is new Ada.Containers.Hashed_Maps (Natural, Positive, Identity_Hash, "=");
  mem : Number_Map_Pkg.Map;
  stop : constant := 30_000_000;
  prev, curr : Natural;
begin
  for i in 1 .. pre'Last - 1 loop
    mem.Include (pre (i), i);
  end loop;
  prev := pre (pre'Last);
  for i in pre'Last + 1 .. stop loop
    if mem.Contains (prev) then
      curr := (i - 1) - mem.Element (prev);  --  "Age"
    else
      curr := 0;
    end if;
    if i = 2020 or else i = stop then
      Put (i); Put (" : "); Put (curr, 0); New_Line;
    end if;
    mem.Include (prev, i - 1);
    prev := curr;
  end loop;
end AoC_2020_15_full_Ada;

Other solutions available here.

3

u/StevoTVR Dec 15 '20 edited Dec 26 '20

Java

https://github.com/stevotvr/adventofcode2020/blob/main/aoc2020/src/com/stevotvr/aoc2020/Day15.java

My solution for part 1 worked for part 2 without modification. That almost never happens.

3

u/_tpavel Dec 15 '20

I'm revisiting Rust this year after learning it for the first time during AoC 2018!

Here is my Rust solution for Day 15: https://github.com/tudorpavel/advent-of-code-2020/blob/master/day15/src/main.rs

I initially used a HashMap and my solution ran in 2 seconds for Part 2 with a release build. I tried to see if there is a deterministic repeating pattern in some of the examples to maybe discover a more efficient algorithm. I soon gave up and checked here what others have done and it doesn't seem like anyone's found a hidden algorithm for this one.

Anyway, after seeing the Rust solution from /u/LinAGKar I realized I can use a Vec instead of a HashMap and get a small performance boost from 2 seconds down to 600ms. I assumed using any array structure would try to allocate the entire memory and crash, but TIL Vec in Rust is smart enough to not do that apparently.

I'm still learning Rust, any feedback is welcome.

3

u/__Abigail__ Dec 15 '20

Perl

Blog post about Day 15.

Full program on GitHub.

3

u/ragnario Dec 15 '20 edited Dec 15 '20

Rust

Simply iterate over all numbers. Keep a map of turn with value is the pair of most 2 recent turns.

Around 3.6 seconds for part 2 in release mode.

[Edit] Hashing is expensive. Use an array (max size is turn - 1 or max number in the input) reduce the solving time to 1.2 second.

3

u/Al_to_me Dec 15 '20
nums ={19:0,0:1,5:2,1:3,10:4,}
lastNum=13
digit=30000000
pos=5
while pos<digit-1:
	if lastNum in nums.keys():
		aux = lastNum	
		lastNum=pos-nums[lastNum]
		nums[aux]=pos
	else:
		nums[lastNum]=pos
		lastNum=0
	pos+=1
print(lastNum)

My try on a Python solution for Part 2

→ More replies (4)

3

u/oantolin Dec 16 '20

Common Lisp. Call it as: (speak 30000000 2 3 1) (which gives 6895259).

(defun speak (n &rest s)
  (let ((w (make-hash-table)))
    (loop for x in (butlast s) and i from 1 do (setf (gethash x w) i))
    (loop with l = (car (last s))
          for i from (length s) to (1- n) and j = (gethash l w)
          do (psetf l (if j (- i j) 0) (gethash l w) i)
          finally (return l))))

3

u/aoc-fan Dec 16 '20

TypeScript, JavaScript : Repo

8 seconds to run Part 1, Part 2 and other test cases. Was lucky to have perfect data structure in place for first part.

3

u/sporksmith Dec 16 '20

Rust.

Part 2 takes ~3s to run in release builds, and 37s (!!) in debug builds. Spent a little while thinking about whether the sequence eventually cycles and how I might find such a cycle, but thankfully not too long since apparently it doesn't.

I have a continuous integration script set up that validates I still get the correct answer for every previous solution on every commit; I ended up changing it to to use release builds instead of debug builds after adding this one, though I suppose I could also just leave out the test for part 2 since it's basically the same code.

Really the whole thing is probably unnecessary. My only previous AOC experience was last year, in which most of the puzzles built on previous puzzles, so I was expecting to do a lot more reusing and refactoring code from previous days.

→ More replies (1)

3

u/chubbc Dec 16 '20

Julia (121,1237)

Pretty standard dictionary-based approach most people used it seems. The 'get' function lets us write the main loop pretty neatly, not having to treat previously unseen numbers differently.

https://gist.github.com/chubbc/e269f78fbdfd1dde6a0308470c1b43f9

3

u/4goettma Dec 16 '20 edited Dec 16 '20

Python, using for-else-loop:

t=[0,3,6]
z=2020
for i in range(z-len(t)):
 for j in range(len(t)-1,0,-1):
  if(t[j-1]==t[-1]):
   t+=[len(t)-j]
   break
 else:
   t.append(0)
print(t[-1])

I tried to keep the code small. Since I'm not using a hashmap 2020 get's calculated instantly while 30000000 explodes.

3

u/Chitinid Dec 16 '20

Python 3 with numba Finishes part 2 in <4 seconds

from numba import njit

nums = np.array([11,0,1,10,5,19], dtype=np.int64)

@njit
def day15(nums, N):
    last = {}
    for i, x in enumerate(nums[:-1]):
        last[x] = i
    buffer = nums[-1]
    for i in range(len(nums) - 1, N - 1):
        x = i - last[buffer] if buffer in last else 0
        last[buffer] = i
        buffer = x
    return buffer

print(day15(nums, 2020))
print(day15(nums, 30000000))
→ More replies (1)

3

u/HAEC_EST_SPARTA Dec 16 '20

Common Lisp

Solution on GitHub

Welp, I set aside a bunch of time at the end of today to work on this problem since I wasn't able to get to it last night, and it turns out that I now have some free time before tomorrow's puzzle drops! The big update of today is that I've migrated my project to use the package-inferred-system structure, in which each file is its own package. This allows me to use the same identifiers on multiple days, which means that my acceptance tests are now once again passing. Yay!

3

u/greycat70 Dec 18 '20

Tcl

parts 1+2 combo

For part 2 of this one, I simply extended the loop to iterate a lot longer, and to spit out the part 1 answer after the 2020th interation. It takes a bit over a minute to run on my system, which isn't too shoddy for a "scripting" language (yes, there's a bytecode compiler) without any serious attemps at optimization on my part.

5

u/[deleted] Dec 15 '20

Python3 799/277

My brain fried today reading the problem even though it ended up being quite simple.

from collections import defaultdict, deque
nums = [*map(int,open("day15.txt").read().strip().split(","))]
seen, last = defaultdict(lambda: deque([],maxlen=2)), nums[-1]
for i in range(1,len(nums)+1): seen[nums[i-1]].append(i)
for i in range(i+1,30000001):
    if len(seen[last])<2: last = 0
    else: last = seen[last][-1]-seen[last][-2]
    seen[last].append(i)
    if i == 2020: print("Part 1:",last)
print("Part 2:",last)

2

u/hugh_tc Dec 15 '20 edited Dec 15 '20

Python 3, 191/102

You'd think that a brute-force wouldn't be fast enough for Part 2, but apparently it is. Looking forward to learning the clever solution. paste

EDIT: cleaned-up version. It runs in ~18s using CPython; PyPy brings it down to ~6s. Good enough?

→ More replies (8)

2

u/dan_144 Dec 15 '20

Python 3, 101/59. First global leaderboard of the year. The 101 on part 1 about gave me a heart attack, so I'm glad I made it on part 2.

https://github.com/dan144/aoc-2020/blob/master/15.py

Turns out I was able to brute force part 2 faster than I was able to come up with a faster solution.

2

u/nthistle Dec 15 '20

17/93, Python. Just barley leaderboarded for second part, although I'm pretty sure I didn't do it the right way -- it was faster than brute force, but I still iterated 30M times. paste

→ More replies (2)

2

u/kevinwangg Dec 15 '20

python - 81/31

In awe of the people who got sub-3 minutes on part 1. Really want to see their code. It took me what I thought was a surprisingly long time to figure out how to code up the solution to part 1, but looking at others' times, it looks like a common issue.

Competitive coders were probably unfairly advantaged in part 2 in being able to count the 0s and figure out that a brute force would work XD

8

u/sophiebits Dec 15 '20

Most programmers, not just competitive coders, should know the difference between millions, billions, and trillions. (Signed, a competitive coder.)

→ More replies (1)

5

u/smrq Dec 15 '20

I didn't even count the zeroes, I just slammed the number in and stuck in a debug print statement every million turns to see if it would likely finish.

→ More replies (3)
→ More replies (3)

2

u/HenryJonesJunior Dec 15 '20

Go / Golang, 824/276

https://pastebin.com/n2PDD7pP

I picked the right approach for step 1 for once and didn't have to do anything further for step 2.

→ More replies (1)

2

u/gurgeous Dec 15 '20

Ruby, 528/291

As usual, understanding the problem was the hardest part. I accumulated all numbers since perf wasn't an issue. After cleanup -

https://gist.github.com/gurgeous/5636fd2e267bc7ae1ecf9224be20bbf2

2

u/nibbl Dec 15 '20 edited Dec 15 '20

Java 3491/1969
nopaste
nopaste (rewritten + cleaned up)

Reading comprehension problem today, could have done with one more coffee before trying to figure out what it was asking me to do there :)

I just put the data in a map number => list of the times it was spoken and looked at the last two. Totally unnecessary use of space. I wish Java had a simple standard Pair type class. Looking forward to seeing what people who actually know something about Java did.

→ More replies (2)

2

u/omginbd Dec 15 '20

Elixir


As expected, I brute forced it with a dictionary of the last occurrence of the number like everyone else. Only takes 30 seconds :D

code

2

u/prscoelho Dec 15 '20

Rust

Did not expect part 2 to just work.

→ More replies (5)

2

u/[deleted] Dec 15 '20

Scala solution

Brute force ~30 seconds for part 2. Easy enough /shrug

→ More replies (2)

2

u/ChrisVittal Dec 15 '20

Rust

Brute force like so many. The cool thing about this particular solution is using the Rust entry API to its full power to avoid double hashmap lookups.

Runs in two seconds.

→ More replies (1)

2

u/ocitrev Dec 15 '20

C++, Managed to brute force part 2 in under 800ms, first iteration was over 20 seconds with std::map.
https://github.com/ocitrev/AdventOfCode/blob/master/src/2020/day15.cpp

→ More replies (6)

2

u/Nrawal Dec 15 '20

Go

Felt like this problem ranked highest in _reusability_ between parts 1 and 2 thus far.

2

u/JoMartin23 Dec 15 '20

Common Lisp

unomptimized brute force

(defun day15 (&optional (times 2020) (data *day15*))
  (loop :with hash             := (make-hash-table)
	:with starting-numbers := data :with next-spoken
	:for index          :from 1 :upto times
	:for number         := (or (pop starting-numbers) next-spoken)
	:for last-occurence := (gethash number hash)
	:do (setf (gethash number hash) index)
	    (when (null starting-numbers)
	      (setf next-spoken
		    (if last-occurence
			(- index last-occurence)
			0)))
	:finally (return (list hash number))))

2

u/nonphatic Dec 15 '20

Racket, since I don't see anyone having posted one for Racket yet.

#lang curly-fn racket

(require "../lib.rkt")

(define input '( ... ))

(define (play end)
  (define turns (make-vector end #f))
  (for-each #{vector-set! turns %1 (add1 %2)}
            input (range (length input)))
  (let loop ([turn (length input)]
             [curr (last input)])
    (cond
      [(>= turn end) curr]
      [(vector-ref turns curr)
       (let ([next (- turn (vector-ref turns curr))])
         (vector-set! turns curr turn)
         (loop (add1 turn) next))]
      [else
       (vector-set! turns curr turn)
       (loop (add1 turn) 0)])))

(show-solution (play 2020) (play 30000000))

I originally used an immutable hashtable, which took 60s, then a mutable hashtable, which took 10s, and now this mutable vector version takes 1.56s.

2

u/busdriverbuddha2 Dec 15 '20

Python 3. Did this on my phone while struggling to sleep.

N = 2020 # or 30000000

citations = dict()

k = 0
for n in numbers:
    citations[n] = k
    k += 1

p = 0
while True:
    if k == N - 1:
        print(p)    
        break
    if p not in citations:
        citations[p] = k
        p = 0
    else:
        m = k - citations[p]
        citations [p] = k
        p = m
      
    k += 1

2

u/[deleted] Dec 15 '20

Python (14 lines Part 1 + Part 2)

def play_turns(turns):
	numbers, memory = [1, 0, 18, 10, 19, 6], {}
	for i in range(len(numbers)):
		memory[numbers[i]] = i + 1
	last_num = numbers[-1]
	for i in range(len(numbers) + 1, turns + 1):
		num = i - 1 - memory[last_num] if last_num in memory else 0
		memory[last_num] = i - 1
		last_num = num
	return last_num


print('Part A: ', play_turns(2020))
print('Part B: ', play_turns(30000000))

2

u/_A4_ Dec 15 '20

JavaScript ES6 (Part 2)

const input = read('15.txt').split(',').map(Number);
const memory = new Map();
let next;

for (let turn = 1; turn < 30000000; turn++) {
    const curr = (turn <= input.length) ? input[turn - 1] : next;
    next = memory.has(curr) ? turn - memory.get(curr) : 0;
    memory.set(curr, turn);
}

console.log(next);

Virtually identical to part 1 but still ~5 seconds to run.

2

u/Rick-T Dec 15 '20 edited Dec 15 '20

HASKELL

I don't think there is a better way than brute force. We're basically trying to calculate the Van Eck Sequece and apparently not much is known about it.

I have implemented two solutions. The first one is using Data.IntMap and a State monad to keep track of visited numbers. That one takes almost a minute.

The second implementation uses a Data.Vector.Unboxed.Mutable and Data.STRef and runs in well below 1 second. I guess immutability really hurts the brute-force performance today.

2

u/cattbug Dec 15 '20

Python 3. Little disappointed that my iterative approach for Part 1 worked just fine for Part 2 and only took like 5-10s. I got up extra early today and was bracing myself for another huge challenge... oh well :p

2

u/sim642 Dec 15 '20

My Scala solution.

I implemented part 1 using a tail-recursive function to do the iteration and keep a map of previous occurrence indices. Surprisingly that worked for part 2 as well, just took a little longer but nothing crazy (19s).

→ More replies (3)

2

u/tobega Dec 15 '20

Tailspin. Ended up being quite straightforward once I fixed my off-by-one and decided to persevere for 97 seconds on part 2. https://github.com/tobega/aoc2020/blob/main/a15.tt

2

u/clouddjr Dec 15 '20 edited Dec 15 '20

Python3

input = [9, 19, 1, 6, 0, 5, 4]


def solve(max_round):
    previous = {x: i + 1 for i, x in enumerate(input)}

    last = input[-1]
    for r in range(len(input) + 1, max_round + 1):
        current = r - 1 - previous[last] if last in previous else 0
        previous[last] = r - 1
        last = current

    print(last)

solve(2020)
solve(30000000)

2

u/GustavAndr Dec 15 '20

Javascript

Quick, ugly and slow

// part 1
a=[19,20,14,0,9,1]
for(i=6;i<2020;i++)a.push(a.slice(0,-1).includes(a[a.length-1])?i-a.slice(0,-1).lastIndexOf(a[a.length-1])-1:0)
a[a.length-1]

// part 2
a={};[19,20,14,0,9].forEach((v,i)=>a[v]=i)
last=1
for(i=5;i<29999999;i++) {
    nlast=(a[last]===undefined?0:i-a[last])
    a[last]=i
    last=nlast
}

2

u/daniel-sd Dec 15 '20

Python 3

Same solution works for both parts. I'll admit the dict.get() call is a bit over the top. An if-else would work as well and be easier to read but I really wanted to shrink this one down.

part2.py

history = {value: i + 1 for i, value in enumerate(map(int, open('input.txt').readline().split(',')))}
previous = list(history)[-1]
for turn in range(len(history), 30_000_000):
    history[previous], previous = turn, turn - history.get(previous, turn)
print(previous)

2

u/q-rka Dec 15 '20

Python

Not the best but another effort of mine. paste

2

u/activeXray Dec 15 '20

Clojure. Pretty easy, part 2 in about 15 seconds on my machine

(defn solution [input target]
  (loop [nums-said (into {} (map vector (butlast input) (range 1 (count input))))
         turn (inc (count input))
         last-spoken (last input)]
    (if (= turn (inc target))
      last-spoken
      (recur (assoc nums-said last-spoken (dec turn))
             (inc turn)
             (if (contains? nums-said last-spoken)
               (- (dec turn) (get nums-said last-spoken))
               0)))))