Background
This is a follow up question to the question: Will the Hydra finally die?
As before a dangerous A Medusa have released a dangerous Hydra which is revived unless the exact number of heads it have is removed. The knights can remove a certain number of heads with each type of attack, and each attack causes a specific amount of heads to regrow. This time the knights are more impatient and having seen your previous abilities want you to** write a program or function that returns a list of hits which will leave the hydra 1 hit from death
Note that this is fundamentally different from Become the Hydra Slayer. in 2 aspects. 1: We are not asking for the optimal solution 2: each attack causes a different number of heads to grow back. this radically changes the approach needed.
For example:
input: heads = 2,
attacks = [1, 25, 62, 67],
growths = [15, 15, 34, 25],
output: [5, 1, 0, 0]
Explanation: The Hydra has 10 heads to start with, we have 4 different attacks
and for each attack, growth
gives us the number of heads that grows back. hits
gives us the number of times each attack is applied. So the number of heads the Hydra has after each attack is
2 -> 16 -> 30 -> 44 -> 58 -> 72 -> 62
Since 62
is a valid attack value (It lies in the attack list), we return True
since the Hydra will die on the next attack (be left with 0 heads). Note that the order for when the attacks are done is irrelevant.
2 -> 16 -> 6 -> 20 -> 34 -> 48 -> 62
Input
Input should contain heads
(an integer), attacks
(a list of how many heads can be removed), regrowths
(how many heads grow back per attack)
You may take input in any convenient method. This includes, but is not limited to
- A list of tuples
(1, 15, 5), (25, 15, 1), (62, 34, 0), (67, 25, 0)
- Lists
2, [1, 25, 62, 67], [15, 15, 34, 25], [5, 1, 0, 0]
- Reading values from STDIN
1 15 1 15 1 15 1 15 1 15 25 15
- A file of values
Output
- An array, or some way to easily indicate which hits the knights are to take. Example:
5 1 0 0
Note 1 Say that your input is attacks = [1, 25, 62, 67]
and the hydra has 25 heads left, then you cannot output the answer as [1,0,0,0]
, [0,0,0,1]
etc. Your output and input must be sorted similarly. Otherwise it will be very confusing for the Knights.
Note 2: Your program can never leave the Hydra with a negative number of heads. Meaning if the Hydra has 15 heads, an attack removes 17 heads and regrows 38. You may not perform this attack.
- You may assume that any input is valid. E.g every input will not overkill the Hydra and either result in a number of heads that is an attack value, or not.
Assumptions
There will always be as many attacks as regrowths
Every attack value will always correspond to one regrowth value which never changes. these are not required to be unique
Every input value will be a non-negative integer
You may assume that there always exists a solution (note that this is not neccecarily the case, but for our test data it is)
How you handle non valid inputs is up to you
Scoring
- This is a code-challenge you will be scored as follows: the total sum of hits your code produces from the test data + length of answer in bytes
- Note that how you input and parse the test data is not part of your code length. Your code should, as stated above simply take in some a headcount, attacks, regrowth's and return a list/representation of how many hits each attack has to be performed to leave the hydra exactly 1 hit from death.
Lowest score wins!
Test data
attacks = [1, 25, 62, 67],
growths = [15, 15, 34, 25],
use every integer from 1
to 200
as the number of heads. An sample from the first 100 can be found below. Again your program does not have to return these values, it is merely an example of how the scoring would work. As seen below the total sum for each of these hits are 535
meaning my score would be 535 + length of code in bytes
(If we wanted to use 1-100 instead of 1-200 as the number of heads of course)
1 [0, 0, 0, 0]
2 [5, 1, 0, 0]
3 [3, 2, 0, 0]
4 [7, 4, 0, 0]
5 [5, 5, 0, 0]
6 [4, 0, 0, 0]
7 [2, 1, 0, 0]
8 [6, 3, 0, 0]
9 [4, 4, 0, 0]
10 [8, 6, 0, 0]
11 [1, 0, 0, 0]
12 [5, 2, 0, 0]
13 [3, 3, 0, 0]
14 [7, 5, 0, 0]
15 [5, 6, 0, 0]
16 [4, 1, 0, 0]
17 [2, 2, 0, 0]
18 [6, 4, 0, 0]
19 [4, 5, 0, 0]
20 [3, 0, 0, 0]
21 [1, 1, 0, 0]
22 [5, 3, 0, 0]
23 [3, 4, 0, 0]
24 [7, 6, 0, 0]
25 [0, 0, 0, 0]
26 [4, 2, 0, 0]
27 [2, 3, 0, 0]
28 [6, 5, 0, 0]
29 [4, 6, 0, 0]
30 [3, 1, 0, 0]
31 [1, 2, 0, 0]
32 [5, 4, 0, 0]
33 [3, 5, 0, 0]
34 [2, 0, 0, 0]
35 [0, 1, 0, 0]
36 [4, 3, 0, 0]
37 [2, 4, 0, 0]
38 [6, 6, 0, 0]
39 [2, 0, 0, 0]
40 [3, 2, 0, 0]
41 [1, 3, 0, 0]
42 [5, 5, 0, 0]
43 [3, 6, 0, 0]
44 [2, 1, 0, 0]
45 [0, 2, 0, 0]
46 [4, 4, 0, 0]
47 [2, 5, 0, 0]
48 [1, 0, 0, 0]
49 [2, 1, 0, 0]
50 [3, 3, 0, 0]
51 [1, 4, 0, 0]
52 [5, 6, 0, 0]
53 [1, 0, 0, 0]
54 [2, 2, 0, 0]
55 [0, 3, 0, 0]
56 [4, 5, 0, 0]
57 [2, 6, 0, 0]
58 [1, 1, 0, 0]
59 [2, 2, 0, 0]
60 [3, 4, 0, 0]
61 [1, 5, 0, 0]
62 [0, 0, 0, 0]
63 [1, 1, 0, 0]
64 [2, 3, 0, 0]
65 [0, 4, 0, 0]
66 [4, 6, 0, 0]
67 [0, 0, 0, 0]
68 [1, 2, 0, 0]
69 [2, 3, 0, 0]
70 [3, 5, 0, 0]
71 [1, 6, 0, 0]
72 [0, 1, 0, 0]
73 [1, 2, 0, 0]
74 [2, 4, 0, 0]
75 [0, 5, 0, 0]
76 [1, 0, 1, 0]
77 [0, 1, 0, 0]
78 [1, 3, 0, 0]
79 [2, 4, 0, 0]
80 [3, 6, 0, 0]
81 [1, 0, 1, 0]
82 [0, 2, 0, 0]
83 [1, 3, 0, 0]
84 [2, 5, 0, 0]
85 [0, 6, 0, 0]
86 [1, 1, 1, 0]
87 [0, 2, 0, 0]
88 [1, 4, 0, 0]
89 [2, 5, 0, 0]
90 [0, 0, 1, 0]
91 [1, 1, 1, 0]
92 [0, 3, 0, 0]
93 [1, 4, 0, 0]
94 [2, 6, 0, 0]
95 [0, 0, 1, 0]
96 [1, 2, 1, 0]
97 [0, 3, 0, 0]
98 [1, 5, 0, 0]
99 [2, 6, 0, 0]
100 [0, 1, 1, 0]
535