Determine if a coin system is Canonical

The Cashier's Algorithm is an algorithm for making change in the minimal number of coins that works quite well for most currency systems. However like most greedy algorithms it is not without its flaws. If a currency system is set up just right (or just wrong) there are certain values in which the Cashier's Algorithm will fail to find the optimal change.

Take the following example:

We have 4¢, 3¢, and 1¢ coins. We want to make 6¢.

The Cashier's Algorithm will first select as many of the largest coin (one 4¢ to start) and subtract and repeat. This will result in one 4¢ coin and two 1¢ coins, for a total of 3 coins.

Unfortunately for the Algorithm there is a way to make 6¢ with only two coins (two 3¢ coins).

A system of change will be considered canonical iff for all integer values the Cashier's Algorithm will find the optimal number of coins.

You task will be to take a system as a either an unordered container or sorted ordered container of integers representing coin values and output a truthy value if the system input is canonical and falsy otherwise.

Your program should work for all systems that can create any value. (i.e. all systems will have a 1¢ coin)

This is code golf least bytes wins.

Test cases

This list is by no means exhaustive, your program should work for all valid input

1, 3, 4       -> 0
1, 5, 10, 25  -> 1
1, 6, 10, 25  -> 0
1, 2, 3       -> 1
1, 8, 17, 30  -> 0
1, 3, 8, 12   -> 0
1, 2, 8, 13   -> 0
1, 2, 4, 6, 8 -> 1

• @Geobits not in every case it means more that the difference growing or equal from the smallest coin to the largest Oct 13 '16 at 20:51
• @JörgHülsermann That's not really good enough either. [1, 6, 13] has a growing difference, but it still fails on something like 18 (13+1*5 instead of 6*3). Oct 13 '16 at 20:55
• These are called Canonical Coin Systems. This short paper gives a polynomial-time algorithm for checking whether a coin system is canonical (though a less efficient method might be golfier). An interesting test case is making 37 cents from 25, 9, 4, 1 (from this math.SE post) -- even though each coin is bigger than the sum of the smaller ones, the non-greedy 25, 4, 4, 4 beats the greedy 25, 9, 1, 1, 1.
– xnor
Oct 13 '16 at 23:15
• @xnor Note that 9, 4, 1 -> 4, 4, 4 being better than 9, 1, 1, 1 is a tighter example. Oct 14 '16 at 1:01

f s=and[j i-2<j(i-x)|let j i=last$0:[1+j(i-x)|x<-s,x<i],i<-[1..2*last s],x<-s,x<i]  this solution works by defining a function j which perform's the cashier's algorithm and tells us how many coins the cashier used. we then check up to twice the biggest number in the list, assuming that the system has been canonical for all previous numbers, that taking the biggest possible coin is the right choice. this solution assumes the input is sorted. proof checking up to twice the biggest number is enough: assume that the system is not canonical for some number i, and let k be the biggest number in the list not bigger than i. assume that i >= 2k and the system is canonical for all numbers less than i. take some optimal way to make i out of coins, and assume it doesn't contain the coin k. if we throw away one of the coins, the new sum of coins must be bigger than k and smaller than i - but the cashier's algorithm on this number would use the k coin - and therefore, this set of coins can be replaced with an equal set of coins containing the coin k, and therefore there is a set of coins containing the coin k for the number i, and by induction the cashier's algorithm returns the optimal choice. this argument really shows that we only need to check until the sum of the two biggest elements - but it is lengthier to do so. Edit: five bytes off thanks to Ørjan Johansen! • You can save a byte by using let instead of where. You can either put it as a |let ... pattern guard after f s, or inside the list comprehension. Aug 22 '17 at 16:47 • Another four bytes with j i=last$0:[1+j(i-k)|k<-s,k<i]. Aug 22 '17 at 17:14

Pyth, 18 15 bytes

!x#eST.gsky_S*e


Test suite

A different sort of brute force. This starts by forming all collections of coins with up to k of each, where k is the largest coin, which is assumed to be the last coin. I believe this always sufficient to form two sets of coins with the same sum, one greedy and one shorter, whenever such a pair exists.

