Advent of Code 2023: ChatGPT-4 turbo edition

CiudadanoEj #181 6 Dic

yo nose si he tenido mala suerte con los numeros o que pero a mi me tardan ma de 15 min haciendolo a bruteforce xD

from collections import defaultdict
from functools import reduce
from math import comb
# # Part 1
with open('day 6\input.txt') as f:
    s = f.read().splitlines()

##################### Part I
to_check = []
ans = 0
times = s[0].split(':')[1].strip().split()
dist = s[1].split(':')[1].strip().split()
for i, time in enumerate(times):
    dt, cnt, won = int(time), 0, 0
    while dt > 0:
        win = cnt * dt
        if win > int(dist[i]):
            won += 1
        dt -= 1
        cnt += 1
    to_check.append(won)
print(reduce(lambda x, y: x * y, to_check))
# PART II
time = s[0].split(':')[1].strip()
dist = s[1].split(':')[1].strip()
time = int("".join(time.split()))
dist = int("".join(dist.split()))
ans = 0
for x in range(time+1):
    dx = x*(time-x)
    if dx>=dist:
        ans += 1
print(ans)

mi input:
Time: 59 79 65 75
Distance: 597 1234 1032 1328

2 respuestas

B

[Borrado] #182 6 Dic

#181 mete todo el código en una función y llámala.

Si mal no recuerdo el intérprete de Python interpreta a saco todo lo que está en el scope más externo, pero precompila las funciones a bytecode.

También creo recordar que el map interno de la memoria (donde está cada variable, qué contiene etc) está implementado distinto para ambos casos.

Lo he probado con tu código y termina bastante rápido.

1 1 respuesta

PiradoIV #183 6 Dic Brongster

#181 A fuerza bruta me tarda unos 10s con tu input, en Xojo.

1 respuesta

CiudadanoEj #184 6 Dic

#182 #183 seee no me tarda tanto tenia una parte de codigo de prueba que lo estaba ralentizando todo mb

1

R

ragnar777 #185 6 Dic

Me ha resultado sencillo el de hoy aunque hay conceptos que visualizo pero no se explicar matematicamente xD si alguien sabe darles cuerpo se lo agradecere.

conceptos

C# Day6 1 star

using System;
using System.IO;

namespace day6
{
    class Program
    {
        static void Main(string[] args)
        {
            using (var reader = new StreamReader("Input.txt"))
            {
                var timesInput = reader.ReadLine().Remove(0, "Time:".Length);
                var times = Array.ConvertAll<string, long>(timesInput.Trim().Split(new char[0], StringSplitOptions.RemoveEmptyEntries), (s) => long.Parse(s));
                var distancesInput = reader.ReadLine().Remove(0, "Distance:".Length);
                var distances = Array.ConvertAll<string, long>(distancesInput.Trim().Split(new char[0], StringSplitOptions.RemoveEmptyEntries), (s) => long.Parse(s));

            var result = 1L;
            for (int i = 0; i < times.Length; i++)
            {
                long time = times[i];
                long distance = distances[i];
                var half = time / 2;
                var firstValid = FindFirstValid(time, distance, 0, half);
                var validOptions = (half - (firstValid - 1)) * 2;
                if(time %2 == 0)
                {
                    validOptions--;
                }
                result *= validOptions;
            }

            Console.WriteLine(result.ToString());
            Console.ReadKey();

            long FindFirstValid(long time, long distance, long lInvalid, long lvalid)
            {
                var half = lInvalid + (lvalid - lInvalid) /2;
                var valid = Valid(half);
                if (valid)
                {
                    lvalid = half;
                    if (!Valid(lvalid - 1))
                    {
                        return lvalid;
                    }
                }
                else
                {
                    lInvalid = half;
                    if (Valid(lInvalid + 1))
                    {
                        return lInvalid + 1;
                    }
                }

                return FindFirstValid(time, distance, lInvalid, lvalid);

                bool Valid(long presTime)
                {
                    return (time - presTime) * presTime > distance;
                }
            }

        }
    }
}
}

C# Day6 2 star

using System;
using System.IO;

namespace day6
{
    class Program
    {
        static void Main(string[] args)
        {
            using (var reader = new StreamReader("Input.txt"))
            {
                var timesInput = reader.ReadLine().Remove(0, "Time:".Length);
                var timeParsed = long.Parse(timesInput.Replace(" ", ""));

            var distancesInput = reader.ReadLine().Remove(0, "Distance:".Length); 
            var distanceParsed = long.Parse(distancesInput.Replace(" ", ""));

            var half = timeParsed / 2;
            var firstValid = FindFirstValid(timeParsed, distanceParsed, 0, half);
            var validOptions = (half - (firstValid - 1)) * 2;
            if(timeParsed %2 == 0)
            {
                validOptions--;
            }

            Console.WriteLine(validOptions.ToString());
            Console.ReadKey();

            long FindFirstValid(long time, long distance, long lInvalid, long lvalid)
            {
                var h = lInvalid + (lvalid - lInvalid) /2;
                var valid = Valid(h);
                if (valid)
                {
                    lvalid = h;
                    if (!Valid(lvalid - 1))
                    {
                        return lvalid;
                    }
                }
                else
                {
                    lInvalid = h;
                    if (Valid(lInvalid + 1))
                    {
                        return lInvalid + 1;
                    }
                }

                return FindFirstValid(time, distance, lInvalid, lvalid);

                bool Valid(long presTime)
                {
                    return (time - presTime) * presTime > distance;
                }
            }

        }
    }
}
}

Ayer estuve trabado un buen rato, primero intenté recorrer el mapeo al reves desde el destino mas bajo buscando si habia seed valida pero no lo conseguí.
Cuando desistí y decidí hacerlo con fuerza bruta estuve contestando con la seed en vez del destination

Salgo de puente así que mi idea es intentar hacer pseudocodigo en los ratos libres y intentar resolverlos a la vuelta.

draz1c #186 6 Dic

El de hoy estaba tirado no? Se han flipado mucho ayer y el día 3. De hecho ya me estaba temiendo al ver la segunda parte que iba a ser un marronazo como lo de ayer que tardaría mucho en ejecutarse y cuando he visto que he sacado el resultado en 1 segundo he pensado bah, estará mal calculado pero voy a meterlo y darle a submit por si suena la flauta y efectivamente era correcto

1 respuesta

PiradoIV #187 6 Dic Brongster

#186 El de hoy hubiera molado que fuese más complejo de sacar a fuerza bruta, sabiendo que ya tienes el resultado da pereza ponerte a optimizarlo xD

byJoTaeFe #188 6 Dic Diamond hands

Aún me falta el 3 que le daré un try esta tarde, me rayó bastante.

La Parte 2 del 5 me tardó una barbaridad igual, pero algo es algo.
El 6 demasiado fácil comparado con el resto

JS - Dia 04

/* --- Day 4: Scratchcards ---
https://adventofcode.com/2023/day/4 */
console.log("--- Day 4: Scratchcards ---")

const text = `PUZZLE INPUT`

/* --- Part One --- */

const textToArray = text.split("\n");
let totalPoints = 0

for (let i = 0; i < textToArray.length; i++) {

const parts = textToArray[i].split("|")
const winningNumbers = parts[0].split(":")[1].split(" ").filter(num => num.match(/\d+/))
const totalNumbers = parts[1].split(" ").filter(num => num.match(/\d+/))

let matchs = 0
let points = 0
winningNumbers.forEach(num => {
    if (totalNumbers.includes(num)) {
        matchs === 0 ? points += 1 : points *= 2
        matchs++
    }
})
totalPoints += points
}

console.log("Puntos totales [Parte 1]: " + totalPoints)


/* --- Part Two --- */

let newArray = []

for (let i = 0; i < textToArray.length; i++) {

const parts = textToArray[i].split("|");
const winningNumbers = parts[0].split(":")[1].split(" ").filter(num => num.match(/\d+/))
const totalNumbers = parts[1].split(" ").filter(num => num.match(/\d+/));

let matchs = 0;
winningNumbers.forEach(num => {
    if (totalNumbers.includes(num)) {
        matchs++;
    }
})

let card = {
    cardNumber: textToArray[i].split(":")[0].replace("Card ", ""),
    matchs: matchs,
    instances: 1
}
newArray.push(card)
}

for (let i = 0; i < newArray.length; i++) {
    for (let j = 0; j < newArray[i].instances; j++) {
        for (let k = 0; k < newArray[i].matchs; k++) {
            newArray[i + 1 + k].instances += 1
        }
    }
}

console.log("Cartas totales [Parte 2]: " + newArray.reduce((total, card) => total + card.instances, 0));

JS - Dia 05

/* --- Day 5: If You Give A Seed A Fertilizer ---
https://adventofcode.com/2023/day/5 */
console.log("--- Day 5: If You Give A Seed A Fertilizer ---")

