1
\$\begingroup\$

The way these 1's and 0's flip are like the Lights Out game, except I only have to worry about a single row.

So, if I have 1001 and I "press" the first bit it will become 0101 Now if I "press" the third bit, it will become 0010 and so on until you get the string to be all zeros.

The way I solved this puzzle was to test it against every possible solution. So I go through the permutations and it is ungodly slow. If I have a bit sequence of 20 it takes well over 1 hour. I understand my solution is an n! solution, but I don't think it should take as long as it does.

I can't seem to pinpoint the slowness or really know how to optimize this any further.

#include "stdafx.h"
#include <iostream>
#include <string>
#include <algorithm> 
using namespace std;

//Global
string clickSequence;
bool solved = false;

string pressLight(string lights, int pressLight)
{
    //This is the case if the first light in the sequence is pressed
    if (pressLight == 0)
    {
        if (lights[pressLight] == '0')
            lights[pressLight] = '1';
        else
            lights[pressLight] = '0';

        if (lights[pressLight+1] == '0')
            lights[pressLight+1] = '1';
        else
            lights[pressLight+1] = '0';
    }
    //Case if the last light in the sequence is pressed
    else if (pressLight == lights.length() - 1)
    {
        if (lights[pressLight] == '0')
            lights[pressLight] = '1';
        else
            lights[pressLight] = '0';

        if (lights[pressLight - 1] == '0')
            lights[pressLight - 1] = '1';
        else
            lights[pressLight - 1] = '0';
    }
    //Case for any light with two lights on the 
    else
    {
        if (lights[pressLight] == '0')
            lights[pressLight] = '1';
        else
            lights[pressLight] = '0';

        if (lights[pressLight + 1] == '0')
            lights[pressLight + 1] = '1';
        else
            lights[pressLight + 1] = '0';

        if (lights[pressLight - 1] == '0')
            lights[pressLight - 1] = '1';
        else
            lights[pressLight - 1] = '0';
    }
    return lights;
}

string solveLightsOut(string lights, int sequence[], int i)
{
    if (string(lights.length(), '0') == lights)
    {
        solved = true;
        return clickSequence;
    }

    if (i < lights.length())
    {
        clickSequence += to_string(sequence[i] + 1) + "  ";
        lights = pressLight(lights, sequence[i]);
        return solveLightsOut(lights, sequence, i += 1);   //Recursivly click lights for solution
    }
    if (!solved)
    {
        clickSequence = "";
        return "";
    }
}

int main()
{
    string solution;

    string lights;
    int n = -1;
    int i;
    int *permutations;

    //Test cases given by professor, comment one and uncomment another for testing
        //string lights = "000110"; // 1 2 4
        //string lights = "10000"; //NO SOLUTION
        //string lights = "00111"; // 4 (Actually return 1 2 5)
        //string lights = "00101"; // NO SOLUTION
        //string lights = "1000101"; // 2 3 5 7
        //string lights = "00001111"; // NO SOLUTION  --------This takes ~9 seconds to complete
        //string lights = "1100010011"; // 2 4 5 10   --------This takes ~2.5 minutes to complete
        //--------------------------WARNING, SLOW--------------------------*/
        //string lights = "10101010101010101011"; //1 3 5 7 9 11 13 15 17 19 --------This takes >1 hour to complete
        //--------------------------WARNING, SLOW--------------------------*/
        //string lights = "001100011000000"; // 1 2 5 6 8 --------This takes >1 hour to complete

    while (n != '0')
    {
        while (n > 20 || n < 0)
        {
            cout << "Enter number of bits" << endl;
            cin >> n;
        }
        if (n != 0)
        {
            while (lights.length() != n)
            {
                cout << "Enter bit sequence" << endl;
                cin >> lights;
            }
            i = 0;
            permutations = new int[lights.length()];

            while (i < lights.length())
            {
                permutations[i] = i;
                i++;
            }

            //cout << lights.length() << endl;
            //cout << lights << endl;

            do {
                solution = solveLightsOut(lights, permutations, 0);
                if (solved)
                {
                    cout << solution << endl << endl;
                    clickSequence = "";
                    solution = "";
                    break;
                }
            } while (next_permutation(permutations, permutations + lights.length()));
            if (!solved)
            {
                cout << "NO SOLUTION" << endl << endl;
            }

            delete[] permutations;
            lights = "";
            solved = false;
            n = -1;
        }
        else
            return 0;
    }
}

