day_22.R

library(reticulate)
library(tidyverse)

# Define the Python function for evolving the secret number
py_run_string("
def evolve_secret(secret_number, steps):
    MODULO = 16777216
    secret_number = int(secret_number)  # Ensure the input is an integer
    steps = int(steps)  # Ensure steps are treated as an integer
    for _ in range(steps):
        # Step 1: Multiply by 64, XOR, prune
        secret_number = (secret_number * 64) ^ secret_number
        secret_number %= MODULO

        # Step 2: Divide by 32, floor, XOR, prune
        secret_number = (secret_number // 32) ^ secret_number
        secret_number %= MODULO

        # Step 3: Multiply by 2048, XOR, prune
        secret_number = (secret_number * 2048) ^ secret_number
        secret_number %= MODULO

    return secret_number
")

# List of initial secret numbers
initial_secrets <- as.integer(readLines("inputs/input22.txt"))


# Number of steps to evolve the secret numbers
steps <- 2000

# Part 1
results <- numeric(length(initial_secrets))

# Iterate over the initial secrets and call the Python function
for (i in seq_along(initial_secrets)) {
  results[i] <- py$evolve_secret(as.integer(initial_secrets[i]), as.integer(steps))
}

# Calculate the sum of the 2000th secret numbers
sum_2000th_secrets <- sum(results)

print(sum_2000th_secrets)

## Part 2

py_run_string("
def evolve_secret_optimized(secret_number, steps):
    MODULO = 16777216
    seen_states = {}
    cycle_start = None
    cycle_length = None

    # Initial state
    current_step = 0
    while current_step < steps:
        if secret_number in seen_states:
            # Cycle detected
            cycle_start = seen_states[secret_number]
            cycle_length = current_step - cycle_start
            break
        # Store the current state
        seen_states[secret_number] = current_step

        # Perform evolution
        secret_number = (secret_number * 64) ^ secret_number
        secret_number %= MODULO
        secret_number = (secret_number // 32) ^ secret_number
        secret_number %= MODULO
        secret_number = (secret_number * 2048) ^ secret_number
        secret_number %= MODULO

        current_step += 1

    # If a cycle was detected, skip redundant steps
    if cycle_length:
        remaining_steps = (steps - cycle_start) % cycle_length
        for _ in range(remaining_steps):
            secret_number = (secret_number * 64) ^ secret_number
            secret_number %= MODULO
            secret_number = (secret_number // 32) ^ secret_number
            secret_number %= MODULO
            secret_number = (secret_number * 2048) ^ secret_number
            secret_number %= MODULO

    return secret_number
")

py_run_string("
def evolve_secret_last_digit(secret_number, steps):
    MODULO = 16777216
    seen_states = {}
    cycle_start = None
    cycle_length = None

    # Keep track of last digit states
    last_digit = secret_number % 10
    current_step = 0

    while current_step < steps:
        state = (secret_number, last_digit)
        if state in seen_states:
            # Cycle detected
            cycle_start = seen_states[state]
            cycle_length = current_step - cycle_start
            break
        # Store the current state
        seen_states[state] = current_step

        # Perform evolution
        secret_number = (secret_number * 64) ^ secret_number
        secret_number %= MODULO
        secret_number = (secret_number // 32) ^ secret_number
        secret_number %= MODULO
        secret_number = (secret_number * 2048) ^ secret_number
        secret_number %= MODULO

        last_digit = secret_number % 10
        current_step += 1

    # If a cycle was detected, skip redundant steps
    if cycle_length:
        remaining_steps = (steps - cycle_start) % cycle_length
        for _ in range(remaining_steps):
            secret_number = (secret_number * 64) ^ secret_number
            secret_number %= MODULO
            secret_number = (secret_number // 32) ^ secret_number
            secret_number %= MODULO
            secret_number = (secret_number * 2048) ^ secret_number
            secret_number %= MODULO

            last_digit = secret_number % 10

    return last_digit
")

initial_secrets <- as.integer(readLines("inputs/input22.txt"))

# Number of steps to evolve the secret numbers
steps <- 2000

# Initialize variables for all secret numbers and prices
all_secret_numbers <- list()
all_prices <- list()
all_price_changes <- list()

# Generate secret numbers and compute prices and changes for each buyer
for (i in seq_along(initial_secrets)) {
  # Generate secret numbers using the optimized Python function
  secret_numbers <- py$evolve_secret_optimized(as.integer(initial_secrets[i]), as.integer(steps))
  all_secret_numbers[[i]] <- secret_numbers
  
  # Compute prices (ones digit of secret numbers)
  prices <- sapply(secret_numbers, function(x) x %% 10)
  all_prices[[i]] <- prices
  
  # Compute price changes (differences between consecutive prices)
  if (length(prices) > 1) {
    changes <- diff(prices)
  } else {
    changes <- numeric(0)
  }
  all_price_changes[[i]] <- changes
}

# Generate all unique 4-change sequences
all_sequences <- list()
for (changes in all_price_changes) {
  if (length(changes) >= 4) {
    embedded <- embed(changes, 4)
    all_sequences <- c(all_sequences, split(embedded, row(embedded)))
  }
}
all_sequences <- unique(all_sequences)

# Function to calculate total bananas for a given sequence
get_bananas_for_sequence <- function(sequence, price_changes, prices) {
  total_bananas <- 0
  for (i in seq_along(price_changes)) {
    changes <- price_changes[[i]]
    prices_i <- prices[[i]]
    if (length(changes) >= 4) {
      # Find the first occurrence of the sequence
      change_matrix <- embed(changes, 4)
      match_index <- which(rowSums(change_matrix == sequence) == 4)[1]
      if (!is.na(match_index)) {
        total_bananas <- total_bananas + prices_i[match_index + 4]  # Add the corresponding price
      }
    }
  }
  return(total_bananas)
}

# Evaluate all sequences to find the best one
most_bananas <- 0
best_sequence <- NULL

for (sequence in all_sequences) {
  bananas <- get_bananas_for_sequence(sequence, all_price_changes, all_prices)
  if (bananas > most_bananas) {
    most_bananas <- bananas
    best_sequence <- sequence
  }
}

# Output the results
cat("Maximum Bananas:", most_bananas, "\n")
cat("Best Sequence:", best_sequence, "\n")