const text = `PUZZLE INPUT`

/* --- Part One --- */

const textToArray1 = text.split(/\n\n/)
const seeds = textToArray1[0].split(" ").slice(1)
let maps = []
let lowest = Number.MAX_SAFE_INTEGER;

// Maps
for (let i = 1; i < textToArray1.length; i++) {
    const regex = /\b(\d+)\s+(\d+)\s+(\d+)\b/g
    const rowsOfNumbers = [];
    let match;

while ((match = regex.exec(textToArray1[i])) !== null) {
    const numbers = match.slice(1).map(Number);
    rowsOfNumbers.push(numbers);
}
maps.push(rowsOfNumbers)
}

for (let i = 0; i < seeds.length; i++) {
    let seed = parseInt(seeds[i], 10)

maps.forEach(type => {
    for (let j = 0; j < type.length; j++) {

        const dest = type[j][0]
        const source = type[j][1]
        const range = type[j][2]

        if (seed >= source && seed < source + range) {
            seed = dest + (seed - source)
            break
        }
    }
})
if (lowest > seed) lowest = seed
}

console.log("Número de localización más bajo [Parte 1]: " + lowest)


/* --- Part Two --- */

let lowest2 = Number.MAX_SAFE_INTEGER;

const seedsPairs = []
for (let i = 0; i < seeds.length; i += 2) {
    seedsPairs.push([parseInt(seeds[i]), parseInt(seeds[i + 1])])
}

for (let i = 0; i < seedsPairs.length; i++) {

for (let index = seedsPairs[i][0]; index < seedsPairs[i][0] + seedsPairs[i][1]; index++) {
    let seed = index

    maps.forEach(type => {
        for (let j = 0; j < type.length; j++) {

            const dest = type[j][0]
            const source = type[j][1]
            const range = type[j][2]

            if (seed >= source && seed < source + range) {
                seed = dest + (seed - source)
                break
            }
        }
    })
    if (lowest2 > seed) lowest2 = seed
}
}

console.log("Número de localización más bajo [Parte 2]: " + lowest2)

JS - Dia 06

/* --- Day 6: Wait For It ---
https://adventofcode.com/2023/day/6 */
console.log("--- Day 6: Wait For It ---")

const text = `PUZZLE INPUT`

/* --- Part One --- */

const textToArray = text.split("\n")
const timesArr = textToArray[0].match(/\d+/g)
const distancesArr = textToArray[1].match(/\d+/g)

let total = 0

for (let j = 0; j < timesArr.length; j++) {
    let numberWays = 0

for (let i = 0; i <= timesArr[j]; i++) {
    if ((i * (timesArr[j] - i)) > distancesArr[j]) numberWays++
}
total === 0 ? total = numberWays : total *= numberWays
}

console.log("Multiplicación del número de caminos para ganar [Parte 1]: " + total)

/* --- Part Two --- */

const time2 = parseInt(textToArray[0].replace(/\s/g, "").split(":")[1])
const distance2 = parseInt(textToArray[1].replace(/\s/g, "").split(":")[1])

let total2 = 0

for (let i = 0; i <= time2; i++) {
    if ((i * (time2 - i)) > distance2) total2++
}

console.log("Número de caminos para ganar [Parte 2]: " + total2)

Frankicia #189 6 Dic

Como me gusta pasar tiempo debuggando para que al final sea que el numerito no me entraban en 32 bits

1

Flashk #190 6 Dic

Me ocupó más el código del parseo que lo que es luego la solución del problema xD

Day 6

Class WaitForIt

public class WaitForIt {

private static final Pattern NUMBER_PATTERN = Pattern.compile(" +(\\d*)");
private final List<Race> races = new ArrayList<>();

public WaitForIt(List<String> inputs, boolean isPartOne) {

    if(isPartOne) {
        initPartOne(inputs);
    } else {
        initPartTwo(inputs);
    }

}

private void initPartOne(List<String> inputs) {
    String times = inputs.get(0).split(":")[1];
    String records = inputs.get(1).split(":")[1];

    Matcher timesMatcher = NUMBER_PATTERN.matcher(times);
    List<Integer> timesList = new ArrayList<>();
    while(timesMatcher.find()) {
        timesList.add(Integer.parseInt(timesMatcher.group(1)));
    }

    Matcher recordsMatcher = NUMBER_PATTERN.matcher(records);
    List<Integer> recordsList = new ArrayList<>();
    while(recordsMatcher.find()) {
        recordsList.add(Integer.parseInt((recordsMatcher.group(1))));
    }

    for(int i = 0; i < timesList.size(); i++) {
        races.add(new Race(timesList.get(i), recordsList.get(i)));
    }
}

private void initPartTwo(List<String> inputs) {
    String times = inputs.get(0).split(":")[1];
    String records = inputs.get(1).split(":")[1];

    times = StringUtils.getDigits(times);
    records = StringUtils.getDigits(records);

    races.add(new Race(Long.parseLong(times), Long.parseLong(records)));
}

public long solve() {
    return races.stream().map(Race::waysToBeatTheRecord).reduce(1L, Math::multiplyExact);
}
}

Class Race
public class Race {

private final long time;
private final long recordDistance;

public Race(long time, long recordDistance) {
    this.time = time;
    this.recordDistance = recordDistance;
}

public long waysToBeatTheRecord() {

    long speed = 0;
    long remainingTime = time;
    long waysToBeatRecord = 0;

    for(long i = 1; i < time-1; i++) {
        speed++;
        remainingTime--;
        long distance = remainingTime * speed;
        if(distance > recordDistance) {
            waysToBeatRecord++;
        }
    }

    return waysToBeatRecord;
}

}

R

RsTTa #191 7 Dic

Bueno la parte 2 del dia 5 se me complicó un poco, mas que nada por pasar de largo uno de las opciones que tenia para solucionarlo, buscando algo mas sencillo de implementar, pero al final me ha tocado volver xD

edit: Bueno, el dia 6 lo he visto bastante mejor que el 5. Solucion en O(1) para las dos partes

Enfoque dia 5

Enfoque dia 6

Para el 6, lo primero que he visto, que el tiempo pulsando el boton mas optimo es la mitad del tiempo total de la carrera.
Luego, desde ese punto maximo, segun vas disminuyendo el tiempo en 1, al recorrido anterior se le resta un numero que sigue una seria. Para tiempos totales de carrera impares, segun te alejas del punto maximo se resta un numero de la secuencia de los numeros pares al al recorrido anterior, para tiempo pares, se resta un numero de la secuencia de los numeros impares.

Tiempo = 7
[tiempo presionando el boton] [tiempo en movimiento]

0 x 7 = 0 (6 - 0 = 6)
1 x 6 = 6 (10 - 6 = 4)
2 x 5 = 10 (12 - 10 = 2)
3 x 4 = 12
4 x 3 = 12
5 x 2 = 10 (12 - 10 = 2)
6 x 1 = 6 (10 - 6 = 4)
7 x 0 = 0 (6 - 0 = 6)

Tiempo = 8
[tiempo presionando el boton] [tiempo en movimiento]

0 x 8 = 0 (7 - 0 = 7)
1 x 7 = 7 (12 - 7 = 5)
2 x 6 = 12 (15 - 12 = 3)
3 x 5 = 15 (16 - 15 = 1)
4 x 4 = 16
5 x 3 = 15 (16 - 15 = 1)
6 x 2 = 12 (15 - 12 = 3)
7 x 1 = 7 (12 - 7 = 5)
8 x 0 = 0 (7 - 0 = 7)

Viendo estas secuencias, y sabiendo que el punto optimo esta en

floor(tiempo / 2)

se puede calcular cual es el punto mas lejano al optimo que sigue cumpliendo la condicion de recorrer una distancia mayor.
(n * (n + 1)) nos da el sumatoria de los n primeros numeros pares
(n * n) nos da el sumatorio de los n primeros impares

por tanto, si la distancia maxima que podemos recorrer es mx, tenemos un margen de

diff = mx - record_anterior

, como queremos superar el record al menos por 1, en realidad el margen es

diff = mx - record_anterior - 1

con esto podemos plantear las inecuaciones

n^2 + n <= diff

(cuando el tiempo es impar y, por tanto, la secuencia es la de los numeros pares)

n^2 <= diff

(cuando el tiempo es par y, por tanto, la secuancia es la de los numeros impares)

Como nos interesa solo el resultado mas cercano a diff, podemos plantearlas como ecuaciones de segundo grado

n^2 + n - diff = 0

n^2 - diff = 0

y aplicar la funcion floor al resultado para quitar los decimales en caso de que existan.

El resultado de la ecuacion sera la distancia entre el valor maximo y el valor minimo que permite cumplir la condicion, vamos el numero de posibilidades (en realidad la mitad, ya que si miramos a las tablas de arriba, a partir del punto maximo los numeros se repiten por arriba y por abajo)

