Thanks to Vladimir Zelevinsky for creating this curious problem!

Medieval Medicine

Brother Asclepius needs your help. He's the one who writes prescriptions for sick people, and he's got his hands full.

To help him, you need to know everything about modern medieval medicine. Fortunately, it is not a difficult subject; the entirety of humanity's medical knowledge can be summarized in a few brief paragraphs on this very page.

As everyone knows, human health is governed by humors, of which they are four. They have their names (blood, yellow bile, black bile, and phlegm), but these names do not matter for our purposes. All you need to know is that there are four of them, and that each humor has a level. This level can be any integer: positive, negative, or zero. A humor at level zero is considered balanced. If all four humors are balanced, the human is healthy. If even one humor is imbalanced, the human feels sick. We are going to write the levels of the four humors as a four-element integer array, denoting it with brackets and a prefix H. For example, a person with H[0,0,0,0] is healthy because all four humors are balanced; a person with humors H[1,0,-2,0] is sick because the first and the third humors are imbalanced.

What makes humors imbalanced is a disease. A disease can also be described as a four-element integer array, which we will denote with the prefix D. Disease affects humors by adding its levels element-wise to the humors daily. For example, if a healthy human H[0,0,0,0] catches a disease D[1,0,-2,0], then in one day the humors will be H[0+1,0+0,0-2,0+0] = H[1,0,-2,0]; in two days, the humor levels will be H[2,0,-4,0], and so on.

Fortunately, humanity has discovered the wonders of medicine. Each medicine can also be described as a four-element integer array, which we will denote with the prefix M. Medicine acts on the disease by - you can probably guess where this is going - adding its levels to the levels of the disease. For example, if a human has a disease D[1,0,-2,0] and takes a medicine M[-2,0,2,2], the next day the disease will have levels D[1-2,0+0,-2+2,0+2] = D[-1,0,0,2]. Since medicines are quite strong, a patient can only take a single dose of a single medicine per day. Also, since it's important to cure patients quickly, the patient should take some medicine every day during their course of treatment.

To summarize the above: each day, first the disease acts on the humors by adding its levels to the humors; second, the medicine acts on the disease by adding the medicine levels to the disease levels.

Now, where do you, the doctor, come in? When a patient feels sick, they see you the very first day. Since the patient was healthy (H[0,0,0,0]) the day before, on this day - day one - the levels of their humors are identical to the levels of the disease. You can easily determine what these levels are (part of your puzzle input), because every doctor must have a well-developed sense of humors.

