Advent of Code 2020

¿Dónde me apunto?

https://adventofcode.com/

Normas

  • Cada día se desbloquea un problema nuevo
  • Programas en el lenguaje que te da la gana
  • Utilizas las técnicas que te da la gana
  • Le dedicas el tiempo que te da la gana
  • Cada problema tiene una caja de texto para meter la solución (suelen ser números o alguna cadena de texto pequeña)

Leaderboard privado para el pique sano

NSFW

Las respuestas se postean en Spoiler + code

Traber

El mejor grafo es un documento HTML, el DOM es un mapa de grafos enorme. Para daros una idea, es como un tío en silla de ruedas que se chupa su propia polla.

Huk

Yo haría matplotlib o pandas/anaconda todo el día y luego ya saldría de casa, de lo contrario eres una vergüenza de ciudadano

2 respuestas
B

#572 @RusTu no notaste que te faltaba alguien en el recuento? Llévatelo por favor jajaja

1
Traber

#572

#572Huk:

patplotlib

Algunos deberían repasar mejor los cuadernillos rubio antes de dar lecciones a los demás. No homo. <3.

1 respuesta
Huk

#574 se te ve asertivo, inteligente y muy poco llorón. No parece que seas un imbécil. Yo creo que sabes programar.

1 respuesta
Traber

#575 Nah, soy un hater porque me gusta el salseo, pero el que me conoce bien sabe que soy un cacho de pan que siempre va a echar una mano. Pero siempre que puedo, voy a tocar los huevos por los loles xD.

JonaN
Día 8, Python
Fyn4r

Yo me iba a poner con esto pero me estoy comiendo unas porras, no homo

1
ciza

Yo lo he hecho con fuerza bruta como todos pero quizá sería inteligente ejecutar el programa a la inversa y ver desde donde puedes llegar a la última instrucción y eventualmente encuentras que hay una instrucción a la que no se llega y el jmp anterior está mal.

2 respuestas
Traber

#579 Hostia, me has dado una idea, dame 10 minutos.

Edito: No, da igual, hay que hacer fuerza bruta inversa igualmente, así que GL xd.

BeheritSp

Fuerza bruta tambien :D lo de hacerlo al reves suena bien.

Aunque sean mas lineas, me ha hecho gracia hacer dos clases: GameBoy y GameBoyHacked

Part 1
Part 2
Ranthas

Bueno, terminado el día de hoy, el mayor por culo Java y su mierda de paso de parámetros por valor, cuando te das cuenta has estado modificando el vector original en lugar de la copia.

Yo también pensé en recorrer el programa hacia atrás #579, pero hay varios pitfalls: uno, para llegar a la instrucción X, puedes llegar o bien secuencialmente desde X-1, pero también desde cualquier jump cuya posición + offset = X; por tanto, no puedes determinar cual de esas instrucciones es la que te dirige hasta la instrucción actual.

No lo he comprobado empíricamente, pero vamos, que quizás sí se pueda, pero es mejor tirar de fuerza bruta y a correr

Fyn4r

Se viene intcode 2.0? Se me va a ir de las manos otra vez

r2d2rigo

Solo vengo para decir que aun no he empezado, pero he echado un ojo al enunciado y mola mil.

JuAn4k4

Si la fase 2 es como llegar a X instrucción, solo hay que mirar los jump relativos no? No he visto el enunciado de la fase 2. ¿Que dice?

eZpit

Yo he tirado de fuerza bruta también probando las permutaciones. Lo de retroceder e ir alternando es rollo laberinto/branches. Te ahorraría repetir multiples veces operaciones por debajo del fork, pero vamos tampoco veo muchísimo beneficio.

Aviso: Si es como el año pasado, prepararos para expandir y reusar el programita con más intrucciones en futuros ejercicios. Yo para la segunda parte he aprovechado para estructurar un poco. También quiero mantener todo el código estable, así que he añadido unos tests para todos los ejercicios hasta el momento.

Day 8 (Rust): Instrucciones, parseo y el programa en si
Pt 1
Pt 2
r2d2rigo

Pues ya estaria, en el primer intento de la segunda parte he pensado que quiza la instruccion mala era la primera que te hacia volver a ejecutar una instruccion anterior pero no es asi. Al final he optado por fuerza bruta como los demas.

Fyn4r

Listo, fuerza bruta ftw xD

Dejo mi parte 2 por aquí aunque es ciertamente cutre:

Handheld por si tengo que aprovechar el cacharro
Part 2
Saiko9

joder veo q estáis todos usando clases y cosas para el 8, que bien.

Yo todavía voy por el 7, espero tener tiempo libre en el curro (irónico) jajajaja.

R

Día 8. Si con Python. De momento no he creado la clase para ejecutar las instrucciones. Por cierto, fuerza bruta también, no veo otra forma.

parte 1

spoiler

parte 2

spoiler

----
edit : parte 2 optimizada con recursividad

spoiler

Actualizo el código de la parte1 y parte2 (este último con la solución iterativa y recursiva).

MaSoBa

Yo también he tirado por fuerza bruta. No se me ha ocurrido otra forma.

Parte 1
Parte2
B

He encontrado una manera de hacerlo en O(N) usando programacion dinamica y backpointing, codigo y explicacion en spoiler. El codigo esta super sucio porque de sobra he tenido con que me funcionara.