Dia 5 parte 1

def parse(filepath: str) -> tuple[list, dict]:
    with open(filepath) as fp:
        _map = {}
        seeds = [int(seed) for seed in fp.readline().split(':', 1)[1].strip().split()]
        parts = fp.read().strip().split('\n\n')
        for p in parts:
            title, content = p.split(':\n')
            srcname, dstname = title.split(' ', 1)[0].split('-to-')
            _map[srcname] = {}
            _map[srcname][dstname] = []
            for reg in content.split('\n'):
                dststart, srcstart, rngsize = map(int, reg.split())
                _map[srcname][dstname].append((srcstart, dststart, rngsize))
        return seeds, _map

def solve(currsrcname, val, _map, targetname):
    if currsrcname == targetname:
        return val
    for currdstname, ranges in _map[currsrcname].items():
        dstval = val
        for srcstart, dststart, rngsize in ranges:
            if 0 <= (diff := val - srcstart) <= rngsize:
                val = dststart + diff
                break
        return solve(currdstname, val, _map, targetdstname)

if __name__ == '__main__':
    seeds, _map = parse('in.txt')
    targetdstname = 'location'
    currsrcname = 'seed'
    print(min(solve(currsrcname, seed, _map, targetdstname) for seed in seeds))

Dia 5 parte 2

def parse(filepath: str) -> tuple[list, dict]:
    with open(filepath) as fp:
        _map = {}
        raw_seeds = [int(seed) for seed in fp.readline().split(':', 1)[1].strip().split()]
        parts = fp.read().strip().split('\n\n')
        for p in parts:
            title, content = p.split(':\n')
            srcname, dstname = title.split(' ', 1)[0].split('-to-')
            _map[srcname] = {}
            _map[srcname][dstname] = []
            for reg in content.split('\n'):
                dststart, srcstart, rngsize = map(int, reg.split())
                _map[srcname][dstname].append((srcstart, dststart, rngsize))
        return raw_seeds, _map

def solve(currsrcname, start, end, _map, targetname):
    if currsrcname == targetname:
        return start
    mn = float('inf')
    for currdstname, ranges in _map[currsrcname].items():
        visited_ranges = [(start - 1, start - 1), (end, end)]
        for srcstart, dststart, rngsize in ranges:
            srcend = srcstart + rngsize - 1
            if start > srcend:
                continue
            if end < srcstart:
                continue
            unionstart = max(start, srcstart)
            unionend = min(end, srcend)
            assert unionstart <= unionend, 'check the ranges'
            offset = dststart - srcstart
            mn = min(
                solve(currdstname, unionstart + offset, unionend + offset, _map, targetname),
                mn
            )
            visited_ranges.append((unionstart, unionend))
        visited_ranges.sort()
        for i in range(1, len(visited_ranges)):
            s1, e1 = visited_ranges[i - 1]
            s2, e2 = visited_ranges[i]
            s = e1 + 1
            e = s2 - 1
            if s <= e:
                mn = min(
                    solve(currdstname, s, e, _map, targetname),
                    mn
                )
    return mn
            


if __name__ == '__main__':
    raw_seeds, _map = parse('in.txt')
    targetdstname = 'location'
    currsrcname = 'seed'
    mn = float('inf')
    for i in range(1, len(raw_seeds), 2):
        mn = min(
            solve(currsrcname, raw_seeds[i - 1], raw_seeds[i - 1] + raw_seeds[i] - 1, _map, targetdstname),
            mn
        )
    print(mn)

Dia 6 parte 1 [O(1) en tiempo]

from math import isqrt

# given two numbers m1, m2 such as m1 + m2 = n, the greatest product for all possible (m1, m2) pairs is found for
# m1 = floor(n / 2)
# m2 = n - m1

# sum of n first even numbers: n * (n + 1) = n^2 + n
# sum of n first odd numbers: n * n = n^2

# floor(n^2 + n - distance = 0)
def even_distance(distance):
    return (-1 + isqrt(1 + (4 * 1 * distance))) // 2

# floor(n^2 - distance = 0) => n = floor(sqrt(distance))
def odd_distance(distance):
    return isqrt(distance)


if __name__ == '__main__':
    with open('test.txt') as fp:
        times = [int(t) for t in fp.readline().split(':', 1)[1].strip().split()]
        distances = [int(d) for d in fp.readline().split(':', 1)[1].strip().split()]
    ans = 1
    for time, min_distance in zip(times, distances):
        time_pressing_button = time // 2
        time_moving = time - time_pressing_button
        max_distance = time_pressing_button * time_moving
        diff = max_distance - min_distance
        if diff <= 0:
            ans *= 0
            break
        elif time % 2:
            ans *= (2 + 2 * even_distance(diff - 1))
        else:
            ans *= (1 + 2 * odd_distance(diff - 1))
    print(ans)

Dia 6 parte 2 [O(1) en tiempo]

from math import isqrt

# given two numbers m1, m2 such as m1 + m2 = n, the greatest product for all possible (m1, m2) pairs is found for
# m1 = floor(n / 2)
# m2 = n - m1

# sum of n first even numbers: n * (n + 1) = n^2 + n
# sum of n first odd numbers: n * n = n^2

# floor(n^2 + n - distance = 0)
def even_distance(distance):
    return (-1 + isqrt(1 + (4 * 1 * distance))) // 2

# floor(n^2 - distance = 0) => n = floor(sqrt(distance))
def odd_distance(distance):
    return isqrt(distance)


if __name__ == '__main__':
    with open('in.txt') as fp:
        time = int(fp.readline().split(':', 1)[1].replace(' ', ''))
        min_distance = int(fp.readline().split(':', 1)[1].replace(' ', ''))
    time_pressing_button = time // 2
    time_moving = time - time_pressing_button
    max_distance = time_pressing_button * time_moving
    diff = max_distance - min_distance
    ans = 0
    if diff <= 0:
        ans = 0
    elif time % 2:
        ans = (2 + 2 * even_distance(diff - 1))
    else:
        ans = (1 + 2 * odd_distance(diff - 1))
    print(ans)

byJoTaeFe #192 7 Dic Diamond hands

Al fin consigo terminar el 3, menudo puto sufrimiento.

JS - Dia 03

/* --- Day 3: Gear Ratios  ---
https://adventofcode.com/2023/day/3 */
console.log("--- Day 3: Gear Ratios  ---")

const text = `PUZZLE INPUT`

/* --- Part One --- */

const textToArray = text.split("\n");
const regexSymb = /[^\d.]/
const regexNumb = /\d/
let total = 0

const matrix = []
textToArray.forEach(row => {
    matrix.push(row.split(""))
})

for (let i = 0; i < matrix.length; i++) {
    const row = matrix[i]
    for (let j = 0; j < row.length; j++) {
        const celda = row[j]

    if (regexNumb.exec(celda)) {
        const number = searchNumberFromPosition(row, j).toString().replace(/,/g, "")
        const hasAdjacentSymbol = hasAdjacentSymbolAround(matrix, i, j, number.length)

        if (number && hasAdjacentSymbol) {
            total += parseInt(number)
        }

        for (let k = j; k < j + number.length; k++) {
            matrix[i][k] = "."
        }
    }
}
}

console.log(`Suma de todos los números con símbolos adyacentes [Parte 1]: ${total}`)

function searchNumberFromPosition(line, position) {
    let startIndex = position
    let endIndex = position

while (startIndex >= 0 && regexNumb.test(line[startIndex])) {
    startIndex--
}

while (endIndex < line.length && regexNumb.test(line[endIndex])) {
    endIndex++
}

return line.slice(startIndex + 1, endIndex)
}

function hasAdjacentSymbolAround(array, row, col, length) {
    const directions = [
        { row: -1, col: 0 },
        { row: 1, col: 0 },
        { row: 0, col: -1 },
        { row: 0, col: 1 },
        { row: -1, col: -1 },
        { row: -1, col: 1 },
        { row: 1, col: -1 },
        { row: 1, col: 1 },
    ]

for (const direction of directions) {
    for (let i = 0; i < length; i++) {
        const rowToCheck = row + direction.row
        const colToCheck = col + direction.col + i

        if (
            rowToCheck >= 0 && rowToCheck < array.length &&
            colToCheck >= 0 && colToCheck < array[rowToCheck].length &&
            regexSymb.test(array[rowToCheck][colToCheck])
        ) {
            return true
        }
    }
}
return false
}


/* --- Part Two --- */

const regexGear = /\*/
let total2 = 0

const matrix2 = []
textToArray.forEach(row => {
    matrix2.push(row.split(""))
})

