Group Integers by Originality

Question

Introduction:

I collect twisty puzzles. Most twisty puzzles are produced and sold by Chinese companies. Most well-known companies ask permission from puzzle designers to produce their designs and work together towards a product on the market. In this case, puzzle designers are of course very happy and proud that one of their puzzles hit the market.

There are however also Chinese companies which make knock-off puzzles. These knock-offs are either designs used without permission from the original creator, or are downright cheaper lower quality copies of already existing puzzles.

Challenge:

We're going to determine the originality of numbers that are 'released' in a specific order (from left to right^†).
Given a list of integers, group and output them by their originality.

How is the originality of the numbers determined?

• Is a number an exact duplicate of an earlier number? Group \$X+1\$ (least original), where group \$X+1\$ is trailing, after all the other groups.
• Is a number a duplicate of an earlier number, but its negative instead (i.e. original number was \$n\$, but now \$-n\$; or vice-versa)? Group \$X\$.
• Can the absolute value of the number be formed by concatenating one or more earlier absolute numbers, and is it not part of the earlier mentioned groups \$X+1\$ or \$X\$? Group \$X-N\$, where \$N\$ is the amount of distinct numbers used in the concatenation (and \$N\geq1\$).
• Does the number not fit in any of the groups above, so is completely unique thus far? Group \$1\$ (most original), which is leading before all other groups.

This may sound pretty vague, so here a step-by-step example:

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

• 34 is the first number, which is always original and in group \$1\$. Output thus far: [[34]]
• 9 is also original: [[34,9]]
• 4 is also original: [[34,9,4]]
• -34 is the negative of the earlier number 34, so it's in group \$X\$: [[34,9,4],[-34]]
• 19 is original: [[34,9,4,19],[-34]]
• -199 can be formed by the two earlier numbers 19 and 9, so it's in group \$X-2\$: [[34,9,4,19],[-199],[-34]]
• 34 is an exact copy of an earlier number, so it's in group \$X+1\$: [[34,9,4,19],[-199],[-34],[34]]
• -213 is original: [[34,9,4,19,-213],[-199],[-34],[34]]
• 94 can be formed by the two earlier numbers 9 and 4, so it's in group \$X-2\$: [[34,9,4,19,-213],[-199,94],[-34],[34]]
• 1934499 can be formed by the four earlier numbers 19, 34, 4, and two times 9, so it's in group \$X-4\$: [[34,9,4,19,-213],[19499],[-199,94],[-34],[34]]
• 213 is the negative of the earlier number -213, so it's in group \$X\$: [[34,9,4,19,-213],[1934499],[-199,94],[-34,213],[34]]
• 3 is original: [[34,9,4,19,-213,3],[1934499],[-199,94],[-34,213],[34]]
• 21 is original: [[34,9,4,19,-213,3,21],[1934499],[-199,94],[-34,213],[34]]
• -2134 can be formed by the two earlier numbers 213 and 4 (or the three earlier numbers 21, 3, and 4, but we always use the least amount of concatenating numbers to determine originality), so it's in group \$X-2\$: [[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134],[-34,213],[34]]
• 44449 can be formed by the two earlier numbers four times 4 and 9, so it's in group \$X-2\$: [[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[-34,213],[34]]
• 44 can be formed by a single earlier number 4, repeated two times, so it's in group \$X-1\$: [[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[44],[-34,213],[34]]

