19
\$\begingroup\$

Story

My local pizza delivery introduced new discount. You get 50% discount from every second item on your order.

But being greedy capitalists, they forgot to mention that they will rearrange items the way they need to give you as little as possible.

Example

Imagine you ordered

- Pizza $20
- Pizza $20
- Coke $2
- Coke $2

You expect to get $10 discount from the second pizza and $1 from the coke, but they rearrange it as

- Pizza $20
- Coke $2
- Pizza $20
- Coke $2

and give you $2.

Trick

Later I noticed that I can place as many orders as I want simultaneously, so I just split my order into two:

 1. 
 - Pizza $20
 - Pizza $20
 2. 
 - Coke $2
 - Coke $2

and I got the discount I deserve.

Problem

Can you please help me to write a program that calculate the maximum discount I can get by splitting my order.

It should accept a list of prices and return an amount.

For simplicity, all prices are even numbers, so the result is always an integer. Order is never empty. Input have no specific order.

This is code golf, do all usual rules applies.

Testcases

[10]             -> 0
[10,20]          -> 5
[10,20,30]       -> 10
[2,2,2,2]        -> 2
[4,10,6,8,2,40]  -> 9
\$\endgroup\$
12
  • 3
    \$\begingroup\$ You might want to give some test cases. Including some without duplicates and some with an odd number of items. \$\endgroup\$
    – Adám
    Aug 23 at 18:12
  • \$\begingroup\$ Added some testcases. If you can think of some other interesting cases please add it, or tell me I'll edit my question. \$\endgroup\$
    – talex
    Aug 23 at 18:41
  • \$\begingroup\$ Is the order guaranteed to be nonempty? \$\endgroup\$
    – att
    Aug 23 at 19:24
  • 3
    \$\begingroup\$ Just out of curiosity, is it just made up or does this silly pizza delivery really exist? \$\endgroup\$
    – Arnauld
    Aug 23 at 22:28
  • 5
    \$\begingroup\$ @Arnauld Yes. It based on real discount in real pizza delivery. Though I don't know will they rearrange your order, I newer tried it. Also there is probably delivery fee for small orders. So it is not entirely real, but "based on real story". \$\endgroup\$
    – talex
    Aug 24 at 7:17

19 Answers 19

16
\$\begingroup\$

Python 3, 33 bytes

lambda a:sum(sorted(a)[-2::-2])/2

Try it online!

This is my first answer :D

\$\endgroup\$
9
\$\begingroup\$

APL (Dyalog Extended), 11 10 bytes

−1 thanks to Jonah.

Anonymous tacit prefix function.

⌊∨+.÷∞2⍴⍨≢

Try it online!

 the tally of item prices

⍴⍨ use that to reshape…

0∞ the list [0,infinity]

+.÷ sum the division of the following by that:

 the item prices sorted into descending order

 floor (because the infinity is actually just the largest representable float and thus the values are slightly too large)

\$\endgroup\$
5
  • \$\begingroup\$ Nice idea. In J I was able to save 2 bytes by dividing by _ 2 (infinity, 2) instead of multiplying by 0 0.5. Looks like it would only save a byte in APL, but should work if APL has an infinity char? J solution 1#.\:~%_ 2$~# \$\endgroup\$
    – Jonah
    Aug 23 at 19:20
  • \$\begingroup\$ Looks like +/∨÷∞ 2⍴⍨≢ works for 10 but you get small floating point errors. \$\endgroup\$
    – Jonah
    Aug 23 at 19:30
  • 1
    \$\begingroup\$ @Jonah Nice idea. It is actually 9 because I don't need the space, but OP wants integers. ⌊∨+.÷∞2⍴⍨≢ is still only 10… \$\endgroup\$
    – Adám
    Aug 24 at 8:46
  • \$\begingroup\$ still -1 off current answer no? \$\endgroup\$
    – Jonah
    Aug 24 at 13:53
  • 1
    \$\begingroup\$ @Jonah Sure, I was just too busy to update. \$\endgroup\$
    – Adám
    Aug 24 at 14:00
6
\$\begingroup\$

05AB1E, 6 bytes

