Supprimer une lettre pour faire un palindrome

15

Problème

Disons qu'un mot est presque un palindrome s'il est possible d'enlever une de ses lettres pour que le mot devienne un palindrome. Votre tâche consiste à écrire un programme qui, pour un mot donné, détermine la lettre à supprimer pour obtenir un palindrome.

Le code le plus court pour le faire dans n'importe quel langage de programmation gagne.

Contribution

L'entrée se compose d'un mot de lettres majuscules de 2 à 1 000 caractères.

Production

Sortez la position indexée 1 (la lettre la plus à gauche a la position 1, la suivante a la position 2 et ainsi de suite) de la lettre qui doit être supprimée. S'il existe des choix possibles menant au palindrome, sortez l'une de ces positions. Notez que vous devez supprimer une lettre même si le mot donné est déjà un palindrome. Si le mot donné n'est pas presque un palindrome, affichez -1.


Exemple

L'entrée:

racercar

pourrait produire la sortie:

5

parce que la suppression de la 5e lettre produit racecar, qui est un palindrome.

De plus, l'entrée

racecar

peut toujours produire la sortie

4

parce que retirer la 4e lettre à produire raccarest toujours un palindrome.

User011001
la source
5
Aucun exemple publié? Et quoi sortir s'il n'est pas possible de faire l'entrée dans un Palindrome?
ProgrammerDan
3
@ Arm103 vous manque toujours les exemples auxquels vous faites référence
Martin Ender
27
Avertissement: "(voir exemple 3)". Cela suggère qu'il s'agit de devoirs, car aucun exemple n'a été publié.
Justin
3
@Quincunx Assurez-vous de lire également le fil de la soumission Mathematica. :-)
Chris Jester-Young
3
Cette question semble être hors sujet car l' exemple 3 est absent de la question.
devnull

Réponses:

10

J - 31 25 caractères

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

