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.

Problem

Let's say that a word is almost a palindrome if it is possible to remove one of its letters so that the word becomes a palindrome. Your task is to write a program that for a given word determines which letter to remove to get a palindrome.

The shortest code to do this in any programming language wins.

Input

Input consists of a word of uppercase letters from 2 to 1000 characters long.

Output

Output the 1-indexed position (leftmost letter has position 1, the next one has position 2 and so on) of the letter which should be removed. If there are possible choices that lead to the palindrome, output any of those positions. Note that you are required to remove a letter even if the given word is already a palindrome. If the given word is not almost an palindrome, output -1.


Example

The input:

racercar

might produce the output:

5

because removing the 5th letter produces racecar, which is a palindrome.

Also, the input

racecar

can still produce the output

4

because removing the 4th letter to produce raccar is still a palindrome.

share|improve this question
5  
No examples posted? And what to output if it is not possible to make the input into a Palindrome? –  ProgrammerDan Apr 3 at 18:55
3  
@Arm103 you are still missing the examples you are referring to –  Martin Büttner Apr 3 at 19:14
23  
Warning: "(see example 3)". This suggests that this is homework since no examples were ever posted. –  Quincunx Apr 3 at 19:55
3  
@Quincunx Be sure to read the thread on the Mathematica submission, too. :-) –  Chris Jester-Young Apr 3 at 20:01
3  
This question appears to be off-topic because example 3 is missing from the question. –  devnull Apr 4 at 3:15

14 Answers 14

J - 31 25 char