for (let i = 0; i < matrix2.length; i++) {
    const row = matrix2[i]
    for (let j = 0; j < row.length; j++) {
        const celda = row[j]

    if (regexGear.exec(celda)) {
        let numsAdj = 0
        let numbersPerGear = []

        const positions = adjacentNumber(matrix2, i, j)
        for (let posI = 0; posI < positions.length; posI++) {
            const rowPosition = positions[posI][0]
            const colPosition = positions[posI][1]

            const number = searchNumberFromPosition(matrix2[rowPosition], colPosition).toString().replace(/,/g, "")
            if (!numbersPerGear.includes(number)) {
                numbersPerGear.push(number)
            }
        }

        if (numbersPerGear.length === 2) {
            numbersPerGear.forEach(num => {
                numsAdj === 0 ? numsAdj = num : numsAdj *= num
            })
        }
        total2 += numsAdj
    }
}
}

console.log(`Suma de todas las multiplicaciones de los engranajes [Parte 2]: ${total2}`)

function adjacentNumber(array, row, col) {
    const directions = [
        { row: -1, col: 0 },
        { row: 1, col: 0 },
        { row: 0, col: -1 },
        { row: 0, col: 1 },
        { row: -1, col: -1 },
        { row: -1, col: 1 },
        { row: 1, col: -1 },
        { row: 1, col: 1 },
    ]

const numbers = []

for (const direction of directions) {
    const rowToCheck = row + direction.row
    const colToCheck = col + direction.col

    if (
        rowToCheck >= 0 && rowToCheck < array.length &&
        colToCheck >= 0 && colToCheck < array[rowToCheck].length &&
        regexNumb.test(array[rowToCheck][colToCheck])
    ) {
        numbers.push([rowToCheck, colToCheck])
    }
}
return numbers
}

Mandarino #193 7 Dic

Dia 7
La primera parte me ha ido bien, pero en la segunda ..

spoiler

R

RsTTa #194 7 Dic

Bueno pues dia 7

Enfoque

Dia 7 parte 1

from collections import Counter

def rate_hand(hand):
    freqs = Counter(hand)
    size = len(freqs)
    mx = max(freqs.values())
    if size == 1:
        return 7
    if size == 2 and mx == 4:
        return 6
    if size == 2 and mx == 3:
        return 5
    if size == 3 and mx == 3:
        return 4
    if size == 3 and mx == 2:
        return 3
    if size == 4:
        return 2
    if size == 5:
        return 1
    

def transform_hand(hand):
    m = {'A': 14, 'K': 13, 'Q': 12, 'J': 11, 'T': 10}
    thand = tuple(int(m.get(v, v)) for v in hand)
    rating = rate_hand(thand)
    return tuple((rating, *thand))


if __name__ == '__main__':
    with open('in.txt') as fp:
        hand_bid_pairs = [(transform_hand(hand), int(bid)) for hand, bid in map(str.split, fp.readlines())]
        hand_bid_pairs.sort()
        print(sum(
            (bid * idx)
            for idx, (_, bid) in enumerate(sorted(hand_bid_pairs), start=1)
        ))

Dia 7 parte 2

from collections import Counter

def rate_hand(hand):
    freqs = Counter(hand)
    size = len(freqs)
    mx = max(freqs.values())
    joker_count = freqs.get(0, 0)
    if size == 1:
        return 7
    if size == 2 and mx == 4:
        return 7 if (joker_count in {1, 4}) else 6
    if size == 2 and mx == 3:
        return 7 if (joker_count in {2, 3}) else 5
    if size == 3 and mx == 3:
        return 6 if (joker_count in {1, 3}) else 4
    if size == 3 and mx == 2:
        return 6 if (joker_count == 2) else 5 if (joker_count == 1) else 3
    if size == 4:
        return 4 if (joker_count in {1, 2}) else 2
    if size == 5:
        return 2 if (joker_count == 1) else 1
    

def transform_hand(hand):
    m = {'A': 14, 'K': 13, 'Q': 12, 'J': 0, 'T': 10}
    thand = tuple(int(m.get(v, v)) for v in hand)
    rating = rate_hand(thand)
    return tuple((rating, *thand))


if __name__ == '__main__':
    with open('in.txt') as fp:
        hand_bid_pairs = [(transform_hand(hand), int(bid)) for hand, bid in map(str.split, fp.readlines())]
        print(sum(
            (bid * idx)
            for idx, (_, bid) in enumerate(sorted(hand_bid_pairs), start=1)
        ))

1

B

[Borrado] #195 7 Dic

Dia 7 parte 1

spoiler

-module(part1).
-export([main/0]).
-record(hand, {rank, hand_str, reward}).

freq_to_rank() ->
  #{
    [5] => 0,
    [4, 1] => -1,
    [3, 2] => -2,
    [3, 1, 1] => -3,
    [2, 2, 1] => -4,
    [2, 1, 1, 1] => -5,
    [1, 1, 1, 1, 1] => -6
  }.

card_to_rank(C) ->
  case C of
    $T -> 10;
    $J -> 11;
    $Q -> 12;
    $K -> 13;
    $A -> 14;
    _ -> C - $0
  end.


get_card_freq_map([], Acc) -> Acc;
get_card_freq_map([Card | T], Acc) ->
  NewCardFreq = maps:get(Card, Acc, 0) + 1,
  UpdatedMap = maps:put(Card, NewCardFreq, Acc),
  get_card_freq_map(T, UpdatedMap).

get_hand_rank(CardFreqMap) ->
  maps:get(
    lists:sort(fun _(A, B) -> A > B end, maps:values(CardFreqMap)),
    freq_to_rank()
  ).

read_card_list(Acc) ->
  case io:get_line("") of
    eof -> Acc;
    Line ->
      {_, [Cards, RewardBin]} =
        re:run(Line, "(.*) (.*)\n", [{capture, all_but_first, binary}]),
      CardInts = [card_to_rank(C) || C <- binary_to_list(Cards)],
      HandRank = get_hand_rank(get_card_freq_map(CardInts, maps:new())),
      {RewardInt, _} = string:to_integer(binary_to_list(RewardBin)),
      NewHand = #hand{
        rank=HandRank,
        reward=RewardInt,
        hand_str=CardInts
      },
      read_card_list([NewHand | Acc])
  end.

compare_hands(A, B) ->
  RankA = A#hand.rank,
  RankB = B#hand.rank,
  case RankA == RankB of
    true -> A#hand.hand_str > B#hand.hand_str;
    _ -> RankA > RankB
  end.

solve() ->
  HandList = lists:sort(fun compare_hands/2, read_card_list([])),
  lists:foldl(
    fun _(A, B) -> A + B end,
    0,
    lists:map(
      fun _({Hand, Index}) -> Hand#hand.reward * Index end,
      lists:zip(HandList, lists:reverse(lists:seq(1, length(HandList))))
    )
  ).

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

Parte 2, que cerdada lo de las Js xD

spoiler

-module(part2).
-export([main/0]).
-record(hand, {rank, hand_str, reward}).

freq_to_rank() ->
  #{
    [5] => 0,
    [4, 1] => -1,
    [3, 2] => -2,
    [3, 1, 1] => -3,
    [2, 2, 1] => -4,
    [2, 1, 1, 1] => -5,
    [1, 1, 1, 1, 1] => -6
  }.

card_to_rank(C) ->
  case C of
    $T -> 10;
    $J -> 1;
    $Q -> 12;
    $K -> 13;
    $A -> 14;
    _ -> C - $0
  end.

compare_hands(A, B) ->
  RankA = A#hand.rank,
  RankB = B#hand.rank,
  case RankA == RankB of
    true -> A#hand.hand_str > B#hand.hand_str;
    _ -> RankA > RankB
  end.

get_card_freq_map([], Acc) -> Acc;
get_card_freq_map([Card | T], Acc) ->
  NewCardFreq = maps:get(Card, Acc, 0) + 1,
  UpdatedMap = maps:put(Card, NewCardFreq, Acc),
  get_card_freq_map(T, UpdatedMap).

get_hand_rank(CardFreqMap) ->
  maps:get(
    lists:sort(fun _(A, B) -> A > B end, maps:values(CardFreqMap)),
    freq_to_rank()
  ).

get_best_hand([], Original, Reward, CardInts, BestHand) ->
  CandidateFreqMap = get_card_freq_map(CardInts, maps:new()),
  CandidateHand =
    #hand{
      rank=get_hand_rank(CandidateFreqMap),
      reward=Reward,
      hand_str=Original
    },
  case compare_hands(CandidateHand, BestHand) of
    true -> CandidateHand;
    _ -> BestHand
  end;

get_best_hand([Card | T], Original, Reward, CardInts, BestHand) ->
  case Card of
    1 ->
        hd(
          lists:sort(
            fun compare_hands/2,
            lists:map(
              fun _(C) -> get_best_hand(T, Original, Reward, [C | CardInts], BestHand) end,
              [X || X <- lists:seq(1, 14), X /= 11]
            )
          )
        );
    _ -> get_best_hand(T, Original, Reward, [Card | CardInts], BestHand)
  end.

