16
\$\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\$
7
  • \$\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\$
    – Grain Ghost
    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\$
    – user41805
    Aug 7 '17 at 16:46
  • \$\begingroup\$ I suggest allowing undefined behaviour for invalid inputs. \$\endgroup\$
    – Mr. Xcoder
    Aug 7 '17 at 16:46

14 Answers 14

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\$
3
  • \$\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\$ 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\$ 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\$
8
  • 2
    \$\begingroup\$ Ninja'd :D 65 bytes \$\endgroup\$ 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\$ 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\$ 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\$
0
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\$
2
  • \$\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\$
2
\$\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\$
2
\$\begingroup\$

Husk, 17 15 bytes

£moiṁsṁṠehGJC2N

Try it online!

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

-2 bytes from Leo, GJ!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice, particularly the z*İ_ trick to reverse alternate elements. 15 bytes by using string input... \$\endgroup\$ Mar 16 at 11:35
  • \$\begingroup\$ String input doesn't really work because values are not lexicographically ordered: Try it online! \$\endgroup\$
    – Leo
    Mar 17 at 0:42
  • \$\begingroup\$ There is a shorter way by scanning with J, though: Try it online! \$\endgroup\$
    – Leo
    Mar 17 at 4:05
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\$
5
  • \$\begingroup\$ How long would it take to compute 211917151311975312468101214161820? \$\endgroup\$
    – Okx
    Aug 7 '17 at 17:01
  • \$\begingroup\$ A long, long time :p \$\endgroup\$ 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\$ Aug 7 '17 at 17:24
  • \$\begingroup\$ @JonathanAllan Technically you call that :p \$\endgroup\$ 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\$
1
  • \$\begingroup\$ @BruceForte I actually managed to save 30 thanks to your suggestion. \$\endgroup\$
    – Grain Ghost
    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\$

Japt, 17 bytes

@P=PiXv n X;¥P}a1

Try it online! or check (valid) test cases

Takes input as a string or integer. On invalid input, continues "forever" looking for a solution (thus why I didn't include them in the test cases).

Explanation:

@P=PiXv n X;¥P}a1    
                     # Implicitly start with P = ""
@             }a1    # Repeat the function for each integer X > 0 until one returns true
 P=Pi     X          #  Insert X into P at index:
     Xv              #   X is divisible by 2?
        n            #   Times -1
           ;¥P       #  Return whether P now equals the input
                     # Implicitly output the last value of X

The "insert at index" portion might be a bit confusing, so I'll add more detail here. In Japt, NvD is a function which returns 1 if N is divisible by D, and 0 otherwise. If D is not provided, it defaults to 2. Thus Xv here is equal to 1 if X is even, and 0 if X is odd. NnD is a function that returns D - N. If D is not provided it defaults to 0, effectively returning -N. In this program, that results in -1 if X is even, and still 0 if X is odd. Finally, in Japt indexing negative numbers count from the end of a string or array. Thus the segment PiXv n X evaluates to Pi0 X if X is odd, prepending X, but it evaluates to Pi-1 X if X is even, appending it instead.

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