11
0
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 number34
, 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 numbers19
and9
, 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 numbers9
and4
, so it's in group \$X-2\$:[[34,9,4,19,-213],[-199,94],[-34],[34]]
1934499
can be formed by the four earlier numbers19
,34
,4
, and two times9
, 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 numbers213
and4
(or the three earlier numbers21
,3
, and4
, 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 times4
and9
, 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 number4
, 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 by213
and4
- two numbers; and not by21
,3
, and4
- three numbers). - As you can see at the example for integer
1934499
, you can use an earlier number (the9
in this case) multiple times (similar with44449
using four4
s and a9
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]]
So
X + 1
is a special group for exact copies, andX
is a group for other numbers that can be formed from copies of a single number, such as its negation? – Neil – 2019-06-05T12:43:35.460@Neil
X+1
is indeed for exact copies,X
is for negative (exact) numbers, andX-1
is for numbers that can be formed from multiple copies of a single number (i.e.444
from three earlier4
),X-2...X-9
is for numbers that can be formed by 2..9 of the previous numbers with one or multiple copies each, and group1
is for truly unique / original numbers. – Kevin Cruijssen – 2019-06-05T12:50:23.953Are there any limits on how many copies of a number can constitute another? Would, for example,
[4, 444444444444444]
be a valid input? – ArBo – 2019-06-05T18:02:19.1031@ArBo Let's assume the integers are maximum 32 bits, so in the range $[-2147483648, 2147483647]$. So your example is not a valid input, but
[1, 1111111111]
is possible. – Kevin Cruijssen – 2019-06-05T18:18:30.887If we output as a map with keys, do they still have to be in order? – Embodiment of Ignorance – 2019-06-06T03:10:19.773
@EmbodimentofIgnorance No, if they have map-key the order can be deducted from those. So if, in for example Java, you use a HashMap (simple map) instead of a TreeMap (map sorted by keys) then that's fine. – Kevin Cruijssen – 2019-06-06T07:14:38.720
1Being a collector myself: that's a damn fine collection you got there, Kevin. Very nice indeed. – J. Sallé – 2019-06-07T13:29:50.370
@J.Sallé Thanks. :) You collect twisty puzzles as well? Or a collector in general? – Kevin Cruijssen – 2019-06-07T13:53:25.297
1I collect Magic: The Gathering cards and sets, which still occupy a suprisingly big amount of space even though they're fairly small. – J. Sallé – 2019-06-07T13:56:18.930
1
@J.Sallé Oh, I know the feeling. I also collect Pokémon TCG cards (and actually have the second largest Pikachu TCG collection in the world with more than 1200 unique Pikachu cards).. When you have over 9,000 cards it indeed takes up quite a bit of space. Not as much as the puzzles, though. Only 1.5 shelves instead of 10. ;p
– Kevin Cruijssen – 2019-06-07T17:08:16.903