Advent of Code 2020

B

[Borrado] #151 Dic '20

#149 Yo ayer estuve pensando en una idea para hacerlo nlogn, pero no consigo acabar de pulirla, te la cuento por si quieres seguir o pensarla.

Definimos dos arrays, S y P

S[ i ] = numero de elementos del array menores o iguales a i
P[ i ] = numero de parejas que su suma es menor o igual a i

S y P pueden calcularse en tiempo lineal, inicialmente asignamos S[ i ] = ocurrencias de i en el array y para cada a[ i-1 ] + a[ i ] sumamos i a P[ a[ i-1 ] + a[ i ] ] .

Luego con un for sumamos S[ i - 1 ] a S[ i ], y lo mismo con P. Con esto no es dificil ver que consigues S y P en tiempo lineal con dos pasadas al array. Esto ultimo es porque si a < b entonces a < b + 1.

Ahora considera S y P como polinomios. El producto de S y P es un polinomio T tal que

T[ k ] = sum (i + j = k) S[ i ] * P[ j ]

o en otras palabras T[ i + j ] contiene el numero de tripletes a,b,c tales que a + b + c <= i + j.

Con la FFT podemos pasar los polinomios a point-value form en O(nlogn) rapidamente, y multiplicando elemento a elemento las transformadas obtenemos T en point-value form. Haciendo la transformada inversa obtenemos T en forma de coeficiente. Si hay un i tal que T[ i ] > T[ i - 1 ] entonces existe un triplete que suma exactamente i.

El problema? T tambien contiene los tripletes de la forma ai,,ai,aj, y no se descartarlos. Tampoco te permite rescatar que triplete da la suma. Pero me parece interesante compartirlo por si a alguien se le ocurre (y se aburre lo bastante) una forma de arreglarlo.

Esto es asumiendo que los numeros que salen en el array estan acotados linealmente por el tamaño de la entrada. También puede probarse a hacerse con programación dinámica, pero con eso creo que te quedaría cuadrático, como con la solución de hashing.

2 respuestas

AikonCWD #152 Dic '20 Git Gud

Vale me acabo de dar cuenta que cada día tiene 2 pruebas xddd. Aquí la parte 2 del día 2:

spoiler

Voy a hacer la parte 2 del día 1... ahora vengo
edit: ya tengo ambas partes de los 2 días.

Me molaría poder leer el input con un http_get, pero te tienes que validar ya que cada input es único por usuario y me da mucho palo programar eso.

Fyn4r #153 Dic '20 Inocente

Hice el primer día y la primera parte del segundo día, voy a comer, luego termino y apunto a algunos que me faltan. Gracias @jastro por la cabecera y eso, no sabía ni como se hacía xD

P.D el primero del día 2 lo hice con 1 oneliner, para que luego os quejéis de mi toque

spoiler

https://github.com/Fynardo/AoC2k20/blob/main/day2/pwdfixer.py

filter(lambda passwd: passwd.lower <= passwd.text.count(passwd.letter) <= passwd.upper, passwords)

#151 Te leia con atención hasta FFT jajajaj

2 3 respuestas

B

[Borrado] #154 Dic '20

#153 O sea, da igual que se use la FFT. Piensa en la parte de productos de polinomios sin tener en cuenta como lo calculas, yo creo que la idea no está mal pero no acaba de funcionar...

AikonCWD #155 Dic '20 Git Gud

#153 Apúntame a mi, mi usuario es siempre AikonCWD

1 respuesta

aren-pulid0 #156 Dic '20

#153 Joder que elegante la solución, mis dies

Fyn4r #157 Dic '20 Inocente

#155 Apuntado, no sé si estás metido en la clasificación privada, está el código en #1

1 respuesta

Jastro #158 Dic '20 Moderador

#145 son cosas mias o estas usando gscript? xD

1 respuesta

AikonCWD #159 Dic '20 Git Gud