I realize there is probably more wrong to this program than just time (weird globals), but that's a different story.

I also have a solution where I recursively find the permutations that is equally as slow...

EDIT:
I'm posting my code based off information @user1118321 gave me. I never realized how costly strings could be. I followed through with the masking idea (great trick) and I tried to minimize my use of strings especially in my recursive call. The test case 1100010011 that originally took around 2.5 minutes now takes just seconds, but the case of 001100011000000 still takes quite a bit of time. I waited 6 minutes and gave up.

I'm not sure what else I can do to optimize this. Also to address @ErickWong comment, the challenge specifically required recursion.

#include "stdafx.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <vector>
using namespace std;

//Global
bool solved = false;
int numOfBits;
vector<int> clickSequence;


unsigned long long pressLight(unsigned long long lights, const int pressLight)
{   
    int mask = 0;

    if (pressLight == 0)
    {
                //Left Most Bit       //Right of Left most bit
        mask = (1 << numOfBits - 1) + (1 << numOfBits - 2);
    }
    else if (pressLight == numOfBits - 1)
    {
        //Right most bit and bit to left
        mask = 3;
    }
    else
    {
        mask = (1 << (numOfBits - pressLight)) + (1 << (numOfBits - pressLight - 1)) + (1 << (numOfBits - pressLight - 2));
    }

    return lights ^ mask;
}

vector<int> solveLightsOut(unsigned long long lights, int sequence[], int i)
{
    if (lights == 0)
    {
        solved = true;
        return clickSequence;
    }

    if (i < numOfBits)
    {
        clickSequence.push_back(sequence[i] + 1);
        lights = pressLight(lights, sequence[i]);
        return solveLightsOut(lights, sequence, i += 1);   //Recursivly click lights for solution
    }
    if (!solved)
    {
        clickSequence.clear();
        return clickSequence;
    }
}

int main()
{
    vector<int> solution;

    string Slights;
    unsigned long long Ilights;
    int n = -1;
    int i;
    int *permutations;

    while (n != '0')
    {
        while (n > 20 || n < 0)
        {
            cout << "Enter number of bits" << endl;
            cin >> n;
        }
        if (n != 0)
        {
            while (Slights.length() != n)
            {
                cout << "Enter bit sequence" << endl;
                cin >> Slights;
            }
            i = 0;
            permutations = new int[Slights.length()];

            while (i < Slights.length())
            {
                permutations[i] = i;
                i++;
            }

            numOfBits = Slights.length();
            Ilights = stoull(Slights, 0, 2);

            do {
                solution = solveLightsOut(Ilights, permutations, 0);
                if (solved)
                {
                    for(int x = 0; x < solution.size(); x++)
                        cout << solution[x] << " ";
                    cout << endl << endl;
                    clickSequence.clear();
                    solution.clear();
                    break;
                }
            } while (next_permutation(permutations, permutations + Slights.length()));
            if (!solved)
            {
                cout << "NO SOLUTION" << endl << endl;
            }

            delete[] permutations;
            Slights = "";
            solved = false;
            n = -1;
        }
        else
            return 0;
    }
}

Here is a more recursive approach, but seems equally as slow...

#include "stdafx.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <vector>
using namespace std;

//Global
bool solved = false;
int numOfBits;
vector<int> clickSequence;


unsigned long long pressLight(unsigned long long lights, const int pressLight)
{
    int mask = 0;

    if (pressLight == 0)
    {
        //Left Most Bit       //Right of Left most bit
        mask = (1 << numOfBits - 1) + (1 << numOfBits - 2);
    }
    else if (pressLight == numOfBits - 1)
    {
        //Right most bit and bit to left
        mask = 3;
    }
    else
    {
        mask = (1 << (numOfBits - pressLight)) + (1 << (numOfBits - pressLight - 1)) + (1 << (numOfBits - pressLight - 2));
    }

    return lights ^ mask;
}

