Gruppieren Sie Ganzzahlen nach Originalität

11

Einführung:

Ich sammle verdrehte Rätsel. Die meisten kurvenreichen Puzzles werden von chinesischen Unternehmen hergestellt und verkauft. Die meisten bekannten Unternehmen bitten Puzzle-Designer um Erlaubnis, ihre Designs zu produzieren und gemeinsam auf ein Produkt auf dem Markt hinzuarbeiten. In diesem Fall sind Puzzle-Designer natürlich sehr glücklich und stolz darauf, dass eines ihrer Puzzles auf den Markt kommt.

Es gibt jedoch auch chinesische Unternehmen, die Fälschungen herstellen. Bei diesen Nachahmungen handelt es sich entweder um Designs, die ohne Genehmigung des ursprünglichen Erstellers verwendet wurden, oder um deutlich billigere Kopien bereits vorhandener Rätsel von geringerer Qualität.

Herausforderung:

Wir werden die Originalität von Zahlen bestimmen, die in einer bestimmten Reihenfolge (von links nach rechts ) "freigegeben" werden .
Gruppieren und geben Sie anhand einer Liste von Ganzzahlen diese nach ihrer Originalität aus.

Wie wird die Originalität der Zahlen bestimmt?

  • Ist eine Zahl ein genaues Duplikat einer früheren Zahl? Gruppe (am wenigsten original), wobei Gruppe nach allen anderen Gruppen hinterherhinkt.X+1X+1
  • Ist eine Zahl ein Duplikat einer früheren Zahl, aber stattdessen negativ (dh die ursprüngliche Zahl war , aber jetzt ; oder umgekehrt)? Gruppe .nnX
  • Kann der Absolutwert der Zahl durch Verketten einer oder mehrerer früherer Absolutzahlen gebildet werden und gehört er nicht zu den zuvor genannten Gruppen oder ? Gruppe , wobei die Anzahl der in der Verkettung verwendeten unterschiedlichen Zahlen ist (und ).X+1XXNNN1
  • Passt die Nummer nicht in eine der oben genannten Gruppen, ist sie also bisher völlig eindeutig? Gruppe (am originellsten), die vor allen anderen Gruppen führend ist.1