read_card_list(Acc) ->
  case io:get_line("") of
    eof -> Acc;
    Line ->
      {_, [CardTemplate, RewardBin]} =
        re:run(Line, "(.*) (.*)\n", [{capture, all_but_first, binary}]),
      CardTemplateInts = [card_to_rank(C) || C <- binary_to_list(CardTemplate)],
      {RewardInt, _} = string:to_integer(RewardBin),
      NewHand = get_best_hand(
        CardTemplateInts,
        CardTemplateInts,
        RewardInt,
        [],
        #hand{rank=-7, reward=0, hand_str="11111"}
      ),
      io:format("~p ~n", [NewHand]),
      read_card_list([NewHand | Acc])
  end.

solve() ->
  HandList = lists:sort(fun compare_hands/2, read_card_list([])),
  lists:foldl(
    fun _(A, B) -> A + B end,
    0,
    lists:map(
      fun _({Hand, Index}) -> Hand#hand.reward * Index end,
      lists:zip(HandList, lists:reverse(lists:seq(1, length(HandList))))
    )
  ).

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

Frankicia #196 7 Dic

Dia 7 - C++

Parte 2 a base de bruteforce

spoiler

#include <algorithm>
#include <stdio.h>
#include <string>
#include <sstream>
#include <map>
#include <iostream>
#include <vector>


std::map<char, int> letter_to_int = {
    {'A',14},
    {'K',13},
    {'Q',12},
    #ifdef SECOND_PART
        {'J', 1},
    #else
        {'J',11},
    #endif
    {'T',10},
    {'9', 9},
    {'8', 8},
    {'7', 7},
    {'6', 6},
    {'5', 5},
    {'4', 4},
    {'3', 3},
    {'2', 2},
    #ifdef SECOND_PART
        {'J', 1},
    #endif
};

#define POINTS_FIVE     7
#define POINTS_FOUR     6
#define POINTS_FULL     5
#define POINTS_THREE    4
#define POINTS_TWO_PAIR 3
#define POINTS_ONE_PAIR 2
#define POINTS_UNIQUE   1

int get_points(std::map<int, int> num_cards) {

#ifdef SECOND_PART
    // We have jokers
    if(num_cards[1]) {
        num_cards[1]--;
        int max_points = 0;
        for(int i = 2; i <= 14; ++i) {
            num_cards[i]++;
            max_points = std::max(max_points, get_points(num_cards));
            num_cards[i]--;
        }

        return max_points;

    }
#endif

bool three_en = false;
int two_en   = 0;
for(auto &[k, v] : num_cards) {
    if (v == 5) return POINTS_FIVE;
    if (v == 4) return POINTS_FOUR;
    if (v == 3) three_en = true;
    if (v == 2) two_en++;
}

if      (three_en && two_en     ) return POINTS_FULL;
else if (three_en               ) return POINTS_THREE;
else if (            two_en == 2) return POINTS_TWO_PAIR;
else if (            two_en == 1) return POINTS_ONE_PAIR;

return POINTS_UNIQUE;

}

struct hand {
    int bid;
    int points;
    std::vector<int> cards;
};

static bool comp(const hand& h1, const hand& h2){

if (h1.points > h2.points) return true;
if (h1.points < h2.points) return false;

// same points
for(int i = 0; i < h1.cards.size(); i++) {
    if (h1.cards[i] > h2.cards[i]) return true;
    if (h1.cards[i] < h2.cards[i]) return false;
}

return true;
}


int main(int argc, char * argv[]){

std::string line;
std::vector<hand> hands;

while(getline(std::cin, line)) {
    std::istringstream iss(line);
    std::string token;

    iss >> token;
    struct hand h;

    std::map<int, int> num_cards;
    for(auto &c : token) {
        h.cards.push_back(letter_to_int[c]);
        num_cards[letter_to_int[c]]++;
    }
    h.points = get_points(num_cards);

    iss >> token;
    h.bid = stoi(token);
    hands.push_back(h);

}

std::sort(hands.begin(), hands.end(), comp);

int sum = 0;
for(int i = 0; i < hands.size(); i++) {
    sum += (hands.size() - i) * hands[i].bid;
}

std::cout << "Result: " << sum << std::endl;
return 0;
}

R

RsTTa #197 7 Dic

Ya se acerca el finde, se vendrán problemas más difíciles, aunque a mí el 5 ya se me complicó un poco xD

B

[Borrado] #198 7 Dic

Me quería pegar con la implementación de la ordenación en Rust y cosillas orientadas a objetos y ha estado interesante. Voy a ver si lo puedo optimizar, pero tampoco me voy a calentar mucho que no me pagan por esto xD

EDIT: Pequeño refactor para toda la morralla del part2

Día 07 Parte1 + Parte2 [Rust]

use std::{cmp::Ordering, collections::HashMap};

use crate::handler::Handler;

#[derive(Debug)]
pub struct Hand {
    pub bid: usize,
    pub cards: Vec<char>,
    pub strength: u32,
}

impl Hand {
    pub fn new(cards: Vec<char>, bid: usize) -> Self {
        Hand {
            bid,
            cards,
            strength: Default::default(),
        }
    }
}

#[derive(Debug)]
pub struct Day07 {
    pub card_converter1: HashMap<char, u32>,
    pub card_converter2: HashMap<char, u32>,
}

impl Day07 {
    pub fn new() -> Self {
        Day07 {
            card_converter1: HashMap::from([
                ('2', 2),
                ('3', 3),
                ('4', 4),
                ('5', 5),
                ('6', 6),
                ('7', 7),
                ('8', 8),
                ('9', 9),
                ('T', 10),
                ('J', 11),
                ('Q', 12),
                ('K', 13),
                ('A', 14),
            ]),
            card_converter2: HashMap::from([
                ('J', 1),
                ('2', 2),
                ('3', 3),
                ('4', 4),
                ('5', 5),
                ('6', 6),
                ('7', 7),
                ('8', 8),
                ('9', 9),
                ('T', 10),
                ('Q', 11),
                ('K', 12),
                ('A', 13),
            ]),
        }
    }

pub fn calculate_hand_value(hand: &mut Hand, is_part2: bool) {
    let mut coincidences: HashMap<char, u32> = HashMap::new();
    hand.cards.iter().for_each(|&card| {
        *coincidences.entry(card).or_insert(0) += 1;
    });
    match coincidences.keys().count() {
        1 => hand.strength = 7,
        2 => {
            if coincidences.values().any(|&value| value == 4) {
                hand.strength = 6
            } else {
                hand.strength = 5
            }
        }
        3 => {
            if coincidences.values().any(|&value| value == 3) {
                hand.strength = 4
            } else {
                hand.strength = 3
            }
        }
        4 => hand.strength = 2,
        _ => hand.strength = 1,
    }
    if is_part2 && coincidences.contains_key(&'J') {
        match hand.strength {
            7 => {}
            6 | 1 => hand.strength += 1,
            3 => hand.strength += coincidences.get(&'J').unwrap() + 1,
            _ => hand.strength += 2,
        }
    }
}

fn process_input(is_part2: bool) -> Vec<Hand> {
    Handler::new("./src/day07/input.txt")
        .handle_input()
        .unwrap()
        .lines()
        .map(|line| {
            let values: Vec<&str> = line.split_whitespace().collect();
            let mut hand = Hand::new(values[0].chars().collect(), values[1].parse().unwrap());
            Self::calculate_hand_value(&mut hand, is_part2);
            hand
        })
        .collect::<Vec<Hand>>()
}

pub fn part1() -> usize {
    let mut hands = Self::process_input(false);
    let day_handler = Self::new();
    hands.sort_by(|prev, next| {
        if prev.strength == next.strength {
            for i in 0..prev.cards.len() {
                let ordering = day_handler
                    .card_converter1
                    .get(&prev.cards[i])
                    .unwrap()
                    .cmp(day_handler.card_converter1.get(&next.cards[i]).unwrap());

                if ordering != Ordering::Equal {
                    return ordering;
                }
            }
        }
        prev.strength.cmp(&next.strength)
    });
    hands
        .iter()
        .enumerate()
        .map(|(idx, card)| (idx + 1) * card.bid)
        .sum()
}

pub fn part2() -> usize {
    let mut hands = Self::process_input(true);
    let day_handler = Self::new();
    hands.sort_by(|prev, next| {
        if prev.strength == next.strength {
            for i in 0..prev.cards.len() {
                let ordering = day_handler
                    .card_converter2
                    .get(&prev.cards[i])
                    .unwrap()
                    .cmp(day_handler.card_converter2.get(&next.cards[i]).unwrap());

                if ordering != Ordering::Equal {
                    return ordering;
                }
            }
        }
        prev.strength.cmp(&next.strength)
    });
    hands
        .iter()
        .enumerate()
        .map(|(idx, card)| (idx + 1) * card.bid)
        .sum()
}
}

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

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

