Sums of digits 1 through 7

Question

Challenge

Given a positive integer N that is 28 or above, output a list of numbers summing to N that uses each digit 1 through 7 exactly once. You can give as a program or function.

The digits can appear by themselves or concatenated, as long as you use each of them once without repeats. For example,[12, 34, 56, 7] is valid, as is [1, 27, 6, 4, 35] and [1234, 567], but not [123, 34567] or [3, 2, 1476]. The order that the numbers are listed does not matter.

If N cannot be made with 1-7, return or output nothing.

Other information

• This is code golf, so the shortest code in bytes by Thursday the 15th of October wins.

• Ask any questions in the comments.

• Anything I do not specify in the challenge is up to you.

• Standard loopholes are disallowed.

Examples

These may clear any confusion up:

Input

28

Output

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

Input

100

Output

[56, 7, 4, 31, 2]

Input

1234567

Output

[1234567]

Input

29

Output

Nothing, 29 is invalid.

Input

1891

Output

[1234, 657]

Input

370

Output

[15, 342, 7, 6]

I'll make more if needed.

Here's a pastebin of all of the possible numbers created with these seven numbers, courtesy of FryAmTheEggman.

Answer 1

Pyth, 18 14 bytes

hfqSjkTjkS7./Q

Thanks to @isaacg for golfing off 2 bytes and paving the way for 2 more.

The code will crash if it should produce no output, which causes no output to be produced.

This will work for small-ish inputs if you're patient enough, and for larger ones if given enough time and memory.

To verify that the code works as intended, you can replace the 7 with a 3 for sums of digits 1 through 3. Click here for a test suite.

Example runs

$ 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

How it works

           ./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.

Answer 2

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

A function that takes a number and outputs a tuple in the like 123,4567,. Yes, this is a valid tuple.

The idea is to generate all possible strings like 43,126,7,5, that have the digits 1 through 7 separated by commas, with no two commas consecutive. Evaluate this expression as a tuple, and its sum equals n, print it and terminate with error.

To build all such strings, we track the set s of chars to use, and try appenping each one either with a comma, which makes the digit end the entry, or without, in which case future digits will concatenate onto it.

Short-circuiting is used to check that s is empty because the list-comp is empty, and that n==sum(eval(l)), in which case we print l and terminate with an error by taking ~ of the None returned by printing (thanks to Sp3000 for this.).

I believe that in Python 3.5, two chars can be saved by writing s={*'1234567'} (thanks Sp3000).

There's some small annoyances that eat up chars. One is that in the case that l looking like 1234567 with no commas, it is parsed as a single number and calling sum gives an error. This is handled with the hack of starting l with the element 0 and stripping it when printing. This costs 6 chars.

Iterating c over the comma and the empty string is annoyingly wordy for c in(',',''), since Python 3 doesn't allow this tuple to be naked. I'd like there to be some char ? that is ignored in numbers to do ',?' for 4 chars less, but there doesn't seem to be such a char.

---

Old method:

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

Defines a function that takes a number and prints a list.

The idea is to use recursion to try every branch. The variables track are

• The remaining sum n needed
• The set of digits s remaining to use
• The list l of numbers made so far
• The current partially-formed number p

When n==0 and s is empty, print l and terminate by error.

If the current partially-formed number p is non-zero, try adding it to the list and removing it from the remaining sum.

For each digit x we can use from s, try appending it to p and removing it from s.

Answer 3

Pyth, 23

#iRThfqQsiR10Ts./M.pS7q

Naive brute force, too slow online, takes about a minute on my computer. Uses the common "loop forever until exception" pattern of pyth golfs where accessing the resulted filtered list of combinations causes an error for impossible numbers, like 29.

Outputs like a pythonic list, e.g.

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

Here is a paste of all of the 10136 numbers that can be made this way.

Answer 4

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

Note that the last three lines are supposed to be indented with tabs but I can't figure out how to do so in this editor.

Edit: Flattened one layer of nesting with the help of Sp3000

Answer 5

JavaScript (ES6), 165 196

Edit Shortened a little. Could be shorter using eval, but I like it being fast

Brute force, shamefully longer than Pith version, but faster. Test running the snippet below in an EcmaScript 6 compliant browser.

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>

Answer 6

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

Still working on golfing.

This loops until a match is found.

Answer 7

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

Uses recursion.

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

Answer 8

Jelly, 12 bytes

ŒṗDẎṢ⁼ʋƇ7R¤Ḣ

Try it online!

Times out for pretty much all inputs. Outputs 0 if no such list exists. Requiring empty output adds 3 bytes.

This is a 14 byte (17 for empty output) answer which has a more or less constant runtime (~40 seconds).

How they work

ŒṗDẎṢ⁼ʋƇ7R¤Ḣ - Main link. Takes n on the left
Œṗ           - Integer partitions of n
      ʋƇ     - Keep those for which the following is true:
  D          -   Convert to digits
   Ẏ         -   Flatten
    Ṣ        -   Sorted
     ⁼  7R¤  -   Equals [1, 2, 3, 4, 5, 6, 7]
           Ḣ - Take the first list

The 14 byte version:

7Œ!ŒṖ€ẎḌS=¥Ƈ⁸Ḣ - Main link. Takes n on the left
7              - Yield 7
 Œ!            - Get all permutations of [1, 2, 3, 4, 5, 6, 7]
     €         - Over each:
   ŒṖ          - Yield it's partitions
      Ẏ        - Flatten to a single list of all partitions
       Ḍ       - Convert from digits
          ¥Ƈ   - Keep those for which the following is true:
        S      -   Sum
         =  ⁸  -   Equals n
             Ḣ - Take the first list

Answer 9

Scala, 195 bytes

This isn't the most efficient and it took over 15 minutes to get the output for 29 but it works

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)

Here is some output

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

Answer 10

Ruby, 105 bytes

Brute force! Checks every subset of lengths between 0 and 7 of the integers between 1 and 7654321 and sees if any of them matches our criteria. You probably don't want to wait for this to terminate.

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

To run and verify the algorithm you can narrow down the search space by replacing 7654321 with the largest number you know will be in the answer. For instance, 56 for n=100, or 1234 for n=1891. Here's a trial run of the latter:

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

Answer 11

Husk, 15 bytes

ḟȯ=ḣ7Oṁdfo=¹ΣṖḣ

Try it online!