Agrupar enteros por originalidad

12

Introducción:

Colecciono rompecabezas retorcidos. La mayoría de los rompecabezas retorcidos son producidos y vendidos por compañías chinas. La mayoría de las compañías conocidas solicitan permiso de los diseñadores de rompecabezas para producir sus diseños y trabajar juntos para lograr un producto en el mercado. En este caso, los diseñadores de rompecabezas están muy contentos y orgullosos de que uno de sus rompecabezas llegue al mercado.

Sin embargo, también hay empresas chinas que hacen rompecabezas. Estas imitaciones son diseños utilizados sin el permiso del creador original, o son copias de menor calidad de rompecabezas ya existentes.

Desafío:

Vamos a determinar la originalidad de los números que se 'liberan' en un orden específico (de izquierda a derecha ).
Dada una lista de enteros, agrúpelos y expórtelos por su originalidad.

¿Cómo se determina la originalidad de los números?

  • ¿Es un número un duplicado exacto de un número anterior? Grupo X+1 (menos original), donde el grupo está detrás, después de todos los otros grupos.X+1
  • ¿Es un número un duplicado de un número anterior, pero es negativo en su lugar (es decir, el número original era , pero ahora ; o viceversa)? Grupo .nnX
  • ¿Se puede formar el valor absoluto del número concatenando uno o más números absolutos anteriores, y no forma parte de los grupos o mencionados anteriormente ? Grupo , donde es la cantidad de números distintos utilizados en la concatenación (y ).X+1XXNNN1
  • ¿El número no cabe en ninguno de los grupos anteriores, por lo que es completamente único hasta ahora? Grupo (el más original), que lidera antes que todos los demás grupos.1

Esto puede sonar bastante vago, así que aquí hay un ejemplo paso a paso :

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

  • 34es el primer número, que siempre es original y en el grupo . Salida hasta ahora:1[[34]]
  • 9 también es original: [[34,9]]
  • 4 también es original: [[34,9,4]]
  • -34es el negativo del número anterior 34, por lo que está en el grupo :X[[34,9,4],[-34]]
  • 19 es original: [[34,9,4,19],[-34]]
  • -199puede estar formado por los dos números anteriores 19y 9, por lo tanto, está en el grupo :X2[[34,9,4,19],[-199],[-34]]
  • 34es una copia exacta de un número anterior, por lo que está en el grupo :X+1[[34,9,4,19],[-199],[-34],[34]]
  • -213 es original: [[34,9,4,19,-213],[-199],[-34],[34]]
  • 94puede estar formado por los dos números anteriores 9y 4, por lo tanto, está en el grupo :X2[[34,9,4,19,-213],[-199,94],[-34],[34]]
  • 1934499puede estar formado por los cuatro números anteriores 19, 34, 4, y dos veces 9, por lo que es en el grupo X4 :[[34,9,4,19,-213],[19499],[-199,94],[-34],[34]]
  • 213es el negativo del número anterior -213, por lo que está en el grupo X :[[34,9,4,19,-213],[1934499],[-199,94],[-34,213],[34]]
  • 3 es original: [[34,9,4,19,-213,3],[1934499],[-199,94],[-34,213],[34]]
  • 21 es original: [[34,9,4,19,-213,3,21],[1934499],[-199,94],[-34,213],[34]]
  • -2134puede estar formado por los dos números anteriores 213y 4(o los tres números anteriores 21, 3y 4, pero siempre utilizamos la menor cantidad de la concatenación de números para determinar la originalidad), por lo que es en el grupo X2 :[[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134],[-34,213],[34]]
  • 4444949X2[[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[-34,213],[34]]
  • 444X1[[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[44],[-34,213],[34]]

Entonces, para la entrada, [34,9,4,-34,19,-199,34,-213,94,1934499,213,3,21,-2134,44449,44]la salida es [[34,9,4,19,-213,3,21],[1934499],[-199,94,-2134,44449],[44],[-34,213],[34]].

Reglas de desafío:

  • I / O es flexible. Puede ingresar como una lista / matriz / secuencia de enteros o cadenas, ingresarlos uno por uno a través de STDIN, etc. La salida puede ser un mapa con los grupos como clave, una lista anidada como ejemplo y casos de prueba en este desafío, impresos nueva línea separada, etc.
  • Se le permite tomar la lista de entrada en orden inverso (tal vez útil para idiomas basados ​​en pila). En cuyo caso, el mencionado de izquierda a derecha es, por supuesto, de derecha a izquierda.
  • Como se puede ver en el ejemplo de número entero -2134, siempre agrupar un número que es una concatenación de otros números con el menor número posible (formado por 213y 4- dos números; y no por 21, 3y 4- tres números).
  • Como puede ver en el ejemplo de entero 1934499, puede usar un número anterior (el 9en este caso) varias veces (similar al 44449uso de cuatro 4sy a 9en el ejemplo). Sin embargo, solo se cuentan una vez para determinar el grupo.
  • [1,58,85,-8,5,8585,5885,518][[1,58,85,8,5],[518],[5885],[8585],[],[]]XX1[[34,9,4,19,-213,3,21],[1934499],[],[-199,94,-2134,44449],[44],[-34,213],[34]]X3
  • [34,9,4,19,-213,3,21]1[21,3,-213,19,4,9,34][-213,4,34,19,9,21,3]
  • X10[1,X9,X8,...,X2,X1,X,X+1]
  • Puede suponer que los enteros serán de 32 bits como máximo, por lo que están dentro del rango [−2147483648,2147483647].

Reglas generales:

  • Este es el , por lo que la respuesta más corta en bytes gana.
    No permita que los lenguajes de code-golf lo desanimen a publicar respuestas con lenguajes que no sean codegolf. Trate de encontrar una respuesta lo más breve posible para 'cualquier' lenguaje de programación.
  • Las reglas estándar se aplican a su respuesta con las reglas de E / S predeterminadas , por lo que puede usar STDIN / STDOUT, funciones / método con los parámetros adecuados y programas completos de tipo retorno. Tu llamada.
  • Las lagunas predeterminadas están prohibidas.
  • Si es posible, agregue un enlace con una prueba para su código (es decir, TIO ).
  • Además, se recomienda agregar una explicación para su respuesta.

Casos de prueba:

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
fuente
Entonces, ¿ X + 1es un grupo especial para copias exactas, y Xes un grupo para otros números que se pueden formar a partir de copias de un solo número, como su negación?
Neil
1
[2147483648,2147483647][1, 1111111111]
1
Ser un coleccionista: esa es una muy buena colección que tienes allí, Kevin. Muy bueno de verdad.
J. Sallé
1
Colecciono cartas y sets de Magic: The Gathering, que todavía ocupan una cantidad sorprendentemente grande de espacio a pesar de que son bastante pequeños.
J. Sallé
1
@ J.Sallé Oh, conozco el sentimiento. También colecciono cartas de TCG Pokémon (y en realidad tengo la segunda colección más grande de TCG de Pikachu en el mundo con más de 1200 cartas de Pikachu únicas). Cuando tienes más de 9,000 cartas, de hecho ocupa bastante espacio. Sin embargo, no tanto como los rompecabezas. Solo 1.5 estantes en lugar de 10.; p
Kevin Cruijssen

Respuestas:

1

Gelatina , 36 33 bytes

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

Pruébalo en línea!

Estoy seguro de que esto se puede jugar más al golf. Un poco de inspiración tomada de la respuesta 05AB1E de Grimy , ¡así que asegúrese de votar esa también!

Nick Kennedy
fuente
9

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

Implementación de fuerza bruta usando itertools; no todos los casos de prueba se ejecutan dentro del límite de 60 segundos en TIO.

Pruébalo en línea!

Gracias a ArBo por jugar 101 bytes, a Galen Ivanov por jugar 19 bytes, a ElPedro por jugar 5 bytes, a movatica por jugar 17 bytes, a Black Owl Kai por jugar 2 bytes, a los calamares por jugar 2 bytes y a Kevin Cruijssen por Golf 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)]

