Last active
October 6, 2022 06:45
-
-
Save karagog/16d3edaf9d86828fab68c21f057d2f0d to your computer and use it in GitHub Desktop.
Chinese Rings Puzzle Solver
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <vector> | |
using namespace std; | |
// This class solves the Chinese Rings puzzle (https://en.wikipedia.org/wiki/Baguenaudier), | |
// optionally printing each move, and tells you how many moves it takes to solve it. It runs in O(2^N) | |
// time, because it actually simulates each move and it takes 2^N - 1 moves in the worst case. | |
class ChineseRings { | |
public: | |
// Initializes the solver with the given state. Pass verbose = false to | |
// suppress output, in case you're solving a large input. | |
ChineseRings(const vector<bool> &initial_state, bool verbose = true) | |
: state_(initial_state), verbose_(verbose) {} | |
// If unspecified, then we'll solve for all rings off. Otherwise we solve for | |
// the desired state. | |
void Solve(const vector<bool> &desired_state = {}) { | |
if (!desired_state.empty() && desired_state.size() != state_.size()) | |
cout << "Desired state must be the same size as initial state" << endl; | |
PrintLastMove(-1); // show the initial state | |
// We can solve each ring in order, starting from the largest index to the | |
// smallest, since each ring is only limited by the rings that precede it. | |
for (int i = state_.size() - 1; i >= 0; i--) | |
SetRing(i, desired_state.empty() ? false : desired_state[i]); | |
} | |
int move_count() const { return move_cnt_; } | |
private: | |
// Sets the given ring N to the target state. This mutates all rings <= N, but | |
// does not mutate any rings > N. It guarantees that the given index will be | |
// set to the target upon return, although there is no guarantee about the | |
// rings < N. | |
// | |
// This method is recursive, with maximum call depth of N. | |
void SetRing(int N, bool target) { | |
// Look at the current ring state. | |
bool cur = state_[N]; | |
if (cur == target) | |
return; // ring is already in desired state | |
// We can change the ring at N=0 any time we want. Rings at N > 0 must | |
// satisfy a precondition in order to be changed. | |
if (N > 0) { | |
// In order to change the state of the given ring, the ring at N-1 must be | |
// the only one < N which is on. We don't care about any rings > N. | |
SetRing(N - 1, true); // put on the ring at N-1 | |
for (int i = N - 2; i >= 0; i--) | |
SetRing(i, false); // take off all the other rings < N | |
} | |
// Now we are free to change the state of the current ring. | |
state_[N] = target; | |
move_cnt_++; | |
if (verbose_) | |
PrintLastMove(N); | |
} | |
// Prints the last move to the console, for visual inspection. | |
void PrintLastMove(int N) { | |
string note = "Initial Position"; | |
if (N >= 0) | |
note = state_[N] ? "Raise" : "Lower"; | |
cout << String() << " - " << note << " Index " << N << endl; | |
} | |
// Serializes the current puzzle state into a string. | |
// 'N' indicates the ring is 'on' and 'F' indicates the ring is 'off'. | |
string String() const { | |
string ret; | |
for (bool ring : state_) { | |
ret += ring ? "N" : "F"; | |
} | |
return ret; | |
} | |
// True = ON, False = OFF | |
vector<bool> state_; | |
vector<int> moves_; | |
int64_t move_cnt_ = 0; | |
bool verbose_ = false; | |
}; | |
int main(int argc, char **argv) { | |
// Solve the puzzle when all rings are initially "on". | |
vector<bool> input{true, true, true, true, true, true, true, true, true}; | |
ChineseRings rings(input, /*verbose=*/true); | |
rings.Solve(); | |
cout << "# of moves: " << rings.move_count() << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment