DEV Community: Eduardo

Solving Advent of Code 2020 - Day 10

Eduardo — Fri, 11 Dec 2020 00:14:04 +0000

Why Day 10

Not only I've found Day 10 of this year's Advent of Code challenging, but also I've come up with a particular enough solution that I'd like to share (and document!) somewhere.

Problem rules

I strongly encourage you to read the full puzzle description if you aren't familiar with it, here I'm just gonna try to extract problem the restrictions with no amazing elves story behind:

We're given a list of integers, each of one representing the output joltage supported by a different joltage adapter.

Sample input: 16 10 15 5 1 11 7 19 6 12 4

Each one of our adapters can take an input joltage up to 3 jolts lower than its rating while still producing its rated output joltage (quite shocking, right?).
We need to use our adapters to connect a charging outlet (0 jolts) to our device (3 jolts more than the highest of our adapters).

Warming up: part 1

Let's assume we use all our adapters chained one after the other: between each one of them there will be a joltage difference.

What is the number of 1-jolt differences multiplied by the number of 3-jolt differences?

The approach for this part is relatively simple:

Sorting the input in ascending order.
Creating two counters: number of 1-jolt differences and number of 3-jolt differences.
Looping through our ordered list, comparing each item with the previous one and incrementing the relevant counter consequently. The initial 'previous' value is 0.
Incrementing the 3-jolt counter by one, since that's a known problem restriction.

The solution asked is the product of both counters.

Something similar to:

public string Solve_1()
{
    var ascendingInput = File.ReadAllLines("input.txt").Select(int.Parse).OrderBy(_ => _).ToList();

    var ones = 0;
    var threes = 0;

    var previous = 0;
    for (int i = 0; i < ascendingInput.Count; i++)
    {
        var current = ascendingInput[i];

        if (current - previous == 1)
        {
            ++ones;
        }
        else
        {
            ++threes;
        }

        previous = current;
    }

    ++threes;   // Last connection is highest adapter + 3 jolts

    return $"{ones * threes}";
}

The real challenge: part 2

How many different ways are there to arrange your adapters, not necessarily using them all?

As the problem hints ("there must be more than a trillion valid ways to arrange them!"), trying to brute-force all the possible sequences may not be the ideal approach.

We're going to follow a different one: finding which adapters are optional, and based on that, trying to deduct how many different ways of arranging our adapters are there.

Finding optional adapters

First things first, let's try to identify those parameters that are optional:

Statement 1:

Given   Three consecutive adapters (A <= B <= C)
When    A and C have a voltage difference of three or less jolts
Then    B is optional

That one was easy, right?

Optional adapters and bifurcations

How does having an optional adapter exactly affect the number of possible ways of arranging our sequence? Let's see:

Statement 2:

Given   Given any sequence of adapters [N-Z] (N < O < ... < Z)
When    The first adapter is optional (and could be removed)
Then    The number of possible arrangements of the sequence [N-Z]
          is twice the number of possible arrangements in the subsequence [O-Z] (O < ... < Z):
          all the arrangements in [O-Z] plus the same arrangements preceded by N.

Sounds good, right? Maybe too good to be true.

Using the examples to find our mistake

If both statements were right:

The solution to the example 1, with three optional adapters, would be 2^3 = 8, which is correct.
The solution to the example 2, with fifteen optional adapters, would be 2^15 = 32.768, which is not correct.

Let's have a look at the failing example, more specifically at the first group of lines:

(0), 1, 2 ... 42, 45, 46, 47, 48, 49, (52)

(0), 1, 2 ... 42, 45, 46, 47, 49, (52)

(0), 1, 2 ... 42, 45, 46, 48, 49, (52)

(0), 1, 2 ... 42, 45, 46, 49, (52)

(0), 1, 2 ... 42, 45, 47, 48, 49, (52)

...

Eric Wastl, AoC creator, could have provided us with any random arrangements (there were 19208 different ways of using the adapters for this example), but these specific ones seem to follow a certain pattern. Let's try to see what is it.

(0), 1, 2 ... 42, 45, 46, 47, 48, 49, (52) → Complete sequence

(0), 1, 2 ... 42, 45, 46, 47, {}, 49, (52) → Missing 48

(0), 1, 2 ... 42, 45, 46, {}, 48, 49, (52) → Missing 47

(0), 1, 2 ... 42, 45, 46, {}, {}, 49, (52) → Missing 47 and 48

(0), 1, 2 ... 42, 45, {}, 47, 48, 49, (52) → Missing 46

Let's continue ourselves:

(0), 1, 2 ... 42, 45, {}, {}, 48, 49, (52) → Missing 46 and 47`

(0), 1, 2 ... 42, 45, {}, 47, {}, 49, (52) → Missing 46 and 48`

But the following one isn't a valid sequence:

~~(0), 1, 2 ... 42, 45, {}, {}, {}, 49, (52)~~ → Missing 46, 47 and 48

If we iterate over the optional adapters from the right (48 > 47 > 46 ...), we see that:

Initially, the number of valid arrangements is one (the whole sequence).

(0), 1, ... 49, (52)

The first optional adapter, 48, duplicates the number of valid arrangements in the sequence, which was initially 1 and is 2 afterwards.

(0), 1, 2 ... 47, {48}, 49, (52)

(0), 1, 2 ... 47, {}, 49, (52)

The second one, 47, duplicates the number of valid arrangements in the sequence, which was initially 2 and is 4 afterwards.

(0), 1, 2 ... 46, {47}, 48, 49, (52)

(0), 1, 2 ... 46, {47}, 49, (52)

(0), 1, 2 ... 46, {}, 48, 49, (52) [new]

(0), 1, 2 ... 46, {}, 49, (52) [new]

