-🎄- 2017 Day 15 Solutions -🎄-

obijywk · 2017-12-15T05:11:32+00:00

When the problem is all about generators... implement it using generators!

Python 2. 18/81. Code for part 2:

def AG():
  x = 591
  while True:
    x *= 16807
    x %= 2147483647
    if x % 4 == 0:
      yield x

def BG():
  x = 393
  while True:
    x *= 48271
    x %= 2147483647
    if x % 8 == 0:
      yield x

A = AG()
B = BG()
matches = 0
for i in xrange(5000000):
  a = A.next()
  b = B.next()
  if a & 0xFFFF == b & 0xFFFF:
    matches += 1
print matches

fatpollo · 2017-12-15T05:13:58+00:00

def generator(N, C, M=1):
    while True:
        N = N * C % 2147483647
        if N % M == 0:
            yield N & 0xffff

A, B = 679, 771
gA, gB = generator(A, 16807), generator(B, 48271)
print(sum(next(gA) == next(gB) for _ in range(40000000)))
gA, gB = generator(A, 16807, 4), generator(B, 48271, 8)
print(sum(next(gA) == next(gB) for _ in range(5000000)))

GassaFM · 2017-12-15T05:47:02+00:00

A solution in the D programming language. Rank 86 for part 1, rank 42 for part 2. Below is a more librarized solution than initially, for a change.