(_1{ ::[1+[:I.1(-:|.)\.])

Largely standard fare for J, so I'll just point out the cool bits.

  • The adverb \. is called Outfix. x u\. y removes every infix of length x from y and applies u to the result of each removal. Here, x is 1, y is the input string, and u is (-:|.), a test for whether the string matches its reverse. Hence the result of this application of \. is a list of booleans, 1 in the place of each character whose removal makes the input a palindrome.

  • I. creates an list of all the indices (0-origin) from above where there was a 1. Adding 1 with 1+ makes these 1-origin indices. If no indices were 1, the list is empty. Now, we try to take the last element with _1{. (We are allowed to output any of the removable letters!) If this works, we return. However, if the list was empty, there were no elements at all, so { throws a domain error which we catch with :: and return the -1 with [.

Usage (recall that NB. is for comments):

   (_1{ ::[1+[:I.1(-:|.)\.]) 'RACECAR'    NB. remove the E
4
   (_1{ ::[1+[:I.1(-:|.)\.]) 'RAACECAR'   NB. remove an A
3
   (_1{ ::[1+[:I.1(-:|.)\.]) 'RAAACECAR'  NB. no valid removal
_1
share|improve this answer
    
I should learn J. Any tutorials for a python programmer? –  ɐɔıʇǝɥʇuʎs Apr 3 at 20:27
1  
@Synthetica the official one is good –  Jan Dvorak Apr 3 at 20:28
2  
@Synthetica Nothing specifically for Pythoners, but J for C Programmers is a great resource for anybody migrating from imperative programming. –  algorithmshark Apr 3 at 20:30

Not-PHP Python (73):

[a[:g]+a[g+1:]==(a[:g]+a[g+1:])[::-1] for g in range(len(a))].index(1)

Where a is the string you want to check. This, however, throws an error if you can't turn it in an palindrome. Instead, you could use

try:print [a[:g]+a[g+1:]==(a[:g]+a[g+1:])[::-1] for g in range(len(a))].index(True)
except ValueError:print -1

EDIT: No, wait, it does work!

try: eval("<?php $line = fgets(STDIN); ?>")
except: print [a[:g]+a[g+1:]==(a[:g]+a[g+1:])[::-1] for g in range(len(a))].index(1)

Thanks, this does indeed raise the php-contents of this script by about 25% (that's what you want, right?)

share|improve this answer
9  
+1 for "Not PHP" ;) –  Martin Büttner Apr 3 at 19:28
1  
<?php $line = fgets(STDIN); ?> –  User011001 Apr 3 at 19:28
2  
@User011001 Where would that fit in? –  ɐɔıʇǝɥʇuʎs Apr 3 at 19:55
1  
You could save a char each by writing 1>0 instead of True and by removing the space between ] and for in ...[::-1] for g... –  Kaya Apr 3 at 20:53
1  
@Kaya You can simply use 1 instead of True as well. 1 == True, after all. –  arshajii Apr 4 at 13:38

GolfScript, 28 26 characters

:I,,{)I/();\+.-1%=}?-2]0=)

Thanks to Peter for shortening by 2 characters. Try the test cases online:

> "RACECAR" 
4
> "RAACECAR" 
2
> "RAAACECAR" 
-1
> "ABCC1BA" 
5
> "AAAAAA" 
1
> "ABCDE" 
-1
> "" 
-1
> "A" 
1
share|improve this answer
    
Guess there must be a shorter way but I didn't find it. –  Howard Apr 3 at 21:14
    
RACECAR is still a palindrome with the E. Is it necessary to specify a character to remove, when the inputted word is already a palindrome? –  unclemeat Apr 3 at 22:12
    
@unclemeat, yes. Penultimate sentence of the spec. –  Peter Taylor Apr 3 at 22:17
    
Why -2]$-1=)? At the start of that block you have at most one item on the stack, so you can easily shorten to -2]0=). (Or for the same length, ]-2or). I've learnt to love or for special cases). –  Peter Taylor Apr 3 at 22:21
2  
@Howard If I had a nickel for every time I felt that way about Golfscript... –  algorithmshark Apr 3 at 23:21

Mathematica, 106 98 87 91 characters

I suppose I'm slightly handicapped by the long function names, but problems like this are quite fun in Mathematica:

f=Tr@Append[Position[c~Drop~{#}&/@Range@Length[c=Characters@#],l_/;l==Reverse@l,{1}],{-1}]&

It throws some warnings, because the l_ pattern also matches all the characters inside, which Reverse can't operate on. But hey, it works!

Somewhat ungolfed:

f[s_] := 
  Append[
    Cases[
      Map[{#, Drop[Characters[s], {# }]} &, Range[StringLength[s]]], 
      {_, l_} /; l == Reverse[l]
    ], 
    {-1}
  ][[1, 1]]
share|improve this answer
2  
@Arm103 I could, but I'll leave that to someone else. ;) –  Martin Büttner Apr 3 at 19:08
2  
@Arm103 wait, is this your homework? –  Jan Dvorak Apr 3 at 19:14
2  
@JanDvorak There are CS courses that use PHP? That would be scary. –  Chris Jester-Young Apr 3 at 19:15
2  
@Arm103 no. You can't ;-) –  Jan Dvorak Apr 3 at 19:16
4  
@JanDvorak hmmm, what's a program in Mathematica? –  Martin Büttner Apr 3 at 19:29

Rebol (81)

r: -1 repeat i length? s[t: head remove at copy s i if t = reverse copy t[r: i]]r

Example usage in Rebol console:

>> s: "racercar"
== "racercar"

>> r: -1 repeat i length? s[t: head remove at copy s i if t = reverse copy t[r: i]]r
== 5

>> s: "1234"
== "1234"

>> r: -1 repeat i length? s[t: head remove at copy s i if t = reverse copy t[r: i]]r 
== -1


Above returns index of last palindrome found. An alternative solution (85 chars) which returns every palindrome found would be:

collect[repeat i length? s[t: head remove at copy s i if t = reverse copy t[keep i]]]

So for "racercar" this would return list [4 5].

share|improve this answer
    
If you used the Rebmu dialect that first solution is just 37 characters, despite being basically the same code :-) Invoke as rebmu/args "Rng01rpNl?A[ThdRMatCYaNieTrvCYt[Rn]]r" "racecar". Note that the Rebmu documentation has been improved, and recent changes have tightened it up a bit...still looking to feedback before everyone and their D starts using it. :-) –  Dr. Rebmu Apr 6 at 22:05

C#, 134 Characters

static int F(string s,int i=0){if(i==s.Length)return-1;var R=s.Remove(i,1);return R.SequenceEqual(R.Reverse())?i+1:F(s,i+1);}

I know I lose :( but it was still fun :D

Readable version:

using System.Linq;

// namespace and class

static int PalindromeCharIndex(string str, int i = 0)
{
    if (i == str.Length) return -1;
    var removed = str.Remove(i, 1);
    return removed.SequenceEqual(removed.Reverse()) 
        ? i+1
        : PalindromeCharIndex(str, i + 1); 
}
share|improve this answer
3  
Yay fun!!!!! :) –  Almo Apr 4 at 15:23
1  
+1 for non-standard language –  Jeff Gohlke Apr 4 at 19:55
1  
In the golfed version, where is R defined and used? –  toothbrush Apr 5 at 10:31
    
oh yeah, it should say var R = s.Remove(i,1). good catch –  Will Newton Apr 5 at 14:56

Ruby (61):

(1..s.size+1).find{|i|b=s.dup;b.slice!(i-1);b.reverse==b}||-1

Here, have a ruby solution. It will return the position of the character to remove or -1 if it cannot be done.

I can't help but feel there's improvement to be made with the dup and slice section, but Ruby doesn't appear to have a String method that will remove a character at a specific index and return the new string -__-.

Edited as per comment, ty!

share|improve this answer
1  
You can save some space by not wrapping in a function/method. However your code currently returns 0-based index (needs to be 1-based) and it also needs to return -1 if no palindrome found. –  draegtun Apr 4 at 16:06
    
Fixed the -1, thanks. Not sure what you have in mind regards taking it out a method though, I'll have a think. –  Mike Campbell Apr 4 at 17:31
    
Ok, took your advise on board and rewrote it :), ty. –  Mike Campbell Apr 4 at 17:40
    
You're welcome! Now that is much better :) +1 –  draegtun Apr 4 at 18:45

Haskell, 107 characters:

(x:y)!1=y;(x:y)!n=x:y!(n-1)
main=getLine>>= \s->print$head$filter(\n->s!n==reverse(s!n))[1..length s]++[-1]

As a function (85 characters):

(x:y)!1=y;(x:y)!n=x:y!(n-1)
f s=head$filter(\n->s!n==reverse(s!n))[1..length s]++[-1]

original ungolfed version:

f str = case filter cp [1..length str] of
          x:_ -> x
          _   -> -1
    where cp n = palindrome $ cut n str
          cut (x:xs) 1 = xs
          cut (x:xs) n = x : cut xs (n-1)
          palindrome x = x == reverse x
share|improve this answer

C# (184 characters)

I admit this is not the best language to do code-golfing...

using System.Linq;class C{static void Main(string[]a){int i=0,r=-1;while(i<a[0].Length){var x=a[0].Remove(i++,1);if(x==new string(x.Reverse().ToArray()))r=i;}System.Console.Write(r);}}

Formatted and commented:

using System.Linq;

class C
{
    static void Main(string[] a)
    {
        int i = 0, r = -1;
        // try all positions
        while (i < a[0].Length)
        {
            // create a string with the i-th character removed
            var x = a[0].Remove(i++, 1);
            // and test if it is a palindrome
            if (x == new string(x.Reverse().ToArray())) r = i;
        }
        Console.Write(r);
    }
}
share|improve this answer

C# (84 Characters)

int x=0,o=i.Select(c=>i.Remove(x++,1)).Any(s=>s.Reverse().SequenceEqual(s))?x:-1;

LINQpad statement expecting the variable i to contain the input string. Output is stored in the o variable.

share|improve this answer

Haskell, 118C

m s|f s==[]=(-1)|True=f s!!0
f s=[i|i<-[1..length s],r s i==(reverse$r s i)]
r s i=let(a,_:b)=splitAt (i-1) s in a++b

Ungolfed:

fix s
    |indices s==[] = (-1)
    |True = indices s!!0
indices s = [i|i<-[1..length s],remove s i==(reverse$remove s i)]
remove s i = let (a,_:b) = (splitAt (i-1) s) in a++b
share|improve this answer

Python, 84

for i in range(len(s)):
    if s[i]!=s[-(i+1)]:
        if s[i]!=s[-(i+2)]:
            return i+1
        else:
            return len(s)-i

This does not check is the input (string s) is almost palindrome, but is time efficient and readable.

share|improve this answer
2  
s[-(i+1)] can be shortened to s[-i-1]. Also, I'm not sure but you may be able to replace the if...else... with return i+1 if ... else len(s)-1 –  ace Apr 4 at 14:24

Haskell, 80

a%b|b<1=0-1|(\x->x==reverse x)$take(b-1)a++b`drop`a=b|1<2=a%(b-1)
f a=a%length a

Called like this:

λ> f "racercar"
5
share|improve this answer

My first code-golf.

Java. ~1200 characters in the main (and sub) functions. Yeah baby.

Class top and usage:

public class ElimOneCharForPalindrome  {
   public static final void main(String[] ignored)  {
      System.out.println(getEliminateForPalindromeIndex("racercar"));
      System.out.println(getEliminateForPalindromeIndex("racecar"));
   }

The main function:

   public static final int getEliminateForPalindromeIndex(String oneCharAway_fromPalindrome)  {
      for(int i = 0; i < oneCharAway_fromPalindrome.length(); i++)  {
         String strMinus1Char = oneCharAway_fromPalindrome.substring(0, i) + oneCharAway_fromPalindrome.substring(i + 1);

         String half1 = getFirstHalf(strMinus1Char);
         String half2Reversed = getSecondHalfReversed(strMinus1Char);

         if(half1.length() != half2Reversed.length())  {
            //One half is exactly one character longer
            if(half1.length() > half2Reversed.length())  {
               half1 = half1.substring(0, (half1.length() - 1));
            }  else  {
               half2Reversed = half2Reversed.substring(0, (half2Reversed.length() - 1));
            }
         }

         //System.out.println(i + " " + strMinus1Char + " --> " + half1 + " / " + half2Reversed + "  (minus the singular [non-mirrored] character in the middle, if any)");

         if(half1.equals(half2Reversed))  {
            return  i;
         }
      }
      return  -1;
   }

Sub-functions:

   public static final String getFirstHalf(String whole_word)  {
      return  whole_word.substring(0, whole_word.length() / 2);
   }
   public static final String getSecondHalfReversed(String whole_word)  {
      return  new StringBuilder(whole_word.substring(whole_word.length() / 2)).reverse().toString();
   }
}

Full class:

public class ElimOneCharForPalindrome  {
   public static final void main(String[] ignored)  {
      System.out.println(getEliminateForPalindromeIndex("racercar"));
      System.out.println(getEliminateForPalindromeIndex("racecar"));
   }
   public static final int getEliminateForPalindromeIndex(String oneCharAway_fromPalindrome)  {
      for(int i = 0; i < oneCharAway_fromPalindrome.length(); i++)  {
         String strMinus1Char = oneCharAway_fromPalindrome.substring(0, i) + oneCharAway_fromPalindrome.substring(i + 1);

         String half1 = getFirstHalf(strMinus1Char);
         String half2Reversed = getSecondHalfReversed(strMinus1Char);

         if(half1.length() != half2Reversed.length())  {
            //One half is exactly one character longer
            if(half1.length() > half2Reversed.length())  {
               half1 = half1.substring(0, (half1.length() - 1));
            }  else  {
               half2Reversed = half2Reversed.substring(0, (half2Reversed.length() - 1));
            }
         }

         //System.out.println(i + " " + strMinus1Char + " --> " + half1 + " / " + half2Reversed + "  (minus the singular [non-mirrored] character in the middle, if any)");

         if(half1.equals(half2Reversed))  {
            return  i;
         }
      }
      return  -1;
   }
   public static final String getFirstHalf(String whole_word)  {
      return  whole_word.substring(0, whole_word.length() / 2);
   }
   public static final String getSecondHalfReversed(String whole_word)  {
      return  new StringBuilder(whole_word.substring(whole_word.length() / 2)).reverse().toString();
   }
}
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.