34
\$\begingroup\$

It is fairly simple to, given a number n, create a range from 0 to n-1. In fact, many languages provide this operation as a builtin.

The following CJam program reads an integer, and then prints out such a range (Try it online!):

ri,

Notice that it prints out numbers without a separator.

The Challenge

Your task is to reverse this process. You should write a program that, given a string representing a range, returns the number used to produce that range.

Specifications

  • The numbers are given without any separator.
  • You may assume the string forms a valid range.
  • You may use 0- or 1-based indexing for your range.
  • You may assume that a correct output will never exceed 32,767 (so a valid input will never have a length greater than 152,725).
  • You may assume that a correct output will always be positive (so you do not have to handle 0 or negative).

This is , so the shortest competing answer (measured in bytes) wins.

Test Cases

0-indexed:

0123 -> 4
0 -> 1
0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100 -> 101

1-indexed:

1234 -> 4
1 -> 1
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100 -> 100
\$\endgroup\$
  • \$\begingroup\$ Are there any descending ranges? Does it need to work for negative numbers? \$\endgroup\$ – Daniel Aug 21 '17 at 8:37
  • \$\begingroup\$ @Daniel No. Forgot to mention that; added. \$\endgroup\$ – Esolanging Fruit Aug 21 '17 at 8:41
  • 4
    \$\begingroup\$ Do our programs really need to handle the empty string? I think it would be reasonable to allow us to ignore that. Some answers do not benefit from that rule at all. \$\endgroup\$ – Mr. Xcoder Aug 21 '17 at 9:34
  • \$\begingroup\$ Can the output be a string representation of the number i.e. taken as a substring from the original string? \$\endgroup\$ – user2390246 Aug 21 '17 at 10:04
  • \$\begingroup\$ @user2390246 Yes, that's fine. \$\endgroup\$ – Esolanging Fruit Aug 21 '17 at 18:11

35 Answers 35

11
\$\begingroup\$

Prolog (SWI), 91 80 bytes

0-indexed.

X*L:-atom_length(X,L),
     between(0,L,Y),
     numlist(0,Y,B),
     atomic_list_concat(B,X)
     ;L=0.

Newlines added for readability.

Try it online!

\$\endgroup\$
11
\$\begingroup\$

Husk, 5 bytes

LCmLN

Try it online!

Only letters!

Takes input as a string, result is 1-indexed.

Explanation

LCmLN
  mLN    get the list of lengths of all positive naturals
 C       cut the input into slices of those lengths
L        get the length of the resulting list
\$\endgroup\$
8
\$\begingroup\$

05AB1E, 7 6 bytes

1-indexed.

āηJsk>

Try it online! or as a Test Suite

Explanation

ā        # push range [1 ... len(input)]
 η       # compute prefixes of the range
  J      # join each prefix to a string
   sk    # get index of the input in the list of prefixes
     >   # increment