After you know the levels of the humors and of the disease, you can write a prescription for a course of treatment that starts the same day. So on this first day, the disease affects the previously healthy human; then the human takes the first medicine, which affects the disease. On the second day, the disease (with its levels modified by the first day's medicine) affects the human, after which the human takes the second prescribed medicine, which affects the disease; and so on.

Your task is to cure the patient by prescribing a course of medicines, to be taken one per day. It is important, however, to define what is meant by "cure." Let's work our way through an example.

Let's say you receive a patient with levels H[1,0,-2,0]. Since this is day one, it's obvious that they have a disease with levels D[1,0,-2,0]. Then you can prescribe a medicine with levels M[-1,0,2,0]. After the patient takes this medicine, the disease will have the levels D[1,0,-2,0] + M[-1,0,2,0] = D[0,0,0,0] and will stop affecting the patient.

Does this mean the patient is cured? No, it does not. Since the patient's humors remain imbalanced at H[1,0,-2,0], the human will continue feeling sick.

What if instead of prescribing M[-1,0,2,0] on day one you prescribed M[-2,0,4,0]? In this case, at the end of day one, the disease will have levels D[1,0,-2,0] + M[-2,0,4,0] = D[-1,0,2,0]. Then on the second day, the human levels will change to H[1,0,-2,0] + D[-1,0,2,0] = H[0,0,0,0] and the human will feel fine.

Does this mean they are cured? Again the answer is no, because the disease (with its non-zero levels) will continue affecting the patient, making them sick again the next day.

However, if on day two this patient takes the medicine M[1,0,-2,0], then the disease will change to D[-1,0,2,0] + M[1,0,-2,0] = D[0,0,0,0] and will stop affecting the patient. This means that at the end of day two, both the patient and the disease will have all four humors at level zero, which is your goal.

One additional wrinkle you need to be aware of is that humanity, so far, hasn't discovered medicines with all possible levels. As a matter of fact, your medicine chest (the rest of your puzzle input) has exactly 32 different medicines (fortunately, there is an unlimited supply of each). You should also know that any disease you are likely to encounter can be cured in exactly 10 days. What you need to provide is a list of 10 medicines out of those you have that are to be taken in the order you specify, so that the disease ends up cured and the patient's humors end up balanced by the end of day 10. These ten medicines could all be different, or some of them might be the same. If there are multiple valid courses of treatment, any one of them will be accepted.

Your puzzle input will start with a single line of four comma-delimited numbers, which represent the humors of your patient on day one (and, thus, the initial levels of the disease). The next 32 lines will list the medicines at your disposal in the format name:level,level,level,level (for example, ipecac:10,-17,3,1). Your solution should be a list of exactly ten medicine names (comma-delimited), which, taken in that order, one per day will end up reducing the levels of both the patient and the disease to exactly [0,0,0,0] at the end of day ten.

Here is a full example.

input:
-50,-66,68,36
ipecac:25,-20,30,23
triticale:-43,-20,-24,-44
oleaster:-43,23,30,-25
tamarind:-43,49,-36,23
castor:25,-20,-24,23
durian:-15,49,-1,-44
verbena:-43,23,-1,23
buttercup:-15,-20,-1,14
sloe:25,49,-1,23
caraway:-15,49,-36,-44
salsify:-15,-21,30,14
guava:12,23,-36,-44
marshmallow:12,23,30,14
acerola:-15,-20,-36,-44
manioc:-15,-21,-36,23
buckthorn:-43,-21,-36,14
turmeric:25,-20,-24,-25
hazel:-15,49,30,-25
sumac:12,-21,-36,14
blackstrap:12,-21,30,-44
lycopersicon:-43,-21,-24,23
foxglove:25,49,30,-44
lotus:12,23,-36,14
allspice:-43,-20,-1,23
jujube:12,-20,30,23
yucca:25,49,-36,-25
sienna:25,23,-36,14
echinacea:25,23,-24,14
hawthorn:-15,49,-24,23
sycamore:-43,-21,-24,14
resin:12,-21,-1,23
fuchsia:12,49,-36,-25

solution:
sloe,fuchsia,turmeric,guava,buttercup,ipecac,triticale,lotus,marshmallow,salsify

To check that this course of treatment indeed cures the patient, we can take a look at the human and disease levels at the end of each day:

DAY  HUMAN               DISEASE            MEDICINE
===  =====               =======            ========
1    H[-50,-66,68,36]    D[-25,-17,67,59]   M[25,49,-1,23]
2    H[-75,-83,135,95]   D[-13,32,31,34]    M[12,49,-36,-25]
3    H[-88,-51,166,129]  D[12,12,7,9]       M[25,-20,-24,-25] 
4    H[-76,-39,173,138]  D[24,35,-29,-35]   M[12,23,-36,-44]
5    H[-52,-4,144,103]   D[9,15,-30,-21]    M[-15,-20,-1,14]
6    H[-43,11,114,82]    D[34,-5,0,2]       M[25,-20,30,23]
7    H[-9,6,114,84]      D[-9,-25,-24,-42]  M[-43,-20,-24,-44]
8    H[-18,-19,90,42]    D[3,-2,-60,-28]    M[12,23,-36,14]
9    H[-15,-21,30,14]    D[15,21,-30,-14]   M[12,23,30,14]
10   H[0,0,0,0]          D[0,0,0,0]         M[-15,-21,30,14]

Notice that on day 0 the disease levels were indeed D[-50,-66,68,36] (as specified in the sample input above), and that both H and D end up at all zeroes.

Good luck to you. Good luck to your patients. They will need it.

P.S. Standard disclaimer: the above is not intended as professional medical advice. Don't try to treat your phlegm with ipecac.