Um quebra-cabeça semi-palíndromo

23

Um palíndromo é uma palavra que é seu próprio reverso.

Agora, existem algumas palavras que podem parecer palíndromos, mas não são. Por exemplo, considere a palavra sheesh, sheeshnão é um palíndromo porque seu reverso é hseehsdiferente; no entanto, se considerarmos shuma única letra, é inverso sheesh. Esse tipo de palavra chamaremos de semi-palíndromo.

Especificamente, uma palavra é um semi-palíndromo se pudermos dividir a palavra em um número de pedaços, de modo que, quando a ordem dos pedaços for revertida, a palavra original seja formada. (Para sheeshesses pedaços sh e e sh). Também não exigiremos que nenhum pedaço contenha letras de ambas as metades da palavra (caso contrário, cada palavra seria um semi-palíndromo). Por exemplo, rearnão é um semi-palíndromo porque r ea rpossui um pedaço ( ea) que contém letras de ambos os lados da palavra original. Consideramos que o caractere central em uma palavra de comprimento ímpar não está em nenhum dos lados da palavra; portanto, para palavras com comprimento ímpar, o caractere central deve sempre estar em seu próprio pedaço.

Sua tarefa será pegar uma lista de números inteiros positivos e determinar se eles são um semi-palíndromo. Seu código deve gerar dois valores desiguais consistentes, um se a entrada for um semi-palíndromo e o outro caso contrário. No entanto, a sequência de bytes do seu código deve ser um semi-palíndromo .

As respostas serão pontuadas em bytes, com menos bytes sendo melhores.

Casos de teste

[] -> True
[1] -> True
[2,1,2] -> True
[3,4,2,2,3,4] -> True
[3,5,1,3,5] -> True
[1,2,3,1] -> False
[1,2,3,3,4,1] -> False
[11,44,1,1] -> False
[1,3,2,4,1,2,3] -> False

Programa para gerar mais casos de teste.


emprestável apontou que estes são semelhantes aos palíndromos generalizados de Smarandache . Portanto, se você quiser ler mais, esse é o lugar para começar.

Assistente de Trigo
fonte
2
Por que você definiu semi-palíndromos usando cadeias, mas suas entradas são matrizes de números inteiros? Além de confuso, isso significa que não podemos testar nosso código-fonte usando nosso próprio programa.
21318 BradC
Palindromes @BradC e similares geralmente são explicados em termos de palavras, já que é um pouco mais fácil fazê-lo.
Erik the Outgolfer
As @BradC Strings tendem a apresentar casos extremos estranhos, principalmente em termos de caracteres versus bytes. Eu escolho o número porque eles são mais simples. Eu pensei que as palavras seriam mais fáceis para fins de explicação.
Assistente de trigo
2
Esses tipos de palíndromos são conhecidos como palíndromos generalizados de Smarandache na literatura.
Emprestável 16/10/19
1
@RosLuP Sim, os palíndromos "verdadeiros" também são semi-palíndromos, apenas trate cada caractere / inteiro como está, sem "chunking" adicional.
BradC

Respostas:

6

Retina 0.8.2 , 85 69 bytes

M`^(.+,)*(\d+,)?(?<-1>\1)*$(?(1)^)|M`^(.+,)*(\d+,)?(?<-1>\1)*$(?(1)^)

Experimente online! Explicação:

M`

Seleciona o modo de correspondência. De fato, o Retina usa como padrão o modo Corresponder para um programa de linha única, mas a segunda cópia do código sempre corresponderia, se não fosse por esses caracteres extras.

^

A partida deve começar do início.

(.+,)*

Capture várias execuções de caracteres. Cada execução deve terminar em vírgula.

(\d+,)?

Opcionalmente, combine uma sequência de dígitos e uma vírgula.

(?<-1>\1)*

Combine opcionalmente todas as capturas na ordem inversa, exibindo cada uma delas conforme corresponder.

$

A partida deve terminar no final.

(?(1)^)

Retroceda, a menos que todas as capturas tenham sido exibidas. Funciona exigindo que a correspondência ainda esteja no início da string, se tivermos uma captura não capturada, o que é impossível.

Neil
fonte
5

Geléia , 27 23 bytes

ṖUṁ@Ƒ€ṚẸHḢŒŒHḢŒṖUṁ@Ƒ€ṚẸ

Retorna 1 para semi-palíndromos, 0 caso contrário.

Experimente online!

Como funciona

ṖUṁ@Ƒ€ṚẸHḢŒŒHḢŒṖUṁ@Ƒ€ṚẸ  Main link. Argument: A (array)

          Œ              Invalid token. Everything to its left is ignored.
           ŒH            Halve; divide A into two halves similar lengths. The middle
                         element (if there is one) goes into the first half.
             Ḣ           Head; extract the first half.
              ŒṖ         Generate all partitions of the first half.
                U        Upend; reverse each chunk of each partition.
                         Let's call the result C.

                     Ṛ   Yield R, A reversed.
                   Ƒ€    Fixed each; for each array P in C, call the link to the left
                         with arguments P and R.
                         Return 1 if the result is P, 0 if not.
                 ṁ@          Mold swapped; replace the n integers of C, in reading
                             order, with the first n integers of R.
                     Ẹ   Exists; check if one of the calls returned 1.
Dennis
fonte
4

Python 2 , 157 153 147 147 143 bytes

-4 bytes graças ao tsh .

s=lambda x,i=0:len(x)<2or[]<x[i:]and(x[-i:]==x[:i])&s(x[i:-i])|s(x,i+1)
s=lambda x,i=0:len(x)<2or[]<x[i:]and(x[-i:]==x[:i])&s(x[i:-i])|s(x,i+1)

Experimente online!

ovs
fonte
1
Mude x==x[::-1]para len(x)<2salvar 2 * 2 bytes; 143 bytes
tsh
4

05AB1E , 59 47 43 41 bytes

2äøø€.œ`âʒ`RQ}gĀIg_^q2äøø€.œ`âʒ`RQ}gĀIg_^

-12 bytes graças a @Emigna .

Experimente online ou verifique todos os casos de teste .

Explicação:

2ä               # Split the input into two parts
                 #  i.e. [3,4,2,0,2,3,4] → [[3,4,2,0],[2,3,4]]
  øø             # Zip twice without filler
                 # This will remove the middle item for odd-length inputs
                 #  i.e. [[3,4,2,0],[2,3,4]] → [[3,2],[4,3],[2,4]] → [[3,4,2],[2,3,4]]
    €.œ          #  Then take all possible partitions for each inner list
                 #   i.e. [[3,4,2],[2,3,4]]
                 #    → [[[[3],[4],[2]],[[3],[4,2]],[[3,4],[2]],[[3,4,2]]],
                 #       [[[2],[3],[4]],[[2],[3,4]],[[2,3],[4]],[[2,3,4]]]]
`                # Push both lists of partitions to the stack
 â               # Take the cartesian product (all possible combinations) of the partitions
                 #  i.e. [[[[3],[4],[2]],[[2],[3],[4]]],
                 #        [[[3],[4],[2]],[[2],[3,4]]],
                 #        ...,
                 #        [[[3,4,2]],[[2,3,4]]]]
  ʒ   }          # Filter this list of combinations by:
   `             #  Push both parts to the stack
    RQ           #  Check if the second list reversed, is equal to the first
                 #   i.e. [[3,4],[2]] and [[2],[3,4]] → 1 (truthy)
       gĀ        # After the filter, check if there are any combinations left
                 #  i.e. [[[[3,4],[2]],[[2],[3,4]]]] → 1 (truthy)
         Ig_     # Check if the length of the input was 0 (empty input-list edge-case)
                 #  i.e. [3,4,2,0,2,3,4] → 7 → 0 (falsey)
            ^    # Bitwise-XOR
                 #  i.e. 1 XOR 0 → 1 (truthy)
             q   # Stop the program (and then implicitly output the top of the stack)
2äøø€.œ`âʒ`RQ}gĀIg_^
                 # Everything after the `q` are no-ops to comply to the challenge rules
Kevin Cruijssen
fonte
Você pode contornar o problema com listas de tamanhos ímpares com øøε.œ} `, economizando 6 bytes. Você também parecem ter deixado 30 bytes não utilizados no ...
Emigna
@Emigna os sem-ops no final são para cumprir exigência fonte restrito do desafio
Kamil Drakari
@KamilDrakari: Ah, certo. Esqueci essa parte. A boa notícia é que o 6-byte salvar será de 12 bytes então :)
Emigna
@ Emigna Muito inteligente com o truque de zip duplo. Eu não estava feliz com essa parte, mas isso é muito melhor! Aliás, como o Elixir reescreve os comandos de 2 bytes, pode ser usado com em vez de ε }. :)
Kevin Cruijssen
@KevinCruijssen: Ah legal. Eu não sabia disso.
Emigna 16/10
4