#158 Estoy usando Godot, evidentemente xd

#157 Como me meto en esa clasificación? donde pongo ese codigo?

1 1 respuesta

MartiONE #160 Dic '20 El reportero de guerra sonriente

#159 private leaderboard

GuaNaGe #161 Dic '20

Es posible realizar la segunda fase del primero con un solo bucle y usando set?

AikonCWD #162 Dic '20 Git Gud

qué asco salgo en la posición 12

1 respuesta

LLoid #163 Dic '20

pues aquí la primera parte del día 2:

spoiler

fun solveFirstPart(): Int {
        var count = 0

    this.input.forEachLine { line ->
        val chunks = line.split(" ")
        val range = this.getRange(chunks[0])
        val charToFind = chunks[1].replace(":", "")
        if (chunks[2].count { it.toString() == charToFind } in range) {
            count++
        }
    }

    return count
}

 private fun getRange(input: String): IntRange {
        val chunks = input.split("-")
        repeat(chunks.size) { return IntRange(chunks.first().toInt(), chunks.last().toInt()) }
        throw IllegalArgumentException("Invalid input")
    }

y aquí la segunda parte del día 2:

spoiler

fun solveSecondPart(): Int {
        var count = 0

    this.input.forEachLine { line ->
        var found = 0
        val chunks = line.split(" ")
        val positions = this.getPositions(chunks[0])
        val charToFind = chunks[1].replace(":", "")

        positions.forEach {
            if (chunks[2].toCharArray()[it - 1] == charToFind.toCharArray()[0]) {
                found++
            }
        }

        if (found == 1) {
            count++
        }
    }

    return count
}

private fun getPositions(input: String): IntArray {
        val positions = arrayListOf<Int>()
        val chunks = input.split("-")
        chunks.forEach { positions.add(it.toInt()) }
        return positions.toIntArray()
    }

MTX_Anubis #164 Dic '20 :psyduck:

Venga que me he animado en un rato mientras se hacen deploys

El del día 1 no lo pongo porque ha sido con bucles puros y duros:

Day 2 - 1: Con exp regular ahí:

spoiler

const fs = require('fs');
const input = fs.readFileSync(`${__dirname}/input.txt`, 'utf8')
  .toString()
  .split("\n")
  .map(entry => {
    let [numbers, letter, pass] = entry.split(' ');
    const [min, max] = numbers.split('-').map(n => parseInt(n, 10));
    letter = letter.replace(':','')
    return [min, max, letter, pass]
  });
let valid = 0;

input.forEach(([min, max, letter, pass]) => {
  const reg = new RegExp(`${letter}`, 'g');
  const count = (pass.match(reg) || []).length
  if (min <= count && count <= max) {
    valid++;
  }
})

console.log(valid)

Day 2 - 2:

spoiler

const fs = require('fs');
const input = fs.readFileSync(`${__dirname}/input.txt`, 'utf8')
  .toString()
  .split("\n")
  .map(entry => {
    let [numbers, letter, pass] = entry.split(' ');
    const [min, max] = numbers.split('-').map(n => parseInt(n, 10) - 1);
    letter = letter.replace(':','')
    return pass[min] === letter ^ pass[max] === letter
  })
  .reduce((a, b) => a + b, 0)

console.log(input)

mecmec #165 Dic '20

En javita sin regex guarreando:

spoiler