So for input [34,9,4,-34,19,-199,34,-213,94,1934499,213,3,21,-2134,44449,44] the output is [[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[44],[-34,213],[34]].

Challenge rules:

• I/O is flexible. You can input as a list/array/stream of integers or strings, input them one by one through STDIN, etc. Output can be a map with the groups as key, a nested list as the example and test cases in this challenge, printed newline separated, etc.
• You are allowed to take the input-list in reversed order (perhaps useful for stack-based languages). ^†In which case the mentioned left-to-right is of course right-to-left.
• As you can see at the example for integer -2134, we always group a number that is a concatenation of other numbers with as few as possible (formed by 213 and 4 - two numbers; and not by 21, 3, and 4 - three numbers).
• As you can see at the example for integer 1934499, you can use an earlier number (the 9 in this case) multiple times (similar with 44449 using four 4s and a 9 in the example). They are only counted once for determining the group however.
• You are not allowed to have empty inner lists in the output for empty groups. So test case [1,58,85,-8,5,8585,5885,518] may not result in [[1,58,85,8,5],[518],[5885],[8585],[],[]] instead, where the empty groups are \$X\$ and \$X-1\$, and the example above may not result in [[34,9,4,19,-213,3,21],[1934499],[],[-199,94,-2134,44449],[44],[-34,213],[34]] instead, where the empty group is \$X-3\$.
• The order of the groups are strict (unless you use a map, since the groups can then be deducted from the keys), but the order of the numbers within a group can be in any order. So the [34,9,4,19,-213,3,21] for group \$1\$ in the example above can also be [21,3,-213,19,4,9,34] or [-213,4,34,19,9,21,3].
• You are guaranteed that there will never be any numbers that can be formed by more than nine previous numbers. So you will never have any \$X-10\$ groups, and the largest amount of groups possible is 12: \$[1,X-9,X-8,...,X-2,X-1,X,X+1]\$
• You can assume the integers will be 32 bits at max, so within the range [−2147483648,2147483647].

General rules:

• This is code-golf, so shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (i.e. TIO).
• Also, adding an explanation for your answer is highly recommended.

Test cases:

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]]

Answer 1

Jelly, 36 33 bytes

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

Try it online!

I’m sure this can be golfed more. Some inspiration taken from Grimy’s 05AB1E answer, so be sure to upvote that one too!

Answer 2

Python 3, 565 564 524 523 500 437 399 394 393 389 385 372 bytes

Brute-force implementation using itertools; not all test-cases run within the 60 second limit on TIO.

Try it online!

Thanks to ArBo for golfing 101 bytes, to Galen Ivanov for golfing 19 bytes, to ElPedro for golfing 5 bytes, to movatica for golfing 17 bytes, to Black Owl Kai for golfing 2 bytes, to squid for golfing 2 bytes and to Kevin Cruijssen for golfing 1 byte.

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

Explanation:

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 bytes

Same approach, but shorter due to some golfing tricks Python 3 doesn't support any more. Thanks to ArBo for the backport and for golfing 28 bytes, to ElPedro for golfing 5 bytes, to movatica for golfing 17 bytes, and to squid for golfing 1 more byte.

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)

Try it online!

Answer 3

05AB1E, 43 41 38 35 27 bytes

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

Try it online!

Explanation:

.¡                              # 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

Since group numbers aren't part of the output, we're free to use any numbers we want, as long as the order is correct. This uses 0 for original numbers, 2^-N for group X-N, 1 for group X, 2 for group X+1.

Answer 4

Python 2, 235 234 232 246 245 244 241 240 238 237 236 bytes

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)

Try it online!

-1 byte thanks to Squid's comment on the other Python answer

This answer has no hopes of solving any but the most trivial of test cases. In the TIO link, s*11 has been replaced by s*2, sacrificing correctness in some cases for faster execution time, but as far as I can see, the version in this post always yields the correct answer, in theory.

Explanation

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

Answer 5

Python 2, 195 bytes

The slowest test case can't complete on TIO, but it only takes about 10 seconds on my machine.

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)

It can be shortened by 2 bytes on LP64 Python builds by replacing '%s-%%s'%a%n with `a`+'-'+`n`.

Answer 6

JavaScript (Node.js), 211 205 bytes

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)

Try it online!

Using the assumption that there are at most 12 groups.

JavaScript (Node.js), 267 226 221 218 211 bytes

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)

Try it 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

... or 193 bytes if returning a dictionary is okay:

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

Try it online!

In this case, key -Infinity means Group 1 and other keys means Group X+key.