22
\$\begingroup\$

Definition

There is infinite row of concatenated natural numbers (positive integers, starting with 1):

1234567891011121314151617181920212223...

Challenge

  • Write program in any language, that accepts position number as an input, and outputs digit from that position in the row defined above.
  • Position number is arbitrary size positive integer. That is first position is 1, yielding output digit '1'
  • Input is either in decimal (eg. 13498573249827349823740000191), or e-notation (eg. 1.2e789) corresponding to positive integer.
  • Program has to end in reasonable time (10 seconds on modern PC/Mac), given very large index as an input (eg. 1e123456 - that is 1 with 123456 zeroes). So, simple iteration loop is not acceptable.
  • Program has to terminate with an error in 1 s, if given any invalid input. Eg. 1.23e (invalid), or 1.23e1 (equals to 12.3 - not an integer)
  • It's ok to use public BigNum library to parse/store numbers and do simple mathematical operations on them (+-*/ exp). No byte-penalty applied.
  • Shortest code wins.

TL;DR

  • Input: bignum integer
  • Output: digit at that position in infinite row 123456789101112131415...

Some acceptance test cases

in notation "Input: Output". All of them should pass.

  • 1: 1
  • 999: 9
  • 10000000: 7
  • 1e7: 7 (same as row above)
  • 13498573249827349823740000191: 6
  • 1.1e10001: 5
  • 1e23456: 5
  • 1.23456e123456: 4
  • 1e1000000: 0
  • 1.23e: error (invalid syntax)
  • 0: error (out of bounds)
  • 1.23e1: error (not an integer)

Bonus!

Output digit position number inside the number, and output number itself. For example:

  • 13498573249827349823740000191: 6 24 504062383738461516105596714
    • That's digit '6' at position 24 of number '504062383738461516105596714'
  • 1e1000000: 0 61111 1000006111141666819445...933335777790000
    • Digit '0' at position 61111 of 999995-digit long number I'm not going to include here.

If you fulfill the bonus task, multiply size of your code by 0.75

Credit

This task was given at one of devclub.eu gatherings in year 2012, without large number requirement. Hence, most answers submitted were trivial loops.

Have fun!

\$\endgroup\$
  • \$\begingroup\$ I really don't get what the challenge is. Are we supposed to take the input and output the number at that position? \$\endgroup\$ – The_Basset_Hound Aug 5 '15 at 14:32
  • 1
    \$\begingroup\$ This is OEIS sequence 33307. \$\endgroup\$ – Tyilo Aug 5 '15 at 15:12
  • 2
    \$\begingroup\$ @vihan Using some public bignum library is acceptable. No penalty. Of course including the solution into library and using the library in one-liner is considering cheating. Common sense applies here. \$\endgroup\$ – metalim Aug 5 '15 at 15:22
  • 1
    \$\begingroup\$ Just wanted to show off a surprisingly concise F# solution, clocking in at 44 bytes. Granted, it can only handle indices up to 2^31-1 (and its still trying to compute that value as I write this). I'm not posting this though because it does indeed break the rules, but I'd say its pretty good for F#! \$\endgroup\$ – Jwosty Aug 5 '15 at 21:31
  • 7
    \$\begingroup\$ The requirements to handle inputs like 1.23456e123456 arbitrarily punishes languages that cannot process such values natively and requires them to do string processing that is tangential to the challenge. \$\endgroup\$ – xnor Aug 5 '15 at 22:55
12
\$\begingroup\$

CJam, 78 bytes

