Comprobador de "conveniente palíndromo"

39

Si alguna vez has intentado escribir código palindrómico antes, sabrías cuántos corchetes tienden a interponerse en tu camino. ()()no es un palíndromo, a pesar de que se ve un poco como debería ser, al tiempo ())(, y ()(son a la vez capicúa y ambos mirando muy tonta. ¿No sería conveniente si fuera al revés?

Una cadena es convenientemente palindrómica si es igual a la cadena derivada cuando su reverso tiene todos sus paréntesis ( ()), corchetes ( []) y llaves ( {}) invertidos. Ningún otro personaje es especial y requiere voltear. (a <>veces se combinan, pero a menudo no, por lo que se dejan fuera).

Su tarea es escribir, en su idioma, un programa (tomando entradas en STDIN) o una función (tomando un argumento de cadena única) que (a) da un valor verdadero consistente * cuando su argumento es convenientemente palindrómico y un falso falso diferente y consistente valor de otro modo, y (b) es en sí convenientemente palindrómica.

Por ejemplo, las siguientes entradas son convenientemente palindrómicas:

racecar
(a)(bb)(a)
void main(int argc, *char[] argv) {} (vgra []rahc* ,cgra tni)niam diov

Y los siguientes no son:

non-palindrome
A nut for a jar of tuna?
(old [style] parens) )snerap ]elyts[ dlo(
ingirumimusnocte)etconsumimurigni

No puede confiar en ningún estado externo (nombre de archivo específico, estructura de directorio, otra entrada del usuario, acceso web, etc.), excepto las banderas de intérprete / compilador.

Además, no puede usar "el truco de comentarios" en el que comenta o deja sin usar algún fragmento de código aprovechando las funciones de comentarios de su idioma. Por ejemplo, todo lo siguiente no está permitido, porque contienen partes no funcionales que pueden eliminarse o destruirse de manera segura (a costa de perder convenientemente la palindrómica):

{some code} // {edoc emos}
{some code} NB.BN {edoc emos}
"n\" ;{edoc emos} ;"; {some code}; "\n"

Obviamente, esto podría no cubrir cada uno de estos casos, pero el espíritu del desafío aquí es no usar comentarios y código no analizado ** para lograr palindrominess, en lugar de utilizar los paréntesis y paréntesis corregidos. Te estoy mirando, LISP, Brainfuck.

Este es un , por lo que gana el código más corto, pero todas las longitudes de código son bienvenidas.

* Por valores consistentes de verdadero y falso, quiero decir que puede devolver uno de un par de valores, como 1verdadero y 0falso, o Falseverdadero y "no"falso, siempre que estos valores sean diferentes entre sí y no cambiar de ejecución a ejecución de su programa. Usa lo que te salve personajes.

** No debe confundirse con no ejecutado : el código que es válido y puede hacer cosas raras pero nunca llamado está bien.

Algoritmo de tiburón
fuente
¿Qué pasa con cosas como if(false){some code}o variables no utilizadas? ¿Están permitidos?
pastebin.com slash 0mr8spkT
@ace Si su idioma de alguna manera analiza o verifica el código no ejecutado para determinar el tipo de acuerdo o la validez sintáctica, está bien. Si equivale a un comentario porque su idioma no comprueba el interior de ese bloque, cuando arrojaría un error de sintaxis si lo hiciera, no está bien. Creo que si puedes encontrar un uso válido para (eslaf)fi, puedes usarlo if(false).
algorithmshark
58
Me tomó demasiado tiempo entender por qué ()()no es un palíndromo
David dice que reinstalar a Monica
¿El código tiene que funcionar con entrada de varias líneas?
Ventero
@Ventero Las líneas nuevas y los retornos de carro son caracteres, y no tienen pares para cambiar, por lo que diría que cuentan como caracteres normales.
algorithmshark

Respuestas:

13

J (60)

(|.-:'())([]][{}}{'&charsub) :: (busrahc&'}{{}][[])(()':-.|)

Esta es una función que toma un argumento:

   (|.-:'())([]][{}}{'&charsub) :: (busrahc&'}{{}][[])(()':-.|) 'ingirumimusnocte)etconsumimurigni'
0
   (|.-:'())([]][{}}{'&charsub) :: (busrahc&'}{{}][[])(()':-.|) '(a)(bb)(a)'
1

Explicación:

  • f :: gejecuta la función fsobre la entrada y devuelve el resultado si vuelve sin error. Si ffalla, se ejecuta en su glugar.

  • El faquí es (|.-:'())([]][{}}{'&charsub), que hace el trabajo real:

    • |.: marcha atrás
    • -:: es igual a
    • '())([]][{}}{'&charsub: reemplazar cada soporte con su soporte opuesto
  • La gfunción es (busrahc&'}{{}][[])(()':-.|), que no tiene sentido pero es sintácticamente válida. busrahcno está definido, pero eso no importa porque solo se resuelve cuando se ejecuta (y no se ejecutará).
marinus
fuente
Puede guardar un personaje convirtiéndolo f :: gen g@-@f. ges equivalente al gancho (-.|)debido a :que las salidas se convierten en -1 y la lista vacía para convenientemente palindrómica y no, respectivamente.
algoritmshark
34

GolfScript, 107 91

.4:ab-1:ba=;1
%ba%{...fi@@=
c43.=;)('"([{
}])"'~?~'"([{
}])"')(;=.34c
=@@if...}%ab%
1;=ab:1-ba:4.

