Forming digits on a grid by toggling 5-pixel diamonds

Question

Context: https://www.reddit.com/r/ProgrammerHumor/comments/6ggzvz/exceptionally_late_to_the_party_here_is_my_phone/

Some time ago, /r/ProgrammerHumor was flooding with phone number inputs. In the linked thread, you can find one based on the "Lights off" game. If you click a cell, it will flip, and all neighbouring cells will also flip. In this particular implementation, this propagates through the walls. We can represent a number as a 5x4 matrix of booleans. So if you start from a matrix that's all zeros, clicking the top left cell should leave you with the following:

1, 1, 0, 1,
1, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0,
1, 0, 0, 0

The representation of all numbers is in the file numbers.h below. The question is whether all numbers can be reached, starting from "all lights off" (all values are zero).

The author noted that he had a Python implementation that runs in 5 minutes. This seemed ridiculously long to me and I was curious to compare the timing of his Python implementation to a C implementation, so I wrote it. My C isn't very good, though, so comments are very welcome!

numbers.h:

char numbers[][20] = 
{
    // zero
    {
        1, 1, 1, 1,
        1, 0, 0, 1,
        1, 0, 0, 1,
        1, 0, 0, 1,
        1, 1, 1, 1
    },
    // one
    {
        0, 0, 0, 1,
        0, 0, 1, 1,
        0, 0, 0, 1,
        0, 0, 0, 1,
        0, 0, 0, 1
    },
    // two
    {
        1, 1, 1, 1,
        0, 0, 0, 1,
        1, 1, 1, 1,
        1, 0, 0, 0,
        1, 1, 1, 1
    },
    // three
    {
        1, 1, 1, 1,
        0, 0, 0, 1,
        1, 1, 1, 1,
        0, 0, 0, 1,
        1, 1, 1, 1
    },
    // four
    {
        1, 0, 0, 1,
        1, 0, 0, 1,
        1, 1, 1, 1,
        0, 0, 0, 1,
        0, 0, 0, 1
    },
    // five
    {
        1, 1, 1, 1,
        1, 0, 0, 0,
        1, 1, 1, 1,
        0, 0, 0, 1,
        1, 1, 1, 1
    },
    // six
    {
        1, 1, 1, 1,
        1, 0, 0, 0,
        1, 1, 1, 1,
        1, 0, 0, 1,
        1, 1, 1, 1,
    },
    // seven
    {
        1, 1, 1, 1,
        0, 0, 0, 1,
        0, 0, 1, 0,
        0, 1, 0, 0,
        1, 0, 0, 0
    },
    // eight
    {
        1, 1, 1, 1,
        1, 0, 0, 1,
        1, 1, 1, 1,
        1, 0, 0, 1,
        1, 1, 1, 1
    },
    // nine
    {
        1, 1, 1, 1,
        1, 0, 0, 1,
        1, 1, 1, 1,
        0, 0, 0, 1,
        0, 0, 0, 1
    }
};

phone-number-bruteforce.c:

#include "stdio.h"
#include "string.h"
#include "numbers.h"

void print_num(int in) {
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 4; ++j) {
            int nbit = 4*i+j;
            printf("%d", (in & (1 << nbit)) >> nbit);
        }
        printf("\n");
    }
}

void print_char(char *in) {
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 4; ++j) {
            int n = 4*i+j;
            printf("%d", in[n]);
        }
        printf("\n");
    }
}

int shift(int index, int shift) {
    // Note: NOT the same as (index + shift) / 4, due to rounding
    int row = (5 + index / 4 + shift / 4) % 5;
    int col = (4 + index + shift) % 4;
    return row * 4 + col;
}

char* click(char *in, int click) {
    in[click] ^= 1;
    in[shift(click, 1)] ^= 1;
    in[shift(click, -1)] ^= 1;
    in[shift(click, 4)] ^= 1;
    in[shift(click, -4)] ^= 1;
    return in;
}

int compare_numbers(char *in) {
    for (int i = 0; i < 10; ++i) {
        if (!memcmp(numbers[i], in, 20)) {
            return i;
        }
    }
    return -1;
}

int main() {
    for (int i = 0; i < (1 << 20); ++i) {
        int index = i;
        char new[20] = {0};
        for (int j = 0; j < 20; ++j) {
            if (index & 1) {
                click(new, j);
            }
            index /= 2;
        }
        int found = compare_numbers(new);
        if (found >= 0) {
            printf("Found %d!\n", found);
            print_num(i);
        }
    }
}

I tried to save each number in one int (since I only need 20 bits), but I couldn't figure out the index calculations. This is the working version using an array of chars.

Answer 1

Clarity

The question is whether all numbers can be reached, starting from "all lights off" (all values are zero).

But what this actually checks is if each configuration is reachable clicking any location only once. And it incidentally verifies that each configuration is only reached by one sequence of clicks (since it only says found once for each digit). That's a subset of the original problem.

This could use more explanation, as it's not immediately clear what it's trying to do.

        int index = i;
        char new[20] = {0};
        for (int j = 0; j < 20; ++j) {
            if (index & 1) {
                click(new, j);
            }
            index /= 2;
        }

In particular, either

            if (index % 2 == 1) {
                click(new, j);
            }
            index /= 2;

