Linus-Sequenz generieren

14

Definition

Aus der Beschreibung zu OEIS A006345 :

a(n)Betrachten Sie zum Finden entweder a 1oder a 2. Suchen Sie für jedes das längste wiederholte Suffix, dh für jedes von a(n)=1,2, die längste Sequenz smit der Eigenschaft, mit der die Sequenz a(1),...,a(n)endet ss. Verwenden Sie die Ziffer, die das kürzere Suffix ergibt. a(1) = 1.

Ausgearbeitetes Beispiel

a(1)=1.

Wenn a(2)=1ja, haben wir die Sequenz, 1 1in der sich die längste doppelte Teilzeichenfolge vom Ende befindet 1. Wenn a(2)=2stattdessen, dann wäre es die leere Teilzeichenfolge. Deshalb a(2)=2.

Wann n=6wählen wir zwischen 1 2 1 1 2 1und 1 2 1 1 2 2. Bei der ersten Wahl 1 2 1wird vom Ende an nacheinander verdoppelt. In der zweiten Wahl ist es 2stattdessen. Daher a(6)=2.

Wann n=9wählen wir zwischen 1 2 1 1 2 2 1 2 1 und 1 2 1 1 2 2 1 2 2. In der ersten Wahl ist die längste verdoppelte aufeinanderfolgende Teilzeichenfolge 2 1, während in der zweiten Wahl 1 2 2am Ende nacheinander verdoppelt wird. Deshalb a(9)=1.

Aufgabe

Gegeben n, zurück a(n).

Technische Daten

  • n wird positiv sein.
  • Sie können 0-indiziert anstelle von 1-indiziert verwenden. In diesem Fall geben Sie dies bitte in Ihrer Antwort an. Auch in diesem Fall nkann es sich 0auch.

Testfälle

Die Testfälle sind 1-indiziert. Sie können jedoch 0-indiziert verwenden.

n  a(n)
1  1
2  2
3  1
4  1
5  2
6  2
7  1
8  2
9  1
10 1
11 2
12 1
13 2
14 2
15 1
16 1
17 2
18 1
19 1
20 1

Verweise

Undichte Nonne
quelle
1
Im Testfall von n=9hat die erste Wahl 1 2 1 1 2 2 1 2 1die doppelte Teilzeichenfolge 2 1am Ende.
Sherlock9
1
Beachten Sie, dass die verknüpfte OEIS-Seite eine Perl-Lösung mit einer Größe von ~ 43 Byte enthält.
Liori

Antworten:

7

Haskell, 146 140 137 133 118 Bytes

