Wprowadzenie:

Zbieram kręte puzzle. Większość krętych łamigłówek jest produkowanych i sprzedawanych przez chińskie firmy. Większość znanych firm prosi projektantów puzzli o pozwolenie na opracowanie ich projektów i współpracę nad produktem na rynku. W tym przypadku projektanci puzzli są oczywiście bardzo szczęśliwi i dumni, że jedna z ich łamigłówek trafiła na rynek.

Są jednak także chińskie firmy, które układają puzzle. Te podróbki są albo projektami używanymi bez zgody oryginalnego twórcy, albo są po prostu tańszymi kopiami niższej jakości już istniejących łamigłówek.

Wyzwanie:

Zamierzamy ustalić oryginalność liczb, które są „wypuszczane” w określonej kolejności (od lewej do prawej ^† ).
Biorąc pod uwagę listę liczb całkowitych, pogrupuj i wyślij je według ich oryginalności.

Jak określa się oryginalność liczb?

• Czy liczba jest dokładnym duplikatem wcześniejszej liczby? Grupa $X+1$ (najmniej oryginalna), po której następuje grupa $X+1$ , po wszystkich pozostałych grupach.
• Czy liczba jest duplikatem wcześniejszej liczby, ale zamiast tego jest ujemna (tzn. Pierwotna liczba to $n$ , ale teraz $-n$ ; lub odwrotnie)? Grupa $X$ .
• Czy wartość bezwzględna liczby może być utworzona przez połączenie jednej lub więcej wcześniejszych liczb bezwzględnych i czy nie jest ona częścią wcześniej wymienionych grup $X+1$ lub $X$ ? Grupa $X-N$ , gdzie $N$ jest liczbą wyraźnych liczb użytych w konkatenacji (i $N\geq1$ ).
• Czy liczba nie mieści się w żadnej z powyższych grup, więc jest jak dotąd całkowicie unikalna? Grupa $1$ (najbardziej oryginalna), która prowadzi przed wszystkimi innymi grupami.

Może to zabrzmieć dość ogólnikowo, więc oto przykład krok po kroku :

Lista wejściowa: [34,9,4,-34,19,-199,34,-213,94,1934499,213,3,21,-2134,44449,44]