05AB1E , 37 bytes

Utiliza aproximadamente a mesma técnica que Jonathan inventou.

.œʒ€gηOZ;îå}εÂQ}ZĀqĀZ}QÂε}åî;ZOηg€ʒ.œ

Experimente online!


.œʒ€gηOZ;îå}εÂQ}ZĀqĀZ}QÂε}åî;ZOηg€ʒ.œ

Programa completo. Recebe uma lista de STDIN, gera 1 ou 0 para STDOUT.

.œʒ        }

Mantenha as partições que atendem ao filtro ...

   €gηOZ;îå

Esta condição: Os comprimentos de cada ( €g) são armazenados em uma lista, cujos prefixos ( η) são somados ( O), fornecendo, portanto, as somas cumulativas da lista de comprimentos. Em seguida, a metade do teto da lista máxima é empurrada para a pilha - mas mantendo a lista original também ( Z;î) e, se ocorrer ( å) nas somas acumuladas, a função retornará verdade.

εÂQ}

Para cada um, compare ( Q) a com um invertido, que são pressionados separadamente na pilha por Â. Retorna uma lista de 0 s e 1 s.

ZĀq

Máximo. Se algum for verdade, então mais 1 será 0 . Finalize a execução. Tudo o que se segue é completamente ignorado.

Mr. Xcoder
fonte
3

Python 2 , 275 251 205 bytes

-24 bytes graças a @KevinCruijssen

-44 bytes graças a @PostLeftGhostHunter

-2 bytes adicionais graças a @KevinCruijssen

def s(x):
 l=len(x)
 if l<2:return 1>0
 for i in range(1,l/2+1):
	if x[l-i:]==x[:i]:return s(x[i:l-i])
def s(x):
 l=len(x)
 if l<2:return 1>0
 for i in range(1,l/2+1):
	if x[l-i:]==x[:i]:return s(x[i:l-i])

Retorna Verdadeiro para semi-palíndromo, Nenhum caso contrário

Experimente online!

Cowabunghole
fonte
1
Ou apenas retorne 1
Jo King
Por que s (x) definido duas vezes?
Dr. Y Wit
Porque eles dizem contar como palíndromo ... mas é possível definir uma função com o mesmo nome ???
RosLuP 27/10/19
@RosLuP Sim, você pode. O segundo substitui o primeiro
Jo King
3

Geléia ,  33  32 bytes

-1 Agradecimentos a Erik, o Outgolfer
Agradecemos também a Dennis por uma correção de bug e procurando alterar os detalhes de implementação no Jelly.

ẸƇŒḂƇƊ$ƊĊHṀċÄẈṖŒŒṖẈÄċṀHĊƊ$ƊƇŒḂƇẸ