int* swapArray(int* permuts, int i, int x)
{
    int a = permuts[i];
    permuts[i] = permuts[x];
    permuts[x] = a;
    return permuts;
}

vector<int> solveLightsOut(unsigned long long lights, int permu[], int toSwap)
{
    int i;
    unsigned long long tempLights;
    if (solved)
    {
        return clickSequence;
    }
    if (toSwap == numOfBits - 1) //Base case to show end of permutation
    {
        tempLights = lights;

        for(int i = 0; i < numOfBits; i++)
        {
            tempLights = pressLight(tempLights, permu[i]);
            clickSequence.push_back(permu[i] + 1);
            if (tempLights == 0)          //Solution Found!
            {
                solved = true;
                return clickSequence;
            }
        }
        clickSequence.clear();
    }
    else
    {
        for (int i = toSwap; i < numOfBits; i++)
        {
            solveLightsOut(lights, swapArray(permu, i, toSwap), toSwap + 1);
            swapArray(permu, toSwap, i); //Swaps everything back to the orginial 0,1,2,3... array as it's coming out of stack
        }
    }
    return clickSequence;
}

int main()
{
    vector<int> solution;

    string Slights;
    unsigned long long Ilights;
    int n = -1;
    int i;
    int *permutations;

    Slights = "1100010011";

    numOfBits = Slights.length();
    Ilights = stoull(Slights, 0, 2);
    permutations = new int[Slights.length()];

    i = 0;

    while (i < Slights.length())
    {
        permutations[i] = i;
        i++;
    }
    system("PAUSE");
    solution = solveLightsOut(Ilights, permutations, 0);

    if (solved)
    {
        for (int x = 0; x < solution.size(); x++)
            cout << solution[x] << " ";
        cout << endl << endl;
        clickSequence.clear();
        solution.clear();
    }
    else
    {
        cout << "NO SOLUTION" << endl << endl;
    }

    delete[] permutations;
    Slights = "";
    solved = false;
    n = -1;

    system("PAUSE");
    return 0;
}
\$\endgroup\$
2
  • \$\begingroup\$ Note that you don't need to consider all permutations. It doesn't matter what order you perform the moves, only which moves have been performed at the moment you win (you probably already have some sense of this, otherwise how would you know not to press the same switch twice?). 20' is far too large to iterate through, but 2^20 is quite modest. There are of course polynomial time algorithms using linear algebra. \$\endgroup\$ – Erick Wong Oct 13 '16 at 0:19
  • \$\begingroup\$ Unless you specifically need to find he smallest sequence of moves, it is very easy and natural to search all subsets of moves recursively. In fact this is much simpler to express than generating all permutations recursively. Mostly I'm questioning the implicit assumption in your OP that trying all solutions means trying all permutations: it does not. That is a false equivalence that is making your solution extremely slow. \$\endgroup\$ – Erick Wong Oct 13 '16 at 18:58
1
\$\begingroup\$

Overall, I find your code very readable. I had never heard of "Lights Out", but from reading your code, I think I get how it works! Very cool!

Profile

As with any performance issue, you should profile your code to see where the slowdown is. The part that's slow may differ depending on platform and OS. You don't say what compiler or OS you're using, but most of them have profiling tools available. That said, I can give you some suggestions that might improve things.

Performance

The first issue I see performance-wise is that you're using strings to represent your data. If your string is just 20 characters, each of which is either a 1 or a 0, then you could represent it with a single 32-bit int. string manipulations are relatively expensive compared with int bit manipulations. I'd recommend using an int instead.

This would make your pressLight function look something like this:

int pressLight(const int lights, const int pressedLight)
{
    // Get the mask for the light we want and the one to the right and left
    int mask = 0;
    if (pressedLight == 0)
    {
        mask = 0x00000003;
    }
    else
    {
        mask = 0x00000007 << (pressedLight - 1);
    }

    // Invert all lights
    int invertedLights = ~lights;
    
    // Now make change out only the lights we want with their inverted copies
    int result = (invertedLights & mask) | (lights & ~mask);
    
    return result;
}