I then locate such a pair as follows:

The subsets are generated in order of increasing size, and lexicographically by position in the input secondarily. Group the coin collections by their sums, stably. Each coin collection is generated in descending order, so the greedy solution will be the first element of the group if and only if the greedy solution is optimal, and it will be the last element of the group lexicographically. Thus, we find the greedy solution, and filter on a nonzero index in the group. If the coin set is cannonical, this will filter out everything, so we simply logically negate the result and output.

Explanation:

!x#eST.gsky_S*e
!x#eST.gsky_S*eQQ   Variable introduction.
Q = eval(input()) - sorted list of coins.
eQ    Greatest coin in the list
*  Q   Repeat that many times.
S       Sort the coins
_        Reverse, so we have the coins in descending order.
y         Form all subsets, in increasing size then
decreasing lexicographic order.
.gsk          Group by sum
x#                 Filter by the index in the group of
eST              The last element lexicographically (greedy solution).
!                   Logically negate.

• Very nice - any idea why it hangs on herokuapp for [1, 2, 4, 6, 8] and gets killed with /opt/tryitonline/bin/pyth: line 5: 28070 Killed ... Exit code: 137 at TIO? Just out of memory? Oct 14 '16 at 4:10
• This uses 2^(num coins * last coin) bytes of memory. So for your example, 2^40. There aren't many machines with a terabyte of RAM Oct 14 '16 at 15:09
• I thought that may be the case, the description of the algorithm makes sense, but I hadn't calculated the numbers - so vast so quickly! Oct 14 '16 at 15:17

PHP, 323 Bytes

Same way as other count the coins until the sum of the two last elements in the array

