Znajdź brakującą liczbę w nielimitowanym ciągu

19

Wyzwanie polega na zidentyfikowaniu brakującej liczby w ciągu nieokreślonych liczb całkowitych.

Otrzymujesz ciąg cyfr (prawidłowe dane wejściowe będą pasować do wyrażenia regularnego ^[1-9][0-9]+$). Ciąg reprezentuje ciąg liczb całkowitych. Na przykład 1234567891011. Wszystkie liczby w sekwencji są w zakresie od 1i 2147483647włącznie.

Sekwencja jest ciągiem liczb, w których każda liczba jest o jeden większa od swojego poprzednika. Jednak ta sekwencja może zawierać jedną i tylko jedną brakującą liczbę z sekwencji. Możliwe, że dany ciąg nie zawiera również brakujących liczb w sekwencji. Ciąg zawsze będzie zawierał co najmniej dwie liczby z sekwencji.

Kod musi wygenerować lub zwrócić brakującą wartość lub 0(to 0nie jest wartość fałsz) w przypadku, gdy nie znaleziono brakujących wartości.

Poniżej przedstawiono prawidłowe dane wejściowe i ich wynik / zwrot:

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  

Chociaż wszystko to jest opisane jako „ciąg” jako dane wejściowe, jeśli język jest w stanie obsłużyć dowolnie duże liczby ( dci mathematica, patrzę na was dwoje), wejściem może być dowolnie duża liczba zamiast łańcucha, jeśli to powoduje kod łatwiejszy.

Dla porównania, zostało to zainspirowane pytaniem Programmers.SE: Znajdź brakującą liczbę w sekwencji w ciągu

Społeczność
źródło
4
Czy jesteś pewien, że jest to jednoznaczne?
Martin Ender
@ MartinBüttner Trochę o tym myślałem i nie byłem w stanie wymyślić sytuacji, w której sekwencja rosnąca o 1 (to może być problem) ma niejednoznaczną sytuację.
Czy istnieje wpis w OEIS dla listy liczb całkowitych, które są połączoną sekwencją, w której brakuje dokładnie jednego elementu?
mbomb007
@ mbomb007 Nie sądzę, ponieważ istnieje nieskończenie wiele różnych list. I że jest to tylko jeden duży ciąg znaków. Nie jestem pewien, jak to zdefiniujesz. W związku z tym interesującym pytaniem CS byłoby „jaki język akceptuje wszystkie te ciągi znaków”. To z pewnością nie jest regularne. Wątpię w jego CF.
1
Sekwencję uczyniłem przedmiotem wyzwania: codegolf.stackexchange.com/q/73513/34718
mbomb007

Odpowiedzi:

5

Haskell, 115 112 bajtów

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

Pierwsza linia to definicja funkcji pomocniczej, druga to główna funkcja anonimowa. Sprawdź przypadki testowe (musiałem przeprowadzić krótsze testy z powodu ograniczeń czasowych).

Wyjaśnienie

Jest to rozwiązanie z użyciem siły brute: podziel łańcuch na słowa na wszystkie możliwe sposoby, parsuj słowa do liczb całkowitych, sprawdź, czy jest to zakres z brakującym jednym elementem (zwracając ten element itp. 0), I weź maksimum dla wszystkich podziałów. Sprawdzanie zakresu z brakującym elementem jest wykonywane w funkcji pomocnika g, która pobiera listę bi zwraca jedyny element z zakresu, [head of b..last of b]który nie jest w zasięgu blub 0jeśli nie istnieje.

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
źródło
2

JavaScript (ES6), 117 bajtów

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

Wyjaśnienie

Dość wydajne podejście. Kończy się natychmiast dla wszystkich przypadków testowych.

Pobiera każdy podciąg od początku ciągu wejściowego jako liczbę ni inicjuje brakującą liczbę mna 0. Następnie kilkakrotnie usuwa npoczątek łańcucha, inkrementuje ni wyszukuje go. Jeśli index of n != 0to sprawdzi m. Jeśli m == 0ustaw m = ni kontynuuj, jeśli nie, istnieje wiele brakujących liczb, więc przestań sprawdzać z tego podłańcucha. Proces ten trwa do momentu usunięcia całego łańcucha.

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>

użytkownik 81655
źródło
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")  

Mniej golfa i wyjaśnienia

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>

edc65
źródło
2

C 183 168 166 163 bajtów

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

Nie golfił

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
źródło
2
Jak to działa w przypadku danych wejściowych, np. 891112Gdzie liczby mają różne długości?
Zgarb
@Zgarb Działa dobrze. sprintfWywołanie zwraca długość brakującej liczby, niezależnie czy jest to dłużej niż poprzedni, czy nie.
Cole Cameron
Ok dzięki! Masz +1.
Zgarb