Explicación:

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

El mismo enfoque, pero más corto debido a algunos trucos de golf, Python 3 ya no es compatible. Gracias a ArBo por el backport y por jugar al golf 28 bytes, a ElPedro por jugar al golf 5 bytes, a movatica por jugar al golf 17 bytes y al calamar por jugar al golf 1 byte más.

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)

Pruébalo en línea!

OOBalance
fuente
2
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
James
Puede guardar 5 en ambos moviendo str(abs(x))(o abs (x) con backticks en Python 2) a la llamada a la función y cambiando x en la definición de la función a y eliminando y = str (abs (x)). Lo siento, no puedo hacer que TIO funcione en este momento.
ElPedro
Puedes filtrar por lenpara eliminar otro byte, ¿verdad?
calamar
Puede eliminar la sintaxis de la lista dentro de las any()llamadas, lo que lo convierte en un generador normal, que funciona igual de bien y le ahorra 4 bytes más :)
movatica
... e incluso más corto: ¡en (x in sum(l,[]))lugar de any(x in s for s in l)para ambos xy -xahorra 13 bytes más!
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)

Pruébalo en línea!

-1 byte gracias al comentario de Squid sobre la otra respuesta de Python

Esta respuesta no tiene esperanzas de resolver ninguno de los casos de prueba más triviales. En el enlace TIO, s*11ha sido sustituido por s*2, sacrificando en algunos casos la corrección rápida para er tiempo de ejecución, pero por lo que puedo ver, la versión en este post siempre se obtiene la respuesta correcta, en teoría.

Explicación

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
fuente
2
Me complace ver que ha creado su propia respuesta de Python :-) ¡Y también es más corta!
OOBalance
@OOBalance Ahora, si tan solo terminara en mi vida ...
ArBo
1
Oh, olvidé que eso es una tontería con la versión de Windows (usa solo 32 bits intincluso en la versión de 64 bits).
feersum
7

05AB1E , 43 41 38 35 27 bytes

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

Pruébalo en línea!

Explicación:

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

Dado que los números de grupo no son parte de la salida, somos libres de usar los números que queramos, siempre y cuando el orden sea correcto. Utiliza 0 para los números originales, 2 ^ -N para el grupo XN, 1 para el grupo X, 2 para el grupo X + 1.

Mugriento
fuente
3
Me encantaría ver una explicación de cómo funciona esto ya que no puedo leer 05AB1E.
OOBalance
@OOBalance Agregué una explicación, espero que sea lo suficientemente clara.
Grimmy
Gracias, eso lo explica muy bien. Buen enfoque, tenga mi
voto a favor
2

Python 2, 195 bytes

El caso de prueba más lento no puede completarse en TIO , pero solo toma alrededor de 10 segundos en mi máquina.

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)

Se puede acortar en 2 bytes en las compilaciones LP64 Python reemplazándolas '%s-%%s'%a%npor `a`+'-'+`n`.

Feersum
fuente
1

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)

Pruébalo en línea!

Usando el supuesto de que hay como máximo 12 grupos.

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)

Pruébalo en línea!

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

... o 193 bytes si devolver un diccionario está bien:

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

Pruébalo en línea!

En este caso, clave -Infinitysignifica Grupo 1 y otras claves significa Grupo X+key.

Shieru Asakoto
fuente