14
\$\begingroup\$

Definition

From the description on OEIS A006345:

To find a(n), consider either a 1 or a 2. For each, find the longest repeated suffix, that is, for each of a(n)=1,2, find the longest sequence s with the property that the sequence a(1),...,a(n) ends with ss. Use the digit that results in the shorter such suffix. a(1) = 1.

Worked-out Example

a(1)=1.

If a(2)=1, we will have the sequence 1 1 where the longest doubled substring from the end is 1. If a(2)=2 instead, then it would be the empty substring. Therefore a(2)=2.

When n=6, we choose between 1 2 1 1 2 1 and 1 2 1 1 2 2. In the first choice, 1 2 1 is doubled consecutively from the end. In the second choice, it is 2 instead. Therefore, a(6)=2.

When n=9, we choose between 1 2 1 1 2 2 1 2 1 and 1 2 1 1 2 2 1 2 2. In the first choice, the longest doubled consecutive substring is 2 1, while in the second choice 1 2 2 is doubled consecutively at the end. Therefore a(9)=1.

Task

Given n, return a(n).

Specs

  • n will be positive.
  • You can use 0-indexed instead of 1-indexed. In that case, please state so in your answer. Also, in that case, n can be 0 also.

Testcases

The testcases are 1-indexed. However, you can use 0-indexed.

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

References

\$\endgroup\$
2
  • 1
    \$\begingroup\$ In the test case of n=9, the first choice 1 2 1 1 2 2 1 2 1 has the doubled substring 2 1 at the end. \$\endgroup\$ – Sherlock9 Aug 1 '16 at 19:02
  • 1
    \$\begingroup\$ Note that the linked OEIS page has a golfed Perl solution of ~43 bytes. \$\endgroup\$ – liori Aug 2 '16 at 1:21

13 Answers 13

7
\$\begingroup\$

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]
\$\endgroup\$
5
  • \$\begingroup\$ Do you really need (\x->(\s->...? Otherwise you could write (\x s->.... \$\endgroup\$ – flawr Aug 1 '16 at 20:53
  • \$\begingroup\$ That helps to save a few \$\endgroup\$ – Program man Aug 1 '16 at 22:09
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – betseg Aug 1 '16 at 22:12
  • \$\begingroup\$ Instead of using the sane upper bound div ..., you can use the shorter n. The extra comparisons will all return false and not change the result. \$\endgroup\$ – Christian Sievers Aug 1 '16 at 22:57
  • \$\begingroup\$ ooh nice, I guess I assumed take would crash if given too large a value \$\endgroup\$ – Program man Aug 1 '16 at 23:10
6
\$\begingroup\$

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]

This solution is using 0-based indexing.

\$\endgroup\$
6
\$\begingroup\$

Jelly, 25 24 22 20 bytes

2 bytes thanks to Dennis.

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

Try it online!

A port of my answer 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)
\$\endgroup\$
4
\$\begingroup\$

Mathematica, 84 bytes

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

Jelly, 30 29 28 27 24 bytes

;€¬;\€Z;/f;`€$ṪḢ;
1Ç¡o2Ḣ

Try it online! or verify all test cases.

\$\endgroup\$
2
\$\begingroup\$

MATL, 34 bytes

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

Try it online! or verify all test cases.

Explanation

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
\$\endgroup\$
2
\$\begingroup\$

Python 2, 94 bytes

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

Uses 0-based indexing. Test it on Ideone.

\$\endgroup\$
2
\$\begingroup\$

Pyth, 26 bytes

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

Test suite.

Explanation

When n = 6, we choose between 1 2 1 1 2 1 and 1 2 1 1 2 2.

We generate these two possibilities, and then look at their suffixes.

For the first one, the suffixes are: 1, 2 1, 1 2 1, 1 1 2 1, 2 1 1 2 1, 1 2 1 1 2 1.

We filter for doubled suffixes by checking if they are the same after rotating them for their length divided by 2 (it turns out that this check is not perfect, because it confirms 1 and 2 also).

We take the last doubled suffix and then take its length.

We then choose the possibility that corresponds to a minimum length generated above.

Then we proceed to the next value of n.

For the purpose of this program, it was golfier to generate the reversed array instead.

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
\$\endgroup\$
2
\$\begingroup\$

Pyth, 46 29 bytes

Took some inspiration from @Leaky Nun's excellent Pyth answer. Tried to see if there was a shorter way using strings. Still 3 bytes short!

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

You can try it out here.

\$\endgroup\$
1
2
\$\begingroup\$

Retina, 51 42 bytes

9 bytes thanks to Martin Ender.

.+
$*x
+`((.*)(^|2|(?<3>1))\2)x
$1$#3
!`.$

Try it online!

A port of this answer.

\$\endgroup\$
2
\$\begingroup\$

Perl, 40 bytes

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

The code is 39 bytes long and requires the -p switch (+1 byte).

The loop is inspired by the Perl solution on the relevant OEIS page, although I did come up independently with the regular expression.

Test it on Ideone.

\$\endgroup\$
2
  • \$\begingroup\$ You have outgolfed OEIS, specifically, Ton Hospel/Phil Carmody... \$\endgroup\$ – Leaky Nun Aug 2 '16 at 4:36
  • \$\begingroup\$ Not really comparable since the OEIS script takes no input and prints the whole sequence. \$\endgroup\$ – Dennis Aug 2 '16 at 4:39
1
\$\begingroup\$

JavaScript (ES6), 84

Index base 0

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

Less golfed

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

Test

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

\$\endgroup\$
0
\$\begingroup\$

Husk, 20 bytes

!¡λ◄(L←SnmDṫ:⁰)ḣ2);1

Try it online! or Verify first 20 values

Same algorithm as Leaky Nun's answers.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.