Find the missing number in an undelimited string
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)
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 */
}
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>