Las nuevas líneas son artísticas. fi, c43y cson noops, pero se ejecuta todo el código.

Imprime -3-1-1para palíndromos convenientes, de lo -4-1-1contrario. Pruébalo en línea!

Versión alternativa, 155 bytes.

A un costo de 64 bytes, esto se puede mejorar con:

0!*1{!}\;:);0:f;0:i;-1:ab;9:ba;
...=;1%ab%{....i@f@@fi@@=@.=@\)
+""'"([{}])"'~+?+~'"([{}])"'""+
(\@=.@=@@if@@f@i....}%ba%1;=...
;ab:9;ba:1-;i:0;f:0;(:;\{!}1*!0

Como antes, se ejecuta todo el código y cada byte afecta la salida.

Imprime 010para palíndromos convenientes, de lo -100contrario. Pruébalo en línea!

Pruebas y ejemplos.

$ base64 > palindrome.gs -d <<< LjQ6YWItMTpiYT07MSViYSV7Li4uZmlAQD1jNDMuPTspKCciKFt7fV0pIid+P34nIihbe31dKSInKSg7PS4zNGM9QEBpZi4uLn0lYWIlMTs9YWI6MS1iYTo0Lg==
$ wc -c palindrome.gs
91 palindrome.gs
$ rev palindrome.gs | tr '([{}])' ')]}{[(' | diff - palindrome.gs
$ echo -n 'r(a[c{"e"}c]a)r' | golfscript palindrome.gs
-3-1-1
$ echo -n 'totallynotapalindrome' | golfscript palindrome.gs
-4-1-1
$
$ base64 > pal.gs -d <<< MCEqMXshfVw7Oik7MDpmOzA6aTstMTphYjs5OmJhOy4uLj07MSVhYiV7Li4uLmlAZkBAZmlAQD1ALj1AXCkrIiInIihbe31dKSInfis/K34nIihbe31dKSInIiIrKFxAPS5APUBAaWZAQGZAaS4uLi59JWJhJTE7PS4uLjthYjo5O2JhOjEtO2k6MDtmOjA7KDo7XHshfTEqITA=
$ wc -c pal.gs
155 pal.gs
$ rev pal.gs | tr '([{}])' ')]}{[(' | diff - pal.gs
$ echo -n 'r(a[c{"e"}c]a)r' | golfscript pal.gs
010
$ echo -n 'totallynotapalindrome' | golfscript pal.gs
-100
$ for i in {1..154}; do head -c $i pal.gs > tmp.gs; tail -c +$[i+2] pal.gs >> tmp.gs
> [ "$(echo -n 'r(a[c{"e"}c]a)r' | golfscript tmp.gs 2> /dev/null)" = "010" ] && echo $i
> done; rm tmp.gs
1
for i in {1..154}; do head -c $i pal.gs > tmp.gs; tail -c +$[i+2] pal.gs >> tmp.gs
>  [ "$(echo -n '42' | golfscript tmp.gs 2> /dev/null)" = "-100" ] && echo $i
> done | grep '^1$'; rm tmp.gs

Cómo funciona

.             # Duplicate the input string.
4:ab-1:ba     # Save 4 in “ab” and -1 in “ba”.
=;            # Compare 4 to -1 and discard the result.
1%            # Save every element from the input string in a new string.
ab%           # Reverse the input string.
{             # For each character in the input string:
  ...         # Duplicate the character thrice.
  fi          # Variable “fi” is undefined; this does nothing.
  @@=         # Verify that the character is equal to itself; push 1.
  c43         # Variable “c43” is undefined; this does nothing.
  .=;         # Verify that 1 is equal to itself and discard the result.
  )(          # Increment and decrement the character.
  '"([{}])"'~ # Push that string and evaluate it. Result: '([{}])'
  ?           # Retrieve the character's position in '([{}])'. -1 means not found.
  ~           # Negate the position.. Examples: -1 -> 0    0 -> -1    2 -> -3
  '"([{}])"') # Push that string and pop its last element. Result: '"([{}])' 34
  (;          # Decrement 34 (the ASCII code of a double quote) and discard.
  =           # Retrieve the corresponding character.
  .34         # Duplicate the character and push 34.
  c           # Variable “c” is undefined; this does nothing.
  =           # If the character is a double quote, the index was -1.
  @@if        # In that case, replace the double quote with the original character.
  ...         # Duplicate the new character thrice.
}%            #
ab%           # Save every fourth element in a new string to discard dummy values.
1;            # Push 1 and discard.
=             # Push 1 if the modified string matches the original, 0 otherwise.
ab:1-         # Save 4 in “1” and subtract.
ba:4.         # Save -1 in “4” and duplicate.

0!*           # Pop and push the input string.
1{!}\;:);     # Make “)” an alias for “!”.
0:f;0:i;      # Variables.
-1:ab;9:ba;   # Moar variables.
...=;         # Duplicate the input string.
1%ab%         # Reverse the copy.
{             # For each character in the input string:
  ....        # Duplicate the character four times.
  i@          # Push 0 and rotate a string copy on top of it.
  f@@fi@@     # Push 0 and rotate 0 on top of it.
  =@          # Push 1 and rotate a string copy on top of it.
  .=@         # Push 1 and rotate 1 on top of it.
  \)+         # Negate a 1 and add. Result: 1
  ""          # Push that string.
  '"([{}])"'  # Push that string.
   ~+         # Evaluate the second string and concatenate. Result: '([{}])'
   ?          # Retrieve the characters position in '([{}])'. -1 means not found.
   +~         # Add 1 to the position and negate. Ex.: -1 -> -1 | 0 -> -2 | 1 -> -3
  '"([{}])"'  # Push that string.
  ""          # Push that string.
  +           # Concatenate. Result: '"([{}])"' 
  (\          # Pop the first double quote and swap it with the rest of the string.
  @=.         # Retrieve the corresponding character and duplicate it.
  @=          # If the character is a double quote, the index was -1.
  @@if        # In that case, replace the double quote with the original character.
  @@          # Rotate the modified character to the bottom.
  f@i....     # Push dummy values.
  }%          #
  ba%         # Save every ninth element in a new string to discard dummy values.
  1;          # Push 1 and discard.
  =           # Push 1 if the modified string matches the original, 0 otherwise.
  ...;        # Duplicate thrice and discard the last copy.
  ab:9;ba:1-; # Variables.
  i:0;f:0;    # Moar variables.
  (:;\        # Negate, override “;” and swap.
  {!}1*!0     # Negate twice and push 0.
Dennis
fuente
13

Ruby, 110

(z=gets;r=z.tr *["([{}])",")]}{[("];p *z==r.reverse;1)||(1;esrever.r==z* p;[")]}{[(","([{}])"]* rt.z=r;steg=z)

Imprime truesi la entrada es un palíndromo conveniente y falsesi no lo es. Tenga en cuenta que esta solución supone que la entrada no termina en una nueva línea, así que pruébela con echo -n:

echo -n '(a)(bb)(a)' | ruby convpal.rb
true

echo -n '(a)(bb()a(' | ruby convpal.rb
false

# note that for this to work, the file must not contain a newline
# to remove a trailing newline, pipe it through tr -d $'\n'
cat convpal.rb | ruby convpal.rb
true

Este es un puerto algo directo de mi respuesta a Palindromic Palindrome Checker (y hasta ahora no ha jugado golf). El truco principal utilizado es que la primera expresión entre paréntesis siempre regresa 1, por lo que la segunda mitad de la expresión booleana nunca se evalúa (pero se analiza).

La única dificultad para adaptar esto fue descubrir cómo agregar la llamada para z.trque su "reverso conveniente" también fuera sintácticamente válido, pero simplemente podría usar el mismo truco que ya usé put: *que en la primera mitad se analiza como operador splat (use el contenido de la matriz como parámetros de función) y como operador de multiplicación de matriz (o repitición) en la segunda mitad.

Rubí, 157 297, todo el código ejecutado

w=tsoh=gets p
o=rt=esrever=Gem
q=tsoh.tr *["([{}])",")]}{[("]
q==esrever.host=w=tsoh.reverse==q
[")]}{[(","([{}])"]* rt.host=q
meG=reverse=tr=o
p steg=host=w

Esta versión (un poco más larga) ejecuta todo el código, y todas menos dos líneas afectan la salida, que se imprime en la última línea, pero todas las líneas se analizan y ejecutan sin ningún error. Esta versión interpreta cualquier nueva línea final como parte de la entrada, así que úsela echo -npara probarla o anteponga su entrada con una nueva línea. Imprime truesi la entrada es un palíndromo conveniente, y de lo falsecontrario.

Explicación

# Read the input by calling gets(nil), which is achieved by passing the return
# value of a call to Kernel#p (which returns nil if no argument is supplied) to
# gets.
w=tsoh=gets p
# Assign the global Gem module to three variables.
# The variable names are the reversed names of methods we have to call later.
# This doesn't necessarily have to be the Gem module, any global module/variable
# (or class that allows object creation through a call to the module itself,
# e.g. Hash or GC) with a writable property would do, but Gem#host was
# the shortest one I could find. This is necessary because Ruby doesn't
# allow setting previously undefined properties through the dot syntax.
o=rt=esrever=Gem
# Replace the parentheses with the corresponding flipped one.
# sserts is the reverse of the property name we're going to use later.
q=tsoh.tr *["([{}])",")]}{[("]
# Do the convinient palindrome check and assign its result to a few variables
# and Gem's host property.
q==esrever.host=w=tsoh.reverse==q
# Here, the * is parsed as array join operator.
[")]}{[(","([{}])"]* rt.host=q
# Nothing special here.
meG=reverse=tr=o
# Print the result of the palindrome check, which was stored in w.
p steg=host=w
Ventero
fuente
9

GolfScript, 61 caracteres

OK, aquí hay una solución de referencia en GolfScript. Estoy seguro de que podría mejorarse aún más:

{.-1%{"([{}])".2$?~@[.]@+=}%=}~{=%{=+@[.]@~?$2."([{}])"}%1-.}

Como es habitual en GolfScript, este programa lee su entrada de stdin. Produce:

1{=%{=+@[.]@~?$2."([{}])"}%1-.}

si la entrada es un palíndromo conveniente, como se define en el desafío anterior, y:

0{=%{=+@[.]@~?$2."([{}])"}%1-.}

si no es.

Explicación: Este programa se basa en gran medida en la decisión de que el código no ejecutado está bien, siempre que se analice. Se compone de dos bloques de código, delimitados por llaves ( { }), que son imágenes especulares entre sí.

El primer bloque de código se ejecuta al ~seguirlo, y comprueba si la entrada es un palíndromo conveniente, generando 1si lo es y 0si no lo es. El segundo bloque de código no se ejecuta, por lo que simplemente permanece en la pila hasta que finaliza el programa y todo el contenido de la pila se encadena e imprime automáticamente por el intérprete de GolfScript.

Cabe señalar que el intérprete de GolfScript realiza muy pocas verificaciones de sintaxis en el momento del análisis (o alguna vez, para el caso); un literal de bloque de código GolfScript puede contener casi cualquier cosa, incluso si se bloquea cuando se ejecuta. Aún así, algunos errores de sintaxis, como los literales de cadena no terminados, generan un error incluso en código no ejecutado, por lo que creo que esta solución (apenas) se encuentra dentro de las reglas.

PD. Mirando el código ejecutado real, contiene algunos elementos convenientemente palindrómicos como @[.]@el literal de cadena "([{}])"e incluso el bucle %{ ... }%. Esto ofrece la sugerencia tentadora de que una solución GolfScript "intrínsecamente palindrómica", donde el programa palindrómico completo sería ejecutado y funcional, podría ser realmente posible. Como todavía no he logrado producir uno, ¡por la presente ofrezco una recompensa de +100 repeticiones a la primera persona que logra inventar una!

Ilmari Karonen
fuente
3
espera, tu código es un palíndromo en sí mismo? : O
Fabricio
Me inclino a considerar esta solución más como el "n\";X;";X;"\n"tipo de comentarios, pero le daré el beneficio de la duda. Sin embargo, en realidad estaba buscando tales soluciones "intrínsecamente palindrómicas", o al menos aquellas en las que la no ejecución de los bloques fuera un poco menos clara.
algoritmshark
Mi respuesta tiene un noop (variable indefinida) y algunas partes que no logran nada (por ejemplo, 1;). ¿Eso todavía cuenta como completamente funcional?
Dennis
@ Dennis: Sí, creo que sí. Felicidades, ciertamente es lo suficientemente impresionante. La pregunta parece ser lo suficientemente nueva como para que aún no pueda publicar la recompensa, pero la tendrás en unos días.
Ilmari Karonen
1
formato de salida leeway abuuuse :-)
John Dvorak
4