Dies mag ziemlich vage klingen, daher hier ein schrittweises Beispiel :

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

  • 34ist die erste Nummer, die immer original ist und in Gruppe . Bisherige Ausgabe:1[[34]]
  • 9 ist auch original: [[34,9]]
  • 4 ist auch original: [[34,9,4]]
  • -34ist das Negativ der früheren Zahl 34, also in Gruppe :X[[34,9,4],[-34]]
  • 19 ist original: [[34,9,4,19],[-34]]
  • -199kann durch die zwei früheren Zahlen gebildet werden 19und 9ist daher in Gruppe :X2[[34,9,4,19],[-199],[-34]]
  • 34ist eine exakte Kopie einer früheren Nummer, also in Gruppe :X+1[[34,9,4,19],[-199],[-34],[34]]
  • -213 ist original: [[34,9,4,19,-213],[-199],[-34],[34]]
  • 94kann durch die zwei früheren Zahlen gebildet werden 9und 4ist daher in Gruppe :X2[[34,9,4,19,-213],[-199,94],[-34],[34]]
  • 1934499kann durch die vier früheren Nummern gebildet werden 19, 34, 4, und zwei Mal 9, so ist es in der Gruppe :X4[[34,9,4,19,-213],[19499],[-199,94],[-34],[34]]
  • 213ist das Negativ der früheren Zahl -213, also in Gruppe :X[[34,9,4,19,-213],[1934499],[-199,94],[-34,213],[34]]
  • 3 ist original: [[34,9,4,19,-213,3],[1934499],[-199,94],[-34,213],[34]]
  • 21 ist original: [[34,9,4,19,-213,3,21],[1934499],[-199,94],[-34,213],[34]]
  • -2134kann durch die zwei früheren Zahlen 213und 4(oder die drei früheren Zahlen 21, 3und gebildet werden 4, aber wir verwenden immer die geringste Anzahl an verkettenden Zahlen, um die Originalität zu bestimmen), also in Gruppe :X2[[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134],[-34,213],[34]]
  • 44449kann durch die zwei früheren Zahlen viermal gebildet werden 4und 9ist daher in Gruppe :X2[[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[-34,213],[34]]
  • 44kann durch eine einzelne frühere Zahl gebildet werden 4, die zweimal wiederholt wird, also in Gruppe : X1[[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[44],[-34,213],[34]]

Für die Eingabe ist [34,9,4,-34,19,-199,34,-213,94,1934499,213,3,21,-2134,44449,44]die Ausgabe also [[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[44],[-34,213],[34]].

Herausforderungsregeln:

  • E / A ist flexibel. Sie können als Liste / Array / Stream von Ganzzahlen oder Zeichenfolgen eingeben, diese einzeln über STDIN eingeben usw. Die Ausgabe kann eine Karte mit den Gruppen als Schlüssel, eine verschachtelte Liste als Beispiel und Testfälle in dieser Herausforderung sein, die gedruckt werden Newline getrennt usw.
  • Sie dürfen die Eingabeliste in umgekehrter Reihenfolge verwenden (möglicherweise nützlich für stapelbasierte Sprachen). In diesem Fall ist das erwähnte von links nach rechts natürlich von rechts nach links.
  • Wie Sie am Beispiel für integer sehen -2134wir immer Gruppe eine Zahl , die eine Verkettung von anderen Zahlen mit so wenig wie möglich ist (gebildet durch 213und 4- zwei Zahlen, und nicht durch 21, 3und 4- drei Zahlen).
  • Wie Sie im Beispiel für eine Ganzzahl sehen können 1934499, können Sie eine frühere Zahl ( 9in diesem Fall die mehrfache) mehrmals verwenden (ähnlich wie bei der 44449Verwendung von vier 4s und a 9im Beispiel). Sie werden jedoch nur einmal zur Bestimmung der Gruppe gezählt.
  • Sie dürfen keine leeren inneren Listen in der Ausgabe für leere Gruppen haben. Daher führt der Testfall [1,58,85,-8,5,8585,5885,518]möglicherweise nicht zu [[1,58,85,8,5],[518],[5885],[8585],[],[]]stattdessen, wenn die leeren Gruppen und , und das obige Beispiel führt möglicherweise nicht dazu , dass die leere Gruppe .XX1X - 3[[34,9,4,19,-213,3,21],[1934499],[],[-199,94,-2134,44449],[44],[-34,213],[34]]X3
  • Die Reihenfolge der Gruppen ist streng (es sei denn, Sie verwenden eine Karte, da die Gruppen dann von den Schlüsseln abgezogen werden können), aber die Reihenfolge der Zahlen innerhalb einer Gruppe kann in beliebiger Reihenfolge erfolgen. So kann die [34,9,4,19,-213,3,21]für Gruppe im obigen Beispiel auch oder sein .1[21,3,-213,19,4,9,34][-213,4,34,19,9,21,3]
  • Sie werden garantiert, dass es niemals Zahlen geben wird, die aus mehr als neun vorherigen Zahlen bestehen können. Sie werden also niemals Gruppen haben, und die größtmögliche Anzahl von Gruppen ist 12:X10[1,X9,X8,...,X2,X1,X,X+1]
  • Sie können davon ausgehen, dass die Ganzzahlen maximal 32 Bit betragen, also innerhalb des Bereichs [−2147483648,2147483647].

Allgemeine Regeln:

  • Dies ist , also gewinnt die kürzeste Antwort in Bytes.
    Lassen Sie sich nicht von Code-Golf-Sprachen davon abhalten, Antworten mit Nicht-Codegolf-Sprachen zu veröffentlichen. Versuchen Sie, eine möglichst kurze Antwort für "jede" Programmiersprache zu finden.
  • Für Ihre Antwort gelten Standardregeln mit Standard-E / A-Regeln . Sie können also STDIN / STDOUT, Funktionen / Methoden mit den richtigen Parametern und vollständige Programme vom Rückgabetyp verwenden. Ihr Anruf.
  • Standardschlupflöcher sind verboten.
  • Wenn möglich, fügen Sie bitte einen Link mit einem Test für Ihren Code (dh TIO ) hinzu.
  • Es wird dringend empfohlen, eine Erklärung für Ihre Antwort hinzuzufügen.

Testfälle:

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]]
Kevin Cruijssen
quelle
Ist X + 1also eine spezielle Gruppe für exakte Kopien und Xeine Gruppe für andere Zahlen, die aus Kopien einer einzelnen Zahl gebildet werden können, wie z. B. deren Negation?
Neil
1
@ArBo Nehmen wir an, die Ganzzahlen sind maximal 32 Bit, also im Bereich . Ihr Beispiel ist also keine gültige Eingabe, aber möglich. [2147483648,2147483647][1, 1111111111]
Kevin Cruijssen
1
Ich bin selbst Sammler: Das ist eine verdammt gute Sammlung, Kevin. Wirklich sehr nett.
J. Sallé
1
Ich sammle Magic: The Gathering-Karten und -Sets, die immer noch überraschend viel Platz einnehmen, obwohl sie ziemlich klein sind.
J. Sallé
1
@ J.Sallé Oh, ich kenne das Gefühl. Ich sammle auch Pokémon-TCG-Karten (und habe tatsächlich die zweitgrößte Pikachu-TCG-Sammlung der Welt mit mehr als 1200 einzigartigen Pikachu-Karten). Wenn Sie über 9.000 Karten haben, nimmt dies tatsächlich ziemlich viel Platz ein. Nicht so sehr wie die Rätsel. Nur 1,5 Regale statt 10 .; p
Kevin Cruijssen

Antworten:

9

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

Brute-Force-Implementierung mit itertools; Nicht alle Testfälle werden innerhalb der 60-Sekunden-Grenze für TIO ausgeführt.

Probieren Sie es online aus!

Dank an ArBo für das Golfen von 101 Bytes, an Galen Ivanov für das Golfen von 19 Bytes, an ElPedro für das Golfen von 5 Bytes, an movatica für das Golfen mit 17 Bytes, an Black Owl Kai für das Golfen von 2 Bytes, an Squid für das Golfen von 2 Bytes und an Kevin Cruijssen für Golfen 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)]