spoiler

Os dejo el link en github por si parece demasiado ilegible en spoiler y code
https://github.com/srgrr/aoc20202/blob/main/8/main_dp.py

spoiler

Para hacernos una idea, un input de 16517 lineas tarda 0.75s con la implementación recursiva anterior, y 0.08s con la de programación dinámica.

1 2 respuestas
QuitCat

#592 No he entendido nada

Yo he tirado por fuerza bruta porque tenía poco tiempo hoy, pero esta claro que tiene haber métodos mucho mas óptimos, que es al final lo que marcará la diferencia entre los que nos quedaremos en el día 9 y los que llegarán al día 20

1 respuesta
eZpit

#592 Me has picado y he probado también a bajar el tiempo, aunque tampoco he entendido del todo tu explicación xD

Por intentar explicar la mía, lo que hago es iterar normalmente pero cada vez que llego a una instrucción nop/jmp, primero hago el swap y ejecuto el resto de instrucciones a ver si funciona. Si falla sigo con la instrucción original hasta el siguiente nop/jmp y así hasta encontrar el swap que funciona.
Lo único que cambia, respecto a mi implementación original, es que no repito las primeras instrucciones en cada intento. Como ya asumía, no hay mucho performance win, pero aun así le he sacado un 5x (de 2ms -> 0,4ms)

test tests::bench_day8_pt2      ... bench:   2,086,742 ns/iter (+/- 110,221)
test tests::bench_day8_pt2_fast ... bench:     393,516 ns/iter (+/- 21,826)
1 respuesta
B

#593 #594 Ya, la verdad es que me explico un poco como el culo.

Vuelvo a intentar explicarlo

Lo de dynamic programming es esto

https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence

Es decir, si tu tienes una funcion f(x) que se calcula recursivamente con términos anteriores o posteriores a x lo que puedes hacer es guardar en alguna estructura de datos los valores que ya hayas calculado para f(x) y devolverlos inmediatamente en lugar de emplear la recurrencia.

O sea, si f son los números de Fibonacci entonces f(13) = f(12) + f(11), pero si ya sabemos que f(13) = 144 podríamos expresar f(14) = 144 + f(12) en lugar de f(14) = f(13) + f(12), ahorrándonos un cojón de cálculos. Y si los calculamos crecientemente resulta que eliminamos la recursividad al 100%.

Pues en mi planteamiento f(x) es una función con dos variables

f(i, ac) = 1 si puedo llegar a la última instrucción del programa partiendo de la iésima instrucción, 0 en caso contrario. ac es un número que puede valer 0 o 1 y nos indica si ya hemos cambiado alguna instrucción o no

Entonces, f(i, ac) = max(f(siguiente_i, ac), f(siguiente_i_si_huberamos_modificado_la_instruccion, 1) si ac vale 0 si no 0)

Y usamos la misma idea para reutilizar resultados ya calculados.

f(0, 0) significa entonces "conseguiré llegar a la última instrucción estando ahora en la primera y sin haber cambiado ninguna?", que es de hecho lo que corresponde calcular.

Entonces, el primer f(i, 0) que vale 1 porque f(siguiente_i_si_huberamos_modificado_la_instruccion, 1) vale 1 es justamente la instrucción que hemos modificado en el programa. Sabiendo esa información podemos ejecutar el programa normal, cambiando la instrucción que toca, y calcular el acumulador en otra pasada.

A efectos prácticos estamos iterando sobre una matriz de Nx2 y dedicando un tiempo constante al cada celda de la matriz, por lo que este algoritmo resuelve el problema en tres pasadas al código en lugar de un número cuadrático de ellas.

1 1 respuesta
Taiden

Hasta el día 8 todos hechos menos la segunda parte del 7 que se me está atascando. Mañana le daré otro intento.

Traber

#595 Venga dadle el mod ya a este tio y acabemos esta tortura

1 1 respuesta
B

#597 aunque ganara no querria el mod, me come mucho tiempo leer mv como para encima moderarla, me despiden de mi trabajo jajaja

1 respuesta
Fyn4r

#598 para uno en el foro que tiene toque...

1
JuAn4k4

Edit: Listo, he me tenido que pegar con Rust para modificar el programa pero bueno ya está.

Para la fase 2 tengo algo similar a @sergioRG yo creo, aunque no tengo una matriz sino una array simple con el que luego busco qué linea cambiar:

https://github.com/juancarrey/aoc-2020/blob/main/day_8/src/main.rs

spoiler

Explicación (Es más simple de lo que parece):

Por cada instrucción, ejecutas el programa desde ahi, viendo si acaba o no acaba en la última linea. LOC[ i ] = (true/false)
Buscas de entre todas las instrucciones aquella que cumple:

  • No es la última linea
  • Se puede llegar a ella sin cambiar nada (covered_lines al ejecutar el programa sin loops la contiene)
  • No acaba desde esa linea. (LOC[ i ] = false)
  • Si acaba desde la siguiente linea al hacer swap: nop -> LOC[i+arg] = true. jmp -> LOC[i+1] = true

Una vez tienes la linea en discordia, haces el swap en el programa y lo ejecutas.

1 respuesta