Flashk #199 7 Dic

Day 7

Hoy ha sido uno de esos días en los que es muy entretenido modelar la solución.

Class Card

@Getter
public class Card implements Comparable<Card> {

private final char number;
private final int value;

public Card(char number, boolean useJokers) {
    this.number = number;
    switch(number) {
        case 'A': value = 14; break;
        case 'K': value = 13; break;
        case 'Q': value = 12; break;
        case 'J': value = useJokers ? 1 : 11; break; // Jokers are the weakest in part 2
        case 'T': value = 10; break;
        default: value = Character.getNumericValue(number);
    }
}

@Override
public int compareTo(Card o) {
    return Integer.compare(this.value, o.value);
}
}

Enum HandType

@Getter
public enum HandType {
    FIVE_OF_A_KIND(7),
    FOUR_OF_A_KIND(6),
    FULL_HOUSE(5),
    THREE_OF_A_KIND(4),
    TWO_PAIR(3),
    ONE_PAIR(2),
    HIGH_CARD(1);

private final int value;

HandType(int value) {
    this.value = value;
}

}

Class Hand

Aquí es donde está la mayor parte de la chicha:

public class Hand implements Comparable<Hand> {

private static final Pattern HANDS_PATTERN = Pattern.compile("(\\w*) (\\d*)");
private static final Character JOKER = 'J';

private List<Card> cards;
private int bid;
private HandType handType; // The hand type from strongest (7) to weakest (1).

public Hand(String input, boolean useJokers) {
    Matcher handMatcher = HANDS_PATTERN.matcher(input);

    if(handMatcher.find()) {
        cards = handMatcher.group(1).chars().mapToObj(c -> new Card((char)c, useJokers)).toList();
        bid = Integer.parseInt(handMatcher.group(2));
    }

    setHandType(useJokers);
}

private void setHandType(boolean useJokers) {
    Map<Character, Long> cardsByType = cards.stream()
            .map(Card::getNumber)
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

    if((!useJokers) || (!cardsByType.containsKey(JOKER))){
        setHandType(cardsByType);
    } else {
        setHandTypeWithJokers(cardsByType);
    }
}

private void setHandType(Map<Character,Long> cardsByType) {
    handType = switch(cardsByType.size()) {
        case 1: yield HandType.FIVE_OF_A_KIND;
        case 2: yield cardsByType.containsValue(4L) ? HandType.FOUR_OF_A_KIND : HandType.FULL_HOUSE;
        case 3: yield cardsByType.containsValue(3L) ? HandType.THREE_OF_A_KIND : HandType.TWO_PAIR;
        case 4: yield HandType.ONE_PAIR;
        case 5: yield HandType.HIGH_CARD;
        default: throw new IllegalStateException("Unexpected value: " + cardsByType.size());
    };
}

private void setHandTypeWithJokers(Map<Character,Long> cardsByType) {

    handType = switch(cardsByType.size()) {
        case 1,2: yield HandType.FIVE_OF_A_KIND;
        case 3: yield (cardsByType.containsValue(3L) || (cardsByType.get(JOKER) == 2L)) ? HandType.FOUR_OF_A_KIND : HandType.FULL_HOUSE;
        case 4: yield HandType.THREE_OF_A_KIND;
        case 5: yield HandType.ONE_PAIR;
        default: throw new IllegalStateException("Unexpected value: " + cardsByType.size());
    };
}

public int getValue(int rank) {
    return bid * rank;
}

@Override
public int compareTo(Hand o) {

    // Wins highest hand
    if(this.handType != o.handType) {
        return Integer.compare(this.handType.getValue(), o.handType.getValue());
    }

    // Wins first highest card found from left to right
    int i = 0;
    while(i < cards.size()) {
        Card thisCard = cards.get(i);
        Card otherCard = o.cards.get(i);
        if(thisCard.compareTo(otherCard) != 0) {
            return thisCard.compareTo(otherCard);
        }
        i++;
    }

    return 0;
}
}

Class CamelCards

public class CamelCards {

private final List<String> inputs;

public CamelCards(List<String> inputs) {
    this.inputs = inputs;
}

public int solve(boolean useJokers) {

    AtomicInteger rank = new AtomicInteger(1);
    return inputs.stream()
            .map(s -> new Hand(s, useJokers))
            .sorted()
            .map(h -> h.getValue(rank.getAndIncrement()))
            .reduce(0, Integer::sum);

}
}

Mandarino #200 8 Dic

Me he leido solo el enunciado del Day8 y pinta interesante. Me pregunto como será la parte2 para hacerlo un proceso lento...
Voy a ello a ver !

B

[Borrado] #201 8 Dic

Dia 8 parte 1, la parte 2 no es dificil pero es un poco palo de implementar

spoiler

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

read_graph(Acc) ->
  case io:get_line("") of
    eof -> Acc;
    Line ->
      {_, [NodeBin, LeftBin, RightBin]} =
        re:run(Line, "(.*) = \\((.*), (.*)\\)\n", [{capture, all_but_first, binary}]),
      [Node, Left, Right] = lists:map(fun binary_to_list/1, [NodeBin, LeftBin, RightBin]),
      NewGraph = maps:put(Node, [Left, Right], Acc),
      read_graph(NewGraph)
  end.

next_step(Mov, L, _) when Mov == $L -> L;
next_step(_, _, R) -> R.

num_steps([Mov], M, Current, Graph, Acc) when Mov == $\n ->
  num_steps(M, M, Current, Graph, Acc);

num_steps([Mov | T], M, Current, Graph, Acc) ->
  case Current == "ZZZ" of
    true -> Acc;
    _ ->
      [L, R] = maps:get(Current, Graph),
      Next = next_step(Mov, L, R),
      num_steps(T, M, Next, Graph, 1 + Acc)
  end.

solve() ->
  {Movements, _} = {io:get_line(""), io:get_line("")},
  Graph = read_graph(maps:new()),
  num_steps(Movements, Movements, "AAA", Graph, 0).

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

Parte 2, siendo francos he bruteforceado el num de ciclos sobre una longitud total porque el tamaño max / longitud avg del ciclo lo permitía. Podría haber hecho una diofántica o un LCM como una persona normal pero también podía dejarlo corriendo mientras me iba a cagar xD

spoiler

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

read_graph(Acc) ->
  case io:get_line("") of
    eof -> Acc;
    Line ->
      {_, [NodeBin, LeftBin, RightBin]} =
        re:run(Line, "(.*) = \\((.*), (.*)\\)\n", [{capture, all_but_first, binary}]),
      [Node, Left, Right] = lists:map(fun binary_to_list/1, [NodeBin, LeftBin, RightBin]),
      NewGraph = maps:put(Node, [Left, Right], Acc),
      read_graph(NewGraph)
  end.

next_step(Mov, L, _) when Mov == $L -> L;
next_step(_, _, R) -> R.

get_cycle([Mov], M, Current, Graph, Steps, Acc) when Mov == $\n ->
  get_cycle(M, M, Current, Graph, Steps, Acc);

get_cycle([Mov | T] = List, M, Current, Graph, Steps, Acc) ->
  Key = {length(List), Current},
  case maps:is_key(Key, Acc) of
    true ->
      CycleInit = maps:get(Key, Acc),
      NormMap = maps:from_list(
        [{{Kl, Kc}, V - CycleInit} || {{Kl, Kc}, V} <- maps:to_list(Acc), V >= CycleInit]
      ),
      maps:put("init_steps", CycleInit, NormMap);
    _ ->
      [L, R] = maps:get(Current, Graph),
      Next = next_step(Mov, L, R),
      NextMap = maps:put(Key, Steps, Acc),
      get_cycle(T, M, Next, Graph, Steps + 1, NextMap)
  end.

get_cycle_info(C) ->
  #{
    "Z" =>
      lists:sort(
        [Value || {{_, Key}, Value} <- maps:to_list(C), lists:last(Key) == $Z]
      ),
    "cycle_length" => lists:foldl(fun erlang:max/2, 0, maps:values(C)) + 1,
    "init_steps" => maps:get("init_steps", C)
  }.

% k * length + offset = target
% k = (target - offset) / length
can_match(CycleInfo, TargetSteps) ->
  Length = maps:get("cycle_length", CycleInfo),
  Offset = hd(maps:get("Z", CycleInfo)) + maps:get("init_steps", CycleInfo),
  ((TargetSteps - Offset) rem Length) == 0.

