19
\$\begingroup\$

Story:

The π was recently computed with accuracy to 100 trillions digits, but it is useless to us. We can't do accurate enough math, because rational numbers are too boring and so we don't know that much digits of them!

Challenge:

Your task will be to write program or function which takes string of digits including decimal separator and outputs next digit of this number. You can get next digit by knowing, that the input is composed out of two strings (ignoring the decimal separator) like this abb. For example the number 0.1818 is composed of string a which is 0 and b which is 18 and the output will be first digit of b, which is 1. If there are multiple choices for string b you have to use longest one. The string a can be empty.

The decimal separator is guaranteed to be in every number and won't be first or last character of input. You can choose which decimal separator you want to support from following characters: .,·'

Testcases:

Input a b Output
0.1818 0 18 1
6.66 6 6 6
3.3 3 3
0.0526315789473684210526315789473684210 00 526315789473684210 5
37.0370 370 3
88.998899 8899 8
1657.7771657777 1657777 1
5.0000000 50 000 0
25885882588.588 2588588 2
9.99999 999 9
1.221122 12211 2 2
1.2112113211 121121132 1 1
\$\endgroup\$
15
  • 2
    \$\begingroup\$ Most test cases are not of the format abb, they are of the format ab[most of b]. In the test case starting 2588, you have to pull the next digit from a and not from b. I can't find a fixed pattern here. \$\endgroup\$ Jul 18 at 14:00
  • 1
    \$\begingroup\$ @EngineerToast The b is this case is 2588588, a is empty. \$\endgroup\$
    – Jiří
    Jul 18 at 14:16
  • 2
    \$\begingroup\$ @Adam a=12211, b=2 probably. \$\endgroup\$ Jul 18 at 14:19
  • \$\begingroup\$ So it's not just a is what's before the decimal, OK. In my head, a being empty was shown as a 0 before the decimal but that isn't right. So the 4th test case has a = 00 and b = 526...210. Now I can see the patterns. May I suggest adding more explanation to the test cases? \$\endgroup\$ Jul 18 at 14:20
  • 1
    \$\begingroup\$ @DavidConrad You have to extract b from input. And for example this input 88.998899 offers multiple choices for b, which are 9 and 8899. \$\endgroup\$
    – Jiří
    Jul 20 at 20:41

20 Answers 20

16
\$\begingroup\$

Regex (ECMAScript or better), 38 34 20 bytes

((.).*),?(.*)\1,?\3$

Uses , as the decimal separator. Returns its output as capture group \2.

Try it on regex101 - ECMAScript (and can be switched to others)
Try it online! - ECMAScript
Attempt This Online! - PCRE2
Try it online! - .NET

It occurred to me after writing both of the below regexes that an entirely different approach would also work.

# Search for a "first half", which is repeated exactly following itself
# (except that there can be a decimal point anywhere in either half, which
# is not repeated), with the end of the string following that in turn.
((.).*)      # \1 = part 1 of first half;
             # \2 = first digit of this half (the return value)
             # A decimal point may be here in the other half.
,?           # Skip a decimal point, if there is one in this half. If there isn't
             # one here in this half, there must be one here in the other half.
(.*)         # \3 = part 2 of first half
# Match the other half, which is an exact repetition of the first half
# except that a decimal point can occur anywhere in either half and is
# not repeated.
\1           # Match part 1
,?           # Skip a decimal point, if there is one here.
\3           # Match part 2
$            # Assert that we've reached the end of the string.

It even almost works in GNU ERE:
Attempt This Online! - but fails on the 5.0000000 case, because this engine really doesn't like to backtrack much. The strangest thing is that if REG_NOSUB is enabled, it claims to match everything... is it lying? It's Schrödinger's match. (You can experiment with that by changing SHOW_MATCH to 0 in the test harness.)

This 20 byte regex obsoletes the other two below, as it runs at the same speed or faster... but I'm not sure if I want to delete them, since they're interesting in their own right. And they would still be the only working solutions if the entire string could be littered with any number of decimal points.

Regex (.NET), 39 bytes

(?=((.),?)*$)(?<=(?(2)$)(?<-2>(\2),?)*)

Returns its output as capture group \3.

Try it online!

