Advent of Code 2020

GuaNaGe #91 Dic '20

Esta noche lo empezaré. Seré fiel a Java....

Lo mas jodido es el inglés, pero bueno. Soy muy pussy, losé

mecmec #92 Dic '20

#89 tengo bastante olvidado el tema, pero sería buscar la solución más óptima matemáticamente de forma que si el volumen de datos fuera muy superior se redujera el cómputo de forma significativa. Hacerlo por fuerza bruta debería ser la última solución a proponer ya que es directa.

2 respuestas

B

[Borrado] #93 Dic '20

#92 Ahora mismo que se me ocurra no veo mejor manera que fijar dos números x, y con dos loops y buscar en un hashmap, o mediante binary searches, 2020 - x - y, que sería cuadrático (o n² logn si usas binary search) en lugar de cúbico (lo que sería si usáramos tres loops).

Igualmente la entrada son 200 números, se puede sacar a fuerza bruta realmente.

B

[Borrado] #94 Dic '20

.

1 1 respuesta

B

[Borrado] #95 Dic '20

#94 por dios cuánto código no?

JuAn4k4 #96 Dic '20

Apuntame https://github.com/juancarrey/aoc-2020

QuitCat #97 Dic '20 Gafe

#92 sinceramente no creo que se pueda hacer en menos de O(n) que ya se ha puesto.

#86 está explicado en #80

1 respuesta

isvidal #98 Dic '20

Os dejo mi solucion de la parte 1 en JS, muy sencillo no? Al menos a lo bruto.

spoiler

const year = 2020

let index1 = null
let index2 = null

const filtered = data.filter((number) => number < year)

filtered.findIndex((number, i) => {
    const condition = (number2, j) => (number + number2 === 2020) && j !== i
    

index1 = i;
index2 = filtered.findIndex(condition)

return index2 !== -1
})

const result1 = filtered[index1] * filtered[index2]

Y el repo donde lo metere: https://github.com/jvidalv/advent-of-code-2020

edit la parte 2 aun mas guarra:

spoiler

    let index1 = null
    let index2 = null
    let index3 = null

filtered.findIndex((number, i) => {
    index1 = i;

    filtered.findIndex((number2, j) => {
        const condition2 = (number3, x) => ((number + number2 + number3 )=== 2020) && x !== j && x !== i && j !== i

        index2 = j
        index3 = filtered.findIndex(condition2)
        
        return index3 !== -1
    })

    return (index2  && index2 !== -1) && (index3  && index3 !== -1)
})

return filtered[index1] * filtered[index2] * filtered[index3]

aren-pulid0 #99 Dic '20

Entonces para la parte 1 que es la más sencilla:

¿Lo correcto es hacer un hashmap con la misma clave:valor por cada elemento de la lista de números y luego iterar sobre ese hashmap?

1 respuesta

ckrass #100 Dic '20

#99 No. En ningún momento iteras el hashmap.

Se utiliza como si una caché se tratara para no tener que volver a calcular x cosas ...

R

RsTTa #101 Dic '20

Bueno, otro año más, nunca he terminado todos los dias, este año currando menos U.u
usuario AoC: NovelleP
repo: https://github.com/NovelleP/AdventOfCode2020

Ya de paso dejo solucion del día 1 en Python

parte 1: O(N) en tiempo y espacio

spoiler

def search_target_by_2numsum(nums, target):
    diff = set()
    for num in nums:
        if (target - num) in diff:
            return (target - num), num
        diff.add(num)
    return float('nan'), float('nan')


if __name__ == '__main__':
    with open('input', 'r') as f:
        nums = [int(num) for num in f.readlines()]
    target = 2020
    num1, num2 = search_target_by_2numsum(nums, target)
    print(num1, num2, num1*num2)

parte 2: O(N²) en tiempo y O(N) espacio

spoiler

def search_target_by_3numsum(nums, target):
    for idx1 in range(len(nums)):
        diff = set()
        for idx2 in range(idx1 + 1, len(nums)):
            if (target - nums[idx1] - nums[idx2]) in diff:
                return nums[idx1], nums[idx2], (target - nums[idx1] - nums[idx2])
            diff.add(nums[idx1])
            diff.add(nums[idx2])
    return float('nan'), float('nan'), float('nan')


if __name__ == '__main__':
    with open('input', 'r') as f:
        nums = [int(num) for num in f.readlines()]
    target = 2020
    num1, num2, num3 = search_target_by_3numsum(nums, target)
    print(num1, num2, num3, num1*num2*num3)

