From f940276fd9bc38ae34d4119fd1d983171a627400 Mon Sep 17 00:00:00 2001
From: Franklin Wei <git@fwei.tk>
Date: Wed, 15 May 2019 18:16:27 -0400
Subject: puzzles: resync with upstream

This brings the puzzles source to upstream commit e2135d5. (I've made my own
changes on top of that.)

This brings in a couple bugfixes and a new solver for Dominosa.

Change-Id: I11d46b43171787832330a5e2e0d2f353f36f727d
---
 apps/plugins/puzzles/src/findloop.c | 31 ++++++++++++++++++++++++++++++-
 1 file changed, 30 insertions(+), 1 deletion(-)

(limited to 'apps/plugins/puzzles/src/findloop.c')

diff --git a/apps/plugins/puzzles/src/findloop.c b/apps/plugins/puzzles/src/findloop.c
index ffda12d716..4ebdea1f85 100644
--- a/apps/plugins/puzzles/src/findloop.c
+++ b/apps/plugins/puzzles/src/findloop.c
@@ -14,7 +14,7 @@
 #include "puzzles.h"
 
 struct findloopstate {
-    int parent, child, sibling;
+    int parent, child, sibling, component_root;
     bool visited;
     int index, minindex, maxindex;
     int minreachable, maxreachable;
@@ -57,6 +57,33 @@ bool findloop_is_loop_edge(struct findloopstate *pv, int u, int v)
     return !(pv[u].bridge == v || pv[v].bridge == u);
 }
 
+static bool findloop_is_bridge_oneway(
+    struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices)
+{
+    int r, total, below;
+
+    if (pv[u].bridge != v)
+        return false;
+
+    r = pv[u].component_root;
+    total = pv[r].maxindex - pv[r].minindex + 1;
+    below = pv[u].maxindex - pv[u].minindex + 1;
+
+    if (u_vertices)
+        *u_vertices = below;
+    if (v_vertices)
+        *v_vertices = total - below;
+
+    return true;
+}
+
+bool findloop_is_bridge(
+    struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices)
+{
+    return (findloop_is_bridge_oneway(pv, u, v, u_vertices, v_vertices) ||
+            findloop_is_bridge_oneway(pv, v, u, v_vertices, u_vertices));
+}
+
 bool findloop_run(struct findloopstate *pv, int nvertices,
                   neighbour_fn_t neighbour, void *ctx)
 {
@@ -94,6 +121,7 @@ bool findloop_run(struct findloopstate *pv, int nvertices,
              */
             pv[v].sibling = pv[root].child;
             pv[root].child = v;
+            pv[v].component_root = v;
             debug(("%d is new child of root\n", v));
 
             u = v;
@@ -116,6 +144,7 @@ bool findloop_run(struct findloopstate *pv, int nvertices,
                             pv[w].child = -1;
                             pv[w].sibling = pv[u].child;
                             pv[w].parent = u;
+                            pv[w].component_root = pv[u].component_root;
                             pv[u].child = w;
                         }
 
-- 
cgit v1.2.3