Advent of Code 2023: ChatGPT-4 turbo edition

-module(part1).
-export([main/0]).

get_seed_list() ->
  [SeedLine, _] = [io:get_line(""), io:get_line("")],
  {_, [SeedNumsBin]} =
    re:run(SeedLine, "seeds: (.*)\n", [{capture, all_but_first, binary}]),
  lists:map(
    fun _(X) -> {Val, _} = string:to_integer(X), Val end,
    string:split(binary_to_list(SeedNumsBin), " ", all)
  ).

add_map(Acc, CurrentMap) ->
  case io:get_line("") of
    eof -> Acc ++ [CurrentMap];
    "\n" -> Acc ++ [CurrentMap];
    Line ->
      {_, Matches} =
        re:run(Line, "(\\d+) (\\d+) (\\d+)\n", [{capture, all_but_first, binary}]),
      [Dest, Source, Len] =
        lists:map(fun _(X) -> {Val, _} = string:to_integer(X), Val end, Matches),
      add_map(Acc, CurrentMap ++ [[Source, Source + Len - 1, Dest]])
  end.


get_map_list(Acc) ->
  case io:get_line("") of
    eof -> Acc;
    _ -> get_map_list(add_map(Acc, []))
  end.

get_next_id(CurrentId, []) -> CurrentId;
get_next_id(CurrentId, [[L, R, D] | _]) when (CurrentId >= L andalso CurrentId =< R) ->
  D + CurrentId - L;
get_next_id(CurrentId, [_ | T]) ->
  get_next_id(CurrentId, T).

iterate_seed(CurrentId, []) -> CurrentId;
iterate_seed(CurrentId, [Map | T]) ->
  NextId = get_next_id(CurrentId, Map),
  iterate_seed(NextId, T).


solve() ->
  Seeds = get_seed_list(),
  Maps = get_map_list([]),
  lists:foldl(
    fun _(A, B) -> erlang:min(A, B) end,
    23898895723587,
    lists:map(
      fun _(X) -> iterate_seed(X, Maps) end,
      Seeds
    )
  ).

main() ->
  R = solve(),
  io:format("~p~n", [R]).

-module(part2).
-export([main/0]).

get_seed_intervals([], Acc) -> Acc;
get_seed_intervals([Ls, Ds | T], Acc) ->
  [L, D] = lists:map(fun _(X) -> {Val, _} = string:to_integer(X), Val end, [Ls, Ds]),
  get_seed_intervals(T, [[L, L + D - 1, notfound] | Acc]).

get_seed_list() ->
  [SeedLine, _] = [io:get_line(""), io:get_line("")],
  {_, [SeedNumsBin]} =
    re:run(SeedLine, "seeds: (.*)\n", [{capture, all_but_first, binary}]),
  get_seed_intervals(
    string:split(binary_to_list(SeedNumsBin), " ", all),
    []
  ).

add_map(Acc, CurrentMap) ->
  case io:get_line("") of
    eof -> Acc ++ [CurrentMap];
    "\n" -> Acc ++ [CurrentMap];
    Line ->
      {_, Matches} =
        re:run(Line, "(\\d+) (\\d+) (\\d+)\n", [{capture, all_but_first, binary}]),
      [Dest, Source, Len] =
        lists:map(fun _(X) -> {Val, _} = string:to_integer(X), Val end, Matches),
      add_map(Acc, CurrentMap ++ [[Source, Source + Len - 1, Dest]])
  end.


get_map_list(Acc) ->
  case io:get_line("") of
    eof -> Acc;
    _ -> get_map_list(add_map(Acc, []))
  end.

add_nonempty_rems([], Acc) -> Acc;

add_nonempty_rems([[L, R, _] = I | T], Acc) when L =< R ->
  add_nonempty_rems(T, [I | Acc]);

add_nonempty_rems([_ | T], Acc) ->
  add_nonempty_rems(T, Acc).


replace_intervals([] , _, Acc) -> Acc;


replace_intervals([[SL, SR, _] = Seed | T1], [L, R, _] = Interval, Acc)
  when (SR < L orelse SL > R) ->
  replace_intervals(T1, Interval, [Seed | Acc]);

replace_intervals([[_, _, found] = Seed | T1], Interval, Acc) ->
  replace_intervals(T1, Interval, [Seed | Acc]);

replace_intervals([[SL, SR, notfound] | T1], [L, R, D] = Interval, Acc) ->
  [IL, IR] = [erlang:max(L, SL), erlang:min(R, SR)],
  NewInterval = [D + IL - L, D + IR - L, found],
  LeftRemainder = [SL, IL - 1, notfound],
  RightRemainder = [IR + 1, SR, notfound],
  ToAdd = add_nonempty_rems([LeftRemainder, RightRemainder], []),
  replace_intervals(
    ToAdd ++ T1,
    Interval,
    [NewInterval | Acc]
  ).