aren-pulid0 #102 Dic '20

Joder que rabia me da no haber ido a la universidad, podría alguien decirme dónde puedo aprender un básico de la complejidad algorítmica?

No me entero cuando habláis de eso, y aunque intuyo ciertas cosas porque mi solución "se parece" no llego a entender el porqué de la cosas ni cómo funciona mi código por dentro

Si me pasáis alguna documentación o algún sitio por dónde empezar estaría muy agradecido

1 respuesta

JuAn4k4 #103 Dic '20

Parte1 en Rust, la niña no para de despertarse xD: https://github.com/juancarrey/aoc-2020/commit/86c15b9596b2d8ee026887466b6b93f368fde625

La solución es un Set, metes todo al set, y luego iteras el set para buscar el remaining de cada uno (2020 - x), hasta que encuentres el que lo tiene (se presupone que solo hay 1) y ya está.

Fase 2 en 1 minuto: https://github.com/juancarrey/aoc-2020/commit/bb3cb5093a327fc57c4087483c96a56893f3316c

2 respuestas

B

[Borrado] #104 Dic '20

#97 vale ya entiendo lo que quieres decir, tienes razón, al hacer a y luego b, en b coincide con el mismo que a, tenía que haber controlado eso, cierto

Gracias

isvidal #105 Dic '20

#103 En las especificaciones no dicen nada de no repetidos, de ser eso cierto si que es verdad que con un set te quitas complejidades.

1 respuesta

JuAn4k4 #106 Dic '20

#105 Funciona perfectamente, no hay repetidos, ni más de un resultado, salvo el hecho de que a+b = b+a y a+b+c = a+c+b = b+a+c = b+c+a = c+a+b = c+b+a
Tampoco está el 1010 por lo que no hace falta comprobar que esté, lo mismo pasa para cuando hay 3 , tipo: a+b+b. No he hecho ninguna comprobación para esos casos.

MaSoBa #107 Dic '20 Penitente

#103 En ese caso, si en el input hay dos 1010 no valdría no?

En otro orden de cosas, ¿sería más eficiente ordenar primero el array para no seguir calculando más allá del número 1010?

1 respuesta

JuAn4k4 #108 Dic '20

#107 No, es más barato recorrerlo que ordenarlo, a no ser que hagas bucket sort, y aun así no creo que compense. (Lo que sí puedes hacer es saltartelos, y en fase2 saltarte b, si b<a).
Y no, no funciona si hay dos 1010, o en la fase 2, si hay repetidos.

Pero vamos si hubiera repetidos seria cambiar el set por un map y tener el count de numeros que hay, para poder usar un número más de una vez:

si hay dos a -> probar 2a+b
si hay 3, probar 3a
probar a+b+(remaining)

voy a hacerlo... xD

1

LLoid #109 Dic '20

me apunto yo también, pero voy con retraso

y aparte llego tarde HUEHUE

B

[Borrado] #110 Dic '20

.

JuAn4k4 #111 Dic '20

Actualizado comprobando los edge cases de las dos fases usando HashMap con count, aunque no hace falta para nada pero bueno: https://github.com/juancarrey/aoc-2020/commit/8f0cd1e12c8e17f869e02d1e6071fadc9a6f52ba
Muy guarro pero me voy a dormir que sino no duermo nada.

GuaNaGe #112 Dic '20

¿Alguien que controle de java podría pasarme su solución para echarle un ojo y comparar? La mía es basura máxima. Curro mañana y la he picado volando

spoiler


public static Integer logicaPart1(ArrayList<String> lista) {
	Integer resultado = 0;
	
	for (int i = 0; i < lista.size(); i++) {
		for (int j = i + 1; j < lista.size(); j++) {
			if (Integer.valueOf(lista.get(i)) + Integer.valueOf(lista.get(j)) == 2020) {
				resultado = Integer.valueOf(lista.get(i)) * Integer.valueOf(lista.get(j));
			}
		}
	}

	return resultado;
}

public static Integer logicaPart2(ArrayList<String> lista) {
	Integer resultado = 0;
	
	for (int i = 0; i < lista.size(); i++) {
		for (int j = i + 1; j < lista.size(); j++) {
			for (int k = j + 1; k < lista.size(); k++) {
				if (Integer.valueOf(lista.get(i)) + Integer.valueOf(lista.get(j)) + Integer.valueOf(lista.get(k)) == 2020) {
					resultado = Integer.valueOf(lista.get(i)) * Integer.valueOf(lista.get(j)) * Integer.valueOf(lista.get(k));
				}
			}
		}
	}

	return resultado;
}