s!l|take l s==take l(drop l s)=l|1<2=s!(l-1)
g[w,x]|w<x=1|1<2=2
a 1=1
a n=g$(\s x->(x:s)!n)(a<$>[n-1,n-2..1])<$>[1,2]
Programm Mann
quelle
Haben Sie wirklich brauchen (\x->(\s->...? Sonst könntest du schreiben (\x s->....
Fehler
Das hilft, ein paar zu retten
Program man
Willkommen bei PPCG!
Betseg
Anstatt die normale Obergrenze zu verwenden div ..., können Sie die kürzere verwenden n. Die zusätzlichen Vergleiche geben alle false zurück und ändern das Ergebnis nicht.
Christian Sievers
ooh nett, ich schätze, ich nahm an, dass take abstürzen würde, wenn man einen zu großen Wert
Program man
6

Python, 137 Bytes

def a(n,s=[0],r=lambda l:max([0]+filter(lambda i:l[-i:]==l[-i*2:-i],range(len(l))))):
 for _ in[0]*n:s+=[r(s+[0])>r(s+[1])]
 return-~s[n]

Diese Lösung verwendet eine 0-basierte Indizierung.

Loovjo
quelle
6

Jelly , 25 24 22 20 Bytes

2 Bytes dank Dennis.

2;€µḣJf;`€$ṪLµÞḢ
Ç¡Ḣ

Probieren Sie es online!

Ein Port meiner Antwort in Pyth .

Ç¡Ḣ   Main chain

 ¡    Repeat for (input) times:
Ç         the helper chain
  Ḣ   Then take the first element



2;€µḣJf;`€$ṪLµÞḢ  Helper chain, argument: z

2;€               append z to 1 and 2, creating two possibilities
   µ         µÞ   sort the possibilities by the following:
    ḣJ                generate all prefixes from shortest to longest
       ;`€            append the prefixes to themselves
      f   $           intersect with the original set of prefixes
           Ṫ          take the last prefix in the intersection
            L         find its length
                 Ḣ   take the first (minimum)
Undichte Nonne
quelle
4

Mathematica, 84 Bytes

a@n_:=a@n=First@MinimalBy[{1,2},Array[a,n-1]~Append~#/.{___,b___,b___}:>Length@{b}&]
Alephalpha
quelle
2

MATL , 34 Bytes

vXKi:"2:"K@h'(.+)\1$'XXgn]>QhXK]0)

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Erläuterung

v             % Concatenate stack vertically: produces empty array
XK            % Copy to clipboard K. This clipboard holds the current sequence
i:            % Take input n. Generate vector [1 2 ... n]
"             % For each k in [1 2 ... n]
  2:          %   Push [1 2]. These are the possible digits for extending the sequence
  "           %     For each j in [1 2]
    K         %       Push contents of clipboard K (current sequence)
    @         %       Push j (1 or 2)
    h         %       Concatenate horizontally: gives a possible extension of sequence
    '(.+)\1$' %       String to be used as regex pattern: maximal-length repeated suffix
    XX        %       Regex match
    gn        %       Convert to vector and push its length: gives length of match
  ]           %    End. We now have the suffix lengths of the two possible extensions
  >           %    Push 1 if extension with "1" has longer suffix than with "2"; else 0 
  Q           %    Add 1: gives 2 if extension with "1" produced a longer suffix, or 1
              %    otherwise. This is the digit to be appended to the sequence
  h           %    Concatenate horizontally
  XK          %    Update clipboard with extended sequence, for the next iteration
]             % End
0)            % Get last entry (1-based modular indexing). Implicitly display
Luis Mendo
quelle
2

Python 2, 94 Bytes

import re
s='1'
exec"s+=`3-int(re.search(r'(.*)(.)\\1$',s).groups()[1])`;"*input()
print s[-1]

Verwendet eine 0-basierte Indizierung. Teste es auf Ideone .

Dennis
quelle
2

Pyth , 26 Bytes

huh.mleq#.<T/lT2._b+RGS2QY

Testsuite.

Erläuterung

Wann n = 6wählen wir zwischen 1 2 1 1 2 1und 1 2 1 1 2 2.

Wir generieren diese beiden Möglichkeiten und betrachten dann ihre Suffixe.

Für die erste, die Suffixe sind: 1, 2 1, 1 2 1, 1 1 2 1, 2 1 1 2 1, 1 2 1 1 2 1.

Wir filtern nach doppelten Suffixen, indem wir prüfen, ob sie gleich sind, nachdem wir sie für ihre Länge geteilt durch 2 gedreht haben (es stellt sich heraus, dass diese Prüfung nicht perfekt ist, weil sie bestätigt 1und 2auch).

Wir nehmen das letzte doppelte Suffix und nehmen dann seine Länge.

Wir wählen dann die Möglichkeit, die einer oben erzeugten Mindestlänge entspricht.

Dann fahren wir mit dem nächsten Wert von fort n.

Für die Zwecke dieses Programms war es Golfspieler, stattdessen das umgekehrte Array zu erzeugen.

huh.mleq#.<T/lT2._b+RGS2QY
 u                      QY   repeat Q (input) times,
                             start with Y (empty array),
                             storing the temporary result in G:
                   +RGS2         prepend 1 and 2 to G,
                                 creating two possibilities
   .m             b              find the one that
                                 makes the following minimal:
                ._                   generate all prefixes
       q#                            filter for prefixes as T
                                     that equals:
         .<T/lT2                         T left-rotated
                                         by its length halved
      e                              take the last one
     l                               generate its length
  h                              take the first minimal one
h                                take the first one from the generated
                                 array and implicitly print it out
Undichte Nonne
quelle
2

Pyth, 46 29 Bytes

Hat sich von @Leaky Nuns hervorragender Pyth-Antwort inspirieren lassen. Versucht zu sehen, ob es einen kürzeren Weg mit Strings gibt. Noch 3 Bytes zu kurz!

huh.melM+kf!x>blTT._bm+dGS2Qk

Sie können es hier ausprobieren .

Rhyzomatisch
quelle
Die Verwendung von Red uCe anstelle einer expliziten for-Schleife spart Ihnen 4 Bytes
Leaky Nun
2

Perl, 40 Bytes

$a.=/(.*)(.)\1$/^$2for($a)x$_;$_=$a%5+1

Der Code ist 39 Byte lang und erfordert den -pSchalter ( +1 Byte).

Die Schleife ist von der Perl-Lösung auf der entsprechenden OEIS-Seite inspiriert , obwohl ich mir den regulären Ausdruck unabhängig ausgedacht habe.

Teste es auf Ideone .

Dennis
quelle
Sie haben OEIS übertroffen, insbesondere Ton Hospel / Phil Carmody ...
Undichte Nonne
Nicht wirklich vergleichbar, da das OEIS-Skript keine Eingabe vornimmt und die gesamte Sequenz druckt.
Dennis
1

JavaScript (ES6), 84

Indexbasis 0

n=>eval("s='1';for(r=d=>(s+d).match(/(.*)\\1$/)[0].length;n--;s+=c)c=r(1)>r(2)?2:1")

Weniger golfen

n=>{
  r = d => (s+d).match(/(.*)\1$/)[0].length;
  c = '1';
  for(s = c; n--; s += c)
    c = r(1) > r(2) ? 2 : 1;
  return c;
}

Prüfung

F=
n=>eval("s='1';for(r=d=>(s+d).match(/(.*)\\1$/)[0].length;n--;s+=c)c=r(1)>r(2)?2:1")

for(n=0;n<20;n++)console.log(n,F(n))

edc65
quelle