This works (using .NET's Balancing Groups feature) by pushing a portion of the end of the string onto the group \2 capture stack, one digit at a time, and then scanning in reverse from the position it started from, popping off one digit at a time from the stack to check that they match. The last one popped off is then the return value, if it matches.

              # No anchor - This regex will try starting its match at each
              # character of the string until succeeding.
(?=           # Positive atomic lookahead - Match the following, but then
              # return to this position.
    (
        (.)   # Push a digit onto the group \2 capture stack.
        ,?    # Skip a decimal point if there is one here.
    )*        # Iterate the above as many times as possible, minimum zero
    $         # Assert we've reached the end of the string.
)
(?<=          # Lookbehind - evaluated right-to-left
              # (read this from the bottom up)
    (?(2)$)   # Assert that if the group \2 stack is not empty, we're at the
              # end of the string (which is impossible). Basically, assert
              # that the group \2 stack is empty.
    (?<-2>    # Pop a capture from the group \2 stack and match:
        (\2)  # \3 = digit that matches with \2
        ,?    # Skip a decimal point if there is one here.
    )*
)

Try it on regex101 - putting this link down below here because regex101's .NET support is a bit buggy. With this example, it sees the capture groups in the wrong order, and thinks the return value is in group 1.

Regex (PCRE2), 48 bytes

(?*(.).*(.*+))((.),?(?=.*(?=\2$)(\5?+,?\4)))+\5$

Returns its output as capture group \1.

Try it on regex101
Attempt This Online!

                   # No anchor - This regex will try starting its match at each
                   # character of the string until succeeding.
(?*                # Non-atomic lookahead - Match the following, but then return
                   # to this position; if a non-match is subsequently found,
                   # backtrack to here and try other possible matches.
    (.)            # Capture the first digit in \1; this will be our return value.
    .*(.*+)        # Search for a \2 that is the last instance of the entire
                   # repeating pattern, using non-atomic lookahead.
)
(                  # Loop the following:
    (.)            # \4 = a digit
    ,?             # Skip a decimal point if there is one here.
    (?=            # Positive atomic lookahead - Match the following, but then
                   # return to this position.
        .*(?=\2$)  # Skip to where \2 begins.
        (          # \5 = the following:
            \5?+   # The previous value of \5, or nothing if this is the first
                   # iteration and \5 is unset.
            ,?     # Skip a decimal point if there is one here.
            \4     # Match a copy of the digit captured in \4.
        )
    )
)+                 # Iterate as many times as possible (minimum one) to match the
                   # following assertion:
\5$                # Assert that the \5 we captured is identical to \2 and is
                   # located at the end of the string.

This uses a PCRE2 feature, non-atomic lookahead (?*...). I'm pretty sure it's also possible to solve this without non-atomic lookahead, but I'll look into that later.

Note that the only reason this regex is so complicated is because of the presence of the decimal point. If not for that, the solution would be (?=(.+)\1$|.$). (which is what I came up with before realizing the decimal point was in the way, when I still wanted to return the output as the match instead of a capture group), or what is used in ovs's Retina solution, ((.).*)\1$.

But this is a pure regex solution, and can't do any substitutions before doing its matching work.

\$\large\textit{Full programs}\$

Perl -p, 28 bytes

/((.).*),?(.*)\1,?\3$/;$_=$2

Try it online!

\$\large\textit{Anonymous functions}\$

Ruby, 31 bytes

->s{~/((.).*),?(.*)\1,?\3$/;$2}

Try it online!

JavaScript (ES6), 37 bytes

s=>s.match(/((.).*),?(.*)\1,?\3$/)[2]

Try it online!

Julia v0.4+, 38 bytes

s->match(r"((.).*),?(.*)\1,?\3$",s)[2]

Try it online!

R v4.1.0+, 48 bytes

\(s)gsub('.*?((.).*),?(.*)\\1,?\\3$','\\2',s,,1)

Attempt This Online!

Java 8, 49 bytes

s->s.replaceAll(".*?((.).*),?(.*)\\1,?\\3$","$2")

Try it online!

Java's split method just doesn't work the right way to be useful for this.

PHP, 54 bytes

fn($s)=>preg_split('/(?=(.+),?(.*)\1,?\2$)/',$s)[1][0]

Try it online!

Python, 57 bytes

lambda s:re.split(r'(.+),?(.*)\1,?\2$',s)[1][0];import re

Try it online!

Python, 61 bytes

lambda s:__import__('re').split(r'(.+),?(.*)\1,?\2$',s)[1][0]

Try it online!

(If it must be a pure lambda.)

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Umm these languages should probably be split up? \$\endgroup\$
    – Seggan
    Jul 20 at 1:26
  • 3
    \$\begingroup\$ @Seggan Well, I've been doing it this way for a while now, because I like the presentation style of keeping them together, and to avoid being greedy with expecting upvotes on lots of separate answers (which is as much about my well-being as avoiding greed... I feel sorry for answers that don't do well – it stresses me). You're the first to suggest I do it differently. I did split off my Perl and Java lambda answers in "Do you make me up?", but I think that was mainly because the main pure-regex answer was so long. \$\endgroup\$
    – Deadcode
    Jul 20 at 1:45
  • \$\begingroup\$ I'm very open to other changes though, like perhaps spatially compressing the presentation by using single-backticks instead of multiline code blocks (and not having one heading per function/program). Anybody think I should do that? \$\endgroup\$
    – Deadcode
    Jul 20 at 2:05
