14
\$\begingroup\$

Task

The prepend,append-Sequence is defined recursively, like this

  • a(1) = 1
  • a(n) = a(n-1).n , if n is even
  • a(n) = n.a(n-1) , if n is odd

where the . represents an integer concatenation.

So the first few terms are: 1,12,312,3124,53124,531246,7531246,... This is A053064.

Your task is, given an integer a > 0 to return n, such that the nth element in the prepend,append-Sequence is equal to a and if no such n exists return 0, a negative number or error out etc.

Rules

  • Input can be taken as an integer, string, list of characters/digits etc.
  • Output can be printed to STDOUT or returned (integer, string etc. is fine)
  • On invalid input & in the case no such n exists your program may do anything but return a positive integer (eg. loop forever, return 0 etc.)
  • You may choose to use 0-indexing, but then the output in case no n exists cannot be 0

Test cases

1 -> 1
12 -> 2
21 -> 0
123 -> 0
312 -> 3
213 -> 0
211917151311975312468101214161820 -> 21
2119171513119753102468101214161820 -> 0
333129272523211917151311975312468101214161820222426283031 -> 0
999795939189878583817977757371696765636159575553514947454341393735333129272523211917151311975312468101214161820222426283032343638404244464850525456586062646668707274767880828486889092949698100 -> 100
\$\endgroup\$
  • \$\begingroup\$ More formal: a(n-1)*(int(log(n))+1)+n and n*(int(log(n))+1)+a(n-1)? \$\endgroup\$ – Mr. Xcoder Aug 7 '17 at 16:19
  • 1
    \$\begingroup\$ @Mr.Xcoder I would call that less formal :P \$\endgroup\$ – Sriotchilism O'Zaic Aug 7 '17 at 16:20
  • \$\begingroup\$ @JonathanAllan That is already in the question for ~10 minutes. \$\endgroup\$ – Mr. Xcoder Aug 7 '17 at 16:27
  • 2
    \$\begingroup\$ I suggest allowing errors for invalid inputs. \$\endgroup\$ – Cows quack Aug 7 '17 at 16:46
  • \$\begingroup\$ I suggest allowing undefined behaviour for invalid inputs. \$\endgroup\$ – Mr. Xcoder Aug 7 '17 at 16:46

12 Answers 12

6
\$\begingroup\$

JavaScript (ES6), 40 bytes

Takes input as a string. Throws a recursion error if no index is found.

f=(n,s=k='1')=>n==s?k:f(n,++k&1?k+s:s+k)

Demo

f=(n,s=k='1')=>n==s?k:f(n,++k&1?k+s:s+k)

console.log(f('1')) // 1
console.log(f('12')) // 2
console.log(f('312')) // 3
console.log(f('211917151311975312468101214161820')) // 21
console.log(f('999795939189878583817977757371696765636159575553514947454341393735333129272523211917151311975312468101214161820222426283032343638404244464850525456586062646668707274767880828486889092949698100')) // 100

\$\endgroup\$
  • \$\begingroup\$ I think you can save a byte with this: f=(n,s=k='1')=>n-s?f(n,++k&1?k+s:s+k):k \$\endgroup\$ – Rick Hitchcock Aug 7 '17 at 21:56
  • \$\begingroup\$ @RickHitchcock Unfortunately, that would force Number comparisons and introduce false positives on large inputs caused by the loss of precision. \$\endgroup\$ – Arnauld Aug 7 '17 at 22:11
  • \$\begingroup\$ Gotcha. It works on the test cases but was unsure how it would handle other situations. \$\endgroup\$ – Rick Hitchcock Aug 7 '17 at 22:12
6
\$\begingroup\$

C# (.NET Core), 83, 80, 60 59 bytes

n=>{int i=0;for(var t="";t!=n;)t=++i%2<1?t+i:i+t;return i;}

Try it online!