\$\endgroup\$
  • \$\begingroup\$ Am I doing something wrong? This seems to return 0 no matter the input: tio.run/##MzBNTDJM/f8/3efcdi/PbLv//5UMjYxNTM3MLSwNDZQA \$\endgroup\$ – Shaggy Aug 21 '17 at 9:25
  • \$\begingroup\$ @Shaggy: You have to do it like this or this as single quotes count as part of the input. \$\endgroup\$ – Emigna Aug 21 '17 at 9:26
  • \$\begingroup\$ Ah, so string inputs in 05AB1E need to be triple quoted? \$\endgroup\$ – Shaggy Aug 21 '17 at 9:26
  • \$\begingroup\$ @Shaggy: If you want the empty string or newlines in the input yes. Otherwise you don't need to quote it at all. \$\endgroup\$ – Emigna Aug 21 '17 at 9:27
  • \$\begingroup\$ [NÝJQ#]N was my idea, but this is better because it works for "". \$\endgroup\$ – Magic Octopus Urn Aug 21 '17 at 17:54
7
\$\begingroup\$

Java 8, 66 59 bytes

s->{int r=0;for(String c="";!c.equals(s);c+=r++);return r;}

0-indexed

-7 bytes thanks to @PunPun1000.

I have the feeling this can be shortened by only checking the length of the input somehow, since we can assume the input is always valid. Still figuring this out. Unable to figure this out, and it will probably cost too many bytes in Java to be useful anyway (same applies to returning a substring of the end of a 1-indexed input).

Explanation:

Try it here.

s->{                 // Method with String parameter and integer return-type
  int r=0;           //  Result-integer
  for(String c="";   //  Check-String
      !c.equals(s);  //  Loop as long as the sum-String doesn't equal the input-String
    c+=r++           //   Append the number to the the Check-String,
                     //   and increase the Result-integer by 1
  );                 //  End of loop
  return r;          //  Return the result-integer
}                    // End of method
\$\endgroup\$
  • 1
    \$\begingroup\$ 59 bytes: TIO \$\endgroup\$ – PunPun1000 Aug 21 '17 at 13:42
  • \$\begingroup\$ There's probably some absurd shortcut like counting the number of ones or using the logarithm of the length to get the length of the needed substring... I only seem to have bad ideas for this. \$\endgroup\$ – JollyJoker Aug 21 '17 at 15:04
6
\$\begingroup\$

Brachylog, 9 7 bytes

⟦kṫᵐc,Ẹ

Try it online!

0-indexed.

Explanation

Here we pass the input through the Output variable, and access the result through the Input variable.

⟦          The result is the input to a range…
 k         …with the last element removed…
  ṫᵐ       …which when all elements are casted to string…
    c      …and are then concatenated results in the input string
     ,Ẹ    (Append the empty string, this is necessary for it to work in the case where the 
             input is the empty string)
\$\endgroup\$
5
\$\begingroup\$

Ly, 29 bytes

iys&p>0<11[ppl>s1+<lfspSylL]>

Try it online!

Can't believe this worked as well as it did...

\$\endgroup\$
5
\$\begingroup\$

Japt, 8 bytes

Starting to get to grips with function methods in Japt.

0-indexed. Can take input as a string, an integer or an array containing 0 or 1 elements.

_o ´U}a

Test it


Explanation

Implicit input of string U.

_     }a

Get the first integer >=0 that returns true when passed through a function that ...

o

Generates an array of integers from 0 to 1 less than the current integer ...

¬

Joins it to a string ...

¥U

Checks that string for equality with U.

Implicit output of resulting integer.


Alternative, 8 bytes

ÊÇo ¬ÃbU

Test it

\$\endgroup\$
4
\$\begingroup\$

Charcoal, 13 bytes

I⌕E⁺ψθ⪫EκIλωθ

Try it online! Link is to verbose version of code. Explanation:

          λ     Inner map variable (μ inner map index also works)
         I      Cast to string
        κ       Outer map index
       E        Map over implicit range
      ⪫    ω    Join result
     θ          Input string
   ⁺ψ           Plus an extra character
  E             Map over each character
 ⌕          θ   Find the index of the original string
I               Cast from integer to string
                Implicit print
\$\endgroup\$
4
\$\begingroup\$

Haskell, 40 37 bytes

f s=[n|n<-[0..],(show=<<[0..n])>s]!!0

Function that reverses zero-based ranges.

Thanks to Laikoni for saving 3 bytes!

Try it online.

\$\endgroup\$
  • 1
    \$\begingroup\$ 37 bytes with a list comprehension: f s=[n|n<-[0..],(show=<<[0..n])>s]!!0. \$\endgroup\$ – Laikoni Aug 21 '17 at 10:03
  • 1
    \$\begingroup\$ And just to mention it, you can save a byte by using the second pattern guard: |m<-n+1=s!m. \$\endgroup\$ – Laikoni Aug 21 '17 at 10:07
4
\$\begingroup\$

Retina, 30 bytes