8
\$\begingroup\$

Retina, 19 bytes

Uses , as a decimal separator.

,

.*?((.).*)\1$
$2

Try it online!

\$\endgroup\$
8
\$\begingroup\$

Jelly, 10 bytes

ḟṂŒHÐƤEƇFḢ

A monadic Link that accepts a string of digit characters containing a decimal point, ., and yields a digit character.

Try it online! Or see the test-suite.

How?

ḟṂŒHÐƤEƇFḢ - Link: list of characters, N
 Ṃ         - minimum of N (guaranteed to be the '.')
ḟ          - filter ('.') from N
    ÐƤ     - for each suffix of that:
  ŒH       -   split into two halves
       Ƈ   - filter keep those which are:
      E    -   all equal (i.e first half = second half)
        F  - flatten
         Ḣ - head
\$\endgroup\$
8
\$\begingroup\$

05AB1E, 14 13 12 9 bytes

RþηD2×Ãθθ

-1 byte porting @JonathanAllan's Jelly answer
-3 bytes thanks to @CommandMaster with a very smart usage of à as golf on my 13-byter(s)

Try it online or verify all test cases.

Explanation:

R          # Reverse the (implicit) input
 þ         # Remove the dot by only keeping the digits
  η        # Pop and push a list of its prefixes
   D       # Duplicate this list of prefixes
    2×     # Double each string in the top prefixes-list
      Ã    # Only keep those doubled-prefixes from the prefixes-list
       θ   # Pop and push the last/longest
        θ  # Pop and push its last digit
           # (which is output implicitly as result)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ RþηD2×Ãθθ seems to work for -4 bytes \$\endgroup\$ Jul 19 at 6:51
  • \$\begingroup\$ @CommandMaster Oh, very smart use of à like that. Thanks! I'll wait for 2 more minutes to have history for the current answer before I update it, but that ηD2×à is indeed a very smart way of doing this to get rid of all the Duplicates I had in my original 13-byter(s). :) \$\endgroup\$ Jul 19 at 6:56
7
\$\begingroup\$

Python, 68 62 57 bytes

lambda x:re.split(r"(.+),?(.*)\1,?\2$",x)[1][0]
import re

Attempt This Online!

Takes in a string with , as the decimal separator.


-6 bytes from @loopy walt by using $ instead of reversal.
-5 bytes from @loopy walt / @DeadCode using the matching regex to ignore the , instead of adding a re.sub

