Day 6: Wait For It

import json
from copy import copy


class Solver:

    def __init__(self):
        with open('info2.json', 'r', encoding='utf-8') as f:
            self.data = json.load(f)

    def run(self):
        product = 1
        for race in self.data['races']:
            ways = 0
            for i in range(race['time']):
                if i * (race['time'] - i) > race['distance']:
                    ways += 1
            product *= max(ways, 1)
        return product


if __name__ == '__main__':
    print(Solver().run())

DROP FUNCTION IF EXISTS parse;
DROP FUNCTION IF EXISTS solve1;
DROP FUNCTION IF EXISTS solve1_arr;
DROP TYPE IF EXISTS problem;

CREATE TYPE problem AS
(
    time     BIGINT,
    distance BIGINT
);

CREATE FUNCTION parse(input TEXT) RETURNS problem[] AS
$$
DECLARE
    inputTrim text   := trim(both E'\r\n' from input);
    lines     text[] := regexp_split_to_array(inputTrim, '\n');
    times     text[] := array(SELECT regexp_matches(lines[1], '\d+', 'g'));
    distances text[] := array(SELECT regexp_matches(lines[2], '\d+', 'g'));
    out       problem[];
    i         BIGINT;
BEGIN
    FOR i IN 1..array_length(times, 1)
        LOOP
            out = array_append(out, (times[i][1], distances[i][1])::problem);
        END LOOP;
    RETURN out;
END
$$ LANGUAGE plpgsql;

CREATE FUNCTION solve1(problem) RETURNS BIGINT AS
$$
DECLARE
    hold_duration           BIGINT;
    remaining_duration BIGINT;
    travel_distance BIGINT;
    winning_ways BIGINT := 0;
BEGIN
    FOR hold_duration IN 1..($1.time-1)
    LOOP
        remaining_duration = $1.time - hold_duration;
        travel_distance = remaining_duration * hold_duration;
        IF travel_distance > $1.distance THEN
            winning_ways = winning_ways + 1;
        end if;
    END LOOP;
    RETURN winning_ways;
END
$$ LANGUAGE plpgsql;

CREATE FUNCTION solve1_arr(problem[]) RETURNS BIGINT AS
$$
DECLARE
    acc BIGINT := 1;
    problem problem;
BEGIN
    FOREACH problem IN ARRAY $1
    LOOP
        -- RAISE NOTICE '%', to_json(times);
        acc = acc * solve1(problem);
    END LOOP;
    RETURN acc;
END
$$ LANGUAGE plpgsql;

-- Part 1
-- SELECT solve1_arr((parse($input$
-- Time:      7  15   30
-- Distance:  9  40  200
-- $input$)));
-- SELECT solve1_arr((parse($input$
-- Time:        46     85     75     82
-- Distance:   208   1412   1257   1410
-- $input$)));

-- Part 2
SELECT solve1_arr((parse($input$
Time:        46857582
Distance:   208141212571410
$input$)));

Apparently SQL array starts from 1. That wasted me an hour.

"""Advent of Code 2023 Day 6"""
from collections import Counter

with open("input.txt", 'r') as file:
    data = file.read().strip().split('\n')

times, distances = ([int(j) for j in i.split() if j.isdigit()] for i in data)

# Part 1
t_C = Counter()

for i in range(len(times)): # Iterating through each index in list of record times
    for j in range(times[i]): # Trying each amount of time holding the button
        time_held = speed = j # j is time held in ms and speed in units/ms
        time_left =  times[i] - time_held # Time left when releasing button
        distance_travelled = speed * time_left
        if distance_travelled > distances[i]:
            t_C[times[i]] += 1 # Add to counter for the given time if distance record is set
part_1 = 1 # Multiply all counter values together...gotta initialize and gotta multiply so =1
for i in t_C.values():
    part_1 *= i
print(f"Part 1: {part_1}")

#Part 2
t = int("".join(str(x) for x in times))
d = int("".join(str(y) for y in distances))

# Answer is really x^2 - tx + d
import math
part_2 = math.floor(t + math.sqrt(t**2 - 4*d)/2) - math.floor(t - math.sqrt(t**2 - 4*d)/2)
print(f"Part 2: {part_2}")

#!/usr/bin/env pypy3

product = 1
for t, d in zip(*(map(int, line.split(':')[1].split()) for line in open(0))):
    product *= sum(x * t - x * x > d for x in range(1, t))
print(product)

#!/usr/bin/env pypy3

t, d = map(int, (line.split(':')[1].replace(' ', '') for line in open(0)))
print(sum(x * t - x * x > d for x in range(1, t)))