{RιθO;

Try it online!

Sort, Reverse, split into even and odd indices, get second part, sum and take half.

\$\endgroup\$
2
  • \$\begingroup\$ Aww, ι is 2 bytes in Jelly (Œœ), so a port of this comes to 7 bytes :( \$\endgroup\$ Aug 23 at 18:31
  • \$\begingroup\$ Yeah ι has won me quite a few challenges ;) \$\endgroup\$
    – ovs
    Aug 23 at 18:32
5
\$\begingroup\$

Perl 5, 49 44 bytes

sub f{@_=sort{$a-$b}@_;pop;pop()/2+(@_&&&f)}

Try it online!

-5 thanx to @kjetil-s; previous.

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

Jelly, 7 bytes

ṢU0Hƭ€S

Try it online!

Based on Adám's method, so go upvote that as well

How it works

ṢU0Hƭ€S - Main link. Takes a list L on the left
ṢU      - Sort L in descending order
    ƭ€  - Tie the previous 2 atoms, and alternate between the two for each element:
  0     -   At odd-indexed elements: Replace the element with 0
   H    -   At even-indexed elements: Halve the element
      S - Sum
\$\endgroup\$
1
  • \$\begingroup\$ Odd that Jelly doesn't have a "Sort descending" atom. \$\endgroup\$
    – Adám
    Aug 23 at 18:28
4
\$\begingroup\$

Vyxal s, 4 bytes

sṘy½

Try it Online!

5 bytes without the flag. Port of ovs's answer but with two key differences:

  • y, uninterleave, pushes both halves separately on the stack, so we don't need to get the second half
  • We have the s flag, so we don't need to sum the list in the code.
s    # Sort
 Ṙ   # Reverse
  y  # Interleave
   ½ # Take half (vectorised)
\$\endgroup\$
1
  • \$\begingroup\$ I'm not even half sorry. \$\endgroup\$
    – Adám
    Aug 23 at 20:30
4
\$\begingroup\$

Perl 5, 66 64 bytes

use List::Util pairmap,sum;sub f{sum+pairmap{$b/2}sort{$b-$a}@_}

Try it online!

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

Charcoal, 23 bytes

W⁻θυF№ι⌊ι⊞υ⌊ιI⊘ΣEυ×ι﹪κ²

Try it online! Link is to verbose version of code. Explanation:

W⁻θυF№ι⌊ι⊞υ⌊ι

Sort the input in descending order.

I⊘ΣEυ×ι﹪κ²

Multiply each value by its index modulo 2, then take half the sum.

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

Wolfram Language (Mathematica), 25 bytes

-Tr@Sort[-#/2][[2;;;;2]]&

Try it online!

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

JavaScript (ES6), 49 bytes

f=a=>1/a.sort((a,b)=>a-b)?0:a.pop(a.pop())/2+f(a)

Try it online!

How?

Because sort() operates in lexicographical order by default, we unfortunately need the explicit callback function (a, b) => a - b, although all test cases would pass without it.

We can stop as soon as the array is empty or only one element remains. Hence the test 1 / a which evaluates to:

  • Infinity (truthy) if the array is empty
  • A positive float (truthy) if the array is a singleton
  • NaN (falsy) when at least 2 elements remain

Because the .pop() method ignores its argument(s), the expression a.pop(a.pop()) simply discards the last element and returns the penultimate one.

\$\endgroup\$
2
  • \$\begingroup\$ I'm confused by the "lexical order as default" behaviour. Is there no way to prevent JavaScript from interpreting the input as strings? \$\endgroup\$
    – Stef
    Aug 24 at 13:40
  • 2
    \$\begingroup\$ @Stef Without any callback, the elements are explicitly converted to strings, no matter what the original type is. \$\endgroup\$
    – Arnauld
    Aug 24 at 14:41
3
\$\begingroup\$

R, 36 bytes

function(p)sum(-sort(-c(p,0))*0:1)/2

Try it online!

Assumes the price of each item in the order is non-negative.

\$\endgroup\$
3
  • \$\begingroup\$ 31 bytes \$\endgroup\$ Aug 24 at 14:45
  • \$\begingroup\$ @RobinRyder - Beautiful. You've got to post that: order(-p)%%2 is really clever! \$\endgroup\$ Aug 24 at 15:01
  • \$\begingroup\$ Thanks! Posted. \$\endgroup\$ Aug 24 at 15:10
3
\$\begingroup\$

R, 35 bytes

Thanks to att for spotting a bug.

function(p).5*p%*%!rank(-p,,"f")%%2

Try it online!

Takes the dot-product (%*%) of p/2 and a vector of 0s and 1s, with the 1s at the positions corresponding to even ranks in the sorted version of -p. We need to use .5*p instead of p/2 because of operator precedence. The "f" is needed to handle ties correctly in the vector of ranks.

Dominic van Essen also has an R answer, with a different strategy, currently at 36 bytes.

\$\endgroup\$
2
  • \$\begingroup\$ fails on [20, 10, 30] \$\endgroup\$
    – att
    Aug 24 at 18:29
  • \$\begingroup\$ @att Thanks for spotting the bug! Fixed, at the cost of +4 bytes. \$\endgroup\$ Aug 24 at 19:42
2
\$\begingroup\$

Husk, 7 bytes

ṁ½Ċ2Θ↔O

Try it online!

      O  # sort in ascending order
     ↔   # reverse
    Θ    # prepend a zero
  Ċ2     # get every 2nd element, starting at the first
ṁ½       # halve each of these, and then sum the results
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 100 78 73 bytes

r;f(a,l)int*a;{qsort(a,l,4,L"\x72b068bǃ");for(r=0;l--;++a)r+=*++a/2;r=r;}

Try it online!

Saved a whopping 22 bytes thanks to ceilingcat!!!

\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat That's awesome - thanks! :D \$\endgroup\$
    – Noodle9
    Aug 25 at 10:05
1
\$\begingroup\$

Ruby, 34 bytes

f=->l{*l,a,b=l.sort;b ?a/2+f[l]:0}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Japt -x, 8 bytes

+1 byte to handle unsorted inputs.

ñÍË*½*Eu

Try it

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

PHP, 68 bytes

FWIW, as small I can go down in PHP.

function d($a){rsort($a);for($c=0;$b=$a[++$i]/2;$i++)$c+=$b;echo$c;}

Try it online!

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

MathGolf, 9 bytes

êzhrg¥§Σ½

Try it online.

Explanation:

ê         # Read the inputs as integer-list
 z        # Sort this list in decreasing order
  h       # Push the length of the list (without popping the list itself)
   r      # Pop and push a list in the range [0, length)
    g     # Filter this list by:
     ¥    #  Modulo-2 (only keep the odd values)
      §   # Use those to index into the decreasing ordered input-list
       Σ  # Sum this list
        ½ # Halve the sum
          # (after which the entire stack - this value - is output implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

jq, 37 bytes

sort|.[range(length-1;-1;-2)]=0|add/2

Try it online!

\$\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.