Cleanup & progress on tutorial

7 files changed, 81 insertions, 162 deletions

@@ -1,4 +1,4 @@
-#include "PuzzlerSerializer.h"
+#include "PuzzleSerializer.h"
 #include "Memory.h"
 
 #pragma warning (disable:26451)
@@ -1,128 +1,39 @@
+#include "Memory.h"
 #include "Randomizer2.h"
+#include "Randomizer2Core.h"
 #include "Puzzle.h"
 #include "Random.h"
 #include "Solver.h"
-#include "Memory.h"
-#include "Randomizer2Core.h"
-#include "PuzzlerSerializer.h"
+
 #include <cassert>
 #include <string>
 
-void FloodFillInternal(const Puzzle& p, std::vector<std::vector<bool>>& reached, int x, int y) {
-    if (x%2 == 1 && y%2 == 1) return;
-    auto cell = p.GetCell(x, y);
-    if (cell.undefined) return;
-    if (cell.gap != Cell::Gap::NONE) return;
-    if (reached[x][y]) return;
+#pragma warning (disable: 26451)
 
-    reached[x][y] = true;
-    FloodFillInternal(p, reached, x-1, y);
-    FloodFillInternal(p, reached, x+1, y);
-    FloodFillInternal(p, reached, x, y-1);
-    FloodFillInternal(p, reached, x, y+1);
-}
+Randomizer2::Randomizer2(const std::shared_ptr<Memory>& memory) : _memory(memory), _serializer(PuzzleSerializer(_memory)) {}
 