<?function t($g){rsort($g);$m=array_slice($g,1);for($y=1,$i=$g[0];$i<$g[0]+$m[0];$i++){$a=$b=$i;$p=0;$r=$s=[];while($a||$b){$o=$n=0;$g[$p]<=$a?$a-=$r[]=$g[$p]:$o=1;($m[$p]??1)<=$b?$b-=$s[]=$m[$p]:$n=1;$p+=$o*$n;}$y*=count($r)<=count($s);}return$y;}for($i=0,$t=1;++$i<count($a=$_GET[a]);)$t*=t(array_slice($a,0,$i+1));echo$t;  My best and longest answer I believe >370 Bytes I give only an expanded version cause it is longer then my answer before for($x=1,$n=0,$f=[];++$n<count($a)-1;){
$z=array_slice($a,0,$n+1);$q=$a[$n]-$a[$n-1];
$i=array_fill(1,$c=max($a[$n+1]??1,11),"X");#$q*$a[$n]$f=range($a[$n],$c,$q);

$f[]=2*$a[$n]; for($d=[$z[$n]],$j=0;$j<$n;){$f[]=$a[$n]+$d[]=$z[$n]-$z[$j++]; } while($f){
$i[$t=array_pop($f)]="T"; foreach($d as $g) if(($l=$t+$g)<=$c)$f[]=$l; } foreach($i as$k=>$v){
if(in_array($k,$z))$i[$k]="S";
}
#var_dump($i); if($i[$a[$n+1]]=="X")$x*=0; } echo$x;


Online Version

1. Set all in the array to false == X

2. Set all numbers in the array you control to S

3. Found differences between the last S and the other S or 0

4. Start at last S in the array

5. Set all number to D Where Last S+ one of all differences

6. Begin at all D

7. SET "T" to D values in the array

8. GOTO 5 Repeat it with all found D I did it not really in the code

9. If next item in the Array has X it is a false case else True

Additional Steps Difference is in the case in the snippet 3 Between 1 and 4 are 2 X This means you need the second D by Step 5. After this value in this case 10 are all cases true I could see so far that there is a relationship between difference and the count in the array you control to calculate how much D (Step 5) you need to get the point before you find the last false case.

You set multiple values from the last item directly to true. These Points can make a difference to decide if it could been that the greedy count of coins with the next value is same then the multiple of the last in the array. On the other way you can set enemy

1. Set first enemy at 1+Last S

2. From this Point add each value in the array to set the next enemies

If you now have enemies and true cases in it the probability grows that the counts can be the same With more D the probability sinks.

table{width:80%}
td,th{width:45%;border:1px solid blue;}
<table>
<caption>Working [1,4]</caption>
<tr><th>Number</th><th>Status</th></tr>
<tr><td>1</td><td>S</td></tr>
<tr><td>2</td><td>X</td></tr>
<tr><td>3</td><td>X</td></tr>
<tr><td>4</td><td>S</td></tr>
<tr><td>5</td><td>X</td></tr>
<tr><td>6</td><td>X</td></tr>
<tr><td>7</td><td>D3</td></tr>
<tr><td>8</td><td>D4</td></tr>
<tr><td>9</td><td>X</td></tr>
<tr><td>10</td><td>D3D3</td></tr>
<tr><td>11</td><td>D4D3</td></tr>
<tr><td>12</td><td>D4D4</td></tr>
<tr><td>13</td><td>D3D3D3</td></tr>
<tr><td>14</td><td>D4D3D3</td></tr>
<tr><td>15</td><td>D4D4D4</td></tr>
<tr><td>16</td><td>D4D4D3</td></tr>
</table>
<ul>
<li>S Number in Array</li>
<li>D Start|End point TRUE sum Differences from last S</li>
<li>X False</li>
</ul>

plus ? Bytes Thank You @JonathanAllan to give me wrong test cases
262 Bytes Nearly but not good enough 4 wrong testcase in the moment

test cases [1,16,256] before should true after false

<?for($q=[1],$i=0,$t=1,$w=[0,1];++$i<count($a=$_GET[v]);$w[]=$a[$i],$q[]=$m)($x=$a[$i]-$a[$i-1])>=($y=$a[$i-1]-$a[$i-2])&&((($x)%2)==(($m=(($a[$i]+$x)*$a[$i-1])%$a[$i])%2)&&$m>array_sum($q)||(($x)%2)==0&&(($a[$i]-$a[$i-2])*2%$y)==0||in_array($m,$w))?:$t=0;echo$t;  Ascending Order of the Array Explanation for($q=[1],$i=0,$t=1,$w=[0,1] #$t true case $q array for modulos$w checke values in the array
;++$i<count($a=$_GET[v]) #before loop ;$w[]=$a[$i],$q[]=$m) # after loop $q get the modulo from the result and fill$w with the checked value

($x=$a[$i]-$a[$i-1])>=($y=$a[$i-1]-$a[$i-2])
# First condition difference between $a[i] and$a[$i-1] is greater or equal$a[$i-1] and$a[$i-2] # if$a[$-1] == 1$a[$i-2] will be interpreted as 0 && ## AND Operator with the second condition ( (($x)%2)==   # See if the difference is even or odd
(($m=(($a[$i]+$x)*$a[$i-1])%$a[$i])%2)&&$m>array_sum($q)
# After that we multiply the result with the lower value *$a[$i-1]
# for this result we calculate the modulo of the result with the greater value %$a[$i]
# if the difference and the modulo are both even or odd this belongs to true
# and the modulo of the result must be greater as the sum of these before
# Ask me not why I have make try and error in an excel sheet till I see this relation
||
(($x)%2)==0&&(($a[$i]-$a[$i-2])*2%$y)==0 # or differce modulator is even and difference $a[$i],$a[$i-1] is a multiple of half difference $a[$i-1],$a[$i-2]
||
in_array($m,$w) # if the modulo result is equal to the values that we have check till this moment in the array we can also neglect the comparison
)
?:$t=0; # other cases belongs to false echo$t; #Output


It looks like that what I have seen the table contains values from [1,2,3,4,5,6] and I change only the last item until 9. for 2to3 and 4to5 we create the value of the lower value in the modulo calculation

table{width:95%;}th,td{border:1px solid}
<table><tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>35</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>2</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>7</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>45</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>3</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>3</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>8</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>55</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>7</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>4</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>9</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>65</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>2</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></tr></table>

• Why do you split on ", " when you could split on ","; why do you split when you could take a list; why do you sort when you could take a sorted list? (I am also still unsure if the method you are using is infallible, have you a proof, because the literature I have skimmed through seems to suggest it is harder than what I think your code is doing.) Oct 13 '16 at 23:26
• @JörgHülsermann Sorry if I have caused any confusion, although it was different before you can now take a sorted list if you so choose. Oct 13 '16 at 23:44
• I'm afraid I think you'd have to test more than just mod 2 on the differences, as an example [1,2,5,11,17] is canonical. Maybe have a look at the paper linked in my answer. Oct 14 '16 at 16:26
• ...and just to confirm it with proud haskeller's code rather than mine: ideone.com/C022x0 Oct 14 '16 at 16:33
• @WheatWizard is [1,2,5,11,17] true or false? Oct 14 '16 at 17:02

JavaScript (ES6), 116 125 130

l=>eval("r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;for(x=l[0]*2;--x>1;r(x,g))g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));x")


This needs the input array sorted in descending order. For each value from 2N downto 2 (N being the max coin value), it find the number of coins from the greedy algorithm and try to find a smaller set of coins.

Less golfed

l=>{
// recursive function to to find a smaller set of coins
// parameter k is the max coin limit
r = (d,k) => d // check if difference is not 0
? --k // if not, and if the number of coins used will be less than limit
&& l.map(v => v>d || r(d-v, k))  // proceed with the recursive search
: x=1 // if diff is 0, value found, set x to 1 to stop the loop
for( x=l[0]*2; --x > 1; )
g=0, h=x, l.map(v=>(g += h/v|0, h %= v)), // find g with the greedy algorithm
r(x,g) // call with initial difference equal to target value
return x
}


Test

f=
l=>eval("r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;for(x=l[0]*2;--x>1;r(x,g))g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));x")

/* No eval
f=l=>{
r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;
for(x=l[0]*2;--x>1;r(x,g))
g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));
return x;
}*/

;[
[[100,50,20,10,5,2,1],1], [[4,3,1],0],
[[25,10,5,1],1], [[25,10,6,1],0],
[[3,2,1],1], [[30,17,8,1], 0],
[[12,8,3,1],0], [[13,8,2,1], 0]
].forEach(t=>{
var i=t[0],k=t[1],r=f(i),
msg=((r==k)?'OK ':'KO ')+i+' -> '+r
+ (r==k?'':' (should be '+k+')')
O.textContent += msg+'\n'
})

function test()
{
var i=I.value.match(/\d+/g).map(x=>+x).sort((a,b)=>b-a)
O.textContent = i+' -> '+f(i)+'\n'+O.textContent
}
#I { width:50% }
<input id=I value='1 4 9'><button onclick='test()'>test</button>
<pre id=O></pre>

Python, 218 211 205 bytes

-1 byte thanks to @TuukkaX (a space could be deleted between <3 and or)

from itertools import*
g=lambda x,c,n=0:x and g(x-[v for v in c if v<=x][0],c,n+1)or n
lambda c:len(c)<3or 1-any(any(any(x==sum(p)for p in combinations(c*i,i))for i in range(g(x,c)))for x in range(c[0]*2))


repl.it

Input in descending order.

Horribly brute force. Any set of a single unit coin and some other coin is canonical. For larger sets the smallest fail case, if one exists will be greater than or equal to the 3rd smallest coin (not sure myself how it could be equal!) and less than the sum of the two largest coins - see this paper (which actually references another but also gives an O(n^3) method).

g counts the coins used by the greedy method, and the unnamed function traverses the possible candidates (actually from 0 to one less than twice the largest coin to save bytes) and looks for any collection of less coins that also sum to that amount.

g works by performing what a cashier would, it recursively takes the largest coin less than or equal to the amount still to make up, [v for v in c if v<=x][0] away, and counts up the number of coins used, n.

The unnamed function returns 1 if len(c) is less than 3, and otherwise tests that it is not the case, 1-..., that any values in the range of possibilities, range(c[0]*2))), are possible with less coins, i in range(g(x,c)), by making a collection of that many of every coin, c*i, and examining all combinations of i coins, combinations(c*i,i), to see if any sum to the same value.

