Sumas de dígitos del 1 al 7

21

Reto

Dado un número entero positivo Nque es 28 o por encima de, la salida de una lista de números de suma a Nque los usos cada dígito 1a través de 7exactamente una vez. Puedes dar como un programa o función.

Los dígitos pueden aparecer solos o concatenados, siempre que los use una vez sin repeticiones. Por ejemplo, [12, 34, 56, 7]es válido, como es [1, 27, 6, 4, 35]y [1234, 567], pero no [123, 34567]o [3, 2, 1476]. El orden en que se enumeran los números no importa.

Si Nno se puede hacer con 1-7, no devuelve ni genera nada.

Otra información

  • Este es el código de golf, por lo que gana el código más corto en bytes para el jueves 15 de octubre.

  • Haga cualquier pregunta en los comentarios.

  • Cualquier cosa que no especifique en el desafío depende de usted.

  • Las lagunas estándar no están permitidas.

Ejemplos

Estos pueden aclarar cualquier confusión:

Entrada

28

Salida

[1, 2, 3, 4, 5, 6, 7]

Entrada

100

Salida

[56, 7, 4, 31, 2]

Entrada

1234567

Salida

[1234567]

Entrada

29

Salida

Nada, 29 no es válido.

Entrada

1891

Salida

[1234, 657]

Entrada

370

Salida

[15, 342, 7, 6]

Haré más si es necesario.

Aquí hay una lista de todos los números posibles creados con estos siete números, cortesía de FryAmTheEggman.

The_Basset_Hound
fuente
¿Para qué es la salida 29?
Geobits
44
Si desea que la salida no sea nada, no la ponga (N/A)como salida.
mbomb007
1
@LukStorms [1234566, 1]no es una salida válida, porque 6 se repite. No puede repetir números en la salida.
The_Basset_Hound
2
Quizás »... una lista de números hecha de los dígitos decimales 1 a 7 que suman N« es una redacción más clara que la que se encuentra actualmente en la pregunta.
Paŭlo Ebermann
3
Para una solución de fuerza bruta un poco menos: esto es equivalente a asignar un coeficiente de potencia de 10 a cada uno de 1, ..,, 7modo que haya al menos tantos 1's como 10' s, al menos tantos 10's como 100' s, y así sucesivamente.
xnor

Respuestas:

9

Pyth, 18 14 bytes

hfqSjkTjkS7./Q

Gracias a @isaacg por jugar 2 bytes y allanar el camino para 2 más.

El código se bloqueará si no produce salida, lo que hace que no se produzca ninguna salida.

Esto funcionará para entradas pequeñas si es lo suficientemente paciente, y para las más grandes si se le da suficiente tiempo y memoria.

Para verificar que el código funciona como está previsto, que puede sustituir a la 7de una 3de las sumas de los dígitos 1 a 3 . Haga clic aquí para obtener un conjunto de pruebas.

Ejecuciones de ejemplo

$ time pyth/pyth.py -c 'hfqSjkTjkS7./Q' <<< 28
(1, 2, 3, 4, 5, 6, 7)

real    4m34.634s
user    4m34.751s
sys     0m0.101s
$ time pyth/pyth.py -c 'hfqSjkTjkS7./Q' <<< 29 2>/dev/null

real    9m5.819s
user    9m6.069s
sys     0m0.093s