Takes the input as a string into a lambda function. 1-indexed. Returns the index of the value for truthy, or infitnitely loops for a "falsey"

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

Python 2, 63 bytes

-1 byte thanks to @EriktheOutgolfer.

f=lambda x,i='1',j=2:i!=`x`and f(x,[i+`j`,`j`+i][j%2],j+1)or~-j

Try it online!

Python 2, 64 bytes

-18 bytes thanks to @officialaimm, because I didn't notice erroring out was allowed!

x,i,j=input(),'1',1
while i!=x:j+=1;i=[i+`j`,`j`+i][j%2]
print j

Try it online!

Python 2, 82 bytes (does not loop forever)

This one returns 0 for invalid inputs.

def f(n,t="",i=1):
 while len(t)<len(n):t=[t+`i`,`i`+t][i%2];i+=1
 print(n==t)*~-i

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Ninja'd :D 65 bytes \$\endgroup\$ – officialaimm Aug 7 '17 at 17:02
  • \$\begingroup\$ @officialaimm Thanks a lot! I didn't notice erroring out / loop forever was allowed. \$\endgroup\$ – Mr. Xcoder Aug 7 '17 at 17:05
  • \$\begingroup\$ Save a byte with a lambda: f=lambda x,i='1',j=2:i!=`x`and f(x,[i+`j`,`j`+i][j%2],j+1)or~-j \$\endgroup\$ – Erik the Outgolfer Aug 7 '17 at 18:17
  • \$\begingroup\$ @EriktheOutgolfer Wait, it throws recursion error for everything, although I set sys.setrecursionlimit(). Can you provide a tio? \$\endgroup\$ – Mr. Xcoder Aug 7 '17 at 18:20
  • \$\begingroup\$ @Mr.Xcoder Does it throw an error for x=1? Or x=12? I thought it only threw such an error for at least x=151311975312468101214 or something. \$\endgroup\$ – Erik the Outgolfer Aug 7 '17 at 18:24
3
\$\begingroup\$

Jelly, 12 bytes

Rs2ZU1¦ẎVµ€i

Try it online!

Explanation:

Rs2ZU1¦ẎVµ€i
         µ€  Eval this link for each (automatic [1..n] range)
R             Range
 s2           Split in pieces of: 2
   Z          Zip
    U1¦       Only keep index: 1 of: Vectorized reverse
       Ẏ      Flatten 1-deep
        V     Concatenate string versions and eval
           i Find index of y in x (y = implicit input)
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 14 bytes

$vDNÌNFs}«})Ik

Try it online! or as a Test suite

Explanation

0-indexed.
Returns -1 if the input is not in the sequence.

$                 # push 1 and input
 v                # for each y,N (element, index) in input do:
  D               # duplicate top of stack
   NÌ             # push N+2
     NF }         # N times do:
       s          # swap the top 2 elements on the stack
         «        # concatenate the top 2 elements on the stack
          })      # end loop and wrap in a list
            Ik    # get the index of the input in this list
\$\endgroup\$
  • \$\begingroup\$ Haha, this is basically my solution with the g removed and the append/prepend thing shortened. I'll delete my answer \$\endgroup\$ – Okx Aug 7 '17 at 17:26
  • \$\begingroup\$ @Okx: Oh yeah, I see you golfed yours down to almost exactly this only minutes after my post. Great minds ;) \$\endgroup\$ – Emigna Aug 7 '17 at 17:34
2
\$\begingroup\$

R, 73 bytes

p=paste0;n=scan(,'');l='';while(l!=n){F=F+1;l="if"(F%%2,p(F,l),p(l,F))};F

Reads from stdin and returns the value of the index (implicitly printed). Infinite loops when the value isn't in the sequence. F is by default FALSE which is cast to 0 when used in arithmetic.

Try it online!

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

Mathematica, 135 bytes