\$\endgroup\$
10
  • 2
    \$\begingroup\$ 63 by avoiding reversal. \$\endgroup\$
    – loopy walt
    Jul 18 at 17:06
  • \$\begingroup\$ 57 by letting the main regex filter out the separator. \$\endgroup\$
    – loopy walt
    Jul 19 at 1:43
  • 1
    \$\begingroup\$ Of course I did @Deadcode. It is not that revolutionary an approach, really. And besides, just think about what you seem to be suggesting: Do you really think it plausible anyone would go through the trouble of sneakily nicking somebody else's idea for --- yeah, for what? The Nobel Prize? There are quite a few smart enough people here. Of course they will sometimes think along similar lines. I know it's nice to be credited but in the end we are all just trying to have a bit of fun. \$\endgroup\$
    – loopy walt
    Jul 19 at 3:50
  • 1
    \$\begingroup\$ @loopywalt For the record, I have seen someone on this site use another person's idea knowingly without crediting them. It's not common; I've only seen it that once, and I give them the benefit of the doubt (they probably thought it wasn't a big deal), but I encouraged them to include the credit, and they subsequently did. Anyway, I'm glad that's not what you were doing. \$\endgroup\$
    – Deadcode
    Jul 19 at 4:11
  • 2
    \$\begingroup\$ At the very least, if two people converged on the same exact same minimal solution, it's probably close to the ideal :P \$\endgroup\$ Jul 19 at 14:13
6
\$\begingroup\$

Husk, 8 bytes

←ḟoE½ṫf±

Try it online!

      f   # filter to keep only
       ±  #  characters that are digits,
 ḟ        # now get the first 
     ṫ    #  of all the tails (possible 'bb's)
  oE½     #  which is two copies of the same thing,
←         # and return the first element.    
\$\endgroup\$
5
\$\begingroup\$

Raku, 31 bytes

