Palíndromos sem prefixo

8

Escreva um programa ou função que use N e S e produz o número de palíndromos de comprimento S que você pode construir usando um alfabeto de tamanho N, de modo que qualquer prefixo de tamanho entre 2 e S-1 não seja um palíndromo.

Por exemplo, se N fosse 2 e S fossem 5

Os palíndromos válidos seriam

01110
10001

E assim a resposta seria 2

Isso é código-golfe, então as respostas serão pontuadas em bytes com base em seu comprimento, com menos bytes sendo melhores.

code-golf string combinatorics user77149
fonte
2
Bem-vindo ao PPCG! Apesar de seu formato lacônico, isso parece um desafio válido - desde que não seja um tolo nem uma pergunta escolhida em outro lugar sem permissão. No mínimo, você precisará adicionar um critério objetivo de vitória primário , como código-golfe . Eu recomendo adicionar alguns exemplos e casos de teste também.
Arnauld
@ Arnauld É possível alterar uma pergunta fora de tópico para um desafio válido (o ais523 fez isso algumas vezes), mas nesse caso, obviamente, não é o que o OP deseja. Não vai doer de qualquer maneira.
user202729
o resultado não é infinito? para N> = 2: 01111111111111111111111111..0é um palíndromo tal que qualquer prefixo não é um palíndromo
Nahuel Fouilleul
@NahuelFouilleul de comprimento S.
user202729
1
@ user77149 Se você perguntar aqui, obterá respostas como "Gelatina, 15 bytes: experimente online! " #
user202729

Respostas:

1

Pitão , 16 bytes

lf!tit_IM._T2^SE

Experimente aqui!

Minha resposta concorda com os resultados de Dennis , em vez das respostas de Haskell e Python.

Como funciona

lf! tit_IM._T2 ^ SE | Programa completo.

              SE Pegue a segunda entrada (E), faça um intervalo inteiro de 1 ... E.
             ^ | E pegue o Qº poder cartesiano, onde Q é a primeira entrada.
 f Filtre por uma condição que use T como uma variável.
         ._T | Pegue todos os prefixos de T ...
      _IM | E para cada prefixo, verifique se eles são invariantes em relação à reversão.
     t Pegue a cauda (remova o primeiro elemento).
    i 2 | Converta da base 2 para inteiro.
  ! t | Decremento, negue. Observe que entre os números inteiros, apenas 0 é falso.
eu Pegue o comprimento da lista filtrada.
Mr. Xcoder
fonte
1

Casca , 19 bytes

Lf(=1ḋ↔mS=↔‼hU¡h)πŀ

Experimente online ou veja as soluções!

Explicação

Lf(=1ḋ↔mS=↔‼hU¡h)πŀ  -- takes two arguments N S, example: 2 4
                  ŀ  -- range [0..N-1]: [0,1]
                 π   -- all strings of length S: [[[0,0,0,0],[0,0,0,1],…,[1,1,1,1]]
 f(             )    -- filter with the following predicate (example with [0,1,1,0]):
              ¡h     --   infinitely times take the head & accumulate in list: [[0,1,1,0],[0,1,1],[0,1],[0],[],[],…
             U       --   only keep longest prefix with unique elements: [[0,1,1,0],[0,1,1],[0,1],[0],[]]
           ‼h        --   get rid of last two (apply twice head): [[0,1,1,0],[0,1,1],[0,1]]
       m             --   map the following
        S=           --     is itself equal to..
          ↔          --     .. itself reversed?
                     --   ↳ [1,0,0]
      ↔              --   reverse: [0,0,1]
     ḋ               --   convert from binary: 1
   =1                --   is it equal to 1: 1
                     -- ↳ [[1,0,0,1],[0,1,1,0]]
L                    -- length: 2
ბიმო
fonte
0

Limpo , 129 bytes

import StdEnv,StdLib
?l=l==reverse l
@n s=sum[1\\p<-iter s(\a=[[e:b]\\e<-[1..n],b<-a])[[]]|and[?p:[not(?q)\\q<-inits p%(2,s-1)]]]

Experimente online!

Furioso
fonte