Tarif largement standard pour J, donc je vais juste souligner les morceaux sympas.

  • L'adverbe \.s'appelle Outfix . x u\. ysupprime tous les infix de la longueur xde yet applique uau résultat de chaque retrait. Ici, xest 1, yest la chaîne d'entrée, et uest (-:|.), un test pour savoir si la chaîne correspond à son inverse. D'où le résultat de cette application de \.est une liste de booléens, 1 à la place de chaque personnage dont la suppression fait de l'entrée un palindrome.

  • I.crée une liste de tous les indices (origine 0) d'en haut où il y avait un 1. L'ajout de 1 avec 1+rend ces indices d'origine 1. Si aucun indice n'était égal à 1, la liste est vide. Maintenant, nous essayons de prendre le dernier élément avec _1{. (Nous sommes autorisés à sortir n'importe laquelle des lettres amovibles!) Si cela fonctionne, nous revenons. Cependant, si la liste était vide, il n'y avait aucun élément du tout, {lance donc une erreur de domaine avec laquelle nous interceptons ::et renvoyons le -1 avec [.

Utilisation (rappelez-vous que NB.c'est pour les commentaires):

   (_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
algorithmshark
la source
Je devrais apprendre J. Des tutoriels pour un programmeur python?
ɐɔıʇǝɥʇuʎs
1
@Synthetica l'officiel est bon
John Dvorak
2
@Synthetica Rien de spécifique pour Pythoners, mais J for C Programmers est une excellente ressource pour quiconque migre de la programmation impérative.
algorithmshark
10

Python non PHP (73):

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

Où a est la chaîne que vous souhaitez vérifier. Cependant, cela génère une erreur si vous ne pouvez pas le tourner dans un palindrome. Au lieu de cela, vous pouvez utiliser

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: Non, attendez, cela fonctionne!

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)

Merci, cela augmente en effet le contenu php de ce script d'environ 25% (c'est ce que vous voulez, non?)

ɐɔıʇǝɥʇuʎs
la source
10
+1 pour "Not PHP";)
Martin Ender
1
<? php $ line = fgets (STDIN); ?>
User011001
2
@ User011001 Où cela s'intégrerait-il?
ɐɔıʇǝɥʇuʎs
1
Vous pouvez enregistrer un omble chevalier chacun en écrivant au 1>0lieu de Trueet en supprimant l'espace entre ]et fordans...[::-1] for g...
Kaya
1
@Kaya Vous pouvez simplement utiliser 1plutôt Trueque. 1 == True, après tout.
arshajii
5

Mathematica, 106 98 87 91 caractères

Je suppose que je suis légèrement handicapé par les longs noms de fonctions, mais des problèmes comme celui-ci sont assez amusants dans Mathematica:

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

Il lance quelques avertissements, car le l_modèle correspond également à tous les caractères à l'intérieur, qui Reversene peuvent pas fonctionner. Mais bon, ça marche!

Assez peu golfé:

f[s_] := 
  Append[
    Cases[
      Map[{#, Drop[Characters[s], {# }]} &, Range[StringLength[s]]], 
      {_, l_} /; l == Reverse[l]
    ], 
    {-1}
  ][[1, 1]]
Martin Ender
la source
2
@ Arm103 Je pourrais, mais je laisserai ça à quelqu'un d'autre. ;)
Martin Ender
2
@ Arm103 attendez, est-ce vos devoirs?
John Dvorak
2
@JanDvorak Il existe des cours CS qui utilisent PHP? Ce serait effrayant.
Chris Jester-Young
2
@ Arm103 no. Vous ne pouvez pas ;-)
John Dvorak
4
@JanDvorak hmmm, qu'est-ce qu'un programme en Mathematica?
Martin Ender
5

GolfScript, 28 26 caractères

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

Merci à Peter d'avoir raccourci de 2 caractères. Essayez les cas de test en ligne :

> "RACECAR" 
4
> "RAACECAR" 
2
> "RAAACECAR" 
-1
> "ABCC1BA" 
5
> "AAAAAA" 
1
> "ABCDE" 
-1
> "" 
-1
> "A" 
1
Howard
la source
Je suppose qu'il doit y avoir un chemin plus court mais je ne l'ai pas trouvé.
Howard
RACECARest toujours un palindrome avec le E. Est-il nécessaire de spécifier un caractère à supprimer, alors que le mot saisi est déjà un palindrome?
unclemeat
@unclemeat, oui. Avant-dernière phrase de la spécification.
Peter Taylor
Pourquoi -2]$-1=)? Au début de ce bloc, vous avez au plus un élément sur la pile, vous pouvez donc facilement le raccourcir -2]0=). (Ou pour la même durée ]-2or). J'ai appris à aimer ordes cas spéciaux).
Peter Taylor
2
@Howard Si j'avais un nickel pour chaque fois que je ressentais ça pour Golfscript ...
algorithmshark
3

Rebol (81)

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

Exemple d'utilisation dans la console Rebol:

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


Ci-dessus retourne l'indice du dernier palindrome trouvé. Une solution alternative (85 caractères) qui renvoie chaque palindrome trouvé serait:

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

Donc, "racercar"cela reviendrait à la liste [4 5].

draegtun
la source
Si vous avez utilisé le dialecte Rebmu, cette première solution ne compte que 37 caractères, bien qu'il s'agisse essentiellement du même code :-) Appelez comme rebmu / args "Rng01rpNl? A [ThdRMatCYaNieTrvCYt [Rn]] r" "racecar" . Notez que la documentation de Rebmu a été améliorée et que les récents changements l'ont resserrée un peu ... toujours à la recherche de commentaires avant que tout le monde et son D ne commencent à l'utiliser. :-)
HostileFork dit de ne pas faire confiance au SE
3

C #, 134 caractères

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);}

Je sais que je perds :( mais c'était quand même amusant : D

Version lisible:

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); 
}
Will Newton
la source
3
Yay fun !!!!! :)
Almo
1
Dans la version golfée, où est Rdéfini et utilisé?
Brosse à dents
oh ouais, ça devrait dire var R = s.Remove (i, 1). bonne prise
Will Newton
3

Stax , 8 10 octets

ú·àA÷¡%5Ñ╙

Exécuter et déboguer

Ce programme montre tous les indices basés sur 1 qui peuvent être supprimés de la chaîne pour former un palindrome. Et s'il n'y en a pas, il indique -1.

