Autor Tema: Advent of Code Problema 10.

0 Usuarios y 1 Visitante están viendo este tema.

10 Diciembre, 2021, 04:54 pm
Leído 520 veces

C. Enrique B.

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 566
  • País: es
  • Karma: +0/-0
    • Mi página en WikiPedia.
.
https://adventofcode.com/2021/day/10

Día 10: Puntuación de sintaxis

Le pides al submarino que determine la mejor ruta para salir de la cueva de aguas profundas, pero solo responde:

Error de sintaxis en el subsistema de navegación en línea: todos

¡¿Todos ellos?! El daño es peor de lo que pensaba. Abra una copia del subsistema de navegación (your puzzle input).

--- --- La sintaxis del subsistema de navegación se compone de varias líneas que contienen fragmentos. Hay uno o más fragmentos en cada línea y los fragmentos contienen cero o más fragmentos. Los fragmentos adyacentes no están separados por ningún delimitador; si un fragmento se detiene, el siguiente fragmento (si lo hay) puede comenzar inmediatamente. Cada fragmento debe abrirse y cerrarse con uno de los cuatro pares de caracteres coincidentes legales:

    Si un fragmento se abre con (, debe cerrarse con).
    Si un fragmento se abre con [, se debe cerrar con].
    Si un fragmento se abre con {, debe cerrarse con}.
    Si un fragmento se abre con <, debe cerrarse con>.

