Präfixlose Palindrome

8

Schreiben Sie ein Programm oder eine Funktion, die N und S verwendet und die Anzahl der Palindrome der Länge S ausgibt, die Sie mit einem Alphabet der Größe N erstellen können, sodass ein Präfix der Größe zwischen 2 und S-1 kein Palindrom ist.

Zum Beispiel , wenn N waren 2 und S waren 5

Die gültigen Palindrome wären

01110
10001

Und damit wäre die Antwort 2

Dies ist Code-Golf, daher werden Antworten in Bytes basierend auf ihrer Länge bewertet, wobei weniger Bytes besser sind.

code-golf string combinatorics user77149
quelle
2
Willkommen bei PPCG! Trotz seines lakonischen Formats scheint dies eine gültige Herausforderung zu sein - vorausgesetzt, es handelt sich weder um einen Betrüger noch um eine Frage, die ohne Erlaubnis an einer anderen Stelle gestellt wurde. Zumindest müssten Sie ein objektives primäres Gewinnkriterium wie Code-Golf hinzufügen . Ich würde empfehlen, auch einige Beispiele und Testfälle hinzuzufügen.
Arnauld
@Arnauld Es ist uns möglich, eine Off-Topic-Frage in eine gültige Herausforderung umzuwandeln (ais523 hat dies einige Male getan), aber in diesem Fall ist es offensichtlich nicht das, was das OP will. Es wird sowieso nicht weh tun.
user202729
Das Ergebnis ist nicht unendlich? für N> = 2: 01111111111111111111111111..0ist ein Palindrom, so dass jedes Präfix kein Palindrom ist
Nahuel Fouilleul
@NahuelFouilleul der Länge S.
user202729
1
@ user77149 Wenn Sie es hier fragen, erhalten Sie Antworten wie "Gelee, 15 Bytes: Versuchen Sie es online! "
user202729

Antworten:

1

Pyth , 16 Bytes

lf!tit_IM._T2^SE

Probieren Sie es hier aus!

Meine Antwort stimmt eher mit Dennis 'Ergebnissen überein als mit den Antworten von Haskell und Python.

Wie es funktioniert

lf! tit_IM._T2 ^ SE | Volles Programm.

              SE | Nimm den zweiten Eingang (E) und mache einen ganzzahligen Bereich von 1 ... E.
             ^ | Und nimm die Q-te kartesische Kraft, wobei Q die erste Eingabe ist.
 f | Filtern Sie nach einer Bedingung, die T als Variable verwendet.
         ._T | Nehmen Sie alle Präfixe von T ...
      _IM | Überprüfen Sie für jedes Präfix, ob sie bei der Umkehrung unveränderlich sind.
     t | Nimm den Schwanz (entferne das erste Element).
    i 2 | Konvertieren Sie von Basis 2 in Ganzzahl.
  ! t | Dekrementieren, negieren. Beachten Sie, dass unter den ganzen Zahlen nur 0 falsch ist.
l | Nehmen Sie die Länge der gefilterten Liste.
Mr. Xcoder
quelle
1

Schale , 19 Bytes

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

Probieren Sie es online aus oder sehen Sie sich die Lösungen an!

Erläuterung

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
ბიმო
quelle
0

Sauber , 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)]]]

Probieren Sie es online aus!

Οurous
quelle