The third one, 46, can't duplicate the number of valid arrangements in the sequence, because those combinations where neither 46, 47 and 48 are included are invalid.

(0), 1, 2 ... 45, {46}, 47, 48, 49, (52)

(0), 1, 2 ... 45, {46}, 47, 49, (52)

(0), 1, 2 ... 45, {46}, 48, 49, (52)

(0), 1, 2 ... 45, {46}, 49 (52)

(0), 1, 2 ... 45, {}, 47, 48, 49, (52) [new]

(0), 1, 2 ... 45, {}, 47, 49, (52) [new]

(0), 1, 2 ... 45, {}, 48, 49, (52) [new]

~~(0), 1, 2 ... 45, {}, 49, (52) [new]~~

Analyzing all the cases we checked that 46 can only provide another extra 0.75n, increasing the total by 1.75 rather than duplicating it.

We can also validate that mathematically:

If 47 provides n combinations:

46 was supposed to provide another n ones, to reach 2n in total.

However, it will only be able to provide part of them: another xn combinations, being x the number of 47 and 48 combinations where at least one of those optional adapters are present.

50% of the combinations provided by 47 didn't include the 47 adapter itself, that is 0.5n.
48 provided 0.5n combinations, and half of them didn't included 48. That is 0.25n

That means that x, or the number of combinations that include either 47 or 48, is 0.5n + 0.25n = 0.75n.

This rule can be generalized to (at least) any optional adapter that is used immediately before another 2 optional adapters, which is enough to solve our problem.

So, fixing Statement 2, we get:

Given   Given any sequence of adapters [N-Z] (N < O < P < ... < Z)
When    The first adapter is optional (and could be removed)
Then    The number of possible arrangements of the sequence [N-Z] is:
          a/ 1.75 2x the number of arrangements in the subsequence [O-Z]
             when the first two adapters in [O-Z] are also optional
          b/ 2x the number of arrangements in the subsequence [O-Z]
             otherwise

Implementation

Putting together both statements, we can implement the solution to the part 2 like this:


public string Solve_2()
{
    var descendingInput = File.ReadAllLines("input.txt").Select(int.Parse).OrderByDescending(_ => _).ToList();

    ulong totalNumberOfWays = 1;

    IEnumerable<int> GetOptionalAdapters()
    {
        for (int i = 1; i < descendingInput.Count - 1; ++i)
        {
            if (descendingInput[i - 1] - descendingInput[i + 1] <= 3)   // Statement 1
            {
                yield return descendingInput[i];
            }
        }
    }

    var optionalParametersList = GetOptionalAdapters().ToList();

    foreach (var optionalAdapter in optionalParametersList)
    {
        totalNumberOfWays += optionalParametersList.Contains(optionalAdapter + 1) && optionalParametersList.Contains(optionalAdapter + 2)
            ? 3 * totalNumberOfWays / 4     // Statement 2
            : totalNumberOfWays;
    }

    return totalNumberOfWays.ToString();
}

All the code shown here was taken from my Advent of Code 2020 repository.

Disclaimer: this way of resolving the puzzle is not necessarily the best one. As a matter of a fact, it's not.

You can read here some mathematical concepts behind the puzzle.
Some examples of implementations that follow that idea or similar ones are:
- In JavaScript by Rubén Valseca.
- In Kotlin by Natalia Vidal.
- In PHP by Guillermo Ibáñez.
- In Python by Javier Abadía.
- In JavaScript + memes by Juan Antonio 'Muxed'.
- In Rust by Mario Juárez.

Deprecating methods with optional arguments

Eduardo — Sat, 05 Dec 2020 17:04:39 +0000

Introduction

Optional arguments

From C# 4 methods, indexers, constructors, and delegates can have both named and optional arguments.

In the following example, int bar is a named argument and bool isZeroIndexArray is an optional argument, which becomes true if no other value is provided.

void Foo(int bar, bool isZeroIndexArray = true) { }

`ObsoleteAttribute`

Since .NET Framework 1.1 ObsoleteAttribute can be used to "mark program elements as no longer in use". Those program elements include classes, methods, fields, etc.

It's a common practice to place it in those elements that are no longer maintained and/or may disappear in future versions:

[Obsolete("This method is obsolete. Please use xxxx instead.")]
void Foo(bool isZeroIndexArray = true) { }

Semantic versioning

Semantic versioning is a common practice in software development nowadays (or at least it should be!).

Essentially, it's a way of versioning software that sticks to the following rules:

Given a version number MAJOR.MINOR.PATCH, increment the:

MAJOR version when you make incompatible API changes,

MINOR version when you add functionality in a backwards compatible manner, and

PATCH version when you make backwards compatible bug fixes.

Deprecating methods that have optional arguments

Real life scenario

Sometimes one doesn't want their users to continue using a method/class/property because:

There are plans to remove it in the future.
There is already a working alternative in place that mimics its behavior.

Given that scenario, there are some chances that, sticking to semantic versioning and its advice about handling deprecation, you want to release some minor versions where the legacy part of your code appears as 'obsolete' before actually removing it (and therefore bumping your major version).

And there are also some (smaller) chances that the method that needs to be deprecated contains optional arguments.

That's the scenario we're going to focus on.

Initial implementation and gotcha

Let's go back to one of the examples presented in the introduction:

We've always had the following method in our library:

public class OurClass
{
    public static void Foo(bool isZeroIndexArray = true) { }

    // ...
}

We now want to allow our users to use Foo() method in a more flexible way, so we've implemented:


public class FooConfiguration
{
    public bool IsZeroIndexArray { get; set; }

    public int Verbosity { get; set; }

    public FooConfiguration() { IsZeroIndexArray = true; }
}

public class OurClass
{
    public static void Foo(FooConfiguration configuration? = null) { }

    // ...
}

