9
$\begingroup$

The general from Optimal Building Strategy Puzzle is in a conflict with another general. This general is from another faction with 3 major differences in his technology:

  1. Instead of the worker having to be present during the building process, the worker instead just instantly places a marker on the ground. After 100 seconds, a new base has landed from an overhead satellite. The worker is not needed for the further construction of the building after the base is dropped and can continue with mining. The cost is also 400 units of gold.
  2. The mining base can overcharge their production of (mechanical) workers. To do this, they require 25% of their electricity upfront. electricity recharges at 0.5625% per second. They can do this as often as they like. Overcharging production lasts 20 seconds at a time and increases production speed by 50% (without affecting cost), but cannot be applied multiple times simultaneously on the same base. Electricity is not shared between bases: each base has their own supply. however, they can choose to overcharge another base instead of their own base.
  3. A worker requires processing overhead from a mainframe. A default mining base provides support for 11 workers. A worker can call in additional extension to this support for 100 units gold in the same way as a mining base, with the extension arriving 25 seconds after landing. One extension supports an additional 8 workers.

Just like his adversary, this general wants to have 3 mining bases active as quickly as possible. What is the fastest way for this general to reach this?

$\endgroup$
  • 4
    $\begingroup$ Next up: Optimal building strategy with sacrificial workers... $\endgroup$ – Psychemaster Nov 19 '14 at 11:06
  • $\begingroup$ @Psychemaster I was thinking about that, but I doubt the result would be that different from the standard methodology that stems from the original function, because the solution for the original problem also doesn't need the builder units AFTER the building has been completed. $\endgroup$ – Nzall Nov 19 '14 at 11:09
  • $\begingroup$ @Psychemaster indeed :D btw, OP, The original problem lacks the worker supply aspect ! $\endgroup$ – TheNaturalTanuki Nov 28 '14 at 9:41
  • 1
    $\begingroup$ "400 units of gold", "extension supports additional 8 workers" -> sounds like the game Starcraft ... $\endgroup$ – Marconius Jul 14 '15 at 15:23
1
$\begingroup$

I believe the answer to be

$267.187$ seconds = $4$ minutes $27.187$ seconds

The strategy to get this time is

Overcharge production of workers every $20$ seconds until $60$ seconds is reached. Build the number of workers up to $11$ and let the $11$ workers mine until $800$ units of gold is reached. At that point, two of the workers should place markers on the ground to request additional bases. There is no benefit from providing mainframe support extension. There is no benefit from requesting airdrop of one base before another.

There are several things which are a little unclear but to get to my answer I have made the following assumptions:

(i) The initial number of workers is $5$ and the general has $50$ units of gold originally as in the first Optimal Building Strategy Puzzle.
(ii) Each worker is able to mine $40$ units of gold per minute (as in the original problem) and production of a new worker costs $50$ units of gold
(iii) Initially, producing a new worker takes $17$ seconds but after overcharging, the speed of this production increases by $50\%$ (this equates to dividing the production time for a single worker by $1.5$ after each overcharge).
(iv) The electricity of the mining base is at $100\%$ initially and this is true for any subsequent new mining base.
(v) Important: If the overcharge finishes as a worker is being created then the new production rate applies to the completion of this worker, not the old production rate.

If we first consider the problem without parts 2 and 3 above, it's clear that

The solution to the problem is the same as the original where base creation is $100$ seconds instead of $120$. Hence, without the additional advances in technology, we know that it takes at most $275.5$ seconds for the general to have three active mining bases.

Now let us consider the problem where we just take points 1 and 2 into account.

In this case, we assume that each mining base provides support for a maximum of $11$ workers. Since it takes six workers $100$ seconds to accumulate $400$ units of gold, it is inevitable with any reasonable strategy that the general will have enough gold to request the second additional base to be dropped before the first additional base arrives. Hence, we may simplify the problem by assuming that the general builds up his gold supply to $800$ units and requests both additional bases to be dropped simultaneously. Since there is no monetary demand on electricity, the general may as well adopt a strategy to overcharge the base every $20$ seconds, when possible until he has $11$ workers. With this strategy, we obtain the following table:

Time          | Action                    | Workers |     Gold       | Electricity (%) | Time to 800 |
---------------------------------------------------------------------------------------------------------------------
 0.000000  | Create Worker      |      5        |   0.000000  |  100.000000  |  240.000000  |
 0.000000  | Begin Overcharge |      5        |   0.000000  |   75.000000  |  240.000000  |
17.000000  | Worker Created    |      6        |  56.666667  |   84.562500  |  185.833333  |
17.000000  | Create Worker      |      6        |   6.666667  |   84.562500  |  198.333333  |
20.000000  | Overcharge Done |      6        |  18.666667  |   86.250000  |  195.333333  |
20.000000  | Begin Overcharge |      6        |  18.666667  |   61.250000  |  195.333333  |
29.333333 | Worker Created    |      7        |  56.000000  |   66.500000  |  159.428571  |
29.333333  | Create Worker      |      7        |   6.000000  |   66.500000  |  170.142857  |
40.000000  | Overcharge Done |      7        |  49.777778  |   72.500000  |  160.761905  |
40.000000  | Begin Overcharge |      7        |  49.777778  |   47.500000  |  160.761905  |
40.444444 | Worker Created    |      8        |  51.851851  |   47.750000  |  140.277778  |
40.444444  | Create Worker      |      8        |   1.851851  |   47.750000  |  149.652778  |
48.000000 | Worker Created    |      9        |  42.148147  |   52.000000  |  126.308642  |
49.308642  | Create Worker      |      9        |   0.000000  |   52.736111  |  133.333333  |
56.864198 | Worker Created    |      10       |  45.333333  |   56.986111  |  113.200000  |
57.564198  | Create Worker      |      10       |   0.000000  |   57.379861  |  120.000000  |
60.000000  | Overcharge Done |      10       |  16.238680  |   58.750000  |  117.564198  |
60.000000  | Begin Overcharge |      10       |  16.238680  |   33.750000  |  117.564198  |
63.413169 | Worker Created    |      11       |  38.993140  |   35.669908  |  103.773663  |
167.186832| Base Requested    |      11       |  400.000000 |   94.042953  |   0.000000  |
167.186832| Base Requested    |      11       |   0.000000  |   94.042953  |   0.000000  |
267.186832| Base Completed    |      11       |  733.333333 |  100.000000  |   0.000000  |
267.186832| Base Completed    |      11       |  733.333333 |  100.000000  |   0.000000  |

There are some points here which need explaining. The first relates to the speed at which workers are created. Take for example the second worker that the general creates. At the outset, creation takes $17$ seconds but, $3$ seconds into production, the first overcharge is completed so the remaining completion time for the second worker is cut to $\frac{14}{1.5} = 9.333333$ seconds. The same logic is used throughout.

The second point relates to the 'Time to 800' column. This represents the time it would take the general reach the goal of $800$ units of gold with the current stash of gold and number of workers after the 'Action' in the same row is executed. The most important times are when the general should opt to Create Worker or not. From this analysis, it is clear that he should build up the workers to the maximum allowed and let them work to mine $800$ units of gold. This process takes $267.186832$ seconds which is the best that can be achieved under these conditions.

The final thing we need to take into account is point 3

Is it worth providing additional processing overhead to the base at any point?

To answer this, first note that it is only worth providing additional support if the general is to have at least $12$ workers at the base. To build a support extension, he must take a break between consecutive worker production at some point along the way. We assume that overcharging proceeds as before. In the following table let 'Support Workers' be the number of workers after which the base saves enough gold to provide the mainframe support extension, let $T_{all}$ be the total time taken to provide $11$ workers and the support extension under these conditions, let 'Gold' be the amount of gold accumulated at time $T_{all}$ and $T_{12}$ the time taken to begin creating the 12th worker. We can look at the following table to determine the smallest value of $T_{12}$
Support Worker |      $T_{all}$      |      Gold      |      $T_{12}$      |
            5            | 86.525133 | 22.386831 | 90.288565 |
            6            | 82.920116 | 23.846529 | 86.486498 |
            7            | 81.325867 | 29.160689 | 84.167591 |
            8            | 80.549108 | 31.749887 | 83.087760 |
            9            | 82.641976 | 46.997531 | 83.051404 |
           10            | 90.064198 |124.975309 | 90.064198 |
           11            | 96.732286 |183.333333 | 96.732286 |