+1`(\d+?)(?!\D)(?<!\1.+)
$0;
;

Recursively adds a semicolon after each number then counts the number of semicolons

Try it online!

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

JavaScript (ES6), 32 31 bytes

Saved 1 byte thanks to Challenger5

f=(s,r=n='')=>r<s?f(s,r+n++):+n

Test cases

f=(s,r=n='')=>r<s?f(s,r+n++):+n

console.log(f('0123'))
console.log(f('0'))
console.log(f(''))
console.log(f('0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100'))

\$\endgroup\$
  • 1
    \$\begingroup\$ Again, can you compare the strings lexicographically? \$\endgroup\$ – Esolanging Fruit Aug 21 '17 at 8:57
  • \$\begingroup\$ I was going to suggest currying but it looks like that's no longer a consensus :( \$\endgroup\$ – Shaggy Aug 21 '17 at 9:01
  • 1
    \$\begingroup\$ @Shaggy Umm, it is actually... \$\endgroup\$ – Erik the Outgolfer Aug 21 '17 at 11:47
  • 1
    \$\begingroup\$ @EriktheOutgolfer Standard currying is fine, but Shaggy was referring to this special form of currying which requires calls such as f(payload_param)() or even f(payload_param)(some_constant). (Incidentally, I'm not sure that would work in this particular case because I need both r and n to be initialized.) \$\endgroup\$ – Arnauld Aug 21 '17 at 12:10
2
\$\begingroup\$

Mathematica, 46 bytes

Array[""<>ToString/@Range@#&,2^15]~Position~#&

1-indexed

input

["12345678910"]

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

Ruby, 51 50 46 bytes

->n{(0..4e4).map{|x|(1..x).to_a.join}.index n}

(This is my first Ruby program ever so it must be easy to golf it further)

-4 bytes thanks to @Nnnes

\$\endgroup\$
  • 1
    \$\begingroup\$ You don't need the last set of parenthesis: .index(gets) => .index gets. You can use 4e4 instead of 8**5, though this will make it run even slower. It's generally OK, and often saves a few bytes, to use anonymous lambdas for Ruby answers: Try it online! (I changed the limit to 100 so that it doesn't time out.) \$\endgroup\$ – Nnnes Aug 21 '17 at 16:16
2
\$\begingroup\$

Python 2, 43 bytes

f=lambda s,i=1,r='':r<s and-~f(s,i+1,r+`i`)

Try it online!


Python 2, 43 bytes

f=lambda s,i=1:s>''and-~f(s[len(`i`):],i+1)

Try it online!


Python, 46 bytes

lambda s:s[-sum(i*'0'in s for i in range(5)):]

Try it online!

A different strategy. Takes a number of characters from the end equal to the length of the largest run of 0's in s.


Python, 46 bytes

f=lambda s,c=0:c*'0'in s and f(s,c+1)or s[-c:]

Try it online!

Recursive version of the above.

\$\endgroup\$
  • \$\begingroup\$ Does your "different strategy" (very clever, btw) work for 0-based ranges as required in the statement of the challenge? Should you change the inner bit to ... i*'0'in s[1:] for ... or something like that? \$\endgroup\$ – Luca Citi Aug 21 '17 at 23:07
  • \$\begingroup\$ @LucaCiti It works for 1-based ranges, and the challenge lets us choose. \$\endgroup\$ – xnor Aug 21 '17 at 23:08
  • \$\begingroup\$ Sure, you are right. I only looked at the initial description and missed the part where it allows for 1-based ranges. \$\endgroup\$ – Luca Citi Aug 21 '17 at 23:11
2
\$\begingroup\$

R, 47 bytes

n=nchar(scan(,""));which(cumsum(nchar(1:n))==n)

Try it online!

1-indexed

\$\endgroup\$
  • 3
    \$\begingroup\$ Use "if" instead of ifelse \$\endgroup\$ – Giuseppe Aug 21 '17 at 15:59
  • \$\begingroup\$ Good point! But OP has now removed the requirement to deal with the 0 case, so I can get rid of that bit entirely... \$\endgroup\$ – user2390246 Aug 22 '17 at 12:39
  • 1
    \$\begingroup\$ You can take input as a number, as nchar works as you might expect on numbers. However, you need to handle printing your output, since this wouldn't when run as a full program. \$\endgroup\$ – JAD Aug 23 '17 at 11:27
  • 1
    \$\begingroup\$ n=nchar(scan());cat(which(cumsum(nchar(1:n))==n)) \$\endgroup\$ – JAD Aug 23 '17 at 11:30
2
\$\begingroup\$

APL (Dyalog), 17 11 bytes

-6 bytes thanks to ngn.

{,\⍕¨⍳≢⍵}⍳⊂

Try it online!

⍳⊂ find the ɩndex of the entire argument in

{} the result of this anonymous function:

 length of the argument

ɩntegers until that

⍕¨ format (stringify) each

,\ cumulative concatenation of those

\$\endgroup\$
  • \$\begingroup\$ Oh, I forgot I could just go off of the length, nice job. \$\endgroup\$ – Zacharý Aug 22 '17 at 18:53
  • \$\begingroup\$ {,\⍕¨⍳≢⍵}⍳⊂ (11 chars) \$\endgroup\$ – ngn Aug 22 '17 at 21:42
  • \$\begingroup\$ @ngn Silly me. Of course! \$\endgroup\$ – Adám Aug 22 '17 at 21:47
2
\$\begingroup\$

Perl 5, 19 bytes

18 bytes code + 1 for -p.

$i++while s/$i\B//

Uses 1-based indexing. -7 bytes thanks to @nwellnhof's much better approach!

Try it online!

Explanation

$\ is a special variable that is printed automatically after each statement, so by using that to store our number we don't need to update $_ (which is automatically printed as part of the functionality of the -p flag) to contain the desired output. Then, whilst the input starts with $\, remove it and redo the program, which again increments $\ and replaces it. When it no longer finds the number at the beginning of the string, we're done! Finally, decrement $\ so we have the last number in the range.

\$\endgroup\$
  • \$\begingroup\$ What about $i++while s/$i\B// (18 + 1 bytes)? \$\endgroup\$ – nwellnhof Aug 24 '17 at 11:45
  • \$\begingroup\$ @nwellnhof That's much better! I think I started down a more complex route as I made the answer 0-indexed first of all... Thanks! \$\endgroup\$ – Dom Hastings Aug 24 '17 at 17:38
1
\$\begingroup\$

Python 2, 46 bytes

0-indexed

l=lambda x,z="",y=0:z<x and l(x,z+`y`,y+1)or y

Try it online!

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

CJam, 16 bytes

r0({)_,s2$=!}g\;

Try it online!

Alternative 16 bytes

r:V;0({)_,sV=!}g

Try it online!

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

CJam, 13 bytes

q:Q,),{,sQ=}#

So many commas...

Try it online!

Explanation

q:Q            Read the input and store it in Q
   ,           Get its length
    ),         Get the range 0..n
      {,sQ=}#  Find the index of the first number in the range to satisfy this block:
       ,        Get the range 0..(number)-1
        s       Stringify it
         Q=     Check if it equals the input
\$\endgroup\$
1
\$\begingroup\$

Perl 6,  30 28  27 bytes

{first :k,*eq$_,[\~] '',0...*}

Test it

{[\~]('',0...*).first($_):k}

Test it

{first :k,$_,[\~] '',0...*}

Test it

Expanded:

{  # bare block lambda with implicit parameter 「$_」

  first       # find the first one
  :k,         # return the index into the Seq instead of what matched
  $_          # that matches the input

  # from the following

  [\~]        # triangle reduce using &infix:«~» (string concatenation)

              # a Seq
    '',       #   that starts with an empty Str
    0         #   then a 0
    ...       #   generate values
    *         #   indefinitely
}

'',0...* produces an infinite sequence of values '',0,1,2,3

[\~] '',0...* produces an infinite sequence of all of the possible inputs

""
"0"
"01"
"012"
"0123"
...

Note that this code will never stop if you give it an invalid input.

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

Pyth, 11 10 bytes

1-indexed.

fqQ|jkSTk0

Try it here

If the empty string could be ignored, this can be shortened to 6 bytes:

fqQjkS

-1 byte thanks to @Mnemonic

\$\endgroup\$
  • \$\begingroup\$ ?QfqQjkUT)1 can do it in 11 as well, but I feel like some reordering can golf off a byte. Any ideas? \$\endgroup\$ – Dave Aug 21 '17 at 19:09
  • \$\begingroup\$ You can save a byte by using jk instead of s`m. \$\endgroup\$ – Mnemonic Aug 21 '17 at 19:38