récursif
la source
2
Cela renvoie le dernier index au lieu de -1 si aucun palindrome n'est trouvé (c'est-à-dire des aaabbsorties 5au lieu de -1).
Kevin Cruijssen
1
@KevinCruijssen: Vous avez raison. Je l'ai corrigé au prix de 2 octets.
récursif
2

Rubis (61):

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

Ici, ayez une solution rubis. Il retournera la position du personnage à supprimer ou -1 si cela ne peut pas être fait.

Je ne peux pas m'empêcher de penser qu'il y a une amélioration à faire avec la section dup et slice, mais Ruby ne semble pas avoir de méthode String qui supprimera un caractère à un index spécifique et renverra la nouvelle chaîne -__-.

Modifié selon le commentaire, ty!

Mike Campbell
la source
1
Vous pouvez économiser de l'espace en n'encapsulant pas une fonction / méthode. Cependant, votre code retourne actuellement un index basé sur 0 (doit être basé sur 1) et il doit également retourner -1si aucun palindrome n'a été trouvé.
draegtun
Correction du -1, merci. Je ne sais pas ce que vous avez en tête concernant la suppression d'une méthode, j'aurai une réflexion.
Mike Campbell
Ok, a pris votre conseil à bord et l'a réécrit :), ty.
Mike Campbell
Vous êtes les bienvenus! Maintenant, c'est beaucoup mieux :) +1
draegtun
2

05AB1E , 10 octets

gL.Δõs<ǝÂQ

Essayez-le en ligne ou vérifiez d'autres cas de test .

Explication:

g           # Get the length of the (implicit) input-string
 L          # Create a list in the range [1,length]
          # Find the first value in this list which is truthy for:
            # (which will output -1 if none are truthy)
    õ       #  Push an empty string ""
     s      #  Swap to get the current integer of the find_first-loop
      <     #  Decrease it by 1 because 05AB1E has 0-based indexing
       ǝ    #  In the (implicit) input-String, replace the character at that index with
            #  the empty string ""
        Â   #  Then bifurcate the string (short for Duplicate & Reverse copy)
         Q  #  And check if the reversed copy is equal to the original string,
            #  So `ÂQ` basically checks if a string is a palindrome)
            # (after which the result is output implicitly)
Kevin Cruijssen
la source
2

Pas PythonPHP ,85 83 81 octets

while($argn[$x])$s!=strrev($s=substr_replace($argn,'',$x++,1))?:die("$x");echo-1;
  • -2 octets grâce à @ Night2!

Essayez-le en ligne!

Inutilement récursif:

PHP , 96 octets

function f($a,$b='',$d=1){return$a?$c==strrev($c=$b.$e=substr($a,1))?$d:f($e,$b.$a[0],$d+1):-1;}

Essayez-le en ligne!

640 Ko
la source
1

Haskell, 107 caractères:

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

En fonction ( 85 caractères ):

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

version originale non golfée:

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
John Dvorak
la source
1

C # (184 caractères)

J'avoue que ce n'est pas la meilleure langue pour faire du golf de code ...

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);}}

Formaté et commenté:

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);
    }
}
Mormegil
la source
1

C # (84 caractères)

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

Instruction LINQpad s'attendant à ce que la variable icontienne la chaîne d'entrée. La sortie est stockée dans la ovariable.

Oskar Sjöberg
la source
1

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

Appelé comme ceci:

λ> f "racercar"
5
Flonk
la source
1

Japt , 8 octets

a@jYÉ êS

Essayez-le

a@jYÉ êS     :Implicit input of string
a            :Last 0-based index that returns true (or -1 if none do)
 @           :When passed through the following function as Y
  j          :  Remove the character in U at index
   YÉ        :    Y-1
      êS     :  Is palindrome?
Hirsute
la source
0

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

Non golfé:

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
danmcardle
la source
0

Gelée , 17 14 octets

ŒPṖLÐṀṚŒḂ€TXo-

Essayez-le en ligne!

           X      A random
          T       truthy index
ŒP                from the powerset of the input
  Ṗ               excluding the input
   LÐṀ            and all proper subsequences with non-maximal length
      Ṛ           reversed
       ŒḂ€        with each element replaced with whether or not it's a palindrome,
            o-    or -1.

Puisque j'ai changé mon approche assez rapidement pour que l'ancienne version ne s'affiche pas dans l'historique des modifications, voici ce qui suit: ŒPṚḊŒḂ€TṂ©’<La®o-