Traber #113 Dic '20

Venga masillas, que el segundo caso es facilón también:

spoiler

using System;
using System.IO;
using System.Linq;

namespace Day2 {
    class Program {
        static void Main(string[] args) {
            int ValidFirst  = FirstPolicy();
            int ValidSecond = SecondPolicy();
        }

    public static int FirstPolicy() {
        string[] Input = File.ReadAllLines("input.txt");

        int Correct = 0;

        foreach(string Line in Input) {
            // 4-10 w: wwccwcqwdmbktjrxhw
            string[] LineData   = Line.Split(": ");
            string[] PolicyData = LineData[0].Split(" ");
            string[] MinMaxData = PolicyData[0].Split("-");

            int    Min       = Int32.Parse(MinMaxData[0]);
            int    Max       = Int32.Parse(MinMaxData[1]);
            string Password  = LineData[1];
            char   Character = PolicyData[1].ToCharArray()[0];

            int    Occurences = Password.Count(f => f == Character);

            if(Occurences >= Min && Occurences <= Max) {
                Correct++;
            }
        }

        return Correct;
    }

    public static int SecondPolicy() {
        string[] Input = File.ReadAllLines("input.txt");

        int Correct = 0;

        foreach(string Line in Input) {
            // 4-10 w: wwccwcqwdmbktjrxhw
            string[] LineData   = Line.Split(": ");
            string[] PolicyData = LineData[0].Split(" ");
            string[] MinMaxData = PolicyData[0].Split("-");

            int    FirstIndex  = Int32.Parse(MinMaxData[0]);
            int    SecondIndex = Int32.Parse(MinMaxData[1]);
            string Password    = LineData[1];
            char   Character   = PolicyData[1].ToCharArray()[0];

            int    Occurences = 0;

            if(Password[FirstIndex - 1] == Character) {
                Occurences++;
            }
            if (Password[SecondIndex - 1] == Character) {
                Occurences++;
            }

            if(Occurences == 1) {
                Correct++;
            }
        }

        return Correct;
    }
}
}

pineda #114 Dic '20

no entiendo como me lo formatea mal... en fin, link directo
https://github.com/pineda89/advent-of-code-2020/blob/master/day02/main.go

spoiler

package main

import (
	"fmt"
	"io/ioutil"
	"strconv"
	"strings"
)

func main() {
	content, err := ioutil.ReadFile("input.txt")
	checkErr(err)

lines := strings.Split(string(content), "\n")

counterValidsMethod1 := 0
counterValidsMethod2 := 0

for _, v := range lines {
	pw := &PasswordValidator{}
	pw.LineToPasswordValidator(v)
	if pw.isValidMethodOne() {
		counterValidsMethod1++
	}
	if pw.isValidMethodTwo() {
		counterValidsMethod2++
	}
}

fmt.Println("counterValidsMethod1", counterValidsMethod1)
fmt.Println("counterValidsMethod2", counterValidsMethod2)
}

func checkErr(err error) {
	if err != nil {
		panic(err)
	}
}

type PasswordValidator struct {
	MinTimes int
	MaxTimes int
	Char string
	Chain string
}

func (pw *PasswordValidator) LineToPasswordValidator(input string) {
	pw.MinTimes, _ = strconv.Atoi(strings.Split(input, "-")[0])
	pw.MaxTimes, _ = strconv.Atoi(strings.Split(strings.Split(input, "-")[1], " ")[0])
	pw.Char = strings.Split(strings.Split(input, " ")[1], ":")[0]
	pw.Chain = strings.Split(input, ": ")[1]
}

func (pw *PasswordValidator) isValidMethodOne() bool {
	count := strings.Count(pw.Chain, pw.Char)
	return count >= pw.MinTimes && count <= pw.MaxTimes
}

func (pw *PasswordValidator) isValidMethodTwo() bool {
	return (pw.Chain[pw.MinTimes-1:pw.MinTimes] == pw.Char && pw.Chain[pw.MaxTimes-1:pw.MaxTimes] != pw.Char) ||
		(pw.Chain[pw.MinTimes-1:pw.MinTimes] != pw.Char && pw.Chain[pw.MaxTimes-1:pw.MaxTimes] == pw.Char)
}