Erläuterung:

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

Gleicher Ansatz, aber aufgrund einiger Golftricks kürzer Python 3 unterstützt nicht mehr. Vielen Dank an ArBo für den Backport und für das Golfen von 28 Bytes, an ElPedro für das Golfen von 5 Bytes, an movatica für das Golfen von 17 Bytes und an Squid für das Golfen von 1 weiteren Bytes.

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)

Probieren Sie es online aus!

OOBalance
quelle
2
Kommentare sind nicht für eine ausführliche Diskussion gedacht. Dieses Gespräch wurde in den Chat verschoben .
James
Sie können 5 in beiden speichern, indem Sie str(abs(x))(oder abs (x) mit Backticks in Python 2) zum Funktionsaufruf verschieben und x in der Funktionsdefinition in y ändern, indem Sie y = str (abs (x)) entfernen. Entschuldigung, ich kann TIO momentan nicht zum Arbeiten bringen.
ElPedro
Sie können nach filtern len, um ein weiteres Byte zu entfernen, oder?
Stellen Sie Monica am
Sie können die Listensyntax in any()Aufrufen entfernen und so zu einem normalen Generator machen, der genauso gut funktioniert und Ihnen 4 weitere Bytes spart :)
movatica
... und noch kürzer: (x in sum(l,[]))statt any(x in s for s in l)für beide xund -xspart 13 weitere Bytes!
movatica
7

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)

Probieren Sie es online aus!

-1 Byte dank Squids Kommentar zur anderen Python-Antwort

Diese Antwort hat keine Hoffnung auf irgendwelche, aber die banalsten von Testfällen zu lösen. In der Verbindung TIO, s*11wurde ersetzt durch s*2, Korrektheit für die schnellen in einigen Fällen zu opfern er die Ausführungszeit, aber soweit ich sehen kann, ist die Version in diesem Beitrag liefert immer die richtige Antwort, in der Theorie.

Erläuterung

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
ArBo
quelle
2
Ich freue mich zu sehen, dass Sie Ihre eigene Python-Antwort erstellt haben :-) Und sie ist auch kürzer!
OOBalance
@OOBalance Nun, wenn es nur in meinem Leben enden würde ...
ArBo
1
Oh, ich habe vergessen, wie dumm das mit der Windows-Version ist (sie verwendet nur 32 Bit, intselbst in der 64-Bit-Version).
Feersum
7

05AB1E , 43 41 38 35 27 Bytes

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

Probieren Sie es online aus!

Erläuterung:

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

Da Gruppennummern nicht Teil der Ausgabe sind, können wir beliebige Zahlen verwenden, solange die Reihenfolge korrekt ist. Dies verwendet 0 für Originalnummern, 2 ^ -N für Gruppe XN, 1 für Gruppe X, 2 für Gruppe X + 1.

Grimmy
quelle
3
Ich würde gerne eine Erklärung sehen, wie dies funktioniert, da ich 05AB1E nicht lesen kann.
OOBalance
@OOBalance Ich habe eine Erklärung hinzugefügt, hoffentlich ist es klar genug.
Grimmy
Danke, das erklärt es gut. Guter Ansatz, habe meine positive Bewertung :)
OOBalance
2

Python 2, 195 Bytes

Der langsamste Testfall kann auf TIO nicht abgeschlossen werden , auf meinem Computer dauert es jedoch nur etwa 10 Sekunden.

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)

Es kann durch 2 Bytes verkürzt werden auf LP64 Python baut durch den Ersatz '%s-%%s'%a%nmit `a`+'-'+`n`.

Feersum
quelle
1

JavaScript (Node.js) , 211 205 Byte

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)

Probieren Sie es online aus!

Unter der Annahme, dass es höchstens 12 Gruppen gibt.

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)

Probieren Sie es online aus!

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

... oder 193 Bytes, wenn die Rückgabe eines Wörterbuchs in Ordnung ist:

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

Probieren Sie es online aus!

In diesem Fall -Infinitybedeutet Schlüssel Gruppe 1 und andere Schlüssel Gruppe X+key.

Shieru Asakoto
quelle