% solo funciona si cada ciclo de forma individual pasa por una unica casilla
% que termina en Z, si hay mas de una hay que probar todas las combinaciones
get_first_coincidence(Iteration, [HeadInfo | CycleInfos] = AllInfos) ->
  FirstCycleSteps =
    hd(maps:get("Z", HeadInfo)) + maps:get("init_steps", HeadInfo) +
    Iteration * maps:get("cycle_length", HeadInfo),
  RestCanMatch =
    lists:all(fun _(C) -> can_match(C, FirstCycleSteps) end, CycleInfos),
  case RestCanMatch of
    true -> FirstCycleSteps;
    _ -> get_first_coincidence(Iteration + 1, AllInfos)
  end.

solve() ->
  {Movements, _} = {io:get_line(""), io:get_line("")},
  Graph = read_graph(maps:new()),
  Origins = [X || X <- maps:keys(Graph), lists:last(X) == $A],
  Cycles = [get_cycle(Movements, Movements, X, Graph, 0, maps:new()) || X <- Origins],
  CycleInfos = [get_cycle_info(C) || C <- Cycles],
  io:format("~p~n", [CycleInfos]),
  FirstCycle = get_first_coincidence(0, CycleInfos),
  FirstCycle.

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

Mandarino #202 8 Dic

Parte 1 entretenida

Parte 2

spoiler

Ya se pone más interesante, cuando la fuerza bruta de por si no funciona xD

Mi intuición me decia que cada nodo de inicio (11A, 22A, MSA, ...) tardaria X pasos en llegar a xxZ, y luego desde ahi tardaria otros Y pasos para ir de xxZ al mismo xxZ (no puede ser otro porque lo dice el enunciado).

Lo que probé y no me funcionó
Función (cached) que, a partir de un nodo y indice para saber el siguiente camino, te devuelve el número de steps necesarios para llegar al siguiente xxZ Y en que indice del path acabas.
Con esto, creé una priority queue con (steps counter, current node) y iba avanzando el camino del que iba más atrasado. Con esto hacias muchos millones de steps por segundo, pero seguia siendo insuficiente para llegar a la solución a tiempo.

Observación que cambió la forma de resolverlo
Desde un inicio pensaba que el numero de pasos para ir de xxA->xxZ (X) y de xxZ->xxZ (Y) eran diferentes, y también que el "siguiente paso" (LLRLRLRR...) no tenia por qué ser el mismo. Hasta que no lo calculé no me di cuenta de que no era asi:

origin='MSA' -> XHZ (14893 steps) -> XHZ (14893 steps) indice path=0
origin='AAA' -> ZZZ (20513) -> ZZZ (20513) indice path=0
origin='PKA' -> FHZ (22199) -> FHZ (22199) indice path=0
origin='NBA' -> LSZ (19951) -> LSZ (19951) indice path=0
origin='RHA' -> RQZ (17141) -> RQZ (17141) indice path=0
origin='CDA' -> LXZ (12083) -> LXZ (12083) indice path=0

Para ir de MSA a XHZ tardas lo mismo que ir de XHZ->xxx->XHZ? Interesante, esto no lo vi mencionado en el problema. También me resultó interesante que siempre acabas en el indice del path 0 (al inicio). Si no fuera asi, supongo que se complicaria un huevo el problema.

Con esto, supe que basicamente seria buscar el número X mas pequeño que sea multiplo de 14893,20513,22199,19951,17141,12083. Estuve un rato buscando por que no recordaba que se llamaba "minimo comun multiplo". Una vez descubierto el termino, pues python "math.lcm(los numeros)" y solución encontrada! Un número de 13 digitos, no está mal.. Con razón lo del priority queue no llegaba.

edit: Me alegra pensar que no soy el único, parece que en reddit tambien hablan de para que LCM (least common multiple) se tienen que cumplir varias propiedades que no te dice el problema: https://www.reddit.com/r/adventofcode/comments/18dfpub/2023_day_8_part_2_why_is_spoiler_correct/

Ya pasé por el mismo problema en el pasado, que me enfoco solo en solucionar el "caso general" tal cual esta descrito el problema y me olvido de analizar los datos de este problema en concreto. No hace falta resolver cualquier input, solo este en concreto!

Frankicia #203 8 Dic

Lo de numeros grandes y enunciados a medias habria que discutirlo. Puedo entender los numeros grandes para "evitar" bruteforces. Pero el de hoy se oculta informacion de como es el input.
Cuando miras el input te das cuenta que puedes usar matematicas.

Le jour 8 - C++

spoiler

#include <algorithm>
#include <stdio.h>
#include <string>
#include <sstream>
#include <map>
#include <cmath>
#include <iostream>
#include <numeric>
#include <vector>
#include <iomanip>


int main(int argc, char * argv[]){

std::map<std::string, std::pair<std::string, std::string>> directions;
std::string line;

getline(std::cin, line);

std::istringstream iss(line);
std::string instructions;

iss >> instructions;
getline(std::cin, line);

std::vector<std::string> current_positions;
while(getline(std::cin, line)) {

    std::replace( line.begin(), line.end(), '=', ' ');
    std::replace( line.begin(), line.end(), ')', ' ');
    std::replace( line.begin(), line.end(), '(', ' ');
    std::replace( line.begin(), line.end(), ',', ' ');
    iss.str(line);
    iss.clear();

    std::string id, left, right;
    iss >> id >> left >> right;

    directions[id] = std::make_pair(left ,right);

    #ifdef SECOND_PART
       if (id[2] == 'A') current_positions.push_back(id);
    #else
       if (id == "AAA") current_positions.push_back(id);
    #endif

}

unsigned long long int steps = 0;
std::vector<unsigned long long int> results;
for(int i = 0; i < current_positions.size(); i++) {

    unsigned long long int local_steps = 0;
    std::string current_position = current_positions[i];
    char        current_instr    = instructions[0];

    while(current_position[2] != 'Z') {
        current_position = current_instr == 'L' ? directions[current_position].first : 
                                                  directions[current_position].second;
        local_steps++;
        current_instr = instructions[local_steps % instructions.length()];
    }
    results.push_back(local_steps);
    steps += local_steps;
}


std::cout << "Result: ";
#ifdef SECOND_PART
    std::cout << std::setprecision(15) << std::fixed;
    unsigned long long int result = 1.0;
    for(auto &i : results)
        result = std::lcm(result, i);
    std::cout << result << std::endl;
#else
    std::cout << (unsigned long long int)steps<< std::endl;
#endif

return 0;
}

1 respuesta

Mandarino #204 8 Dic

#203 Bueno eso ya se ha visto en otras ediciones, que hay un poco de analisis de datos. Para el que este sea su primer año y no conozca AoC (o no lo recuerde) pues le va a pasar como a nosotros xD. A mi me parece interesante que incluya esta parte a veces para hacerlo un poco diferente al tipico problema bien definido+resolver caso generico.

B

[Borrado] #205 8 Dic

Otra vez me la he comío xD Las he pasado putas para poner todos los borrows y mutable references en orden para la recursividad (qué locura de lenguaje Hulio) y al final me he comido un pene con el overflow. Para la parte 2 lo mismo; He tenido que tirar de un poco de ayudita porque lo había hecho a lo Berserker con 8 de inteligencia.

Día 08 Parte1 + Parte2 [Rust]

use std::collections::HashMap;

use regex::Regex;

use crate::handler::Handler;

#[derive(Debug)]
pub struct Day08 {
    pub node_mapper: HashMap<char, u32>,
}

