New puzzle! Or rather, new-ish, because this one has been lying around

in the 'unfinished' directory for a while, and has now been finished
up thanks to James Harvey putting in some effort and galvanising me to
put in the rest. This is 'Pearl', an implementation of Nikoli's 'Masyu'.

The code in Loopy that generates a random loop along grid edges to use
as the puzzle solution has been abstracted out into loopgen.[ch] so
that Pearl can use it for its puzzle solutions too. I've also
introduced a new utility module called 'tdq' (for 'to-do queue').

[originally from svn r9379]

1 files changed, 88 insertions, 0 deletions

diff --git a/tdq.c b/tdq.c
new file mode 100644
index 0000000..d66f9f4
--- /dev/null
+++ b/tdq.c
@@ -0,0 +1,88 @@
+/*
+ * tdq.c: implement a 'to-do queue', a simple de-duplicating to-do
+ * list mechanism.
+ */
+
+#include <assert.h>
+
+#include "puzzles.h"
+
+/*
+ * Implementation: a tdq consists of a circular buffer of size n
+ * storing the integers currently in the queue, plus an array of n
+ * booleans indicating whether each integer is already there.
+ *
+ * Using a circular buffer of size n to store between 0 and n items
+ * inclusive has an obvious failure mode: if the input and output
+ * pointers are the same, how do you know whether that means the
+ * buffer is full or empty?
+ *
+ * In this application we have a simple way to tell: in the former
+ * case, the flags array is all 1s, and in the latter case it's all
+ * 0s. So we could spot that case and check, say, flags[0].
+ *
+ * However, it's even easier to simply determine whether the queue is
+ * non-empty by testing flags[buffer[op]] - that way we don't even
+ * _have_ to compare ip against op.
+ */
+
+struct tdq {
+    int n;
+    int *queue;
+    int ip, op;                        /* in pointer, out pointer */
+    char *flags;
+};
+
+tdq *tdq_new(int n)
+{
+    int i;
+    tdq *tdq = snew(struct tdq);
+    tdq->queue = snewn(n, int);
+    tdq->flags = snewn(n, char);
+    for (i = 0; i < n; i++) {
+        tdq->queue[i] = 0;
+        tdq->flags[i] = 0;
+    }
+    tdq->n = n;
+    tdq->ip = tdq->op = 0;
+    return tdq;
+}
+
+void tdq_free(tdq *tdq)
+{
+    sfree(tdq->queue);
+    sfree(tdq->flags);
+    sfree(tdq);
+}
+
+void tdq_add(tdq *tdq, int k)
+{
+    assert((unsigned)k < (unsigned)tdq->n);
+    if (!tdq->flags[k]) {
+        tdq->queue[tdq->ip] = k;
+        tdq->flags[k] = 1;
+        if (++tdq->ip == tdq->n)
+            tdq->ip = 0;
+    }
+}
+
+int tdq_remove(tdq *tdq)
+{
+    int ret = tdq->queue[tdq->op];
+
+    if (!tdq->flags[ret])
+        return -1;
+
+    tdq->flags[ret] = 0;
+    if (++tdq->op == tdq->n)
+        tdq->op = 0;
+
+    return ret;
+}
+
+void tdq_fill(tdq *tdq)
+{
+    int i;
+    for (i = 0; i < tdq->n; i++)
+        tdq_add(tdq, i);
+}