From the table, it seems as though the best way to proceed is to build up to $9$, $10$ or $11$ workers and then call in for a support extension. The case with $9$ workers is quicker but it is not immediately clear whether the stash of extra gold will be a benefit in the $10$ or $11$ worker case. In the support worker $9$ case, the general will have enough gold to start creating the $12$th worker at $83.051404$ seconds. Going with this case, we can analyse what happens when he tries to create additional workers in the same way as the first table above. For this purpose, let us assume that at each $20$ second mark an overcharge on production has been requested.

Time          | Action                    | Workers |     Gold       | Electricity (%) | Time to 800 |
---------------------------------------------------------------------------------------------------------------------
 83.051414 | Create Worker      |      11       |   0.000000  |   21.716420  |  109.090909  |
86.409439 | Worker Created    |      12       |  24.625514  |   23.605309  |  96.921811  |
 89.58125 | Create Worker      |      12       |   0.000000  |   25.389453  |  100.000000  |
92.939275 | Worker Created    |      13       |  26.864198  |   27.278342  |  89.207977  |
 95.608791 | Create Worker      |      13       |   0.000000  |   28.779945  |   92.307692  |
98.966816 | Worker Created    |      14       |  29.102881  |   30.668834  |  82.59612  |
100.000000 | Overcharge Done |      14       |  38.745932  |   31.250000  |   81.562936  |
100.000000 | Begin Overcharge |      14       |  38.745932  |   6.250000  |   81.562936  |
 101.205793 | Create Worker      |      14       |   0.000000  |   6.928259  |   85.714286  |
103.444476 | Worker Created    |      15       |  20.894375  |   8.187518  |  77.910563  |
 106.355039 | Create Worker      |      15       |   0.000000  |   9.824709  |   80.000000  |
108.593722 | Worker Created    |      16       |  22.386831  |   11.083968  |  72.901235  |
 111.182457 | Create Worker      |      16       |   0.000000  |   12.540131  |   75.000000  |
113.421140 | Worker Created    |      17       |  23.879287  |   13.79939  |  68.481239  |
 115.725909 | Create Worker      |      17       |   0.000000  |   15.095822  |   70.588235  |
117.964592 | Worker Created    |      18       |  25.371742  |   16.392255  |  64.552355  |
120.000000 | Overcharge Done |      18       |  49.796638  |   17.500000  |   62.516947  |
 120.016947 | Create Worker      |      18       |   0.000000  |   17.509533  |   62.500000  |
121.509402 | Worker Created    |      19       |  17.909465  |   18.349039  |  61.74399  |

At this point we need to pause as the general has reached the quota that our support extension will allow. However, we notice that this is as far as we need to go because the mininum time to achieve a gold supply of $800$ units in this phase is attained after the creation of the $15$th worker where, if the general keeps the number of workers fixed, the bases will begin building at $181.355039 $seconds. After that point, even if the next support extension is given for free he will not be able to build the base quicker with extra workers. This may seem counterintuitive since the speed at which the base may produce workers increases. However, after a few overcharges, the bottleneck is not the rate at which new workers are produced but the time it takes to reach $50$ units of gold. If we let $W$ be the number of workers then the point at which it becomes impractical to create additional workers is when the time taken to mine 50 units of gold ($\frac{75}{W}$) is greater than the time saved getting to 800 units with the additional worker ($\frac{1200}{W(W+1)}$) i.e, when $W > 15$.
We can also run the same analysis for the cases when the support extension is built after the $10$th or $11$th worker. The advantage here is that for the next few worker creations the general doesn't need to wait to build up to $50$ units of gold. I won't write the full analysis here but, as before the optimal solution is to build to $15$ workers and then mine until $800$ units of gold. In the case that the support worker is $10$ our quickest time to get $800$ units is $179.724582$ seconds. In the case that the support worker is $11$ our quickest time to get $800$ units is $180.032626$ seconds. Both are better than the case above, but not by enough to beat the time given when just taking points 1 and 2 into account.

P.S. Sorry about the wobbly tables. I don't really know how to format them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.