require_relative 'util'

# --- Day 15: Dueling Generators ---

# Here, you encounter a pair of dueling generators. The generators,
# called generator A and generator B, are trying to agree on a
# sequence of numbers. However, one of them is malfunctioning, and so
# the sequences don't always match.

# As they do this, a judge waits for each of them to generate its next
# value, compares the lowest 16 bits of both values, and keeps track
# of the number of times those parts of the values match.

# The generators both work on the same principle. To create its next
# value, a generator will take the previous value it produced,
# multiply it by a factor (generator A uses 16807; generator B uses
# 48271), and then keep the remainder of dividing that resulting
# product by 2147483647. That final remainder is the value it produces
# next.

# To calculate each generator's first value, it instead uses a
# specific starting value as its "previous value" (as listed in your
# puzzle input).

# For example, suppose that for starting values, generator A uses 65,
# while generator B uses 8921. Then, the first five pairs of generated
# values are:

#     --Gen. A--  --Gen. B--
#        1092455   430625591
#     1181022009  1233683848
#      245556042  1431495498
#     1744312007   137874439
#     1352636452   285222916

# In binary, these pairs are (with generator A's value first in each pair):

#     00000000000100001010101101100111
#     00011001101010101101001100110111

#     01000110011001001111011100111001
#     01001001100010001000010110001000

#     00001110101000101110001101001010
#     01010101010100101110001101001010

#     01100111111110000001011011000111
#     00001000001101111100110000000111

#     01010000100111111001100000100100
#     00010001000000000010100000000100

# Here, you can see that the lowest (here, rightmost) 16 bits of the
# third value match: `1110001101001010`. Because of this one match,
# after processing these five pairs, the judge would have added only 1
# to its total.

# To get a significant sample, the judge would like to consider 40
# million pairs. (In the example above, the judge would eventually
# find a total of 588 pairs that match in their lowest 16 bits.)

# After 40 million pairs, what is the judge's final count?

def make_generator(start, factor)
  Enumerator.new do |y|
    start = start
    loop do
      result = (start * factor) % 2_147_483_647
      y << result
      start = result
    end
  end
end

def lowest(i)
  i & (2**16 - 1)
end

def judge(a, b, rounds)
  matches = 0
  rounds.times do
    matches += 1 if lowest(a.next) == lowest(b.next)
  end
  matches
end

input = File.open('15.txt', &:read).scan(/\d+/).map(&:to_i)

def easy(input, rounds)
  a = make_generator(input[0], 16_807)
  b = make_generator(input[1], 48_271)
  judge(a, b, rounds)
end

assert(easy([65, 8_921], 5) == 1)
assert(easy([65, 8_921], 40_000_000) == 588)
puts "easy(input, 40_000_000): #{easy(input, 40_000_000)}"

# --- Part Two ---

# In the interest of trying to align a little better, the generators
# get more picky about the numbers they actually give to the judge.

# They still generate values in the same way, but now they only hand a
# value to the judge when it meets their criteria:

# - Generator A looks for values that are multiples of 4.
# - Generator B looks for values that are multiples of 8.

# Each generator functions completely independently: they both go
# through values entirely on their own, only occasionally handing an
# acceptable value to the judge, and otherwise working through the
# same sequence of values as before until they find one.

# The judge still waits for each generator to provide it with a value
# before comparing them (using the same comparison method as
# before). It keeps track of the order it receives values; the first
# values from each generator are compared, then the second values from
# each generator, then the third values, and so on.

# Using the example starting values given above, the generators now
# produce the following first five values each:

#     --Gen. A--  --Gen. B--
#     1352636452  1233683848
#     1992081072   862516352
#      530830436  1159784568
#     1980017072  1616057672
#      740335192   412269392

# These values have the following corresponding binary values:

#     01010000100111111001100000100100
#     01001001100010001000010110001000

#     01110110101111001011111010110000
#     00110011011010001111010010000000

#     00011111101000111101010001100100
#     01000101001000001110100001111000

#     01110110000001001010100110110000
#     01100000010100110001010101001000

#     00101100001000001001111001011000
#     00011000100100101011101101010000

# Unfortunately, even though this change makes more bits similar on
# average, none of these values' lowest 16 bits match. Now, it's not
# until the 1056th pair that the judge finds the first match:

#     --Gen. A--  --Gen. B--
#     1023762912   896885216

#     00111101000001010110000111100000
#     00110101011101010110000111100000

# 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?

def make_picky_generator(start, factor, multiples_of)
  Enumerator.new do |y|
    start = start
    loop do
      result = (start * factor) % 2_147_483_647
      y << result if (result % multiples_of).zero?
      start = result
    end
  end
end

def hard(input, rounds)
  a = make_picky_generator(input[0], 16_807, 4)
  b = make_picky_generator(input[1], 48_271, 8)
  judge(a, b, rounds)
end

assert(hard([65, 8_921], 1056) == 1)
puts "hard(input, 5_000_000): #{hard(input, 5_000_000)}"