Alan's Automaton Workshop

Alan's Automaton Workshop

Not enough ratings
Solving the automatons for Complexity or Speed
By fef
This guide shows some possible solutions to solve the first levels for complexity and speed (not necessarily at the same time), and also provides some explanations about the algorithms used.
3
4
3
   
Award
Favorite
Favorited
Unfavorite
1-1 Switch Assembly
Complexity and Speed
(Complexity 120 / 120, Speed 4 / 4)
No difficulty here, just follow the tutorial.
1-2 Westminster Quarters
Complexity and Speed
(Complexity 120 / 120, Speed 10 / 10)
No difficulty here, just follow the tutorial.
1-3 Chime Selector
Complexity and Speed
(Complexity 180 / 230, Speed 10 / 10)
A node has a high complexity (30 points) so avoid using too many nodes if you're trying to solve the Complexity challenge. In this puzzle there are only 4 different tones, so you need only 4 nodes.

A transition costs 10 points no matter how complex it is, be it a "default" or a test with multiple AND conditions. So use them a lot if you want to reduce complexity.

For this puzzle, it's mostly a matter of setting the right conditions on the transitions between nodes.
1-4 Control Valve
Complexity and Speed
(Complexity 190 / 190, Speed 4 / 4)
No difficulty here, just follow the tutorial.
1-5 Recorder
Complexity and Speed
(Complexity 150 / 150, Speed 4 / 4)
There are only 2 possible actions: write X, or write -
That means 2 nodes. Then you can add the conditions, and you can even add several conditions that link the same nodes (this creating an OR condition).
1-6 Welcome Chimes
Complexity and Speed
(Complexity 160 / 160, Speed 4 / 4)
Same kind of puzzle as before: there are only 2 actions to perform: ring C or ring E.
The fact that they have to be used in different order can be managed with conditions reduces the complexity score.

Oh, and if no condition matches nothing happens and the test case ends. So the "Otherwise, do nothing" requirement is actually automatically handled by... doing nothing.
1-7 Automatic Transmission
Complexity and Speed
(Complexity 160 / 160, Speed 4 / 4)
Same as 1-4 : three possible states, so three nodes. The rest is conditions to reach them.
1-8 Heartbeat Compressor
Complexity and Speed
(Complexity 130 / 130, Speed 5 / 5)
Here the most complex case is to perform 3 heartbeats (the other cases requires less heartbeats). With the tools at your disposal at this stage of the game, you can't perform any iteration/loop. So if you try with only a single node, you won't be able to keep track of how many heartbeats you've already done and therefore won't be able to stop at the right time. So only option is to set the 3 heartbeats in 3 nodes and setting the right conditions.
2-1 Cable Release
Straightforward solution meeting both Complexity and Speed requirements at the same time. The array always starts in position 1 (starting from the right). To reach the 3rd position we therefore need to go left twice. Then turn it on.
2-2 Resetter
For complexity, you have to play with the option of setting multiple actions in the same node. You can't set multiple actions on the same device, but you can perform actions on different devices. In this case, you can increase the counter and move to the next position at the same time (in node Q3 on the figure)


For Speed, you need to minimize the steps performed during the execution of your tests. This is achieved by:
  • Avoiding the integrator: there is only 4 positions in the array and the number of nodes is not important for Speed, so avoid taking time/steps to increase the integrator and test its values.
  • Avoiding setting to 0 a value which is already 0. So use a condition to check if it's useful first.
2-3 Grouphead
Let's start with a solution for Complexity.
  • The highlighted part in red is simply adding the 4 consecutive ingredients needed for the current coffee, with some optimizations (for instance Capuccino and Latte have only 1 ingredient which is different, so the path is pretty much the same except that ingredient. But you know that already from the previous chapters).
  • The part to the left is the starting point of each new coffee, ready to dispatch the task to the sequence that will handle teh ingredients
  • The part to the top right is serving the coffee and moving on to the next one (remember you can set 2 actions in a single node if they're operated on different devices)

So what about Speed ?
But you have probably noticed that the left node is empty. So let's optimize that further to avoid this unnecessary step. If you have node X going to that empty node, and then going further to node Y then you can replace that by an equivalent condition directly from X to Y. After removing that node, we get the final solution reaching both Complexity and Speed at the same time (I've highlighted the same red part as before to help visualize it).
2-4 Timer
Complexity
For complexity, you can use the new mapper (setting the variable for number of X to write in I2), and then do a loop by decrementing I2.

Speed
For speed, we need to save some operations. This is done by improving the "default" rule and avoid preparing the mapper if unnecessary:


I would like to take this opportunity with a not-so-complex puzzle to illustrate a different Speed solution. Maybe not the most elegant, but it's the fastest. This is called loop unrolling, and it consists in removing every operation used for managing the loop even if it means doing repetitive tasks. In this case the operations that are not strictly necessary would be:
  • Using the mapper (we can use the RTMR instead)
  • Doing the final I2.Dec (no need to decrement it from 1 to 0 because it was the last one)
  • And more generally, if we remove the mapper we can remove the counter and I2 as well
So we can "unroll" the loop by writing the Xs one by one. Painful, but it works... and you get a better Speed than actually required.
2-5 Pump
This works for both Complexity and Speed at the same time.
For this we use mostly 2 nodes:
  • Create a mapper with the right value to write which is the computed value for 9-X (0 becomes 9, 1 becomes 8, 2 becomes 7 and so on)
  • One node to move on to the next number
And as usual don't forget to test constantly (using conditions on transitions) if you've reached the end, to avoid unnecessary steps.
2-6 Heater
This works for both Complexity and Speed at the same time.
Here the idea is to:
  • prepare a mapper counter in I2 with the number of "2"s that you're going to write. That means the mapping is (0 and 1 become 0, 2 and 3 become 1, 4 and 5 become 2 and son on...).
  • Then add one more node for a loop to write those "2" (with a transition on itself to iterate and a dec counter to know when to stop the loop)
  • And one final node to write the "1" if the initial number is even.

    Don't forget to use the right condition on every transition to make sure you're not moving to the next step unless strictly necessary, otherwise you won't reach the Speed requirement.
2-7 Main Gearbox
The idea is to iterate over the different positions in the Array (from right to left) and increase a counter every time we find a "1". For this we'll need to add:
  • One integrator Icnt to count the number of "1" that we have already found
  • One integrator Ipos to know which is the current position in the Array
  • One mapper to copy the result from our Icnt to the expected Rspwr register
At the end we copy the response value from Icnt to the expected Rspwr.

Complexity
(Complexity 250 / 260 , Speed 16 / 14)
  • One node "Q2" is used to move on to the next position, by moving left and increasing our Ipos variable
  • One node "Qinc counter" is used to increase the counter Iinc when we find a "1"
  • If we are in a certain position of the Array in Q2, there are 3 options:
    • We have reached the end of the array (our Ipos has reached value 4), so we go to the last step with the mapper
    • We have not reached the end and the current array value is "1" --> we increase the counter before going back to Q2 to move on to the next position
    • We have not reached the end and the current array value is "0" --> we go directly to Q2 again to move on to the next position


Speed
(Complexity 270 / 260 , Speed 12 / 14)
In this case we want to minimize the number of transitions especially when we need to increase our Icnt. Instead of having a specific node for increasing the counter (your program had to test if the counter was "1", then go to the node to increase the counter, then go back to Q2), we use:
  • One node to handle the current position if its value is 0 (at the bottom on the picture). It will move to the next position (go left + increase Ipos).
  • One node to handle the current position if its value is 1 (at the top on the picture). It will increase Ipos AND move to the next position (go left + increase Ipos).
Then it's mostly a matter of setting the right conditions on each transition to alternate between the top (array=1), the bottom (array=0) or the final mapper when we reach the end.
2-8 Coin Mechanism
Complexity

(Complexity 260 / 310 , Speed 33.33 / 20.08)
This is how it works:
  • We create one integrator Itot to remember how many pences we have processed so far
  • We create one integrator Icoin to know how many pences the current coin is worth
  • Then the workflow is the following:
    • For the current coin, we use a mapper to set the value of the current coin into Icoin. The mapper maps 0 to 0, 1 to 1, 3 to 3 and 6 to 6
    • Then the node Q2 increase Itot by the amount in Icoin. We can only increment or decrement, we can't add values. So we do it with a loop by decreasing Icoin 1 by 1 and increasing Itot 1 by 1 at the same time, until Icoin is 0 (we basically transfer 1 pence at a time from Icoin to Itot)
    • Then the node Q3 moves on to the next coin (and we do the same again setting the mapper then transferring to Itot...)
    • Finally we need an exit condition to turn on Cpwr. This is done when we reach 9 in Itot.

Speed
This solution for speed is very different from the complexity solution. Here the idea consists in creating a state diagram using nodes where each node represents the number of pence already found.

(Complexity 400 / 310 , Speed 9.75 / 20.08)