I suppose if you naively implemented the race as an actual simulation, instead of just computing the distance, maybe it would be harder? But even then, part 2 just scales linearly, so it was just ... change the input and rerun it?

package main

import (
	h "aoc2023/internal/helpers"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {

	d := &Day6{}

	err := h.Dispatch(os.Args, d)
	if err != nil {
		fmt.Println("Error:", err)
		os.Exit(1)
	}

}

func RaceDistance(raceLength int, holdTime int) int {
	return holdTime * (raceLength - holdTime)
}

func WaysToWin(raceLength int, record int) int {
	winWays := 0
	for i := 0; i < raceLength; i++ {
		dist := RaceDistance(raceLength, i)
		if dist > record {
			winWays += 1
		}
	}
	return winWays
}

type Day6 struct {
	lines     []string
	times     []int
	distances []int
}

func (d *Day6) Setup(filename string) {
	fmt.Println("Setup")
	d.lines = h.ReadFileToLines(filename)

	d.times = h.ParseIntList(strings.Split(d.lines[0], ":")[1], " ")
	d.distances = h.ParseIntList(strings.Split(d.lines[1], ":")[1], " ")

	fmt.Println("Times:", d.times)
	fmt.Println("DIstances:", d.distances)
}

func (d *Day6) Part1() {
	fmt.Println("Part 1")
	waysProd := 1
	for index := 0; index < len(d.times); index++ {
		raceLength := d.times[index]
		record := d.distances[index]
		winWays := WaysToWin(raceLength, record)
		fmt.Println("WinWays", winWays)
		waysProd *= winWays
	}
	fmt.Println("WinWays product", waysProd)
}

func CombineVals(input string) int {
	output := ""
	for _, c := range input {
		if c >= '0' && c <= '9' {
			output += string(c)
		}
	}
	intVal, err := strconv.Atoi(output)
	h.Assert(err == nil, "error not nil")
	return intVal
}

func (d *Day6) Part2() {
	fmt.Println("Part 2")
	raceLength := CombineVals(d.lines[0])
	record := CombineVals(d.lines[1])
	fmt.Println("raceLength", raceLength)
	fmt.Println("record", record)

	winWays := WaysToWin(raceLength, record)
	fmt.Println("WinWays", winWays)
}

# Advent of Code 2023
# Day 6: Wait For It

from functools import reduce
from operator import mul

with open("inputs/day_6.txt") as file:
    line_1 = next(file)
    line_2 = next(file)

    races_part_1 = list(zip(
        (int(n) for n in line_1.split()[1:]),
        (int(n) for n in line_2.split()[1:])
    ))

    race_part_2 = (
        int("".join(line_1.split()[1:])),
        int("".join(line_2.split()[1:]))
    )

def find_ways(race):
    ways = 0

    for hold_duration in range(1, race[0]):
        distance = (race[0] - hold_duration) * hold_duration

        if distance > race[1]:
            ways += 1

    return ways

print(f"Part 1: {reduce(mul, (find_ways(race) for race in races_part_1))}")
print(f"Part 2: {find_ways(race_part_2)}")

=ARRAYFORMULA(
  IF(F2=FALSE,,
   PRODUCT(
    BYCOL(
     H2:K2,
     LAMBDA(
      x,
      COUNTIFS(
       (x-SEQUENCE(100))*SEQUENCE(100),">"&OFFSET(x,1,0),
       SEQUENCE(100),"<="&x))))))

=INT(
  SQRT(
   REGEXREPLACE(A2,"\D",)^2-
   4*REGEXREPLACE(A3,"\D",)))

package aoc2023

object Day6 {
    fun parse(input: String): Pair<List<Int>, List<Int>> {
        fun intsOf(s: String) = Regex("""\d+""").findAll(s).map { it.value.toInt() }
        val (times, dists) = input.trim().lines().map { intsOf(it).toList() }.toList()
        return Pair(times, dists)
    }

    fun part1(input: String): Int {
        val (times, dists) = parse(input)
        fun wins(time0: Int, dist0: Int) = (0..time0).fold(0) { acc, time ->
            if (time * (time0 - time) > dist0) acc + 1 else acc
        }
        return times.indices.map { wins(times[it], dists[it]) }.reduce { x, y -> x * y }
    }

    fun part2(input: String): Long {
        val (times, dists) = parse(input)
        val time0 = times.joinToString("") { it.toString() }.toLong()
        val dist0 = dists.joinToString("") { it.toString() }.toLong()
        fun wins(time0: Long, dist0: Long) = (0..time0).fold(0L) { acc, time ->
            if (time * (time0 - time) > dist0) acc + 1 else acc
        }
        return wins(time0, dist0)
    }
}

Not much to say... this was pretty straightforward.

def race(charge_time: int, total_time: int) -> int:
    return charge_time * (total_time - charge_time)

def main(stream=sys.stdin) -> None:
    times     = [int(t) for t in stream.readline().split(':')[-1].split()]
    distances = [int(d) for d in stream.readline().split(':')[-1].split()]
    product   = 1

    for time, distance in zip(times, distances):
        ways     = [c for c in range(1, time + 1) if race(c, time) > distance]
        product *= len(ways)

    print(product)

Probably could have done some math, but didn't need to :]

def race(charge_time: int, total_time: int):
    return charge_time * (total_time - charge_time)

def main(stream=sys.stdin) -> None:
    time     = int(''.join(stream.readline().split(':')[-1].split()))
    distance = int(''.join(stream.readline().split(':')[-1].split()))
    ways     = [c for c in range(1, time + 1) if race(c, time) > distance]
    print(len(ways))

use nom::{
    bytes::complete::tag,
    character::complete::{newline, space0, space1},
    combinator::eof,
    multi::separated_list1,
    IResult,
};

#[derive(Debug)]
pub struct Race {
    pub time: usize,
    pub distance: usize,
}

pub fn parse(input: &str) -> IResult<&str, Vec<Race>> {
    let (input, times) = parse_times(input)?;
    let (input, distances) = parse_distances(input)?;
    let (input, _) = eof(input)?;

    Ok((
        input,
        times
            .into_iter()
            .zip(distances)
            .map(|(t, d)| Race {
                time: t,
                distance: d,
            })
            .collect::<Vec<_>>(),
    ))
}

fn parse_times(input: &str) -> IResult<&str, Vec<usize>> {
    let (input, _) = tag("Time:")(input)?;
    let (input, _) = space1(input)?;
    let (input, times) = separated_list1(space1, parse_usize)(input)?;
    let (input, _) = newline(input)?;

    Ok((input, times))
}

fn parse_distances(input: &str) -> IResult<&str, Vec<usize>> {
    let (input, _) = tag("Distance:")(input)?;
    let (input, _) = space1(input)?;
    let (input, distances) = separated_list1(space1, parse_usize)(input)?;
    let (input, _) = newline(input)?;
    let (input, _) = space0(input)?;

    Ok((input, distances))
}

fn parse_usize(input: &str) -> IResult<&str, usize> {
    let (input, num) = nom::character::complete::digit1(input)?;
    let num = num.parse::<usize>().unwrap();

    Ok((input, num))
}

mod parser;

use parser::Race;

fn main() {
    println!("Part 1: {}", part1(include_str!("../input.txt")));
    println!(
        "Part 2: {}",
        // I was lazy and just manually edited the input
        part2(
            "Time:        58996469
Distance:   478223210191071
"
        )
    );
}

fn part1(input: &str) -> usize {
    let races = parser::parse(input).unwrap().1;

    races
        .iter()
        .map(winning_race_strategies)
        .map(|(min, max)| max - min + 1)
        .product()
}

fn part2(input: &str) -> usize {
    part1(input)
}

fn boat_distance(race: &Race, button_held_for: usize) -> usize {
    let speed = button_held_for;
    let remaining_time = race.time - button_held_for;

    speed * remaining_time
}

fn bisect(race: &Race, lower: usize, upper: usize, win: bool) -> usize {
    if lower >= upper {
        return lower;
    }

    let lower_dist = boat_distance(race, lower);
    let upper_dist = boat_distance(race, upper);
    let lower_wins = lower_dist > race.distance;
    let upper_wins = upper_dist > race.distance;

    if upper_wins == win && lower_wins == win {
        return lower;
    }

    let mid = (lower + upper) / 2;
    let mid_dist = boat_distance(race, mid);
    let mid_wins = mid_dist > race.distance;

    if mid_wins == win {
        if lower_wins == win {
            return bisect(race, mid + 1, upper, win);
        } else {
            return bisect(race, lower + 1, mid, win);
        }
    }

    bisect(race, mid + 1, upper, win)
}

fn winning_race_strategies(race: &Race) -> (usize, usize) {
    let min_hold = bisect(race, 0, race.time, true);
    let max_hold = bisect(race, min_hold, race.time, false) - 1;

    (min_hold, max_hold)
}

This took an embarassingly long time to write though. Off-by-one errors in a bisection search are nasty...

Huh. After yesterday's problem it didn't even occur to me that I could just brute force this, so I wrote a recursive bisection search. 478223210191071 seemed like a scary-large number to brute-force, but I guess computers are fast...

Benchmark 1: target/release/day-06
  Time (mean ± σ):       1.1 ms ±   0.1 ms    [User: 0.3 ms, System: 0.7 ms]
  Range (min … max):     0.4 ms …   1.9 ms    4090 runs

import re


class Race:
    def __init__(self, time, dist):
        self.time = time
        self.dist = dist

    def __repr__(self, options):
        return f'To win, hold the button for {[x for x in options]} second(s)'

    def best_options(self):
        options = []
        for x in range(self.time):
            if x * (self.time - x) > self.dist:
                options.append(x)
        return options

def part1(lines):
    print(f"Part 1!")
    lines = lines.strip().split('\n')
    times, dist = [re.findall(r'(\d+)', s) for s in lines]
    times = list(map(int, times))
    dist = list(map(int, dist))
    races = []
    for x in range(len(times)):
        races.append(Race(times[x], dist[x]))
    winners = 1
    for race in races:
        winners *= len(race.best_options())
    print(f"Result: {winners}")


def part2(lines):
    print(f"Part 2!")
    lines = lines.strip().split('\n')
    times, dist = [re.findall(r'(\d+)', s) for s in lines]
    times = int(''.join(times))
    dist = int(''.join(dist))
    race = Race(times, dist)
    winners = len(race.best_options())
    print(f"Result: {winners}")


def openFile():
    return open("input.txt", "r").read()


def main():
    f = openFile()
    part1(f)
    part2(f)


if __name__ == '__main__':
    main()

import { getInput } from "./input";
import * as utils from "./utils";

(async () => {
  const input = getInput();
  const lines = input.split("\n");

  const times = utils.ints(lines[0]);
  const distance = utils.ints(lines[1]);

  let total = 1;

  for (let i = 0; i < times.length; i++) {
    const time = times[i];
    const dist = distance[i];
    let wins = 0;

    for (let charge = 1; charge < time; charge++) {
      const rem = time - charge;
      if (charge * rem > dist) {
        wins++;
      }
    }

    total *= wins;
  }

  console.log(total);
})();

import { getInput } from "./input";
import * as utils from "./utils";

(async () => {
  const input = getInput();
  const lines = input.split("\n");

  const times = [
    parseInt(
      utils
        .ints(lines[0])
        .map((x) => x.toString())
        .join(""),
    ),
  ];
  const distance = [
    parseInt(
      utils
        .ints(lines[1])
        .map((x) => x.toString())
        .join(""),
    ),
  ];

  let total = 1;

  for (let i = 0; i < times.length; i++) {
    const time = times[i];
    const dist = distance[i];
    let wins = 0;

    for (let charge = 1; charge < time; charge++) {
      const rem = time - charge;
      if (charge * rem > dist) {
        wins++;
      }
    }

    total *= wins;
  }

  console.log(total);
})();

use std::env;
use std::io::{self, prelude::*};
use std::fs::File;

fn solve(input: &str) -> io::Result<()> {
    // File handling
    let input_str = std::fs::read_to_string(input).unwrap();
    let input_str = input_str.trim();
    let input: Vec<_> = input_str.lines().collect();

    // Part 1 Inputs
    let times: Vec<_> = input[0]
        .split_whitespace()
        .skip(1)
        .map(|x| x.parse::<usize>().unwrap())
        .collect();
    let distances: Vec<_> = input[1]
        .split_whitespace()
        .skip(1)
        .map(|x| x.parse::<usize>().unwrap())
        .collect();

    // Part 1
    let mut part1 = 1;
    for (time,dist) in times.iter().zip(distances.iter()) {
        let ways = (1..*time)
            .into_iter()
            .filter(|hold| hold * (time - hold) > *dist)
            .count();
        if ways > 0 { part1 *= ways; }
    }
    println!("Part 1: {part1}"); // 800280

    // Part 2 Inputs
    let time_p2 = times
        .iter()
        .map(|x| format!("{x}"))
        .collect::<Vec<_>>()
        .concat()
        .parse::<usize>()
        .unwrap();
    let dist_p2 = distances
        .iter()
        .map(|x| format!("{x}"))
        .collect::<Vec<_>>()
        .concat()
        .parse::<usize>()
        .unwrap();

    // Part 2 Solve
    let part2 = (1..time_p2)
        .into_iter()
        .filter(|hold| hold * (time_p2 - hold) > dist_p2)
        .count();
    println!("Part 2: {part2}"); // 45128024

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

defmodule AdventOfCode.Solution.Year2023.Day06 do
  import Integer, only: [is_even: 1]

  def part1(input) do
    input
    |> parse_p1()
    |> Enum.map(&count_wins/1)
    |> Enum.product()
  end

  def part2(input) do
    input
    |> parse_p2()
    |> count_wins()
  end

  defp parse_p1(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(fn line ->
      line
      |> String.split()
      |> Enum.drop(1)
      |> Enum.map(&String.to_integer/1)
    end)
    |> Enum.zip()
  end

  defp parse_p2(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(fn line ->
      line
      |> String.split(":")
      |> Enum.at(1)
      |> String.replace(" ", "")
      |> String.to_integer()
    end)
    |> List.to_tuple()
  end

  defp count_wins({t, d}) do
    half_t = div(t, 2)
    n = binary_search_first_win(1, half_t, t, d)

    if is_even(t), do: 2 * (half_t - n) + 1, else: 2 * (half_t - n + 1)
  end

  defp binary_search_first_win(n_min, n_max, t, d) do
    n = div(n_min + n_max, 2)

    with {:n_wins_race?, true} <- {:n_wins_race?, n * (t - n) > d},
         n_sub1 = n - 1,
         {:n_sub1_loses_race?, true} <- {:n_sub1_loses_race?, n_sub1 * (t - n_sub1) <= d} do
      n
    else
      {:n_wins_race?, false} -> binary_search_first_win(n + 1, n_max, t, d)
      {:n_sub1_loses_race?, false} -> binary_search_first_win(n_min, n - 1, t, d)
    end
  end
end

#[derive(Debug)]
struct Race {
    time: usize,
    record: usize,
}

impl Race {
    fn num_solutions(&self) -> usize {
        let min = binary_search(0, self.time / 2 - 1, |val| {
            match (self.is_solution(val), self.is_solution(val + 1)) {
                (true, true) => Ordering::Greater,
                (false, false) => Ordering::Less,
                (false, true) => Ordering::Equal,
                (true, false) => unreachable!(),
            }
        });
        let max = binary_search(self.time / 2, self.time, |val| {
            match (self.is_solution(val), self.is_solution(val + 1)) {
                (true, true) => Ordering::Less,
                (false, false) => Ordering::Greater,
                (true, false) => Ordering::Equal,
                (false, true) => unreachable!(),
            }
        });
        let (max, min) = (max.expect("Max exists"), min.expect("Min exists"));
        max - min + 1
    }

    fn is_solution(&self, val: usize) -> bool {
        val * (self.time - val) > self.record
    }
}

impl From<(usize, usize)> for Race {
    fn from(val: (usize, usize)) -> Self {
        Self {
            time: val.0,
            record: val.1,
        }
    }
}

#[inline]
fn binary_search<F>(mut bottom: usize, mut top: usize, cond: F) -> Option<usize>
where
    F: Fn(usize) -> Ordering,
{
    while bottom < top {
        if top - bottom < 10 {
            return (bottom..=top).find(|i| cond(*i) == Ordering::Equal);
        } else {
            let mid = (top + bottom) / 2;
            match cond(mid) {
                Ordering::Less => bottom = mid - 1,
                Ordering::Greater => top = mid + 1,
                Ordering::Equal => return Some(mid),
            }
        }
    }
    None
}

fn parse_input(part: Puzzle) -> Result<Vec<Race>> {
    let input = load_input(6)?;
    let mut lines = input.lines();
    let times = lines
        .next()
        .and_then(|l| l.strip_prefix("Time:"))
        .ok_or("No line 1")?;
    let records = lines
        .next()
        .and_then(|l| l.strip_prefix("Distance:"))
        .ok_or("No line 2")?;
    match part {
        Puzzle::First => {
            let times = times
                .split_whitespace()
                .filter(|n| !n.is_empty())
                .map(parse_as::<usize>)
                .collect::<Result<Vec<usize>>>()?;
            let records = records
                .split_whitespace()
                .filter(|n| !n.is_empty())
                .map(parse_as::<usize>)
                .collect::<Result<Vec<usize>>>()?;
            Ok(times.into_iter().zip(records).map(Race::from).collect())
        }
        Puzzle::Second => {
            let time = parse_as::<usize>(&times.replace(' ', ""))?;
            let record = parse_as::<usize>(&records.replace(' ', ""))?;
            Ok(vec![(time, record).into()])
        }
    }
}

fn first() -> Result<String> {
    let races = parse_input(Puzzle::First)?;
    let total = races
        .into_iter()
        .map(|race| race.num_solutions())
        .product::<usize>()
        .to_string();
    Ok(total)
}

fn second() -> Result<String> {
    let race = parse_input(Puzzle::Second)?.remove(0);
    Ok(race.num_solutions().to_string())
}