-// Returns true: All nodes reachable / false: Some node disconnected
-bool FloodFill(const Puzzle& p) {
-    std::vector<std::vector<bool>> reached;
-    reached.resize(p.width);
-    for (int x=0; x<p.width; x++) reached[x].resize(p.height);
-    FloodFillInternal(p, reached, 0, 0);
-
-    for (int x=0; x<p.width; x++) {
-        for (int y=0; y<p.height; y++) {
-            if (x%2 == 0 && y%2 == 0) { // @Specialized
-                if (!reached[x][y]) return false;
-            }
-        }
-    }
-    return true;
+void Randomizer2::Randomize() {
+    RandomizeTutorial();
+    RandomizeKeep();
 }
 
-Randomizer2::Randomizer2(const std::shared_ptr<Memory>& memory) : _memory(memory) {}
-
-void Randomizer2::Randomize() {
-    // 4x4
-    // 14 gaps
-    // start (x=0, y=8)
-    // end (x=8, y=0) Up
-    // 1 solution
-    Puzzle p;
-    while (true) {
+void Randomizer2::RandomizeTutorial() {
+    { // Far center
+        Puzzle p;
         p.NewGrid(4, 4);
-
-        std::vector<Pos> corners;
-        std::vector<Pos> cells;
-        std::vector<Pos> edges;
-        for (int x=0; x<p.width; x++) {
-            for (int y=0; y<p.height; y++) {
-                if (x%2 == 0 && y%2 == 0) corners.emplace_back(Pos{x, y});
-                else if (x%2 == 1 && y%2 == 1) cells.emplace_back(Pos{x, y});
-                else edges.emplace_back(Pos{x, y});
-            }
-        }
-
-        for (int i=0; i<14; i++) {
-            for (int j=0; j<edges.size(); j++) {
-                int edge = Random::RandInt(0, static_cast<int>(edges.size() - 1));
-                Pos pos = edges[edge];
-                edges.erase(edges.begin() + edge);
-
-                if (FloodFill(p)) {
-                    p.grid[pos.x][pos.y].gap = Cell::Gap::FULL;
-                    break;
-                } else {
-                    p.grid[pos.x][pos.y].gap = Cell::Gap::NONE;
-                }
-            }
-        }
-
         p.grid[0][8].start = true;
         p.grid[8][0].end = Cell::Dir::UP;
 
-        auto solutions = Solver::Solve(p);
-        if (solutions.size() > 0) break;
+        for (Pos pos : Randomizer2Core::CutEdges(p, 14)) {
+            p.grid[pos.x][pos.y].gap = Cell::Gap::FULL;
+        }
+        _serializer.WritePuzzle(p, 0x293);
     }
-    PuzzleSerializer(_memory).WritePuzzle(p, 0x293);
 
-    // 7x7
-    // 35 gaps
-    // start (x=8, y=8)
-    // end (x=4, y=0) Up
-    // 2 solutions, 37 & 39
-    while (true) {
+    {
+        Puzzle p;
         p.NewGrid(7, 7);
 
-        std::vector<Pos> corners;
-        std::vector<Pos> cells;
-        std::vector<Pos> edges;
-        for (int x=0; x<p.width; x++) {
-            for (int y=0; y<p.height; y++) {
-                if (x%2 == 0 && y%2 == 0) corners.emplace_back(Pos{x, y});
-                else if (x%2 == 1 && y%2 == 1) cells.emplace_back(Pos{x, y});
-                else edges.emplace_back(Pos{x, y});
-            }
-        }
-
-        for (int i=0; i<35; i++) {
-            for (int j=0; j<edges.size(); j++) {
-                // TODO: Precompute edge weights and make a weighted cut.
-                // This will also preclude the need for flood filling.
-                // https://en.wikipedia.org/wiki/Biconnected_component
-
-                int edge = Random::RandInt(0, static_cast<int>(edges.size() - 1));
-                Pos pos = edges[edge];
-                edges.erase(edges.begin() + edge);
-                
-                if (FloodFill(p)) {
-                    p.grid[pos.x][pos.y].gap = Cell::Gap::FULL;
-                    break;
-                } else {
-                    p.grid[pos.x][pos.y].gap = Cell::Gap::NONE;
-                }
-            }
-        }
-
         switch (Random::RandInt(1, 4)) {
             case 1:
                 p.grid[Random::RandInt(0, p.width-1)][0].end = Cell::Dir::UP;
@@ -148,17 +59,17 @@ void Randomizer2::Randomize() {
                 p.grid[Random::RandInt(0, 2)*2 + 4][Random::RandInt(0, 2)*2 + 4].start = true;
                 break;
         }
+    
+        for (Pos pos : Randomizer2Core::CutEdges(p, 35)) {
+            p.grid[pos.x][pos.y].gap = Cell::Gap::FULL;
+        }
 
-        auto solutions = Solver::Solve(p);
-        if (solutions.size() > 0) break;
+        _serializer.WritePuzzle(p, 0x295);
     }
-    PuzzleSerializer(_memory).WritePuzzle(p, 0x295);
-
 }
 
 void Randomizer2::RandomizeKeep() {
-    // *** Hedges 1 ***
-    {
+    { // Hedges 1
         Puzzle p;
         p.NewGrid(4, 4);
 
@@ -177,8 +88,7 @@ void Randomizer2::RandomizeKeep() {
         p.grid[4][8].start = true;
         p.grid[6][0].end = Cell::Dir::UP;
 
-        std::vector<Pos> cutEdges = Randomizer2Core::CutEdgesToBeUnique(p);
-        assert(cutEdges.size() == 5);
+        std::vector<Pos> cutEdges = Randomizer2Core::CutEdges2(p, 5);
         Puzzle copy = p;
         std::vector<int> gates = {0x00344, 0x00488,  0x00489, 0x00495, 0x00496};
         for (int i=0; i<gates.size(); i++) {
@@ -186,14 +96,12 @@ void Randomizer2::RandomizeKeep() {
             copy.grid[pos.x][pos.y].gap = Cell::Gap::BREAK;
             SetGate(gates[i], pos.x, pos.y);
         }
-        auto solutions = Solver::Solve(copy);
-        assert(solutions.size() == 1);
-        p.sequence = solutions[0].sequence;
-        PuzzleSerializer(_memory).WritePuzzle(solutions[0], 0x139);
+        auto solution = GetUniqueSolution(copy);
+        p.sequence = solution.sequence;
+        _serializer.WritePuzzle(p, 0x139);
     }
 
-    // *** Hedges 2 ***
-    {
+    { // Hedges 2
         Puzzle p;
         p.NewGrid(4, 4);
 
@@ -210,29 +118,28 @@ void Randomizer2::RandomizeKeep() {
         p.grid[0][8].start = true;
         p.grid[8][0].end = Cell::Dir::RIGHT;
 
-        std::vector<Pos> cutEdges = Randomizer2Core::CutEdgesToBeUnique(p);
-        assert(cutEdges.size() == 7);
+        std::vector<Pos> cutEdges = Randomizer2Core::CutEdges2(p, 7);
         for (Pos pos : cutEdges) {
             p.grid[pos.x][pos.y].gap = Cell::Gap::FULL;
         }
-        auto solutions = Solver::Solve(p);
-        assert(solutions.size() == 1);
+        auto solution = GetUniqueSolution(p);
 
         Puzzle q;
         q.NewGrid(4, 4);
         q.grid[0][8].start = true;
         q.grid[8][0].end = Cell::Dir::RIGHT;
-        q.sequence = solutions[0].sequence;
+        q.sequence = solution.sequence;
         for (Pos pos : cutEdges) {
             q.grid[pos.x][pos.y].gap = Cell::Gap::FULL;
         }
-        // Cut to 4 of 9 additional edges (total: 11)
-        Randomizer2Core::CutEdgesNotOutsideNotBreakingSequence(q, 4);
-        PuzzleSerializer(_memory).WritePuzzle(q, 0x19DC);
+        // Cut to 6 of 9 additional edges
+        for (Pos pos : Randomizer2Core::CutEdges2(q, 6)) {
+            q.grid[pos.x][pos.y].gap = Cell::Gap::FULL;
+        }
+        _serializer.WritePuzzle(q, 0x19DC);
     }
     
-    // *** Hedges 3 **
-    {
+    { // Hedges 3 [WIP]
         Puzzle p;
         p.NewGrid(4, 4);
 
@@ -251,17 +158,14 @@ void Randomizer2::RandomizeKeep() {
 
         std::vector<int> pebbleMarkers = {0x034a9, 0x034b1, 0x034be, 0x034c4};
 
-
-        std::vector<Pos> cutEdges = Randomizer2Core::CutEdgesToBeUnique(p);
-        assert(cutEdges.size() == 7);
+        std::vector<Pos> cutEdges = Randomizer2Core::CutEdges2(p, 7);
         for (Pos pos : cutEdges) {
             p.grid[pos.x][pos.y].gap = Cell::Gap::BREAK;
         }
-        PuzzleSerializer(_memory).WritePuzzle(p, 0x19E7);
+        // _serializer.WritePuzzle(p, 0x19E7);
     }
 
-    // *** Hedges 4 ***
-    {
+    { // Hedges 4
         Puzzle p;
         p.NewGrid(4, 4);
 
@@ -283,28 +187,33 @@ void Randomizer2::RandomizeKeep() {
         p.grid[0][8].start = true;
         p.grid[4][0].end = Cell::Dir::UP;
 
-        std::vector<Pos> cutEdges = Randomizer2Core::CutEdgesToBeUnique(p);
-        assert(cutEdges.size() == 2);
+        std::vector<Pos> cutEdges = Randomizer2Core::CutEdges2(p, 2);
         for (Pos pos : cutEdges) {
             p.grid[pos.x][pos.y].gap = Cell::Gap::FULL;
         }
-        auto solutions = Solver::Solve(p);
-        assert(solutions.size() == 1);
+        auto solution = GetUniqueSolution(p);
 
         Puzzle q;
         q.NewGrid(4, 4);
         q.grid[0][8].start = true;
         q.grid[4][0].end = Cell::Dir::UP;
-        q.sequence = solutions[0].sequence;
+        q.sequence = solution.sequence;
         for (Pos pos : cutEdges) {
             q.grid[pos.x][pos.y].gap = Cell::Gap::FULL;
         }
-        // 9 cuts, -2 from existing cuts
-        Randomizer2Core::CutEdgesNotOutsideNotBreakingSequence(q, 7);
-        PuzzleSerializer(_memory).WritePuzzle(q, 0x1A0F);
+        for (Pos pos : Randomizer2Core::CutEdges2(q, 7)) {
+            q.grid[pos.x][pos.y].gap = Cell::Gap::FULL;
+        }
+        _serializer.WritePuzzle(q, 0x1A0F);
     }
 }
 
+Puzzle Randomizer2::GetUniqueSolution(Puzzle& p) {
+    auto solutions = Solver::Solve(p);
+    assert(solutions.size() == 1);
+    return solutions[0];
+}
+
 void Randomizer2::SetGate(int panel, int X, int Y) {
     float x, y, z, w;
     if (X%2 == 0 && Y%2 == 1) { // Horizontal
@@ -1,16 +1,20 @@
 #pragma once
 #include <memory>
+#include "PuzzleSerializer.h"
 
 class Memory;
 class Randomizer2 {
 public:
     Randomizer2(const std::shared_ptr<Memory>& memory);
     void Randomize();
+    void RandomizeTutorial();
     void RandomizeKeep();
     
 private:
+    Puzzle GetUniqueSolution(Puzzle& p);
     void SetGate(int panel, int X, int Y);
     void SetPos(int panel, float x, float y, float z);
 
     std::shared_ptr<Memory> _memory;
+    PuzzleSerializer _serializer;
 };
@@ -6,40 +6,46 @@
 #include <iostream>
 #include <cassert>
 
-std::vector<Pos> Randomizer2Core::CutEdgesToBeUnique(const Puzzle& p) {
-    auto [colorGrid, numColors] = CreateColorGrid(p);
+// @Cutnpaste
+std::vector<Pos> Randomizer2Core::CutEdges(const Puzzle& p, size_t numEdges) {
     std::vector<Pos> edges;
     for (int x=0; x<p.width; x++) {
         for (int y=0; y<p.height; y++) {
             if (x%2 == y%2) continue;
             if (p.grid[x][y].gap != Cell::Gap::NONE) continue;
+
+            // If the puzzle already has a sequence, don't cut along it.
+            bool inSequence = false;
+            for (Pos pos : p.sequence) inSequence |= (pos.x == x && pos.y == y);
+            if (inSequence) continue;
             edges.emplace_back(Pos{x, y});
         }
     }
-    return CutEdgesInternal(p, colorGrid, edges, numColors);
+    return CutEdgesInternal(p, edges, numEdges);
 }
 
-void Randomizer2Core::CutEdgesNotOutsideNotBreakingSequence(Puzzle& p, size_t numEdges) {
-    auto [colorGrid, numColors] = CreateColorGrid(p);
-    assert(numEdges <= numColors);
+std::vector<Pos> Randomizer2Core::CutEdges2(const Puzzle& p, size_t numEdges) {
     std::vector<Pos> edges;
+    // Note the iterator bounds; we skip the outer edges.
     for (int x=1; x<p.width-1; x++) {
         for (int y=1; y<p.height-1; y++) {
             if (x%2 == y%2) continue;
             if (p.grid[x][y].gap != Cell::Gap::NONE) continue;
+
+            // If the puzzle already has a sequence, don't cut along it.
             bool inSequence = false;
             for (Pos pos : p.sequence) inSequence |= (pos.x == x && pos.y == y);
             if (inSequence) continue;
             edges.emplace_back(Pos{x, y});
         }
     }
-    std::vector<Pos> cutEdges = CutEdgesInternal(p, colorGrid, edges, numEdges);
-    for (Pos pos : cutEdges) {
-        p.grid[pos.x][pos.y].gap = Cell::Gap::FULL;
-    }
+    return CutEdgesInternal(p, edges, numEdges);
 }
 
-std::vector<Pos> Randomizer2Core::CutEdgesInternal(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, std::vector<Pos>& edges, size_t numEdges) {
+std::vector<Pos> Randomizer2Core::CutEdgesInternal(const Puzzle& p, std::vector<Pos>& edges, size_t numEdges) {
+    auto [colorGrid, numColors] = CreateColorGrid(p);
+    assert(numEdges <= numColors);
+
     std::vector<Pos> cutEdges;
     for (int i=0; i<numEdges; i++) {
         for (int j=0; j<edges.size(); j++) {
@@ -79,6 +85,7 @@ std::vector<Pos> Randomizer2Core::CutEdgesInternal(const Puzzle& p, std::vector<
             }
         }
     }
+    assert(cutEdges.size() == numEdges);
     return cutEdges;
 }
 
@@ -7,12 +7,11 @@ class Puzzle;
 class Randomizer2Core {
 public:
     // CAUTION: Does not actually cut edges, just returns a list of suggested cuts.
-    // Cuts a number of edges equal to the number of colors in the color grid.
-    static std::vector<Pos> CutEdgesToBeUnique(const Puzzle& p);
-    static void CutEdgesNotOutsideNotBreakingSequence(Puzzle& p, size_t numEdges);
+    static std::vector<Pos> CutEdges(const Puzzle& p, size_t numEdges);
+    static std::vector<Pos> CutEdges2(const Puzzle& p, size_t numEdges);
 
 private:
-    static std::vector<Pos> CutEdgesInternal(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, std::vector<Pos>& edges, size_t numEdges);
+    static std::vector<Pos> CutEdgesInternal(const Puzzle& p, std::vector<Pos>& edges, size_t numEdges);
     static void DebugColorGrid(const std::vector<std::vector<int>>& colorGrid);
     static void FloodFill(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, int color, int x, int y);
     static void FloodFillOutside(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, int x, int y);
@@ -161,7 +161,7 @@
     <ClInclude Include="Memory.h" />
     <ClInclude Include="Puzzle.h" />
     <ClInclude Include="Panels.h" />
-    <ClInclude Include="PuzzlerSerializer.h" />
+    <ClInclude Include="PuzzleSerializer.h" />
     <ClInclude Include="Random.h" />
     <ClInclude Include="Randomizer.h" />
     <ClInclude Include="Randomizer2.h" />
@@ -173,7 +173,7 @@
     <ClCompile Include="ChallengeRandomizer.cpp" />
     <ClCompile Include="Memory.cpp" />
     <ClCompile Include="Puzzle.cpp" />
-    <ClCompile Include="PuzzlerSerializer.cpp" />
+    <ClCompile Include="PuzzleSerializer.cpp" />
     <ClCompile Include="Random.cpp" />
     <ClCompile Include="Randomizer.cpp" />
     <ClCompile Include="Randomizer2.cpp" />