Eight coins for the fair king

This is a "counterpart" of another puzzle, Eight coins for the fair king on Puzzling.SE.

A set of 8 kinds of coins of different values are created, the king wants you to find out the maximum N such that any number of price from 0 to N can be paid with a combination no more than 8 coins and without charges.

For example, (taken from Glorfindel's answer). If a set of coins of values 1, 2, 5, 13, 34, 89, 233, 610 are given, your program should output 1596, because every number between 0 and 1596 (inclusive) can be represented by the sum of no more than 8 numbers from the given list (numbers may repeat), while 1597 cannot be represented in that way.

In a mathematical way, if the input is a set S consisting of 8 positive integers, the desired output N satisfies that for any number n between 0 and N, there exists x1, x2, x3, ..., x8 such that

$$x_1 + x_2 + ... + x_8 = n \quad\textrm{and}\quad x_1, x_2, ...,x_8 \in \{0\} \cup S$$

Your goal is to write a program, a function, or a snippet that takes 8 numbers as input, and output the maximum N as described above.

Rules:

• Flexible I/O allowed, so your program can take the input in any form that's best suitable. You may assume that the input numbers are sorted in the way that best suits your program.
• Input is a set of 8 different, positive integers (no zeros). The output is one non-negative integer.
• In case there's no 1 in the input set, your program should output 0 because any number from 0 to 0 satisfies the requirement.
• In the case of invalid input (the set contains zero, negative or duplicate numbers), your program can do anything.
• Standard loopholes are forbidden.
• Your program should run within a few minutes on a modern computer.

Test cases (mostly taken from the answers under the linked question on Puzzling):

[1, 2, 3, 4, 5, 6, 7, 8] => 64
[2, 3, 4, 5, 6, 7, 8, 9] => 0
[1, 3, 4, 5, 6, 7, 8, 9] => 72
[1, 2, 5, 13, 34, 89, 233, 610] => 1596
[1, 5, 16, 51, 130, 332, 471, 1082] => 2721
[1, 6, 20, 75, 175, 474, 756, 785] => 3356

This is a , so the shortest program or snippet in each language wins!

• Nice puzzle, but I personally think that some more test cases would be helpful in order to test our submissions. Dec 25 '18 at 11:42
• Wouldn't it be better to make input size a parameter? Brute force approaches will struggle with 8 Dec 25 '18 at 11:43
• @iBug Then the usual rule is something like "submissions shoud run within a minute in a modern computer". It's fuzzy, but usually good enough, because the difference between brute force and efficient approaches is very large Dec 25 '18 at 11:48
• Brute force is still possible with your time limit of "a few minutes". A slightly modified version of my answer runs the last test case in 1m20s on my 7 year old laptop.
– nimi
Dec 25 '18 at 12:01
• @Arnauld Clarified
– iBug
Dec 26 '18 at 1:34

Python 3, 113 62 bytes

for i in*3:x|={a+b for a in x for b in x}
while{i+1}&x:i+=1

Here x is the input as a set of ints, and i is the output.

Try it online!

(Thanks: Erik the Outgolfer, Mr. Xcoder, Lynn)

• Dec 25 '18 at 20:16
• x=0,*x saves 1 byte. Better yet, x+=0, saves 2. Dec 25 '18 at 23:21
• 78 bytes in Python 2.
– Lynn
Dec 28 '18 at 15:04

Jelly, 12 bytes

œċⱮ8Ẏ§ṢQJƑƤS

Try it online!

Takes on average ~3.7 seconds to run all test cases on TIO on my phone, so surprisingly it is quite fast.

Explanation

Ɱ8             Promote 8 to [1 ... 8] and for each value k:
œċ                    Generate all combinations of k elements from the list.
Ẏ§           Tighten, then sum. Flatten to a 2D list then sum each.
ṢQ         Sort the result and remove equal entries.
JƑƤ      For each prefix of this list, return 1 if it is equal to its length range, 0 otherwise.
S     Finally, sum the result (counts the 1's which is equivalent to what is being asked).

g c=[x|x<-[1..],all((/=x).sum)$mapM(0:)$c<$c]!!0-1 Try it online! A brute force approach. Add 0 to the list of coins and try all combinations of 8 picks. Find the first number n that is not equal to the sum of any of the picks and return n-1. Takes about 5m30s for [1, 2, 5, 13, 34, 89, 233, 610] on my 7 year old laptop hardware. Edit: -6 bytes thanks to @Ørjan Johansen An even shorter version (-2 bytes, again thanks to @Ørjan Johansen) is Haskell, 48 bytes g c=[x|x<-[1..],all((/=x).sum)$mapM(:0:c)c]!!0-1

but it uses significantly more memory and runs into heavy paging on my machine and does not finish "within a few minutes".

• You can use mapM(0:)$c<$c. (In fact mapM(:0:c)c should work, but times out on TIO for the given test case.) Dec 25 '18 at 20:06

Jelly, 9 bytes

Żœċ8§ḟ’$Ṃ Try it online! How it works Żœċ8§ḟ’$Ṃ  Main link. Argument: A (array)

Ż          Prepend a 0 to A.
œċ8       Take all combinations of length 8, with repetitions.
§      Take the sum of each combination.
$Combine the two links to the left into a monadic chain. ’ Decrement all sums. ḟ Filterfalse; keep only sums that do not appear in the decremented sums. Ṃ Take the minimum. • Żṗ8§ḟ’$Ṃ saves one byte, but I'm not sure if 8.5 minutes counts as a few. Dec 26 '18 at 4:02

Wolfram Language (Mathematica), 53 bytes

LengthWhile[CoefficientList[(1+Tr[x^#])^8,x],#>0&]-1&

Try it online!

JavaScript (ES6),  100 88 80  76 bytes

This is essentially a brute-force search, but enhanced with pruning to speed it up. The average execution time for the test cases is close to 1 second on TIO.

Assumes that the input array is sorted from highest to lowest.

a=>[...Array(a*9)].findIndex(g=(i=8,s)=>s*i>0?a.every(x=>g(i-1,s-x)):s)-1

Try it online!

Commented

a =>                      // a[] = input array
[...Array(a * 9)]    // create an array of 9 * max(a) entries
.findIndex(             // find the position of the first truthy result
g = (i = 8, s) =>     // g = recursive function taking a counter i, initialized to 8
//     and a sum s, initialized to the position in the above array
s * i > 0 ?         //   if s is positive and i is not equal to 0:
a.every(x =>      //     for each value x in a[]:
g(i - 1, s - x) //       do a recursive call with i - 1 and s - x
)                 //     end of every()
:                   //   else:
s                 //     yield s (s = 0 means success and makes findIndex go on)
) - 1                   // end of findIndex(); decrement the result

Python 2, 145 bytes

from itertools import*
x=set(map(sum,reduce(chain,map(combinations_with_replacement,[input()]*9,range(9)))))
print~-min(set(range(1,max(x)+2))-x)

Try it online!

Pari/GP, 57 bytes

a->n=-1;while(polcoeff((1+sum(i=1,8,x^a[i]))^8,n++),);n-1

Try it online!

• is this using generating function? Jan 2 '19 at 0:03
• @donbright Yes. Jan 2 '19 at 7:18
• that is awesome.. one of the few answers not brute-forcing the solution. alot of languages probably dont have built in polynomial symbolic features. Pari GP is cool. Jan 2 '19 at 7:36

Python 2, 125115 111 bytes

lambda c:sum(i==j for i,j in enumerate(sorted(set(map(sum,product(+c,repeat=8))))))-1
from itertools import*

Try it online!

Expects a list of integers as input.

Explanation:

# an anonymous function
lambda c:
# get all length-8 combinations of values, from (0,0,0,0,0,0,0,0) to (8,8,8,8,8,8,8,8)
# zero is added to ensure that combinations of fewer than 8 coins are represented Ex:(1,0,0,0,0,0,0,0)
product(+c,repeat=8)
# for each combination, sum the values
map(sum,.......................)
# get unique values, then sort them smallest to largest
sorted(set(................................))
# for each index, value pair, return if the index is equal to the value
i==j for i,j in enumerate(.............................................)
# in Python arithmetic, False is 0 and True is 1. So, count how many items match their index.
# Since zero was added to the list, there will always be one extra match (0==0). So offset by one.
sum(........................................................................)-1
from itertools import*

{@_=(0,|@_)X+(0,|@_)for ^3;($_ if$_==$++for @_.sort.unique)-1} Try it online! This is an anonymous block that gets passed its data as an array. The (0,|@_) is a quick way to add a 0 to @_, and even though it's done twice, it's still a bit shorter than @_.push: 0; which would then need spaces after the _. This is a brute force approach that cheeses a bit on the fact that it's 8 combinations. After cross adding, an anonymous list is created for sequential values. With math operators, lists evaluate to their length, so the -1 pulls double duty: accounting for the 0 and coercing to Int. This can take its sweet time, but by changing one or both (0,|@_) to (0,|@_.unique) before the first for it can be sped up considerably. That adds +7 (runtime <60s) or +14 (runtime <10s) to the score if you feel the first is too slow (I did this for the linked code to avoid timeouts after 60 seconds). Edit: JoKing in the comments improved it (same idea, cross add, then return the last consecutive result) to an astonishing 39 chars (41 bytes): {(@_=@_ X+0,|@_)xx 3;first *+1∉@_,^∞} Try it online! The final tabulation doesn't need a 0, saving a few bytes by only needing to add 0 in once. The xx 3 mimics the for loop (still cheeses on the coins being a power of 2). The first sub returns the first number in the infinite list 0..* (^Inf is possible too, but doesn't save space) whose +1 is not a member of the cross added list. Like mine, it's slow, so add +7 for a unique after the first equals if you feel it's too slow for guidelines. • 48 bytes. Technically, the unique is not needed, but it speeds it up a lot – Jo King Dec 28 '18 at 7:14 • @JoKing nice, I don't know why I didn't think about using xx. I knew there had to be a way to do the final tabulation in a much shorter way using set functions, but my brain wasn't working. Dec 28 '18 at 15:17 • The xx 1 should be xx 3 – Jo King Mar 29 '19 at 0:56 • @JoKing fixed. Also I realized two chars (but no bytes) can be saved by using ^∞ Mar 29 '19 at 1:01 • Actually, you can save some bytes with (1...*∉@_)-1 instead of using first, (which I realise is the same method I used here) – Jo King Mar 29 '19 at 1:05 JavaScript (Node.js), 171145 115 bytes f=(s,n=3)=>n?f(s=new Set(a=[0,...s]),n-1,a.map(m=>a.map(n=>s.add(m+n)))):Math.min(...[...s].filter(m=>!s.has(m+1))) Try it online! Port of @Mark's Python 3 answer. 108 bytes in Firefox 30-57: f=(s,n=3)=>n?f(new Set((for(n of s=[0,...s])for(m of s)n+m)),n-1):Math.min(...[...s].filter(m=>!s.has(m+1))) Wolfram Language (Mathematica), 46 bytes 0//.x_/;Min[Tr/@FrobeniusSolve[#,x+1]]<9:>x+1& Try it online! Brute force approach: checks integers counting upward until it reaches a value that can't be paid for in 8 coins. Very, very slow (tio times out), but I'm fairly sure the condition is correct. Clean, 161 bytes import StdEnv,Data.List$l=:[1:_]#k=sort(nub(map sum(iter 8(concatMap(\[h:t]=[[e,h:t]\\e<-[0:l]|e>=h]))[])))
=length(takeWhile((>=)1)(zipWith(-)(tl k)k))
\$_=0

Try it online!