13
\$\begingroup\$

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.

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

14 Answers 14

10
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I should learn J. Any tutorials for a python programmer? \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Apr 3 '14 at 20:27
  • 1
    \$\begingroup\$ @Synthetica the official one is good \$\endgroup\$ – John Dvorak Apr 3 '14 at 20:28
  • 2
    \$\begingroup\$ @Synthetica Nothing specifically for Pythoners, but J for C Programmers is a great resource for anybody migrating from imperative programming. \$\endgroup\$ – algorithmshark Apr 3 '14 at 20:30
10
\$\begingroup\$

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

\$\endgroup\$
  • 9
    \$\begingroup\$ +1 for "Not PHP" ;) \$\endgroup\$ – Martin Ender Apr 3 '14 at 19:28
  • 1
    \$\begingroup\$ <?php $line = fgets(STDIN); ?> \$\endgroup\$ – User011001 Apr 3 '14 at 19:28
  • 2
    \$\begingroup\$ @User011001 Where would that fit in? \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Apr 3 '14 at 19:55
  • 1
    \$\begingroup\$ 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... \$\endgroup\$ – Kaya Apr 3 '14 at 20:53
  • 1
    \$\begingroup\$ @Kaya You can simply use 1 instead of True as well. 1 == True, after all. \$\endgroup\$ – arshajii Apr 4 '14 at 13:38
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Guess there must be a shorter way but I didn't find it. \$\endgroup\$ – Howard Apr 3 '14 at 21:14
  • \$\begingroup\$ 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? \$\endgroup\$ – unclemeat Apr 3 '14 at 22:12
  • \$\begingroup\$ @unclemeat, yes. Penultimate sentence of the spec. \$\endgroup\$ – Peter Taylor Apr 3 '14 at 22:17
  • \$\begingroup\$ 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). \$\endgroup\$ – Peter Taylor Apr 3 '14 at 22:21
  • 2
    \$\begingroup\$ @Howard If I had a nickel for every time I felt that way about Golfscript... \$\endgroup\$ – algorithmshark Apr 3 '14 at 23:21
4
\$\begingroup\$

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]]
\$\endgroup\$
  • 2
    \$\begingroup\$ @Arm103 I could, but I'll leave that to someone else. ;) \$\endgroup\$ – Martin Ender Apr 3 '14 at 19:08
  • 2
    \$\begingroup\$ @Arm103 wait, is this your homework? \$\endgroup\$ – John Dvorak Apr 3 '14 at 19:14
  • 2
    \$\begingroup\$ @JanDvorak There are CS courses that use PHP? That would be scary. \$\endgroup\$ – Chris Jester-Young Apr 3 '14 at 19:15
  • 2
    \$\begingroup\$ @Arm103 no. You can't ;-) \$\endgroup\$ – John Dvorak Apr 3 '14 at 19:16
  • 4
    \$\begingroup\$ @JanDvorak hmmm, what's a program in Mathematica? \$\endgroup\$ – Martin Ender Apr 3 '14 at 19:29
3
\$\begingroup\$

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].

\$\endgroup\$
  • \$\begingroup\$ 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. :-) \$\endgroup\$ – Dr. Rebmu Apr 6 '14 at 22:05
3
\$\begingroup\$

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); 
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Yay fun!!!!! :) \$\endgroup\$ – Almo Apr 4 '14 at 15:23
  • 1
    \$\begingroup\$ In the golfed version, where is R defined and used? \$\endgroup\$ – Toothbrush Apr 5 '14 at 10:31
  • \$\begingroup\$ oh yeah, it should say var R = s.Remove(i,1). good catch \$\endgroup\$ – Will Newton Apr 5 '14 at 14:56
2
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – draegtun Apr 4 '14 at 16:06
  • \$\begingroup\$ Fixed the -1, thanks. Not sure what you have in mind regards taking it out a method though, I'll have a think. \$\endgroup\$ – Mike Campbell Apr 4 '14 at 17:31
  • \$\begingroup\$ Ok, took your advise on board and rewrote it :), ty. \$\endgroup\$ – Mike Campbell Apr 4 '14 at 17:40
  • \$\begingroup\$ You're welcome! Now that is much better :) +1 \$\endgroup\$ – draegtun Apr 4 '14 at 18:45
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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);
    }
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – ace Apr 4 '14 at 14:24
  • \$\begingroup\$ This worked alright..Can anyone explain the logic behind this ? \$\endgroup\$ – Arindam Roychowdhury Apr 25 '16 at 10:07
0
\$\begingroup\$

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
\$\endgroup\$
-1
\$\begingroup\$

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();
   }
}
\$\endgroup\$
  • \$\begingroup\$ This shows no attempt at golfing the code. \$\endgroup\$ – mbomb007 Oct 6 '16 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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