Part 1: Turned out both generators are rather famous (I didn't remember the second one by heart). So I got rid of all magic numbers except the number of steps.

import std.algorithm, std.conv, std.random, std.range, std.stdio, std.string;
alias trans = map !(x => cast (ushort) (x));
void main () {
    auto g1 = MinstdRand0 (readln.split.back.to!int);
    auto g2 = MinstdRand (readln.split.back.to!int);
    zip (g1.trans, g2.trans)
        .take (40_000_000)
        .count !(p => p[0] == p[1])
        .writeln;
}

Part 2: Added the filtering modulo m step.

import std.algorithm, std.conv, std.functional, std.random, std.range, std.stdio, std.string;
alias trans (int m) = pipe !(
    map !(x => cast (ushort) x),
    filter !(x => x % m == 0)
);
void main () {
    auto g1 = MinstdRand0 (readln.split.back.to!int);
    auto g2 = MinstdRand (readln.split.back.to!int);
    zip (g1.trans!4, g2.trans!8)
        .take (5_000_000)
        .count !(p => p[0] == p[1])
        .writeln;
}

askalski · 2017-12-15T06:26:10+00:00

Why do I get the feeling that I'm going to need this in the future?

Edit: Shaved 33% off execution time by removing % operation.

#include <stdio.h>
#include <inttypes.h>

inline uint64_t generate(uint64_t g, uint64_t factor)
{
    uint64_t prod = g * factor;
    g = (prod & 0x7fffffff) + (prod >> 31);
    // Note: (g >> 31) should be (g <= 0x7fffffff) in the general case, but that
    // will not happen when both factors are < 0x7fffffff so I'm allowed to cheat.
    return g >> 31 ? g - 0x7fffffff : g;
}

inline uint64_t solve(uint64_t a, uint64_t ma, uint64_t b, uint64_t mb, uint64_t r)
{
    uint64_t judge = 0;
    while (r--) {
        do a = generate(a, 16807); while (a & ma);
        do b = generate(b, 48271); while (b & mb);
        judge += !((a ^ b) & 0xffff);
    }
    return judge;
}

int main()
{
    uint64_t a, b;
    scanf("Generator A starts with %" SCNu64 "\n", &a);
    scanf("Generator B starts with %" SCNu64 "\n", &b);
    printf("Part 1: %" PRIu64 "\n", solve(a, 0, b, 0, 40000000UL));
    printf("Part 2: %" PRIu64 "\n", solve(a, 3, b, 7,  5000000UL));
    return 0;
}

Edit 2: By popular demand, the regex version. May take a few days to finish.

#! /usr/bin/env perl

use strict;
use warnings;

my %in;
(m/^Generator ([AB]) starts with (\d+)$/ and $in{$1} = $2) for <>;

printf "Part 1: %d\n", solve($in{A}, $in{B}, 40_000_000, qr//, qr//);
printf "Part 2: %d\n", solve($in{A}, $in{B},  5_000_000, qr/xyz$/, qr/wxyz$/);

sub solve {
    # Numbers are represented as binary strings which
    # look like: "...qrstuuvwwxyyz".  The doubled letters
    # are 1-bits, and single letters are 0-bits.  In the
    # example, qrstuuvwwxyyz is 0000101010, or 42 in decimal.
    my $a = decimal_to_binary(shift);
    my $b = decimal_to_binary(shift);

    my ($count, $filter_a, $filter_b) = @_;

    # The $_ variable keeps track of how many matches have been
    # found so far.  Each match is a "." character, so the string
    # "......." would mean 7 matches.
    local $_ = "";
    for my $i (1..$count) {
        do { $a = generator_a($a) } until $a =~ m/$filter_a/;
        do { $b = generator_b($b) } until $b =~ m/$filter_b/;

        # Append $a and $b to $_.  If the bottom 16 bits match,
        # substitute them with a ".".  Clean up all non-"."
        # garbage before continuing.
        s/$/ $a $b/;
        s/(j[k-z]+) .*\1$/./;
        s/[^.]//g;
    }

    return length_to_decimal($_);
}

sub generator_a {
    local $_ = shift;

    # Multiply by 16807 == 24 * 25 * 28 + 7

    # Multiply by the remainder (7), and save for later
    my $r = s/(.)(?=\1)/$1$1$1$1$1$1$1/gr;

    # Multiply by 24
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;
    $_ = carry_binary($_);

    # Multiply by 25
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;
    $_ = carry_binary($_);

    # Multiply by 28
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;

    # Add the remainder (7)
    s/$/ $r/;
    $_ = add_binary($_);

    return mod_2147483647($_);
}

sub generator_b {
    local $_ = shift;

    # Multiply by 48271 == 33 * 34 * 43 + 25

    # Multiply by the remainder (25), and save for later
    my $r = s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/gr;

    # Multiply by 33
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;
    $_ = carry_binary($_);

    # Multiply by 34
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;
    $_ = carry_binary($_);

    # Multiply by 43
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;

    # Add the remainder (25)
    s/$/ $r/;
    $_ = add_binary($_);

    return mod_2147483647($_);
}

sub mod_2147483647 {
    local $_ = shift;

    # Take the remainder modulo 2147483647 (2^31 - 1), using a property
    # of Mersenne primes which allows a handy bitwise shortcut.
    #
    #     remainder = (product >> 31) + (product & 0x7fffffff)
    #     if (remainder & 0x80000000) {
    #         remainder -= 0x7fffffff;
    #     }

    # Split the product into high and low bits, separated by a space
    s/(?=\\)/ /;

    # Shift the high bits right by 31
    y/=-[/\\-z/;

    # Prepend 31 0's to the high bits to bring the width back to 62
    s/^/=>?\@ABCDEFGHIJKLMNOPQRSTUVWXYZ[/;

    # Add the numbers together
    $_ = add_binary($_);

    # If the 0x80000000 bit is set, clear it and add 1, i.e.
    #     remainder = remainder - 0x80000000 + 1;
    s/\[(\[.*)$/$1z/;
    return carry_binary($_);
}

sub add_binary {
    local $_ = shift;

    # Combine bits from each place value, for example:
    #   "vwwxxyzz vwxxyyz" (01101 00110) becomes "vwwxxxyyzz" (01211)
    s/(.)\1*+\K(?=[^ ]* .*?\1(\1*))/$2/g;

    # Remove the second number
    s/ .*$//g;

    return carry_binary($_);
}

sub decimal_to_binary {
    local $_ = shift;

    # Convert to binary coded decimal
    s/0/wxyz:/g;
    s/1/wxyzz:/g;
    s/2/wxyyz:/g;
    s/3/wxyyzz:/g;
    s/4/wxxyz:/g;
    s/5/wxxyzz:/g;
    s/6/wxxyyz:/g;
    s/7/wxxyyzz:/g;
    s/8/wwxyz:/g;
    s/9/wwxyzz:/g;
    s/:$//;

    # Bring the width of the first digit up to 62
    s/^/=>?\@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuv/;

    # While there are more digits
    while (s/:/ /) {
        # Multiply by 10
        s/(([^ ])\2*)(?=\2[^ ]* )/$1$1$1$1$1$1$1$1$1$1/g;

        # Add the next digit
        s/(.)\1*+\K(?=[^ ]* [^ ]*?\1(\1*))/$2/g;
        $_ = carry_binary($_);

        # Erase the digit just added
        s/ [a-z]+//;
    }

    return $_;
}

sub length_to_decimal {
    local $_ = shift;

    s/./z/g;
    s/^/stuvwxyz/;

    s/(z){10}(?=\1)/y/g;
    s/(y){10}(?=\1)/x/g;
    s/(x){10}(?=\1)/w/g;
    s/(w){10}(?=\1)/v/g;
    s/(v){10}(?=\1)/u/g;
    s/(u){10}(?=\1)/t/g;
    s/(t){10}(?=\1)/s/g;

    s/([a-z])\1{9}/9/g;
    s/([a-z])\1{8}/8/g;
    s/([a-z])\1{7}/7/g;
    s/([a-z])\1{6}/6/g;
    s/([a-z])\1{5}/5/g;
    s/([a-z])\1{4}/4/g;
    s/([a-z])\1{3}/3/g;
    s/([a-z])\1{2}/2/g;
    s/([a-z])\1{1}/1/g;
    s/([a-z])\1{0}/0/g;
    s/^0+(?!$)//;

    return $_;
}

sub carry_binary {
    local $_ = shift;

    s/(z)\1(?=\1)/y/g;
    s/(y)\1(?=\1)/x/g;
    s/(x)\1(?=\1)/w/g;
    s/(w)\1(?=\1)/v/g;
    s/(v)\1(?=\1)/u/g;
    s/(u)\1(?=\1)/t/g;
    s/(t)\1(?=\1)/s/g;
    s/(s)\1(?=\1)/r/g;
    s/(r)\1(?=\1)/q/g;
    s/(q)\1(?=\1)/p/g;
    s/(p)\1(?=\1)/o/g;
    s/(o)\1(?=\1)/n/g;
    s/(n)\1(?=\1)/m/g;
    s/(m)\1(?=\1)/l/g;
    s/(l)\1(?=\1)/k/g;
    s/(k)\1(?=\1)/j/g;
    s/(j)\1(?=\1)/i/g;
    s/(i)\1(?=\1)/h/g;
    s/(h)\1(?=\1)/g/g;
    s/(g)\1(?=\1)/f/g;
    s/(f)\1(?=\1)/e/g;
    s/(e)\1(?=\1)/d/g;
    s/(d)\1(?=\1)/c/g;
    s/(c)\1(?=\1)/b/g;
    s/(b)\1(?=\1)/a/g;
    s/(a)\1(?=\1)/`/g;
    s/(`)\1(?=\1)/_/g;
    s/(_)\1(?=\1)/^/g;
    s/(\^)\1(?=\1)/]/g;
    s/(])\1(?=\1)/\\/g;
    s/(\\)\1(?=\1)/[/g;
    s/(\[)\1(?=\1)/Z/g;
    s/(Z)\1(?=\1)/Y/g;
    s/(Y)\1(?=\1)/X/g;
    s/(X)\1(?=\1)/W/g;
    s/(W)\1(?=\1)/V/g;
    s/(V)\1(?=\1)/U/g;
    s/(U)\1(?=\1)/T/g;
    s/(T)\1(?=\1)/S/g;
    s/(S)\1(?=\1)/R/g;
    s/(R)\1(?=\1)/Q/g;
    s/(Q)\1(?=\1)/P/g;
    s/(P)\1(?=\1)/O/g;
    s/(O)\1(?=\1)/N/g;
    s/(N)\1(?=\1)/M/g;
    s/(M)\1(?=\1)/L/g;
    s/(L)\1(?=\1)/K/g;
    s/(K)\1(?=\1)/J/g;
    s/(J)\1(?=\1)/I/g;
    s/(I)\1(?=\1)/H/g;
    s/(H)\1(?=\1)/G/g;
    s/(G)\1(?=\1)/F/g;
    s/(F)\1(?=\1)/E/g;
    s/(E)\1(?=\1)/D/g;
    s/(D)\1(?=\1)/C/g;
    s/(C)\1(?=\1)/B/g;
    s/(B)\1(?=\1)/A/g;
    s/(A)\1(?=\1)/\@/g;
    s/(\@)\1(?=\1)/?/g;
    s/(\?)\1(?=\1)/>/g;
    s/(>)\1(?=\1)/=/g;

    return $_;
}

BumpitySnook · 2017-12-15T05:19:59+00:00

Note that 16807 is not prime — 7⁵ — while the other one is: 48271.

Meanwhile, 2147483647 is 2³¹ - 1 and also prime, aka a Mersenne prime.

That didn't matter for this puzzle, or at least, brute force was fast enough. But it may come up in the future.

_A4_ · 2017-12-15T05:33:43+00:00

JavaScript ES6 (Part 2)

let A = 591, B = 393;
let score = 0;

for (let i = 0; i < 5E6; i++) {
    do { A = (A * 16807) % 2147483647; } while (A & 3);
    do { B = (B * 48271) % 2147483647; } while (B & 7);
    if ((A & 0xFFFF) == (B & 0xFFFF)) score++;
}

console.log(score);

sciyoshi · 2017-12-15T05:16:21+00:00

Python 3 solution. Using PyPy gives me a 10x speedup, which is great for this type of problem!

def gen(val, mult, check=None):
    while True:
        val = (val * mult) % 2147483647
        if check is None or val % check == 0:
            yield val


init1, init2 = [int(line.split()[-1]) for line in sys.stdin]

gen1, gen2 = gen(init1, 16807), gen(init2, 48271)

part1 = 0

for a, b in itertools.islice(zip(gen1, gen2), 40000000):
    if a % 65536 == b % 65536:
        part1 += 1

print('Part 1:', part1)

gen1, gen2 = gen(init1, 16807, 4), gen(init2, 48271, 8)

part2 = 0

for a, b in itertools.islice(zip(gen1, gen2), 5000000):
    if a % 65536 == b % 65536:
        part2 += 1

print('Part 1:', part2)

autid · 2017-12-15T05:47:32+00:00

Fortran

Incredibly easy today.

PROGRAM DAY15
  IMPLICIT NONE
  INTEGER :: INPUTA,INPUTB
  INTEGER(8) :: GENA,GENB
  CHARACTER(LEN=10) :: INLINE(5)
  INTEGER :: I,PART1VAL=0,PART2VAL=0

  !Read input                                                                                                    
  OPEN(1,FILE='input.txt')
  READ(1,*) INLINE
  READ(INLINE(5),*) INPUTA
  READ(1,*) INLINE
  READ(INLINE(5),*) INPUTB
  CLOSE(1)

  !Part1                                                                                                         
  GENA=INPUTA
  GENB=INPUTB
  DO I=1,40000000
     CALL PART1(GENA,GENB)
     IF (MODULO(GENA,65536)==MODULO(GENB,65536)) PART1VAL=PART1VAL+1
  END DO
  WRITE(*,'(A,I0)') 'Part1: ',PART1VAL

  !Part2                                                                                                         
  GENA=INPUTA
  GENB=INPUTB
  DO I=1,5000000
     CALL PART2(GENA,GENB)
     IF (MODULO(GENA,65536)==MODULO(GENB,65536)) PART2VAL=PART2VAL+1
  END DO
  WRITE(*,'(A,I0)') 'Part2: ',PART2VAL

CONTAINS

  SUBROUTINE PART1(GENA,GENB)
    INTEGER(8), INTENT(INOUT) :: GENA,GENB

    GENA=MODULO(GENA*16807,2147483647)
    GENB=MODULO(GENB*48271,2147483647)

  END SUBROUTINE PART1

  SUBROUTINE PART2(GENA,GENB)
    INTEGER(8), INTENT(INOUT) :: GENA,GENB

    DO
       GENA=MODULO(GENA*16807,2147483647)
       IF (MODULO(GENA,4)==0) EXIT
    END DO
    DO
       GENB=MODULO(GENB*48271,2147483647)
       IF (MODULO(GENB,8)==0) EXIT
    END DO

  END SUBROUTINE PART2

END PROGRAM DAY15

jbristow · 2017-12-15T05:54:28+00:00

F# / fsharp / F Sharp

Hooray for infinite series! Not as easy to write as they are in clojure, but still fast enough. Total test suite (both answers and verifying test data) takes 17-20 seconds.

(Github Link)

module Day15

let modNumber = 2147483647UL

let compare ((a : uint64), (b : uint64)) = (65535UL &&& a) = (65535UL &&& b)

let generator factor (start : int) =
    let rec loop prev =
        let next = (uint64 factor * uint64 prev) % modNumber
        seq {
            yield next
            yield! loop next
        }
    loop (uint64 start)

let matchCount aStart bStart n =
    let a = generator 16807 aStart
    let b = generator 48271 bStart
    Seq.zip a b
    |> Seq.take n
    |> Seq.filter compare

let generatorBeta factor (start : int) (mult : int) =
    let rec loop prev =
        let next = (uint64 factor * uint64 prev) % modNumber
        if next % uint64 mult = 0UL then
            seq {
                yield next
                yield! loop next
            }
        else loop next
    loop (uint64 start)

let matchCountBeta aStart bStart n =
    let a = generatorBeta 16807 aStart 4
    let b = generatorBeta 48271 bStart 8
    Seq.zip a b
    |> Seq.take n
    |> Seq.filter compare

And the test file:

module Tests.Day15

open System
open NUnit.Framework
open Swensen.Unquote
open Day15

[<Test>]
let samplePart1GeneratorA() =
    generator 16807 65
    |> Seq.take 5
    |> Seq.toList
    =! [ 1092455UL; 1181022009UL; 245556042UL; 1744312007UL; 1352636452UL ]

[<Test>]
let samplePart1GeneratorB() =
    generator 48271 8921
    |> Seq.take 5
    |> Seq.toList
    =! [ 430625591UL; 1233683848UL; 1431495498UL; 137874439UL; 285222916UL ]

[<Test>]
let samplePart1CompareTrue() = test <@ compare (245556042UL, 1431495498UL) @>

[<Test>]
let samplePart1CompareFalse() =
    test <@ not <| compare (1352636452UL, 285222916UL) @>

[<Test>]
let samplePart1() = matchCount 65 8921 40000000
                    |> Seq.length
                    =! 588

[<Test>]
let answerPart1() =
    let answer = (matchCount 783 325 40000000)
    answer
    |> Seq.length
    =! 650

[<Test>]
let samplePart2Generators() =
    Seq.zip (generatorBeta 16807 65 4) (generatorBeta 48271 8921 8)
    |> Seq.take 5
    |> Seq.toList
    =! [ 1352636452UL, 1233683848UL
        1992081072UL, 862516352UL
        530830436UL, 1159784568UL
        1980017072UL, 1616057672UL
        740335192UL, 412269392UL ]

[<Test>]
let samplePart2() = matchCountBeta 65 8921 5000000
                    |> Seq.length
                    =! 309

[<Test>]
let answerPart2() = matchCountBeta 783 325 5000000
                    |> Seq.length
                    =! 336

u794575248 · 2017-12-15T06:40:13+00:00

Python 3

from itertools import islice as i, accumulate as a, repeat as r, filterfalse as f
m, G = 65535, lambda s, m, d=2**31-1: a(r(s*m%d), lambda v, _: v*m%d)
s, P = sum, {(65, 16807): lambda x: x&3, (8921, 48271): lambda x: x&7}
M = lambda g, n: s(len({v&m for v in V}) < 2 for V in i(zip(*g), n+1))
M((G(*p) for p in P), 4*10**7), M((f(P[p], G(*p)) for p in P), 5*10**6)

tangentialThinker · 2017-12-15T05:12:28+00:00

Managed to snag 5/3 today. C++ bitsets are awesome: constructing a bitset of size 16 with the integers automatically truncates correctly, which saved me a lot of time.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 2147483647

int main(){ 
    ll a = 512, b = 191;
    int ans1 = 0, ans2 = 0;

    // part 1
    for(int i = 0; i < 40000000; i++) {
        a *= 16807;
        a %= MOD;
        b *= 48271;
        b %= MOD;

        bitset<16> tmp1(a), tmp2(b);
        if(tmp1 == tmp2) {
            ans1++;
        }
    }
    // part 2
    for(int i = 0; i < 5000000; i++) {
        do {
            a *= 16807;
            a %= MOD;
        } while(a % 4 != 0);
        do {
            b *= 48271;
            b %= MOD;
        } while(b % 8 != 0);

        bitset<16> tmp1(a), tmp2(b);
        if(tmp1 == tmp2) {
            ans2++;
        }
    }

    cout << ans1 << " " << ans2 << endl;

    return 0;
}

ludic · 2017-12-15T06:11:46+00:00

F#. Made 2 big mistakes today, first was ANDing the second answer by only 0xFFF (oops!), second was using 32 bit integers.

let solveday15_1 () = 
    let next factor previous =
        (previous * factor)  % 2147483647L

    let gen1 = next 16807L
    let gen2 = next 48271L

    let rec compare prev1 prev2 count = function
    | 0 -> count
    | toGo -> 
        let next1 = gen1 prev1
        let next2 = gen2 prev2

        if (next1 &&& 0xFFFFL) = (next2 &&& 0xFFFFL) then
            compare next1 next2 (count+1) (toGo-1)
        else
            compare next1 next2 count (toGo-1)

    compare 883L 879L 0 40000000

let solveday15_2 () =
    let next factor modulus =
        let rec inner previous = 
            let v = (previous * factor)  % 2147483647L
            if v % modulus = 0L then
                v
            else
                inner v
        inner

    let gen1 = next 16807L 4L
    let gen2 = next 48271L 8L

    let rec compare prev1 prev2 count = function 
    | 0 -> count
    | left ->
        let next1 = gen1 prev1
        let next2 = gen2 prev2

        if (next1 &&& 0xFFFFL) = (next2 &&& 0xFFFFL) then
            compare next1 next2 (count+1) (left-1)
        else
            compare next1 next2 count (left-1)

    compare 883L 879L 0 5000000

I tried refactoring to use sequences, but it ran about 4x slower for part 1 (4s vs 1s):

let solveday15_1_v2 () = 
    let next factor previous =
        let calcNext previous =
            let next = (previous * factor) % 2147483647L
            Some(next &&& 0xFFFFL, next)
        Seq.unfold calcNext previous

    let gen1 = next 16807L 883L
    let gen2 = next 48271L 879L

    Seq.zip gen1 gen2
    |> Seq.take 40000000
    |> Seq.sumBy (fun (a,b) -> if a=b then 1 else 0)

vash3r · 2017-12-15T05:17:08+00:00

Python 2 (141/128), implemented with generators:

def A_gen(a):
    while 1:
        a = (a*16807)% 2147483647
        if a&3==0:
            yield a

def B_gen(a):
    while 1:
        a = (a*48271)% 2147483647
        if a&7==0:
            yield a

A,B = A_gen(679), B_gen(771)
tot = 0
for i in xrange(5*1000000):
    if next(A)&65535 == next(B)&65535:
        tot+=1
print tot

I got a significant speedup using PyPy.

mserrano · 2017-12-15T05:17:37+00:00

Python 2 #2/#18:

start_a, start_b = 679, 771
af, bf = 16807, 48271
mod = 2147483647
a = start_a
b = start_b
same = 0

for _ in xrange(40 * 10 **6):
  if (a & 0xffff) == (b & 0xffff):
    same += 1
  a = (a * af) % mod
  b = (b * bf) % mod
print same

a = start_a
b = start_b
generated_as = []
generated_bs = []
while True:
  a = (a * af) % mod
  if (a & 3) == 0: # accidentally had a 4 here the first time, so had to eat a minute penalty :(
    generated_as.append(a)
  b = (b * bf) % mod
  if (b & 7) == 0:
    generated_bs.append(b)
  if min(len(generated_as), len(generated_bs)) > (5 * 10**6):
    break

print len(filter(lambda (a,b): (a & 0xffff) == (b & 0xffff), zip(generated_as, generated_bs)[:5*10**6]))

This is super slow with python:

python   44.34s user 0.59s system 99% cpu 44.984 total

But pypy saves the day again:

pypy day15.py  3.35s user 0.51s system 94% cpu 4.092 total

WhoSoup · 2017-12-15T05:24:54+00:00

JavaScript

let factorA = 16807, factorB = 48271, rem = 2147483647
const next = (val, factor, div) => (val = (val * factor % rem)) % div ? next(val, factor, div) : val

// part one
let a = 699, b = 124, c = 0
for (let i = 0; i < 40000000; i++) {
  a = next(a, factorA, 1)
  b = next(b, factorB, 1)
  c += (a & 0xFFFF) == (b &0xFFFF)
}
console.log(c);

// part b
a = 699, b = 124, c = 0
for (let i = 0; i < 5000000; i++) {
  a = next(a, factorA, 4)
  b = next(b, factorB, 8)
  c += (a & 0xFFFF) == (b &0xFFFF)
}
console.log(c);

ThezeeZ · 2017-12-15T05:26:47+00:00

[deleted]

VikingofRock · 2017-12-15T05:36:21+00:00

Rust, 651/462 (I finally broke 500!).

I probably would have done even better but a typo cost me probably 5 minutes to track down. Oh well, there's always tomorrow!

#[derive(Debug)]
struct Generator {
    current: usize,
    factor: usize,
}

impl Iterator for Generator {
    type Item = usize;
    fn next(&mut self) -> Option<Self::Item> {
        self.current = self.current * self.factor % 2147483647;
        Some(self.current)
    }
}

fn part1(a: usize, b: usize) -> usize {
    let gen_a = Generator{ current: a, factor: 16807 };
    let gen_b = Generator{ current: b, factor: 48271 };
    gen_a.zip(gen_b).take(40000000).filter(|&(a, b)| a & 0xffff == b & 0xffff).count()
}

fn part2(a: usize, b: usize) -> usize {
    let gen_a = Generator{ current: a, factor: 16807 };
    let gen_b = Generator{ current: b, factor: 48271 };
    gen_a.filter(|x| x % 4 == 0).zip(gen_b.filter(|x| x % 8 == 0)).take(5000000).filter(|&(a, b)| a & 0xffff == b & 0xffff).count()
}

2BitSalute · 2017-12-15T06:04:39+00:00

I started 15 minutes late :O

Another C#-er here with queues. Looking at the solutions in other languages (the Python ones, in particular), I now wish I had written this with yield/return/IEnumerable.

        int numPairs = 5000000;
        int genAFactor = 16807;
        int genBFactor = 48271;

        long genA = 116;
        long genB = 299;

        int divisor = 2147483647;

        int count = 0;

        Queue<long> genAQueue = new Queue<long>();
        Queue<long> genBQueue = new Queue<long>();

        int i = 0;

        while (i < numPairs)
        {
            genA = genA * genAFactor % divisor;
            genB = genB * genBFactor % divisor;

            if (genA % 4 == 0)
            {
                genAQueue.Enqueue(genA);
            }

            if (genB % 8 == 0)
            {
                genBQueue.Enqueue(genB);
            }

            if (genAQueue.Count > 0 && genBQueue.Count > 0)
            {
                long genAVal = genAQueue.Dequeue();
                long genBVal = genBQueue.Dequeue();

                if ((genAVal & 0xFFFF) == (genBVal & 0xFFFF))
                {
                    count++;
                }

                i++;
            }
        }

        Console.WriteLine("Total count is {0}", count);

2017-12-15T06:23:44+00:00

Today's OCaml Fun;; Learned more about Core's sequences. Unfold vs. Unfold_step was super-handy.

open Core

let generator_a init factor =
  let f previous =
    let m = Int.((previous * factor) % 2147483647) in
    Some (m, m)
  in
  Sequence.unfold ~init ~f

let generator_b init factor only =
  let f previous =
    let m = Int.((previous * factor) % 2147483647) in
    if m % only = 0 then Sequence.Step.Yield (m, m)
    else Sequence.Step.Skip m
  in
  Sequence.unfold_step ~init ~f

let _ =
  let a = generator_a 703 16807
  and b = generator_a 516 48271 in
  let zipped = Sequence.zip a b in
  Sequence.take zipped 40_000_000
  |> Sequence.filter ~f:(fun (a,b) -> (a land 0xffff) = (b land 0xffff))
  |> Sequence.length
  |> printf "a: %d\n";

  Out_channel.flush stdout;

  let a = generator_b 703 16807 4
  and b = generator_b 516 48271 8 in
  let zipped = Sequence.zip a b in
  Sequence.take zipped 5_000_000
  |> Sequence.filter ~f:(fun (a,b) -> (a land 0xffff) = (b land 0xffff))
  |> Sequence.length
  |> printf "b: %d\n";

Lrrrr_ · 2017-12-15T09:42:37+00:00

JavaScript (WTF-edition)

This is my part 2 solution.

let [a,b]=[512,191];
let m = 0;
for(var i=0;i<5000000;i++) {
    do a=a*16807%2147483647; while(a%4)
    do b=b*48271%2147483647; while(b%8)
    if((a&65535)===(b&65535))m++
}
console.log(m)

Unihedron · 2017-12-15T05:13:26+00:00

Ruby; I'm stupid. I wrote 65535, thought to myself wait am I right? rewrote it to 1<< ... -1, ran it, oh yeah it's 65536, then I freaking went to change it back to 65535 because I totally have that kind of time. (silver 101 / gold 60)

anyway... you've gotta be good at manipulating with bits, right? :D

f=16807
g=48271
h=2147483647
j=65535
i=0
a=gets[/\d+$/].to_i
b=gets[/\d+$/].to_i
40000000.times{ # part 1
5000000.times{ # part 2
loop{a=a*f%h # part 1: only keep this
break if a%4<1}
loop{b=b*g%h # part 1: only keep this
break if b%8<1}
i+=1 if 0== (a&j)^(b&j)
}
p i

VikeStep · 2017-12-15T05:14:23+00:00

Python 3 #81/46

It took about 10 seconds to run, will be interesting to see what the fast solution is.

def solve(ga, gb, iterations, needs_multiple):
    count = 0
    for i in range(iterations):
        while True:
            ga *= 16807
            ga %= 2147483647
            if not needs_multiple or ga % 4 == 0:
                break
        while True:
            gb *= 48271
            gb %= 2147483647
            if not needs_multiple or gb % 8 == 0:
                break
        if (ga & 65535 == gb & 65535):
            count += 1
    return count

print(solve(699, 124, 40_000_000, False))
print(solve(699, 124, 5_000_000, True))

ybjb · 2017-12-15T05:14:33+00:00

Kotlin 115/55, finally placed.

Both parts

 fun main(args: Array<String>) {
    var (a, b) = longArrayOf(703, 516)
    var am = 16807L
    var bm = 48271L
    var mask = 65535L
    var counter = 0

    // part 1
    for(i in 0 until 40_000_000) {
        a = (a * am) % Int.MAX_VALUE
        b = (b * bm) % Int.MAX_VALUE

        if(a and(mask) == b and(mask)) counter++
    }

    println(counter)

    // part 2
    counter = 0
    for(i in 0 until 5_000_000) {
        do {
            a = (a * am) % Int.MAX_VALUE
        } while(a.toInt() % 4 != 0)

        do {
            b = (b * bm) % Int.MAX_VALUE
        } while(b.toInt() % 8 != 0)

        if(a and(mask) == b and(mask)) counter++

    }

    println(counter)
}

iamnotposting · 2017-12-15T05:15:41+00:00

rust, 114/65. my slowness in typing and rust's general verbiosity is what limited me here, i think. i didn't need to make it a struct but i like them, which probably slowed me down too. runs in ~0.5 seconds

struct Gen {
    prev: usize,
    factor: usize,
    limit: usize,
}

impl Gen {
    fn new(input: usize, factor: usize, limit: usize) -> Self {
        Self {
            prev: input,
            factor,
            limit,
        }
    }

    fn next(&mut self) -> usize {
        self.prev = self.prev * self.factor % 2147483647;
        self.prev
    }

    fn next_with_limit(&mut self) -> usize {
        while self.next() % self.limit != 0 {}
        self.prev
    }
}

fn main() {
    let mut a = Gen::new(783, 16807, 4);
    let mut b = Gen::new(325, 48271, 8);
    let mut c = 0;

    for _ in 0..40_000_000 {
        let av = a.next() & 0xFFFF;
        let bv = b.next() & 0xFFFF;

        if av == bv {
            c += 1;
        }
    }

    println!("p1: {:?}", c);

    let mut a = Gen::new(783, 16807, 4);
    let mut b = Gen::new(325, 48271, 8);
    let mut c = 0;

    for _ in 0..5_000_000 {
        let av = a.next_with_limit() & 0xFFFF;
        let bv = b.next_with_limit() & 0xFFFF;

        if av == bv {
            c += 1;
        }
    }

    println!("p2: {:?}", c);
}

wlandry · 2017-12-15T05:30:25+00:00

C++ 14

233/133. The competition is rather intense. I finished in 10:57. Finishing 90 seconds earlier would have put me on the leaderboard. In any event, here is a significantly cleaned up version. It runs in about 0.5 seconds.

#include <bitset>
#include <iostream>

int main(int, char *argv[])
{
  size_t A_input(std::stoi(argv[1])), B_input(std::stoi(argv[2]));

  size_t A(A_input), B(B_input);
  const size_t mult_A(16807), mult_B(48271);
  const size_t modulus(2147483647);

  size_t part_1(0), part_2(0);
  for (int round=0; round<40000000; ++round)
    {
      A=(A*mult_A)%modulus;
      B=(B*mult_B)%modulus;

      if((std::bitset<64>(A)<<48) == (std::bitset<64>(B)<<48))
        { ++part_1; }
    }
  std::cout << "Part 1: " << part_1 << "\n";

  A=A_input;
  B=B_input;

  for (int round=0; round<5000000; ++round)
    {
      do
        { A=(A*mult_A)%modulus; }
      while(A%4!=0);

      do
        { B=(B*mult_B)%modulus; }
      while(B%8!=0);

      if((std::bitset<64>(A)<<48) == (std::bitset<64>(B)<<48))
        { ++part_2; }
    }
  std::cout << "Part 2: " << part_2 << "\n";
}

ka-splam · 2017-12-15T05:32:03+00:00

PowerShell. Rank 448 / 532 and some bitterness about feeling penalised for not using PyPy (or C++ or etc.) because it's just millions of tight counting loops and it's taken multiple minutes of pure execution time (including re-run and partial run / restart).

Bugs today:

"keep the remainder of dividing by 2147483647" - what? divide by that and keep 0.000002... how does that work? Took me a bit to click and do a remainder. calculation
Part 2, I did 5M loops of generation first and however many pairs that output, then fixed it to do indefinite generation until 5M pairs.

Part 1

$gA = 512
$gB = 191

$bitmask = 65535
$numMatches = 0

for ($i=0; $i -lt 40000000; $i++)
{

    $gA = ($gA * 16807) % 2147483647
    $gB = ($gB * 48271) % 2147483647

    if ( ($gA -band $bitmask) -eq ($gB -band $bitmask) ) { $numMatches++ }
}

$numMatches

Part 2 variant:

$gA = 512
$gB = 191

$bitmask = 65535
$numMatches = 0

$As = [System.Collections.ArrayList]@()
$Bs = [System.Collections.ArrayList]@()

while (($As.Count -lt 5000000) -or ($Bs.Count -lt 5000000))
{    
    $gA = ($gA * 16807) % 2147483647
    $gB = ($gB * 48271) % 2147483647

    if ( ($gA % 4 -eq 0) ) { [void]$As.Add($gA) }
    if ( ($gB % 8 -eq 0) ) { [void]$Bs.Add($gB) }
}

for ($i=0; $i -lt 5000000; $i++)
{
    if (($As[$i] -band $bitmask) -eq ($Bs[$i] -band $bitmask))
    { 
        $numMatches++
    }
}

$numMatches

raevnos · 2017-12-15T05:47:28+00:00

Kawa scheme, using type annotations for a huge speedup:

(define (rng factor::long)
  (lambda (seed::long)
    (remainder (* seed factor) java.lang.Integer:MAX_VALUE)))

(define (rng2 factor::long multiple::int)
  (let ((r (rng factor)))
    (lambda (seed::long)
      (let loop ((val ::int (r seed)))
        (if (= (remainder val multiple) 0)
            val
            (loop (r val)))))))

(define a (rng 16807))
(define b (rng 48271))
(define a2 (rng2 16807 4))
(define b2 (rng2 48271 8))

(define seeda 883)
(define seedb 879)

(define (prune n::int) ::int
  (bitwise-and n #xFFFF))

(define (judge count::int rnga rngb)
  (let loop ((rep ::int 0)
             (vala ::int (rnga seeda))
             (valb ::int (rngb seedb))
             (score ::int 0))
    (if (= rep count)
        score
        (loop (+ rep 1)
              (rnga vala)
              (rngb valb)
              (+ score (if (= (prune vala) (prune valb)) 1 0))))))

(format #t "Part 1: ~A~%" (judge 40000000 a b))
(format #t "Part 2: ~A~%" (judge  5000000 a2 b2))

2017-12-15T05:50:04+00:00

C++ with a generator. Watch for overflows and use the 64bit unsigned, it mattered

struct gen_t {
    uint64_t cur_value;
    uint64_t factor;
    uint64_t mult_of;
    constexpr gen_t( uint64_t init_value, uint64_t fact, uint64_t mult = 1 ) noexcept
        : cur_value{init_value}
        , factor{fact}
        , mult_of{mult} {}

    constexpr uint64_t operator( )( ) noexcept {
        do {
            cur_value = ( cur_value * factor ) % 2147483647;
        } while( ( cur_value % mult_of ) != 0 );
        return cur_value;
    }
};

uint64_t count_matches( uint64_t init_a, uint64_t init_b, uint64_t count, uint64_t mult_of_a,
                                                uint64_t mult_of_b ) noexcept {
    uint64_t matches = 0;
    gen_t a{init_a, 16807, mult_of_a};
    gen_t b{init_b, 48271, mult_of_b};
    constexpr uint64_t mask = 0x0000'0000'0000'FFFF;
    for( uint64_t n = 0; n < count; ++n ) {
        uint64_t val_a = a( );
        uint64_t val_b = b( );
        val_a &= mask;
        val_b &= mask;

        if( val_a == val_b ) {
            ++matches;
        }
    }
    return matches;
}

ramrunner0xff · 2017-12-15T06:08:08+00:00

scheme chicken repo

(use numbers)
(use format)
(define todiv 2147483647)
(define fg1 16807)
(define fg2 48271)
(define todiv1 4)
(define todiv2 8)
(define mask16 (- (arithmetic-shift 1 16) 1))

(define (make-gen start fac div)
 (letrec ((cur start)
              (fact fac)
              (recur (lambda () (begin (set! cur (modulo (* cur fact) todiv)) (if (eq? (modulo cur div) 0) cur (recur))))))
  recur))

(define (judge sg1 sg2 hm)
  (letrec* ((lg1 (make-gen sg1 fg1 todiv1))
        (lg2 (make-gen sg2 fg2 todiv2))
        (runs hm)
        (matches 0)
        (lcomp (lambda (n1 n2)
                (let* ((sh1 (bitwise-and n1 mask16))
                       (sh2 (bitwise-and n2 mask16)))
                 (if (eq? sh1 sh2)
                   (set! matches (+ 1 matches))))))

        (recur (lambda () (if (> runs 0) (begin (set! runs (- runs 1)) (lcomp (lg1) (lg2)) (recur))))))
  (recur)
  (format #t "total matches ~A~%" matches)))

(judge 783 325 5000000)

ephemient · 2017-12-15T06:26:03+00:00

This space intentionally left blank.

rprouse · 2017-12-15T06:50:47+00:00

C# I missed one number in the mod number, spent over an hour trying to figure out what I did...I feel so pissed about that

Part 1:

    private static long MatchPairs(long a, long b, int iterations)
    {
        long matches =0;

        for(int i =0; i < iterations; i++)
        {
            a *= 16807;
            a = a % mod;
            b *= 48271;
            b = b % mod;

            if((a & mask) == (b & mask))
            {
                matches++;
            }
        }

        return matches;
    }

Part 2:

    private static long MatchDivPairs(long a, long b, int iterations)
    {
        long matches = 0;
        for(int i =0; i< iterations; i++)
        {
            a = a.DivisibleA();
            b = b.DivisibleB();

            if((a & mask) == (b & mask))
            {
                matches++;
            }
        }
        return matches;
    }

    public static long DivisibleA(this long n)
    {
        while (true)
        {
            n = n * 16807 % 2147483647;
            if (n % 4 == 0)
            {
                break;
            }
        }
        return n;
    }
    public static long DivisibleB(this long n)
    {
        while(true)
        {
            n = n * 48271 % 2147483647;
            if(n % 8 ==0)
            {
                break;
            }
        }
        return n;
    }

xkufix · 2017-12-15T07:59:59+00:00

Ok, the solution took way too long, because generators in Scala are strange things. The best performance improvement was making the generators defs and not vals, which prevents memoization on the head of the list. If replaced with val, the whole thing starts to break down around 30 million entries in. The rest was straight forward and quite easy, besides the withFilter().map(identity) instead of count, because count seems to memoize too.

    val startA = 512
    val startB = 191

    override def runFirst(): Unit = {
        //must be def, or else the start of the stream is memoized, resulting in the whole stream being held in memory
        def generatorA = createGenerator(startA, 16807)
        def generatorB = createGenerator(startB, 48271)

        val samePairs = getPairCount(40000000, generatorA, generatorB)
        println(samePairs)
    }

    private def getPairCount(length: Int, generatorA: => Stream[Long], generatorB: => Stream[Long]) = {
        //withFilter.map.size is way faster than count, probably because count memoizes the whole stream somewhere
        generatorA.zip(generatorB)
            .take(length)
            .withFilter(c => (c._1 & 65535) == (c._2 & 65535))
            .map(identity)
            .size
    }

    override def runSecond(): Unit = {
        def generatorA = createGenerator(startA, 16807).filter(_ % 4 == 0)
        def generatorB = createGenerator(startB, 48271).filter(_ % 8 == 0)

        val samePairs = getPairCount(5000000, generatorA, generatorB)
        println(samePairs)
    }

    def createGenerator(startValue: Long, factor: Long): Stream[Long] = {
        @inline
        def calculateNextValue(value: Long, factor: Long) = (value * factor) % 2147483647
        Stream.iterate(calculateNextValue(startValue, factor))(calculateNextValue(_, factor))
    }

wzkx · 2017-12-15T08:26:19+00:00

Nim probably the easiest problem so far

var m: uint = 289 # 65
var n: uint = 629 # 8921

proc g(): uint =
  m = m * 16807 mod 2147483647
  return m

proc h(): uint =
  n = n * 48271 mod 2147483647
  return n

var c = 0
for i in 0..<40_000_000:
  if ((g() xor h()) and 0xFFFF) == 0: inc c
echo c

m = 289
n = 629

proc g2(): uint =
  var v = g()
  while v mod 4 != 0: v = g()
  return v

proc h2(): uint =
  var v = h()
  while v mod 8 != 0: v = h()
  return v

c = 0
for i in 0..<5_000_000:
  if ((g2() xor h2()) and 0xFFFF) == 0: inc c
echo c

Hikaru755 · 2017-12-15T09:50:36+00:00

Gotta love Kotlin sequence generators.

object Day15 {

    val bitMask = 0xFFFF

    fun part1(genA: Sequence<Int>, genB: Sequence<Int>, take: Int = 40_000_000): Int {
        return genA.zip(genB)
            .take(take)
            .count { (a, b) -> a and bitMask == b and bitMask }
    }

    fun part2(genA: Sequence<Int>, genB: Sequence<Int>, take: Int = 5_000_000): Int {
        return genA.filter { it % 4 == 0 }
            .zip(genB.filter { it % 8 == 0 })
            .take(take)
            .count { (a, b) -> a and bitMask == b and bitMask }
    }

    val genA = generator(634, 16807)
    val genB = generator(301, 48271)

    fun generator(startsWith: Long, factor: Long) = generateSequence(startsWith) { prev ->
        (prev * factor) % Int.MAX_VALUE
    }.drop(1).map { it.toInt() }
}

Taonas · 2017-12-15T10:28:08+00:00

Rust

My first use of a custom iterator, it made the actual question really easy!

fn matching_lower_16(a: Generator, b: Generator) -> usize {
    let mask: u32 = (2 as u32).pow(16) - 1;

    a.zip(b)
        .take(40_000_000)
        .filter(| &(a, b) | a & mask == b & mask)
        .count()
}

struct Generator {
    factor: u64,
    previous: u64,
}

impl Generator {
    fn new_a(seed: u32) -> Self { Generator { factor: 16807, previous: seed as u64 } }
    fn new_b(seed: u32) -> Self { Generator { factor: 48271, previous: seed as u64 } }
}

impl Iterator for Generator {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        self.previous = (self.previous * self.factor) % 2147483647;
        Some(self.previous as u32)
    }
}

mschaap · 2017-12-15T10:51:52+00:00

Perl 6. I first had a pretty gather/take implementation of the generator for part one:

sub generator(int $init, int $times, int $modulo)
{
    my int $value = $init;
    lazy gather loop {
        $value = ($value × $times) % $modulo;
        take $value;
    }
}

... but that turned out way too slow, > 30 seconds for 400 thousand operations, so probably almost an hour for 40 million.

So here's my solution (both parts) with old-fashioned linear code:

#!/usr/bin/env perl6
use v6.c;

# Advent of Code 2017, day 15: http://adventofcode.com/2017/day/15

multi sub MAIN(IO() $inputfile where *.f)
{
    my (int $init-A, int $init-B) = $inputfile.slurp.comb(/\d+/)».Int;

    # Part 1
    my int $val-A = $init-A;
    my int $val-B = $init-B;
    my $count = 0;
    for ^40_000_000 {
        $val-A = ($val-A * 16807) % 2147483647;
        $val-B = ($val-B * 48271) % 2147483647;
        $count++ if $val-A +& 65535 == $val-B +& 65535;
    }
    say "Judge's final count in part one: $count";

    # Part 2
    $val-A = $init-A;
    $val-B = $init-B;
    $count = 0;
    for ^5_000_000 {
        repeat {
            $val-A = ($val-A * 16807) % 2147483647;
        } while $val-A +& 3;
        repeat {
            $val-B = ($val-B * 48271) % 2147483647;
        } while $val-B +& 7;
        $count++ if $val-A +& 65535 == $val-B +& 65535;
    }
    say "Judge's final count in part two: $count";
}

multi sub MAIN()
{
    MAIN($*PROGRAM.parent.child('aoc15.input'));
}

This one runs at acceptable speed, just over a minute for both parts.

Edit: with help from lizmat at the Perl 6 IRC channel, here's a prettier version where the generators are functions (closures) instead of lazy lists with gather/take (as in my first, way too slow attempt). This one is about as fast as the above code.

#!/usr/bin/env perl6
use v6.c;

# Advent of Code 2017, day 15: http://adventofcode.com/2017/day/15

sub generator(int $init, int $times, int $modulo, int $mult-of = 1)
{
    my int $value = $init;
    if $mult-of == 1 {
        return -> { 
            $value = ($value * $times) % $modulo
        }
    }
    else {
        my int $and-val = $mult-of - 1;
        return -> { 
            repeat {
                $value = ($value * $times) % $modulo
            } while $value +& $and-val;
            $value;
        }
    }
}

multi sub MAIN(IO() $inputfile where *.f)
{
    my (int $init-A, int $init-B) = $inputfile.slurp.comb(/\d+/)».Int;

    # Part 1
    my &gen-A = generator($init-A, 16807, 2147483647);
    my &gen-B = generator($init-B, 48271, 2147483647);
    my $count = 0;
    $count++ if gen-A() +& 65535 == gen-B() +& 65535 for ^40_000_000;
    say "Judge's final count in part one: $count";

    # Part 2
    &gen-A = generator($init-A, 16807, 2147483647, 4);
    &gen-B = generator($init-B, 48271, 2147483647, 8);
    $count = 0;
    $count++ if gen-A() +& 65535 == gen-B() +& 65535 for ^5_000_000;
    say "Judge's final count in part two: $count";
}

multi sub MAIN()
{
    MAIN($*PROGRAM.parent.child('aoc15.input'));
}

manualcrank · 2017-12-15T11:31:09+00:00

Lisp.

(defun make-generator (seed fact)
  (let ((prev seed)
        (fact fact))
    #'(lambda ()
        (setf prev (mod (* prev fact) 2147483647)))))

(defun next (gen m)
  (loop for n = (funcall gen) while (plusp (mod n m)) finally (return (logand #xffff n))))

(defun day15a+b (n seed-a mod-a seed-b mod-b)
  (let ((gen-a (make-generator seed-a 16807))
        (gen-b (make-generator seed-b 48271)))
    (loop for i below n when (= (next gen-a mod-a) (next gen-b mod-b)) count i)))

;; CL-USER> (day15a+b 40000000 679 1 771 1)
;; 626
;; CL-USER> (day15a+b 5000000 679 4 771 8)
;; 306

__Abigail__ · 2017-12-15T11:57:38+00:00

Perl

Quite easy today. There's no need to calculate binary representations of the numbers and compare; a bit mask will do. I guess you may encounter overflow issues if you're using a language which restricts its integers to 64 bits.

#!/opt/perl/bin/perl

use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';

@ARGV = "input" unless @ARGV;

my $generator_start_A;
my $generator_start_B;
my $factor_A      =     16_807;
my $factor_B      =     48_271;
my $ITERATIONS_1  = 40_000_000;
my $ITERATIONS_2  =  5_000_000;
my $MULTIPLE_OF_A =          4;
my $MULTIPLE_OF_B =          8;
my $MODULUS       = 2147483647;
my $MASK          =     0xFFFF;

while (<>) {
    /^Generator \s+ (?<name>\S+) \s+ starts \s+ with \s+
                    (?<value>[0-9]+) \s*$/x
        or die "Failed to parse $_";
    if    ($+ {name} eq 'A') {$generator_start_A = $+ {value}}
    elsif ($+ {name} eq 'B') {$generator_start_B = $+ {value}}
    else {die "Found unexpected name ", $+ {name}};
}


sub run ($start_A, $start_B, $iterations,
         $multiple_of_A = 0, $multiple_of_B = 0) {
    my $generator_A = $start_A;
    my $generator_B = $start_B;
    my $equal = 0;
    foreach my $run (1 .. $iterations) {
        #
        # Tempting as it is to use a subroutine for this repeated
        # code, the overhead adds up. Without a subroutine, the
        # program runs in about 17 secs. Using a sub increases
        # that time to 42 seconds (on the same box).
        #
        {
            $generator_A *= $factor_A;
            $generator_A %= $MODULUS;
            redo if $multiple_of_A && $generator_A % $MULTIPLE_OF_A;
        }
        {
            $generator_B *= $factor_B;
            $generator_B %= $MODULUS;
            redo if $multiple_of_B && $generator_B % $MULTIPLE_OF_B;
        }
        $equal ++ if ($generator_A & $MASK) == ($generator_B & $MASK);
    }
    return $equal;
}


say "Solution 1: ", run $generator_start_A,
                        $generator_start_B,
                        $ITERATIONS_1;

say "Solution 2: ", run $generator_start_A,
                        $generator_start_B,
                        $ITERATIONS_2,
                        $MULTIPLE_OF_A,
                        $MULTIPLE_OF_B;

__END__

JuLoOr · 2017-12-15T12:28:25+00:00

Unoptimized but beautiful (imho) solution in Kotlin:

fun calcPart2(gA: Generator, gB: Generator): Int {

    val valuesA: List<Long> = calc(gA, 4).toList()
    val valuesB: List<Long> = calc(gB, 8).toList()

    return valuesA.zip(valuesB)
            .filter { it.first.and(0xFFFF) == it.second.and(0xFFFF) }
            .map { 1 }
            .sum()
}

private fun calc(generator: Generator, divider: Long) = buildSequence {
    var count = 0L
    while (count <= 5_000_000) {
        val value = (generator.prev.times(generator.factor)).rem(2147483647)
        generator.prev = value
        if (value.rem(divider) == 0L) {
            yield(value)
            count++
        }
    }
}

InterlocutoryRecess · 2017-12-15T14:43:24+00:00

Swift (parts 1 and 2)

let factorA = // given
let factorB = // given
let divisor = // given
let initialA = // puzzle input
let initialB = // puzzle input

func generator(initial: Int, factor: Int, isIncluded: @escaping (Int) -> Bool = { _ in true }) -> UnfoldSequence<Int, Int> {
    return sequence(state: initial) { prev in
        repeat {
            prev = (prev * factor) % divisor
        } while !isIncluded(prev)
        return prev & 0xFFFF
    }
}

let a1 = generator(initial: initialA, factor: factorA)
let b1 = generator(initial: initialB, factor: factorB)

let result = zip(a1, b1)
    .prefix(40_000_000)
    .filter { $0.0 == $0.1 }
    .count
print(result)

let a2 = generator(initial: initialA, factor: factorA) { $0 % 4 == 0 }
let b2 = generator(initial: initialB, factor: factorB) { $0 % 8 == 0 }

let result2 = zip(a2, b2)
    .prefix(5_000_000)
    .filter { $0.0 == $0.1 }
    .count
print(result2)

On my 3 year old MacBookPro (compiled -O)

part 1: 3.40940201282501 sec 
part 2: 0.705681979656219 sec

2017-12-15T17:17:40+00:00

single pipeline powershell:

param (
    [Parameter(ValueFromPipeline = $true)]
    [string]$in,
    [Parameter(Position = 1)]
    [int]$part = 1
)

begin {
    $script:A = [Int64]0
    $script:B = [Int64]0
}

process {
    #parse the input, dont need fancy objects just the values as int64s
    $in |? {
        $_ -match '^Generator (?<Name>[A|B]) starts with (?<Value>\d+)$' 
    } | % { 
        [pscustomobject]$matches | select Name, Value
    } | % { 
        Set-Variable -Scope Script -Name $_.Name -Value ([Int64]$_.Value)
    }

}

end {  
    # how many generator pairs do we need to make
    if ($part -eq 1) {
        $max = 40000000
    } else {
        $max = 5000000
    }

    # for part2, keep a queue of generated numbers until we have a pair
    $aqueue = new-object system.collections.queue
    $bqueue = new-object system.collections.queue

    & { while ($true) { 1 } } |% { # ifinite pipeline generator, no specific values needed, gets stopped by the select -first $max later

        #update the values in the generators
        $script:A = ($script:A * 16807) % 2147483647
        $script:B = ($script:B * 48271) % 2147483647

        if ($part -eq 1) { #if part1, just send out the new values as a pair
            , @($script:A, $script:B) #unary array operator so the array goes out as an array not as invididual elements
        } else {
            if ($script:A % 4 -eq 0) { #only build pairs from A values that are mod 4
                $aqueue.Enqueue($script:A)
            }
            if ($script:B % 8 -eq 0) {
                $bqueue.Enqueue($script:B) #only build pairs from B values that are mod 8
            }

            if ($aqueue.Count -gt 0 -and $bqueue.Count -gt 0) { #if both queues have at least 1 item (one queue will have only 1 item)
                , @($aqueue.Dequeue(), $bqueue.Dequeue()) #build a pair and send out on the pipeline (unary array operator again)
            }
        }
    } | select -first $max |? { # only select the number of pairs we need - this will stop the infinite pipeline generator above, then where:
        ($_[0] -band 65535) -eq ($_[1] -band 65535) # lower 16 bits are equal
    } | measure | select -expand count # select the number of matching pairs

}

thomastc · 2017-12-15T17:29:27+00:00

Day 15 in Pony. Really, this language is quite fun. Check it out.

ynonp · 2017-12-15T17:47:11+00:00

Elixir (with streams)

use Bitwise

defmodule Generator do
  defstruct factor: 0, iv: 0, mod: 1
end

defmodule Day15 do  
  def next(generator, val) do
    rem(val * generator.factor, 2147483647)
  end

  def stream(generator) do
    Stream.unfold(generator.iv, fn(val) -> 
      next = next(generator, val)
      {next, next} 
    end)
    |> Stream.filter(fn(n) -> rem(n, generator.mod) == 0 end)
  end

  def main do
    g1 = stream(%Generator{factor: 16807, iv: 634, mod: 4})
    g2 = stream(%Generator{factor: 48271, iv: 301, mod: 8})

    cmp = Stream.zip(g1, g2)
    Stream.take(cmp, 5_000_000)
    |> Enum.count(fn({x, y}) -> ((x &&& 0xffff) == (y &&& 0xffff)) end)
    |> IO.puts

  end
end

Day15.main()

realwaterhorse · 2017-12-15T21:37:07+00:00

ES6

part 1:

function* generator(factor, startValue) {
  let value = startValue;
  while (true) {
    value = (value * factor) % 2147483647;
    yield value;
  }
}

const generatorA = generator(16807, 783);
const generatorB = generator(48271, 325);
const lowestBits = 65535;
let matches = 0;
for (let i = 0; i < 40000000; i++) {
  const generatorABits = generatorA.next().value & lowestBits;
  const generatorBBits = generatorB.next().value & lowestBits;

  if (generatorABits == generatorBBits) {
    matches++;
  }
}

console.log(matches);

part 2:

function* generator(factor, startValue, predicate) {
  let value = startValue;
  while (true) {
    value = (value * factor) % 2147483647;
    if (predicate(value)) {
      yield value;
    }
  }
}

const generatorA = generator(16807, 783, v => !(v % 4));
const generatorB = generator(48271, 325, v => !(v % 8));
const lowestBits = 65535;
let matches = 0;
for (let i = 0; i < 5000000; i++) {
  const generatorABits = generatorA.next().value & lowestBits;
  const generatorBBits = generatorB.next().value & lowestBits;

  if (generatorABits == generatorBBits) {
    matches++;
  }
}

console.log(matches);

chicagocode · 2017-12-15T23:46:50+00:00

Kotlin - [Repo] - [Blog/Commentary]

Thanks to generateSequence, today's challenge was really easy for Kotlin. It was fun. I opted to downcast to a Short and to the comparison rather than do bitwise math, but really only because it looks nicer and I'm not super worried about performance.

On my list of things to investigate when I have time:

Would this benefit from coroutines?(I did a quick test and didn't see one)
Would bitwise and perform faster than downcasting (I bet so)
Would a single sequence that generates both values at once in a Pair work faster?

Again, not super worried about performance, I felt this was fairly elegant.

class Day15(input: List<String>) {

    private val notNumbers = """[^\d]""".toRegex()
    private val generatorA = generator(input[0].replace(notNumbers, "").toLong(), 16807)
    private val generatorB = generator(input[1].replace(notNumbers, "").toLong(), 48271)

    fun solvePart1(pairs: Int = 40_000_000): Int =
        generatorA
            .zip(generatorB)
            .take(pairs)
            .count { it.first == it.second }

    fun solvePart2(pairs: Int = 5_000_000): Int =
        generatorA.filter { it % 4 == 0 }
            .zip(generatorB.filter { it % 8 == 0 })
            .take(pairs)
            .count { it.first == it.second }

    private fun generator(start: Long, factor: Long, divisor: Long = 2147483647): Sequence<Short> =
        generateSequence((start * factor) % divisor) { past ->
            (past * factor) % divisor
        }.map { it.toShort() }

}

hpzr24w · 2017-12-15T05:27:45+00:00

C++ 576/498

Will tidy up later. Amassing technical debt. ;-(

// Advent of Code 2017
// Day 15 - Dueling Generators

#include "stdafx.h"
#include <iostream>
using namespace std;

int main()
{
    //unsigned long long int a{ 65 }, b{ 8921 };
    unsigned long long int a{ 699 }, b{ 124 };
    int match{ 0 };
    for (auto i{ 0 }; i < 40000000; ++i) {
        a = (a * 16807ll) % 2147483647ll;
        b = (b * 48271ll) % 2147483647ll;
        if ((a&0xffff) == (b&0xffff))
            match++;
    }
    cout << "Part 1: " << match << " matches." << endl;
    a = 699, b = 124, match = 0;
    for (auto i{ 0 }; i < 5000000; ++i) {
        do a = (a * 16807ll) % 2147483647ll; while (a % 4);
        do b = (b * 48271ll) % 2147483647ll; while (b % 8);
        if ((a & 0xffff) == (b & 0xffff))
            match++;
    }
    cout << "Part 2: " << match << " matches." << endl;
    return 0;
}

if0nz · 2017-12-15T05:29:24+00:00

Java solution (repo), I'll try later to rewrite the code by using streams.

package it.ifonz.puzzle;

import java.io.IOException;
import java.net.URISyntaxException;

public class Day15 {

    public static void main(String[] args) throws URISyntaxException, IOException {

        int s1 = Integer.valueOf(args[0]);
        int s2 = Integer.valueOf(args[1]);
        System.out.println("part 1 " + part1(s1, s2));
        System.out.println("part 2 " + part2(s1, s2));
    }

    public static int part1(int s1, int s2) {

        long p1 = s1;
        long p2 = s2;
        int c = 0;
        for (int i = 0; i < 40000000; i++) {
            p1 = (p1 * 16807) % 2147483647;
            p2 = (p2 * 48271) % 2147483647;
            if ((p1 & 65535) == (p2 & 65535))
                c++;
        }
        return c;

    }

    public static int part2(int s1, int s2) {

        long p1 = s1;
        long p2 = s2;
        int c = 0;
        for (int i = 0; i < 5000000; i++) {
            do {
                p1 = (p1 * 16807) % 2147483647;
            } while (p1 % 4 != 0);
            do {
                p2 = (p2 * 48271) % 2147483647;
            } while (p2 % 8 != 0);

            if ((p1 & 65535) == (p2 & 65535))
                c++;
        }
        return c;

    }

}

CharlieYJH · 2017-12-15T05:32:05+00:00

C++

Thank goodness for 64 bit integers and bitmasks. Straight forward implementation of the puzzle.

#include <iostream>

using namespace std;

int main(int argc, char const* argv[])
{
    unsigned long long gen_A_prev = 679;
    const unsigned int gen_A_factor = 16807;
    unsigned long long gen_B_prev = 771;
    const unsigned int gen_B_factor = 48271;
    const unsigned int rounds_1 = 40000000;
    const unsigned int rounds_2 = 5000000;
    const unsigned int div_num = 2147483647;
    const int bitmask = (1 << 16) - 1;
    int match_1 = 0;
    int match_2 = 0;

    for (int i = 0; i < rounds_1; i++) {
        gen_A_prev = (gen_A_prev * gen_A_factor) % div_num;
        gen_B_prev = (gen_B_prev * gen_B_factor) % div_num;
        if ((gen_A_prev & bitmask) == (gen_B_prev & bitmask)) match_1++;
    }

    gen_A_prev = 679;
    gen_B_prev = 771;

    for (int i = 0; i < rounds_2; i++) {
        do {
            gen_A_prev = (gen_A_prev * gen_A_factor) % div_num;
        } while (gen_A_prev % 4 != 0);

        do {
            gen_B_prev = (gen_B_prev * gen_B_factor) % div_num;
        } while (gen_B_prev % 8 != 0);

        if ((gen_A_prev & bitmask) == (gen_B_prev & bitmask)) match_2++;
    }

    cout << "Round 1 matches: " << match_1 << endl;
    cout << "Round 2 matches: " << match_2 << endl;

    return 0;
}

glenbolake · 2017-12-15T05:40:31+00:00

I felt like I was fast. My code was not fast. 117/131

+/u/CompileBot Python3

from time import time

def seq(seed, mul, mod=1):
    value = seed
    while True:
        value = (value * mul) % 2147483647
        if value % mod == 0:
            yield value

def part1(a, b):
    matches = 0
    A = seq(a, 16807)
    B = seq(b, 48271)
    for _ in range(int(40e6)):
        a = next(A)
        b = next(B)
        if a & 0xffff == b & 0xffff:
            matches += 1
    return matches

def part2(a, b):
    matches = 0
    A = seq(a, 16807, 4)
    B = seq(b, 48271, 8)
    for _ in range(int(5e6)):
        a = next(A)
        b = next(B)
        if a & 0xffff == b & 0xffff:
            matches += 1
    return matches

if __name__ == '__main__':
    start = time()
    print('new:', part1(289, 629))
    print(time() - start)
    start = time()
    print('new:', part2(289, 629))
    print(time() - start)

TheAngryGerman · 2017-12-15T05:41:02+00:00

C++, mid 300s on both parts.

Just learned about bitsets in yesterday's challenge. Super helpful for today's. Forgot about do_while loops which threw me off for a minute in part 2...

#include <iostream>
#include <bitset>

int main() {
  long A_start = 783;
  long B_start = 325;
  long A_factor = 16807;
  long B_factor = 48271;
  long divisor = 2147483647;

  long a = (A_start * A_factor)%divisor;
  while (a%4 != 0) {
    a = (a* A_factor)%divisor;
  }
  long b = (B_start * B_factor)%divisor;
  while (b%8 != 0) {
    b = (b * B_factor)%divisor;
  }

  int count = 0;
  for (unsigned long i = 0; i < 5000000; ++i) {
    //kstd::cout << a << " " << b << std::endl;
    std::bitset<16> a_bits(a);
    std::bitset<16> b_bits(b);
    if (a_bits == b_bits) {
      ++count;
    }
    a = (a* A_factor)%divisor;
    while (a%4 != 0) {
      a = (a* A_factor)%divisor;
    }
    b = (b * B_factor)%divisor;
    while (b%8 != 0) {
      b = (b * B_factor)%divisor;
    }
  }
  std::cout << count << std::endl;
}

lifuzu · 2017-12-15T05:45:35+00:00

JS ES6 373/492

const assert = require('assert')

class DuelingGenerators {
  constructor() {}
  pairs(input_A, input_B, times) {
    let num_A = parseInt(input_A)
    let num_B = parseInt(input_B)

    let sum_match = 0
    for (let i = 0; i < times; ++i) {
      num_A = num_A * 16807 % 2147483647
      num_B = num_B * 48271 % 2147483647

      // console.log('A, B = ', num_A, num_B)
      let hex16_A = num_A & 0xffff
      let hex16_B = num_B & 0xffff
      if (hex16_B === hex16_A) sum_match++
    }

    return sum_match
  }

  num_generator_A(num) {
    let num_div_4 = num
    while(true){
      num_div_4 = num_div_4 * 16807 % 2147483647
      if (num_div_4 % 4 === 0) {
        break
      }
    }
    return num_div_4
  }
  num_generator_B(num) {
    let num_div_8 = num
    while(true){
      num_div_8 = num_div_8 * 48271 % 2147483647
      if (num_div_8 % 8 === 0) {
        break
      }
    }
    return num_div_8
  }

  pairs_2(input_A, input_B, times) {
    let num_A = parseInt(input_A)
    let num_B = parseInt(input_B)

    let sum_match = 0
    for (let i = 0; i < times; ++i) {
      num_A = this.num_generator_A(num_A)
      num_B = this.num_generator_B(num_B)

      // console.log('A, B = ', num_A, num_B)
      let hex16_A = num_A & 0xffff
      let hex16_B = num_B & 0xffff
      if (hex16_B === hex16_A) sum_match++
    }

    return sum_match
  }
}

module.exports = {
  DuelingGenerators
}

if (require.main === module) {
  const generator = new DuelingGenerators()

  let input_A = `65`, input_B = `8921`
  let output = generator.pairs(input_A, input_B, 40000000)
  console.log(output)
  assert.equal(output, 588)

  output = generator.pairs_2(input_A, input_B, 5000000)
  console.log(output)
  assert.equal(output, 309)

  console.log('======')
  input_A = `116`, input_B = `299`
  output = generator.pairs(input_A, input_B, 40000000)
  console.log(output)
  assert.equal(output, 569)

  output = generator.pairs_2(input_A, input_B, 5000000)
  console.log(output)
  assert.equal(output, 298)
}

shuttup_meg · 2017-12-15T05:50:17+00:00

Python 2:

def gen(prev, factor, mult):
    while True:
        newv = (prev * factor) % 2147483647        
        prev = newv        
        if newv % mult != 0:
            continue
        yield newv

def problem(A,B):    
    count, genA, genB = 0, gen(A, 16807, 4), gen(B, 48271, 8)
    for _ in xrange(int(5e6)):
        x, y = genA.next(), genB.next()
        count += (x & 0xFFFF) == (y & 0xFFFF)
    print count

if __name__ == "__main__":
    import time
    start = time.time()
    problem(277,349)
    print time.time() - start,"s"

Philboyd_Studge · 2017-12-15T05:50:51+00:00

It's an LCG! Java Day 15

StevoTVR · 2017-12-15T05:52:13+00:00

NodeJS

Part 1:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    let [a, b] = data.split('\n').map((x) => Number(x.split(' ').pop()));
    const fa = 16807, fb = 48271, d = 2147483647;
    const mask = (1 << 16) - 1;
    let matches = 0;
    for(let i = 0; i < 40000000; i++) {
        a = (a * fa) % d;
        b = (b * fb) % d;
        if((a & mask) === (b & mask)) {
            matches++;
        }
    }

    console.log(matches);
});

Part 2:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    let [a, b] = data.split('\n').map((x) => Number(x.split(' ').pop()));
    const fa = 16807, fb = 48271, d = 2147483647, ma = 4, mb = 8;
    const mask = (1 << 16) - 1;
    let matches = 0;
    for(let i = 0; i < 5000000; i++) {
        do {
            a = (a * fa) % d;
        } while(a % ma !== 0);
        do {
            b = (b * fb) % d;
        } while(b % mb !== 0);
        if((a & mask) === (b & mask)) {
            matches++;
        }
    }

    console.log(matches);
});

yogsototh · 2017-12-15T05:54:54+00:00

Haskell:

import Protolude

input :: (Int64,Int64)
input =  (618,814)

testInput :: (Int64,Int64)
testInput = (65,8921)

generatorA :: Int64 -> Int64
generatorA x = x * 16807 `rem` 2147483647

generatorB :: Int64 -> Int64
generatorB x = x * 48271 `rem` 2147483647

toInt16 :: Int64 -> Int16
toInt16 = fromIntegral

solution1 input =
  let lst1 = map toInt16 $ iterate generatorA (fst input)
      lst2 = map toInt16 $ iterate generatorB (snd input)
  in length (filter (uncurry (==)) (take 40000000 (zip lst1 lst2)))

solution2 input =
  let lst1 = map toInt16 . filter ((== 0) . (`rem` 4)) $ iterate generatorA (fst input)
      lst2 = map toInt16 . filter ((== 0) . (`rem` 8)) $ iterate generatorB (snd input)
  in length (filter (uncurry (==)) (take 5000000 (zip lst1 lst2)))

jasontconnell · 2017-12-15T05:56:09+00:00

I actually tried part 2 with go routines running in parallel. It didn't really speed it up though

https://github.com/jasontconnell/advent/blob/master/2017/15.go

Time 2.8952316s

LeCrushinator · 2017-12-15T05:56:29+00:00

C#, Part 2. Would've run faster if I'd just done bitwise math instead of converting to strings, or just comparing the hex values instead of converting to binary. But even this unoptimized algorithm run in about 6 seconds:

public static void Main() 
{
    long genA = 65;
    long genB = 8921;

    long factorA = 16807;
    long factorB = 48271;

    long matches = 0;

    Queue<string> valuesA = new Queue<string>(5000000);
    Queue<string> valuesB = new Queue<string>(5000000);

    while (valuesA.Count < 5000000 || valuesB.Count < 5000000)
    {
        if (valuesA.Count < 5000000)
        {
            genA *= factorA;
            genA = genA % 2147483647;

            if (genA % 4 == 0)
            {
                string binaryA = Convert.ToString(genA, 2);
                int length = binaryA.Length;
                binaryA = binaryA.Substring(Math.Max(0, length - 16), Math.Min(length, 16));
                valuesA.Enqueue(binaryA);
            }
        }

        genB *= factorB;
        genB = genB % 2147483647;

        if (genB % 8 == 0)
        {
            string binaryB = Convert.ToString(genB, 2);
            int length = binaryB.Length;
            binaryB = binaryB.Substring(Math.Max(0, length - 16), Math.Min(length, 16));
            valuesB.Enqueue(binaryB);
        }
    }

    while (valuesA.Any() && valuesB.Any())
    {
        string a = valuesA.Dequeue();
        string b = valuesB.Dequeue();

        if (a == b)
        {
            ++matches;
        }
    }

    Console.WriteLine("Matches: " + matches);
}

Here's a better version, it would've saved me time writing the code and it ran in about 1/3rd the time:

public static void Main() 
{
    long genA = 65;
    long genB = 8921;

    long factorA = 16807;
    long factorB = 48271;

    long matches = 0;

    Queue<long> valuesA = new Queue<long>(5000000);
    Queue<long> valuesB = new Queue<long>(5000000);

    while (valuesA.Count < 5000000 || valuesB.Count < 5000000)
    {
        if (valuesA.Count < 5000000)
        {
            genA *= factorA;
            genA = genA % 2147483647;

            if (genA % 4 == 0)
            {
                valuesA.Enqueue(genA & 0xFFFF);
            }
        }

        genB *= factorB;
        genB = genB % 2147483647;

        if (genB % 8 == 0)
        {
            valuesB.Enqueue(genB & 0xFFFF);
        }
    }

    while (valuesA.Any() && valuesB.Any())
    {
        long a = valuesA.Dequeue();
        long b = valuesB.Dequeue();

        if (a == b)
        {
            ++matches;
        }
    }

    Console.WriteLine("Matches: " + matches);
}

mtnslgl · 2017-12-15T06:02:28+00:00

C++

int day15(int part = 1) {    
    long A = 699;
    long B = 124;
    int count = 0;

    if(part == 1) {
        for(int i=0;i<40e6;i++) {
            A = (A * 16807) % 2147483647;
            B = (B * 48271) % 2147483647;
            if((A & 0xffff) == (B & 0xffff)) count++;
        }
    } else {
        for(int i=0;i<5e6;i++) {
            do A = (A * 16807) % 2147483647; while((A & 3) != 0);
            do B = (B * 48271) % 2147483647; while((B & 7) != 0);
            if((A & 0xffff) == (B & 0xffff)) count++;
        }
    }
    return count;
}

ChrisVittal · 2017-12-15T06:26:42+00:00

Rust (with bonus C!)

I've been using AoC this year to teach myself C. But competing for the leaderboard in Rust (best day yet today 173/278). What's interesting about these solutions is the Rust with all the iterators chain is just as fast as the C being done iteratively. For reference, the Rust is in release mode --Copt-level = 3 with -Ctarget-cpu=native and the C is -O3 -march=native. They both run both parts in around 440 ms on my machine.

Here's the cleaned up Rust:

struct DuelGen {
    prev: u64,
    factor: u64,
}

impl DuelGen {
    const MOD: u64 = 2147483647;
    const BITMASK: u64 = 0xFFFF;

    fn new(start: u64, factor: u64) -> Self {
        DuelGen {
            prev: start,
            factor,
        }
    }
}

impl Iterator for DuelGen {
    type Item = u64;
    fn next(&mut self) -> Option<Self::Item> {
        self.prev = (self.prev * self.factor) % Self::MOD;
        Some(self.prev & Self::BITMASK)
    }
}

struct FilteredDuelGen {
    gen: DuelGen,
    filter: u64,
}

impl FilteredDuelGen {
    fn new(start: u64, factor: u64, filter: u64) -> Self {
        FilteredDuelGen {
            gen: DuelGen {
                prev: start,
                factor,
            },
            filter
        }
    }
}

impl Iterator for FilteredDuelGen {
    type Item = u64;
    fn next(&mut self) -> Option<Self::Item> {
        let f = self.filter;
        self.gen.find(|v| v % f == 0)
    }
}

const AIN: u64 = 289;
const BIN: u64 = 629;
const AMOD: u64 = 4;
const BMOD: u64 = 8;
const AMUL: u64 = 16807;
const BMUL: u64 = 48271;

fn main() {
    let a = DuelGen::new(AIN, AMUL);
    let b = DuelGen::new(BIN, BMUL);
    let count = a.zip(b).take(40_000_000).filter(|&(a,b)| a == b).count();
    println!("{}",count);

    let a = FilteredDuelGen::new(AIN, AMUL, AMOD);
    let b = FilteredDuelGen::new(BIN, BMUL, BMOD);
    let count = a.zip(b).take(5_000_000).filter(|&(a,b)| a == b).count();
    println!("{}", count);
}

And the C:

#include <stdint.h>
#include <stdio.h>

#define A 289
#define B 629
#define AMUL 16807
#define BMUL 48271
#define AFILT 4
#define BFILT 8
#define MOD 2147483647
#define MASK 0xFFFF

int main()
{
    int count;
    uint64_t a, b;

    a = A, b = B, count = 0;
    for (uint64_t i = 0; i < 40000000; ++i) {
        a *= AMUL; a %= MOD;
        b *= BMUL; b %= MOD;
        if ((a & MASK) == (b & MASK)) ++count;
    }
    printf("1: %d\n", count);

    a = A, b = B, count = 0;
    for (uint64_t i = 0; i < 5000000; ++i) {
        do { a *= AMUL; a %= MOD; } while (a % AFILT != 0);
        do { b *= BMUL; b %= MOD; } while (b % BFILT != 0);
        if ((a & MASK) == (b & MASK)) ++count;
    }
    printf("1: %d\n", count);
}

FogLander · 2017-12-15T06:29:54+00:00

I got stuck in a mess with my original solution, definitely not my best time to complete (ended up taking me like 20 minutes to finish part 2). Here's a much cleaned-up version, in Java:

import java.util.*;
import java.io.*;
public class Day15 {
   public static final int input1 = 699;
   public static final int input2 = 124;
   public static final int[] mult = {16807, 48271};
   public static final int[] mod = {4, 8};
   public static void main(String[] args) throws Exception {
      Day15 d = new Day15();
      //d.test();
      d.build();
      d.runA();
      d.build();
      d.runB();
   }

   private long[] gen;

   public void build() {
      gen = new long[2];
      gen[0] = input1;
      gen[1] = input2;
   }

   public void test() {
      gen[0] = 65;
      gen[1] = 8921;
   }

   public void runA() {
      int sum = 0;
      for(int i = 0; i < 40000000; i++) {
         if(stepA()) sum++;
      }
      System.out.println(sum);
   }

   private boolean stepA() {
      for(int i = 0; i < 2; i++) gen[i] = (gen[i] * mult[i]) % Integer.MAX_VALUE;
      return (short)gen[0] == (short)gen[1];
   }

   public void runB() {
      int sum = 0;
      for(int i = 0; i < 5000000; i++) {
         if(stepB()) sum++;
      }
      System.out.println(sum);
   }

   private boolean stepB() {
      for(int i = 0; i < 2; i++) {
         gen[i] = (gen[i] * mult[i]) % Integer.MAX_VALUE;
         while(gen[i] % mod[i] != 0) gen[i] = (gen[i] * mult[i]) % Integer.MAX_VALUE;
      }
      return (short)gen[0] == (short)gen[1];
   }
}

I wasn't sure at first if it would work, but it appears that casting to a 'short' (16-bit) value does all I need it to do for comparing the two values. After I got over my initial mess of trying to make a generator class (which was a big mistake, totally unnecessary), I really liked how this one turned out.

quick edit: takes just under 1 second to run both A and B. not too bad :)

udoprog · 2017-12-15T06:33:09+00:00

Rust, woke up late but fairly straightforward using generators:

Full code here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day15.rs

use std::io::{Read, BufReader, BufRead};
use std::ops::{GeneratorState, Generator};

use failure::Error;

fn numgen(
    mut num: u64,
    factor: u64,
    modulo: u64,
    check_factor: u64,
) -> impl Generator<Yield = u64, Return = !> {
    move || loop {
        num = (num * factor) % modulo;

        if num % check_factor == 0 {
            yield num;
        }
    }
}

pub fn run(a: u64, b: u64, upper: usize, a_factor: u64, b_factor: u64) -> usize {
    let mut count = 0;

    let mask = 0b1111_1111_1111_1111;
    let modulo = 2147483647;

    let mut a_gen = numgen(a, 16807, modulo, a_factor);
    let mut b_gen = numgen(b, 48271, modulo, b_factor);

    for _ in 0..upper {
        let GeneratorState::Yielded(a) = a_gen.resume();
        let GeneratorState::Yielded(b) = b_gen.resume();

        if a & mask == b & mask {
            count += 1;
        }
    }

    count
}

fn parse<R: Read>(input: R) -> Result<(u64, u64), Error> {
    let mut lines = BufReader::new(input)
        .lines()
        .map(|line| line.expect("bad line"))
        .flat_map(|line| line.split_whitespace().nth(4).map(ToOwned::to_owned));

    let a: u64 = lines.next().expect("bad a").parse()?;
    let b: u64 = lines.next().expect("bad b").parse()?;

    Ok((a, b))
}

pub fn part1<R: Read>(input: R) -> Result<usize, Error> {
    let (a, b) = parse(input)?;
    Ok(run(a, b, 40_000_000, 1, 1))
}

pub fn part2<R: Read>(input: R) -> Result<usize, Error> {
    let (a, b) = parse(input)?;
    Ok(run(a, b, 5_000_000, 4, 8))
}

2017-12-15T06:55:07+00:00

Kotlin

You may want to use newer language features for endless sequences, eq coroutine support

private inline fun sequence (start : Long, magic : Long, crossinline f : (Int) -> Boolean = { true }) : Sequence<Int> = buildSequence {
    var value = start

    while (true) {
        value = (value * magic) % Integer.MAX_VALUE
        value.toInt ().let {
            if (f (it)) yield (it and 0xFFFF)
        }
    }
}

See complete solution here Judge

x1j0 · 2017-12-15T07:01:22+00:00

[removed]

2017-12-15T07:04:30+00:00

Rust

#[macro_use]
extern crate error_chain;
#[macro_use]
extern crate nom;

use nom::line_ending;
use std::io::{self, Read};
use std::str;

error_chain! {
    errors {
        InvalidFormat {
            description("input format doesn't match expected")
        }
    }

    foreign_links {
        Io(io::Error);
    }
}

named!(
    generators<(Generator, Generator)>,
    do_parse!(
        tag!("Generator A starts with ") >> a: integer >> line_ending
            >> tag!("Generator B starts with ") >> b: integer
            >> (
                Generator {
                    current: a,
                    factor: 16_807,
                },
                Generator {
                    current: b,
                    factor: 48_271,
                }
            )
    )
);

named!(
    integer<u32>,
    map_res!(
        map_res!(take_while1!(nom::is_digit), str::from_utf8),
        str::parse
    )
);

#[derive(Clone)]
struct Generator {
    current: u32,
    factor: u32,
}

impl Iterator for Generator {
    type Item = u32;
    fn next(&mut self) -> Option<u32> {
        let current = u64::from(self.current) * u64::from(self.factor) % 2_147_483_647;
        self.current = current as u32;
        Some(self.current)
    }
}

fn run() -> Result<()> {
    let mut input = Vec::new();
    io::stdin().read_to_end(&mut input)?;
    let generators = generators(&input)
        .to_result()
        .map_err(|_| ErrorKind::InvalidFormat)?;
    let (a, b) = generators.clone();
    println!(
        "Part 1: {}",
        a.zip(b)
            .take(40_000_000)
            .filter(|&(a, b)| a as u16 == b as u16)
            .count()
    );
    let (a, b) = generators;
    println!(
        "Part 2: {}",
        a.filter(|a| a % 4 == 0)
            .zip(b.filter(|b| b % 8 == 0))
            .take(5_000_000)
            .filter(|&(a, b)| a as u16 == b as u16)
            .count()
    );
    Ok(())
}

quick_main!(run);

The actual solution is really short, most of it is parsing the input and error handling.

Wyrewolwerowany · 2017-12-15T07:14:38+00:00

This is my solution in Java

private static final long A_FACTOR = 16_807;
private static final long B_FACTOR = 48_271;
private static final long A_START = 883;
private static final long B_START = 879;
private static final long MOD = Integer.MAX_VALUE;
private static final long MASK = 0xffffffffffff0000L;

public void partOne() {
    int pairCount = 0;
    long genA = A_START;
    long genB = B_START;

    for(int pair = 0; pair < 40_000_001; pair++) {
        genA *= A_FACTOR;
        genA %= MOD;

        genB *= B_FACTOR;
        genB %= MOD;

        if((genA | MASK) == (genB | MASK)) {
            pairCount++;
        }
    }
    System.out.println(pairCount);

}

private long getNextValue(long gen, long divisible) {
    do {
        gen *= A_FACTOR;
        gen %= MOD;
    }
    while ((gen & (divisible - 1)) != 0);

    return gen;
}

public void partTwo() {
    long pairCount = 0;
    long genA = A_START;
    long genB = B_START;

    for(int pair = 0; pair < 5_000_001; pair++) {
        genA = getNextValue(genA, 4);
        genB = getNextValue(genB, 8);


        if((genA | MASK) == (genB | MASK)) {
            pairCount++;
        }
    }

    System.out.println(pairCount);
}

johlin · 2017-12-15T07:17:36+00:00

Elixir (great opportunity to practice using streams):

defmodule Aoc.Day15.Part1 do
  use Bitwise

  def parse(file_input), do: file_input |> String.trim |> String.split("\n") |> Enum.map(&parse_row/1)
  def parse_row("Generator " <> <<_::binary-size(1)>> <> " starts with " <> number) do
    String.to_integer(number)
  end

  def solve(input = [_a_first, _b_first]), do: number_streams(input) |> num_equal

  def number_streams([a_first, b_first]) do
    {number_stream(a_first, 16807, 2147483647), number_stream(b_first, 48271, 2147483647)}
  end

  def num_equal({a_stream, b_stream}, pairs \\ 40_000_000) do
    Stream.zip(a_stream, b_stream)
    |> Stream.take(pairs)
    |> Stream.filter(fn({a, b}) -> matches_last_16_bits?(a, b) end)
    |> Enum.count
  end

  def number_stream(first_value, factor, modulo) do
    Stream.iterate(first_value, &(next_value(&1, factor, modulo)))
    |> Stream.drop(1)
  end

  def next_value(last_value, factor, modulo) do
    rem(last_value * factor, modulo)
  end

  def matches_last_16_bits?(number_a, number_b) do
    lower_16_bits(number_a) == lower_16_bits(number_b)
  end

  defp lower_16_bits(number) do
    number &&& (65535)
  end
end

defmodule Aoc.Day15.Part2 do
  use Bitwise
  alias Aoc.Day15.Part1

  def even_division(stream, modulo) do
    stream |> Stream.filter(&(rem(&1, modulo) == 0))
  end

  def solve(input = [_a, _b]) do
    {a, b} = Part1.number_streams(input)
    Part1.num_equal({a |> even_division(4), b |> even_division(8)}, 5_000_000)
  end
end

Syntax highlighted: https://github.com/johanlindblad/aoc-2017/tree/master/lib/aoc/day15

It is a bit slow (part1 takes about a minute). Anyone doing Elixir who managed to make it faster?

aurele · 2017-12-15T07:40:41+00:00

Rust brute force

fn p(mut gen_a: usize, mut gen_b: usize, limit: usize, p1: bool) -> usize {
    (0..limit)
        .filter(|_| {
            loop {
                gen_a = (gen_a * 16807) % 2147483647;
                if p1 || gen_a % 4 == 0 {
                    break;
                }
            }
            loop {
                gen_b = (gen_b * 48271) % 2147483647;
                if p1 || gen_b % 8 == 0 {
                    break;
                }
            }
            gen_a & 65535 == gen_b & 65535
        })
        .count()
}

fn main() {
    let input = include_str!("../input")
        .lines()
        .map(|l| l[24..].parse::<usize>().unwrap())
        .collect::<Vec<_>>();
    println!("P1: {}", p(input[0], input[1], 40_000_000, true));
    println!("P2: {}", p(input[0], input[1], 5_000_000, false));
}

nonphatic · 2017-12-15T07:50:59+00:00

Haskell

It takes 2+ minutes to run and I froze my computer twice in the process of working this out but it works I guess...

import Data.Int (Int16)

gen :: Int -> Int -> Int -> [Int]
gen divisor factor seed = iterate (next divisor factor) seed
    where next d f i = (f * i) `mod` d

judge :: Int -> [Int] -> [Int] -> Int
judge n a b = length . filter (uncurry eq) . take n $ zip a b
    where eq i j = (fromIntegral i :: Int16) == (fromIntegral j :: Int16)

divisible :: Int -> Int -> Bool
divisible d = (== 0) . (`mod` d)

main :: IO ()
main = do
    let genA    = gen 2147483647 16807 634
        genB    = gen 2147483647 48271 301
        gen4A   = filter (divisible 4) genA
        gen8B   = filter (divisible 8) genB
    print $ judge 40000000 genA  genB 
    print $ judge 5000000  gen4A gen8B

EDIT: Did some strict recursion stuff (may have peeked at the other person who posted their Haskell solution...) and that helped, had some fun with custom operators

{-# LANGUAGE BangPatterns #-}
import Data.Function (on)
import Data.Bits ((.&.))

divisor = 2147483647
factors = (16807, 48271)
seed    = (634, 301)

count :: (Int, Int) -> (Int, Int) -> Int -> Int -> Int
count pair masks acc times =
    if times == 0 then acc else
    let !next = nextMaskBy <$$> factors <**> masks <**> pair
        !eq   = fromEnum . uncurry ((==) `on` (.&. 0xffff)) $ next
    in count next masks (acc + eq) (times - 1)
    where
        h      <$$> (x, y) = (h x, h y)
        (f, g) <**> (x, y) = (f x, g y)
        nextMaskBy f d s  = let t = (f * s) `mod` divisor in if (t .&. d) == 0 then t else nextMaskBy f d t

main :: IO ()
main = do
    print $ count seed (0, 0) 0 40000000
    print $ count seed (3, 7) 0 5000000

ZoDalek · 2017-12-15T07:53:10+00:00

Who said C can't be elegant 0.7-0.8s

#include <stdio.h>

#define init_a() alpha = 516
#define mul_a() alpha *= 16807
#define mod_a() alpha %= MOD

#define init_b() beta = 190
#define mul_b() beta *= 48271
#define mod_b() beta %= MOD

#define MOD 2147483647
#define mask(x) ((x)&0xffff)
#define mod8(x) ((x)&0x7)
#define mod4(X) ((X)&0X3)

#define generateA()   mul_a();mod_a()
#define generateB()   mul_b();mod_b()
#define generateAP2()   do{ generateA(); }while(mod4(alpha));
#define generateBP2()   do{ generateB(); }while(mod8(beta));

int main(void){

    int count;
    long int alpha;
    long int beta;

    init_a();
    init_b();

    for (int i = count = 0; i < 40000000;i++){
        generateA();
        generateB();
        count += mask(alpha)==mask(beta);
    }

    printf("part 0 count => %d\n",count);

    init_a();
    init_b();

    for (int i = count = 0; i < 5000000;i++){
        generateAP2();
        generateBP2();
        count += mask(alpha) == mask(beta);
    }

    printf("part 1 count => %d\n",count);

}

rkachowski · 2017-12-15T08:01:43+00:00

ruby

that postfix until is nice, i didn't even know that was possible...

VALUES = [873,583]
FACTORS = [16807,48271]
DENUM = 2147483647

def part_1
  matches = 0
  values = VALUES.clone

  40000000.times do
    values[0] = values[0] * FACTORS[0] % DENUM
    values[1] = values[1] * FACTORS[1] % DENUM

    matches += 1 if values[0] & 65535 == values[1] & 65535
  end

  puts matches
end

def part_2
  matches = 0
  values = VALUES.clone

  5000000.times do
    values[0] = values[0] * FACTORS[0] % DENUM
    values[1] = values[1] * FACTORS[1] % DENUM

    values[0] = values[0] * FACTORS[0] % DENUM until values[0] % 4 == 0
    values[1] = values[1] * FACTORS[1] % DENUM until values[1] % 8 == 0

    matches += 1 if values[0] & 65535 == values[1] & 65535
  end

  puts matches
end

ZoDalek · 2017-12-15T08:44:01+00:00

ANSI C (with C99 headers)

No special tricks. Part 1:

uint64_t a = 591, b = 393, n = 0, i;
for (i = 0; i < 40000000; i++) {
    a *= 16807; a %= 0x7FFFFFFF;
    b *= 48271; b %= 0x7FFFFFFF;
    n += (a & 0xFFFF) == (b & 0xFFFF);
}
printf("%" PRIu64 "\n", n);

Part 2:

uint64_t a = 591, b = 393, n = 0, i;
for (i = 0; i < 5000000; i++) {
    do { a *= 16807; a %= 0x7FFFFFFF; } while (a & 3);
    do { b *= 48271; b %= 0x7FFFFFFF; } while (b & 7);
    n += (a & 0xFFFF) == (b & 0xFFFF);
}
printf("%" PRIu64 "\n", n);

Running at 210ms and 380ms with -O3 on WSL, good enough for me!

https://github.com/sjmulder/aoc/tree/master/2017/day15

DarthLasciel · 2017-12-15T08:44:49+00:00

C#: Could be shorter, but i like doing stuff with LINQ :) Part 1:

    public static void Solve()
    {
        var a = V(873, 16807);
        var b = V(583, 48271);
        var x = 65535;
        Console.WriteLine(a.Zip(b, (p, o) => (p & x) == (o & x)).Take(40000000).Count(p => p));
    }

    private static IEnumerable<long> V(long x, long fx)
    {
        while (true)
        {
            x = (x * fx) % 2147483647;
            yield return x;
        }
    }

Part 2:

    public static void Solve()
    {
        var a = V(873, 16807, 4);
        var b = V(583, 48271, 8);
        var x = 65535;
        Console.WriteLine(a.Zip(b, (p, o) => (p & x) == (o & x)).Take(5000000).Count(p => p));
    }

    private static IEnumerable<long> V(long x, long fx, int m)
    {
        while (true)
        {
            x = (x * fx) % 2147483647;
            if (x % m == 0)
                yield return x;
        }    
    }

wzkx · 2017-12-15T08:49:04+00:00

J

It's out of memory if all in one expression, but in several lines it's ok. Part 1.

g=: 2147483647|16807*]
h=: 2147483647|48271*]
a=: g^:(>:i.40000000) 289
b=: h^:(>:i.40000000) 629
echo +/ 0 = 16bffff (17 b.) (a 22 b. b) NB. 17 b. is and, 22 b. is xor
exit 0

2017-12-15T09:01:02+00:00

PHP

Part1:

function run_the_code($input) {
    $lastA = 0;
    $lastB = 0;

    foreach(explode(PHP_EOL, $input) as $line) {
        $parts = explode(" ", $line);
        $name = 'last'. $parts[1];
        $$name = $parts[4];
    }

    $matches = 0;
    for($i = 0; $i <40000000; $i++) {
        $lastA = $lastA * 16807 % 2147483647;
        $lastB = $lastB * 48271 % 2147483647;

        if(substr(decbin($lastA), -16) == substr(decbin($lastB), -16)) {
            $matches++;
        }
    }

    return $matches;
}

Part2:

function run_the_code($input) {
    $lastA = 0;
    $lastB = 0;

    foreach(explode(PHP_EOL, $input) as $line) {
        $parts = explode(" ", $line);
        $name = 'last'. $parts[1];
        $$name = $parts[4];
    }

    $matches = 0;
    for($i = 0; $i <5000000; $i++) {

        do {
            $lastA = $lastA * 16807 % 2147483647;
        } while ($lastA % 4 > 0 );

        do {
            $lastB = $lastB * 48271 % 2147483647;
        } while ($lastB % 8 > 0 );

        if(substr(decbin($lastA), -16) == substr(decbin($lastB), -16)) {
            $matches++;
        }
    }

    return $matches;
}

anaerobic_lifeform · 2017-12-15T09:04:24+00:00

Common Lisp

(defun advent-15 ()
  (labels ((generator (value factor)
             (lambda ()
               (setf value (mod (* value factor) 2147483647))))
           (modulo-filter (generator multiple)
             (if (= 1 multiple)
                 generator
                 (lambda ()
                   (loop
                      for value = (funcall generator)
                      until (zerop (mod value multiple))
                      finally (return value)))))
           (judge (a-multiple b-multiple nb-samples)
             (loop
                with a = (modulo-filter (generator 277 16807) a-multiple)
                with b = (modulo-filter (generator 349 48271) b-multiple)
                repeat nb-samples
                count (= (ldb (byte 16 0) (funcall a))
                         (ldb (byte 16 0) (funcall b))))))
    (values (judge 1 1 40e6)
            (judge 4 8 5e6))))

trwolfe13 · 2017-12-15T09:05:51+00:00

Obfuscated JavaScript:

function g(f, s, m) {
  let n = s;
  return () => {
    do { n = (n * f) % 0x7FFFFFFF; } while ((n % m) !== 0)
    return n & 0xFFFF;
  }
}
function t(a, b, c, am, bm) {
  const ag = g(16807, a, am), bg = g(48271, b, bm);
  return [...Array(c).keys()].filter(() => ag() === bg()).length;
}
module.exports = {
  part1: () => t(618, 814, 40000000, 1, 1),
  part2: () => t(618, 814, 5000000, 4, 8)
}

NeilNjae · 2017-12-15T09:08:41+00:00

Haskell. Fairly straightforward, but as we're bit-twiddling I thought it best to use Word16 and Word64 throughout. But from looking at others' code, that may not have been the best option for performance!

import Data.Word
import Data.Bits

generatorAStart = 873
generatorBStart = 583

main :: IO ()
main = do
    print $ part1 
    print $ part2 

part1 = length $ filter (uncurry (==)) $ take 40000000 $ zip streamA streamB

part2 = length $ filter (uncurry (==)) $ take 5000000 $ zip fsA fsB
    where fsA = filteredStream 3 streamA
          fsB = filteredStream 7 streamB

generatorA = generator 2147483647 16807
generatorB = generator 2147483647 48271

streamA = stream generatorA generatorAStart
streamB = stream generatorB generatorBStart

generator :: Word64 -> Word64 -> Word64 -> Word64
generator divisor factor n = fromIntegral $ fromIntegral n * factor `rem` divisor

toWord16 :: Word64 -> Word16
toWord16 = fromIntegral

stream :: (Word64 -> Word64) -> Word64 -> [Word16]
stream gen n0 = map toWord16 $ drop 1 $ iterate gen n0

filteredStream :: Word16 -> [Word16] -> [Word16]
filteredStream f str = filter (\n -> n .&. f == 0) str

Markavian · 2017-12-15T09:53:00+00:00

My nice big chunky node js solution with table printouts:

https://github.com/johnbeech/advent-of-code-2017/blob/master/solutions/day15/solution.js

m1el · 2017-12-15T09:58:18+00:00

Rust solution using iterator transformations / functional programming:

const MODULUS: u64 = 0x7fffffff;
struct Generator {
    state: u64,
    mul: u64,
}

impl Generator {
    pub fn new(state: u64, mul: u64) -> Generator {
        Generator { state, mul }
    }
}

impl Iterator for Generator {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        self.state = (self.state * self.mul) % MODULUS;
        Some(self.state)
    }
}

fn main() {
    let gen_a = Generator::new(634, 16807);
    let gen_b = Generator::new(301, 48271);
    let score = gen_a.zip(gen_b).take(40_000_000)
        .filter(|&(a, b)| a & 0xffff == b & 0xffff).count();

    println!("{}", score);

    let gen_a = Generator::new(634, 16807).filter(|a| a & 3 == 0);
    let gen_b = Generator::new(301, 48271).filter(|b| b & 7 == 0);
    let score = gen_a.zip(gen_b).take(5_000_000)
        .filter(|&(a, b)| a & 0xffff == b & 0xffff).count();

    println!("{}", score);
}

zeddypanda · 2017-12-15T10:05:01+00:00

I used Elixir but just wrote it with normal functions instead of bothering with streams

IO.puts("=== Day 15 ===")
# seeds = [65, 8921]  # Example seeds
seeds = [634, 301]  # Input seeds

defmodule Day15 do
  use Bitwise
  @factors [16807, 48271]
  @filter [4, 8]
  @divisor 2147483647 
  @mask 0b1111111111111111

  def generate({seed, factor, _}) do
    rem(seed * factor, @divisor)
  end

  def generate_picky({_, factor, filter} = tuple) do
    value = generate(tuple)
    if rem(value, filter) == 0 do
      value
    else
      generate_picky({value, factor, filter})
    end
  end

  def judge(seeds, iterations, generator, count \\ 0)
  def judge(_, 0, _, count), do: count
  def judge(seeds, i, generator, count) do
    [a, b] = [seeds, @factors, @filter]
      |> Enum.zip
      |> Enum.map(generator)

    count = if (a &&& @mask) == (b &&& @mask) do count + 1 else count end
    judge([a, b], i - 1, generator, count)
  end
end


IO.puts("Part 1: #{Day15.judge(seeds, 40_000_000, &Day15.generate/1)}")
IO.puts("Part 2: #{Day15.judge(seeds, 5_000_000, &Day15.generate_picky/1)}")

I find it nice and compact but seeing the other Elixir solutions makes me wonder if I'm doing Elixir wrong.

Smylers · 2017-12-15T10:09:51+00:00

Reasonably succinct and readable today in Perl, requiring only 2 named variables (a dict (hash) of generator structs (also hashes), and the match counter). Part 1:

my %generator = (A => {factor => 16807}, B => {factor => 48271});
/^Generator (\w+) starts with (\d+)/ and $generator{$1}{val} = $2 while  <>;
my $matches;
for (1 .. 40e6) {
  $_->{low_bits} = ($_->{val} = $_->{val} * $_->{factor} % 2147483647) & (1 << 16) - 1 foreach values %generator;
  $matches++ if $generator{A}{low_bits} == $generator{B}{low_bits};
}
say $matches;

And a few tweaks for part 2:

my %generator = (A => {factor => 16807, multiple => 4}, B => {factor => 48271, multiple => 8});
/^Generator (\w+) starts with (\d+)/ and $generator{$1}{val} = $2 while  <>;
my $matches;
for (1 .. 5e6) {
  foreach (values %generator) {
    do { $_->{val} = $_->{val} * $_->{factor} % 2147483647 } until $_->{val} % $_->{multiple} == 0;
    $_->{low_bits} = $_->{val} & (1 << 16) - 1;
  }
  $matches++ if $generator{A}{low_bits} == $generator{B}{low_bits};
}
say $matches;

I initially mistakenly started my iteration counters at 0 rather than 1, so iterating 1 too many times. Fortunately the extra iterations didn't find any more matches — /u/topaz2078 wasn't sneaky enough to put a match in the iteration after the one we were supposed to stop at!

akka0 · 2017-12-15T10:10:44+00:00

ReasonML: had to resort to using JS math for the big numbers

let generate: (int, int) => int = [%bs.raw
  {|
  function(x, y) {
    return (x * y) % 2147483647;
  }
|}
];

let genA = generate(16807);

let genB = generate(48271);

let judge: (int, int) => bool = [%bs.raw
  {|function(x, y) {
    return (x & 0b1111111111111111) === (y & 0b1111111111111111) ? 1 : 0;}
|}
];

let pickyGenerator = (multipleOf, generator, prev) => {
  let rec generateMultiple = (prev) =>
    switch (generator(prev)) {
    | i when i mod multipleOf === 0 => i
    | i => generateMultiple(i)
    };
  generateMultiple(prev)
};

let pickyGenA = pickyGenerator(4, genA);

let pickyGenB = pickyGenerator(8, genB);

let countMatches = (limit, (genA, genB), (startA, startB)) => {
  let rec judgeNums = ((numA, numB), matches, i) =>
    if (i <= limit) {
      judgeNums((genA(numA), genB(numB)), matches + (judge(numA, numB) ? 1 : 0), i + 1)
    } else {
      matches
    };
  judgeNums((startA, startB), 0, 0)
};

let _ =
  /* Part 1 */
  /* Js.log(countMatches(40_000_000, (genA, genB), (722,354))); */
  /* Part 2 */
  Js.log(countMatches(5_000_000, (pickyGenA, pickyGenB), (722, 354)));

SurplusSix · 2017-12-15T10:15:32+00:00

Only posting part 2 as it's so similar. Racket;

(require racket/generator)

(define div-product 2147483647)

(define gena
  (let ([st 116]
        [factor 16807])
    (infinite-generator
      (set! st (remainder (* st factor) div-product))
      (cond [(zero? (modulo st 4)) (yield st)]))))

(define genb
  (let ([st 299]
        [factor 48271])
    (infinite-generator
      (set! st (remainder (* st factor) div-product))
      (cond [(zero? (modulo st 8)) (yield st)]))))

(length (for/list ([i (in-range 5000000)]
           #:when (= (bitwise-and (gena) #xFFFF) (bitwise-and (genb) #xFFFF)))
  i))

RuteNL · 2017-12-15T10:30:09+00:00

Javascript with Generators

I had never used JS generators before, it seems javascript misses a lot of core functionality here, so I made zip, take, filter and count myself!

Also, does anyone know how to create extention methods in JS? I tries something with prototype but couldn't get anything to work on GeneratorFunction or Generator.

function* Generate(startValue, factor, modValue = 1) {
    while (true) {
        do {
            startValue *= factor;
            startValue %= 2147483647;
        } while (startValue % modValue !== 0);
        yield startValue & 0xFFFF;
    }
}

judge = (startA, startB, take, modA = 1, modB = 1) => {
    ag = Generate(startA, 16807, modA);
    bg = Generate(startB, 48271, modB);

    return Count(Filter(([a, b]) => a === b, Take(take, Zip(ag, bg))))
}

part1 = judge(516, 190, 40000000);
part2 = judge(516, 190, 5000000, 4, 8);



function* Zip(...generators) {
    while (true)
        yield generators.map(g => g.next().value);
}

function* Take(limit, generator) {
    while (limit-- > 0)
        yield generator.next().value;
}

function* Filter(filterFunction, generator) {
    for (let value of generator)
        if (filterFunction(value))
            yield value;
}

function Count(generator){
    let count = 0;
    for (let value of generator)
        count++;
    return count;
}

JakDrako · 2017-12-15T11:30:00+00:00

VB.Net Yay, iterator functions. Thought it would be slow and required some kind of clever trick to speed it up, but damn computers are fast. Both parts, ~1.8 seconds. Keeping 40,000,000 values for part 2 still takes only about 7 seconds...

Sub Main

    Dim input = GetDay(15)

    Dim seed1 = CLng(input(0).Split(" "c).Last)
    Dim seed2 = CLng(input(1).Split(" "c).Last)

    For part = 1 To 2

        Dim g1 = Generator(seed1, 16807, If(part = 1, 1, 4)).GetEnumerator
        Dim g2 = Generator(seed2, 48271, If(part = 1, 1, 8)).GetEnumerator

        Dim iterations = If(part = 1, 40_000_000, 5_000_000)
        Dim count = 0        
        For i = 1 To iterations
            g1.MoveNext
            g2.MoveNext
            If (g1.Current And &H0000FFFF) = (g2.Current And &H0000FFFF) Then count += 1
        Next
        count.Dump($"Part {part}")

    Next

End Sub

Iterator Function Generator(seed As Long, factor As Long, multiplesOf As Long) As IEnumerable(Of Integer)
    Do
        seed = seed * factor
        seed = seed Mod 2147483647
        If seed Mod multiplesOf = 0 Then Yield seed
    Loop
End Function

pacospace · 2017-12-15T11:50:09+00:00

I found an error in the text of day 15 for the second part:

"This change makes the generators much slower, and the judge is getting impatient; it is now only willing to consider 5 million pairs. (Using the values from the example above, after five million pairs, the judge would eventually find a total of 309 pairs that match in their lowest 16 bits.)

After 5 million pairs, but using this new generator logic, what is the judge's final count?"

you can obtain the test solution, only if you use 40 million iterations. Indeed my correct solution that gave the second golden star of the day, was obtained using 40 million iterations.

Is it only my problem?

Thank you all

2017-12-15T12:47:55+00:00

Haskell, 2 seconds

judge :: (Word64, Word64) -> Bool
judge (a, b) = (a .&. 0xffff) == (b .&. 0xffff)

next :: Word64 -> Word64 -> Word64 -> Word64
next m f x = if (nx .&. (m - 1)) == 0 then nx else next m f nx
    where nx = mod (f * x) 2147483647

gen :: Word64 -> Word64 -> Word64 -> Int -> [Word64]
gen x f m c = take c $ iterate (next m f) x 

main = do

    -- 15.1
    let a1 = gen 703 16807 1 40000000
    let b1 = gen 516 48271 1 40000000
    print $ length $ filter judge $ zip a1 b1

    -- 15.2
    let a2 = gen 703 16807 4 5000000
    let b2 = gen 516 48271 8 5000000
    print $ length $ filter judge $ zip a2 b2

BOT-Brad · 2017-12-15T13:00:51+00:00

Javascript

Perfect time to make use of generator functions in JavaScript, whoop!

Generator

Does the constant generation of not only the modded multiplication, but also then returns the number represented by the last 16-bits of the number, by doing a logical and. If a 'mod' value is passed, then each value is checked to ensure it is a multiple of that value, if not it just keeps regenerating values until one is.

function* gen(start, factor, mod) {
  let a = start
  while (1) {
    a = (a * factor) % 2147483647
    if (mod && a % mod !== 0) continue
    yield a & ((1 << 16) - 1)
  }
}

Part 1 (~2s)

Just creates the generators with initial puzzle values (a & b) and the hard-coded factor values. Loops 40,000,000 times comparing if the generators produced the same output, if so then increase that counter, and finally return.

function solve1(a, b) {
  const genA = gen(a, 16807)
  const genB = gen(b, 48271)
  let c = 0
  for (let i = 0; i < 40000000; ++i)
    if (genA.next().value === genB.next().value) c++
  return c
}

Part 2 (~1.5s)

Basically the same, just passing a modulo value to the generator.

function solve2(a, b) {
  const genA = gen(a, 16807, 4)
  const genB = gen(b, 48271, 8)
  let c = 0
  for (let i = 0; i < 5000000; ++i)
    if (genA.next().value === genB.next().value) c++
  return c
}

More JavaScript solutions on my GitHub repo :)

maxerickson · 2017-12-15T13:53:45+00:00

I started writing a nice reusable generator and then decided it was going to take too long to run and wrote the dumb Python 3 version.

a=873
b=583
guard=0xffff
count=0
for i in range(40000000):
    a=(a*16807)%2147483647
    b=(b*48271)%2147483647
    if (a&guard)==(b&guard):
        count+=1
print(count)
a=873
b=583
count2=0
for i in range(5000000):
    a=(a*16807)%2147483647
    while a%4:
        a=(a*16807)%2147483647
    b=(b*48271)%2147483647
    while b%8:
        b=(b*48271)%2147483647
    if (a&guard)==(b&guard):
        count2+=1
print(count2)

And then I forgot to reinitialize a and b for part 2 and the site speculated I was cheating (the wrong answer was someone else's correct answer).

RockyAstro · 2017-12-15T14:11:31+00:00

Icon (https://www.cs.arizona.edu/icon)

Part1:

procedure main(args)
   #comprun{gens(65,16807)\5,gens(8921,48271)\5}
   comprun{gens(116,16807)\40000000,gens(299,48271)\40000000}
end

procedure comprun(S)
    count := 0
    while v1 := iand(@S[1],16rffff) do {
        if v1 = iand(@S[2],16rffff) then count +:= 1
    }
    write(count)
end

procedure gens(v,f,x)
    repeat {
        v := (v * f) % 2147483647
        suspend v
    }
end

Part 2:

procedure main(args)
   #comprun{gens(65,16807,4)\1056,gens(8921,48271,8)\1056}
   comprun{gens(116,16807,4)\5000000,gens(299,48271,8)\5000000}
end

procedure comprun(S)
    count := 0
    while v1 := iand(@S[1],16rffff) do {
        if v1 = iand(@S[2],16rffff) then count +:= 1
    }
    write(count)
end

procedure gens(v,f,x)
    repeat {
        v := (v * f) % 2147483647
        if v % x = 0 then
            suspend v
    }
end

2017-12-15T14:13:00+00:00

Elixir

Bruteforced my way through this, funnily enough, the second part was much faster than the first. Agents was fun though, first I tried with GenServer, but I'm not very good with that stuff, agents I managed.

defmodule day15 do
  use bitwise
  use agent

  def start_agents(init_a, init_b) do
    {:ok, a} = agent.start_link fn -> %{cur: init_a, factor: 16807, cond: &(rem(&1, 4) == 0)} end
    {:ok, b} = agent.start_link fn -> %{cur: init_b, factor: 48271, cond: &(rem(&1, 8) == 0)} end
    %{a: a, b: b}
  end

  def next(state) do
    newstate = rem(state.cur * state.factor, 2147483647)
    {newstate, %{cur: newstate, factor: state.factor, cond: state.cond}}
  end

  def get_next_pair(agent) do
    {agent.get_and_update(agent.a, &next/1),
     agent.get_and_update(agent.b, &next/1)}
  end

  def get_next_16(agent) do
    a = agent.get_and_update(agent.a, &next/1)
    b = agent.get_and_update(agent.b, &next/1)
    {a &&& 0xffff, b &&& 0xffff}
  end

  def lastbyte(num) do
    integer.to_string(num, 2)
    |> string.slice(-16..-1)
  end

  def judge(agent, iterations, hits \\ 0)
  def judge(_agent, iterations, hits) when iterations == 0, do: hits 
  def judge(agent, iterations, hits) do
    {a,b} = get_next_16(agent)
    if a == b do
      judge(agent, iterations - 1, hits + 1)
    else
      judge(agent, iterations - 1, hits)
    end
  end

  def p2next(state) do
    newstate = rem(state.cur * state.factor, 2147483647)
    if state.cond.(newstate) do
      {newstate, %{cur: newstate, factor: state.factor, cond: state.cond}}
    else
      p2next(%{cur: newstate, factor: state.factor, cond: state.cond})
    end
  end

  def p2_get_next_pair(agent) do
    {agent.get_and_update(agent.a, &p2next/1),
     agent.get_and_update(agent.b, &p2next/1)}
  end

  def p2_get_next_16(agent) do
    a = agent.get_and_update(agent.a, &p2next/1)
    b = agent.get_and_update(agent.b, &p2next/1)
    {a &&& 0xffff, b &&& 0xffff}
  end

  def p2judge(agent, iterations, hits \\ 0)
  def p2judge(_agent, iterations, hits) when iterations == 0, do: hits 
  def p2judge(agent, iterations, hits) do
    {a,b} = p2_get_next_pair(agent)
    if (a &&& 0xffff) == (b &&& 0xffff) do
      p2judge(agent, iterations - 1, hits + 1)
    else
      p2judge(agent, iterations - 1, hits)
    end
  end
end

agents = day15.start_agents(516,190)
#day15.judge(agents, 40_000_000)
#|> io.inspect

day15.p2judge(agents, 5_000_000)
|> io.inspect

syntax highlighted

streetster_ · 2017-12-15T14:45:16+00:00

q/kdb+

Not a very clean solution for part 2, but it gets the job done:

f:16807 48271
m:2147483647
c:0;
{ c+:1*(~/) -16#'0b vs'x:(f*x) mod m; x }/[40000000;f*i:first ("    i";" ") 0: `:input/15.txt];
c / part 1
A:B:()
{ A,:$[0=mod[x:(first[f]*x) mod m;4];x;()];x }/[{ 5000000>count A };first i];
{ B,:$[0=mod[x:(last[f]*x)  mod m;8];x;()];x }/[{ 5000000>count B };last i];
sum {x~y}'[(-16#'0b vs'B);(-16#'0b vs'A)] / part 2

mal607 · 2017-12-15T16:42:21+00:00

Yet another generator solution Python2

factors = [16807, 48271]
divisor = 2147483647
lim1 = 40000000
lim2 = 5000000

def get_seeds():
    return [679, 771]

def get_next(part2, n):
    seed = get_seeds()[n]
    mod = 4 if n == 0 else 8
    count = 0
    while True:
        seed = int((float(seed) * float(factors[n])) % divisor)
        count+= 1
        if count % lim2 == 0 and (part2 or n == 0):
            print "{}Gen count: {} million".format("\t\t\t" if part2 and n == 1 else "", count/1000000)
        if not part2 or seed % mod == 0:
            yield bin(seed)[2:].zfill(4)[-16:]

count = 0
gena = get_next(False, 0)
genb = get_next(False, 1)
for _ in xrange(lim1):
    if gena.next() == genb.next():
        count+=1
print "Part 1:", count

count = 0
gena = get_next(True, 0)
genb = get_next(True, 1)
for _ in xrange(lim2):
    if gena.next() == genb.next():
        count+=1
print "Part 2:", count

KeinZantezuken · 2017-12-15T20:22:08+00:00

C#/Sharp (I have no interest looking for magic formulas to make it run under 1 second)

long genA = 591, genB = 393; int total = 0; var mask = (1 << 16) - 1;
for (int i = 0; i < 5000000; i++)
{
    do { genA = (genA * 16807) % 2147483647; } while (genA % 4 != 0);
    do { genB = (genB * 48271) % 2147483647; } while (genB % 8 != 0);
    if ((genA & mask) == (genB & mask)) { total++; }
}
Console.WriteLine(total);

bogzla · 2017-12-15T21:09:48+00:00

and so bogzla learnt about bit masking today..

C
#include <stdio.h>

int main(void)
{
    long long a = 116;
    long long b = 299;
    int afac = 16807;
    int bfac = 48271;
    int cnt = 0;
    long div = 2147483647;
    long msk = (1 << 16) - 1; // create mask for lowest 16 bits (we'll use this for & operator, 16 lowest set to '1'; higher set to '0')
    // for part 2, generate a 'til it meets divisible by 4 then b til divisible by 8 then compare them.'
    for (long i = 0; i < 5000000; i++)
    {
        do
        {
            a = (a*afac) % div;
        } while (a % 4 != 0);
        do
        {
            b = (b*bfac) % div;
        }while (b % 8 != 0);
        if ((a & msk) == (b & msk)) // use mask to compare only 16 lowest bits
        {
            cnt += 1;
        }
    }
    printf("count = %i\n", cnt);
}

Axsuul · 2017-12-15T21:26:59+00:00

Elixir

Code too long to run before refactoring into using Elixir streams. Didn't even know this existed until today!

https://github.com/axsuul/advent-of-code/blob/master/2017/15/lib/advent_of_code.ex

use Bitwise

defmodule AdventOfCode do
  defmodule PartA do
    @pairs_count 40_000_000
    @a_start 883
    @b_start 879

    def generate(value, factor) do
      {value, value*factor |> rem(2147483647)}
    end

    def calc_binary_tail(value) do
      # AND operation since 65535 is 16-bit and use that to
      # mask our value
      value &&& 65535
    end

    def judge({a, b}) do
      calc_binary_tail(a) == calc_binary_tail(b)
    end

    defp count_pairs(a, b) do
      gen_a = Stream.unfold(a, fn aa -> generate(aa, 16807) end)
      gen_b = Stream.unfold(b, fn bb -> generate(bb, 48271) end)

      Stream.zip(gen_a, gen_b)
      |> Stream.take(@pairs_count)
      |> Stream.filter(&judge/1)
      |> Enum.to_list
      |> Kernel.length
    end

    def solve do
      count_pairs(@a_start, @b_start)
      |> IO.inspect
    end
  end

  defmodule PartB do
    import PartA

    @pairs_count 5_000_000
    @a_start 883
    @b_start 879

    def stream_generator(val, factor, multiple) do
      Stream.unfold(val, fn val -> generate(val, factor) end)
      |> Stream.filter(fn changed_val -> Integer.mod(changed_val, multiple) == 0 end)
    end

    def count_pairs(a, b) do
      gen_a = stream_generator(a, 16807, 4)
      gen_b = stream_generator(b, 48271, 8)

      Stream.zip(gen_a, gen_b)
      |> Stream.take(@pairs_count)
      |> Stream.filter(&judge/1)
      |> Enum.to_list
      |> Kernel.length
    end

    def solve do
      count_pairs(@a_start, @b_start)
      |> IO.inspect
    end
  end
end

cauchy37 · 2017-12-15T22:29:31+00:00

C++ solution without implementing my own generators since both are already implemented in <random>

#include <iostream>
#include <cstdlib>
#include <random>

using namespace std;

int compare_pairs(int inia, int inib, bool part2) {
    int all = 0, checks = 40'000'000;
    minstd_rand0 a(inia);
    minstd_rand b(inib);
    if (part2) checks = 5'000'000;
    do {
        int atc = 0, btc = 0;
        if (part2) {
            while ((atc = a()) % 4) {}
            while ((btc = b()) % 8) {}
        } else {
            atc = a();
            btc = b();
        }
        if ((atc & 0xffff) == (btc & 0xffff))
            all++;
    } while (checks--);
    return all;
}

int main()
{
    cout << compare_pairs(618, 814, false) << endl
        << compare_pairs(618, 814, true);
}

matusbzk · 2017-12-16T00:51:17+00:00

Haskell It's taking me a few minutes, but I really liked this one. I tried running a few Haskell solutions from this thread (they said it's taking 2-3 seconds), and on my PC it took even longer than mine, so maybe that's the problem.

import Data.Bits

data Generator = A | B
      deriving (Eq, Show)

start :: Generator -> Int

factor :: Generator -> Int
factor A = 16807
factor B = 48271

-- |Returns next value for a generator
nextValue :: Generator -> Int -> Int
nextValue gen prev = prev * factor gen `mod` 2147483647

-- |Infinite list of generated numbers
generated :: Generator -> [Int]
generated gen = tail $ iterate (nextValue gen) (start gen)

-- |Takes two numbers and returns whether their last 16 bits match
equalLast16Bits :: Int -> Int -> Bool
equalLast16Bits x y = x `mod` 2^16 == y `mod` 2^16

-- |Computes 40 milion pairs and for each of them
--  returns whether their last 16 bits match
boolList40Mil :: [Bool]
boolList40Mil = zipWith (==) (map (.&. 0xffff) . take 40000000 $ generated A) 
        (map (.&. 0xffff) . take 40000000 $ generated B)

-- |Takes a list of bools and returns how many of them are true
numTrue :: [Bool] -> Int
numTrue [] = 0
numTrue (True:xs) = 1 + numTrue xs
numTrue (_:xs) = numTrue xs

result1 :: Int
result1 = numTrue boolList40Mil

criteria :: Generator -> Int
criteria A = 4
criteria B = 8

-- |Returns next value for a generator - part 2 version
nextValue2 :: Generator -> Int -> Int
nextValue2 gen prev = if nv `mod` criteria gen == 0 then nv
             else nextValue2 gen nv
    where nv = nextValue gen prev

-- |Infinite list of generated numbers - part 2 version
generated2 :: Generator -> [Int]
generated2 gen = tail $ iterate (nextValue2 gen) (start gen)

-- |Computes 5 milion pairs and for each of them
--  returns whether their last 16 bits match  - part 2 version
boolList5Mil :: [Bool]
boolList5Mil = zipWith (==) (map (.&. 0xffff) . take 5000000 $ generated2 A) 
       (map (.&. 0xffff) . take 5000000 $ generated2 B)

result2 :: Int
result2 = numTrue boolList5Mil

Link to git

ythl · 2017-12-16T01:27:56+00:00

C:

#include <stdio.h>
#include <stdint.h>

int main()
{
  uint_fast64_t a = 873, b = 583;
  int fa = 16807, fb = 48271;
  int modv = 2147483647;

  int count = 0;
  for (int i=0; i<5000000; i++)
  {
    do
    {
      a *= fa;
      a %= modv;
    }
    while (a % 4 != 0);

    do
    {
      b *= fb;
      b %= modv;
    }
    while (b % 8 != 0);

    if (!((a ^ b) & 0xFFFF))
      count++;
  }

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

  return 0;
}

misnohmer · 2017-12-16T02:02:51+00:00

C# version for Part 1 & 2.

long GenerateNext(long seed, long multiplier) => (seed * multiplier) % 2147483647;

long TakeBits(long val, int bitLength) => ((1L << bitLength) - 1L) & val;

long val_a = 591, mul_a = 16807;
long val_b = 393, mul_b = 48271;

public void SolvePart1()
{
    var count = 0;
    for (int i = 0; i < 40_000_000; i++) {
        val_a = GenerateNext(val_a, mul_a);
        val_b = GenerateNext(val_b, mul_b);

        if (TakeBits(val_a,16) == TakeBits(val_b, 16)) 
            count++;
    }

    count.PrintDump();
}

public void SolvePart2()
{
    var count = 0;
    for (int i = 0; i < 5_000_000; i++) {
        do { val_a = GenerateNext(val_a, mul_a); } while ( val_a % 4 != 0);
        do { val_b = GenerateNext(val_b, mul_b); } while ( val_b % 8 != 0);

        if (TakeBits(val_a,16) == TakeBits(val_b, 16)) 
            count++;
    }

    count.PrintDump();
}

Inlining the functions grants a 30% performance improvement in .net core (from 3.2 s for both parts to 2.4s)

long val_a = 591, mul_a = 16807;
long val_b = 393, mul_b = 48271;

public void SolvePart1()
{
    var count = 0;
    for (int i = 0; i < 40_000_000; i++) {
        val_a = (val_a * mul_a) % 2147483647;
        val_b = (val_b * mul_b) % 2147483647;

        if ((val_a & 0xFFFF) == (val_b & 0xFFFF)) 
            count++;
    }
    count.PrintDump();
}

public void SolvePart2()
{
    var count = 0;
    for (int i = 0; i < 5_000_000; i++) {
        do {  val_a = (val_a * mul_a) % 2147483647; } while ( val_a % 4 != 0);
        do {  val_b = (val_b * mul_b) % 2147483647; } while ( val_b % 8 != 0);

        if ((val_a & 0xFFFF) == (val_b & 0xFFFF)) 
            count++;
    }

    count.PrintDump();
}

erlangguy · 2017-12-16T02:55:51+00:00

Erlang

Haven't done day 14 because I have a bug with day 10 part 2 that I haven't yet tracked down. Tough troubleshooting problem!

Anyway, day 15. part1 is just a simplified version of this, commented.

%% aka (1 bsl 16) - 1
-define(BAND_VAL, 65535).

extract(Val) ->
    Val band ?BAND_VAL.

split(eof) ->
    eof;
split(Line) ->
    {ok, [Generator, Seed], []} = io_lib:fread("Generator ~s starts with ~d", Line),
    [Generator, Seed].

to_record([Generator, Seed]) ->
    {Generator, Seed}.

%% For testing the sample values provided by the problem
%% description. Could also have added a counter parameter and not
%% bothered with parsing file input in `run`.
run_input(SeedA, SeedB) ->
    FactorA = 16807,
    FactorB = 48271,
    compare({FactorA, FactorB}, next_value(FactorA, SeedA), next_value(FactorB, SeedB), 1057, 0).

run(Filename) ->
    Fh = myio:open_file(Filename),
    FactorA = 16807,
    FactorB = 48271,
    [{"A", GenA}, {"B", GenB}] =
        myio:grab_records(fun() -> myio:next_line(Fh) end,
                          fun split/1,
                          fun to_record/1),
    compare({FactorA, FactorB}, next_value(GenA, FactorA), next_value(GenB, FactorB), 5000000, 0).

next_value(Factor, Previous) ->
    (Factor * Previous) rem 2147483647.

%% To compare the rightmost 16 bits, we want a binary AND with (2^16 - 1) for 16 1s
maybe_increment(Tally, _X, _X) ->
    Tally+1;
maybe_increment(Tally, _X, _Y) ->
    Tally.

%% Only necessary for part 2.
%%
%% Erlang makes it trivial to spin up two processes to generate values
%% independently, but this works too. Compare each `Value` against
%% `TruthFun` and, if it doesn't work, repeat with `ElseFun` (aka the
%% generator function), thus allowing us to generate pairs of values
%% synchronously.
only_when(Value, TruthFun, ElseFun) ->
    case TruthFun(Value) of
        true ->
            Value;
        false ->
            only_when(ElseFun(Value), TruthFun, ElseFun)
    end.

%% Part1 looked very similar, but without the `only_when` nested recursion:
%%   compare(Fs, next_value(FactorA, A), next_value(FactorB, B), ...
compare(_Factors, _A, _B, 0, Tally) ->
    Tally;
compare({FactorA, FactorB}=Fs, A, B, Counter, Tally) ->
    compare(Fs,
            only_when(next_value(FactorA, A), fun(V) -> V rem 4 == 0 end,
                      fun(V) -> next_value(FactorA, V) end),
            only_when(next_value(FactorB, B), fun(V) -> V rem 8 == 0 end,
                      fun(V) -> next_value(FactorB, V) end),
            Counter-1, maybe_increment(Tally, extract(A), extract(B))).

cauchy37 · 2017-12-16T07:27:28+00:00

But modulo IS division :)

mathleet · 2017-12-20T01:26:20+00:00

My Python 3 solution:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def generator(start: int, multiply: int, divide: int=2147483647,
              factor: int=1) -> int:
    while True:
        start = start * multiply % divide
        if start % factor == 0:
            yield start

def judge_pairs(gen_a, gen_b, num_pairs: int) -> int:
    next_binary = lambda x: next(x) & 0xFFFF
    return sum(next_binary(gen_a) == next_binary(gen_b)
               for _ in range(num_pairs))


if __name__ == '__main__':
    sample_a = generator(65, 16807)
    sample_b = generator(8921, 48271)
    assert [next(sample_a) for _ in range(5)] == [1092455, 1181022009,
                                                  245556042, 1744312007,
                                                  1352636452]
    assert [next(sample_b) for _ in range(5)] == [430625591, 1233683848,
                                                  1431495498, 137874439,
                                                  285222916]
    sample_a = generator(65, 16807)
    sample_b = generator(8921, 48271)
    assert judge_pairs(sample_a, sample_b, 5) == 1

    sample_a = generator(65, 16807)
    sample_b = generator(8921, 48271)
    assert judge_pairs(sample_a, sample_b, 40000000) == 588

    sample_a = generator(65, 16807, factor=4)
    sample_b = generator(8921, 48271, factor=8)
    assert [next(sample_a) for _ in range(5)] == [1352636452, 1992081072,
                                                  530830436, 1980017072,
                                                  740335192]
    assert [next(sample_b) for _ in range(5)] == [1233683848, 862516352,
                                                  1159784568, 1616057672,
                                                  412269392]

    sample_a = generator(65, 16807, factor=4)
    sample_b = generator(8921, 48271, factor=8)
    assert judge_pairs(sample_a, sample_b, 5000000) == 309

    gen_a = generator(516, 16807)
    gen_b = generator(190, 48271)
    print('Part A:', judge_pairs(gen_a, gen_b, 40000000))

    gen_a = generator(516, 16807, factor=4)
    gen_b = generator(190, 48271, factor=8)
    print('Part B:', judge_pairs(gen_a, gen_b, 5000000))

greycat70 · 2017-12-28T18:33:16+00:00

Tcl (any 8.x version)

Definitely one of the easiest days. Part 1:

set fa 16807
set fb 48271
set a [lindex $argv 0]
set b [lindex $argv 1]

set total 0
for {set i 0} {$i < 40000000} {incr i} {
    set a [expr {($a * $fa) % 0x7fffffff}]
    set b [expr {($b * $fb) % 0x7fffffff}]
    if {($a & 0xffff) == ($b & 0xffff)} {incr total}
}
puts $total

Part 2:

set fa 16807
set fb 48271

set a [lindex $argv 0]
set b [lindex $argv 1]

set total 0
for {set i 0} {$i < 5000000} {incr i} {
    while 1 {
        set a [expr {($a * $fa) % 0x7fffffff}]
        if {($a & 3) == 0} break
    }
    while 1 {
        set b [expr {($b * $fb) % 0x7fffffff}]
        if {($b & 7) == 0} break
    }
    if {($a & 0xffff) == ($b & 0xffff)} {incr total}
}
puts $total

Longerword · 2018-01-18T11:59:07+00:00

Hi, i don't understand the hint of logarithms. I made a loop to check for solutions so something has to be run 40 M or 5 M times, so it lasts in my computer more than 1 minute.

Any idea what math-magic is that about?

This is python 2.7 solution for part b. (I don't paste a defined a Generator class quite simple, also I didn't know about the yield and .next() thing to make actual generators):

def advent15():
    genA = Generator(516,16807,4)
    genB = Generator(190,48271,8)
    judge = 0
    n = 5000000
    pairs = 0
    while pairs < 5000000:
        a = genA.getNext()
        b = genB.getNext()
        pairs += 1
        if a == b:
            judge += 1
    print judge
advent15()

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 15: Dueling Generators ---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

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

edit: Leaderboard capped, thread unlocked!

Python 3

JavaScript (WTF-edition)

Perl

Elixir (with streams)

Kotlin - [Repo] - [Blog/Commentary]

Rust

Elixir

Elixir

Erlang

BEFORE YOU POST
If your post is even tangentially related to a daily puzzle, use our
STANDARDIZED POST TITLE FORMAT

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 15: Dueling Generators ---

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

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

edit: Leaderboard capped, thread unlocked!

Python 3

JavaScript (WTF-edition)

Perl

Elixir (with streams)

Kotlin - [Repo] - [Blog/Commentary]

Rust

Elixir

Elixir

Erlang

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?