Entonces, () es un fragmento legal que no contiene otros fragmentos, como []. Los fragmentos más complejos pero válidos incluyen ([]), {() () ()}, <([{}])>, [<> ({}) {} [([]) <>]] e incluso ( ((((((((())))))))).

--- --- Algunas líneas están incompletas, pero otras están dañadas. Primero busque y descarte las líneas dañadas.

Una línea corrupta es aquella en la que un fragmento se cierra con el carácter incorrecto, es decir, donde los caracteres con los que se abre y se cierra no forman uno de los cuatro pares legales enumerados anteriormente.

Entre los ejemplos de fragmentos dañados se incluyen (], {() () ()>, (((()))} y <([]) {()} [{}]). Dicho fragmento puede aparecer en cualquier lugar dentro de una línea, y su presencia hace que toda la línea se considere corrupta.

--- --- Por ejemplo, considere el siguiente subsistema de navegación:

[({(<(()) []> [[{[] {<() <>>
[(() [<>])] ({[<{<< [] >> (
{([(<{} [<> []}> {[] {[(<()>
(((({<>} <{<{<>} {[] {[] {}
[[<[([])) <([[{} [[()]]]
[{[{({}] {}} ([{[{{{}} ([]
{<[[]]>} <{[{[{[] {() [[[]]]
[<(<(<(<{}))> <([] ([] ()
<{([([[(<> ()) {}]> (<< {{
<{([{{}} [<[[[<> {}]]]> []]

--- --- Algunas de las líneas no están dañadas, simplemente están incompletas; puede ignorar estas líneas por ahora. Las cinco líneas restantes están dañadas:

    {([(<{} [<> []}> {[] {[(<()> - esperado], pero encontrado} en su lugar.
    [[<[([])) <([[{} [[()]]] - Se esperaba], pero se encontró) en su lugar.
    [{[{({}] {}} ([{[{{{}} ([] - esperado), pero encontrado] en su lugar.
    [<(<(<(<{}))> <([] ([] () - Se esperaba>, pero se encontró) en su lugar.
    <{([([[(<> ()) {}]> (<< {{- Esperado], pero encontrado> en su lugar).

--- --- Detente en el primer carácter de cierre incorrecto en cada línea dañada.

--- --- ¿Sabía que los verificadores de sintaxis en realidad tienen concursos para ver quién puede obtener la puntuación más alta por errores de sintaxis en un archivo? ¡Es cierto! Para calcular la puntuación de error de sintaxis de una línea, tome el primer carácter ilegal de la línea y búsquelo en la siguiente tabla:

    ) ... 3 puntos.
    ] ... 57 puntos.
    } ... 1197 puntos.
    > ... 25137 puntos.

En el ejemplo anterior, un ilegal ) se encontró dos veces (2 * 3 = 6 puntos), un ilegal ] se encontró una vez (57 puntos), un ilegal } se encontró una vez (1197 puntos) y un ilegal > se encontró una vez ( 25137 puntos). Entonces, la puntuación total de error de sintaxis para este archivo es 6 + 57 + 1197 + 25137 = 26397 puntos.

--- --- Busque el primer carácter ilegal en cada línea dañada en el subsistema de navegación. ¿Cuál es la puntuación total de errores de sintaxis para esos errores?

--- --- Para jugar, identifícate a través de uno de estos servicios:

[GitHub] [Google] [Twitter] [Reddit]
.

---------------------
Moderación. Se han movido aquí los mensajes relativos al problema 8 del advent of code 2021. Aquí el hilo original.
-- FALTAN LAS MUJERES en muchos ámbitos sociales. Yo no me siento perteneciente al bando masculino; soy del bando de las personas. Chicas, manifestáos; no concibo charlar sobre un tema si no estáis vosotras: es impropio, casi absurdo.

10 Diciembre, 2021, 05:11 pm
Respuesta #1

martiniano

  • Moderador Global
  • Mensajes: 1,964
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

El problema 10 es un problema típico cuando se estudian autómatas a pila. Una manera muy eficaz y rápida de resolverlo es mediante una pila de caracteres.

Se va recorriendo la cadena de entrada carácter a carácter. Si el carácter leído es de apertura, es decir, '(', '{' o '<' se almacena en la pila. Si es de cierre se comprueba que en la cima de la pila esté el carácter de apertura correspondiente. Si es así se desempila y si no la cadena no es válida. Cuando la cadena de entrada se ha leído entera la pila debe estar vacía. Si no, la cadena no es válida.

Un saludo.

10 Diciembre, 2021, 05:25 pm
Respuesta #2

C. Enrique B.

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 566
  • País: es
  • Karma: +0/-0
    • Mi página en WikiPedia.
... El problema 10 es un problema típico cuando se estudian autómatas a pila. Una manera muy eficaz y rápida de resolverlo es mediante una pila de caracteres. ...

Cierto, incluso sirve ese ejemplo "no simétrico" que hay por ahí (el que finaliza con dos corchetes, al comienzo del enunciado).

Sería una pila o stack LIFO, ¿no?, L.ast I.n F.irst O.ut.
____________________


P.D.: Aprovecho para decir que el bestia Magnus Carlsen acaba de revalidar el título de Campeón Mundial de Ajedrez, en lo que ha sido un match algo desilusionante (dentro de lo que es la enorme profundidad y belleza que cada partida de Ajedrez posibilita).
.
-- FALTAN LAS MUJERES en muchos ámbitos sociales. Yo no me siento perteneciente al bando masculino; soy del bando de las personas. Chicas, manifestáos; no concibo charlar sobre un tema si no estáis vosotras: es impropio, casi absurdo.

10 Diciembre, 2021, 05:39 pm
Respuesta #3

martiniano

  • Moderador Global
  • Mensajes: 1,964
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Sería una pila o stack LIFO, ¿no?, L.ast I.n F.irst O.ut.

Sí.

P.D.: Aprovecho para decir que el bestia Magnus Carlsen acaba de revalidar el título de Campeón Mundial de Ajedrez, en lo que ha sido un match algo desilusionante (dentro de lo que es la enorme profundidad y belleza que cada partida de Ajedrez posibilita).
.

Entonces ya ha acabado. Yo también he estado siguiendo la confrontación. Esta noche me veré el resumen de esta última partida. Buen plan.  ;)

Un saludo.

10 Diciembre, 2021, 05:40 pm
Respuesta #4

geómetracat

  • Moderador Global
  • Mensajes: 3,189
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

El problema 10 es un problema típico cuando se estudian autómatas a pila. Una manera muy eficaz y rápida de resolverlo es mediante una pila de caracteres.

Se va recorriendo la cadena de entrada carácter a carácter. Si el carácter leído es de apertura, es decir, '(', '{' o '<' se almacena en la pila. Si es de cierre se comprueba que en la cima de la pila esté el carácter de apertura correspondiente. Si es así se desempila y si no la cadena no es válida. Cuando la cadena de entrada se ha leído entera la pila debe estar vacía. Si no, la cadena no es válida.

Un saludo.

Sí, es un problema muy típico y justo una pila es lo que he implementado yo. Si a alguien le interesa luego cuelgo el código (no estoy en mi ordenador ahora), pero creo que no tiene demasiado interés.

Sería una pila o stack LIFO, ¿no?, L.ast I.n F.irst O.ut.

Que alguien me corrija si me equivoco, pero creo que una pila (stack) en informática es siempre LIFO por definición.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

10 Diciembre, 2021, 05:54 pm
Respuesta #5

C. Enrique B.

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 566
  • País: es
  • Karma: +0/-0
    • Mi página en WikiPedia.
.
Ya sabéis que yo no soy maestro de nada, así que fallo bastante en las explicaciones "precisas", pero no comprendo, geómetracat: Quizá te refieres específicamente al término PILA, y quieres decir que para los otros tipos de listas hay otros términos adecuados ... porque está claro que "formas de evolución de listas de elementos" hay infinitas.
.
-- FALTAN LAS MUJERES en muchos ámbitos sociales. Yo no me siento perteneciente al bando masculino; soy del bando de las personas. Chicas, manifestáos; no concibo charlar sobre un tema si no estáis vosotras: es impropio, casi absurdo.

10 Diciembre, 2021, 06:13 pm
Respuesta #6

martiniano

  • Moderador Global
  • Mensajes: 1,964
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Creo que está habiendo un error comunicativo.

Geómetracat, creo César preguntaba precisamente si pila y stack Lifo eran lo mismo. Por eso le dije que sí.

César, creo que geómetracat ha interpretado tu pregunta como que querías saber si había que utilizar una pila o había que utilizar un stack lifo, cuando en realidad son lo mismo.

Un saludo.

10 Diciembre, 2021, 06:18 pm
Respuesta #7

C. Enrique B.

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 566
  • País: es
  • Karma: +0/-0
    • Mi página en WikiPedia.
.
No. El error debe de ser mío, por la falta de precisión que mencioné. Revisaré el significado de Pila, Stack y términos adyacentes.
.
-- FALTAN LAS MUJERES en muchos ámbitos sociales. Yo no me siento perteneciente al bando masculino; soy del bando de las personas. Chicas, manifestáos; no concibo charlar sobre un tema si no estáis vosotras: es impropio, casi absurdo.

10 Diciembre, 2021, 07:10 pm
Respuesta #8

geómetracat

  • Moderador Global
  • Mensajes: 3,189
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
.
Ya sabéis que yo no soy maestro de nada, así que fallo bastante en las explicaciones "precisas", pero no comprendo, geómetracat: Quizá te refieres específicamente al término PILA, y quieres decir que para los otros tipos de listas hay otros términos adecuados ... porque está claro que "formas de evolución de listas de elementos" hay infinitas.
.

Sí, viene a ser esto. Yo entendí (quizás mal, ya me lo aclararás) que al decir "pila o stack LIFO" es porque creías que también había "pila o stack FIFO" por ejemplo. Y lo que decía era que si dices pila (en inglés stack)  es una estructura LIFO por definición, de manera que "pila LIFO" es redundante. Por ejemplo, una estructura FIFO se llama cola (queue en inglés).
La ecuación más bonita de las matemáticas: \( d^2=0 \)