Solution to the Alchemist Problem

My algorithmists!

It’s time to solve the Alchemist problem from last time. Please revisit that post to get up to speed with this problem. And, if you haven’t tried to solve it yourself yet, do give it a go! (Check the bottom of that post for some hints.)

If you’re ready…

Alkemija, Attempt 2

Last time, I presented some code that was too slow to solve the problem. It passed some test cases before the time limit, but not all of them.

I’ll present a final solution here that is fast enough. Then we’ll look at what changed between the previous attempt and this one, and why this one is so much faster.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
// Idea from https://www.programmersought.com/article/23632686021

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SUBSTANCES 100000
#define MAX_REACTIONS 100000

typedef struct substance_node {
  int substance;
  struct substance_node *next;
} substance_node;

typedef struct reaction_node {
  int reaction;
  struct reaction_node *next;
} reaction_node;

int main(void) {
  static int is_owned[MAX_SUBSTANCES + 1];
  static reaction_node *before[MAX_SUBSTANCES]; // substance -> reactions
  static substance_node *after[MAX_REACTIONS]; // reaction -> substances
  static int substances_needed[MAX_REACTIONS];
  static int reaction_queue[MAX_REACTIONS];
  int num_substances, num_owned, num_reactions, i, j;
  int num_before, num_after, in_queue, queue_index, next_reaction, reaction, substance;
  substance_node *s_node;
  reaction_node *r_node;

  scanf("%d%d", &num_substances, &num_owned);

  for (i = 0; i < num_owned; i++) {
    scanf("%d", &substance);
    is_owned[substance] = 1;
  }

  scanf("%d", &num_reactions);

  for (i = 0; i < num_reactions; i++) {
    scanf("%d%d", &num_before, &num_after);
    for (j = 0; j < num_before; j++) {
      r_node = malloc(sizeof(reaction_node));
      if (r_node == NULL) {
        fprintf(stderr, "malloc error\n");
        exit(1);
      }
      r_node->reaction = i;
      scanf("%d", &substance);
      if (!is_owned[substance])
        substances_needed[i]++;
      r_node->next = before[substance];
      before[substance] = r_node;
    }

    for (j = 0; j < num_after; j++) {
      s_node = malloc(sizeof(substance_node));
      if (s_node == NULL) {
        fprintf(stderr, "malloc error\n");
        exit(1);
      }
      scanf("%d", &s_node->substance);
      s_node->next = after[i];
      after[i] = s_node;
    }
  }

  in_queue = 0;

  // Queue up reactions that we can use based on the initial substances that we own
  for (i = 0; i < num_reactions; i++)
    if (substances_needed[i] == 0)
      reaction_queue[in_queue++] = i;

  queue_index = 0;

  while (queue_index < in_queue) {
    next_reaction = reaction_queue[queue_index++];
    s_node = after[next_reaction];
    while (s_node != NULL) {
      substance = s_node->substance;
      if (!is_owned[substance]) {
        is_owned[substance] = 1;
        num_owned++;
        for (r_node = before[substance]; r_node != NULL; r_node = r_node->next) {
          reaction = r_node->reaction;
          substances_needed[reaction]--;
          if (substances_needed[reaction] == 0)
            reaction_queue[in_queue++] = reaction;
        }
      }
      s_node = s_node->next;
    }
  }

  printf("%d\n", num_owned);

  for (i = 1; i <= num_substances; i++)
    if (is_owned[i])
      printf("%d ", i);
  printf("\n");

  return 0;
}

There are three major innovations between the prior attempt and this one.

1. Last time, the before array mapped from a reaction to the substances required to use that reaction. This time, the before array (22) maps from a substance to the reactions that require that substance. Our new before array is better because for a given substance we can easily determine the relevant reactions. We want to know which reactions require substance 5? Easy – just look in before[5]. The after array is unchanged from last time: it still maps from a reaction to the substances produced by that reaction.

2. How do we know whether we own all of the substances required for a reaction? Last time, we had to check each substance in the “before” set of each reaction, using the can_react function. This time, we do better. We maintain a substances_needed array (24): for each reaction, it tells us the number of substances needed by this reaction that we don’t yet own. If some reaction has a 0 here, then it means that we can trigger this reaction now (because we are missing zero needed substances). If it has a 1 here, it means that we’re missing one substance that we need in order to trigger this reaction… and so on.

3. How do we know which reactions to try next? Last time, we had to search through all reactions, testing to see whether we could use each one given the substances that we own. This time, we maintain a queue of reaction indexes (25) to tell us exactly which reactions are currently pending. We need to trigger each reaction that’s in this queue until there’s nothing in the queue left to process. (We used this very type of queue when we searched graphs in Chapter 4 of the book.)

To initialize the substances_needed array (51), we add one to a reaction’s total each time we find a substance required by the reaction that we don’t own.

Which reactions can we trigger to generate new substances? Well, at first, the only ones we can trigger are the ones whose substances_needed is 0 (72). We add each of these reactions to the queue of reactions (73) for processing.

Now we enter a big while-loop (77) that keeps going as long as we have further reactions in the queue. Each reaction in the queue is ready to go (i.e. we own all of its “before” substances). For each reaction, we loop through all of its “after” substances (80), looking for substances that we don’t already own.

What do we do each time we can use a reaction to generate a new substance that we didn’t yet own? Well, we have this new substance now, so it might take us closer to being able to trigger some other reactions.

For each new substance that we now own, we loop through all of the reactions that need this substance in order to trigger (85). If this was the final substance that we need to trigger this reaction (88), then we add the reaction to our queue for processing. (Notice here how useful it is for our before array to take us from a substance to the reactions that need that substance!)

There’s More

What did you think of this ad hoc problem? Want to see more like this?

Don’t forget to check the growing list of exercises for more practice with the material from the book.

Happy problem solving!