Trouver le nombre manquant dans une chaîne non délimitée

19

Le défi consiste à identifier le nombre manquant dans une chaîne d'entiers non délimités.

Vous recevez une chaîne de chiffres (une entrée valide correspondra à l'expression régulière ^[1-9][0-9]+$). La chaîne représente une séquence d'entiers. Par exemple 1234567891011,. Tous les nombres de la séquence sont compris entre 1et 2147483647inclus.

La séquence est une série de nombres où chaque nombre est supérieur de un à son prédécesseur. Cependant, cette séquence peut contenir un et un seul numéro manquant dans la séquence. Il est possible qu'une chaîne donnée ne contienne également aucun nombre manquant dans la séquence. La chaîne contiendra toujours au moins deux nombres de la séquence.

Le code doit générer ou renvoyer la valeur manquante, ou 0(il s'agit d'une valeur 0- pas une valeur fausse) dans le cas où aucune valeur manquante n'a été trouvée.

Les entrées suivantes sont valides et leur sortie / retour:

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  

Bien que tout cela soit décrit comme une `` chaîne '' en entrée, si la langue est capable de gérer des nombres arbitrairement grands ( dcet mathematica, je vous regarde tous les deux), l'entrée peut être un nombre arbitrairement grand au lieu d'une chaîne si cela fait le code plus facile.

Pour référence, cela a été inspiré par la question Programmers.SE: trouver le numéro manquant dans la séquence dans la chaîne

Communauté
la source
4
Êtes-vous sûr que cela n'est pas ambigu?
Martin Ender
@ MartinBüttner J'y ai réfléchi un peu et je n'ai pas réussi à trouver une situation où une séquence augmentant de 1 (cela pourrait être le problème) a une situation ambiguë.
Existe-t-il une entrée dans OEIS pour la liste des entiers qui sont une séquence concaténée manquant exactement un élément?
mbomb007
@ mbomb007 Je ne pense pas, car il existe une infinité de listes différentes. Et que ce n'est qu'une seule grosse chaîne ole. Je ne sais pas comment vous le définiriez. D'ailleurs, une question CS intéressante serait "quel est le langage qui accepte toutes ces chaînes". Ce n'est certainement pas régulier. Je doute de son CF.
1
J'ai fait de la séquence l'objet d'un défi: codegolf.stackexchange.com/q/73513/34718
mbomb007

Réponses:

5

Haskell, 115 112 octets

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:" "])

La première ligne est une définition de fonction d'assistance, la seconde est la fonction anonyme principale. Vérifiez les cas de test (j'ai dû exécuter des tests plus courts en raison de contraintes de temps).

Explication

Il s'agit d'une solution de force brute: divisez la chaîne en mots de toutes les manières possibles, analysez les mots en nombres entiers, voyez s'il s'agit d'une plage avec un élément manquant (renvoyant cet élément, ou 0autre), et prenez le maximum sur toutes les séparations. La vérification de la plage avec les éléments manquants est effectuée dans la fonction d'assistance g, qui prend une liste bet renvoie le seul élément de la plage [head of b..last of b]qui ne se trouve pas b, ou 0s'il n'existe pas.

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)
Zgarb
la source
2

JavaScript (ES6), 117 octets

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`)

Explication

Approche assez efficace. Finit instantanément pour tous les cas de test.

Obtient chaque sous-chaîne depuis le début de la chaîne d'entrée sous forme de nombre net initialise le nombre manquant mà 0. Il supprime ensuite à plusieurs reprises ndepuis le début de la chaîne, incrémente net recherche la chaîne. Si index of n != 0, il vérifie m. Si m == 0, définissez m = net continuez, sinon, il y a plusieurs nombres manquants, alors arrêtez de vérifier à partir de cette sous-chaîne. Ce processus se poursuit jusqu'à ce que la chaîne entière ait été supprimée.

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>

user81655
la source
2

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")  

Moins golfé et expliqué

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
}

Tester

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>

edc65
la source
2

C, 183 168 166 163 163 octets

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);}

Non golfé

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 */
}
Cole Cameron
la source
2
Comment cela fonctionne-t-il pour des entrées comme 891112lorsque les nombres ont des longueurs différentes?
Zgarb
@Zgarb Cela fonctionne très bien. L' sprintfappel renvoie la longueur du numéro manquant, qu'il soit plus long que le précédent ou non.
Cole Cameron
OK merci! Avoir un +1.
Zgarb