JavaScript (ES6), 245 bytes

Quería una respuesta JS que pudiera ejecutarse en el navegador, así que aquí está.

eurt=>eurt==(("",eurt))["split"||"nioj"]("")["map"||"esrever"](x=>({'{':'}','}':'{','[':']',']':'[','(':')',')':'('})[x]||x||[x]({')':'(','(':')',']':'[','[':']','}':'{','{':'}'})>=x)["reverse"||"pam"]("")["join"||"tilps"]((true,""))==true>=true

Eliminando todo el código que nunca se ejecuta, obtenemos esto:

eurt=>eurt==(("",eurt))["split"||"nioj"]("")["map"||"esrever"](x=>({'{':'}','}':'{','[':']',']':'[','(':')',')':'('})[x]||x||[x]({')':'(','(':')',']':'[','[':']','}':'{','{':'}'})>=x)["reverse"||"pam"]("")["join"||"tilps"]((true,""))==true>=true
eurt=>eurt==(("",eurt))["split"        ]("")["map"           ](x=>({'{':'}','}':'{','[':']',']':'[','(':')',')':'('})[x]||x                                                           )["reverse"       ]("")["join"         ]((true,""))==true>=true

Lo cual se puede simplificar a esto:

eurt=>eurt==eurt.split("").map(x=>({'{':'}','}':'{','[':']',']':'[','(':')',')':'('})[x]||x).reverse("").join("")
ETHproducciones
fuente
Puede guardar unos 60 bytes usando n1 / 1n en lugar de verdadero / eurt, comas en algunos lugares en lugar de ||, y jugando con el selector de paréntesis: n1=>n1==(('',n1))['nioj','split']``['esrever','map'](c=>`()[]{}`[`()[]{}`['indexOf'](c)^1]||c||[1^(c)['fOxedni']`{}[]()`]`{}[]()`>=c)['pam','reverse']``['tilps','join']((1n,''))==1n>=1n(185 bytes)
Yair Rand
3