Rendimento de semi-palíndromos 1, outros 0.

O(2n)

Ou veja a suíte de testes .

Os únicos pedaços são os ŒḂs ({3 ° e 4 ° } vs {29 ° e 30 ° } bytes), apenas para permitir a análise do código.

Quão?

Todo o trabalho é realizado pelo lado direito - o "Link principal":

ŒṖẈÄċṀHĊƊ$ƊƇŒḂƇẸ - Main Link: list
ŒṖ               - all partitions
           Ƈ     - filter keep those for which this is truthy (i.e. non-zero):
          Ɗ      -   last three links as a monad:
  Ẉ              -     length of each
         $       -     last two links as a monad:
   Ä             -       cumulative addition
        Ɗ        -       last three links as a monad:
     Ṁ           -         maximum
      H          -         halve
       Ċ         -         ceiling
    ċ            -     count
              Ƈ  - filter keep those for which this is truthy:
            ŒḂ   -   is palindrome?
               Ẹ - any?
Jonathan Allan
fonte
3

Perl 6 , 87 79 bytes

-8 bytes com alguns truques da resposta de Jo King

$!={/\s/&&/^(.+)\s[(.+)\s]*$0$/&&$1.$!}#$!={/\s/&&/^(.+)\s[(.+)\s]*$0$/&&$1.$!}

Experimente online!

Resposta JavaScript do Port of tsh. Retorna dois objetos Regex diferentes.

Nwellnhof
fonte
2

Ruby , 129 bytes

f=->l{!l[1]||(1...l.size).any?{|x|l[0,x]==l[-x,x]&&f[l[x..~x]]}}#f=->l{!l[1]||(1...l.size).any?{|x|l[0,x]==l[-x,x]&&f[l[x..~x]]}}

Experimente online!

GB
fonte
1

JavaScript (Node.js) , 139 bytes

f=a=>(s=(''+a).replace(/^(.*),((.*),)?\1$/,'$3'))!=a?f(s):/,/.test(s)//^(.*),((.*),)?\1$/,'$3'))!=a?f(s):/,/.test(s)f=a=>(s=(''+a).replace(

Experimente online!

tsh
fonte
1

C (gcc) (X86), 216 bytes

p(L,a,n)int*a;{return n?(memcmp(a,a+L-n,n*4)|p(L-2*n,a+n,L/2-n))&&p(L,a,n-1):1<L;}
#define p(L,a)p(L,a,L/2)//p(L,a,n)int*a;{return n?(memcmp(a,a+L-n,n*4)|p(L-2*n,a+n,L/2-n))&&p(L,a,n-1):1<L;}
#define p(L,a)p(L,a,L/2)

Experimente online!

p(L,a,n)retorna 0 se a matriz ade comprimento Lfor um semi-palíndromo, 1 caso contrário. Dado que todos os prefixos de comprimento >njá estão marcados, ele compara o prefixo de comprimento ncom o sufixo de comprimento n. p(L,a)é o ponto de entrada.

Infelizmente, a solução mais interessante é mais longa:

224 bytes

(f(L,a,n))//#define p(L,a)(n=L/2,
int*a,n;
{return n?(memcmp(a,a+L-n,n*4)|f(L-2*n,a+n,L/2-n))&&f(L,a,n-1):1<L;}//{return n?(memcmp(a,a+L-n,n*4)|f(L-2*n,a+n,L/2-n))&&f(L,a,n-1):1<L;}
int*a,n;
#define p(L,a)(n=L/2,f(L,a,n))//(

Experimente online!

Ungolfed:

(f(L,a,n)) //#define p(L,a)(n=L/2,
int*a,n;
{
  return n 
    ? (memcmp(a, a+L-n, n*4) | f(L-2*n, a+n, L/2-n)) &&
      f(L,a,n-1)
    : 1 < L;
} // { ... } 
int*a,n;
#define p(L,a)(n=L/2,f(L,a,n)) //(
eush77
fonte
1

