Will the hydra finally die? Part II

Question

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

Answer 1

Python 3, 944 hits + 178 bytes = 1122

def f(t,s):
	q=[[[0]*len(s),t]];f={0}
	for p,t in q:
		if any(x==t for x,_ in s):return p
		for i,(k,y)in enumerate(s):n=t-k+y;q+=[[p[:i]+[p[i]+1]+p[i+1:],n]]*(n not in f);f|={n}

Try it online!

I can verify that 944 is the optimal solution; this is guaranteed to be optimal.

;f={0}, n=t-k+y, *(n nt in f), and f|={n} are not necessary for golfing but like with ovs's solution, I have them here just so the solution will run within seconds rather than years.

Trivial BFS solution.

Answer 2

05AB1E --no-lazy, 944 hits + 29 bytes = 973

The ²g∍ part is technically not necessary, but I wanted this to actually finish in seconds rather than years. I think this should return optimal solutions.

[NÅœε²gÅ0«²g∍œε³²-*O¹+²såiy,q

Try it online!

                   # Inputs: ¹ - initial number of heads
                   #         ² - list of attacks
                   #         ³ - list of regrowths
[                  # for N in 0, 1, 2, ...
 NŜ               # push integer partitions of N
    ε              # for each partition:
     ²gÅ0«         #   append as many 0's as there are attacks
          ²g∍      #   take as many integers as there are attacks from the front
              œ    #   take the permutations of this subset

ε                  # for each permutation y of a subset of the integer partition of N
 ³²-               # regrowths - attacks element-wise
    *              # multiply with y element-wise
     O             # take the sum of this
      ¹+           # and add the initial number of heads
        ²såi       # if this is in the list of attacks:       
            y,q    #   print y and exit the program

Here is my output for the 200 cases, generated with this test suite (finishes in 70 seconds locally):

  1 -> [0, 0, 0, 0]
  2 -> [5, 1, 0, 0]
  3 -> [2, 3, 0, 0]
  4 -> [7, 4, 0, 0]
  5 -> [4, 6, 0, 0]
  6 -> [4, 0, 0, 0]
  7 -> [1, 2, 0, 0]
  8 -> [6, 3, 0, 0]
  9 -> [3, 5, 0, 0]
 10 -> [8, 6, 0, 0]
 11 -> [1, 0, 0, 0]
 12 -> [5, 2, 0, 0]
 13 -> [2, 4, 0, 0]
 14 -> [7, 5, 0, 0]
 15 -> [1, 0, 1, 0]
 16 -> [4, 1, 0, 0]
 17 -> [1, 3, 0, 0]
 18 -> [6, 4, 0, 0]
 19 -> [3, 6, 0, 0]
 20 -> [3, 0, 0, 0]
 21 -> [1, 1, 0, 0]
 22 -> [5, 3, 0, 0]
 23 -> [2, 5, 0, 0]
 24 -> [7, 6, 0, 0]
 25 -> [0, 0, 0, 0]
 26 -> [4, 2, 0, 0]
 27 -> [1, 4, 0, 0]
 28 -> [6, 5, 0, 0]
 29 -> [0, 0, 1, 0]
 30 -> [3, 1, 0, 0]
 31 -> [1, 2, 0, 0]
 32 -> [5, 4, 0, 0]
 33 -> [2, 6, 0, 0]
 34 -> [2, 0, 0, 0]
 35 -> [0, 1, 0, 0]
 36 -> [4, 3, 0, 0]
 37 -> [1, 5, 0, 0]
 38 -> [6, 6, 0, 0]
 39 -> [1, 0, 1, 0]
 40 -> [3, 2, 0, 0]
 41 -> [1, 3, 0, 0]
 42 -> [5, 5, 0, 0]
 43 -> [0, 0, 0, 1]
 44 -> [2, 1, 0, 0]
 45 -> [0, 2, 0, 0]
 46 -> [4, 4, 0, 0]
 47 -> [1, 6, 0, 0]
 48 -> [1, 0, 0, 0]
 49 -> [1, 1, 1, 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 -> [0, 0, 2, 0]
 58 -> [1, 1, 0, 0]
 59 -> [1, 2, 1, 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 -> [1, 3, 1, 0]
 70 -> [3, 5, 0, 0]
 71 -> [0, 0, 1, 1]
 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 -> [1, 4, 1, 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, 0, 0, 2]
 86 -> [1, 1, 1, 0]
 87 -> [0, 2, 0, 0]
 88 -> [1, 4, 0, 0]
 89 -> [1, 5, 1, 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 -> [0, 0, 2, 1]
100 -> [0, 1, 1, 0]
101 -> [1, 2, 1, 0]
102 -> [0, 4, 0, 0]
103 -> [1, 5, 0, 0]
104 -> [0, 0, 0, 1]
105 -> [0, 1, 1, 0]
106 -> [1, 3, 1, 0]
107 -> [0, 4, 0, 0]
108 -> [1, 6, 0, 0]
109 -> [0, 0, 0, 1]
110 -> [0, 2, 1, 0]
111 -> [1, 3, 1, 0]
112 -> [0, 5, 0, 0]
113 -> [0, 0, 1, 2]
114 -> [0, 1, 0, 1]
115 -> [0, 2, 1, 0]
116 -> [1, 4, 1, 0]
117 -> [0, 5, 0, 0]
118 -> [0, 0, 2, 0]
119 -> [0, 1, 0, 1]
120 -> [0, 3, 1, 0]
121 -> [1, 4, 1, 0]
122 -> [0, 6, 0, 0]
123 -> [0, 0, 2, 0]
124 -> [0, 2, 0, 1]
125 -> [0, 3, 1, 0]
126 -> [1, 5, 1, 0]
127 -> [0, 0, 0, 3]
128 -> [0, 1, 2, 0]
129 -> [0, 2, 0, 1]
130 -> [0, 4, 1, 0]
131 -> [1, 5, 1, 0]
132 -> [0, 0, 1, 1]
133 -> [0, 1, 2, 0]
134 -> [0, 3, 0, 1]
135 -> [0, 4, 1, 0]
136 -> [1, 6, 1, 0]
137 -> [0, 0, 1, 1]
138 -> [0, 2, 2, 0]
139 -> [0, 3, 0, 1]
140 -> [0, 5, 1, 0]
141 -> [0, 0, 2, 2]
142 -> [0, 1, 1, 1]
143 -> [0, 2, 2, 0]
144 -> [0, 4, 0, 1]
145 -> [0, 5, 1, 0]
146 -> [0, 0, 0, 2]
147 -> [0, 1, 1, 1]
148 -> [0, 3, 2, 0]
149 -> [0, 4, 0, 1]
150 -> [0, 6, 1, 0]
151 -> [0, 0, 0, 2]
152 -> [0, 2, 1, 1]
153 -> [0, 3, 2, 0]
154 -> [0, 5, 0, 1]
155 -> [0, 0, 1, 3]
156 -> [0, 1, 0, 2]
157 -> [0, 2, 1, 1]
158 -> [0, 4, 2, 0]
159 -> [0, 5, 0, 1]
160 -> [0, 0, 2, 1]
161 -> [0, 1, 0, 2]
162 -> [0, 3, 1, 1]
163 -> [0, 4, 2, 0]
164 -> [0, 6, 0, 1]
165 -> [0, 0, 2, 1]
166 -> [0, 2, 0, 2]
167 -> [0, 3, 1, 1]
168 -> [0, 5, 2, 0]
169 -> [0, 0, 0, 4]
170 -> [0, 1, 2, 1]
171 -> [0, 2, 0, 2]
172 -> [0, 4, 1, 1]
173 -> [0, 5, 2, 0]
174 -> [0, 0, 1, 2]
175 -> [0, 1, 2, 1]
176 -> [0, 3, 0, 2]
177 -> [0, 4, 1, 1]
178 -> [0, 6, 2, 0]
179 -> [0, 0, 1, 2]
180 -> [0, 2, 2, 1]
181 -> [0, 3, 0, 2]
182 -> [0, 5, 1, 1]
183 -> [0, 0, 2, 3]
184 -> [0, 1, 1, 2]
185 -> [0, 2, 2, 1]
186 -> [0, 4, 0, 2]
187 -> [0, 5, 1, 1]
188 -> [0, 0, 0, 3]
189 -> [0, 1, 1, 2]
190 -> [0, 3, 2, 1]
191 -> [0, 4, 0, 2]
192 -> [0, 6, 1, 1]
193 -> [0, 0, 0, 3]
194 -> [0, 2, 1, 2]
195 -> [0, 3, 2, 1]
196 -> [0, 5, 0, 2]
197 -> [0, 0, 1, 4]
198 -> [0, 1, 0, 3]
199 -> [0, 2, 1, 2]
200 -> [0, 4, 2, 1]

Total:  944  hits

Answer 3

Jelly, 26 bytes + 944 attacks = 970 score

_Ḣ0œċNƭ€Se¥Ƈ/©¥@1#ṛ®ƲḢċⱮḢƲ

Try it online!

A monadic link taking [attack], [regrowth], heads as its argument and returning a list of counts of attacks.