18
\$\begingroup\$

In Canada, the penny is no longer circulated. Cash payments are rounded to the nearest 5 cents.

Money can be saved by splitting purchases. For example, two $1.02 items cost $2.04 which rounds up to $2.05, but when buying the items in separate purchases, each price rounds to $1.00 for a total of $2.00. However, when buying two items at $1.03 each, it is better to buy them in a single purchase.

Another way to save money is using a credit card when rounding is unfavourable, because credit payments are not rounded. If we want two $1.04 items, the total price will round up to $2.10 regardless of how we split the purchases. Therefore, we should pay for these items with a credit card.

Write a function or program which accepts a list of prices of items as integers in cents and outputs the lowest possible total price (in cents) for those items which can be achieved through a sequence of purchases, each either by cash or by credit.

Shortest code wins.

Test cases

[] : 0
[48] : 48
[92, 20] : 110
[47, 56, 45] : 145
[55, 6, 98, 69] : 225
[6, 39, 85, 84, 7] : 218
[95, 14, 28, 49, 41, 39] : 263
[92, 6, 28, 30, 39, 93, 53] : 335
[83, 33, 62, 12, 34, 29, 18, 12] : 273
[23, 46, 54, 69, 64, 73, 58, 92, 26] : 495
[19, 56, 84, 23, 20, 53, 96, 92, 91, 58] : 583
[3, 3, 19, 56, 3, 84, 3, 23, 20, 53, 96, 92, 91, 58, 3, 3] : 598
[2, 3, 4, 4, 4, 4, 4] : 19
\$\endgroup\$
5
\$\begingroup\$

Ruby, 119 105 characters (93 body)

def f s
a,b,c,d=(1..4).map{|i|s.count{|x|x%5==i}}
s.reduce(0,:+)-a-(c-m=c>d ?d:c)/2-2*(b+m+(d-m)/3)
end

Two characters may be saved if the algorithm is allowed to crash when fed an empty shopping list.

\$\endgroup\$
  • \$\begingroup\$ You may change to s.reduce(:+) (normally you even don't need parantheses, but in your case...) and inline m for additional 2 chars. \$\endgroup\$ – Howard May 30 '13 at 8:19
  • \$\begingroup\$ And of course a,b,c,d=(1..4).map{|i|s.count{|x|x%5==i}}. \$\endgroup\$ – Howard May 30 '13 at 8:25
  • \$\begingroup\$ @Howard if I remove 0, from the reduce call, the code breaks for the empty input. I did mention that in the answer. Inlining m doesn't seem to help. Thanks for the last suggestion - that was stupid from me. \$\endgroup\$ – John Dvorak May 30 '13 at 8:29
  • 1
    \$\begingroup\$ You can write (c-m=c>d ?d:c) which gives you two chars. \$\endgroup\$ – Howard May 30 '13 at 8:36
  • \$\begingroup\$ @Howard I thought that would break because - has higher priority than =. Is it that the assignment has a high priority on its left side (as in, to ensure the left operand is an lvalue)? \$\endgroup\$ – John Dvorak May 30 '13 at 8:44
5
\$\begingroup\$

GolfScript (54 chars)

~]4,{){\5%=}+1$\,,}%~.2$>$:m- 3/m+@+2*@@m- 2/++~)+{+}*

This is a program which takes input from stdin as space-separated values. One character could be saved by forcing the input format to instead be as GolfScript arrays.

Test cases online

The most interesting trick is .2$>$ for a non-destructive min operator.


My analysis of the maths is essentially the same as Jan's and Ray's: considering values mod 5, the only saving is on transactions worth 1 or 2. The credit card option means that we never round up. So an item which costs 5n+2 cents can't benefit from bundling; nor can an item worth 5n+1 cents (because combining two 1-cent savings into a 2-cent saving doesn't give any benefit). 0 is the additive identity, so the only interesting cases involve values of 3 and 4. 3+3 = 1 and 3+4 = 4+4+4 = 2; if we have mixed 3s and 4s then we optimise by preferring 3+4 over 3+3 (strictly better) or 4+4+4 (equivalent).

\$\endgroup\$
  • \$\begingroup\$ +1 - although those spaces look so lavishly ;-) You might remove them by saving -m (~):m) unfortunately with no reduction in char count. \$\endgroup\$ – Howard Jun 7 '13 at 17:12
  • \$\begingroup\$ @Howard, I know, I tried it too. :D \$\endgroup\$ – Peter Taylor Jun 7 '13 at 21:00
3
\$\begingroup\$

C++: 126 character

int P(int*m,int i){int t=0,h=0,d;while(i>-1){d=m[i]%5;t+=m[i--];d<3?t-=d:d==4?h++,t-=2:h--;}h<0?t+=h/2:t+=(h-h/3)*2;return t;}