Javascript (ES6) 288

Se ejecuta en la línea de comandos de Spidermonkey . Lee una sola línea de STDIN y las salidas trueo falsedependiendo de si la entrada es un palíndromo conveniente.

((print)((eval)('r=readline()')==([0]['map']['call'](r,x=>({'{':'}','}':'{','[':']',']':'[','(':')',')':'('})[x]||x)['reverse']()['join']('')))&&((('')['nioj']()['esrever'](x||[x]({')':'(','(':')',']':'[','[':']','}':'{','{':'}'})>=x,r)['llac']['pam'][0])==('()enildaer=r')(lave))(tnirp))

Este código es sintácticamente válido, pero todo lo que &&sigue no se ejecuta, ya que la printfunción devuelve un valor falsey.

Puede ejecutar este código en la consola de Firefox ejecutando este calce primero para emular las funciones readliney print. Edite la entrada dentro readlinesegún sea necesario:

readline = function(){ 
    return "void main(int argc, *char[] argv) {} (vgra []rahc* ,cgra tni)niam diov"; 
}, print = console.log.bind(console);

Y aquí hay un ejemplo rápido de la salida:

ejemplo de línea de comando

nderscore
fuente
Aprovechando que &&fue realmente inteligente, te felicito (pero parece un poco engañoso)
MayorMonty
2