{+(S/\.//~~/((.).*?)$0$/)[0;0]}

Try it online!

S/\.// returns a copy of the input string with the decimal point removed. That string is matched with ~~ against the pattern ((.) .*?) $0 $, which looks for the repeating portion at the end of the string. [0; 0] looks up the first submatch group of the first match group (ie, the digit matched by the (.)) and + converts that match object to an integer.

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

Excel, 118 104 bytes

=LET(a,MID(SUBSTITUTE(A1,".",),ROW(1:32767),2^15),b,LEFT(a,LEN(a)/2),LEFT(INDEX(b,MATCH(TRUE,a=b&b,0))))

Input is in cell A1 of the active sheet. Output is wherever the formula is. Breaking down the LET() function into the variable,value,...,output format, we get this for the first two terms:

  • a,MID(SUBSTITUTE(A1,".",),ROW(1:32767),2^15) removes any decimal point and then creates an array 32767 rows tall where each row removes another character from the beginning of the string. Most of this array will be empty, of course, but this is to accommodate the max number of characters allowed per cell.
  • b,LEFT(a,LEN(a)/2) creates an equally tall array of the first half of the first array.

Now it gets into the more complicated final term:

LEFT(INDEX(b,MATCH(TRUE,a=b&b,0))))
  • MATCH(TRUE,a=b&b,0) finds the first row where a is exactly b twice.
  • INDEX(b,MATCH(~)) pull the entire value of b from the array at that point.
  • LEFT(INDEX(~)) outputs the first character of that result.

Screenshot with details for one of the test cases:

Details


Screenshot with all the test cases:

Testcases

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

Vyxal, 13 10 bytes

~±ÞKvI~≈fh

Try it Online!

~±ÞKvI~≈fh
~±         # Filter for numeric, to remove the ".". Converts to list of chars
  ÞK       # Suffixes
    vI     # Split each into a list of two halves
      ~≈   # Filter for all equal
        f  # Flatten
         h # First item

Original 13 bytes was porting UnrelatedString's Jelly answer, but porting Jonathan Allan's answer saved 3 bytes, so upvote those two!

Alternative:

Vyxal, 10 bytes

goÞK½~≈hhh

Try it Online!

goÞK½~≈hhh
g          # Minimum (".")
 o         # Remove it
  ÞK       # Suffixes
    ½      # Split each into a list of two halves
     ~≈    # Filter for all equal
       h   # First list
        h  # First string
         h # First character
\$\endgroup\$
4
\$\begingroup\$

Brachylog, 7 bytes

ịˢa₁~jh

Try it online!

ịˢ         Filter the input to only digits.
  a₁       For some suffix (tried longest first),
      h    output the first element of
    ~j     a list which repeated twice is the suffix.
\$\endgroup\$
4
\$\begingroup\$

K (ngn/k), 26 bytes

**((~/2 0N#)')#(1_)\(46=)_

Try it online!

Explanation

  • (46=)_ remove decimal
  • (1_)\ generate suffixes
  • ((...)')# filter each suffix...
    • 2 0N# halve suffix
    • ~/ check if halves are equal
  • ** first of first
\$\endgroup\$
3
\$\begingroup\$

Python, 74 bytes

f=lambda s,i=0:s[n:=i-len(s)]*(s[n:]==s[2*n:n])or f(s.replace(".",""),i+1)

Attempt This Online!

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

Jelly, 13 bytes

ḟ”.ŒHẆf/ƊÐƤFḢ

Try it online!

ḟ”.              Remove the radix point.
        ƊÐƤ      For each suffix:
   ŒH            Split it in half,
       /         and reduce
     Ẇ           the sublists of the pair of halves
      f          by filter left by membership in right.
           F     Flatten the results
            Ḣ    and yield the first element.
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 46 bytes

s=>/^.*?(.*)\1$/.exec(s.replace('.',''))[1][0]

Attempt This Online!

\$\endgroup\$
1
  • 3
    \$\begingroup\$ s=>/(.+)\1$/.exec(s.replace('.',''))[1][0] \$\endgroup\$
    – tsh
    Jul 19 at 1:39
2
\$\begingroup\$

Python 3.8 (pre-release), 65 bytes

f=lambda s:(s:=s.replace('.',''))[:s==s[:len(s)//2]*2]or f(s[1:])

Try it online!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Seems to fail on 1.2112113211. \$\endgroup\$
    – loopy walt
    Jul 18 at 14:52
  • \$\begingroup\$ @loopywalt Thanks, fixed \$\endgroup\$
    – Jitse
    Jul 19 at 11:58
2
\$\begingroup\$

lin, 35 bytes

"\, !="`#"1`d"`it"`bi \`= `/"`?' `^

Try it here! Takes string with , comma.

I recently added string literals to lin, still not sure if I regret doing so...

For testing purposes:

"1,2112113211" ; outln
"\, !="`#"1`d"`it"`bi \`= `/"`?' `^

Explanation

More readable version:

( \, != ) `# ( 1`d ) `it ( `bi \`= `/ ) `?' `^
  • ( \, != ) `# filter out comma
  • ( 1`d ) `it generate suffixes
  • (...) `?' find first suffix that satisfies the following...
    • `bi split suffix in half
    • \`= `/ check if both halves are equal
  • `^ first element
\$\endgroup\$
1
\$\begingroup\$

Excel VBA, 107 bytes

Sub o(a)
a=Replace(a,".","")
b=Left(a,Len(a)/2)
If a=b &b Then MsgBox Left(b,1):Exit Sub
o Mid(a,2)
End Sub
  1. Remove any decimal points from the input.
  2. Get the first half (rounded up) of the input.
  3. If the whole string is the first half twice, output the first digit of b to a message and exit.
  4. Otherwise, remove the first letter from the input and recurse.

VBA will pad the code with spaces automatically. The above input is valid but here's what it looks like after that auto-formatting:

Sub o(a)
a = Replace(a, ".", "")
b = Left(a, Len(a) / 2)
If a = b & b Then MsgBox Left(b, 1): Exit Sub
o Mid(a, 2)
End Sub
\$\endgroup\$
1
\$\begingroup\$

Python 3, 93 bytes

def f(s):s=s.replace(".","");return[s[-i:][0]for i in range(len(s))if s[-i:]==s[-2*i:-i]][-1]

Try it online!

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

Charcoal, 22 bytes

§⊟ΦEθ…⮌⁻θ.κ¬⌕⮌⁻θ.×²ι±¹

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

    θ                   Input string
   E                    Map over characters
        θ               Input string
       ⁻ .              With `.`s removed
      ⮌                 Reversed
     …                  Truncated to length
          κ             Current index
  Φ                     Filtered where
            ⌕           Index of
                   ι    Current reversed suffix
                 ײ     Repeated twice
               θ        In current string
              ⁻ .       With `.`s removed
             ⮌          Reversed
           ¬            Is zero
 ⊟                      Take the longest reversed suffix
§                   ±¹  Take its last character
                        Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Haskell, 95 83 bytes

-12 bytes thanks to @Unrelated String

g.filter(>'.')
g x=[x!!d|d<-[0..],uncurry(==)$div(length x-d)2`splitAt`drop d x]!!0

Attempt This Online!

\$\endgroup\$
1

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.