Cómo funciona

           ./Q    Compute all integer partitions of the input.
 f                Filter the integer partitions:
    jkT             Join the integers with empty separator.
   S                Sort the characters of the resulting string.
      jkS7          Join [1, ..., 7] with empty separator.
  q                 Check both results for equality.
                  Keep the partition of `q' returned True.
h                 Retrieve the first element of the filtered list.
                  For a non-empty list, this retrieves the solution.
                  For the empty list, it causes an error and produces no output.
Dennis
fuente
2
¡Bien hecho! Un enfoque bastante innovador. `` MS7`` es más corto que r\1\8. También @ .. 0es lo mismo que h.
isaacg
@isaacg ¡Gracias! No estoy seguro de cómo me perdí h, pero no tenía idea de que podría usarlo de Sesa manera. (La referencia de char en el intérprete en línea no lo menciona) jkS7parece ser aún más corto, ya que no necesito smás.
Dennis
5

Pitón 3, 109

def f(n,s=set('1234567'),l='0,'):[f(n,s-{x},l+x+c)for c in(',','')for x in s]or n-sum(eval(l))or~print(l[2:])

Una función que toma un número y genera una tupla similar 123,4567,. Sí, esta es una tupla válida.

La idea es generar todas las secuencias posibles como la 43,126,7,5,que tienen los dígitos 1a través 7separados por comas, sin comas dos consecutivos. Evalúe esta expresión como una tupla, y su suma es igual n, imprímala y termine con error.

Para construir todas esas cadenas, srastreamos el conjunto de caracteres a usar e intentamos agregar cada uno con una coma, lo que hace que el dígito finalice la entrada, o sin él, en cuyo caso los dígitos futuros se concatenarán en él.

El cortocircuito se usa para verificar que sestá vacío porque la lista de compilación está vacía, y que n==sum(eval(l)), en cuyo caso imprimimos ly terminamos con un error al tomar ~el Nonedevuelto imprimiendo (gracias a Sp3000 por esto).

Creo que en Python 3.5, se pueden guardar dos caracteres escribiendo s={*'1234567'}(gracias Sp3000).

Hay algunas pequeñas molestias que se comen los caracteres. Una es que, en el caso de que lparezca 1234567sin comas, se analiza como un número único y las llamadas sumdan un error. Esto se maneja con el truco de comenzar lcon el elemento 0y quitarlo al imprimir. Esto cuesta 6 caracteres.

Iterar csobre la coma y la cadena vacía es molestamente prolijo for c in(',',''), ya que Python 3 no permite que esta tupla esté desnuda. Me gustaría que haya algunos caracteres ?que se ignoren en los números para hacer ',?'4 caracteres menos, pero no parece haber tal carácter.


Antiguo método:

Pitón 2, 117

def f(n,s={1,2,3,4,5,6,7},l=[],p=0):
 if{n,p}|s=={0}:print l;1/0
 if p:f(n-p,s,l+[p])
 for x in s:f(n,s-{x},l,p*10+x)

Define una función que toma un número e imprime una lista.

La idea es utilizar la recursividad para probar cada rama. Las variables de seguimiento son

  • La suma restante nnecesaria
  • El conjunto de dígitos srestantes para usar
  • La lista lde números hecha hasta ahora
  • El número actual parcialmente formado p

Cuando n==0y sestá vacío, imprima ly finalice por error.

Si el número actual parcialmente formado pno es cero, intente agregarlo a la lista y eliminarlo de la suma restante.

Para cada dígito xque podamos usar s, intente agregarlo py eliminarlo s.

xnor
fuente
4

Pyth, 23

#iRThfqQsiR10Ts./M.pS7q

La fuerza bruta ingenua, demasiado lenta en línea, tarda aproximadamente un minuto en mi computadora. Utiliza el patrón común de "bucle para siempre hasta excepción" de pyth golfs donde el acceso a la lista de combinaciones filtradas resultante causa un error para números imposibles, como 29.

Salidas como una lista pitónica, p. Ej.

1891
[1234, 657]
100
[1, 2, 34, 56, 7]
370
[12, 345, 6, 7]

Aquí hay una pasta de todos los números 10136 que se pueden hacer de esta manera.

FryAmTheEggman
fuente
¿Puedo usar el enlace pastebin para ejemplos?
The_Basset_Hound
@The_Basset_Hound Por supuesto, adelante.
FryAmTheEggman
3

Python 2.7, 178 172 169 bytes

n=input()
for i in range(8**7):
 for j in len(set('%o0'%i))/8*range(128):
    s=''
    for c in'%o'%i:s+='+'[:j%2*len(s)]+c;j/=2
    if eval(s)==n:print map(int,s.split('+'));1/0

Tenga en cuenta que se supone que las últimas tres líneas están sangradas con pestañas, pero no puedo entender cómo hacerlo en este editor.

Editar: aplanó una capa de anidamiento con la ayuda de Sp3000

xsot
fuente
SE desafortunadamente elimina las pestañas, así que solo decir cómo se debe sangrar está bien :)
Sp3000
Ah, vale, sigo pensando en este sitio.
xsot
3

JavaScript (ES6), 165196

Editar acortado un poco. Podría ser más corto usando eval, pero me gusta que sea rápido

Fuerza bruta, vergonzosamente más larga que la versión Pith, pero más rápida. Pruebe a ejecutar el fragmento a continuación en un navegador compatible con EcmaScript 6.

f=z=>{for(r=i=1e6;r&&++i<8e6;)for(m=/(.).*\1|[089]/.test(w=i+'')?0:64;r&&m--;t.split`+`.map(v=>r-=v,r=z))for(t=w[j=0],l=1;d=w[++j];l+=l)t+=l&m?'+'+d:d;return r?'':t}

function test() { O.innerHTML=f(+I.value) }

test()

// Less golfed

f=z=>{
  for(r=i=1e6; r&&++i<8e6;)
    for(m=/(.).*\1|[089]/.test(w=i+'')?0:64; r&&m--; t.split`+`.map(v=>r-=v,r=z))
      for(t=w[j=0],l=1;d=w[++j];l+=l)
        t+=l&m?'+'+d:d;
  return r?'':t
}
<input id=I value=28><button onclick=test()>-></button><span id=O></span>

edc65
fuente
No es una pena estar más tiempo debido al lenguaje, realmente disfruto tus respuestas de JS, +1
FryAmTheEggman
1

Python 2, 270 268 bytes

from itertools import*;P=permutations
x,d,f=range(1,8),[],input()
r=sum([[int(''.join(str(n)for n in i))for i in list(P(x,j))]for j in x],[])
z=1
while z:
 t=sum([[list(j)for j in P(r,z)]for i in x],[])
 v=filter(lambda i:sum(i)==f,t)
 if v:print v[0];break
 else:z+=1

Todavía trabajando en golf.

Esto se repite hasta que se encuentra una coincidencia.

Puertas de Zach
fuente
import asrara vez es necesario - puedes hacerlofrom itertools import*;P=permutations
Sp3000
Es más corto de usar map(str,i)que la comprensión de la lista, y puede construir la lista r directamente en lugar de aplanar una lista anidada r=[int(''.join(map(str,i)))for j in x for i in P(x,j)], y algo similar para t.
Ruth Franklin
Puede usar en `n`lugar de str(n), ya nque nunca estará por encima del número entero máximo.
mbomb007
1

Haskell (145 bytes)

main=getLine>>=print.head.f[1..7].read
f[]0=[[]]
f b s=[n:j|(n,g)<-m b,j<-f g$s-n]
m b=[(d+10*z,g)|d<-b,(z,g)<-(0,filter(/=d)b):m(filter(/=d)b)]

Utiliza la recursividad.

Sin golf (337 bytes):

delete d = filter (/= d)
main = getLine >>= print . (`form` [1..7]) . read

form s [] | s == 0    = [[]]
form s ds | s <= 0    = []
form s ds | otherwise = [n:ns | (n, ds') <- makeNumbers ds, ns <- form (s-n) ds']

makeNumbers [] = []
makeNumbers ds  = [(d + 10 * n',ds') | d <- ds, (n',ds') <- (0,delete d ds):makeNumbers (delete d ds)]
jkabrg
fuente
0

Scala, 195 bytes

Este no es el más eficiente y tardó más de 15 minutos en obtener la salida para 29, pero funciona

def g(s: Seq[Int]): Iterator[Seq[Int]]=s.combinations(2).map(c=>g(c.mkString.toInt +: s.filterNot(c.contains))).flatten ++ Seq(s)
def f(i: Int)=(1 to 7).permutations.map(g).flatten.find(_.sum==i)

Aquí hay algo de salida

scala> f(100)
res2: Option[Seq[Int]] = Some(Vector(46, 35, 12, 7))

scala> f(1891)
res3: Option[Seq[Int]] = Some(Vector(567, 1324))

scala> f(370)
res4: Option[Seq[Int]] = Some(Vector(345, 12, 6, 7))

scala> f(29)
res5: Option[Seq[Int]] = None
JoseM
fuente
0

Ruby, 105 bytes

¡Fuerza bruta! Comprueba cada subconjunto de longitudes entre 0 y 7 de los enteros entre 1 y 7654321 y ve si alguno de ellos coincide con nuestros criterios. Probablemente no quieras esperar a que esto termine.

->n{8.times{|i|[*1..7654321].permutation(i){|x|return x if
x.join.chars.sort==[*?1..?7]&&eval(x*?+)==n}}}

Para ejecutar y verificar el algoritmo, puede reducir el espacio de búsqueda reemplazando 7654321con el número más grande que sabe que estará en la respuesta. Por ejemplo, 56 para n = 100, o 1234 para n = 1891. Aquí hay una prueba de este último:

$ ruby -e "p ->n{8.times{|i|[*1..1234].permutation(i){|x|return x if x.join.chars.sort==[*?1..?7]&&eval(x*?+)==n}}}[gets.to_i]" <<< 1891
[657, 1234]
daniero
fuente
0 a 7 enteros? Debe usar exactamente 7 enteros: 1,2,3,4,5,6,7
edc65
@ edc65 Quiere decir exactamente 7 dígitos . El resultado es un conjunto de enteros, y el tamaño del conjunto depende de la entrada.
daniero
No hablo Ruby, supongo que el programa funciona, pero no entiendo la explicación. Si sus enteros son menores que 1234567, ¿cómo obtiene 7654321?
edc65
@ edc65 Tienes razón, tendré que cambiar ese número. Trataré de explicarlo mejor también.
daniero