private static void parte1(List<String> serie) {
int totalOk = 0;
for (String password : serie) {
int i0 = Integer.parseInt(password.split("-")[0]);
int i1 = Integer.parseInt(password.split("-")[1].split(" ")[0]);

		String letra = password.split("-")[1].split(" ")[1].substring(0,1);
		String palabraLimpia = password.split(":")[1].substring(1);
		
		List<String> prueba = new ArrayList<String>(Arrays.asList(palabraLimpia.split("")));
		prueba.removeIf(e -> !letra.equals(e));
	 
		if (prueba.size() >= i0 && prueba.size() <= i1) {
			totalOk ++;
		}
	 }
	System.out.println(totalOk);
}
private static void parte2(List<String> serie) {
	 int totalOk = 0;
	 for (String password : serie) {
		int pos1 = Integer.parseInt(password.split("-")[0]);
		int pos2 = Integer.parseInt(password.split("-")[1].split(" ")[0]);
		int count = 0;
		
		String letra = password.split("-")[1].split(" ")[1].substring(0,1);
		String palabraLimpia = password.split(":")[1];
		
		List<String> prueba = new ArrayList<String>(Arrays.asList(palabraLimpia.split("")));

		if (prueba.size() > pos1 && prueba.get(pos1).equals(letra)) count++;
		if (prueba.size() > pos2  && prueba.get(pos2).equals(letra)) count++;
		
		if (count == 1) {
			totalOk ++;
		}
	 }
	 
		System.out.println(totalOk);
}

NeV3rKilL #166 Dic '20 :psyduck:

#162 Si quieres competir tienes que estar a las 6 de la mañana aquí completando lo más rápido posible.

El año pasado en MV no se pasó ni del ejercicio 15. https://adventofcode.com/2019/leaderboard/private/view/334594

A ver si este año alguien lo completa.

Yo que ahora lo hago con un lenguaje conocido la diferencia es abismal. Recuerdo hacer el del año pasado con lenguajes raros y tirarme más rato mirando la doc que solucionando el puzle. Pero yo soy un infiltrado, no me dedico a esto de manera profesional

3 respuestas

AikonCWD #167 Dic '20 Git Gud

#166 Tiene pinta que va a escalar la dificultad a lo bestia. Me conformo con llegar al día 5.

1 respuesta

R

RsTTa #168 Dic '20

#102 No tengo una documentación especifica sobre esto. Lo que puedes hacer es buscar analisis algoritmico o analisis complejidad de un algoritmo y tirar por ahi. Ya sabes, si lo haces en ingles pues tendras mas info.
Si no te quieres complicar mucho yo primero iria a tener una idea general, vamos que la mayoria del codigo que haces se puede analizar con una idea basica sobre complejidad.

#151 esto es lo mas optimo que he visto
https://en.m.wikipedia.org/wiki/3SUM

Por cierto, #1 apuntame cuando puedas:
usuario AoC: NovelleP
repo: https://github.com/NovelleP/AdventOfCode2020

1 respuesta

Fyn4r #169 Dic '20 Inocente

#166 Ojo quien ocupa ese top 1

#168 apuntado

P.D os recuerdo que teneis que meteros en el leaderboard privado, yo no puedo añadir gente :_

Unrack #170 Dic '20

#166 #167 A ver cuando llegan los intcode computer para ir bajándonos del barco. Yo hice hasta el día 10 u 11 y tres o cuatro fueron modificaciones del intcode...

2 2 respuestas

NeV3rKilL #171 Dic '20 :psyduck:

#170 No me recuerdes lo de ese hijo de satanás

AikonCWD #172 Dic '20 Git Gud

#170 que es eso?

1 respuesta

Unrack #173 Dic '20

#172 https://adventofcode.com/2019/day/2 Todo empezó aquí. Este era sencillo pero cada vez te iban pidiendo más y más.
https://adventofcode.com/2019/day/5
https://adventofcode.com/2019/day/7
https://adventofcode.com/2019/day/9
https://adventofcode.com/2019/day/13

2 respuestas

HeXaN #174 Dic '20

#173 Fueron un coñazo poco inspirados esos problemas. Yo lo dejé ahí también.

Fyn4r #175 Dic '20 Inocente

#173 fue lo mejor del año pasado, el que jugaba al pong era brutal Jajaja

1 respuesta

Unrack #176 Dic '20

#175 He revisado y me quedé a las puertas de ese. Igual me le miro hehe.