s=t={};x=1;While[x<5!,{s~AppendTo~#&,s~PrependTo~#&}[[x~Mod~2+1]]@x;AppendTo[t,FromDigits@Flatten[IntegerDigits/@s]];x++];t~Position~#&
\$\endgroup\$
1
\$\begingroup\$

Jelly,  19 18  15 bytes

+ḂḶṚm2;RḤ$ṁµ€Vi

A monadic link taking and returning integers.

Try it online! (very slow - takes ~50s on TIO just to confirm that 3124 is at index 4)

For a much faster version use the previous 18 byter (only checks up to the length of the input, which is sufficient).

How?

+ḂḶṚm2;RḤ$ṁµ€Vi - Link: number, v
           µ€   - perform the monadic link to the left for €ach k in [1,2,3,...v]
                -                 (v can be big, lots of k values makes it slow!)
 Ḃ              -   modulo k by 2  = 1 if odd 0 if even
+               -   add to k = k+isOdd(k)
  Ḷ             -   lowered range = [0,1,2,...,k+isOdd(k)]
   Ṛ            -   reverse = [k+isOdd(k),...,2,1,0])
    m2          -   modulo slice by 2 = [k+isOdd(k),k+isOdd(k)-2,...,3,1]
         $      - last two links as a monad:
       R        -   range(k) = [1,2,3,...,k]
        Ḥ       -   double = [2,4,6,...,2k]
     ;          - concatenate = [k+isOdd(k),k+isOdd(k)-2,...,3,1,2,4,6,...,2k]
         ṁ      - mould like range(k) = [k+isOdd(k),k+isOdd(k)-2,...,3,1,2,4,6,...,k-isOdd(k)]
                -   (this is a list of the integers to be concatenated for index k)
             V  - evaluate as Jelly code (yields a list of the concatenated integers)
              i - first index of v in that (or 0 if not found)
\$\endgroup\$
  • \$\begingroup\$ How long would it take to compute 211917151311975312468101214161820? \$\endgroup\$ – Okx Aug 7 '17 at 17:01
  • \$\begingroup\$ A long, long time :p \$\endgroup\$ – Jonathan Allan Aug 7 '17 at 17:21
  • \$\begingroup\$ Yes, but how long? \$\endgroup\$ – Okx Aug 7 '17 at 17:22
  • \$\begingroup\$ Well looks like it's order v squared where v is the input integer. \$\endgroup\$ – Jonathan Allan Aug 7 '17 at 17:24
  • \$\begingroup\$ @JonathanAllan Technically you call that :p \$\endgroup\$ – Erik the Outgolfer Aug 7 '17 at 17:34
1
\$\begingroup\$

Swift 4, 92 bytes

This loops infinitely for invalid cases, so I didn't include them in the testing link.

func f(x:String){var i="1",j=1;while i != x{j+=1;i=[i+String(j),String(j)+i][j%2]};print(j)}

Test Suite.

Amusingly, it is longer with a closure:

var f:(String)->Int={var i="1",j=1;while i != $0{j+=1;i=[i+String(j),String(j)+i][j%2]};return j}

Test Suite.

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

Haskell, 115 85 bytes

s=read.(show=<<)
f 1=1
f x|odd x=s[x,f$x-1]
f x=s[f$x-1,x]
g x=[n|n<-[1..],x==f n]!!0

Try it online!

\$\endgroup\$
  • \$\begingroup\$ @BruceForte I actually managed to save 30 thanks to your suggestion. \$\endgroup\$ – Sriotchilism O'Zaic Aug 7 '17 at 18:54
1
\$\begingroup\$

Perl 5, 54 + 1 (-n) = 55 bytes

$a=++$,%2?$,.$a:$a.$,while length$a<length;say/$a/&&$,

Try it online!

Returns nothing if not found.

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

Haskell, 75 71 57 bytes

f n=[i|i<-[1..],(show=<<reverse[1,3..i]++[2,4..i])==n]!!0

Takes n as a string.

Try it online!

\$\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.