Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The challenge is to identify the missing number in a string of undelimited integers.

You are given a string of digits (valid input will match the regular expression ^[1-9][0-9]+$). The string represents a sequence of integers. For example, 1234567891011. All numbers in the sequence are in the range from 1 and 2147483647 inclusive.

The sequence is a series of numbers where each number is one greater than its predecessor. However, this sequence may contain one and only one missing number from the sequence. It is possible that a given string also contains no missing numbers from the sequence. The string will always contain at least two numbers from the sequence.

The code must output or return the missing value, or 0 (this is a 0 - not a falsy value) in the event that the no missing values were found.

The following are valid inputs and their output/return:

input                         output    actual sequence (for refrence)
123467                        5         1 2 3 4 _ 6 7
911                           10        9 __ 11
123125126                     124       123 ___ 125 126
8632456863245786324598632460  8632458   8632456 8632457 _______ 8632459 8632460  
123                           0         1 2 3
8632456863245786324588632459  0         8632456 8632457 8632458 8632459  

While all of this is described as a 'string' as input, if the language is capable of handling arbitrarily large numbers (dc and mathematica, I'm looking at you two) the input may be an arbitrarily large number instead of a string if that makes the code easier.

For reference, this was inspired by the Programmers.SE question: Find missing number in sequence in string

share|improve this question
3  
Are you sure this is unambiguous? – Martin Ender Feb 16 at 20:36
    
@MartinBüttner I've thought a bit about it and haven't been able to come up with a situation where a sequence increasing by 1 (that might be the problem) has an ambiguous situation. – user12166 Feb 16 at 20:37
    
Is there an entry in OEIS for the list of integers that are a concatenated sequence missing exactly one element? – mbomb007 Feb 16 at 22:20
    
@mbomb007 I don't think so as there are infinitely many different lists. And that this is just one big ole string. Not sure how you'd define it. For that matter, an interesting CS question would be "what is the language that accepts all these strings". Its certainly not regular. I doubt its CF. – user12166 Feb 16 at 22:22
1  
I made the sequence the subject of a challenge: codegolf.stackexchange.com/q/73513/34718 – mbomb007 Feb 18 at 21:27
up vote 5 down vote accepted

Haskell, 115 112 bytes

g b|a<-[b!!0..last b]=last$0:[c|c<-a,b==filter(/=c)a]
maximum.map(g.map read.words.concat).mapM(\c->[[c],c:" "])

The first line is a helper function definition, the second is the main anonymous function. Verify test cases (I had to run shorter tests because of time restrictions).

Explanation

This is a brute force solution: split the string into words in all possible ways, parse the words to integers, see whether it's a range with one element missing (returning that element, and 0 otherwise), and take the maximum over all splittings. The range-with-missing-element check is done in the helper function g, which takes a list b and returns the sole element in the range [head of b..last of b] that's not in b, or 0 if one doesn't exist.

g b|                         -- Define g b
    a<-[b!!0..last b]=       -- (with a as the range [head of b..last of b]) as:
    last$0:[...]             --  the last element of this list, or 0 if it's empty:
            c|c<-a,          --   those elements c of a for which
            b==filter(/=c)a  --   removing c from a results in b.
mapM(\c->[[c],c:" "])        -- Main function: Replace each char c in input with "c" or "c "
map(...)                     -- For each resulting list of strings:
  g.map read.words.concat    --  concatenate, split at spaces, parse to list of ints, apply g
maximum                      -- Maximum of results (the missing element, if exists)
share|improve this answer

JavaScript (ES6), 117 bytes

s=>eval(`for(i=l=0;s[i];)for(n=s.slice(x=i=m=0,++l);s[i]&&!x|!m;x=s.slice(x?i:i+=(n+"").length).search(++n))m=x?n:m`)

Explanation

Fairly efficient approach. Finishes instantly for all test cases.

Gets each substring from the beginning of the input string as a number n and initialises the missing number m to 0. It then repeatedly removes n from the start of the string, increments n and searches the string for it. If index of n != 0, it checks m. If m == 0, set m = n and continue, if not, there are multiple missing numbers so stop checking from this substring. This process continues until the entire string has been removed.

var solution =

s=>
  eval(`                     // use eval to use for loops without writing {} or return
    for(
      i=                     // i = index of next substring the check
      l=0;                   // l = length of initial substring n
      s[i];                  // if it completed successfully i would equal s.length
    )
      for(
        n=s.slice(           // n = current number to search for, initialise to subtring l
          x=                 // x = index of n relative to the end of the previous n
          i=                 // set i to the beginning of the string
          m=0,               // m = missing number, initialise to 0
          ++l                // increment initial substring length
        );
        s[i]&&               // stop if we have successfully reached the end of the string
        !x|!m;               // stop if there are multiple missing numbers
        x=                   // get index of ++n
          s.slice(           // search a substring that starts from the end of the previous
                             //     number so that we avoid matching numbers before here
            x?i:             // if the previous n was missing, don't increment i
            i+=(n+"").length // move i to the end of the previous number
          )
          .search(++n)       // increment n and search the substring for it's index
      )
        m=x?n:m              // if the previous number was missing, set m to it
  `)                         // implicit: return m
<input type="text" id="input" value="8632456863245786324598632460" />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>

share|improve this answer

JavaScript (ES6) 114

s=>eval("for(d=0,n=-9,z=s;z=z.slice((n+'').length);z.search(++n)?z.search(++n)?n=(z=s).slice(x=0,++d):x=n-1:0);x")  

Less golfed and explained

f=s=>{
  d = 0  // initial digit number, will be increased to 1 at first loop 
  n = -9 // initial value, can not be found
  z = s  // initializa z to the whole input string
  // at each iteration, remove the first chars of z that are 'n' 
  // 'd' instead of 'length' would be shorter, but the length can change passing from 9 to 10 
  for(; z=z.slice((n+'').length); ) 
  {
    ++n; // n is the next number expected in sequence
    if (z.search(n) != 0)
    {
      // number not found at position 0
      // this could be the hole
      // try to find the next number
      ++n;
      if (z.search(n) != 0)
      {
        // nope, this is not the correct sequence, start again
        z = s; // start to look at the whole string again
        x = 0; // maybe I had a candidate result in xm but now must forget it
        ++d;   // try a sequence starting with a number with 1 more digit
        n = z.slice(0,d) // first number of sequence
      }
      else
      {
        // I found a hole, store a result in x but check the rest of the string
        x = n-1
      }
    }
  }      
  return x // if no hole found x is 0
}

Test

F=s=>eval("for(d=0,n=-9,z=s;z=z.slice((n+'').length);z.search(++n)?z.search(++n)?n=(z=s).slice(x=0,++d):x=n-1:0);x")

console.log=x=>O.textContent+=x+'\n'

elab=x=>console.log(x+' -> '+F(x))

function test(){ elab(I.value) }

;['123467','911','123125126','8632456863245786324598632460',
  '123','124125127','8632456863245786324588632459']
.forEach(t=>elab(t))
<input id=I><button  onclick='test()'>Try your sequence</button>
<pre id=O></pre>

share|improve this answer

C, 183 168 166 163 bytes

n,l,c,d,b[9];main(s,v,p)char**v,*p;{for(;s>1;)for(d=s=0,n=atoi(strncpy(b,p=v[1],++l)),p+=l;*p&&s<2;)p+=memcmp(p,b,c=sprintf(b,"%d",++n))?d=n,s++:c;printf("%d",d);}

Ungolfed

n,l,c,d,b[9];

main(s,v,p)char**v,*p;
{
    /* Start at length 1, counting upwards, while we haven't
       found a proper number of missing numbers (0 or 1) */
    for(;s>1;)
        /* Start at the beginning of the string, convert the
           first l chars to an integer... */
        for(d=s=0,n=atoi(strncpy(b,p=v[1],++l)),p+=l;*p&&s<2;)
            /* If the next number is missing, then skip, otherwise
               move forward in the string.... */
            p+=memcmp(p,b,c=sprintf(b,"%d",++n))?d=n,s++:c;

    printf("%d",d); /* print the missing number */
}
share|improve this answer
2  
How does this work for inputs like 891112 where the numbers have different lengths? – Zgarb Feb 16 at 23:10
    
@Zgarb It works just fine. The sprintf call returns the length of the missing number, regardless if it's longer than the previous or not. – Cole Cameron Feb 17 at 11:20
    
Ok, thanks! Have a +1. – Zgarb Feb 17 at 15:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.