Si es que he vuelto a mirar y el último era otro sobre el intcode jaja

AikonCWD #177 Dic '20 Git Gud

Pues esta mierda tiene pinta de escalar en dificultad como la espuma.

A ver si llego al día 5 sin dropearlo xd

desu #178 Dic '20

spoiler


(ns aocl.2
  (:gen-class)
  (:require [aocl.core :refer [read-file-into-lines]])
  (:require [clojure.string :as str]))

; Example of a Record, if we wanted ploymorphism and/or dynamic dispatching 
; always use plain hash maps until you really need polymorphism and then decide whether you want
; multi-methods (dispatch on one or more arguments/attributes) 
; or protocols (dispatch on just the type).
(defrecord Password [char min max seq])
; default constructor is
; (->Password char min max seq)

(def input (list (read-file-into-lines "2.txt")))

(defn make-password 
  [char min max seq]
  (hash-map :char (nth char 0) :min min :max max :seq seq))

(defn split-by 
  [input]
  (map #(str/split % #" ") input))

(defn to-flatten-list 
  [tokens]
 (apply list (flatten tokens)))

(defn to-range 
  [raw-range]
  (map #(Integer/parseInt %) ( str/split raw-range #"-")))

(defn token-to-password 
  [token]
  (let [[raw-range char seq] (to-flatten-list token)
       [min max] (to-range raw-range)]
       (make-password char min max seq)))

(defn count-char [char string]
  (loop [i 0 r 0]
    (if (>= i (count string)) r
      (recur 
        (inc i) 
        (if (= (nth string i) char) (inc r) r)))))

(defn is-valid [{:keys [char min max seq]}]
  (let [count (count-char char seq)]
    (and (>= count min) (<= count max))))

(defn count-valid-password [input] 
  (let [tokens (split-by input)
        passwords (map token-to-password tokens)
        valid-passwords (filter is-valid passwords)]
        (count valid-passwords)))

(def solve1 (list(map count-valid-password input)))

(def part1 (str "part1: " solve1))

(defn -main [& args] (run! println [part1]))

Aun no he solucionado el problema de las sequencias xd pero bueno, dejo la primera version. para los que dicen que lisp es dificil de entender fijaros que facil se lee si defines funciones en lguar de usar lambdas en todos lados... Y tambien puedes hacer pipes con -> para darle la vuelta y que se lea como un stream en otros lenguajes como ocaml, rust, java......

He estado practicando un poco con los records, al final lo he dejado con un map y he hecho un poco de deconstruccion.

1 respuesta

JuAn4k4 #179 Dic '20

¿ Yo imagino que irán aprendiendo año a año con las estadísticas de los drops no ?

#178 A mi lisp me gustaba mucho en la universidad, creo que es de los que más me gustan de los que conozco. Con ADA también estaba encantado la verdad. C lo aborrecía, y prolog no se me dió nada bien (aunque tampoco lo intenté mucho), Java lo odiaba con todas mis ganas. He de decir que quedé maravillado con la solución del profesor a resolver un sudoku en prolog.

1 respuesta

Saiko9 #180 Dic '20

Es totalmente obligatorio hacerlos todos en el mismo dia que salen para ganar las estrellas? De momento he hecho los dos primeros en su dia, pero seguramente haya dias que igual ni toque el ordenador.

Dejo la solución del 2, en c++:

https://github.com/Semedi/aoc_2020/blob/main/day2.cpp

Yo en estas cosas siempre hago lo mismo, mi objetivo es aprender c++ y no resolver los problemas de forma rápida (aunque me molan los algoritmos). Asi que basicamente voy a hacer lo contrario a one-liners, lo que quiero es familizarizarme con el lenguaje y usar cuantas mas cosas mejor xD.

De momento esta siendo todo un éxito ya que estoy aprendiendo, aunque lo deje en el dia 3 habrá merecido la pena xDD.

2 respuestas