I need help with this c ++ algorithm

Question

I am trying to solve a problem with an algorithm but cannot find a solution ...

The challenge is to output the fewest steps necessary to achieve a specific lamp configuration.

There are two rows of lamps and N <10000 columns, for example:

11011 11011 

or

 11101101111000101010 01111101100000010100 

These lamps can be "on" (1) or "off" (0).

Starting with all shutdowns (0), the program should output the number of steps necessary to achieve the desired configuration.

The step may be:

• switch one lamp
• switch two lamps, one above the other (in the same column)
• switch n consecutive lamps in one line, it can be a whole line, it can be only two (or one, as described above).

I thought that the algorithm should just count the number of steps needed to completely turn off the lights, and it will be the same as in the "right" order. I also assumed that I would try to find the “holes”, that is, sequences from more than one lamp with the same state, and then switch them. But this gets complicated because there are two lines ...

However, after that I was completely lost and I need help ...

Answer 1

Edit:

Recently, OP published a link to the original task, and it turned out that you are allowed to switch between the lamps back and forth. My lower solution only works if you are allowed to turn on only the lights.

Definitions

Let define:

U[i] := i-th light in the upper row.

L[i] := i-th light in the lower row.

A[i][j] := subconfiguration of the input configuration where you have i lamps in the upper row and j lamps in the lower row.

For example, if the initial state is:

 11101101111000101010 01111101100000010100 

Then A[5][2] :

 11101 01 

Secondly, let it determine:

f(i, j) := minimum number of moves to switch all lights off in A[i][j]

Are you interested in calculating f(n, n)

In addition, we define:

RU[i] := maximal consecutive run of 1 in the upper row ending in the i-th position.

RL[i] := maximal consecutive run of 1 in the lower row ending in the i-th position.

For example, if the initial state is:

 11101101111000101010 01111101100000010100 

Then RU[1] = 1 , RU[3] = 3 , RU[4] = 0

You can calculate both RU and RL from left to right in O(n) time.

Observations

First, note that if A[i][j] has k_1 zeros at the end of the top line and k_2 zeros at the end of the bottom line, then f(i, j) = f(i - k_1, j - k_2) , because the last k_1 and k_2 light is off.

Repetition ratio

Note that if you want to calculate f(i, j) , there are 3 cases:

• Disable max sequential run 1 on the top line in one move.
• Disable max sequential run 1 on bottom line in one move.
• If i = j and the lights U [i] and L [j] are on, you can turn them off in one motion.

Of course, the base case is f(0, 0) and it needs 0 moves.

Then to calculate f(i, j) :

 if U[i] is switched off: //skip zeros at the end of the upper row compute f(i - 1, j) else if L[j] is switched off: //skip zeros at the end of the lower row compute f(i, j - 1) else if i == j // U[i] and L[j] are switched on because we skipped zeros at the end f(i, j) = min(f(i - RU[i], j), f(i, j - RL[j]), f(i - 1, j - 1)) + 1 else: f(i, j) = min(f(i - RU[i], j), f(i, j - RL[j])) + 1 

memorization

To avoid calculating f for the same i and j many times during recursive calls, just save the results of the already computed f in a hash table and return them to O(1) , rather than calculate it again.

Runtime

The simple upper bound is, of course, O(n^2) , because there are at most O(n^2) subtasks.

Answer 2

This is a nice case for std::bitset !

Well, since I misunderstood the first time, I decided to make a simple heuristic.

 //////////////////////////////////////////////////// // The solver with a single, simple heuristic: // // If there a hole in a range for row1 where row2 is to have a `1`, we might // benefit from toggling both rows in advance, because it might result in a // longer stretch to toggle in the first row // // An obvious improvement would to be to try with rows swapped as well. // // (As a bonus, all solutions are verified) int solve(std::ostream& os, bitset row1, bitset row2) { auto candidates = row2 & ~row1; int best_count = row1.size() + 1; // or INT_MAX or similar bitset best_edits; for (auto const& edits : combinations(candidates)) { std::stringstream steps_stream; int count = emit_steps(steps_stream, row1, row2, edits); assert(verify(steps_stream, row1, row2, false)); if (count < best_count) { best_edits = edits; best_count = count; } } return emit_steps(os, row1, row2, best_edits); } 

