In this article, we’re going to look at solving one of this year’s puzzles with Scade One.<\/p>\n
\n “But wait!”, I hear you say. “Scade One is a specialized tool to create embedded software, surely you can’t solve general programming puzzles with it!”. Well I can, and I will, because the true magic of Christmas doesn’t only lie in writing code, but in making it run on impossibly constrained embedded hardware.<\/p>\n First, let’s lay down some ground rules. Scade One (and the underlying Swan programming language) is meant to<\/em> create embedded software, that will run on various types of hardware, from multi-CPU boards to teeny tiny microcontrollers.<\/p>\n In a typical Scade One program, any interaction with the outside world (sensors, actuators or even a file system) typically happens through pre-allocated data structures. For this reason, it doesn’t really make sense to use Scade One to read and parse the raw text puzzle input from a file. Instead, we’ll be using a small Python Extract\/Transform\/Load script to turn the data into ready-to-use Swan types and constants.<\/p>\n Once we have the input data, though, all the logic will be implemented in Scade One.<\/p>\n Our problem today is Day 3 of Advent of Code 2024<\/a>.<\/p>\n Our program receives a character string as an input. Inside this character string are instructions that multiply some numbers. Well-formed multiplication instructions are written Our program must:<\/p>\n We are given an example string:<\/p>\n Well-formed So, we want to recognize patterns in a string. The right tool for this is a regular expression<\/a>.<\/p>\n While we don’t have regular expressions out of the box in Scade One, we have something that does the exact same job: state machines. More precisely: safe, deterministic, memory-constant state machines.<\/p>\n Scade One programs use a dataflow<\/a> paradigm. This means that we’re not describing step-by-step instructions<\/em>, but rather describing the data<\/em> and how it is transformed (via equations<\/em>). The program runs in discrete time steps called cycles<\/em>. At each cycle, the model transforms its inputs to outputs. The sequencing of operations is determined by the code generator, based on static analysis of the model. As far as the model designer is concerned, two independent, parallel operations happen simultaneously (this will be important later).<\/p>\n In our case, our Scade One model consumes a flow<\/em> of characters, which is a sequence of \n At any point during this progression, if we find an unexpected character, we go back to the start. If we successfully make it to the closing parenthesis, we compute the multiplication and add it to a counter.<\/p>\n This is easy to translate into a Swan state machine:<\/p>\n \n Our state machine has two states: Furthermore, we maintain two variables local to the scope of the state machine: One important thing to mention here: state machines are baked into the Swan language and work out-of-the-box<\/strong>. Their implementation is safe<\/strong>, deterministic<\/strong>, and operates at constant memory<\/strong>.<\/p>\n I don’t know about you, but my typical experience with state machines consists in either finding an obscure library and trying to use it correctly or implementing my own and spending more time debugging the state machine itself than my business logic. In my case at least, having safe and ready to go state machines is a relief.<\/p>\n Now that our state machine is complete, we need to test it. For this, we use a test harness, which is what Scade One calls its automated tests. Our harness is a special diagram that exercises the operator under test (outlined in purple below) and makes assertions on some values.<\/p>\n Let’s look at it in debug mode:<\/p>\n \n It works! You can see purple debug values that confirm our desired result of We can now apply our program to our (personalized and not posted here) ~20k character input string and successfully compute the correct answer.<\/p>\n Each Advent of Code puzzle has a second part that brings some complexity to the initial problem. Here, in addition to Our program starts with We are given a new example string:<\/p>\n Our program must detect the instructions in bold<\/strong> above. You can see that only two Now, seeing as we already have a state machine, an immediate reaction may be to think about how we may make it more complex to handle this new logic. However, thanks to the synchronous nature of Scade One and to its dataflow paradigm, parallel processing is free; we can simply add another, simple state machine<\/strong> next to our existing one. Both state machines will execute in parallel, synchronously<\/strong>, and communicate using a boolean flag <\/strong>with no extra effort on our part.<\/p>\n Here’s the simplified version of our new state machine:<\/p>\n \n Here again, if we encounter an unexpected character at any part of this process, we simply go back to the start.<\/p>\n Here is our new state machine in Scade One:<\/p>\n \n This new state machine operates on the same principle as the previous one. Instead of integer operands, it maintains a boolean variable called \n Here is an animated view of our two state machines working together to process each character in the flow:<\/a><\/p>\n \n We write a new test harness and confirm that our two state machines work together to find our desired result of \n Here again, we apply this new program to our long input string and successfully complete the puzzle! While we won’t post said string or result here (inputs are personalized and copyrighted<\/a>), here is a cool visualization of our program running on the ~20k character string: <\/p>\n \n You can see that our result (yellow curve) grows steadily as parsing goes on and temporarily goes flat whenever our I know, right? And in some way, we did: our state machine above is exactly what a (compiled) regex would be doing to our flow of characters.<\/p>\n Let me add a few reasons why our approach may be desirable:<\/p>\n In this article, we have seen how to use Swan state machines to process a flow of character data. We have seen that safe, deterministic, synchronous state machines are baked into the Swan language. We have also seen that parallel processing comes at no extra cognitive cost: side-by-side diagrams execute in parallel, and the code generator figures out execution order and dependencies for us.<\/p>\n If you’d like to play with the model presented in this article, you may download it here<\/a>. You will need Scade One 2025 R1 or later to open it. If you are a SCADE user, access Scade One Essential with your existing licenses on the Ansys Download Portal<\/a>.<\/p>\n You may also schedule a live demo of Scade One using this link<\/a>.<\/p>\n And of course, if you’d like to give Advent of Code a shot, go to https:\/\/adventofcode.com\/<\/a>!<\/p>\n \n ![](\"https:\/\/innovationspace.ansys.com\/knowledge\/wp-content\/uploads\/sites\/4\/2024\/12\/scade-030-banner-scaled.jpg\")
\n <\/em>\n<\/p>\nThe rules<\/h3>\n
Our problem<\/h3>\n
mul(a,b)<\/code>, a<\/code> and b<\/code> being 1-3 digit numbers.<\/p>\n\n
mul(a,b)<\/code> instructions<\/strong>.<\/li>\nmul(2,2]<\/code> or mul ( 4 , 6 )<\/code>.<\/li>\n<\/ul>\nxmul(2,4)<\/strong>%&mul[3,7]!@^do_not_mul(5,5)<\/strong>+mul(32,64]then(mul(11,8)mul(8,5)<\/strong>)<\/code><\/p>\nmul(a,b)<\/code> instructions are in bold<\/strong> above and add up to a total of 2*4 + 5*5 + 11*8 + 8*5 = 161<\/code>.<\/p>\nModeling a solution<\/h3>\n
char<\/code> values that takes, at each cycle, the successive characters of our input string. We are looking for this progression:<\/p>\n![](\"https:\/\/innovationspace.ansys.com\/knowledge\/wp-content\/uploads\/sites\/4\/2024\/12\/scade-030-mul-state-machine-1.png\")
\n <\/em>\n<\/p>\n![](\"https:\/\/innovationspace.ansys.com\/knowledge\/wp-content\/uploads\/sites\/4\/2024\/12\/scade-030-mul-state-machine-swan-1.jpg\")
\n Our Swan state machine (click to enlarge)<\/em>\n<\/p>\nidle<\/code> and parsingMul<\/code>. When it’s parsing, it moves through the expected progression of characters, emitting a boolean ok<\/code> flag to confirm that it should continue. Should an unexpected character be encountered, the ok<\/code> flag is not emitted, and the state machine goes back to idle<\/code>.<\/p>\noperandA<\/code> and operandB<\/code>, used to compute each multiplication and store them into result<\/code>, the output.<\/p>\nTesting it out<\/h3>\n
![](\"https:\/\/innovationspace.ansys.com\/knowledge\/wp-content\/uploads\/sites\/4\/2024\/12\/scade-030-part1-test-harness.jpg\")
\n <\/em>\n<\/p>\n161<\/code>.<\/p>\nGrowing complexity<\/h3>\n
mul(a,b)<\/code> instructions, we must detect two new ones:<\/p>\n\n
do()<\/code> enables<\/strong> future mul(a,b)<\/code> instructions<\/li>\ndon't()<\/code> disables<\/strong> future mul(a,b)<\/code> instructions<\/li>\n<\/ul>\nmul<\/code> instructions enabled.<\/p>\nXmul(2,4)<\/strong>&mul[3,7]!^don't()<\/strong>_mul(5,5)+mul(32,64](mul(11,8)undo()<\/strong>?mul(8,5)<\/strong>)<\/code><\/p>\nmul(a,b)<\/code> instructions must be summed this time, for a total of 2*4 + 8*5 = 48<\/code>.<\/p>\n![](\"https:\/\/innovationspace.ansys.com\/knowledge\/wp-content\/uploads\/sites\/4\/2024\/12\/scade-030-do-dont-state-machine-1.png\")
\n <\/em>\n<\/p>\n![](\"https:\/\/innovationspace.ansys.com\/knowledge\/wp-content\/uploads\/sites\/4\/2024\/12\/scade-030-do-dont-state-machine-swan-1.jpg\")
\n Our second state machine (click to enlarge)<\/em>\n<\/p>\nactive<\/code> to determine whether mul<\/code> expressions should be parsed. To use it in our first state machine, we simply expand the guard condition to detect our first m<\/code> character:<\/p>\n![](\"https:\/\/innovationspace.ansys.com\/knowledge\/wp-content\/uploads\/sites\/4\/2024\/12\/scade-030-new-guard-1.jpg\")
\n Our first state machine using the active<\/code> flag<\/em>\n<\/p>\n![](\"https:\/\/innovationspace.ansys.com\/knowledge\/wp-content\/uploads\/sites\/4\/2024\/12\/scade-030-dual-state-machines-1.gif\")
\n Our two state machines working together (click to enlarge)<\/em>\n<\/p>\n48<\/code>:<\/p>\n![](\"https:\/\/innovationspace.ansys.com\/knowledge\/wp-content\/uploads\/sites\/4\/2024\/12\/scade-030-part2-test-harness.jpg\")
\n <\/em>\n<\/p>\n![](\"https:\/\/innovationspace.ansys.com\/knowledge\/wp-content\/uploads\/sites\/4\/2024\/12\/scade-030-part2-results.jpg\")
\n <\/em>\n<\/p>\nactive<\/code> flag (purple curve) is false<\/code>.<\/p>\nWe could have solved this with a regex<\/h3>\n
\n
Ready to take on the challenge?<\/h3>\n
About the author<\/h3>\n
\n
\n \n ![](\"https:\/\/innovationspace.ansys.com\/knowledge\/wp-content\/uploads\/sites\/4\/2024\/12\/scade-030-author-francois.png\")
\n <\/td>\n\n