1 respuesta

Traber #115 Dic '20

#114 Hostia el tryhardeo de pasar cada línea a un objeto la virgen xD. Bien hecho, pero joder, para algo como esto ni me lo había planteado.

aren-pulid0 #116 Dic '20

Si no haces la prueba el día que sale no te dan la estrellita?

1 respuesta

BeheritSp #117 Dic '20 Juntabrackets

Dejo aquí mi day2 en python:

spoiler


file_lines = open("input.txt").readlines()
count = 0
for line in file_lines:
    split_line=line.split()
    # getting min_max values
    min_value=int(split_line[0].split('-')[0])
    max_value=int(split_line[0].split('-')[1])
    required_letter = split_line[1][0]
    # check if pass is ok:
    n_apperances = split_line[2].count(required_letter)
    if n_apperances >= min_value and n_apperances<=max_value:
        count += 1

print("Valid passwords:", count)

count = 0
for line in file_lines:
    split_line=line.split()
    # getting list positions
    first_pos=int(split_line[0].split('-')[0]) - 1
    second_pos=int(split_line[0].split('-')[1]) - 1
    required_letter = split_line[1][0]
    string_to_check = split_line[2]
    if (string_to_check[first_pos] == required_letter) != (string_to_check[second_pos] == required_letter):
        count += 1
print("Valid passwords part 2:", count)

1 respuesta

NeV3rKilL #118 Dic '20 :psyduck:

Yo he creado 3 listas una de diccionarios con la política, una de strings con el password y una de booleanos de si cumplían. Luego simplemente era contar cuantos true tenía la de booleanos. Está bien para jugar con list comprehension.

#117 Elegante la segunda comprobación.

if (string_to_check[first_pos] == required_letter) != (string_to_check[second_pos] == required_letter):

1 1 respuesta

B

[Borrado] #119 Dic '20

Yo lo he hecho con regex

Parte 1

spoiler

import re
regex = re.compile(r'([0-9]+)-([0-9]+) ([a-z]): ([a-z]+)')

total_number = 0

for line in open('input.txt', 'r').readlines():
    match = re.match(regex, line)
    at_least, at_most, criteria_char, password = \
        [match.group(i) for i in range(1, 5)]
    occurences = password.count(criteria_char)
    if occurences >= int(at_least) and occurences <= int(at_most):
        total_number += 1

print(total_number)

Parte 2

spoiler

import re
regex = re.compile(r'([0-9]+)-([0-9]+) ([a-z]): ([a-z]+)')

total_number = 0

for line in open('input.txt', 'r').readlines():
    match = re.match(regex, line)
    pos_1, pos_2, criteria_char, password = \
        [match.group(i) for i in range(1, 5)]
    occurences = password.count(criteria_char)
    if (password[int(pos_1) - 1] == criteria_char) ^ (password[int(pos_2) - 1] == criteria_char):
        total_number += 1

print(total_number)

Axtrix #120 Dic '20 Diamond hands

Q.E.D

spoiler

import { data } from './data';

export const result: {
  min: number;
  max: number;
  letter: string;
  password: string;
}[] = data.split(/\r\n|\r|\n/g).map(i => {
  const splitted = i.split(' ');
  return {
    min: Number(splitted[0].split('-')[0]),
    max: Number(splitted[0].split('-')[1]),
    letter: splitted[1].split(':')[0],
    password: splitted[2],
  };
});

export const step1 = result.filter(passwordEntry => {
  if (
    passwordEntry.min <=
      Number(passwordEntry.password.split(passwordEntry.letter).length - 1) &&
    Number(passwordEntry.password.split(passwordEntry.letter).length - 1) <=
      passwordEntry.max
  ) {
    return passwordEntry;
  }
});

//step1.length === 396

export const step2 = result.filter(passwordEntry => {
  if (
    (passwordEntry.password[passwordEntry.min - 1] === passwordEntry.letter &&
      passwordEntry.password[passwordEntry.max - 1] !== passwordEntry.letter) ||
    (passwordEntry.password[passwordEntry.max - 1] === passwordEntry.letter &&
      passwordEntry.password[passwordEntry.min - 1] !== passwordEntry.letter)
  ) {
    return passwordEntry;
  }
});

//step2.length === 428

¿Dónde me apunto?

Normas

Leaderboard privado para el pique sano

Las respuestas se postean en Spoiler + code

Usuarios habituales

Tags