This solve(...) method now emits script steps that are checked using the (modified version) of the interpreter from my original answer:

 // test driver reading the target configuration from stdin // and displaying the 'best found' solution with intermediate steps int main() { bitset row1, row2; if (std::cin >> row1 >> row2) { std::stringstream steps; int number = solve(steps, row1, row2); std::cout << "Best candidate found results in " << number << " steps:\n"; verify(steps, row1, row2, true); } } 

Output:

 Best candidate found results in 8 steps: Start verify after 'toggle both 2': row1: 00000000000000000000000000000100 row2: 00000000000000000000000000000100 after 'toggle both 4': row1: 00000000000000000000000000010100 row2: 00000000000000000000000000010100 after 'toggle first from 1 through 5': row1: 00000000000000000000000000101010 row2: 00000000000000000000000000010100 after 'toggle first from 9 through 12': row1: 00000000000000000001111000101010 row2: 00000000000000000000000000010100 after 'toggle first from 14 through 15': row1: 00000000000000001101111000101010 row2: 00000000000000000000000000010100 after 'toggle first from 17 through 19': row1: 00000000000011101101111000101010 row2: 00000000000000000000000000010100 after 'toggle second from 11 through 12': row1: 00000000000011101101111000101010 row2: 00000000000000000001100000010100 after 'toggle second from 14 through 18': row1: 00000000000011101101111000101010 row2: 00000000000001111101100000010100 Done 

Full demo: Live on Coliru

 #define BOOST_SPIRIT_USE_PHOENIX_V3 #include <boost/dynamic_bitset.hpp> #include <iostream> #include <sstream> using bitset = boost::dynamic_bitset<>; // bitset helpers int count_ranges(bitset const& bs); std::vector<bitset> combinations(bitset const& bs); // generate the steps script int emit_apply_both (std::ostream& os, bitset const& edits); int emit_toggles (std::ostream& os, bitset const& row, std::string const& row_name); int emit_steps (std::ostream& os, bitset const& row1, bitset const& row2, bitset const& edits); // applies a steps script from scratch and verifies the result // (optionally tracing all steps along the way) bool verify(std::istream& is, bitset const& target1, bitset const& target2, bool verbose); //////////////////////////////////////////////////// // The solver with a single, simple heuristic: // // If there a hole in a range for row1 where row2 is to have a `1`, we might // benefit from toggling both rows in advance, because it might result in a // longer stretch to toggle in the first row // // An obvious improvement would to be to try with rows swapped as well. // // (As a bonus, all solutions are verified) int solve(std::ostream& os, bitset row1, bitset row2) { auto candidates = row2 & ~row1; int best_count = row1.size() + 1; // or INT_MAX or similar bitset best_edits; for (auto const& edits : combinations(candidates)) { std::stringstream steps_stream; int count = emit_steps(steps_stream, row1, row2, edits); assert(verify(steps_stream, row1, row2, false)); if (count < best_count) { best_edits = edits; best_count = count; } } return emit_steps(os, row1, row2, best_edits); } // test driver reading the target configuration from stdin // and displaying the 'best found' solution with intermediate steps int main() { bitset row1, row2; if (std::cin >> row1 >> row2) { std::stringstream steps; int number = solve(steps, row1, row2); std::cout << "Best candidate found results in " << number << " steps:\n"; verify(steps, row1, row2, true); } } //////////////////////////////////////////////////// /// details, helpers int count_ranges(bitset const& bs) { int count = 0; for (auto bit=bs.find_first(); bit!=bitset::npos; bit=bs.find_next(bit)) { do ++bit; while (bit<=bs.size() && bs[bit]); ++count; } return count; } std::vector<bitset> combinations(bitset const& bs) { bitset accum(bs.size()); std::vector<bitset> result; std::function<void(size_t bit)> recurse = [&](size_t bit) mutable { if (bit == bitset::npos) result.push_back(accum); else { accum.flip(bit); recurse(bs.find_next(bit)); accum.flip(bit); recurse(bs.find_next(bit)); } }; return recurse(bs.find_first()), result; } int emit_toggles(std::ostream& os, bitset const& row, std::string const& row_name) { int count = 0; for (auto start=row.find_first(); start!=bitset::npos; start=row.find_next(start)) { auto end = start; do ++end; while (end<row.size() && row[end]); if (start+1 == end) os << "toggle " << row_name << " " << start << "\n"; else os << "toggle " << row_name << " from " << start << " through " << (end-1) << "\n"; count += 1; start = end; } return count; } int emit_apply_both(std::ostream& os, bitset const& edits) { for (auto bit=edits.find_first(); bit!=bitset::npos; bit=edits.find_next(bit)) os << "toggle both " << bit << "\n"; return edits.count(); } int emit_steps(std::ostream& os, bitset const& row1, bitset const& row2, bitset const& edits) { auto count = emit_apply_both(os, edits); count += emit_toggles (os, row1 ^ edits, "first"); count += emit_toggles (os, row2 ^ edits, "second"); return count; } #include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/phoenix.hpp> template <typename Lambda> struct WrapAction { template <typename...> struct result { typedef void type; }; template <typename... T> void operator()(T&&... t) const { _ll(std::forward<T>(t)...); } WrapAction(Lambda&& ll) : _ll(std::forward<Lambda>(ll)) { } private: mutable Lambda _ll; }; template <typename Lambda> WrapAction<Lambda> make_action(Lambda&& ll) { return { std::forward<Lambda>(ll) }; } bool verify(std::istream& is, bitset const& target1, bitset const& target2, bool verbose) { bitset row1(target1.size()), row2(target2.size()); if (verbose) std::cout << "Start verify\n"; auto toggle1 = make_action([&](int i) mutable { row1.flip(i); }); auto toggle2 = make_action([&](int i) mutable { row2.flip(i); }); auto both = make_action([&](int i) mutable { toggle1(i); toggle2(i); }); auto range1 = make_action([&](int i1, int i2) mutable { while (i2>=i1) toggle1(i2--); }); auto range2 = make_action([&](int i1, int i2) mutable { while (i2>=i1) toggle2(i2--); }); // for statement tracing: typedef boost::spirit::istream_iterator It; auto trace = make_action([&](boost::iterator_range<It> const& raw_iterators) mutable { if (verbose) { std::cout << "after '" << std::string(raw_iterators.begin(), raw_iterators.end()) << "':\n"; std::cout << " row1:\t" << row1 << "\n" << " row2:\t" << row2 << "\n"; } }); using namespace boost::spirit::qi; namespace phx = boost::phoenix; using phx::bind; using phx::construct; is.unsetf(std::ios::skipws); It f(is), l; bool ok = phrase_parse(f, l, - raw [ lit("toggle") >> ("both" >> int_) [ bind(both, _1) ] | lit("toggle") >> lit("first") >> ("from" >> int_ >> "through" >> int_) [ bind(range1, _1, _2) ] | lit("toggle") >> lit("second") >> ("from" >> int_ >> "through" >> int_) [ bind(range2, _1, _2) ] | "toggle" >> lit("first") >> (int_) [ bind(toggle1, _1) ] | "toggle" >> lit("second") >> (int_) [ bind(toggle2, _1) ] | eps(false) ] [ bind(trace, _1) ] % eol, blank); if (verbose) { if (ok) std::cout << "Done\n"; else std::cout << "Failed\n"; if (f != l) std::cout << "Remaining unparsed: '" << std::string(f,l) << "'\n"; } return ok && (f==l) && (row1==target1) && (row2==target2); } 

