karagog · October 6, 2022 06:45 · Oct 6, 2022 · Oct 6, 2022 · Oct 6, 2022 · Oct 6, 2022
diff --git a/main.cc b/main.cc
@@ -3,10 +3,9 @@
 #include <vector>
 using namespace std;
 
-// This class solves the Chinese Rings puzzle, 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.
+// 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

diff --git a/main.cc b/main.cc
@@ -63,7 +63,7 @@ class ChineseRings {
   // Prints the last move to the console, for visual inspection.
   void PrintLastMove(int N) {
     string note = "Initial Position";
-    if (N > 0)
+    if (N >= 0)
       note = state_[N] ? "Raise" : "Lower";
     cout << String() << " - " << note << " Index " << N << endl;
   }

diff --git a/main.cc b/main.cc
@@ -88,7 +88,7 @@ class ChineseRings {
 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=*/false);
+  ChineseRings rings(input, /*verbose=*/true);
   rings.Solve();
   cout << "# of moves: " << rings.move_count() << endl;
   return 0;

diff --git a/gistfile1.txt → main.cc b/gistfile1.txt → main.cc
diff --git a/gistfile1.txt b/gistfile1.txt
@@ -0,0 +1,95 @@
+#include <iostream>
+#include <string>
+#include <vector>
+using namespace std;
+
+// This class solves the Chinese Rings puzzle, 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=*/false);
+  rings.Solve();
+  cout << "# of moves: " << rings.move_count() << endl;
+  return 0;
+}
No results found