Since we don't want to duplicate or complicate our Foo() implementation, ideally we'd like to get rid of void Foo(bool); but we don't want to bump our major version (yet).

However, we do want to release our new code with void Foo(FooConfiguration?).

The solution, as we previously hinted, is marking the old one as obsolete, adding the new one and releasing the code with a new minor version. But there's a gotcha when doing that:

If we simply do

public class OurClass
{
    [Obsolete("This method is obsolete. Please use Foo(FooConfiguration?) instead.")]
    public static void Foo(bool isZeroIndexArray = true) { }

    public static void Foo(FooConfiguration? configuration? = null) { }

    // ...
}

we will potentially break the following user's code:

OurClass.Foo();

They'll get compiler errors similar to:

error CS0121: The call is ambiguous between the following methods or properties: 'OurClass.Foo(bool)' and 'OurClass.Foo(FooConfiguration?)

That is, we would be violating semantic versioning rules, so 💩.

Correct implementation

Fortunately not all hope is gone and there's a way of keeping the required compatibility while releasing our new functionality:

public class OurClass
{
    [Obsolete("This method is obsolete. Please use Foo(FooConfiguration?) instead.")]
    public static void Foo(bool isZeroIndexArray) { }

    public static void Foo(FooConfiguration? configuration = null) { }

    // ...
}

Did you notice the change? Now our legacy void Foo(bool isZeroIndexArray) doesn't have its optional argument any more.

This allows all possible usages of our method to keep compiling:

// Will use Foo(bool FooConfiguration? = null)
OurClass.Foo();

// Will use Foo(bool isZeroIndexArray) and get a compiler warning
OurClass.Foo(true);

// Will use Foo(bool isZeroIndexArray) and get a compiler warning
OurClass.Foo(false);

And if we implement correctly void Foo(FooConfiguration?), we'll manage to keep Foo()'s behavior consistent.

Getting ready for Advent of Code 2020

Eduardo — Thu, 26 Nov 2020 12:35:52 +0000

What's all the fuzz about

It's almost December and Advent of Code is back! For those of you who don't know it yet, AoC is an initiative by the great Eric Wastl that consists of a series of 25 puzzles released daily between 1st and 25th of December.

In 2019 almost 100,000 people completed at least one of the two parts of the first problem and almost 3,000 of them completed them all; and I expect those numbers to increase this year due to the multiple lock-downs/stay-at-home recommendations in place worldwide.

People use Advent of Code as an excuse to learn a new language or paradigm, challenge their friends/colleagues (it has public and private leaderboards) or simply challenge themselves every day for a few minutes/hours and starting or ending the day with the satisfaction of getting stuff done.

However, AoC is not only about solving problems, but also about learning from (or directly admiring) other people's solutions and creativity:

Some people solve certain problems using Minecraft.
Others manage to solve all problems using Excel (which sometimes requires implementing made-up programming languages in a spreadsheet).
A few geniuses stick to more canonical languages/approaches, but solve all 25 problems in 9ms.
Did anyone mentioned Arduino?
And what about Unity here or there?

But please don't let those amazing examples intimidate you, most of us solve the problems in more down-to-earth ways and just enjoy reading about other people's solutions afterwards. And of once a problem is out, you can solve whenever you find time for it, not only during that day (or year!).

You can listen to this inspiring talk by Eric himself where he speaks about why he decided to organize it for the first time, the unexpected success he got the first advent day of the first year (his estimation about the number of participants was of by... 5,600% after the first 12 hours), how he keeps preparing it every year and the amazing community that has arisen around it.

My personal Advent of Code preparation

As stated, the beauty of Advent of Code is that each individual does it in their own way.

In my case, I don't focus on competing in any leaderboards, but just having fun writing some code and trying to make it both understandable and relatively performant.

I discovered AoC in 2018, and that same year while going through the problems I started creating some kind of 'mini-framework' for solving AoC problems using .NET.

I have to admit I had almost as much fun solving the actual problems as I did writing that util, which I released in 2019 as AoCHelper NuGet library.

This year I've tried to improve AoCHelper before starting the actual problem solving, to try to focus on finding the solutions to those problems rather than on tweaking the framework, but we'll see 😉.
And yeah, that has been all my 'preparation'.

In case anyone is curious about it, here you can see the entrypoint to my console app (on the left) and how all my problem classes look like (on the right).

If I name the problem classes correctly and have the input files in the right folder, I just need to invoke:

using AoCHelper;

Solver.SolveAll();

and I'll get some output that measured the performance of each solution:

EDIT

I've also created this GitHub repository template to allow anyone to quickly start solving puzzles.

Come join us 😏

There are tons of tools like mine out there written in/for multiple languages, and honestly most people don't bother or care about doing anything like that, because the only thing that adventofcode.com needs is final solution to the problem!

For the last two years this repo has been aggregating other repositories with solutions and utilities in different languages: Python, JS, TS, Ruby, Java, C++, Ada, Clojure, Prolog and a long etc. You can go there and just have a look, or open a PR to share your own ones!

After all that wording, did I manage to convince you to challenge yourself or your classmates/friends/colleagues from December 1st?

PD: Feel free to share your private leaderboard code in the comments if you want other DEV users to join you there!

Rock, Paper, Scissors, Lizard, Spock

Eduardo — Tue, 13 Oct 2020 21:32:43 +0000

Introduction

In my very first post we went through solving Rock, Paper, Scissors game using a 'mathematical' approach, and that entry ended with an open question:

Can you find a similar, mathematical approach for Rock, Paper, Scissors, Lizard, Spock?

I invested no time at all in thinking about this variant until a few days ago, when @jotagarciaz asked that same question to me and sparked my curiosity.

Game analysis: "Lizard, Spock" or "Spock, Lizard?"

