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

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

• What's the output for 29? Oct 8 '15 at 20:01
• If you want the output to be nothing, don't put (N/A) as the output. Oct 8 '15 at 20:05
• @LukStorms [1234566, 1] is not a valid output, because 6 is repeated. You may not repeat numbers in the output. Oct 8 '15 at 20:12
• Maybe »... a list of numbers made from the decimal digits 1 to 7 which sum up to N« is a clearer wording than the one currently in the question. Oct 8 '15 at 20:17
• For a slightly less brute force solution: This is equivalent to assigning a power-of-10 coefficient to each of 1, ..,, 7 so that there's at least as many 1's as 10's, at least as many 10's as 100's, and so on.
– xnor
Oct 8 '15 at 21:17

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

• Well done! Quite an innovative approach. MS7 is shorter than r\1\8. Also @ .. 0 is the same as h. Oct 9 '15 at 9:20
• @isaacg Thanks! I'm not sure how I missed h, but I had no idea you could use S that way. (The char reference in the online interpreter doesn't mention it.) jkS7 seems to be even shorter, since I don't need s anymore. Oct 9 '15 at 13:37

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

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

• May I use the pastebin link for examples? Oct 8 '15 at 21:32
• @The_Basset_Hound Of course, go ahead. Oct 8 '15 at 22:59

# Python 2.7, 178172 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

• SE strips out tabs unfortunately, so just saying how it's meant to be indented is fine :) Oct 9 '15 at 3:15
• Ah okay, still figuring my way around this site.
– xsot
Oct 9 '15 at 3:18

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

• No shame to be longer because of language, I really enjoy your JS answers, +1 Oct 8 '15 at 23:31

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

• import as is rarely necessary - you can do from itertools import*;P=permutations Oct 9 '15 at 1:07
• It's shorter to use map(str,i) than the list comprehension, and you can construct the list r directly rather than by flattening a nested list: r=[int(''.join(map(str,i)))for j in x for i in P(x,j)], and a similar thing for t. Oct 9 '15 at 9:38
• You can use n instead of str(n), since n will never be above the maximum integer. Oct 9 '15 at 16:46

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

• 0 to 7 integers? You should use exaclty 7 integers: 1,2,3,4,5,6,7 Oct 9 '15 at 20:15
• @edc65 You mean exactly 7 digits. The result is a set of integers, and the size of the set depends on the input. Oct 9 '15 at 20:16
• I don't speak Ruby, I presume the program works, but I don't get the explanation. If your integers are less than 1234567, how do you get 7654321? Oct 9 '15 at 20:18
• @edc65 You're right, I'll have to change that number. I'll try to explain it better too. Oct 9 '15 at 20:20

# Husk, 15 bytes

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


Try it online!