05AB1E, 35 bytes

"{[()]}"DRr‡`rJ¹Q,Q¹Jr`‡rRD"{[()]}"

Pruébalo en línea!

Explicación:

                     # Implicit input
 "{[()]}"            # Push "{[()]}" onto the stack
         DR          # Pushes a reversed copy onto the stack
           r         # Reverse the order of the stack
            ‡        # Transliterate
             `       # Flatten array on stack
              r      # Reverse order of stack
               J     # Join stack
                ¹Q   # Check equality with first input
                  ,  # Print
                     # Everything after is still syntactically correct, but just does not print anything.
Oliver Ni
fuente
No creo que esto ayude, ya que la respuesta no es válida, pero en lugar de "()[]{}"usted puede hacerložu„<>-
acrolith
@daHugLenny Es válido ahora
Oliver Ni el
¿Se qanaliza el resto del programa después de al menos la validez sintáctica? Si no, consideraría esto como comentar la segunda mitad del código.
Algoritmo de tiburón
@algorithmshark Corregido.
Oliver Ni
1

CJam, 38 bytes

Q~"=re%W_@%W_q"`{[()]}`"q_W%@_W%er="~Q

Imprime "=re%W_@%W_q"1si la entrada es convenientemente palindrómica y de "=re%W_@%W_q"0otro modo.

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

Q~                                     e# Evaluate an empty string.
  "=re%W_@%W_q"                        e# Push that string.
               `                       e# Inspect. Pushes "\"=re%W_@%W_q\"".
                {[()]}                 e# Push that block.
                      `                e# Inspect. Pushes "{[()]}".
                       "           "~  e# Push and evaluate.
                        q              e# Read from STDIN.
                         _W%           e# Push a reversed copy.
                            @          e# Rotate "{[()]}" on top of the stack.
                             _W%       e# Push a reversed copy.
                                er     e# Perform transliteration.
                                  =    e# Compare to the input string.
                                     Q e# Push an empty string.

Después de ejecutar el programa, CJam imprime automáticamente los tres elementos en la pila: la cadena inspeccionada, el booleano de la comparación de cadenas y la cadena vacía.

Dennis
fuente
0

Perl, 83 + 2 = 85 bytes

Corre con -nl

say$_~~reverse y-"({[]})"-")}][{("-r;exit;tixe;r-")}][{("-"({[]})"-y esrever~~_$yas

El código sale después de imprimir la veracidad de la entrada. Todo después del punto y coma se interpreta (y se bloqueará cuando el script llegue a ese punto si no fuera por el exitque encuentra), pero no se ejecuta. Si me quedara exit;tixe;fuera del código, aún imprimiría el resultado correctamente antes de que se bloqueara.

Gabriel Benamy
fuente