get_next_intervals(CurrentIntervals, []) ->
  [[X, Y, notfound] || [X, Y, _] <- CurrentIntervals];
get_next_intervals(CurrentIntervals, [MapInterval | T]) ->
  get_next_intervals(
    replace_intervals(CurrentIntervals, MapInterval, []),
    T
  ).

iterate_seed(CurrentIntervals, []) -> CurrentIntervals;
iterate_seed(CurrentIntervals, [Map | T]) ->
  iterate_seed(get_next_intervals(CurrentIntervals, Map), T).

solve() ->
  Seeds = get_seed_list(),
  Maps = get_map_list([]),
  Locations =
  lists:foldl(
    fun _(A, B) -> A ++ B end,
    [],
    lists:map(
      fun _(X) -> iterate_seed([X], Maps) end,
      Seeds
    )
  ),
  [MinVal, _, _] = lists:foldl(
    fun _([A, _, _], [B, _, _]) -> [erlang:min(A, B), 3, xd] end,
    [2934892358988132, 3, xd],
    Locations
  ),
  MinVal.

main() ->
  R = solve(),
  io:format("~w~n", [R]).

En la parte 2, imagino que intentaréis considerar intervalos de semillas cuando lo evalueis contra el map de turno, por ejemplo
[1, 3] vs {[1, 1] => [4, 4], [4, 10] => [14, 22], ...}

Nos daría que [1, 3] quedaría partido en [1, 1], que se iría a [4, 4], y en [2, 3], que se quedaría igual porque no hay map que lo lleve.

Estaba guardando los intervalos creados en un sitio donde se podían volver a procesar, por lo que ese map me acaba enviando el [4, 4] a [10, 10], cuando la intención real era que se quedará en [4, 4] (sólo hay que aplicarlo una vez por semilla).

Utilicé el mismo código que para el 1 pero con el nuevo número. En mi caso tenia que probar ₄₃ millones posibles "holding down time" y me tardó 3.5s en calcular.

Seguramente haya una forma matemática de sacar la solución en O(1).
También creo que, ya que las distancias recorridas primero incrementan y luego (desde la mitad?) decrementan, seguramente se pueda hacer binary search para buscar:

• Entre (0..T/2) -> Buscar el t minimo que cumple el record. Sabemos que t..T/2 también batiran el record.
• Entre (T/2+1..T) -> Buscar el t minimo que NO cumple el record. Sabemos que T/2+1..t batiran el record.
  Con la diferencia de los 2 "t" sacariamos el número de formas posibles. Ambos casos se encuentran en O(logT) con binary search, bastante mejor que O(T).
  Quizás pruebe a implementarlo si tengo ganas luego xD

Al final queremos los valores de tiempo "t" que cumplan:

(total_time - t) * t > distance

Resolviendo la ecuación de segundo grado, los valores que estén entre las raíces serán los que superan la distancia, así que la solución es contar el numero de enteros que hay entre las dos raíces.

use regex::Regex;

use crate::handler::Handler;

#[derive(Debug)]
pub struct Day06;

impl Day06 {
    fn process_input() -> Vec<Vec<u64>> {
        Handler::new("./src/day06/input.txt")
            .handle_input()
            .unwrap()
            .lines()
            .map(|line| {
                Regex::new(r"\D+")
                    .unwrap()
                    .split(&line)
                    .map(|num| num.parse::<u64>().unwrap_or_default())
                    .skip(1)
                    .collect::<Vec<u64>>()
            })
            .collect()
    }

fn get_chances(time: &u64, distance: u64, time_holding: u64) -> u64 {
    if time_holding == *time {
        return 0;
    }

    if (time - time_holding) * time_holding <= distance {
        return Self::get_chances(time, distance, time_holding + 1);
    }

    1 + Self::get_chances(time, distance, time_holding + 1)
}

pub fn part1() -> u64 {
    let input = Self::process_input();
    input[0]
        .iter()
        .enumerate()
        .map(|(idx, time)| {
            let chances = Self::get_chances(time, input[1][idx], 1);

            if chances == 0 {
                1
            } else {
                chances
            }
        })
        .product()
}

pub fn part2() -> u64 {
    let input = Self::process_input();
    let time: u64 = input[0]
        .iter()
        .map(|&num| num.to_string())
        .collect::<String>()
        .parse()
        .unwrap();
    let distance: u64 = input[1]
        .iter()
        .map(|&num| num.to_string())
        .collect::<String>()
        .parse()
        .unwrap();

    let mut chances = 0;
    for holding_time in 1..time {
        let speed = time - holding_time;
        let chance_time = time - speed;

        if speed * chance_time > distance {
            chances += 1;
        }
    }

    chances
}
}

#[test]
fn test1() {
    let expected = 1108800;
    assert_eq!(expected, Day06::part1());
}

#[test]
fn test2() {
    let expected = 36919753;
    assert_eq!(expected, Day06::part2());
}