Let's take an example with the following coin sequence: 3p, 3p, 1p, 6p, 1p
  • You start at 0 (START).
  • Then you find a 3p coin, you switch to the node for 3p (Q3).
  • Then you find a 3p coin, so you move to the node 3+3=6 (Q6)
  • Then you find a 1p coin, so you move to the node 6+1=7 (Q7)
  • Then you find a 6p coin, so you have exceeded 9 and reach the final node to "TURN ON"

Note that this solution reaches the previous speed expectations (9.75). With a patch on December 24th, 2022 the puzzle was made easier by increasing the Speed requirement to (20.08).
3-1 Binary Number Converter
Speed
First let's have a look at the simplest (call it dumb if you want) solution which meets the Speed check:

(Complexity 790 / 460 , Speed 10.75 / 20.5)
Here we're testing all possible combinations in the red part (is the Array digit 0 or 1, go left, is it now 0 or 1, go left, etc...) , and then we write the results. Extremely fast. Probably the fastest you could build. It works. But definitely boring...

Complexity
The main idea is to compute the value from the array into a numeric variable, and then display its value.
To convert an array into a numeric variable, we'll have to iterate over each position of the array. And a reminder about binary basics is that the first position is worth 1 (2^0), the second is worth 2 (2^1), the third is worth 4 (2^2) and the fourth is worth 8 (2^3).
So we'll need to add 1,2,4 or 8 respectively to our counter. Remember the previous puzzle where we had to add 1,3 or 6 pence coins? We'll use the same mechanism.
But... the counter we have at our disposal is called Integrator and can only count up to 9, so how to store values up to 15? We can work around that. You may have noticed that there is a maximum of 2 digits to write, as we're going to write numbers between 0 and 15.
  • The first digit - if present - is always 1
  • The second digit can be anything
That is quite interesting, because the second digit is perfect to fit into our integrator.
As for the remaining digit, all we need to remember is if we have reached 10+ or not. And for this we have a boolean variable in the game called Clutch Switch.

So let's summarize the devices we need:
  • Have an integrator Iunit and a clutch switch C10 to represent the final number
  • We'll need to remember which position in the array we're at. It'll be Integrator Ipos
  • We'll need to know if we're adding 1,2,4 or 8. This value will be stored in integrator Iadd
(Complexity 430 / 460 , Speed 35.75 / 20.5)

And the final algorithm is:
  • Have a "pence counter" (see puzzle 2-8) able to add 1,2,4 and 8 for the current position (stored in Ipos) of the array. This is the part in red in the figure. It consists in:
    • The mapper which maps the Position (0,1,2,3) to the decimal value it represents (1,2,4,8) to Iadd
    • A "pence counter" (called Qincrementor) that increments Iunit and decrements Iadd at the same time until Iadd reaches 0
    • In case Iunit is maxed, the "Qreach10" node will turn on the C10 switch and reset the Iunit counter
  • Have a way to display the final value, which consists in the C10 switch (simple write) and the Iunit (need a mapper to write). That's the part in green on the figure.
  • Have a way to move to the next position in the array. That's the part in yellow on the figure. If all positions have been processed, we go to the green part to display the results. Otherwise we process them in the red part.