Answer 3

Finally, it will open again. Time to post my answer :)

This solution uses one iteration O(n+1) and solves the example of 2x20 lamps in only 7 steps

 #include <vector> #include <string> #include <iostream> #include <algorithm> #include <cassert> #include <functional> using namespace std; const string upperInput("11101101111000101010"); const string lowerInput("01111101100000010100"); vector<bool> upper, lower; void init() { // convert string rows to vector<bool> rows for_each(upperInput.begin(), upperInput.end(), [&](char e) { upper.push_back(e == '1'); }); for_each(lowerInput.begin(), lowerInput.end(), [&](char e) { lower.push_back(e == '1'); }); assert(upper.size() == lower.size()); } void dump() { // output current content of vector<bool> rows for_each(upper.begin(), upper.end(), [] (bool b) { cout << (b ? '1' : '0'); }); cout << endl; for_each(lower.begin(), lower.end(), [] (bool b) { cout << (b ? '1' : '0'); }); cout << endl; cout << endl; } // iterate over both rows with callback typedef function<void (const vector<bool>::iterator& itUpper, const vector<bool>::iterator& itLower)> IteratorCallback; void iterate(const bool includeEnd, const IteratorCallback callback) { for (auto itUpper = upper.begin(), itLower = lower.begin(); itUpper != upper.end(); itUpper++, itLower++) callback(itUpper, itLower); if (includeEnd) callback(upper.end(), lower.end()); } int main() { init(); cout << "Initial rows data: " << endl; dump(); int steps = 0; // a state is isolated if the state before and after holds the opposite value or is an isolated 1 at the beginning or end. const auto isIsolatedState = [] (const vector<bool>& source, const vector<bool>::iterator& it) { return (it != source.begin() && it != source.end() && *(it - 1) != *it && *(it + 1) != *it) || (it == source.begin() && *it && !*(it + 1)) || (it == source.end() && *it && !*(it - 1)); }; // toggle consecutive states in the given range const auto toggle = [] (const vector<bool>::iterator& begin, const vector<bool>::iterator& end) { for (auto it = begin; it != end; it++) *it = !*it; }; auto upperBlockStart = upper.front() ? upper.begin() : upper.end(); auto lowerBlockStart = lower.front() ? lower.begin() : lower.end(); iterate(true, [&upperBlockStart, &lowerBlockStart, &steps, isIsolatedState, toggle] (const vector<bool>::iterator& itUpper, const vector<bool>::iterator& itLower) { // toggle columns if state in both rows is isolated if (itUpper != upper.end()) { const int column = itUpper - upper.begin() + 1; if (isIsolatedState(upper, itUpper) && isIsolatedState(lower, itLower)) { cout << "#" << ++steps << ": Toggling column " << column << endl; toggle(itUpper, itUpper + 1); toggle(itLower, itLower + 1); dump(); } } // keep track of blocks with 1 in upper row const bool upperState = itUpper != upper.end() ? *itUpper : false; if (upperState && upperBlockStart == upper.end()) upperBlockStart = itUpper; // start of block of 1 in upper row if (!upperState && upperBlockStart != upper.end()) { // end of block of 1 in upper row const int count = itUpper - upperBlockStart; const int column = upperBlockStart - upper.begin() + 1; cout << "#" << ++steps << ": Toggling " << count << " lamp(s) in upper row starting from column " << column << endl; toggle(upperBlockStart, itUpper); upperBlockStart = upper.end(); dump(); } // keep track of blocks with 1 in lower row const bool lowerState = itLower != lower.end() ? *itLower : false; if (lowerState && *itLower && lowerBlockStart == lower.end()) lowerBlockStart = itLower; // start of block of 1 in lower row if (!lowerState && lowerBlockStart != lower.end()) { // end of block of 1 in lower row const int count = itLower - lowerBlockStart; const int column = lowerBlockStart - lower.begin() + 1; cout << "#" << ++steps << ": Toggling " << count << " lamp(s) in lower row starting from column " << column << endl; toggle(lowerBlockStart, itLower); lowerBlockStart = lower.end(); dump(); } }); cout << "Solved in " << steps << " step(s)" << endl; return 0; } 

