Hunt for discount

Question

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

Answer 1

Python 3, 33 bytes

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

Try it online!

This is my first answer :D

Answer 2

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)

Answer 3

05AB1E, 6 bytes

{RιθO;

Try it online!

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

Answer 4

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

Answer 5

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)

Answer 6

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.

Answer 7

Perl 5, 49 44 43 bytes

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

Try it online!

-6 thanx to @kjetil-s; previous.

Answer 8

Wolfram Language (Mathematica), 25 bytes

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

Try it online!

Answer 9

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.

Answer 10

Perl 5, 66 64 bytes

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

Try it online!

Answer 11

Charcoal, 23 bytes

Ｗ⁻θυＦ№ι⌊ι⊞υ⌊ιＩ⊘ΣＥυ×ι﹪κ²

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

Ｗ⁻θυＦ№ι⌊ι⊞υ⌊ι

Sort the input in descending order.

Ｉ⊘ΣＥυ×ι﹪κ²

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

Answer 12

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.

Answer 13

Nibbles, 6 bytes

/+`%~>>\`<_~

Attempt This Online!

/+`%~>>\`<_~
          _  Input as a list of numbers
        `<   Sort
       \     Reverse
     >>      Remove first item
  `%~        Take every odd-indexed item
 +           Sum
/          ~ Halve

Answer 14

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

Answer 15

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!

Answer 16

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)

Answer 17

TI-Basic, 27 bytes

Prompt A
SortD(ʟA
sum(ʟAseq(fPart(I/2),I,0,dim(ʟA)-1

Output is stored in Ans and is displayed at the end.

Answer 18

Jelly, 7 bytes

~ỤỤ~ḂHḋ

Try it online!

Or, more to the point, ỤỤ^LḂḋH. Turns out, there's a ton of 7-byters--and when that's the case, it really seems like there ought to be one in 6. I wouldn't normally post this until I've found something that does beat the existing solution in 7, but it's continued to elude me, and this is at least different enough for someone else to maybe springboard off of.

 ỤỤ        Get a permutation of [1 .. len(input)] in the same order as
~          the bitwise negation of the input.
   ~Ḃ      Is the bitwise negation of each element odd?
     H     Halve the results,
      ḋ    and take the dot product with the input.

Bonus in-between: ṢUḊm2SH

Answer 19

C (gcc), ^{100 78} 73 bytes (maybe 74 bytes because of the L"!")

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!!!

Answer 20

PARI/GP, 43 30 bytes

saved 13 bytes thanks to the comment.

adapted from @Basto's answer

---

30 bytes:

a->-[0..#a-1]%2/2*vecsort(-a)~

Try it online!

34 bytes:

a->[0..#a-1]%2/2*vecsort(-a)~*(-1)

Try it online!

---

43 bytes:

a->sum(i=0,(#a-2)\2,vecsort(a)[#a-1-2*i])/2

Try it online!

---

It calculates the sum of alternating elements in the input array a after sorting it in decreasing order.

Answer 21

Ruby, 34 bytes

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

Try it online!

Answer 22

Japt -x, 8 bytes

+1 byte to handle unsorted inputs.

ñÍË*½*Eu

Try it

Answer 23

jq, 37 bytes

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

Try it online!

Answer 24

Haskell + hgl, 17 bytes

mF(//2)<cr<uaL<sr

Explanation

This is a very simple chain of operations:

• sr sorts the input.
• uaL divides it into two lists, those at even indices and those at odd indices.
• cr gets the even indices.
• mF sums them together using a custom function ...
• (//2) divides by 2.

Reflections

Ok so there's a lot to reflect on.

The fact that uaL exists is basically just dumb luck. I made uaL because I needed it to make something else and I just gave it a name because I thought it could come in handy at some point. If it didn't exist this would be a lot longer.

Initially I was going to use im which takes a list and a list of indices and produces a list of all the indices. This would have been pretty cumbersome.

We probably need a couple of index / slicing builtins because next time we probably won't be as lucky that something like uaL just happens to exist.

Next up is dividing by 2. Arithmetic is something I haven't put a lot of time into so I know it's lacking. However, there should be builtins to divide things by small amounts. dv2 should exist and would have saved a byte. I also noticed that fdv a function that is supposed to be the flip of dv is exactly the same as dv. This is just a bug.

So there's a lot to work on here.

Answer 25

Arturo, 35 bytes

$=>[/∑map reverse sort&[x,y][y]2]

Try it

Same method as most of the other answers. Sort, reverse, take every other element, sum, and halve.

Answer 26

Thunno, \$ 9 \log_{256}(96) \approx \$ 7.41 bytes

z;ZlAKS2/

Attempt This Online! or verify all test cases

Port of ovs's 05AB1E answer

Explanation

z;ZlAKS2/  # Implicit input
z;         # Reverse-sort
  Zl       # Uninterleave
    AK     # Last item
      S    # Sum
       2/  # Halve
           # Implicit output

Answer 27

Java, 86 bytes

L->{int s=0,i=L.size();for(L.sort((a,b)->a<b?1:-1);i-->0;)s+=i%2*L.get(i);return s/2;}

Try it online.

Explanation:

L->{                      // Method with Integer-List parameter and Integer return-type
  int s=0,                //  Sum-integer, starting at 0
      i=L.size();         //  Index-integer, starting at the size of the input-List
  for(L.sort(             //  Sort the input-List
        (a,b)->a<b?1:-1); //  in reversed order
      i-->0;)             //  Loop `i` in the range (size,0]:
    s+=                   //   Increase the sum by:
       i%2                //    Check if the current `i` is odd (1 if odd; 0 if even)
       *L.get(i);         //    And multiply that to the current `i`'th value
  return s/2;}            //  After the loop, return halve the sum