3-2 Decimal Number Converter
The main idea of the solutions shown here is the following.
  • The input values on TIN can go from 0 to 15. We can keep this information at any time using 2 devices: one device to store the last digit, and one device to store the first digit.
    • For the first digit, it is either 1 or not present. That's a boolean. We will store it in a clutch switch called C10
    • For the second digit, we can use the TIN itself. We only need to make sure the cursor is located on that second digit
  • Then we build a state machine that go through each position of the array from right (because that's where it starts) to left. And at each position, we set the binary digit to 1 only if the input value (stored in TIN and C10, as mentioned above) corresponds
    • The binary values for 0-15 are respectively 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
    • We can see that the binary digit to the right is set only if the input is 1,3,5,7,9,11,13,15. In short, if and only if the last digit (in TIN) is an odd number
    • Then the digit to the left is set only when the input is 2, 3, 6, 7, 10, 11, 14, 15
    • Then the next digit is set only only when the input is 4, 5, 6, 7, 12, 13, 14, 15
    • And finally the leftmost digit is set only when the input is 8 or higher

Complexity
With the above idea, let's build the automaton.
  • In green, the initialization part. We initialize C10 and TIN so they represent the first and second digit of the input
  • In yellow, an intermediate 'rendez-vous' point between the initialization and the processing
  • In red, the processing that iterates (with Array.left) over the array and set each position to 1 only if the conditions presented earlier are met
(Complexity 400 / 430, Speed 15.75 / 15.37)


Speed and Complexity
With the previous automaton, we reach complexity but not speed. Let's optimize it slightly.
The yellow "rendez.-vous" is costly: every test case goes through it, but it doesn't really do anything. So let's remove it by replacing it with conditions. It's harder to understand, but it reaches the speed requirement.
(Complexity 400 / 430, Speed 13.75 / 15.37)
3-3 Adder
Additions in binary are very similar to additions in decimal: you start with the 2 digits on the right, add them, and if it exceeds to maximum value for a single digit (which is 1 in binary whereas it was 9 in decimal) then you keep an overflow. Then you move to the next column to the left, add them again counting the overflow... and so on.

We're going to do just that: add the digits on the right (from A1 and A2), write the result (A3) then go left, then add the next digits from A1 and A2, write the result then go left... and we'll need to take the overflow into account at each step.

Since there is 3 numbers to add (the digit from A1, the digit from A2, and the overflow) which can either be 0 or 1, that's a total of 8 possible combinations. That's small enough to handle them with a tree state machine (rather than really adding them up numerically).

Speed
So let's try to build that automaton.

(Complexity 390 / 360, Speed 22.85 / 23.35)
  • Check the sum of the digits on the current column (A1 + A2 + OVF). There are 4 possible results (4 nodes, in green) for the 8 possible combinations mentioned earlier (8 transitions in red, or only 4 if coming from START because the overflow is 0 at the beginning):
    • 0 = Write 0, no overflow
    • 1 = Write 1, no overflow
    • 2 = Write 0, keep overflow
    • 3 = Write 1, keep overflow
  • Then move on to the next column to the left (this is the blue node) and repeat, until all the 5 columns have been processed.
  • At the end, write a last 1 in the sixth column of A3 in case the overflow is set. This is the yellow node.
  • One more thing: we need to know if we have reached the last column. So we'll keep an integrator Ipos to store the position, starting at 0. This Ipos check is included in the transitions.

Complexity
Let's proceed to some optimizations of the number of nodes or transitions in order to reduce complexity. First, notice that there are 8 main transitions (the red ones), but there are also 4 other transitions that are redundant coming from the START node.
We want to avoid those transitions from START but we can't go to the blue node right away otherwise it would be going to the next column already. So let's split the blue node in 2 nodes: one node to initiate all the red transactions, and one node to actually go left.

This change adds +1 node and +1 transition to link both nodes. But we are saving -3 transitions because there is only one left from the START node instead of 4. We saved 10 complexity points this way.

(Complexity 380 / 360, Speed 34.84 / 23.35)


Then we can perform 2 more optimizations:
  • The top green node Qsum0 is setting A3 to 0 and turning overflow off. But all digits in A3 are already 0 by default, and overflow is already off according to the only condition that leads to that node. So we can simply remove the node and go directly to the blue node when that condition is met. We save 20 more complexity points.
  • Additionally, the yellow node is only doing A3.set(1). And the last green node is also doing that. We can redirect the condition leading to that yellow node to the last green node for the same result. It will also turn on the overflow and then it will go back to the blue nodes once more, but that's all and it will not impact the final result (going left when you're already to the left is simply not doing anything, and then the Ipos counter will reach 6 and it won't match any conditions so it will stop). We're saving 10 more complexity points by removing that yellow node.

Here's the final automaton with optimized complexity:
(Complexity 350 / 360, Speed 35.05 / 23.35)

3-5 Relational Operator
There's only 3 possible outputs: A < B, A > B, or A = B
We could imagine a simple set of conditions:
  • If A=0 and B=1 to 9 : result is A < B
  • If A=1 and B=2 to 9 : result is A < B
  • If A=2 and B =3 to 9 : result is A < B
  • ...
  • If A=0 and B=0 : result is A = B
  • If A=1 and B=1 : result is A = B
  • If A=2 and B=2 : result is A = B
  • ...
  • If A=1 and B = 0 : result is A > B
  • If A=2 and B = 0 to 1 : result is A > B
  • If A=3 and B = 0 to 2 : result is A > B
  • ...
And so on.. but that would make 30 different conditions, worth 10 complexity points each. That means 300 complexity. Add to that the initial 100, and some more to write the result and you're over 400 complexity already. If we go this way, we'll certainly reach perfect speed but we'll never reach Complexity objective.

So let's work on a more interesting solution for complexity. And then with a few twists we can modify it to reach Speed as well in a "smarter" way than listing every possible condition.

Complexity
The solution presented here is based on the following:
If you add or remove a constant value to both sides of an (in)equation, then the (in)equation is still true. For instance if you have the inequation
  • 7 < 9
you can remove 7 to both sides, leading to the following which is still true
  • 0 < 2
In our automation, we have an (in)equation with A on one side and B on the other. We'll use the property just mentioned to remove 1 to both A and B multiple times (using a loop as we have done several times already in previous automatons) until one of A or B reaches 0.
After this transformation, there will be only 3 possibles cases which can each be represented with a condition:
  • Both A and B are 0. That means A=B
  • Only A is 0. That means A<B
  • Only B is 0. That means A<B
Let's write that algorithm with an automation.

(Complexity 380 / 400, Speed 15.7 / 14.94)

  • The green part is the initialization. The game doesn't let us decrement the initial registers, so we copy RA and RB into two integrators IRA and IRB. I'll keep calling them A and B in this article because it's shorter though.
  • The red part is the loop which is decrementing both sides of the (in)equation IRA and IRB as long as both are higher than 1
  • And the blue part writes the 3 possible results with the 3 remaining conditions.


Speed
For speed we'll use a very similar algorithm as for complexity. First let's figure out what is costly in terms of speed, i.e. which part of our algorithm requires a lot of steps. Observe the following:
  • If A=2 and B=3, we will be decrementing the integrators 2 times, then A will be 0
  • If A=9 and B=3, we will be decrementing the integrators 3 times, then A will be 0
  • If A=9 and B=7, we will be decrementing the integrators 7 times, then B will be 0
  • If A=2 and B=7, we will be decrementing the integrators 2 times, then A will be 0
In those examples we see that it will take a lot more time to reach 0 if both A and B are quite high.
So the idea of the following solution consists in splitting the automaton in 2 parts, depending on how high the first number (A) is.
  • If A is high (5, 6, 7, 8 or 9) then instead of decrementing, we'll be incrementing instead, until one of them reaches 9. In the worst case (if A=5) it will take at most 4 increments to reach 9. And then we can write the results similarly to what we've done earlier. We're only checking which integegrator (A, B or both) has reached the 9.
  • If A is low (0, 1, 2, 3, or 4) then we'll decrement as we've done in the Complexity solution. Here also it will be a maximum of 4 decrements to reach 0.
The final solution is shown here. There are 2 loops now (the parts in red). One is incrementing, and the other is decrementing.

(Complexity 490 / 400, Speed 12.8 / 14.94)

The time we save by splitting the initial design in 2 is sufficient to reach the Speed requirements, despite the added initial condition we needed to add to determine if we're going to increment or decrement.
19 Comments
gg.nadrewod 19 Jun @ 8:03am 
3-5 has been updated to have a standard of 360 Complexity and 11.7 Speed, so neither design now reaches a standard.
gg.nadrewod 19 Jun @ 7:33am 
On 3-3, you can get BOTH Complexity AND Speed by just condensing some extraneous transitions to "Default" or a simple "i-Pos 0-4" check.

For the transition from "Start" to "Sum1", there are only 4 possible combinations of the two checked array values, 2 have already been accounted for with other transitions, and both of the remaining 2 go to Sum1, so that can just be Default.

Then, you can map out the transitions from Go Left to Sum 0 and Sum 3, then choose which of Sum1 and Sum 2 you want to map out with 3 transitions, while the other will handle the 3 remaining values of the 3 checked array/clutch values by simply checking "i-Pos 0, 1, 2, 3, 4".

Ban, EXACT Complexity match, and no change in speed.
gg.nadrewod 18 Jun @ 9:54pm 
I'm confused by 2-6: if the 1 value was already fast-tracked to the end of the sequence with the extra transition, why include it as a variable you're checking in the top transition to Q3?
gg.nadrewod 18 Jun @ 9:45pm 
Same with 2-5. Can't you just choose "NOT Blank" and save yourself 8 clicks per transition?
gg.nadrewod 18 Jun @ 6:25pm 
For the transitions checking for "all values greater than 0", wouldn't it be faster to just select "NOT 0"?
gg.nadrewod 18 Jun @ 5:56pm 
It's funny how they tell you partway through Chapter 1 that you might not be able to get both standards with one design, but you actually can until level 2-2.
Ekaitz 11 Jan, 2024 @ 4:33am 
Hello and thank you for this guide !
I have found another solution for 3-3 with both speed (20.10) and complexity (370) achieved in one design. Link : https://imgur.com/a/kgjrq36
Kopp Kapudd 5 Dec, 2023 @ 2:34pm 
3-3 has been changed since this was written. the complexity limit is so low you can only do decrease OR increase, not both.
Kopp Kapudd 16 Nov, 2023 @ 2:47pm 
2-2 change default to if array is 1, use a second transition to loop back into the pointer mover if its 0
清芷 26 Mar, 2023 @ 1:23am 
3-3 has a method to get both steps and complexity by one automaton. I post a guide for it.