Welcome to give guidance to put this program becomes shorter.Here is the test program,compile with tdm-gcc 4.7.1 compiler and run normally.

#include<iostream>
using namespace std;

//m[i]表示单个商品的价格,t表示所有商品总价格,
//d为单个商品价格取模后的值,h为单个商品价格取模后值为3的个数,
//f为单个商品价格取模后值为4的个数
int P(int*m,int i){int t=0,h=0,d;while(i>-1){d=m[i]%5;t+=m[i--];d<3?t-=d:d==4?h++,t-=2:h--;}h<0?t+=h/2:t+=(h-h/3)*2;return t;}

int main() {
int p1[1]={48};
int p2[2]={92,20};
int p3[3]={47,56,45};
int p4[4]={55,6,98,69};
int p5[5]={6,39,85,84,7};
int p6[6]={95,14,28,49,41,39};
int p7[7]={92,6,28,30,39,93,53};
int p8[8]={83,33,62,12,34,29,18,12};
int p9[9]={23,46,54,69,64,73,58,92,26};
int p10[10]={19,56,84,23,20,53,96,92,91,58};
int p11[10]={1,2,3,4,5,6,7,8,9,10};
cout<<P(p1,0)<<endl
    <<P(p2,1)<<endl
    <<P(p3,2)<<endl
    <<P(p4,3)<<endl
    <<P(p5,4)<<endl
    <<P(p6,5)<<endl
    <<P(p7,6)<<endl
    <<P(p8,7)<<endl
    <<P(p9,8)<<endl
    <<P(p10,9)<<endl
    <<P(p11,9)<<endl;

return 0;
}
\$\endgroup\$
1
\$\begingroup\$

R 143

function(x)min(sapply(rapply(partitions::listParts(length(x)),
                             function(i)min(sum(x[i]),5*round(sum(x[i])/5)),h="l"),
                      function(x)sum(unlist(x))))

Tests (where P is an alias for the code above)

> P(c(48))
[1] 48
> P(c(92, 20))
[1] 110
> P(c(47, 56, 45))
[1] 145
> P(c(55, 6, 98, 69))
[1] 225
> P(c(6, 39, 85, 84, 7))
[1] 218
> P(c(95, 14, 28, 49, 41, 39))
[1] 263
> P(c(92, 6, 28, 30, 39, 93, 53))
[1] 335
> P(c(83, 33, 62, 12, 34, 29, 18, 12))
[1] 273
> P(c(23, 46, 54, 69, 64, 73, 58, 92, 26))
[1] 495
> P(c(19, 56, 84, 23, 20, 53, 96, 92, 91, 58))
[1] 583
\$\endgroup\$
1
\$\begingroup\$

Mathematica 112 126 167 157

Edit: Cases of {3, 3} and {4,4,4} now handled thanks to Peter Taylor and cardboard_box.