See how it works on coliru

Answer 4

Here is my solution. O ( N ), one run. (It can even be adapted to the O (1) repository if you change the input format to accept columns at a time.) Adding comments and validating them is an exercise for the reader.

 #include <cstdlib> #include <iostream> #include <vector> #include <array> int main() { std::array<std::vector<bool>, 2> lamps; auto row_iter = lamps.begin(); char c; while (std::cin.get(c) && row_iter != lamps.end()) { switch (c){ case '0': row_iter->push_back(false); break; case '1': row_iter->push_back(true); break; case '\n': ++row_iter; break; default: std::cerr << "Unexpected input char " << static_cast<int>(c) << std::endl; return EXIT_FAILURE; } } std::vector<bool>& row1 = lamps[0]; std::vector<bool>& row2 = lamps[1]; if (row1.size() != row2.size()) { std::cerr << "Rows must be the same length" << std::endl; return EXIT_FAILURE; } row1.push_back(false); row2.push_back(false); unsigned int col_flips = 0; unsigned int changes = 0; bool prev1 = false, prev2 = false, both_changed = false; for (auto iter1=row1.cbegin(), iter2=row2.cbegin(); iter1 != row1.cend() && iter2 != row2.cend(); ++iter1, ++iter2) { unsigned int col_changes = (*iter1 != prev1); col_changes += (*iter2 != prev2); if (col_changes == 2) { if (both_changed) { changes -= 2; ++col_flips; both_changed = false; } else { changes += col_changes; both_changed = true; } } else { changes += col_changes; both_changed = false; } prev1 = *iter1; prev2 = *iter2; } std::cout << col_flips + changes/2 << std::endl; return EXIT_SUCCESS; } 

Live on coliru