• 34to pierwszy numer, który jest zawsze oryginalny i należy do grupy $1$ . Dotychczasowe wyniki:[[34]]
• 9 jest również oryginalny: [[34,9]]
• 4 jest również oryginalny: [[34,9,4]]
• -34jest ujemną liczbą wcześniejszą 34, więc należy do grupy $X$ :[[34,9,4],[-34]]
• 19 jest oryginalny: [[34,9,4,19],[-34]]
• -199mogą być utworzone przez dwie wcześniejsze liczby, 19a 9więc należy do grupy $X-2$ :[[34,9,4,19],[-199],[-34]]
• 34jest dokładną kopią wcześniejszego numeru, więc należy do grupy $X+1$ :[[34,9,4,19],[-199],[-34],[34]]
• -213 jest oryginalny: [[34,9,4,19,-213],[-199],[-34],[34]]
• 94mogą być utworzone przez dwie wcześniejsze liczby, 9a 4więc należy do grupy $X-2$ :[[34,9,4,19,-213],[-199,94],[-34],[34]]
• 1934499może być utworzone przez cztery wcześniej liczby 19, 34, 4i dwa razy 9, to jest w grupie $X-4$ :[[34,9,4,19,-213],[19499],[-199,94],[-34],[34]]
• 213jest ujemną liczbą wcześniejszą -213, więc należy do grupy $X$ :[[34,9,4,19,-213],[1934499],[-199,94],[-34,213],[34]]
• 3 jest oryginalny: [[34,9,4,19,-213,3],[1934499],[-199,94],[-34,213],[34]]
• 21 jest oryginalny: [[34,9,4,19,-213,3,21],[1934499],[-199,94],[-34,213],[34]]
• -2134mogą być utworzone przez dwie wcześniejsze liczby 213i 4(lub trzy wcześniejsze liczby 21, 3i 4, ale zawsze używamy najmniejszej liczby liczb łączących w celu ustalenia oryginalności), więc znajduje się w grupie $X-2$ :[[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134],[-34,213],[34]]
• 44449mogą być czterokrotnie utworzone przez dwie wcześniejsze liczby, 4a 9więc należy do grupy $X-2$ :[[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[-34,213],[34]]
• 44może być utworzony przez jedną wcześniejszą liczbę 4, powtórzoną dwa razy, więc jest w grupie $X-1$ : [[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[44],[-34,213],[34]]

Tak więc dla danych [34,9,4,-34,19,-199,34,-213,94,1934499,213,3,21,-2134,44449,44]wyjściowych jest to [[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[44],[-34,213],[34]].

Zasady konkursu:

• I / O jest elastyczny. Możesz wprowadzić jako listę / tablicę / strumień liczb całkowitych lub ciągów, wprowadzić je jeden po drugim poprzez STDIN itp. Wyjściem może być mapa z grupami jako kluczem, zagnieżdżona lista jako przykład i przypadki testowe w tym wyzwaniu, wydrukowane znak nowej linii oddzielony itp.
• Możesz wziąć listę wprowadzania w odwrotnej kolejności (być może przydatne w przypadku języków opartych na stosie). ^† W takim przypadku wspomniany od lewej do prawej jest oczywiście od prawej do lewej.
• Jak widać na przykład na liczbę całkowitą -2134, zawsze grupa numer, który jest połączeniem inne numery z tak mało, jak to możliwe (tworzone przez 213i 4- dwa numery, a nie 21, 3oraz 4- trzy numery).
• Jak widać na przykładzie liczby całkowitej 1934499, możesz użyć wcześniejszej liczby ( 9w tym przypadku) wiele razy (podobnie w przypadku 44449użycia czterech 4si 9w tym przykładzie). Są one jednak liczone tylko raz w celu ustalenia grupy.
• Nie możesz mieć pustych wewnętrznych list w wynikach dla pustych grup. Zatem przypadek testowy [1,58,85,-8,5,8585,5885,518]może nie dać wyniku [[1,58,85,8,5],[518],[5885],[8585],[],[]], gdzie puste grupy to $X$ i $X-1$ , a powyższy przykład może nie dać wyniku [[34,9,4,19,-213,3,21],[1934499],[],[-199,94,-2134,44449],[44],[-34,213],[34]], gdy pusta grupa to $X-3$ .
• Kolejność grup jest ścisła (chyba że korzystasz z mapy, ponieważ grupy można następnie odjąć od kluczy), ale kolejność liczb w grupie może być w dowolnej kolejności. Tak więc [34,9,4,19,-213,3,21]dla grupy $1$ w powyższym przykładzie może być również [21,3,-213,19,4,9,34]lub [-213,4,34,19,9,21,3].
• Masz gwarancję, że nigdy nie będzie żadnych liczb, które mogłyby być utworzone z więcej niż dziewięciu poprzednich liczb. Więc nigdy nie będzie miał żadnego $X-10$ grup, a największą ilość grup możliwe jest 12: $[1,X-9,X-8,...,X-2,X-1,X,X+1]$
• Możesz założyć, że liczby całkowite będą miały maksymalnie 32 bity, więc w tym zakresie [−2147483648,2147483647].

Główne zasady:

• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.
  Nie pozwól, aby języki kod-golfowe zniechęcały Cię do publikowania odpowiedzi w językach niekodujących golfa. Spróbuj znaleźć możliwie najkrótszą odpowiedź na „dowolny” język programowania.
• Do odpowiedzi mają zastosowanie standardowe reguły z domyślnymi regułami We / Wy , więc możesz używać STDIN / STDOUT, funkcji / metody z odpowiednimi parametrami i typem zwracanych, pełnych programów. Twoja decyzja.
• Domyślne luki są zabronione.
• Jeśli to możliwe, dodaj link z testem kodu (tj. TIO ).
• Zalecane jest również dodanie wyjaśnienia do odpowiedzi.

Przypadki testowe:

Input:  [34,9,4,-34,19,-199,34,-213,94,1934499,213,3,21,-2134,44449,44]
Output: [[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[44],[-34,213],[34]]

Input:  [17,21,3,-317,317,2,3,117,14,-4,-232,-43,317]
Output: [[17,21,3,2,117,14,-4],[-317,-232,-43],[317],[3,317]]

Input:  [2,4,8,10,12,-12,-102,488,10824]
Output: [[2,4,8,10,12],[10824],[-102,488],[-12]]

Input:  [0,100,-100,10000,-100,1001000]
Output: [[0,100],[10000,1001000],[-100],[-100]]

Input:  [1,58,85,-8,5,8585,5885,518]
Output: [[1,58,85,-8,5],[518],[5885],[8585]]

Input:  [4,-4,44,5,54]
Output: [[4,5],[54],[44],[-4]]

Galaretka , 36 33 bajtów

ADṪŒṖfƑƇƊQ€Ẉ.*;,AṪe$€SƲṀµƤż⁸ṢZ¹ƙ/

Wypróbuj online!

Jestem pewien, że można więcej grać w golfa. Trochę inspiracji zaczerpnąłem z odpowiedzi Grimy'ego 05AB1E , więc pamiętajcie o tym!

Python 3 , 565 564 524 523 500 437 399 394 393 389 385 372 bajtów

Brute-force wdrożenie przy użyciu itertools; nie wszystkie przypadki testowe działają w ramach 60-sekundowego limitu TIO.

Wypróbuj online!

Dzięki ArBo za grę w golfa 101 bajtów, Galena Iwanowa za grę w golfa 19 bajtów, ElPedro za grę w golfa 5 bajtów, Movatica za grę w golfa 17 bajtów, Black Owl Kai za grę w golfa 2 bajty, kałamarnicy za grę w golfa 2 bajty i Kevina Cruijssena za gra w golfa 1 bajt.

from itertools import*
w=permutations
def c(l,x):
 for i in range(9):
  for q in w(map(abs,sum(l,[]))):
   for s in w(q[:i+1]*len(x)):
    z='';s=[*s]
    while x[len(z):]:
     z+=str(s.pop(0))
     if z==x:return 9-i
 return 0
def f(a):
 l=[[]for _ in a*6]
 for x in a:l[(x in sum(l,[]))*11or(-x in sum(l,[]))*10or any(l)and c(l,str(abs(x)))]+=x,
 return[*filter(len,l)]

Wyjaśnienie:

from itertools import *
w = permutations  # We'll be using this twice

def c  # Helper function to calculate which group a number belongs in according to the concatenation rule; returns 0 (original) if none is found
(l, x):  # First parameter is the list of groups (a list of lists of numbers), second parameter is the number to investigate
 for i in range(9):  # There won't be any concatenations of more than 9 elements
  for q in w(map(abs,sum(l,[]))):  # Flatten l to get a plain list of previous numbers, then generate permutations of their absolute values as lists; for each permutation ...
   for s in w(q[:i+1]*len(x)):  # ... use only the first i + 1 elements; inflate the list with enough copies to compose the target number and permutate; then try to compose the target number from each permutation:
    z = ''  # Start with the empty string
    s = [*s]  # Convert permutation to list
    while x[len(z):]:  # Keep going until the length of the concatenated string equals the length of the target number
     z += str(s.pop(0))  # Concatenate the first element of the current permutation list and remove it
     if z == x:  # If the target number has been synthesized successfully ...
      return 9 - i  # stop searching and return the appropriate group
 return 0  # If no concatenation has been found, consider the number original

def f(a):  # Solution function, takes a list of numbers as argument
 l = [[] for _ in a * 6]  # Populate the result list with at least 12 empty groups if there is more than one number in the input (we'll be using only the first 12 and removing empty ones later); if there is just one, we'll only need one group in the output
 for x in a:  # For each number in order:
  l[(x in sum(l, [])) * 11 or (-x in sum(l, [])) * 10 or any(l) and c(l, str(abs(x)))] += x,  # If x is not the first number, attempt concatenation (if not, c(l, str(abs(x))) would crash due to l not containing any non-empty sublists; use absolute value of the number under investigation; convert to string since we'll be needing the number of digits and comparing it to a string later); if -x has already been seen, put it in Group X; if x has already been seen, put it in Group X + 1
  return [* filter(len, l)]  # Remove empty lists and return the result

Python 2 , 406 379 374 373 372 368 355 bajtów

To samo podejście, ale krótsze z powodu niektórych sztuczek golfowych Python 3 nie obsługuje już. Dzięki ArBo za backport i grę w golfa 28 bajtów, ElPedro za grę w golfa 5 bajtów, Movatica za grę w golfa 17 bajtów i kałamarnicę za grę w golfa jeszcze 1 bajt.

from itertools import*
w=permutations
def c(l,x):
 for i in range(9):
  for q in w(map(abs,sum(l,[]))):
	for s in map(list,w(q[:i+1]*len(x))):
	 z=''
	 while x[len(z):]:
		z+=`s.pop(0)`
		if z==x:return 9-i
 return 0
def f(a):
 l=[[]for _ in a*6]
 for x in a:l[(x in sum(l,[]))*11or(-x in sum(l,[]))*10or any(l)and c(l,`abs(x)`)]+=x,
 return filter(len,l)

Wypróbuj online!

Python 2 , 235 234 232 246 245 244 241 240 238 237 236 bajtów

from itertools import*
s=[];r=map(list,[s]*12)
for e in input():r[-(e in s)or max([10*(-e in s)]+[10-len(set(p[:i]))for p in permutations(`abs(x)`for x in s*11)for i in range(len(p))if''.join(p[:i])==`e`])]+=e,;s+=e,
print filter(len,r)

Wypróbuj online!

-1 bajt dzięki komentarzowi Squid do drugiej odpowiedzi w języku Python

Ta odpowiedź nie ma nadziei na rozwiązanie żadnego z najbardziej trywialnych przypadków testowych. W związku tio s*11został zastąpiony s*2, poświęcając prawidłowości w niektórych przypadkach do szybkiego er czasu wykonywania, ale o ile widzę, wersja w tym poście zawsze teoretycznie daje poprawną odpowiedź.

Wyjaśnienie

from itertools import*          # So that we can abuse permutations
s=[];                           # s will hold the already classified numbers
r=map(list,[s]*12)              # r will hold these too, but in the form of
                                #  a nested list, sorted by originality
for e in input():               # Here comes the big one; iterate over the input
 r[-(e in s)or                  # If e has already passed, it is not original
   max([10*(-e in s)]+          # Else, we count 10 - the number of seen elements
                                #  needed to make this one, or 0 if it's new,
                                #  or 10 if its inverse has already passed
   [10-len(set(p[:i]))          # The number of distinct elements in...
    for p in permutations(      #  for each permutation of the seen elements,
      `abs(x)`for x in s*11)
                                #  with values occuring up to 10 times (to
                                #  account for 1111111111, for example;
                                #  we need 11 here and not 10, because
                                #  p[:i] doesn't include i)...
    for i in range(len(p))      #  each prefix...
    if''.join(p[:i])            #  only if its concatenation is equal to
      ==`e`])]                  #  the current element
 +=e,;s+=e,                     # Append the element to the relevant lists
print filter(len,r)             # And finally, print the non-empty result lists

05AB1E , 43 41 38 35 27 bajtów

.¡IN£UÄ.œεgΘ>XÄyÙå;P*}àXyå+

Wypróbuj online!

Wyjaśnienie:

.¡                              # group by:
  IN£                           #  first N elements of the input, N being the iteration count
     U                          #  store this as X
  Ä                             #  absolute value of the current number
   .œ                           #  partitions (eg 449 => [[4, 4, 9], [44, 9], [4, 49], [449]])
     ε             }            #  map each partition to:
      gΘ>                       #   2 if length = 1, 1 otherwise
           yÙ                   #   for each unique element in the current partition:
         XÄ  å                  #    1 if it's in the absolute value of X, 0 otherwise
              ;                 #   divide all by 2
               P*               #   product of all these numbers
                  à             #  take the maximum
                   Xyå+         #  add 1 if X contains the current number

Ponieważ numery grup nie są częścią danych wyjściowych, możemy dowolnie używać dowolnych liczb, o ile kolejność jest prawidłowa. Używa 0 dla oryginalnych liczb, 2 ^ -N dla grupy XN, 1 dla grupy X, 2 dla grupy X + 1.

Python 2, 195 bajtów

Najwolniejszego przypadku testowego nie można ukończyć na TIO , ale na moim komputerze zajmuje to tylko około 10 sekund.

import re
a=[()];m=a*99
for n in input():
    i=0;r='-('
    while i<10>re.search(r'(\b.+\b).+'*i+r+')+$','%s-%%s'%a%n):i+=1;r+='|\\'+`i`
    m[48*(n in a)|32*(-n in a)|14-i]+=n,;a+=n,
print filter(len,m)

To może być skrócony o 2 bajty na LP64 Python buduje zastępując '%s-%%s'%a%nz `a`+'-'+`n`.

JavaScript (Node.js) , 211 205 bajtów

a=>a.map(s=>(c[q=(G=(n,r=[],A=Math.abs,N=""+A(s))=>N[L="length"]<n[L]?0:N!=n?Math.max(0,...c.flat().map(x=>G(n+A(x),[...r,x]))):1/r?s-r?11:12:12+~new Set(r).size)``]=c[q]||[]).push(s),c=[])&&c.filter(x=>x)

Wypróbuj online!

Przy założeniu, że istnieje maksymalnie 12 grup.

JavaScript (Node.js) , 267 226 221 218 211 bajtów

a=>a.map(s=>(c[q=(G=(n,r=[],A=Math.abs,N=""+A(s))=>N[L]<n[L]?0:N!=n?Math.max(0,...c.flat().map(x=>G(n+A(x),[...r,x]))):1/r?l-(s!=+r):l+~new Set(r).size)``]=c[q]||[]).push(s),c=[],l=a[L="length"])&&c.filter(x=>x)

Wypróbuj online!

a=>a.map(                       // Iterate through all items:
 s=>(c[q=(
  G=(                           //  Helper function to calculate index (=GroupNo-1):
   n,                           //   Stores different (repeatable) permutations
   r=[],                        //   Stores the elements used
   A=Math.abs,
   N=""+A(s))                   //   Stores the string version of the absolute value
  =>
  N[L="length"]<n[L]?           //   If n is longer then N:
   0                            //    0 (Group 1) - no permutation found to equal the string
  :N!=n?                        //   Else if N!=n:
   Math.max(0,...c.flat().map(  //    Return max of the results of the next recursion
    x=>G(n+A(x),[...r,x])       //    for each of the elements in c
   ))
  :1/r?                         //   Else if r has only 1 item: (=+s/-s)
   s-r?11:12                    //    Return l-1 (Group X) if r=-s, and l (Group X+1) if r=s
  :12+~new Set(r).size          //   Else: return l-r.size-1 (Group X-r.size)
 )``]=c[q]||[]).push(s),        //  Push the element into the corresponding array
 c=[]                           //  Initialize an empty array
)&&c.filter(x=>x)               // Filter out all empty groups

... lub 193 bajtów, jeśli zwracanie słownika jest w porządku:

a=>a.map(c=s=>(c[q=(G=(n,r=[],A=Math.abs,N=""+A(s))=>N[L="length"]<n[L]?-1/0:N!=n?Math.max(...d.map(x=>G(n+A(x),[...r,x]))):1/r?+!(s-r):-new Set(r).size)``]=c[q]||[]).push(s)&d.push(s),d=[])&&c

Wypróbuj online!

W takim przypadku klucz -Infinityoznacza grupę 1, a pozostałe klucze oznaczają grupę X+key.