n_~g~o_ := {a___, Sequence @@ n, b___} :> {a, b, o};
f@s_ := Tr@Join[#[[2]], Sort@#[[1]] //. {1 -> 0, 2 -> 0, g[{3, 4}, 5], g[{3, 3}, 5], 
   g[{4, 4, 4}, 10]}] &[Transpose[{m = Mod[#, 5], # - m} & /@ s]]

Note: Non-purchases (test case #1) are entered as f[{0}].

How it works

  1. For each item, the greatest multiple of 5 less than the respective price will be paid regardless of form of payment. (No getting around that.)
  2. The remainders of Mod[n, 5] are then processed: 1's and 2's become 0's. Zeros stay unchanged.
  3. Each pair {3, 4} -> {5}; afterwards each pair {3, 3} -> {5}; then the triple, {4,4,4}-> {10}, if applicable.
  4. The remaining 4's, if any, remain unchanged (paid by credit card).
  5. Original multiples of 5 summed with remainders that were tweaked (or not) in steps (2) to (4).

Testing

a12 adjusts for {3,3} a13 adjusts for {4,4,4}

a1={0};
a2={48};
a3={92,20};
a4={47,56,45};
a5={55,6,98,69} ;
a6={6,39,85,84,7};
a7={95,14,28,49,41,39};
a8={92,6,28,30,39,93,53};
a9={83,33,62,12,34,29,18,12};
a10={23,46,54,69,64,73,58,92,26};
a11={19,56,84,23,20,53,96,92,91,58};
a12={3,3,19,56,3,84,3,23,20,53,96,92,91,58,3,3};
a13={2,3,4,4,4,4,4};

f /@ {a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13}

{0, 48, 110, 145, 225, 218, 263, 335, 273, 495, 583, 598, 19}

\$\endgroup\$
  • 1
    \$\begingroup\$ What about {3,3}? \$\endgroup\$ – Peter Taylor Jun 4 '13 at 15:10
  • \$\begingroup\$ @PeterTaylor. Good point. It slipped by. \$\endgroup\$ – DavidC Jun 4 '13 at 16:22
  • \$\begingroup\$ What about {4,4,4}? I think with {3,4} -> {5}, {3,3} -> {5} and {4,4,4} -> {10} (in that order) it should give optimal answers. \$\endgroup\$ – cardboard_box Jun 4 '13 at 21:34
  • \$\begingroup\$ @cardboard_box You are right! See update. \$\endgroup\$ – DavidC Jun 4 '13 at 22:23
  • \$\begingroup\$ I added your additional test cases to the question. The ones I had were generated randomly so those corner cases didn't show up. \$\endgroup\$ – cardboard_box Jun 4 '13 at 22:47
1
\$\begingroup\$

Python 3 (115 chars)

m=eval(input());t=a=b=0
for v in m:d=v%5;t+=v-d*(d<3);a+=d==3;b+=d==4
d=min(a,b);a-=d;b-=d;print(t-d*2-a//2-b//3*2)

Python 2 (106 chars)

m=input();t=a=b=0
for v in m:d=v%5;t+=v-d*(d<3);a+=d==3;b+=d==4
d=min(a,b);a-=d;b-=d;print t-d*2-a/2-b/3*2
\$\endgroup\$
  • 2
    \$\begingroup\$ The question asks for the total price, so there should be one output for the entire list. For example, the input [3,4,9] should give 14, because you can combine the 3 and 4 cent items to get a 7 cent purchase which you pay in cash with 5 cents, and the remaining 9 cent item you pay with credit because it would otherwise round up. \$\endgroup\$ – cardboard_box May 29 '13 at 22:16
  • 2
    \$\begingroup\$ Given 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, this gives 0.0, 0.0, 2.5, 3.33, 5.0, 5.0, 5.0, 7.5, 8.33, 10.0, which sums to 46.66. However, the correct answer is 45, so the sum of the numbers you print is not the correct answer, and therefore this solution is incorrect. \$\endgroup\$ – Nolen Royalty May 30 '13 at 6:09
  • \$\begingroup\$ This answer was wroted when job not contain "total" yet \$\endgroup\$ – AMK Jun 2 '13 at 14:16
  • 2
    \$\begingroup\$ I'm afraid I have to recommend deletion. Asker didn't change the requirements - he clarified them. If the price for each item separately were desired, then why the mention of a "sequence of purchases / single purchase" and the discussion of which one is favourable? \$\endgroup\$ – John Dvorak Jun 3 '13 at 12:27
  • \$\begingroup\$ I delete wrong answers. Now It's shortest Python answers \$\endgroup\$ – AMK Jun 12 '13 at 13:30
0
\$\begingroup\$

APL, 58 characters

{a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}

The program is essentially a direct translation of Jan Dvorak's Ruby solution.


      {a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}⍬
0
      {a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}95 14 28 49 41 39
263
      {a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}19 56 84 23 20 53 96 92 91 58
583

is the empty vector.

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

Julia 83C

C=L->let
w,z,x,y=map(i->[i==x%5for x=L]|sum,1:4)
L|sum-(x+2w+3min(x,y)+4z)>>1
end

Explaination:

In one purchase, you can save 2 cent at most. So if you have a combination that can save you 2 cents, just buy it that way and it will be optimial. For example, if you have x items with price 3(mod 5) and y items with price 4(mod 5), you can make min(x, y) number of (3, 4) pairs, which save you 2 min(x, y) cents. Then you use the rest 3's, if any, to save you max(0, x-min(x,y)) / 2 cents. This can also be calculated by (max(x,y)-y)/2

w = sum(1 for p in prices if p % 5 == 1)
z = sum(1 for p in prices if p % 5 == 2)
x = sum(1 for p in prices if p % 5 == 3)
y = sum(1 for p in prices if p % 5 == 4)

ans = sum(prices) - (w + 2 z + 2 min(x, y) + div(max(x, y) - y, 2))
    = sum(prices) - (2w + 4z + 4 min(x, y) + x + y - min(x, y) - y) `div` 2
    = sum(prices) - (2w + 4z + 3 min(x, y) + x) `div` 2

Edit

This solution is wrong.

\$\endgroup\$
  • \$\begingroup\$ +1 for using a relatively unknown language that might be interesting to learn \$\endgroup\$ – John Dvorak Jun 6 '13 at 20:06
  • \$\begingroup\$ It's a new language under active development. It combines many strengh from different languages. Hope that more people can known it. \$\endgroup\$ – Ray Jun 6 '13 at 20:12
  • \$\begingroup\$ The analysis isn't quite complete, because if you have 4 4 4 3 3 then 4 4 4 is a combination which can save 2 cents, but buying it that way isn't optimal. (In fact, you don't seem to be taking 4 4 4 into account at all. Doesn't this code fail the last test case?) \$\endgroup\$ – Peter Taylor Jun 7 '13 at 16:01

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.