Japonês , 66 bytes


@¯X eUsXn}a1 "
ʧV?UÊ<2:ßUéV sVÑ
@¯X eUsXn}a1 "
ʧV?UÊ<2:ßUéV sVÑ

Intérprete Japt

Grande melhoria nesta versão, atualmente supera a maioria das linguagens práticas. Agora opera em uma matriz de números inteiros, já que o método anterior teve um bug.

Explicação:

@        }a1         Find the first number n > 0 such that...
 ¯X                   the first n elements
     UsXn             and the last n elements
    e                 are the same

"
ʧV?UÊ<2:ßUéV sVÑ    String literal to make it a Semi-palindrome
@¯X eUsXn}a1 "

ʧV?                 If n >= length of input...
    UÊ<2              return true if the length is less than 2
        :            Otherwise...
          UéV         move n elements from the end of the input to the start
              sVÑ     remove the first 2*n elements
         ß            and repeat on the remaining elements
Kamil Drakari
fonte
0

PHP 237 bytes

function f($a){for($x=2>$c=count($a);++$i<=$c/2;)$x|=($s=array_slice)($a,0,$i)==$s($a,-$i)&f($s($a,$i,-$i));return$x;}#function f($a){for($x=2>$c=count($a);++$i<=$c/2;)$x|=($s=array_slice)($a,0,$i)==$s($a,-$i)&f($s($a,$i,-$i));return$x;}

função recursiva, retorna true(para entrada contendo menos de dois elementos) ou 1para verdade,
0para falsidade. Experimente online (contém informações detalhadas).

O comprimento real do código é 118 bytes; semi-palíndromo criado via duplicação de código.

Para um melhor desempenho, substitua &por &&e insira !$x&&antes ++$i.

Titus
fonte
0

Scala, 252 bytes

def^(s:Seq[Int]):Int={val l=s.size;if(l>1)(1 to l/2).map(i=>if(s.take(i)==s.takeRight(i))^(s.slice(i,l-i))else 0).max else 1}//def^(s:Seq[Int]):Int={val l=s.size;if(l>1)(1 to l/2).map(i=>if(s.take(i)==s.takeRight(i))^(s.slice(i,l-i))else 0).max else 1}

Experimente online!

PS. Aparentemente, a solução é duas vezes mais longa apenas para satisfazer um requisito de que o código-fonte também seja semi-palíndromo.

PPS. Não é um candidato a código-golfe, mas uma solução puramente funcional usando a correspondência de padrões:

  def f(s:Seq[Int], i:Int=1):Int = {
    (s, i) match {
      case (Nil ,_) => 1
      case (Seq(_), _) => 1
      case (l, _) if l.take(i) == l.takeRight(i) => f(l.slice(i,l.size-i), 1)
      case (l, j) if j < l.size/2 => f(l, i+1)
      case (_, _) => 0
    }
  }
Dr. Y Wit
fonte
O desafio exige que seu código também seja um semi-palíndromo. Essa é a maior diversão do desafio.
Assistente de trigo 26/10
@PostLeftGhostHunter, adicionei o código-fonte original ao comentário para atender ao requisito. BTW, qual é a graça de tornar o código-fonte semi-palíndromo? Se não estiver errado, todas as soluções neste segmento serão duas vezes mais curtas sem esse requisito. Você está ciente de alguma solução que não seja assim?
Dr Y Wit
0

Perl 6 , 81 bytes

($!={/../&&/^(.+)(.*)$0$/&&$1.$!})o&chrs#($!={/../&&/^(.+)(.*)$0$/&&$1.$!})o&chrs

Experimente online!

Retorna a regex /../para True e a regex /^(.+)(.*)$0$/para False. Funciona de maneira semelhante à resposta de nwellnhof , mas converte a lista em uma sequência de antemão.

Brincadeira
fonte