Rock, Paper, Scissors, Lizard, Spock is an expansion of Rock, Paper, Scissors created by Sam Kass and Karen Bryla.
It was popularized by The Big Bang Theory TV series.

Let's start from the original game:

Scissors cuts Paper

Paper covers Rock

(and as it always has) Rock crushes Scissors

Those traditional Rock, Paper, Scissors rules still apply, but two new options are added to the game: Lizard and Spock.

Let's introduce the simplest rules related to those new options:

Rock crushes Lizard

Lizard poisons Spock

Spock smashes Scissors

No huge surprises for now. Let's add another rule:

Lizard eats Paper

We can already imagine a possible pattern in the arrow diagram, which gets confirmed when adding the next one:

Spock vaporizes Rock

Scissors decapitates Lizard

Paper disproves Spock

After going through all the new rules one by one, we can conclude that there's definitely a pattern.

We can also observe such pattern by reflecting those rules in a double entry table, providing we use Rock, Paper, Scissors, Spock, Lizard order (that is, swapping Lizard and Spock positions in the game's name).

Shocking, right? The game's most popular name is Rock, Paper, Scissors, Lizard, Spock, as that's how it appears in The Big Bang Theory; but according to the acronyms used in Sam's page, their creators originally named it 'right' (Rock, Paper, Scissors, Spock, Lizard).

I wonder how Doctor Sheldon Lee Cooper missed that!

Solving the game

Once all rules are applied, we end up with this final diagram:

Analyzing this figure and/or the table we saw above, we can write the pattern we've identified as:

Any given option alternates between winning and losing against the other ones if you evaluate it following this (cyclic) order: Rock, Paper, Scissors, Spock, Lizard.
The sequence starts by either losing against the next option in the list (or the first one clockwise in the diagram) or winning against the previous one (or the first one anti/counterclockwise in the diagram).

That's a really solid start, but still not enough. We need some mathematical relationship to be able to transform that into code.

Let's remember what we concluded for Rock, Paper, Scissors:

If both numbers are the same, no one wins

If both numbers are consecutive, the bigger one wins

If both numbers aren’t consecutive, the smaller one wins

We have to find something similar for our pattern, and that's why we added numbers to the diagram above.

Let's write down some examples and try to induct a general rule that satisfies them all:

Spock beats Scissors → 4 beats 3 → > number wins
Spock beats Rock → 4 beats 1 → > number wins
Paper beats Spock → 2 beats 4 → < number wins
Lizard beats Spock → 5 beats 4 → > number wins
Lizard beats Paper → 5 beats 2 → > number wins
Scissors beats Lizard → 3 beats 5 → < number wins
Rock beats Lizard → 1 beats 5 → < number wins

By carefully observing the examples, we can induct that:

If the difference between both numbers is odd, the bigger one wins
If the difference between both numbers is even:
- If both numbers are the same, no one wins
- If both numbers are not the same, the smaller one wins

Feel free to take any other example and verify that it satisfies those statements.

If we implement them using C# 8, we get the following function:

int CalculateWinner(int player1, int player2)
{
    return (Math.Abs(player1 - player2) % 2)
        switch
    {
        0 => player1 == player2
            ? -1
            : new[] { player1, player2 }.Min(),
        1 => new[] { player1, player2 }.Max(),
        _ => throw new Exception(@"¯\_(ツ)_/¯")
    };
}

When we compare it with Rock, Paper, Scissors solution, we see that this algorithm is a generalization of the algorithm we used there, exactly how it's supposed to be, given that we're now solving an expansion of that game.

Console application

Here is an example of an interactive console application that plays Rock, Paper, Scissors, Spock, Lizard with us, and which is based on the previously defined algorithm.

Note that this code can also be used for Rock, Paper, Scissors game if we remove Spock and Lizard from enum Item (line 6).

using System;
using System.Linq;

public static class Program
{
    private enum Item { Rock, Paper, Scissors, Spock, Lizard }

    private static readonly string[] ItemArray = Enum.GetNames(typeof(Item));
    private static readonly Random Rnd = new Random((int)DateTime.Now.Ticks & 0x0000FFFF);

    public static void Main()
    {
        while (true)
        {
            Console.WriteLine($"Let's play! Type '{string.Join("', '", ItemArray[..^1])}' or '{ItemArray.Last()}'");

            if (!Enum.TryParse(typeof(Item), Console.ReadLine().Trim('\''), ignoreCase: true, out var humanInput))
            {
                Console.WriteLine("\tComputer says \"no\": invalid input\n");
                continue;
            }

            var computerInput = Enum.Parse(typeof(Item), ItemArray[Rnd.Next(0, ItemArray.Length)]);
            Console.WriteLine($"\tYou've chosen {humanInput}\n\tComputer has chosen {computerInput}");

            var result = CalculateWinner((int)humanInput, (int)computerInput);

            PrintResultMessage((int)humanInput, result);
        }
    }

    private static int CalculateWinner(int player1, int player2)
    {
        return (Math.Abs(player1 - player2) % 2)
            switch
        {
            0 => player1 == player2
                ? -1
                : new[] { player1, player2 }.Min(),
            1 => new[] { player1, player2 }.Max(),
            _ => throw new Exception(@"¯\_(ツ)_/¯")
        };
    }

    private static void PrintResultMessage(int humanInput, int result)
    {
        var resultMessage = result == -1
            ? "It's a draw!"
            : (result == humanInput) ? "You win!" : "You lose!";

        Console.WriteLine($"\t{resultMessage}\n");
    }
}

You can also find this code here.

I hope you've enjoyed this analysis of Rock, Paper, Scissors, Spock, Lizard and/or that you've found the provided solution interesting!

Waiting in Arduino III: wise methods (simple example)

Eduardo — Wed, 30 Sep 2020 21:26:21 +0000

Introduction: changes in our laser cutting machine project

Let's imagine we started building our laser cutting machine and just realized that the initial state machine we came up with was too simple to be true:

There's an extra state we need to take into account: the motor moving at a reduced speed before completely stopping.
Not every state lasts the same amount of time.

Here's a diagram of how we want our DIY project to behave with time, according to our now estimations:

'Wise' methods approach

In the previous diagram we can observe multiple different states, which we need to associate with different constants or behaviors.

An approach we can use in such cases is following a 'wise' methods pattern^TM, which simply consists of using methods who are fully responsible for acting according to a given state.

Some examples of those methods are, calculate_waiting_time(), do_stuff() and print_message(): their behaviors depend on the value of current_state. For instance, this is our implementation of do_stuff() using switch statements:

void do_stuff()
{
  switch(current_state)
  {
    case State::MotorFast:
    {
      turn_laser_off();
      turn_motor_fast();
      break;
    }
    case State::MotorSlow:
    {
      turn_motor_slow();
      break;
    }
    case State::LaserOn:
    {
      turn_motor_off();
      turn_laser_on();
      break;
    }
    default:
    {
      turn_motor_off();
      turn_laser_off();
      break;
    }
  }
}

It's also worth mentioning that we handle the application state by defining enum class State and storing an instance of it as a global variable (current_state).

next_state() method takes care of calculating the next state in our cycle using modulus operator and static_cast. We can use the small trick of storing the number of enum elements as an element itself to keep it as close to the enum as possible, with the only purpose of trying to avoid forgetting to update it if we add or remove states.

enum class State
{
  MotorFast,
  MotorSlow,
  LaserOn,

  Total = 3
};

State current_state;

State next_state()
{
  return static_cast<State>((static_cast<int>(current_state) + 1) % (static_cast<int>(State::Total)));
}

Here is the complete, full implementation of our brand new laser cutting machine:

#include "limits.h"

const int time_motor_fast   = 3000;
const int time_motor_slow   = 750;
const int time_laser_on     = 3250;

const String message_motor_fast   = "[info] Turning motor fast";
const String message_motor_slow   = "[info] Turning motor slow";
const String message_laser_on     = "[info] Turning motor off and laser ON";

enum class State
{
  MotorFast,
  MotorSlow,
  LaserOn,

  Total = 3
};

unsigned long saved_time;
State current_state;

void setup()
{
  Serial.begin(9600);

  current_state = State::MotorFast;
  turn_motor_fast();
}

void loop()
{
  unsigned long current_moment = millis();
  unsigned long waiting_time = calculate_waiting_time();

  if (current_moment - saved_time >= waiting_time)
  {
    saved_time = current_moment;
    current_state = next_state()

    print_message();
    do_stuff();
  }

  stop_in_case_of_emergency();
}

State next_state()
{
  return static_cast<State>((static_cast<int>(current_state) + 1) % (static_cast<int>(State::Total)));
}

unsigned long calculate_waiting_time()
{
  switch(current_state)
  {
    case State::MotorFast:
    {
      return time_motor_fast;
    }
    case State::MotorSlow:
    {
      return time_motor_slow;
    }
    case State::LaserOn:
    {
      return time_laser_on;
    }
    default:
    {
      return ULONG_MAX;
    }
  }
}

void do_stuff()
{
  switch(current_state)
  {
    case State::MotorFast:
    {
      turn_laser_off();
      turn_motor_fast();
      break;
    }
    case State::MotorSlow:
    {
      turn_motor_slow();
      break;
    }
    case State::LaserOn:
    {
      turn_motor_off();
      turn_laser_on();
      break;
    }
    default:
    {
      turn_motor_off();
      turn_laser_off();
      break;
    }
  }
}

void print_message()
{
  switch(current_state)
  {
    case State::MotorFast:
    {
      Serial.println(message_motor_fast);
      break;
    }
    case State::MotorSlow:
    {
      Serial.println(message_motor_slow);
      break;
    }
    case State::LaserOn:
    {
      Serial.println(message_laser_on);
      break;
    }
    default:
    {
      Serial.println("Error printing message");
      break;
    }
  }
}

bool is_emergency_button_pressed()
{ 
  // Serial.println("Checking emergency button");
  if(Serial.available())
  {
    Serial.println("Stopping due to emergency: " + Serial.readString());
    Serial.println("Please reset");
    return true;
  }

  return false;
}

void stop_in_case_of_emergency()
{
  if (is_emergency_button_pressed())
  {
    turn_motor_off();
    turn_laser_off();

    while (0 != 1) { }
  }
}

void turn_laser_on()    { Serial.println("laser on"); }
void turn_laser_off()   { Serial.println("laser off"); }
void turn_motor_fast()  { Serial.println("motor fast"); }
void turn_motor_slow()  { Serial.println("motor slow"); }
void turn_motor_off()   { Serial.println("motor off"); }

You can also find this code here.

Conclusion

As we already learned, the the usage of millis() allows us to keep checking the emergency stop button very often.

The combination of that technique with this 'wise' methods pattern provides us with a clear separation of concerns, allowing us to forget about states when coding/reviewing the main logic flow of the application.

This helps us to have a very easy to follow logic in our loop():

void loop()
{
  unsigned long current_moment = millis();
  unsigned long waiting_time = calculate_waiting_time();

  if (current_moment - saved_time >= waiting_time)
  {
    saved_time = current_moment;
    current_state = next_state();

    print_message();
    do_stuff();
  }

  stop_in_case_of_emergency();
}

In the next entries of this series we'll have a look at more complex examples of this 'wise' methods pattern, as well as at other alternative patterns to use in combination with millis() that can be followed to achieve similar clean code.

Waiting in Arduino II: millis() function to the rescue

Eduardo — Sun, 06 Sep 2020 21:37:41 +0000

Introduction: Blinking a LED without `delay()`

In the first post we linked to an official Arduino tutorial to quote why the delay() pattern wasn't mean to be used for waiting between tasks. If you fully read it back then, it probably spoiled you the alternative we're going to present in this post: using millis() function instead.

millis() "returns the number of milliseconds passed since the Arduino board began running the current program", so it cannot just replace delay() (otherwise they would just be the same method!).

Here's the pattern that can be used to replace delay() with millis() (which you can compare with the equivalent code using delay).

const int waitingMs = 2000;   // 2 seconds
unsigned long previousMillis = 0;
bool ledState = LOW;

void setup() { pinMode(LED_BUILTIN, OUTPUT); }

void loop()
{
  unsigned long currentMillis = millis();

  if (currentMillis - previousMillis >= waitingMs)
  {
    previousMillis = currentMillis;
    ledState = !ledState;
    digitalWrite(LED_BUILTIN, ledState);
  }
}

You can also find this code here.

We create a global variable to store a certain amount of milliseconds (previousMillis), which we initialize to 0.
We create a global variable to store the current state of the LED (ledState).
In each loop iteration we invoke millis() to get the number of current milliseconds and save its value to a local variable named currentMillis.
We compare the difference between the current number of milliseconds (currentMillis) with the number of milliseconds we have saved (previousMillis) to see if it is bigger than the time we wanted to wait (waitingMs):
- If it is, we update the global variable previousMillis with the current number of milliseconds (currentMillis) and perform whatever operation we were planning to (in this case, change the state of a LED: update the value of ledState variable and apply it using digitalWrite method).
- Otherwise, just continue the execution of the sketch.

Going back to our case study

Let's get back to our case study: we want to build a simple the laser cutting machine.

We identified a first solution based on a fairly right state machine, but it had a main flaw: it wouldn't be able to identify immediately (or at all) when the big, round, red emergency stop button was pressed.

The main issue of our first implementation was using delay() method, which essentially doesn't allow us to check the emergency button as often as we would like to.

A solution using `millis()`

Let's apply the pattern we just learned to our code:

const unsigned long waiting_time_ms = 3000;   // 3s
unsigned long saved_moment = 0;
int state = 0;

void setup() { Serial.begin(9600); }

void loop()
{
  unsigned long current_moment = millis();
  if (current_moment - saved_moment >= waiting_time_ms)
  {
    saved_moment = current_moment;
    state = ++state % 2;        // 0 -> 1 -> 0 -> 1 -> 0 -> 1 -> 0 ...
    do_action();
  }

  stop_in_case_of_emergency();  // This is checked every few milliseconds
}

void do_action()
{
  switch(state)
  {
    case 0:
    {
      turn_laser_off();
      turn_motor_on();
      break;
    }
    case 1:
    {
      turn_motor_off();
      turn_laser_on();
      break;
    }
  }
}

void turn_laser_on()  { Serial.println("laser on"); }
void turn_laser_off() { Serial.println("laser off"); }
void turn_motor_on()  { Serial.println("motor on"); }
void turn_motor_off() { Serial.println("motor off"); }

bool is_emergency_button_pressed()
{
  // Serial.println("Checking emergency button");
  if(Serial.available())
  {
    Serial.println("Stopping due to emergency: " + Serial.readString());
    Serial.println("Please reset");
    return true;
  }

  return false;
}

void stop_in_case_of_emergency()
{
  if (is_emergency_button_pressed())
  {
    turn_motor_off();
    turn_laser_off();

    while (0 != 1) { }
  }
}

You can also find this code here.

The main functional difference between this implementation and the delay() one is that here each loop iteration lasts only few milliseconds (vs more than 6 seconds in the other case).

Arduino performs many more operations while running this code, but after all, that's what we have it for, right? We don't pay any extra 'price'* for it.

In fact, it's just the opposite: for us (makers/programmers), Arduino calculating the value of millis() and comparing it against the content of a saved variable every few milliseconds is way more efficient than Arduino waiting in the delay() method, because the former one allows us to perform any other operation while 'waiting'.

In general terms, this millis() pattern is the approach that one should adopt if they want to level up their Arduino coding and/or use it for real life projects.

There will more entries in this series exploring more complex ways of tackling this problem (so stay tuned!), but all of them rely on the mentioned millis() pattern, so it's vital to assimilate that one first.

* As a mere anecdote, here's the result of compiling both sketches (using arduino-cli):

*       Compiling 1_delay_implementation
Sketch uses 3664 bytes (11%) of program storage space. Maximum is 32256 bytes.
Global variables use 302 bytes (14%) of dynamic memory, leaving 1746 bytes for local variables. Maximum is 2048 bytes.
*       Compiling 3_basic_millis_implementation
Sketch uses 3588 bytes (11%) of program storage space. Maximum is 32256 bytes.
Global variables use 282 bytes (13%) of dynamic memory, leaving 1766 bytes for local variables. Maximum is 2048 bytes.

Using millis is slightly more efficient, storage and memory wise! Of course, it executes many more operations per second when running, but that's a price we happily pay in these kind of devices that are based on executing the same code over and over again, providing those operations take very short time!

Waiting in Arduino I: delay() function is not your friend

Eduardo — Sun, 06 Sep 2020 21:37:19 +0000

Introduction: Blinking a LED

Displaying 'Hello, world!' is usually the first thing you learn (or get taught) when you're getting familiar with a new programming language.

An exception to that statement shows up when you start programming devices that aren't necessarily designed to directly print information on a screen, such as microcontrollers. That's why, in the case of Arduino, displaying 'Hello, world!' is effectively replaced with blinking a LED.

This is typically the first Arduino program (or sketch) that Arduino enthusiasts write (simpler code can be found in this official tutorial):

const int waitingTime = 2000;   // 2 seconds
bool ledState = LOW;

void setup() { pinMode(LED_BUILTIN, OUTPUT); }

void loop()
{
  digitalWrite(LED_BUILTIN, ledState);
  delay(waitingTime);

  ledState = !ledState;
}

You can also find this code here.

For those readers that are not well versed in Arduino (and that haven't already closed this tab), setup() method is executed once (at the beginning of the program, i.e., when the Arduino board is powered on or restarted) and the loop() method is executed over and over again.

Which means that an Arduino board with this program loaded would execute the following instructions indefinitely:

Configures the pin where the LED is connected as output.
Turns the LED on or off according to the value of ledState (initially off).
Waits two seconds.
Updates the value of ledState.
Goes back to step 2.

Understanding why using `delay()` is not always a good idea

So what's all this wording about? Is there something wrong the the blinking LED program shown above? No, absolutely no (and whoever tells you the opposite is a liar 😛). As in any other programming language, each Arduino program/sketch has a very concrete purpose, which in this case is serving as 'Hello, world!' or welcoming sample for beginners.

That example uses the delay() function in order to wait for things to happen for the sake of simplicity, but that's in general not a good pattern to follow.

The main reason for such a hard statement is that while your Arduino board is stuck performing a delay(), it cannot do (almost) anything else. In this tutorial in Arduino official page that is explained with the following example:

Sometimes you need to do two things at once. For example you might want to blink an LED while reading a button press. In this case, you can't use delay(), because Arduino pauses your program during the delay(). If the button is pressed while Arduino is paused waiting for the delay() to pass, your program will miss the button press.

An analogy would be warming up a pizza in your microwave, and also waiting some important email. You put the pizza in the microwave and set it for 10 minutes. The analogy to using delay() would be to sit in front of the microwave watching the timer count down from 10 minutes until the timer reaches zero. If the important email arrives during this time you will miss it.

What you would do in real life would be to turn on the pizza, and then check your email, and then maybe do something else (that doesn't take too long!) and every so often you will come back to the microwave to see if the timer has reached zero, indicating that your pizza is done.

Another practical example can be:

You have two LEDs, a red one and a green one. You want your red LED to blink every 2 seconds, and your green one every 7 seconds.

If you use delay() method for your green LED, how is the red LED supposed to blink every two seconds if Arduino just waits doing almost literally nothing for seven seconds?

In short, delay() function in Arduino is (generally) not your friend.

Case study

Let's imagine that we are building a laser cutting machine as our side project and our aim is to control it using an Arduino board.

We want to be able to:

Move pieces towards a laser using a DC motor that powers a conveyor belt. Stop the motor when the pieces are in front the laser.
Turn the laser on when the pieces are in the right position. Turn it off when the operation is complete.
Be able to stop the machine using a big, red 'Emergency stop' button if needed.

Conveyor belt DIY project (source)

Let's assume for now that it takes three seconds to move a piece from the beginning of the conveyor belt to the laser position and another three seconds to cut the piece using the laser.

All the code that appears in this series is simplified so that it can be run without any actuators, just connecting your Arduino to your laptop, loading the sketch and looking at the serial monitor output. Pressing the emergency button can be simulated by sending anything through the serial port using Arduino's serial monitor window.

Naive solution: using `delay()`

After analyzing our goal, one can conclude that it can be achieved by creating a state machine with three different states:

State 1: Motor on, laser off. The piece is moving through the conveyor belt.
State 2: Motor off, laser on. The laser is cutting the piece.
State 3: Motor off, laser off. Emergency mode (something went wrong), manual intervention is required.

This first implementation uses delay() for handling the amount of time between states 1 and 2.

const unsigned long waiting_time_ms = 3000;   // 3s

void setup() { Serial.begin(9600); }

void loop()
{
  turn_laser_off();
  turn_motor_on();
  delay(waiting_time_ms);

  stop_in_case_of_emergency();  // This is checked every three seconds

  turn_motor_off();
  turn_laser_on();
  delay(waiting_time_ms);

  stop_in_case_of_emergency();  // This is checked every three seconds
}

void turn_laser_on()  { Serial.println("laser on"); }
void turn_laser_off() { Serial.println("laser off"); }
void turn_motor_on()  { Serial.println("motor on"); }
void turn_motor_off() { Serial.println("motor off"); }

bool is_emergency_button_pressed()
{
  Serial.println("Checking emergency button");
  if(Serial.available())
  {
    Serial.println("Stopping due to emergency: " + Serial.readString());
    Serial.println("Please reset");
    return true;
  }

  return false;
}

void stop_in_case_of_emergency()
{
  if (is_emergency_button_pressed())
  {
    turn_motor_off();
    turn_laser_off();

    while (0 != 1) { }
  }
}

You can also find this code here.

The main issue with this piece of code is that when the microcontroller executes our delay(3000), it pauses the program for 3 seconds; therefore stop_in_case_of_emergency method is only invoked every 3 seconds, which implies:

If someone kept the emergency button pressed, our machine wouldn't immediately stop: it could take it up to 3 seconds to do it.
If someone just pressed the emergency button and released it, it could be easily missed by our program if that didn't happen just before the emergency check.

Jump straight to Waiting in Arduino II: millis() function to the rescue to analyze a better way of coding this.

Rock, Paper, Scissors: a mathematical approach

Eduardo — Tue, 07 Jul 2020 12:33:55 +0000

Introduction

I'm sure all of you have played Rock, Paper, Scissors, a simple hand game that is said to have been around for nearly 2000 years.

But has any of you acted as a referee in that game?
Probably not, and that was exactly the purpose of the first problem of Tuenti Challenge 10 (a competitive programming contest that took place early this year): you had to programmatically create a referee for it.

Essentially, the problem consisted of:

Given a pair of inputs, each one of them being R (rock), P (paper) or S (scissors); print either the winning one or - in case of a draw, i.e.:

for input R S your program has to print R

for input P P your program has to print -

Hopefully that sounds easy. What makes this challenge a good one for beginners is its simplicity: it can be easily solved with a bunch of if/else statements.

However, in this post we'll be exploring an alternative, 'mathematical' and hopefully more interesting approach to solve it. Let's have a look!

Getting analytical

First things first, we need numbers to be able to justify the mathematical word in the title of this article. Let's associate each possibility with a number:

1: Rock
2: Paper
3: Scissors

If we combine those numbers and the rules of the game, we get:

Paper (2) covers Rock (1)
Scissors (3) cuts Paper (2)
Rock (1) smashes Scissors (3)

What do we have here?

[CS reader] "That's.. that's.. a circular linked list!"

Well, indeed, but we're not going down that path today. However, the key fact to observe has to do with exactly that: all combinations follow the same pattern (big number beats small number) but the last one (where small number beats big number).

And that's a fact that remains true even if we shift the possibilities (keeping the same order) and use different, consecutive numbers:

Paper (227)
Scissors (228)
Rock (229)

Which would leave us with

Scissors (228) beats Paper (227)
Rock (229) smashes Scissors (228)
Paper (227) covers Rock (229)

Spotting the difference

Our base conclusion is that all combinations follow the same pattern except for one.

In order to create an algorithm that can solve our problem, the first step now is being able to identify that odd combination, the one that doesn't follow the general rule.

Let's put together our pairs of numbers:

2 beats 1, 228 beats 227
3 beats 2, 229 beats 228
1 beats 3, 227 beats 229

Now it may be easier to spot that the combination that behaves differently is the one whose numbers aren't consecutive.

Putting everything together

Let's summarize what we've got:

If both numbers are the same, no one wins
If both numbers are consecutive, the bigger one wins
If both numbers aren't consecutive, the smaller one wins

Let's try to put those three conditions together in code (I'm using C# 8 syntax here):

// Input
int player1 = 229, player2 = 227;

// Output calculation
var players = new []{ player1, player2 };

var winnerNumber = Math.Abs(player2 - player1)
    switch
    {
        0 => -1,
        1 => players.Max(),
        _ => players.Min()
    };

We can use the result of Math.Abs(player2 - player1) in a switch expression to check if the numbers are equal, consecutive or something else; and act accordingly.

[Disappointed reader] "Hey, but hold on a second, those are numbers, not strings!"

Correct.

We already know that it doesn't really matter which numbers we choose, providing they follow a given order. That allows us to get advantage of enums, which are based on integers, in the following way:

using System;
using System.Linq;

namespace RockPaperScissors
{
    public static class Program
    {
        private enum Item { R, P, S }

        public static void Main()
        {
            // Input
            const string str1 = "R";
            const string str2 = "P";

            // Output calculation
            var player1 = (int)Enum.Parse(typeof(Item), str1);
            var player2 = (int)Enum.Parse(typeof(Item), str2);

            var players = new[] { player1, player2 };

            var result = Math.Abs(player2 - player1)
              switch
              {
                  0 => "-",
                  1 => ((Item)players.Max()).ToString(),
                  _ => ((Item)players.Min()).ToString()
              };

            Console.WriteLine($"Winner: {result}");
        }
    }
}

Let's have a look at what's exactly happening here:

We create an enum Item with elements that match the strings we'll be getting as inputs. Note that we could give those elements any consecutive values (i.e., 227, 228 and 229, as we did in our example), or just let the language automatically do it.
That allows us to use Enum.Parse() to get the correct Item from each input, and cast them to get our numbers.
We feed our algorithm with those numbers, which chooses - as output if it declares the game a draw, or the string representation of whoever Item has won (R, S or P).

Hope you liked it!

You can find here the complete implementation I used for the challenge, which includes reading the data from an input file and writing the results to an output one.

Now a small test for you, avid reader:

Can you find a similar, mathematical approach for Rock, Paper, Scissors, Lizard, Spock?

DEV Community: Eduardo

Solving Advent of Code 2020 - Day 10

Why Day 10

Problem rules

Warming up: part 1

The real challenge: part 2

Finding optional adapters

Optional adapters and bifurcations

Using the examples to find our mistake

Implementation

Deprecating methods with optional arguments

Introduction

Optional arguments

ObsoleteAttribute

Semantic versioning

Deprecating methods that have optional arguments

Real life scenario

Initial implementation and gotcha

Correct implementation

Getting ready for Advent of Code 2020

What's all the fuzz about

My personal Advent of Code preparation

EDIT

Come join us 😏

Rock, Paper, Scissors, Lizard, Spock

Introduction

Game analysis: "Lizard, Spock" or "Spock, Lizard?"

Solving the game

Console application

Waiting in Arduino III: wise methods (simple example)

Introduction: changes in our laser cutting machine project

'Wise' methods approach

Conclusion

Waiting in Arduino II: millis() function to the rescue

Introduction: Blinking a LED without delay()

Going back to our case study

A solution using millis()

Waiting in Arduino I: delay() function is not your friend

Introduction: Blinking a LED

Understanding why using delay() is not always a good idea

Case study

Naive solution: using delay()

Rock, Paper, Scissors: a mathematical approach

Introduction

Getting analytical

Spotting the difference

Putting everything together

`ObsoleteAttribute`

Introduction: Blinking a LED without `delay()`

A solution using `millis()`

Understanding why using `delay()` is not always a good idea

Naive solution: using `delay()`