• @WheatWizard it returns False for [13,8,2,1] - I added it to the test cases. Added clarification that input is in descending order. Oct 13 '16 at 22:56
• 3or should work. Oct 14 '16 at 9:23
• Thanks @TuukkaX, also I could replace not(...) with 1-... Oct 14 '16 at 15:07

Jelly (fork), 15 14 bytes

SRæFµS€Ṃ=$Ṫµ€Ȧ  This solution uses the bounds for counter-examples from this paper. There, the author uses a tight bound for the counter-example, but in the interests of golfing, the range of the sum of coin denominations is used which is larger and contains that bound. This program computes all test cases in less than a second on my machine. Unfortunately, this relies on a branch of Jelly where I was working on implementing a Frobenius solve atom so you cannot try it online. Usage $ ./jelly eun 'SRæFµS€Ṃ=$Ṫµ€Ȧ' '1,2,4,6,8' 1  The performance is good and can solve all test cases at once in less than a second. $ time ./jelly eun 'SRæFµS€Ṃ=$Ṫµ€Ȧ¶Ç€' '[[1,3,4],[1,5,10,25],[1,6,10,25],[1,2,3],[1,8,17,30],[1,3,8,12],[1,2,8,13],[1,2,4,6,8]]' [0, 1, 0, 1, 0, 0, 0, 1] real 0m0.793s user 0m0.748s sys 0m0.045s  Explanation SRæFµS€Ṃ=$Ṫµ€Ȧ  Input: list of integers C
µ           Start a new monadic chain
S                 Sum
R                Range, [1, 2, ..., sum(C)]
æF              Frobenius solve for each X in the range using coefficients from C
This generates all vectors where the dot product of a
vector with C equals X, ordered by using values from the
start to end of C
µ€   Start a new monadic chain that operates on each list of vectors
S€           Sum each vector
$Monadic hook on the sums Ṃ Minimum (This is the optimal solution) = Vectorized equals, 1 if true else 0 Ṫ Tail (This is at the index of the greedy solution) Ȧ All, returns 0 if it contains a falsey value, else 1  JavaScript (ES6), 144132124122 110 bytes a=>![...Array(a[0]*2)].some((_,i)=>(g=(a,l=0,n=i)=>[a.filter(c=>c>n||(l+=n/c|0,n%=c,0)),-l*!n])(...g(a))[1]>0)  Requires the array to be sorted in descending order. Uses the observation in the linked paper that if the system is not canonical then there is at least one value less than 2a[0] which takes fewer coins when decomposed using the unused coins from the initial greedy algorithm. Edit: Saved 12 bytes by realising that I could check all the coins even though I had already reached the target value. Saved 8 bytes by switching my intermediate output from [l,b] to [b,-l]; this allowed me to pass the first result directly as the parameter of the second call, plus also a small saving detecting whether the second call was successful. Saved 2 bytes by moving the definition of g into the some callback, allowing me to avoid unnecessarily passing in the loop variable twice. Saved 12 bytes by switching from my recursive helper function to a call to filter (made possible by my intermediate output switch). Perl, 69 bytes Includes +2 for -pa Give coins in descending order on STDIN. You can optionally leave out the 1 coin. coins.pl <<< "4 3 1"  coins.pl: #!/usr/bin/perl -pa$_=!map{grep$>=$_&&($n=$G[$-$_]+1)<($G[$]||=$n),@F,/$/}1..2*"@F"


Builds up the number of coins used by the cashiers algorithm in @G for amounts 1 to twice the largest coin. For each amount checks that if that amount is reduced by 1 coin value the cashiers algorithm needs at most 1 less coin. If not this is a counterexample (or there was an earlier counterexample). I could stop at the first counterexample but that takes more bytes. So the time complexity is O(max_coin * coins) and space complexity is O(max_coin)`