21
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What's the output for 29? \$\endgroup\$ – Geobits Oct 8 '15 at 20:01
  • 4
    \$\begingroup\$ If you want the output to be nothing, don't put (N/A) as the output. \$\endgroup\$ – mbomb007 Oct 8 '15 at 20:05
  • 1
    \$\begingroup\$ @LukStorms [1234566, 1] is not a valid output, because 6 is repeated. You may not repeat numbers in the output. \$\endgroup\$ – The_Basset_Hound Oct 8 '15 at 20:12
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Paŭlo Ebermann Oct 8 '15 at 20:17
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – xnor Oct 8 '15 at 21:17
9
\$\begingroup\$

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.
\$\endgroup\$
  • 2
    \$\begingroup\$ Well done! Quite an innovative approach. ```MS7`` is shorter than r\1\8. Also @ .. 0 is the same as h. \$\endgroup\$ – isaacg Oct 9 '15 at 9:20
  • \$\begingroup\$ @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. \$\endgroup\$ – Dennis Oct 9 '15 at 13:37
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

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

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

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

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>

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

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.

\$\endgroup\$
  • \$\begingroup\$ import as is rarely necessary - you can do from itertools import*;P=permutations \$\endgroup\$ – Sp3000 Oct 9 '15 at 1:07
  • \$\begingroup\$ 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. \$\endgroup\$ – Ruth Franklin Oct 9 '15 at 9:38
  • \$\begingroup\$ You can use `n` instead of str(n), since n will never be above the maximum integer. \$\endgroup\$ – mbomb007 Oct 9 '15 at 16:46
1
\$\begingroup\$

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)]
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ 0 to 7 integers? You should use exaclty 7 integers: 1,2,3,4,5,6,7 \$\endgroup\$ – edc65 Oct 9 '15 at 20:15
  • \$\begingroup\$ @edc65 You mean exactly 7 digits. The result is a set of integers, and the size of the set depends on the input. \$\endgroup\$ – daniero Oct 9 '15 at 20:16
  • \$\begingroup\$ 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? \$\endgroup\$ – edc65 Oct 9 '15 at 20:18
  • \$\begingroup\$ @edc65 You're right, I'll have to change that number. I'll try to explain it better too. \$\endgroup\$ – daniero Oct 9 '15 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.