impl Day08 {
    fn new() -> Self {
        Self {
            node_mapper: HashMap::from([('L', 0), ('R', 1)]),
        }
    }

fn process_input() -> (Vec<char>, HashMap<String, (String, String)>) {
    let input: Vec<String> = Handler::new("./src/day08/input.txt")
        .handle_input()
        .unwrap()
        .lines()
        .map(|line| line.to_string())
        .collect();

    let instructions: Vec<char> = input[0].chars().collect();
    let mut node_map: HashMap<String, (String, String)> = HashMap::new();
    input[2..].iter().for_each(|line| {
        let vec_values: Vec<&str> = Regex::new(r"\W+").unwrap().split(line).collect();

        node_map.insert(
            vec_values[0].to_string(),
            (vec_values[1].to_string(), vec_values[2].to_string()),
        );
    });

    (instructions, node_map)
}

// Recursion yields stack overflow; Works with examples though. Left for reference.
#[allow(dead_code)]
fn check_nodes_recursive(
    node_mapper: HashMap<char, u32>,
    instructions: &Vec<char>,
    node_map: &HashMap<String, (String, String)>,
    instruction_idx: &mut usize,
    current_node: &str,
) -> u32 {
    if current_node.ends_with('Z') {
        return 0;
    }

    if *instruction_idx > instructions.len() - 1 {
        *instruction_idx = 0
    }

    match node_mapper.get(&instructions[*instruction_idx]) {
        Some(&0) => {
            1 + Self::check_nodes_recursive(
                node_mapper,
                instructions,
                node_map,
                &mut (*instruction_idx + 1),
                &node_map.get(current_node).unwrap().0,
            )
        }
        Some(&1) => {
            1 + Self::check_nodes_recursive(
                node_mapper,
                instructions,
                node_map,
                &mut (*instruction_idx + 1),
                &node_map.get(current_node).unwrap().1,
            )
        }
        _ => panic!("Shouldn't reach this case."),
    }
}

fn check_nodes_iterative(
    node_mapper: HashMap<char, u32>,
    instructions: &Vec<char>,
    node_map: &HashMap<String, (String, String)>,
    instruction_idx: &mut usize,
    current_node: &mut String,
) -> usize {
    let mut sum = 1;
    loop {
        match node_mapper.get(&instructions[*instruction_idx]) {
            Some(&0) => *current_node = node_map.get(current_node).unwrap().0.to_string(),
            Some(&1) => *current_node = node_map.get(current_node).unwrap().1.to_string(),
            _ => panic!("Fuck borrowing."),
        }
        if current_node.ends_with('Z') {
            return sum;
        }

        *instruction_idx += 1;
        if *instruction_idx > instructions.len() - 1 {
            *instruction_idx = 0;
        }
        sum += 1;
    }
}

fn greatest_common_divisor(a: usize, b: usize) -> usize {
    if b == 0 {
        a
    } else {
        Self::greatest_common_divisor(b, a % b)
    }
}

fn least_common_multiple(a: usize, b: usize) -> usize {
    (a * b) / Self::greatest_common_divisor(a, b)
}

pub fn part1() -> usize {
    let input = Self::process_input();
    let day_handler = Self::new();

    Self::check_nodes_iterative(
        day_handler.node_mapper,
        &input.0,
        &input.1,
        &mut 0,
        &mut "AAA".to_string(),
    )
}

pub fn part2() -> usize {
    let input = Self::process_input();
    let day_handler = Self::new();

    input
        .1
        .keys()
        .filter(|key| key.ends_with('A'))
        .map(|node| {
            Self::check_nodes_iterative(
                day_handler.node_mapper.clone(),
                &input.0,
                &input.1,
                &mut 0,
                &mut node.to_string(),
            )
        })
        .reduce(|acc, next| Self::least_common_multiple(acc, next))
        .unwrap()
}
}

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

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

Flashk #206 8 Dic

Día 08

Al principio me he comido la trampa esta de que el nodo "AAA" en el input real no estaba en la primera fila, he perdido mucho rato pensando que había que hacer algún tipo de optimización sobre el grafo.

Y luego en la segunda parte, me daba tufillo a MCM, he ignorado mi intuición y luego finalmente he visto que no había otra salida que por ahí.

Nuevamente me ha ocupado más todo lo que es el código de parseo que el algoritmo en si.

Clase Node

@Getter
public class Node {

private final String label;

@Setter
private Node left;

@Setter
private Node right;

public Node(String label) {
    this.label = label;
}

public Node(String label, Node left, Node right) {
    this.label = label;
    this.left = left;
    this.right = right;
}

public Node move(char movement) {
    return movement == 'L' ? left : right;
}

}

Clase HauntedWasteland

public class HauntedWasteland {

private static final Pattern NETWORK_PATTERN = Pattern.compile("(\w*) = \((\w*), (\w*)\)");
private static final String STARTING_NODE = "AAA";
private static final String ENDING_NODE = "ZZZ";
private static final String GHOST_STARTING_NODE = "A";
private static final String GHOST_ENDING_NODE = "Z";
private final char[] movements;
private Node startNode;
private final Set<Node> ghostStartNodes = new HashSet<>();

public HauntedWasteland(List<String> inputs) {

    // Initialize movements
    movements = inputs.get(0).toCharArray();

    // Initialize nodes
    Map<String, Node> createdNodes = new HashMap<>();
    for(String input : inputs) {
        Matcher matcher = NETWORK_PATTERN.matcher(input);
        if(matcher.find()) {
            String label = matcher.group(1);
            String leftLabel = matcher.group(2);
            String rightLabel = matcher.group(3);

            Node left = createdNodes.getOrDefault(leftLabel, new Node(leftLabel));
            createdNodes.putIfAbsent(leftLabel, left);

            Node right = createdNodes.getOrDefault(rightLabel, new Node(rightLabel));
            createdNodes.putIfAbsent(rightLabel, right);

            Node node = createdNodes.getOrDefault(label, new Node(label, left, right));
            createdNodes.putIfAbsent(label, node);

            node.setLeft(left);
            node.setRight(right);

            if(node.getLabel().equals(STARTING_NODE)) {
                startNode = node;
            }

            if(node.getLabel().endsWith(GHOST_STARTING_NODE)) {
                ghostStartNodes.add(node);
            }
        }
    }

}

public long solveA() {
    return pathfind(startNode, false);
}

public long solveB() {
    return ghostStartNodes.stream()
            .map(n -> pathfind(n, true))
            .reduce(1L, ArithmeticUtils::lcm);
}

private long pathfind(Node startNode, boolean isGhost) {
    long steps = 0;
    Node currentNode = startNode;
    int movementIndex = 0;
    do {
        char movement = movements[movementIndex++ % movements.length];
        currentNode = currentNode.move(movement);
        steps++;
    } while (!isEnd(currentNode, isGhost));

    return steps;

}

private boolean isEnd(Node node, boolean isGhost) {
    String label = node.getLabel();
    if(isGhost && label.endsWith(GHOST_ENDING_NODE)) {
        return true;
    }

    return !isGhost && label.equals(ENDING_NODE);
}

}

Mandarino #207 9 Dic

Día 9

spoiler

B

[Borrado] #208 9 Dic

Parte 2 dia 9, la parte 1 es casi identica

spoiler

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

diff_list(L) ->
  [lists:nth(I, L) - lists:nth(I - 1, L) || I <- lists:seq(2, length(L))].

% f - x = p
% x = f - p
process_list(L, Acc) ->
  case lists:all(fun _(X) -> X == 0 end, L) of
    true -> 0;
    _ ->
      DiffList = diff_list(L),
      DiffHead = process_list(DiffList, Acc),
      NewDiffHead = hd(L) - DiffHead,
      NewDiffHead
  end.

solve(Acc) ->
  case io:get_line("") of
    eof -> Acc;
    Line ->
      List = lists:map(
        fun _(X) -> {Val, _} = string:to_integer(X), Val end,
        string:split(string:replace(Line, "\n", "", all), " ", all)
      ),
      Result = process_list(List, 0),
      solve(Acc + Result)
  end.

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

Frankicia #209 9 Dic

Un poco de recursividad para empezar el dia 9 - C++

spoiler

#include <stdio.h>
#include <string>
#include <sstream>
#include <iostream>
#include <vector>


std::pair<int,int> predict(std::vector<int> history) {

std::vector<int> differences;

bool all_zeroes = true;
for(int i = 1; i < history.size(); i++) {
    int diff = history[i] - history[i-1];
    if (diff) all_zeroes = false;
    differences.push_back(diff);
}

if (all_zeroes) return std::make_pair(history[0], history[history.size()-1]);

std::pair<int,int> extrapolated_values = predict(differences);

extrapolated_values.first  = history[0]                - extrapolated_values.first;
extrapolated_values.second = history[history.size()-1] + extrapolated_values.second;
return extrapolated_values; 


}

int main(int argc, char * argv[]){


std::vector<std::vector<int>> report_history;

std::string line;
while(getline(std::cin, line)) {

    std::vector<int> single_history;
    std::istringstream iss(line);
    std::string token;
    while( iss >> token ) {
        single_history.push_back(stoi(token));
    }

    report_history.push_back(single_history);
}

std::pair<int, int> sum = std::make_pair(0,0);
for(int i = 0; i < report_history.size(); ++i) {
    std::pair<int,int> extrapolated_values = predict(report_history[i]);
	sum.first  += extrapolated_values.first ;
	sum.second += extrapolated_values.second;
}

std::cout << "Result: " << std::endl;
std::cout << "left  extrapolation: " << sum.first  << std::endl;
std::cout << "right extrapolation: " << sum.second << std::endl;

return 0;
}

draz1c #210 9 Dic

Los que lo hicisteis por bruteforce la parte 2 de ayer cuanto tiempo os tardó en ejecutar? Porque para el input de ejemplo que ponen me sale el resultado correcto, pero al menterle el input gordo lleva ahi facilmente 2 minutos ejecutandose y no me termina de dar un resultado. Asi que quiero saber si es algo que una cpu lo podria calcular en apenas unos segundos y si tengo que pararlo porque tengo algo mal en el codigo o si dejarlo ejecutandose mas tiempo

1 respuesta

Usuarios habituales

Tags