22
\$\begingroup\$

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

You can read the above puzzle for the background. The details about this puzzle are as follows.

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.
    • Please state it in your answer if your program depends on input order
  • 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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice puzzle, but I personally think that some more test cases would be helpful in order to test our submissions. \$\endgroup\$ – Mr. Xcoder Dec 25 '18 at 11:42
  • \$\begingroup\$ Wouldn't it be better to make input size a parameter? Brute force approaches will struggle with 8 \$\endgroup\$ – Luis Mendo Dec 25 '18 at 11:43
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – Luis Mendo Dec 25 '18 at 11:48
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – nimi Dec 25 '18 at 12:01
  • 1
    \$\begingroup\$ @Arnauld Clarified \$\endgroup\$ – iBug ......................... Dec 26 '18 at 1:34

13 Answers 13

14
\$\begingroup\$

Python 3, 113 62 bytes

for i in[1]*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)

\$\endgroup\$
  • 1
    \$\begingroup\$ 96 bytes. \$\endgroup\$ – Erik the Outgolfer Dec 25 '18 at 20:16
  • \$\begingroup\$ x=0,*x saves 1 byte. Better yet, x+=0, saves 2. \$\endgroup\$ – Mr. Xcoder Dec 25 '18 at 23:21
  • \$\begingroup\$ 78 bytes in Python 2. \$\endgroup\$ – Lynn Dec 28 '18 at 15:04
9
\$\begingroup\$

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Ẏ§ṢQJƑƤS     Monadic link / Full program.
  Ɱ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).
\$\endgroup\$
7
\$\begingroup\$

Haskell, 56 50 bytes

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$ – Ørjan Johansen Dec 25 '18 at 20:06
4
\$\begingroup\$

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.
\$\endgroup\$
  • 2
    \$\begingroup\$ Żṗ8§ḟ’$Ṃ saves one byte, but I'm not sure if 8.5 minutes counts as a few. \$\endgroup\$ – Dennis Dec 26 '18 at 4:02
4
\$\begingroup\$

Wolfram Language (Mathematica), 53 bytes

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

Try it online!

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

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[0]*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[0] * 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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Pari/GP, 57 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ is this using generating function? \$\endgroup\$ – don bright Jan 2 at 0:03
  • 1
    \$\begingroup\$ @donbright Yes. \$\endgroup\$ – alephalpha Jan 2 at 7:18
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – don bright Jan 2 at 7:36
2
\$\begingroup\$

Python 2, 125 115 111 bytes

lambda c:sum(i==j for i,j in enumerate(sorted(set(map(sum,product([0]+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([0]+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*
\$\endgroup\$
2
\$\begingroup\$

Perl6, 65 63 41 bytes (39 37 chars)

{@_=(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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 48 bytes. Technically, the unique is not needed, but it speeds it up a lot \$\endgroup\$ – Jo King Dec 28 '18 at 7:14
  • \$\begingroup\$ @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. \$\endgroup\$ – guifa Dec 28 '18 at 15:17
  • \$\begingroup\$ The xx 1 should be xx 3 \$\endgroup\$ – Jo King Mar 29 at 0:56
  • \$\begingroup\$ @JoKing fixed. Also I realized two chars (but no bytes) can be saved by using ^∞ \$\endgroup\$ – guifa Mar 29 at 1:01
  • \$\begingroup\$ Actually, you can save some bytes with (1...*∉@_)-1 instead of using first, (which I realise is the same method I used here) \$\endgroup\$ – Jo King Mar 29 at 1:05
1
\$\begingroup\$

JavaScript (Node.js), 171 145 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)))
\$\endgroup\$
0
\$\begingroup\$

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]))[[0]])))
=length(takeWhile((>=)1)(zipWith(-)(tl k)k))
$_=0

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

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.