1
\$\begingroup\$

CJam, 14 12 11 bytes

q,_){,s,}%#

Try it Online

q,   e# Get length of input string
_)   e# Duplicate length, increment by 1
{    e# Generate array by mapping [0,1,2,...,length] using the following function: 
,    e# Generate range [0,x] (x is the int we're mapping)
s    e# Convert range to string (e.g [0,1,2,3] => "0123"
,    e# Get the length of that string
}%   e# Map the int to the length of it's range string
#    e# Return the index of the length of the input string in the generated array
\$\endgroup\$
1
\$\begingroup\$

Dyvil, 42 38 bytes

s=>"".{var r=0;while($0!=s)$0++=r++;r}

Same algorithm as this Java answer, except it (ab)uses some of Dyvil's syntactic specialties.

Explanation:

s=>          // starts a lambda expression with one parameter
"".{         // begins a brace access expression, the value before the '.'
             // is available within the braces as a variable named '$0'
var r=0;     // variable with inferred type int
while($0!=s) // while the accumulator $0 does not (structurally) equal s
$0++=r++     // concatenate $0 and the String representation of r,
             // then store the result in $0 and increment r by 1
;            // end of while
r}           // return r as the result of the lambda

  • Saved 4 bytes by using a brace access expression instead of a variable for the accumulator