r_A,s-" e . .e"S/\a#[SSS"'./~'e/~i1$,-'e\]s"0]=~~_i:Q\Q=Qg&/
s,:L{;QAL(:L#9L*(*)9/-_1<}g(L)md_)p\AL#+_ps=

The program is 104 bytes long and qualifies for the bonus.

The newline is purely cosmetic. The first line parses the input, the second generates the output.

Try it online!

Idea

For any positive integer k, there are 9×10k-1 positive integers of exactly k digits (not counting leading zeroes). Thus, if we concatenate all of them, we obtain an integer of 9×n×10k-1.

Now, concatenating all integers of n or less digits yields an integer of

formula

digits.

For a given input q, we try determine the highest n such that the above expression is smaller than q. We set n := ⌈log10q⌉-1, then n := ⌈log10q⌉-2, etc. until the desired expression becomes smaller than q, subtract the resulting expression from q (yielding r) and save the last value of n in l.

r now specifies the index in the concatenation of all positive integers of l+1 digits, which means that the desired output is the r%(l+1)th digit of the r/(l+1)th integer of l+1 digits.

Code (input parsing)

r_          e# Read from STDIN and duplicate.
A,s-        e# Remove all digits.
" e . .e"S/ e# Push ["" "e" "." ".e"].
\a#         e# Compute the index of the non-digit part in this array.

[SSS"'./~'e/~i1$,-'e\]s"0]

            e# Each element corresponds to a form of input parsing:
            e#   0 (only digits): noop
            e#   1 (digits and one 'e'): noop
            e#   2 (digits and one '.'): noop
            e#   3 (digits, one '.' then one 'e'):
            e#     './~    Split at dots and dump the chunks on the stack.
            e#     'e/~    Split the and chunks at e's and dump.
            e#     i       Cast the last chunk (exponent) to integer.
            e#     1$      Copy the chunk between '.' and 'e' (fractional part).
            e#     ,-      Subtract its length from the exponent.
            e#     'e\     Place an 'e' between fractional part and exponent.
            e#     ]s      Collect everything in a string.
            e#   -1 (none of the above): push 0

~           e# For s string, this evaluates. For 0, it pushes -1.
~           e# For s string, this evaluates. For -1, it pushes 0.
            e# Causes a runtime exception for some sorts of invalid input.
_i:Q        e# Push a copy, cast to Long and save in Q.
\Q=         e# Check if Q is numerically equal to the original.
Qg          e# Compute the sign of Q.
&           e# Logical AND. Pushes 1 for valid input, 0 otherwise.
/           e# Divide by Q the resulting Boolean.
            e# Causes an arithmetic exception for invalid input.

Code (output generation)

s,:L     e# Compute the number of digits of Q and save in L.
{        e# Do:
  ;      e#   Discard the integer on the stack.
  Q      e#   Push Q.
  AL(:L# e#   Push 10^(L=-1).
  9L*(   e#   Push 9L-1.
  *)     e#   Multiply and increment.
  9/     e#   Divide by 9.
  -      e#   Subtract from Q.
  _1<    e#   Check if the difference is non-positive.
}g       e# If so, repeat the loop.
(        e# Subtract 1 to account for 1-based indexing.
L)md     e# Push quotient and residue of the division by L+1.
_)p      e# Copy, increment (for 1-based indexing) and print.
\AL#+    e# Add 10^L to the quotient.
_p       e# Print a copy.
s        e# Convert to string.
2$=      e# Retrieve the character that corresponds to the residue.
\$\endgroup\$
5
\$\begingroup\$

CJam, 75 * 0.75 = 56.25

This is quite fast, one iteration per digit of the number that contains the desired position. I'm sure it can be golfed a lot more, it's quite crude as it is.

q~_i_@<{0/}&:V9{VT>}{T:U;_X*T+:T;A*X):X;}w;U-(_X(:X/\X%10X(#@+s_2$\=S+@)S+@

Give the position as input, the output is:

<digit> <position> <full number>

Try it online.

\$\endgroup\$
  • \$\begingroup\$ @Dennis Working with all inputs now :) \$\endgroup\$ – Andrea Biondo Aug 5 '15 at 17:11
  • \$\begingroup\$ This still doesn't raise an error (as it should) for 1.23e1. It errors, however, for 1.23456e123456, since the input cannot represented by a Double. Also, the last test cases takes 3 minutes. \$\endgroup\$ – Dennis Aug 5 '15 at 17:16
  • 2
    \$\begingroup\$ @Dennis Now raises the error. As for the big test case... Damn. I may have to rewrite the whole thing. \$\endgroup\$ – Andrea Biondo Aug 5 '15 at 17:34

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.