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

r2d2rigo

Pues no tengo ni puta idea de como hacer la parte 2 y me esta entrando una pereza...

B

Otra forma que se me ha ocurrido ahora de hacer la parte 2

spoiler

La idea viene a ser esto, pero con enteros para contar en lugar de probabilidades

https://en.wikipedia.org/wiki/Stochastic_matrix#Example:_the_cat_and_mouse

O sea, M[ i ][ j ] vale 1 si podemos ir desde el iesimo numero hasta el j-esimo. O sea, si nums[ j ] - nums[ i ] <= 3. Multiplicar M por si misma es calcular

M2 [ i ][ j ] = sum k M[ i ][ k ] * M[ k ][ j ]

es decir, estamos uniendo los diferentes caminos que van de i a un punto intermedio k, y de este punto intermedio a j. En otras palabras M2 [ i ][ j ] tiene el numero de maneras que existen para ir de i a j en exactamente dos pasos. Como M2 es una matriz cualquiera puedes repetir este proceso para cualquier numero de pasos que funcionara igual.

Te quedas con la suma de todos los Mk [ 0 ][ n - 1] (desde el principio hasta el final) que veas para todas las longitudes posibles y a tomar por culo.

Ranthas

#655 Tenías razón y estaba ofuscado. He conseguido sacarlo con mi solución. Gracias macho.

1 respuesta
B

#663 Creo que es la que más me ha gustado la tuya con diferencia. Además que primeró leí el post en el que ponías 7X * 4Y * 2Z y no sabía de dónde venía esa magia negra jajaja

1 respuesta
r2d2rigo

Ha costado, joder. Os cuento mi proceso:

spoiler
Ranthas

#664 Pues me alegro, ahora subo el código a GitHub para que ya no te guste tanto la implementación jajajaja

bornex

Buah el de hoy no tengo cojones de enterarme de que es lo que hay que hacer en la parte 1, ¿alguien sabe explicarlo pa moguers?

2 respuestas
QuitCat

#667 Tienes X adaptadores de voltajes (array de números), todos de diferente voltaje (números no repetidos) y que entre un adaptador y el siguiente puede haber una diferencia entre 1, 2 o 3 máximo. Te pide que cojas "cuantas diferencias" hay de tamaño 1 y cuantas de tamaño 3 y multipliques esos valores:
Ejemplo: [1,7,4,2]
El punto de partida siempre es 0, y el punto final siempre es el mayor voltaje + 3
[0, 1, 2, 4, 7, 10] -> 2 saltos de 1, 2 saltos de 3 -> Resultado: 4 (2x2)

1 1 respuesta
r2d2rigo

#667

spoiler
1 1 respuesta
bornex

#668 #669 Vale, ahora es cuando! gracias

EDIT: Lista la parte 1, voy a ver que tal la parte 2

EDIT2: Al final no he tenido cojones ha sacar la parte dos sin mirar a vosotros las soluciones, joder... que puta mierda

eZpit

Para la segunda parte, pienso que la solución optima es contar desde atrás. He hecho lo siguiente:

  • Inicializo un vector del tamaño del input (+ el 0 inicial).
  • Calculo, empezando por el final, el número de permutaciones desde cada posición hasta el final y las voy guardando en el vector.
  • La última posición tiene solo 1 permutación.
  • La posición anterior también solo una.
  • A medida que me alejo del final, busco los posibles "saltos" desde cada posición a la siguientes. El numero de permutaciones es la suma de permutaciones de todos los posibles saltos (que tengo guardadas en el vector).
Day 10 pt 2 (Rust)
1
Traber

Nada, doy por perdida la segunda parte, las matemáticas no son lo mio xd.

R

Yo hoy la segunda parte tampoco la he sacado. Vamos tengo solución recursiva, pero obvio no termina en tiempo razonable con la entrada real. Con los ejemplos parece que funciona.

La primera bien, O(N) con counting sort.

B

Qué puto tostón el de hoy...

spoiler
2 respuestas
ciza

#674 yo ahora lo empiezo pero no das ánimos xD

1 respuesta
Traber

#674 Fijate que a mi el de hoy me ha molado bastante más que el de ayer, al menos está mejor explicado y se entiende mejor, pero plantea problemáticas interesantes:

  • Comprobación con elementos adyacentes.
  • Almacenamiento de estados complejos y comprobación de los mismos, para en cada iteración saber si el conjunto de estados de las butacas ha cambiado.

Eso si, la primera parte no la he hecho para nada eficiente, sus putos muertos lo que me está tardando en computar todo JAJAJAJAJAJAJA.

B

#675 Es bastante sencillo, pero estas cosas de grids y vecinos siempre me han dado pereza, la verdad.

Traber

25 minutos aprox. para computar la primera parte, dios, me siento horrible por dentro XD

2 respuestas
B

#678 Lol, cómo lo has hecho?

1 respuesta
Ranthas

He empezado a mirarlo y ya ha caído el puto problema de adyacencia en matrices

A ver si esta tarde puedo ponerme, ahora toca sesión interminable de reuniones

Traber

#679 Mal, seguro xd:

NSFW

Explico el uso de JSON aquí:

En C# los diccionarios se copian por referencia, por lo que para clonarlos necesitamos una de las 3 cosas:

  • Que implemente ICloneable (nope).
  • Implementar nuestra propia función de clonado de diccionarios (mucho curro).
  • Que nos paguen para hacer esto (y no pagan, así que que le jodan xd).

Lo paso a JSON, y luego de JSON a un nuevo Dictionary<>, no hay referencia alguna al objeto anterior.

También, para comparar los layouts de uno a otro, es mucho más rápido (de implementar) comparar el resultado de serializar el objeto a string que comparar todos los elementos hasta encontrar una diferencia, así que hago eso, comparo los strings y a tomar por culo xd.

Edito: Otra puta parte 2 que se explica como el putísimo ojete, qué asco. De hecho, en la primera parte ni siquiera explicaba si las comparaciones de las butacas de las filas se hacían con el elemento anterior o teniendo en cuenta las mutaciones en cada iteración, me toca los huevos.

Edito 2: Acabo de entenderlo, pero vaya, me cago en zeus xd.

2 respuestas
MartiONE

Que pereza el de hoy, a ver si despues de currar le doy un chance

B

#681 No entiendo mucho C# y tampoco se muy bien el workflow de tu codigo, porque veo metodos pero no se en que orden ni como se llaman, pero diria que hemos implementado lo mismo, asi que yo creo que te tarda tanto por el overhead adicional de todo eso que explicas.

edit: vale, ahora entiendo tu codigo, no habia leido el main. Pues la implementacion viene a ser la misma, yo creo que es por el overhead de C#, o porque tienes algun bug y recalculas cosas.

ciza

El mio de hoy da bastante asco pero al menos ejecuta medio rápido

spoiler

Edit. He visto que no tiene error

Estaba esperando a acabarlo para ver otras soluciones a ver si eran mas elegantes pero no sé si hay manera mejor

1 respuesta
QuitCat

#681

NSFW
B

#684 Hay una manera de hacer la segunda parte más rápida, pero es un coñazo y por cómo era el input no merecía la pena

spoiler
JonaN
Día 11 parte 1
Parte 2 NMS

Al menos, aunque el código sea feo, ejecutan en 4-5 secs xd.

1 respuesta
ciza

#687 NMS :joy:

Se nota que haces cosas con números

1 respuesta
Fyn4r

Joder macho, que forma de tirar el tiempo en la primera parte porque tenía una comprobación de adyacentes mal, pero como el puto python te deja indexar con números negativos pues xD

pineda
spoiler