Topics

► Games

► Sound & Music

► Watches & Clocks

► GPS

► Power Supplies

► Computers

► Graphics

► Thermometers

► Tools

► Tutorials

By processor

AVR ATtiny

► ATtiny10

► ATtiny2313

► ATtiny84

► ATtiny841

► ATtiny85

► ATtiny861

► ATtiny88

AVR ATmega

► ATmega328

► ATmega1284

AVR 0-series and 1-series

► ATtiny3216

► ATtiny402

► ATtiny414

► ATmega4809

AVR DA/DB-series

► AVR128DA28

► AVR128DB28

ARM

► ATSAMD21

About me

  • About me

Feeds

RSS feed

Five LEDs Puzzle Solution

7th January 2021

Last month I gave the circuit and program for a puzzle consisting of five LEDs, five pushbuttons, and an ATtiny85. The aim of the puzzle was to find the sequence of button presses that will light up all five LEDs.

Here's a second program that provides a different puzzle using the same circuit.

Read the original article Five LEDs Puzzle, or the PCB version Five LEDs Puzzle PCB, if you haven't yet built the circuit and want to try solving it yourself before reading the solution here.

The solution

The solution is the following sequence of 21 button presses, where 0 is the rightmost button and 4 is the leftmost one:

0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 4 0 1 0 2 0

The rules

The rules determining how the circuit behaves are as follows:

  • Button 0 always toggles on or off its LED.
  • Buttons 1 to 4 only toggle on or off their LED if the LED immediately to the right is on, and all the other LEDs to the right are off.

Once you understand these rules it's fairly easy to find the correct sequence:

  • First we press button 0 to light its LED.
  • Now we have the choice of pressing button 0, from the first rule, or button 1, from the second rule.
  • Pressing button 0 just returns to the previous state, so we press button 1 to get to a new state.
  • Continue in this way, choosing the option that gets to a new state of the display at each step.

The following table shows the button presses, and the state of the LEDs, for the first ten steps in the sequence:

Button LEDs
0 0 0 0 0 1
1 0 0 0 1 1
0 0 0 0 1 0
2 0 0 1 1 0
0 0 0 1 1 1
1 0 0 1 0 1
0 0 0 1 0 0
3 0 1 1 0 0
0 0 1 1 0 1
1 0 1 1 1 1

Gray code

The sequence of states of the LEDs may be familiar as a binary Gray code. The Gray code was invented in the 1940s by Frank Gray, a research physicist at Bell telephone Labs, to prevent errors in pulse-code modulated signals. In binary Gray codes each number differs from its neighbours in the sequence by the alteration of only one bit, and they are now widely used in encoding applications where a normal binary code might give a false reading when changing between two adjacent states.

How the circuit works

The circuit uses just five I/O lines to control the LEDs and read the pushbuttons. It works as follows:

  • To turn off a LED the program configures the I/O pin as an input, so no current flows through the LED.
  • To turn on a LED the program configures the I/O pin as an output and leaves it low.
  • To read the status of a pushbutton the program temporarily configures the I/O line as an input and turns on its pullup resistor, reads the pin, and then restores it to its previous state.

Note that a pin should never be programmed as an output and taken high, as pressing the corresponding button would then short the pin to ground.

The program

Here's the original program:

void setup() {
  PORTB = 0;
  DDRB = 0;
}

void loop() {
  for (int b=0; b<5; b++) {
    int d = DDRB;
    DDRB = d & ~(1<<b);
    PORTB |= 1<<b;
    delay(1);
    if (!(PINB & 1<<b)) {
      while (!(PINB & 1<<b));
      PORTB &= ~(1<<b);
      DDRB = d ^ ((!b || (d & ((1<<b)-1)) == 1<<(b-1))<<b);
    } else {
      PORTB &= ~(1<<b);
      DDRB = d;
    }
    delay(10);
  }
}

The usual way to control an LED from an I/O pin on the ATtiny85 is to make the pin an output, by setting the appropriate bit in DDRB, and then take the pin high or low, by setting or clearing the bit in PORTB.

In this circuit we do things slightly differently. Initially all the pins are set low, and as inputs:

  PORTB = 0;
  DDRB = 0;

Then, to light a LED we don't change the PORTB register, but configure the pin as an output by setting the appropriate bit in the DDRB register. The current state of the LEDs is therefore determined by the DDRB register.

This allows us to read the state of a button by temporarily setting its I/O line as an input and turning on its pullup resistor, reading the I/O line, and then restoring it to its previous state. If the LED was on this will cause it to briefly turn off, but this happens at 100Hz so you don't notice any flicker.

Main loop

The main loop repeats the following operation for each the five I/O lines, for b=0 to b=4:

First it saves the current state of the DDRB register in d, and sets the I/O line as an input with a pullup:

    int d = DDRB;
    DDRB = d & ~(1<<b);
    PORTB |= 1<<b;
    delay(1);

There's a small delay to give the I/O line time to settle.

It then reads the state of the input with the if statement:

    if (!(PINB & 1<<b)) {
      while (!(PINB & 1<<b));
      PORTB &= ~(1<<b);
      // Do something
    } else DDRB = d;

If the button is pressed !(PINB & 1<<b) will be non-zero, ie true, and we wait while the button is still pressed, and then "do something". Otherwise the state of DDRB is restored and nothing is changed.

As you probably guessed, the key to the puzzle is in the statement "do something":

      DDRB = d ^ ((!b || (d & ((1<<b)-1)) == 1<<(b-1))<<b);

The rule

To make it clearer how this works I'll explain it in stages. First of all, the statement:

DDRB = d ^ bits;

takes the exclusive-OR of bits with the previous contents of the DDRB register. The value bits is:

(test<<b)

where test is a logical test, which can have the result zero or one. If the result is zero 0<<b is zero, and the exclusive-OR with zero has no effect. If the result is one it has the effect of toggling bit b in DDRB, which toggles the state of the current LED.

So finally we've got to the test which determines if the button toggles the LED:

!b || (d & ((1<<b)-1)) == 1<<(b-1)

The test is true under two possible conditions. The first one is:

  • Is !b true, ie is b zero?

So the rightmost button always toggles its LED.

If b is some value other than zero, the statement:

(1<<b)-1

gives a binary number of b bits consisting of '1's. So it makes a mask for the bottom b bits.

1<<(b-1)

gives a binary number of b bits consisting of one '1' followed by zeros. So the second part of the test checks:

  • Are the last b bits of DDRB equal to one '1' followed by zeros?

So the buttons 1 to 4 only toggle their LED if the LED immediately to the right is on, and all the other LEDs to the right are off.

Update

9th January 2021: Updated the program and description to turn on the pullup resistor when reading an input for more reliable operation as the battery voltage decreases, or when using yellow LEDs, as suggested by JChristensen.


blog comments powered by Disqus