Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

If you've ever tried to write palindromic code before, you'd know how much brackets tend to get in your way. ()() is not a palindrome, even though it kinda looks like it should be, while ())( and ()( are both palindromic and both very dumb looking. Wouldn't it be convenient if it was the other way around?

A string is conveniently palindromic if it is equal to the string derived when its reverse has all its parentheses (()), brackets ([]), and braces ({}) flipped. No other characters are special and require flipping. (<> are sometimes paired but often not so they are left out.)

Your task is to write, in your language, a program (taking input on STDIN) or a function (taking a single string argument) which (a) gives a consistent true value* when its argument is conveniently palindromic and a different, consistent false value otherwise, and (b) is itself conveniently palindromic.

For example, the following inputs are conveniently palindromic:

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

And the following are not:

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

You may not rely on any external state (specific filename, directory structure, other user input, web access, etc) except interpreter/compiler flags.

Also, you may not use "the comment trick" where you comment out or render unused some piece of code by taking advantage of your language's commenting facilities. For instance, all of the following are not allowed, because they contain non-functional parts that can be safely removed or destroyed (at the expense of losing conveniently-palindromic-ness):

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

Obviously this might not cover every such case, but the spirit of the challenge here is not to use comments and unparsed** code to achieve palindrominess, instead making use of the corrected parens and brackets. I'm looking at you, LISP, Brainfuck.

This is a , so the shortest code wins, but all lengths of code are welcome.

* By consistent true and false values, I mean that you can return one of a pair of values, such as 1 for true and 0 for false, or False for true and "no" for false, so long as these values are different from each other, and do not change from run to run of your program. Use whatever saves you characters.

** Not to be confused with unexecuted: code that is valid and might do weird things but never called is fine.

share|improve this question
    
What about things like if(false){some code} or unused variables? Are they allowed? –  ace May 18 at 17:13
    
@ace If your language somehow parses or checks the unexecuted code for type agreement or syntactic validity, that's fine. If it is tantamount to a comment because your language doesn't check the inside of that block, when it would throw a syntax error if it did, that's not fine. I think if you can find a valid use for (eslaf)fi, you get to use if(false). –  algorithmshark May 18 at 17:35
28  
It took me way too long to figure out why ()() is not a palindrome –  David Grinberg May 18 at 22:27
    
Does the code have to work with multi-line input? –  Ventero May 20 at 2:22
    
@Ventero Newlines and carriage returns are characters, and they don't have any pairs to flip with, so I'd say they count as normal characters. –  algorithmshark May 20 at 2:29

5 Answers 5

up vote 9 down vote accepted

J (60)

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

This is a function that takes an argument:

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

Explanation:

  • f :: g runs the function f over the input, and returns the result if it returns without error. If f fails, it runs g instead.

  • The f here is (|.-:'())([]][{}}{'&charsub), which does the actual work:

    • |.: reverse
    • -:: is equal to
    • '())([]][{}}{'&charsub: replacing each bracket with its opposing bracket
  • The g function is (busrahc&'}{{}][[])(()':-.|), which is nonsense but syntactically valid. busrahc is not defined, but that doesn't matter because it is only resolved when it is run (and it won't run).
share|improve this answer
    
You can save a character by turning your f :: g into g@-@f. g is equivalent to the hook (-.|) because of : so the outputs become -1 and the empty list for conveniently palindromic and not, respectively. –  algorithmshark May 18 at 21:11

GolfScript, 107 91 / 155 bytes

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

Newlines are artistic. fi, c43 and c are noops, but the entire code is executed.

At the cost of 64 bytes, this can be improved upon:

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

As before, the entire code is executed. The difference is that every single byte affects the output.

Tests and examples

$ 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

How it works

.             # 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 present.
  ~           # 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. This discards dummy values.
1;            # Push 1 and discard.
=             # Push 1 if the modified string matches the original one and 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 present.
   +~         # Add 1 to the position and negate. Examples: -1 -> -1    0 -> -2    1 -> -3
  '"([{}])"'  # Push that string.
  ""          # Push that string.
  +           # Concatenate. Result: '"([{}])"' 
  (\          # Unshift 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 the dummy values.
  1;          # Push 1 and discard.
  =           # Push 1 if the modified string matches the original one and 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.
share|improve this answer

Ruby, 110

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

Prints true if the input is a convenient palindrome and false if it isn't. Note that this solution assumes that the input isn't terminated by a newline, so test it with 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

This is a somewhat straightforward port of my answer to Palindromic Palindrome Checker (and not really golfed so far). The main trick used is that the first parenthesised expression always returns 1, so the second half of the boolean expression is never evaluated (but it is parsed).

The only difficulty in adapting this was figuring out how to add the call to z.tr so that its "convenient reverse" would also be syntactically valid - but I could simply use the same trick I already used puts: *, which in the first half is parsed as splat operator (use array contents as function parameters) and as array multiplication (or repitition) operator in the second half.

Ruby, 157 297, all code executed

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

This (slightly longer) version executes all code, and all but two lines affect the output, which is printed in the last line - but all lines are parsed and executed without any errors. This version interprets any trailing newline as part of the input, so use either echo -n to test it, or prepend your input with a newline. It prints true if the input is a convenient palindrome, and false otherwise.

Explanation

# 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
share|improve this answer
    
cat abuuuuuseeeee! –  mniip May 20 at 5:21

GolfScript, 61 chars

OK, here's a baseline solution in GolfScript. I'm sure it could be further improved:

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

As usual for GolfScript, this program reads its input from stdin. It outputs:

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

if the input is a convenient palindrome, as defined in the challenge above, and:

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

if it is not.

Explanation: This program relies heavily on the ruling that unexecuted code is OK, as long as it gets parsed. It consists of two code blocks, delimited by curly braces ({ }), which are mirror images of each other.

The first code block is executed by the ~ following it, and checks if the input is a convenient palindrome, outputting 1 if it is and 0 if it isn't. The second code block is not executed, and so simply remains on the stack until the program ends and everything on the stack gets automatically stringified and printed by the GolfScript interpreter.

It should be noted that the GolfScript interpreter does very few syntax checks at parse time (or ever, for that matter); a GolfScript code block literal can contain almost anything, even if it might crash when executed. Still, a few syntax errors, such as unterminated string literals, do raise an error even in unexecuted code, so I believe this solution (barely) falls within the rules.

Ps. Looking at the actual executed code, it contains a few conveniently palindromic elements like @[.]@, the string literal "([{}])", and even the loop %{ ... }%. This offers the tantalizing suggestion that an "intrinsically palindromic" GolfScript solution, where the full palindromic program would be executed and functional, might actually be possible. As I haven't managed to produce one myself yet, I hereby offer a +100 rep bounty to the first person who manages to come up with one!

share|improve this answer
3  
wait, ur code is a palindrome itself? :O –  Fabricio May 18 at 21:31
    
I'm inclined to consider this solution more like the "n\";X;";X;"\n"-kind of commenting, but I'll give you the benefit of the doubt. I was really looking for such "intrinsically palindromic" solutions to begin with, however, or at least ones where the non-execution of blocks was a little more underhanded. –  algorithmshark May 18 at 21:57
    
My answer has a noop (undefined variable) and a few parts that accomplish nothing (e.g., 1;). Does that still count as fully functional? –  Dennis May 19 at 17:25
    
@Dennis: Yeah, I think it does. Congratulations, it's certainly impressive enough. The question seems to be new enough that I can't post the bounty on it yet, but you'll have it in a few days. –  Ilmari Karonen May 19 at 17:31
    
There's no hurry. I didn't manage to get rid of the undefined variable fi, but at least dropping any of its letters now breaks something. –  Dennis May 19 at 23:56

Javascript (ES6) 288

Runs in the Spidermonkey command line shell. Reads a single line from STDIN and outputs true or false depending on if the input is a convenient palindrome.

((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))

This code is syntactically valid, but everything after && is not executed, as the print function returns a falsey value.

You can run this code in Firefox's console by running this shim first to emulate the readline and print functions. Edit the input inside readline as needed:

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

And here's a quick example of the output:

command line example

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.