or

            if (index & 1) {
                click(new, j);
            }
            index >>= 1;

would be clearer about what it was doing in the center part. And

        int j = 0;
        char configuration[20] = {0};
        for (int click_pattern = i; click_pattern > 0; click_pattern /= 2) {
            if (click_pattern % 2 == 1) {
                click(configuration, j++);
            }
        }

is even clearer.

This also stops iterating if we run out of clicks to perform. The original would iterate twenty times even for 0, which meant no clicks.

On most processors, I suspect that doing division and modulus is faster than doing a bitwise and with a right shift. And the compiler is more likely to optimize division/modulus by 2 into bitwise operations than the other way around. The presumption being that people using bitwise operations know enough to profile and optimize.

If you rewrite this as

int main() {
    for (int click_pattern = (1 << 20) - 1; click_pattern > 0; --click_pattern) {
        char configuration[20] = {0};
        process(configuration, click_pattern);

        int found = compare_to_numbers(configuration);
        if (found >= 0) {
            printf("Found %d!\n", found);
            print_pattern(click_pattern);
        }
    }
}

Now it's much clearer that you are displaying what digit was found and the click pattern to reach there from the starting configuration.

Since we don't care about order, counting down makes it easier to avoid repeated calculations. The compiler would probably optimize that out anyway, but this way it definitely only occurs once.

Now we can clearly see that we print which digit configuration was found and the click_pattern to reach it. Also that we iterate over all 1,048,576 click patterns where each position is flipped at most once.

Alternative

#include <stdio.h>
#include <string.h>
#include <stdint.h>

/*
  F999F in binary is 

  11111
  10001
  10001
  10001
  11111

 */

static int32_t digits[] = {
    0xF999F,
    0x13111,
    0xF1F8F,
    0xF1F1F,
    0x99F11,
    0xF8F1F,
    0xF8F9F,
    0xF1248,
    0xF9F9F,
    0xF9F11
};
const int DIGIT_COUNT = sizeof digits / sizeof digits[0];

/* 1001B is 

   0001
   0000
   0000
   0001
   1011

 */
 static int32_t click_masks[] = {
    0x1001B,
    0x20027,
    0x4004E,
    0x8008D,
    0x001B1,
    0x00272,
    0x004E4,
    0x008D8,
    0x01B10,
    0x02720,
    0x04E40,
    0x08D80,
    0x1B100,
    0x27200,
    0x4E400,
    0x8D800,
    0xB1001,
    0x72002,
    0xE4004,
    0xD8008
};
const int POSITION_COUNT = sizeof click_masks / sizeof click_masks[0];

#define CONFIGURATION_COUNT (1 << 20)
static int8_t searched_configurations[CONFIGURATION_COUNT] = {1};

int is_digit(int32_t in) {
    for (int i = 0; i < DIGIT_COUNT; ++i) {
        if (digits[i] == in) {
            return i;
        }
    }

    return -1;
}

void search(int32_t current, int click_pattern) {
    for (int i = 0; i < POSITION_COUNT; i++) {
        int32_t next = current ^ click_masks[i];
        if (!searched_configurations[next]) {
            searched_configurations[next] = 1;

            search(next, click_pattern ^ (1 << i));
            int found = is_digit(next);
            if (found >= 0) {
                printf("Found %d!\n", found);
                printf("Clicked %05x.\n", click_pattern ^ (1 << i));
            }
        }
    }
}

int main() {
    search(0, 0);
}

Here's an alternative solution. Instead of iterating, this searches recursively for numbers from the start point. If a particular configuration has already been searched, it doesn't try to search it again (no loops). If it hasn't, it continues in a depth first search. This finds all configurations reachable from the empty start point.

As it turns out, all the positions are reachable from the empty configuration (can't see it from this code, but if you count the searched_configurations, all of them are truthy). I'm not sure that this is possible with Lights Out under normal (no wraparound) rules without double clicks.

As with the original code, this displays immediately when it finds something. That's bad form, but fixing that in C is more work than in other languages with better (or at least more complex) native data structures.

This sets constants rather than scattering magic numbers throughout the code.

This limits the global variables to just this compilation unit with the static keyword. In a more object-oriented language, we could do without them. We could also pass around a struct to avoid that, but I don't find that any cleaner.

The logic has been moved out of main and into the recursive search function. The main function could be moved out of this file and everything would work.

I did not name the functions uniquely with a prefix, as I'm not calling them from other code. That's something else that could be done to make the code more reusable. It would also make the code uglier.

I put everything in the same file because I was running on ideone.com. I have no C compiler at the moment. The site reported the runtime as either .05 or .06 seconds. Either of which are much better than five minutes.

I switched the includes from quotation marks ("string.h") to angle brackets (<string.h>) because that is the standard I expect for compiler libraries. To me, quotation marks are for user-defined libraries. The compiler also follows a different search path which may be more efficient, but the primary reason is readability.

The real key to this solution is that it stores the on/off information as bits in an integer. It includes stdint.h so that int32_t can be used to ensure that the integer is wide enough.

To click, first note that there are only twenty places to click. So we can enumerate the possible actions in click_masks. As your original program does, we just exclusive-or the bits of the current configuration with the appropriate mask. That gives us the result, which we pass to the next call to search.