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

B

Si hoy os quedais un poco pillados os recomiendo que leais este articulo de la wikipedia, mi solucion es parecida a lo que dicen aqui, pero adaptandolo un poco al problema

https://en.wikipedia.org/wiki/CYK_algorithm

Ambas partes
1 respuesta
QuitCat
spoiler
JonaN

Tremendo quilombo he montado para el de hoy xd.

Día 19 part 1
Part 2
QuitCat
spoiler
R

Pues hoy solo tengo la parte 1. Con regex por cierto. La parte 2 no la consigo con regex, he intentado hacerlo recursivo, pero se ve que evaluar una gramática no es tan sencillo... Debería mirar el enlace de #841

1 respuesta
ciza

Toca ponerse al día hoy

B

#845 La idea en general es que si tienes una regla del tipo

P -> A B

cualquier string generable con esa regla cumple que tiene un prefijo generado por A, y el sufijo sobrante estara generado por B

con reglas tipo

P -> A B C

pasa lo mismo, pero partiendo el string en 3

Entonces, para un string s de 4 caracteres "abba" y una regla P -> A B tienes que s ha sido generado de alguna de las siguientes maneras

P -> A[a] B[bba]
P -> A[ab] B[ba]
P -> A[abb] [a]

al no haber forma de generar strings vacios con las reglas que te dan en el input estos casos son suficientes.

Si te recorres el grafo de estados donde cada nodo lo defines con una tupla (p, l, r) donde

  • p es la regla actual
  • l es el indice donde empieza el substring que estas tratando
  • r es el indice donde acaba dicho substring

tienes que

  • si p es un terminal entonces solo tiene sentido estar si l == r (tenemos un string de un caracter) y s[l] es justo el terminal de la regla en cuestion
  • si no lo es, p genera s si hay algun match, esto lo podemos saber recursivamente como te he puesto arriba

con esta implementacion si te fijas es irrelevante que haya bucles, porque aunque vuelvas a la misma regla recursivamente volveras con un string mas corto, por lo que realmente estaras en dos estados distintos. Al estar acortando el string cada vez mas tienes garantia de que el proceso termina.

Tambien merece la pena destacar que si llegas a un mismo nodo (p, l, r) dos veces el recorrido que realizarás desde este será igual, por lo que si te guardas el resultado de ese nodo y lo devuelves inmediatamente puedes ahorrarte cálculos redundantes.

El algoritmo que te he pasado justamente implementa esto, aunque ese algoritmo asume que las gramaticas estan retocadas de tal manera que todas las reglas son o bien terminales o dos subreglas consecutivas. Aqui tienes alguna excepcion (de una subregla o tres) ademas de los ors, pero la idea sigue funcionando con minimos cambios.

1 1 respuesta
QuitCat
spoiler
B

Un poco toston el de hoy, pero bueno, cosas peores se han visto

B

Parte 1 y parte 2, espero que dios sepa perdonarme por el aborto supremo de codigo que ha quedado. Lo pongo con link a git porque en code y spoiler es ilegible. Me tarda su buen minutaco largo con el input tocho.

https://github.com/srgrr/aoc20202/blob/main/20/main.py

Hay muchisimas cosas optimizables, pero me da mucha pereza hacerlo y no creo que ganara nada, la verdad.

1 respuesta
ciza

#850 mi codigo de este dia da aun mas vergüenza

spoiler
1 respuesta
eZpit

Ayer la primera parte la hice generando todos los strings validos a partir de las reglas, ya que dicen que no hay loops.
Obviamente al meter el loop en la segunda parte me jodieron la marrana y me dio todo el palo seguir ayer xD

Hoy lo he retomado y al final estos casos en los que la pt2 te obliga a cambiar la pt1 drásticamente dan pereza, pero son también de los más interesantes y gratificantes ya que normalmente la pt2 te obliga a ir a por la solución correcta/eficiente. Con la nueva implementación de hoy la pt1 es 100x más rápida.

B

#851 para ser honestos es un tipo de problema que el esfuerzo que implica hacerlo elegante hace que sea muy poco rentable ponerse a ello