What this does is takes the bit at position pressedLight and creates a mask for that bit and the one to either side. If we're at the first position, we only need the bit to the left. If we're at any other position (including the last), then the else clause generates a proper mask.

Next, we make an inverted copy of all the lights. Finally, we use mask to mask out the inverted ones we don't want, and to mask out the non-inverted ones we don't want, and we combine the results with a logical or.

EDIT: To explain a little further, it helps to understand how numbers are stored in memory. They're stored in binary, which means that each bit represents a power of 2. As I'm sure you know, a decimal number like 5 can be represented in binary as 101, which is one 4 + zero 2s + one 1.

You can use this the other way, too. If you want to store 1101 binary, then you'd need one 8 + one 4 + zero 2s + one 1, which is 8 + 4 + 1 = 13.

You can easily print the bits of a 32-bit int using something like this:

void printBits(const int bits)
{
    for (int i = 31; i >= 0; i--)
    {
        if (((bits >> i) & 0x01))
        {
            std::cout << "1";
        }
        else
        {
            std::cout << "0";
        }
    }
    std::cout << "\n";
}

Likewise, you can convert a std::string of 1s and 0s to an int using this:

int stringToBits(const std::string bitStr)
{
    int len = static_cast<int>(bitStr.size());
    int result = 0;
    for (int i = 0; i < len; ++i)
    {
        if (bitStr [ (len - 1) - i ] == '1')
        {
            result |= (1 << i);
        }
    }
    
    return result;
}

So, in your example, you were using 1100 decimal, which is 10001001100 in binary. When you flipped the bottom 2 bits, it became 10001001111 in binary, which is 1103 in decimal. End Edit

You'd need to update the other functions to use ints as well, which should be pretty straightforward.

There are numerous other ways to make this code faster. Off the top of my head, you could speed it up by performing your solveLightsOut() function on more than one thread at a time. (BTW, what is next_permutation()? I don't see its definition anywhere.)

C++

This code is written in C++, but I don't see much C++ being used. I'd recommend, at the least, using a std::vector instead of an array that's dynamically allocated for permutations array. (Although, if you use ints instead, you wouldn't need to allocate anything!)

const

You'll notice that in my function above I marked the 2 parameters as const. I did that because the function does not change them. If a function doesn't change its parameters, marking them as const lets the reader of the code know at a glance that's the case, which makes it easier to reason about.

\$\endgroup\$
6
  • \$\begingroup\$ Maybe I'm not using your function correctly, but if I pass in an int that is is 1100 it will return 1103. Also, next_permutation() comes from#include <algorithm>. C++ is pretty new to me. I'm going to make changes and I'll keep you updated. \$\endgroup\$ – Timmy Oct 12 '16 at 12:24
  • \$\begingroup\$ That's correct! I probably should have been more clear. I'll write up an explanation that hopefully makes it clearer later today as I'm busy at the moment. As for next_permutation(), I've never noticed that! You taught me something else today. Thanks! \$\endgroup\$ – user1118321 Oct 12 '16 at 14:05
  • \$\begingroup\$ No problem! And thanks for teaching me some things about manipulating ints. What I would have been expecting if I passed 1100 and 0 I would expect it to become 0000 as if pressing the first light. I've tried writing my own nth bit manipulator, but I think the way I'm masking it maybe wrong. \$\endgroup\$ – Timmy Oct 12 '16 at 15:45
  • \$\begingroup\$ OK, I've added a little more explanation. Let me know if it helps at all. Also, I might have the light positions reversed because ints have bit position 0 on the right instead of the left. \$\endgroup\$ – user1118321 Oct 12 '16 at 21:06
  • \$\begingroup\$ Thank you! Your suggestions have drastically increased the speed of my program! I posted two solutions, one using next_permutation() and another where I find the permutations myself. Although the speed of my program has increased, the case 001100011000000 still takes very long, along with anything around that size or complexity to solve. \$\endgroup\$ – Timmy Oct 13 '16 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.