# Hunt for discount

#### 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  • You might want to give some test cases. Including some without duplicates and some with an odd number of items. – Adám Aug 23, 2021 at 18:12 • Added some testcases. If you can think of some other interesting cases please add it, or tell me I'll edit my question. Aug 23, 2021 at 18:41 • Is the order guaranteed to be nonempty? – att Aug 23, 2021 at 19:24 • Just out of curiosity, is it just made up or does this silly pizza delivery really exist? Aug 23, 2021 at 22:28 • @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". Aug 24, 2021 at 7:17 ## 24 Answers # Python 3, 33 bytes lambda a:sum(sorted(a)[-2::-2])/2  Try it online! This is my first answer :D # 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) • 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$~# Aug 23, 2021 at 19:20
• Looks like +/∨÷∞ 2⍴⍨≢ works for 10 but you get small floating point errors. Aug 23, 2021 at 19:30
• @Jonah Nice idea. It is actually 9 because I don't need the space, but OP wants integers. ⌊∨+.÷∞2⍴⍨≢ is still only 10…
– Adám
Aug 24, 2021 at 8:46
• still -1 off current answer no? Aug 24, 2021 at 13:53
• @Jonah Sure, I was just too busy to update.
– Adám
Aug 24, 2021 at 14:00

# 05AB1E, 6 bytes

{RιθO;


Try it online!

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

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

# 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

• Odd that Jelly doesn't have a "Sort descending" atom.
– Adám
Aug 23, 2021 at 18:28

# Vyxals, 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)

• I'm not even half sorry.
– Adám
Aug 23, 2021 at 20:30

## Perl 5, 4944 43 bytes

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


Try it online!

-6 thanx to @kjetil-s; previous.

• Shave 5 bytes with: Try it online! Aug 24, 2021 at 12:59
• Can shave 1 more byte with: Try it online! Sep 29, 2021 at 8:56

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

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

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

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

## Perl 5, 66 64 bytes

use List::Util pairmap,sum;sub f{sum+pairmap{$b/2}sort{$b-$a}@_}  Try it online! # 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. # Wolfram Language (Mathematica), 25 bytes -Tr@Sort[-#/2][[2;;;;2]]&  Try it online! # 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. • I'm confused by the "lexical order as default" behaviour. Is there no way to prevent JavaScript from interpreting the input as strings? – Stef Aug 24, 2021 at 13:40 • @Stef Without any callback, the elements are explicitly converted to strings, no matter what the original type is. Aug 24, 2021 at 14:41 # 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!!! # Nibbles, 6 bytes /+%~>>\<_~  Attempt This Online! /+%~>>\<_~ _ Input as a list of numbers < Sort \ Reverse >> Remove first item %~ Take every odd-indexed item + Sum / ~ Halve  # 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  # Ruby, 34 bytes f=->l{*l,a,b=l.sort;b ?a/2+f[l]:0}  Try it online! # Japt-x, 8 bytes +1 byte to handle unsorted inputs. ñÍË*½*Eu  Try it # 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! # 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)  # jq, 37 bytes sort|.[range(length-1;-1;-2)]=0|add/2  Try it online! # 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. # 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. # 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.

# 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