JonaN

Yo la parte 2 de hoy la llevaba al 60-70% pero me estaba consumiendo el día, supongo que la forma en que lo he planteado me ha lastrado. Así se va a quedar.

BeheritSp

Bueno me ha salido el de hoy después de casi todo el día :D. Aún tengo pendiente el Dia19 parte 2 que no me acaba de salir.

Los próximos dias va a estar chungo porque no voy a poder dedicarle tanto tiempo.

Sobre mi solución day20
Main
Funciones (muchotexto.png)
B

He hecho un video explicando como buenamente puedo el dia 19, del 5:13 en adelante explico el algoritmo en si, mas atras explico lo que es una gramatica. De nuevo, lo hago improvisado asi que imagino que es muy inconexo, perdon y gracias por vuestra paciencia

B

Dia 21, muchisimo mas facil que ayer, no es nada uniforme la dificultad

spoiler
BeheritSp

Si, se nota que los findes ponen los dificiles. Hoy he usado los defaultdicts que os vi usar en un día anterior.

spoiler
NeV3rKilL

Ole vosotros. Mucha gente aún dándole ahí. Chapó :sunglasses:

Parece que @sergioRG quiere ese mod bárbaro.

1 respuesta
JonaN
Día 21
B

#859 La verdad es que no, yo con algun CT tipo tryhard o alguna chorrada me conformo, pero ni de broma me pongo a moderar MV, me consumiría vivo jajaja

1
Unrack

Yo no sé ni dónde lo deje, voy a intentar retomarlo y terminar a tiempo.

S

El de hoy a sido sencillito, pero para la parte 2 leer bien las reglas del

spoiler

yo he estado atascado ahi un buen rato solo por asumir lo que hacia en base al nombre :sweat:

BeheritSp

Dia 22 ready. Al principio pensaba que se me estaba quedando colgado en la parte 2 infinitamente, pero simplemente era que es un poco lento xD

Main Day22
Funciones Day22

A todo esto, anoche conseguí acabar la parte 2 del día 19, aquí esta mi código final.

Mi problema era que:

spoiler
Main Day19
Funciones Day19
1 respuesta
JonaN

Pues mi código imita el ejemplo ronda a ronda con varias partidas nesteadas, pero con mi input el resultado es incorrecto. Lo gracioso es que he probado el código de #864, y me da otro número pero también es incorrecto xD. Habré tenido mala suerte con el input.

Joder, POR FIN. Tenía un if completamente innecesario que además estaba jodiendo el resultado xd.

Día 22 part 2
1 respuesta
BeheritSp

#865 Dices que con mi codigo no te da el número correcto? He probado a hacer copypaste de los spoilers y mi codigo me da:

spoiler

EDIT: igual te refieres a que has intentado copiar solo las funciones y que con tu main no funcionaba bien?

1 respuesta
JonaN

#866 No no, he copiado y pegado tu código y funciones y me daba un número que no era xD pero no te rayes, igual era cosa mía de tener alguna variable guardada o vete a saber. Ya lo he solucionado en mi código así que no voy a darle más vueltas :p

1
B

Dejo mi dia 22, el enunciado costaba un poco de entender

spoiler
eZpit

Por fin día 20 listo, vaya escalada la pt 2. Ayer todo el día mosca por no haberlo hecho xD

Para joder más la marrana, copie & pegue el enunciado sin estar en "monospaced" y el IDE me había trimmeado espacios del monstruo y estaba buscando otra cosa :___D

Edit: Done 22 también :>

QuitCat

Algo no estoy haciendo bien en la segunda parte, y creo que es al encontrar una ronda igual a una que ya se ha jugado, porque el ejemplo (que no tiene este caso) se resuelve bien.
¿Una vez encuentra una ronda idéntica a una ya jugada (diccionario a nivel general, no a nivel de subpartida) gana el jugador 1 toda la partida o solo la subpartida?¿Que cartas se cuentan para la puntuación en ese caso?

2 respuestas