\$\endgroup\$
  • \$\begingroup\$ Cool language!! \$\endgroup\$ – Robert Fraser Aug 22 '17 at 16:45
0
\$\begingroup\$

MATL, 14 bytes

`@q:VXzGX=~}@q

1-indexed.

Try it online!

Explanation

`       % Do...while
  @     %   Push iteration index (1-based), k
  q     %   Subtract 1: gives k-1
  :     %   Range: [1 2 ... k-1]. Will be empty for k=1
  V     %   Convert to string
  Xz    %   Remove spaces
  G     %   Push input
  X=    %   Are the two strings equal?
  ~     %   Negate. This is the loop condition. If true: next iteration
}       % Finally (execute at the end of the loop)
  @     %   Push k
  q     %   Subtract 1: gives k-1. This is the solution
        % End (implicit). Display (implicit)
\$\endgroup\$
  • 1
    \$\begingroup\$ Wait, Charcoal beat MATL? \$\endgroup\$ – Neil Aug 21 '17 at 9:52
0
\$\begingroup\$

C#, 72 bytes


Data

  • Input String i The int array to be deciphered
  • Output Int32 The number used to make the array

Golfed

(string i)=>{int c,p=c=0;for(;p<i.Length;c++)p+=(c+"").Length;return c;}

Ungolfed

( string i ) => {
    int
        c,
        p = c = 0;

    for( ; p < i.Length; c++ )
        p += ( c + "" ).Length;

    return c;
}

Ungolfed readable

// Takes the string with the int array
( string i ) => {
    int
        c,         // Counter, it will count how many ints the array has.
        p = c = 0; // Padding, it will help jumping from int to int on the string.

    // Start counting. If 'i' is empty, the 'c' will be 0.
    for( ; p < i.Length; c++ )

        // Increase the number of digits with the length of 'c'.
        p += ( c + "" ).Length;

    // Return the counter.
    return c;
}

Full code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TestBench {
    public static class Program {
        private static Func<String, Int32> f = ( string i ) => {
            int
                c,
                p = c = 0;

            for( ; p < i.Length; c++ )
                p += ( c + "" ).Length;

            return c;
        };

        static void Main( string[] args ) {
            List<String>
                testCases = new List<String>() {
                    "0123",
                    "0",
                    "",
                    "0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100",
                };

            foreach(String testCase in testCases) {
                Console.WriteLine($" Input: {testCase}\nOutput: {f(testCase)}\n");
            }

            Console.ReadLine();
        }
    }
}

Releases

  • v1.0 - 72 bytes - Initial solution.

Notes

  • None
\$\endgroup\$
  • 1
    \$\begingroup\$ i=>{int c,p=c=0;for(;p<i.Length;)p+=(c+++"").Length;return c;} 62 bytes \$\endgroup\$ – TheLethalCoder Aug 21 '17 at 12:06
0
\$\begingroup\$

SOGL V0.12, 11 10 9 bytes

1-indexed.

I∫HΔ∑=?f←

Try it Here!

Explanation:

I∫         repeat input+1 times
  HΔ         create a range from 1 to the 0-indexed iteration, inclusive
    ∑        join it
     =?      if it's equal to the input
       f←      exit, pushing the 0-indexed counter

..or 7 bytes without the empty case

∫Δ∑=?F←

Try it Here!

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

Aceto, 27 25 bytes

1-based index.

;L[¥
`=]z
MLdI<
r!`;   p

We read the input and Memorize it (and directly Load it again), then we negate it (!; leading to a truthy value only for an empty string). If this value is truthy (`), we jump to the end (;), where we print the implicit zero.

Otherwise, we increment the current stack value (initially a zero), duplicate it, and put one copy on the stack to the right, while also moving there (Id]). We then construct a decreasing range (z), join the stack as a string (¥), and move the value (and us) on the original stack again ([). We Load the value we memorized earlier (the input) and compare it with this string. If equal, we jump to the end again, where we print the current "counter" value (=`;).

Otherwise, lots of empty space is traversed until the Hilbert curve eventually hits the < which puts the IP on top of I again, incrementing the counter and testing again.

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

Stacked, 23 bytes

{!0$#+[::>''#`n=]until}

Try it online!

Basically, increments 0 until the range from 0 to the number looks like the input, checking for equality first.

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

Jelly, 8 bytes

JVṾẎ$$Ƥi

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.