17
2
This tweet lists the possible orders for Wings of a Chinese restaurant1:
When ordering Pizza I usually calculate what size gives me the best Pizza-price ratio which is a simple calculation. However minimizing the price of an order at this restaurant isn't such a simple task, so I'd like to be prepared for my next order there.
Challenge
Given an integer greater or equal to \$4\$, your task is to return one possible order which minimizes the price (overall cheapest) and the number of deals.
Example
If I were to order \$100\$ Wings, it turns out the best bargain will cost \$$111.20\$. However there are multiple orders which will cost that amount, namely:
[50,50],[25,25,50],[25,25,25,25]
Since the first order will use the least amount of deals (\$2\$) the result will be [50,50]
.
Rules
- Input will be some integer \$n \geq 4\$
- Output will be a list/array/... of order sizes that sum up to \$n\$ and minimize the order's price
- you may choose to return all possible orders
Testcases
4 -> [4] (4.55)
23 -> [23] (26.10)
24 -> [6,18],[9,15],[12,12] (27.20)
31 -> [6,25] (34.60)
32 -> [4,28],[6,26],[7,25] (35.75)
33 -> [4,29],[5,28],[6,27],[7,26],[8,25] (36.90)
34 -> [6,28],[9,25] (38.00)
35 -> [35] (39.15)
125 -> [125] (139.00)
200 -> [25,50,125] (222.40)
201 -> [26,50,125] (223.55)
250 -> [125,125] (278.00)
251 -> [26,50,50,125] (279.15)
418 -> [15,28,125,125,125],[18,25,125,125,125] (465.20)
1001 -> [26,50,50,125,125,125,125,125,125,125] (1113.15)
12345 -> [15,80,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125],[25,70,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125],[45,50,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125] (13728.10)
Note: These testcases list all possible outputs including the price, you're only required to output one and you're not required to output the price!
1: You can find the data as a CSV here.
3The real question is, who orders 200 or even 100 wings? ... – Erik the Outgolfer – 2018-10-26T21:43:26.783
Why the Kolmogorov-complexity tag? Also, very hungry people @EriktheOutgolfer – Veskah – 2018-10-26T21:49:18.727
Kolmogorov is all about fixed output though. If the challenge was to output the menu, then it'd be a good tag for this. – Veskah – 2018-10-26T22:02:05.573
@Veskah: It's not, it's about generating a fixed object (which often happens to be the output). For example the third challenge in the tag-wiki is not about constant output.
– ბიმო – 2018-10-26T22:07:04.037Shoot, even after I code a solution, I'm completely unsure if it is right or not – Quintec – 2018-10-26T23:07:09.710
2@Quintec: Why, do you need more testcases? – ბიმო – 2018-10-26T23:24:13.093
1Two answers have misinterpreted the requirements, as only needing to minimise the price. Since minimising the price and number of deals is ambiguous (lowest price available from the ways with the lowest number of deals, or lowest number of deals available from the ways with the lowest price) it would be worth editing the requirement to be more explicit – trichoplax – 2018-10-26T23:49:44.050
@EriktheOutgolfer Party hosts and work-from-home developers (don't judge me) – souldeux – 2018-10-27T01:17:14.183
4
Related: What to do with 10 liters Heinz BBQ sauce? ;)
– Laurel – 2018-10-27T04:12:50.9331I notice that for $ n \leq 23 $ the price is given by $ \frac 1 {20} \lceil \left ( \frac {68 n} 3 \right ) \rceil $, while the prices for $ 25 < n <= 50 $ can be split into $ 25 $ and $ n - 25 $ (for $ n < 29 $ you can't buy them separately but the formula still gives the appropriate value). $ 70 $, $ 80 $ and $ 125 $ can also be derived from earlier values, so if you can use them they will reduce the number of deals. The other values are uneconomic. – Neil – 2018-10-27T11:15:25.037