Chaîne indépendante
la source
0

Brachylog , 24 octets

{l+₁≥.ℕ₂≜&↔⊇ᶠ↖.tT↔T∨0}-₁

Essayez-le en ligne!

Sent trop long.

Peut être de deux octets plus court si la sortie peut être indexée sur 2 :

l+₁≥.ℕ₂≜&↔⊇ᶠ↖.tT↔T∨_1

Deux itérations antérieures et encore pires:

ẹ~c₃C⟨hct⟩P↔P∧C;Ȯ⟨kt⟩hl<|∧_1
l>X⁰ℕ≜<.&{iI¬tX⁰∧Ih}ᶠP↔P∨_1

L'utilisation par ce dernier d'une variable globale nécessite un en- tête de test différent .

Chaîne indépendante
la source
0

Python 3 , 71 octets

def f(s,i=1):n=s[:i-1]+s[i:];return(n==n[::-1])*i-(i>len(s))or f(s,i+1)

Essayez-le en ligne!

Renvoie le caractère indexé 1 si l'opération peut être effectuée et -1sinon.

Jitse
la source
0

C (gcc) , 180 168 159 157 140 139 octets

f(char*s){int j=strlen(s),m=j--/2,p=-1,i=0;for(;p&&i<m;)p=s[i++]^s[j--]&&!++p?s[i]-s[j+1]?s[i-1]-s[j]?p:j--+2:i++:p;return p<0?m+1:p?p:-1;}

Essayez-le en ligne!

2 16 17 octets rasés grâce au plafond! Et 3 octets de plus puisque les règles stipulent que la longueur minimale de l'entrée est de 2 caractères, donc ne devez pas vérifier les chaînes vides.

Non golfé:

f(char *s) {
  int j = strlen(s);             // j = length of input
  int m = j-- / 2;               // m = midpoint of string,
                                 // j = index of right character
  int p = -1;                    // p = position of extra character
                                 //     -1 means no extra character found yet
                                 //     0 means invalid input
  int i = 0;                     // i = index of left character

  for (; p && i < m; i++) {      // loop over the string from both sides,
                                 // as long as the input is valid.
    p = s[i] ^ s[j--]            // if (left character != right character
        && !++p ?                //     and we didn't remove a character yet*)
          s[i + 1] - s[j + 1] ?  //   if (left+1 char != right char)
            s[i] - s[j] ?        //     if (left char != right-1 char)
              p                  //       do nothing,
            :                    //     else
              j-- + 2            //       remove right char.
          :                      //   else
            ++i                  //       remove left char.
        :                        // else
          p;                     //     do nothing, or:
                                 //     *the input is marked invalid 
  } 

  return p < 0 ?                 // if (input valid and we didn't remove a character yet)
           m + 1                 //   return the midpoint character,
         :                       // else
           p ?                   //   if (we did remove a character)
             p                   //     return that character,
           :                     //   else
             -1;                 //     the input was invalid.
}
```
G. Sliepen
la source
@ceilingcat C'est &&!++pjuste sournois à expliquer :)
G. Sliepen
-1

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

Cela ne vérifie pas si l'entrée (chaîne s) est presque palindrome, mais est efficace en temps et lisible.

nicofmay
la source
2
s[-(i+1)]peut être raccourci s[-i-1]. De plus, je ne suis pas sûr, mais vous pourrez peut-être remplacer le if...else...parreturn i+1 if ... else len(s)-1
user12205
Cela a bien fonctionné ... Quelqu'un peut-il expliquer la logique derrière cela?
Arindam Roychowdhury
L'exigence est qu'il renvoie -1 si l'entrée n'est pas un palindrome avec une lettre supplémentaire. Ainsi, par exemple, si s = "abcde", il doit retourner -1.
G. Sliepen
-2

Mon premier code-golf.

Java. ~ 1200 caractères dans les fonctions principales (et secondaires). Ouais bébé.

Dessus de classe et utilisation:

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

La fonction principale:

   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;
   }

Sous-fonctions:

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

Classe complète:

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();
   }
}
aliteralmind
la source
3
Cela ne montre aucune tentative de jouer au golf avec le code.
mbomb007