tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * flip.c: Puzzle involving lighting up all the squares on a grid,
3 * where each click toggles an overlapping set of lights.
4 */
5
6#include <stdio.h>
7#include <stdlib.h>
8#include <string.h>
9#include <assert.h>
10#include <ctype.h>
11#include <limits.h>
12#ifdef NO_TGMATH_H
13# include <math.h>
14#else
15# include <tgmath.h>
16#endif
17
18#include "puzzles.h"
19#include "tree234.h"
20
21enum {
22 COL_BACKGROUND,
23 COL_WRONG,
24 COL_RIGHT,
25 COL_GRID,
26 COL_DIAG,
27 COL_HINT,
28 COL_CURSOR,
29 NCOLOURS
30};
31
32#define PREFERRED_TILE_SIZE 48
33#define TILE_SIZE (ds->tilesize)
34#define BORDER (TILE_SIZE / 2)
35#define COORD(x) ( (x) * TILE_SIZE + BORDER )
36#define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
37
38#define ANIM_TIME 0.25F
39#define FLASH_FRAME 0.07F
40
41/*
42 * Possible ways to decide which lights are toggled by each click.
43 * Essentially, each of these describes a means of inventing a
44 * matrix over GF(2).
45 */
46enum {
47 CROSSES, RANDOM
48};
49
50struct game_params {
51 int w, h;
52 int matrix_type;
53};
54
55/*
56 * This structure is shared between all the game_states describing
57 * a particular game, so it's reference-counted.
58 */
59struct matrix {
60 int refcount;
61 unsigned char *matrix; /* array of (w*h) by (w*h) */
62};
63
64struct game_state {
65 int w, h;
66 int moves;
67 bool completed, cheated, hints_active;
68 unsigned char *grid; /* array of w*h */
69 struct matrix *matrix;
70};
71
72static game_params *default_params(void)
73{
74 game_params *ret = snew(game_params);
75
76 ret->w = ret->h = 5;
77 ret->matrix_type = CROSSES;
78
79 return ret;
80}
81
82static const struct game_params flip_presets[] = {
83 {3, 3, CROSSES},
84 {4, 4, CROSSES},
85 {5, 5, CROSSES},
86 {3, 3, RANDOM},
87 {4, 4, RANDOM},
88 {5, 5, RANDOM},
89};
90
91static bool game_fetch_preset(int i, char **name, game_params **params)
92{
93 game_params *ret;
94 char str[80];
95
96 if (i < 0 || i >= lenof(flip_presets))
97 return false;
98
99 ret = snew(game_params);
100 *ret = flip_presets[i];
101
102 sprintf(str, "%dx%d %s", ret->w, ret->h,
103 ret->matrix_type == CROSSES ? "Crosses" : "Random");
104
105 *name = dupstr(str);
106 *params = ret;
107 return true;
108}
109
110static void free_params(game_params *params)
111{
112 sfree(params);
113}
114
115static game_params *dup_params(const game_params *params)
116{
117 game_params *ret = snew(game_params);
118 *ret = *params; /* structure copy */
119 return ret;
120}
121
122static void decode_params(game_params *ret, char const *string)
123{
124 ret->w = ret->h = atoi(string);
125 while (*string && isdigit((unsigned char)*string)) string++;
126 if (*string == 'x') {
127 string++;
128 ret->h = atoi(string);
129 while (*string && isdigit((unsigned char)*string)) string++;
130 }
131 if (*string == 'r') {
132 string++;
133 ret->matrix_type = RANDOM;
134 } else if (*string == 'c') {
135 string++;
136 ret->matrix_type = CROSSES;
137 }
138}
139
140static char *encode_params(const game_params *params, bool full)
141{
142 char data[256];
143
144 sprintf(data, "%dx%d%s", params->w, params->h,
145 !full ? "" : params->matrix_type == CROSSES ? "c" : "r");
146
147 return dupstr(data);
148}
149
150static config_item *game_configure(const game_params *params)
151{
152 config_item *ret = snewn(4, config_item);
153 char buf[80];
154
155 ret[0].name = "Width";
156 ret[0].type = C_STRING;
157 sprintf(buf, "%d", params->w);
158 ret[0].u.string.sval = dupstr(buf);
159
160 ret[1].name = "Height";
161 ret[1].type = C_STRING;
162 sprintf(buf, "%d", params->h);
163 ret[1].u.string.sval = dupstr(buf);
164
165 ret[2].name = "Shape type";
166 ret[2].type = C_CHOICES;
167 ret[2].u.choices.choicenames = ":Crosses:Random";
168 ret[2].u.choices.selected = params->matrix_type;
169
170 ret[3].name = NULL;
171 ret[3].type = C_END;
172
173 return ret;
174}
175
176static game_params *custom_params(const config_item *cfg)
177{
178 game_params *ret = snew(game_params);
179
180 ret->w = atoi(cfg[0].u.string.sval);
181 ret->h = atoi(cfg[1].u.string.sval);
182 ret->matrix_type = cfg[2].u.choices.selected;
183
184 return ret;
185}
186
187static const char *validate_params(const game_params *params, bool full)
188{
189 int wh;
190
191 if (params->w <= 0 || params->h <= 0)
192 return "Width and height must both be greater than zero";
193 if (params->w > (INT_MAX - 3) / params->h)
194 return "Width times height must not be unreasonably large";
195 wh = params->w * params->h;
196 if (wh > (INT_MAX - 3) / wh)
197 return "Width times height is too large";
198 return NULL;
199}
200
201static char *encode_bitmap(unsigned char *bmp, int len)
202{
203 int slen = (len + 3) / 4;
204 char *ret;
205 int i;
206
207 ret = snewn(slen + 1, char);
208 for (i = 0; i < slen; i++) {
209 int j, v;
210 v = 0;
211 for (j = 0; j < 4; j++)
212 if (i*4+j < len && bmp[i*4+j])
213 v |= 8 >> j;
214 ret[i] = "0123456789abcdef"[v];
215 }
216 ret[slen] = '\0';
217 return ret;
218}
219
220static void decode_bitmap(unsigned char *bmp, int len, const char *hex)
221{
222 int slen = (len + 3) / 4;
223 int i;
224
225 for (i = 0; i < slen; i++) {
226 int j, v, c = hex[i];
227 if (c >= '0' && c <= '9')
228 v = c - '0';
229 else if (c >= 'A' && c <= 'F')
230 v = c - 'A' + 10;
231 else if (c >= 'a' && c <= 'f')
232 v = c - 'a' + 10;
233 else
234 v = 0; /* shouldn't happen */
235 for (j = 0; j < 4; j++) {
236 if (i*4+j < len) {
237 if (v & (8 >> j))
238 bmp[i*4+j] = 1;
239 else
240 bmp[i*4+j] = 0;
241 }
242 }
243 }
244}
245
246/*
247 * Structure used during random matrix generation, and a compare
248 * function to permit storage in a tree234.
249 */
250struct sq {
251 int cx, cy; /* coords of click square */
252 int x, y; /* coords of output square */
253 /*
254 * Number of click squares which currently affect this output
255 * square.
256 */
257 int coverage;
258 /*
259 * Number of output squares currently affected by this click
260 * square.
261 */
262 int ominosize;
263};
264#define SORT(field) do { \
265 if (a->field < b->field) \
266 return -1; \
267 else if (a->field > b->field) \
268 return +1; \
269} while (0)
270/*
271 * Compare function for choosing the next square to add. We must
272 * sort by coverage, then by omino size, then everything else.
273 */
274static int sqcmp_pick(void *av, void *bv)
275{
276 struct sq *a = (struct sq *)av;
277 struct sq *b = (struct sq *)bv;
278 SORT(coverage);
279 SORT(ominosize);
280 SORT(cy);
281 SORT(cx);
282 SORT(y);
283 SORT(x);
284 return 0;
285}
286/*
287 * Compare function for adjusting the coverage figures after a
288 * change. We sort first by coverage and output square, then by
289 * everything else.
290 */
291static int sqcmp_cov(void *av, void *bv)
292{
293 struct sq *a = (struct sq *)av;
294 struct sq *b = (struct sq *)bv;
295 SORT(coverage);
296 SORT(y);
297 SORT(x);
298 SORT(ominosize);
299 SORT(cy);
300 SORT(cx);
301 return 0;
302}
303/*
304 * Compare function for adjusting the omino sizes after a change.
305 * We sort first by omino size and input square, then by everything
306 * else.
307 */
308static int sqcmp_osize(void *av, void *bv)
309{
310 struct sq *a = (struct sq *)av;
311 struct sq *b = (struct sq *)bv;
312 SORT(ominosize);
313 SORT(cy);
314 SORT(cx);
315 SORT(coverage);
316 SORT(y);
317 SORT(x);
318 return 0;
319}
320static void addsq(tree234 *t, int w, int h, int cx, int cy,
321 int x, int y, unsigned char *matrix)
322{
323 int wh = w * h;
324 struct sq *sq;
325 int i;
326
327 if (x < 0 || x >= w || y < 0 || y >= h)
328 return;
329 if (abs(x-cx) > 1 || abs(y-cy) > 1)
330 return;
331 if (matrix[(cy*w+cx) * wh + y*w+x])
332 return;
333
334 sq = snew(struct sq);
335 sq->cx = cx;
336 sq->cy = cy;
337 sq->x = x;
338 sq->y = y;
339 sq->coverage = sq->ominosize = 0;
340 for (i = 0; i < wh; i++) {
341 if (matrix[i * wh + y*w+x])
342 sq->coverage++;
343 if (matrix[(cy*w+cx) * wh + i])
344 sq->ominosize++;
345 }
346
347 if (add234(t, sq) != sq)
348 sfree(sq); /* already there */
349}
350static void addneighbours(tree234 *t, int w, int h, int cx, int cy,
351 int x, int y, unsigned char *matrix)
352{
353 addsq(t, w, h, cx, cy, x-1, y, matrix);
354 addsq(t, w, h, cx, cy, x+1, y, matrix);
355 addsq(t, w, h, cx, cy, x, y-1, matrix);
356 addsq(t, w, h, cx, cy, x, y+1, matrix);
357}
358
359static char *new_game_desc(const game_params *params, random_state *rs,
360 char **aux, bool interactive)
361{
362 int w = params->w, h = params->h, wh = w * h;
363 int i, j;
364 unsigned char *matrix, *grid;
365 char *mbmp, *gbmp, *ret;
366
367 matrix = snewn(wh * wh, unsigned char);
368 grid = snewn(wh, unsigned char);
369
370 /*
371 * First set up the matrix.
372 */
373 switch (params->matrix_type) {
374 case CROSSES:
375 for (i = 0; i < wh; i++) {
376 int ix = i % w, iy = i / w;
377 for (j = 0; j < wh; j++) {
378 int jx = j % w, jy = j / w;
379 if (abs(jx - ix) + abs(jy - iy) <= 1)
380 matrix[i*wh+j] = 1;
381 else
382 matrix[i*wh+j] = 0;
383 }
384 }
385 break;
386 case RANDOM:
387 while (1) {
388 tree234 *pick, *cov, *osize;
389 int limit;
390
391 pick = newtree234(sqcmp_pick);
392 cov = newtree234(sqcmp_cov);
393 osize = newtree234(sqcmp_osize);
394
395 memset(matrix, 0, wh * wh);
396 for (i = 0; i < wh; i++) {
397 matrix[i*wh+i] = 1;
398 }
399
400 for (i = 0; i < wh; i++) {
401 int ix = i % w, iy = i / w;
402 addneighbours(pick, w, h, ix, iy, ix, iy, matrix);
403 addneighbours(cov, w, h, ix, iy, ix, iy, matrix);
404 addneighbours(osize, w, h, ix, iy, ix, iy, matrix);
405 }
406
407 /*
408 * Repeatedly choose a square to add to the matrix,
409 * until we have enough. I'll arbitrarily choose our
410 * limit to be the same as the total number of set bits
411 * in the crosses matrix.
412 */
413 limit = 4*wh - 2*(w+h); /* centre squares already present */
414
415 while (limit-- > 0) {
416 struct sq *sq, *sq2, sqlocal;
417 int k;
418
419 /*
420 * Find the lowest element in the pick tree.
421 */
422 sq = index234(pick, 0);
423
424 /*
425 * Find the highest element with the same coverage
426 * and omino size, by setting all other elements to
427 * lots.
428 */
429 sqlocal = *sq;
430 sqlocal.cx = sqlocal.cy = sqlocal.x = sqlocal.y = wh;
431 sq = findrelpos234(pick, &sqlocal, NULL, REL234_LT, &k);
432 assert(sq != 0);
433
434 /*
435 * Pick at random from all elements up to k of the
436 * pick tree.
437 */
438 k = random_upto(rs, k+1);
439 sq = delpos234(pick, k);
440 del234(cov, sq);
441 del234(osize, sq);
442
443 /*
444 * Add this square to the matrix.
445 */
446 matrix[(sq->cy * w + sq->cx) * wh + (sq->y * w + sq->x)] = 1;
447
448 /*
449 * Correct the matrix coverage field of any sq
450 * which points at this output square.
451 */
452 sqlocal = *sq;
453 sqlocal.cx = sqlocal.cy = sqlocal.ominosize = -1;
454 while ((sq2 = findrel234(cov, &sqlocal, NULL,
455 REL234_GT)) != NULL &&
456 sq2->coverage == sq->coverage &&
457 sq2->x == sq->x && sq2->y == sq->y) {
458 del234(pick, sq2);
459 del234(cov, sq2);
460 del234(osize, sq2);
461 sq2->coverage++;
462 add234(pick, sq2);
463 add234(cov, sq2);
464 add234(osize, sq2);
465 }
466
467 /*
468 * Correct the omino size field of any sq which
469 * points at this input square.
470 */
471 sqlocal = *sq;
472 sqlocal.x = sqlocal.y = sqlocal.coverage = -1;
473 while ((sq2 = findrel234(osize, &sqlocal, NULL,
474 REL234_GT)) != NULL &&
475 sq2->ominosize == sq->ominosize &&
476 sq2->cx == sq->cx && sq2->cy == sq->cy) {
477 del234(pick, sq2);
478 del234(cov, sq2);
479 del234(osize, sq2);
480 sq2->ominosize++;
481 add234(pick, sq2);
482 add234(cov, sq2);
483 add234(osize, sq2);
484 }
485
486 /*
487 * The sq we actually picked out of the tree is
488 * finished with; but its neighbours now need to
489 * appear.
490 */
491 addneighbours(pick, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
492 addneighbours(cov, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
493 addneighbours(osize, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
494 sfree(sq);
495 }
496
497 /*
498 * Free all remaining sq structures.
499 */
500 {
501 struct sq *sq;
502 while ((sq = delpos234(pick, 0)) != NULL)
503 sfree(sq);
504 }
505 freetree234(pick);
506 freetree234(cov);
507 freetree234(osize);
508
509 /*
510 * Finally, check to see if any two matrix rows are
511 * exactly identical. If so, this is not an acceptable
512 * matrix, and we give up and go round again.
513 *
514 * I haven't been immediately able to think of a
515 * plausible means of algorithmically avoiding this
516 * situation (by, say, making a small perturbation to
517 * an offending matrix), so for the moment I'm just
518 * going to deal with it by throwing the whole thing
519 * away. I suspect this will lead to scalability
520 * problems (since most of the things happening in
521 * these matrices are local, the chance of _some_
522 * neighbourhood having two identical regions will
523 * increase with the grid area), but so far this puzzle
524 * seems to be really hard at large sizes so I'm not
525 * massively worried yet. Anyone needs this done
526 * better, they're welcome to submit a patch.
527 */
528 for (i = 0; i < wh; i++) {
529 for (j = 0; j < wh; j++)
530 if (i != j &&
531 !memcmp(matrix + i * wh, matrix + j * wh, wh))
532 break;
533 if (j < wh)
534 break;
535 }
536 if (i == wh)
537 break; /* no matches found */
538 }
539 break;
540 }
541
542 /*
543 * Now invent a random initial set of lights.
544 *
545 * At first glance it looks as if it might be quite difficult
546 * to choose equiprobably from all soluble light sets. After
547 * all, soluble light sets are those in the image space of the
548 * transformation matrix; so first we'd have to identify that
549 * space and its dimension, then pick a random coordinate for
550 * each basis vector and recombine. Lot of fiddly matrix
551 * algebra there.
552 *
553 * However, vector spaces are nicely orthogonal and relieve us
554 * of all that difficulty. For every point in the image space,
555 * there are precisely as many points in the input space that
556 * map to it as there are elements in the kernel of the
557 * transformation matrix (because adding any kernel element to
558 * the input does not change the output, and because any two
559 * inputs mapping to the same output must differ by an element
560 * of the kernel because that's what the kernel _is_); and
561 * these cosets are all disjoint (obviously, since no input
562 * point can map to more than one output point) and cover the
563 * whole space (equally obviously, because no input point can
564 * map to fewer than one output point!).
565 *
566 * So the input space contains the same number of points for
567 * each point in the output space; thus, we can simply choose
568 * equiprobably from elements of the _input_ space, and filter
569 * the result through the transformation matrix in the obvious
570 * way, and we thereby guarantee to choose equiprobably from
571 * all the output points. Phew!
572 */
573 while (1) {
574 memset(grid, 0, wh);
575 for (i = 0; i < wh; i++) {
576 int v = random_upto(rs, 2);
577 if (v) {
578 for (j = 0; j < wh; j++)
579 grid[j] ^= matrix[i*wh+j];
580 }
581 }
582 /*
583 * Ensure we don't have the starting state already!
584 */
585 for (i = 0; i < wh; i++)
586 if (grid[i])
587 break;
588 if (i < wh)
589 break;
590 }
591
592 /*
593 * Now encode the matrix and the starting grid as a game
594 * description. We'll do this by concatenating two great big
595 * hex bitmaps.
596 */
597 mbmp = encode_bitmap(matrix, wh*wh);
598 gbmp = encode_bitmap(grid, wh);
599 ret = snewn(strlen(mbmp) + strlen(gbmp) + 2, char);
600 sprintf(ret, "%s,%s", mbmp, gbmp);
601 sfree(mbmp);
602 sfree(gbmp);
603 sfree(matrix);
604 sfree(grid);
605 return ret;
606}
607
608static const char *validate_desc(const game_params *params, const char *desc)
609{
610 int w = params->w, h = params->h, wh = w * h;
611 int mlen = (wh*wh+3)/4, glen = (wh+3)/4;
612
613 if (strspn(desc, "0123456789abcdefABCDEF") != mlen)
614 return "Matrix description is wrong length";
615 if (desc[mlen] != ',')
616 return "Expected comma after matrix description";
617 if (strspn(desc+mlen+1, "0123456789abcdefABCDEF") != glen)
618 return "Grid description is wrong length";
619 if (desc[mlen+1+glen])
620 return "Unexpected data after grid description";
621
622 return NULL;
623}
624
625static game_state *new_game(midend *me, const game_params *params,
626 const char *desc)
627{
628 int w = params->w, h = params->h, wh = w * h;
629 int mlen = (wh*wh+3)/4;
630
631 game_state *state = snew(game_state);
632
633 state->w = w;
634 state->h = h;
635 state->completed = false;
636 state->cheated = false;
637 state->hints_active = false;
638 state->moves = 0;
639 state->matrix = snew(struct matrix);
640 state->matrix->refcount = 1;
641 state->matrix->matrix = snewn(wh*wh, unsigned char);
642 decode_bitmap(state->matrix->matrix, wh*wh, desc);
643 state->grid = snewn(wh, unsigned char);
644 decode_bitmap(state->grid, wh, desc + mlen + 1);
645
646 return state;
647}
648
649static game_state *dup_game(const game_state *state)
650{
651 game_state *ret = snew(game_state);
652
653 ret->w = state->w;
654 ret->h = state->h;
655 ret->completed = state->completed;
656 ret->cheated = state->cheated;
657 ret->hints_active = state->hints_active;
658 ret->moves = state->moves;
659 ret->matrix = state->matrix;
660 state->matrix->refcount++;
661 ret->grid = snewn(ret->w * ret->h, unsigned char);
662 memcpy(ret->grid, state->grid, ret->w * ret->h);
663
664 return ret;
665}
666
667static void free_game(game_state *state)
668{
669 sfree(state->grid);
670 if (--state->matrix->refcount <= 0) {
671 sfree(state->matrix->matrix);
672 sfree(state->matrix);
673 }
674 sfree(state);
675}
676
677static void rowxor(unsigned char *row1, unsigned char *row2, int len)
678{
679 int i;
680 for (i = 0; i < len; i++)
681 row1[i] ^= row2[i];
682}
683
684static char *solve_game(const game_state *state, const game_state *currstate,
685 const char *aux, const char **error)
686{
687 int w = state->w, h = state->h, wh = w * h;
688 unsigned char *equations, *solution, *shortest;
689 int *und, nund;
690 int rowsdone, colsdone;
691 int i, j, k, len, bestlen;
692 char *ret;
693
694 /*
695 * Set up a list of simultaneous equations. Each one is of
696 * length (wh+1) and has wh coefficients followed by a value.
697 */
698 equations = snewn((wh + 1) * wh, unsigned char);
699 for (i = 0; i < wh; i++) {
700 for (j = 0; j < wh; j++)
701 equations[i * (wh+1) + j] = currstate->matrix->matrix[j*wh+i];
702 equations[i * (wh+1) + wh] = currstate->grid[i] & 1;
703 }
704
705 /*
706 * Perform Gaussian elimination over GF(2).
707 */
708 rowsdone = colsdone = 0;
709 nund = 0;
710 und = snewn(wh, int);
711 do {
712 /*
713 * Find the leftmost column which has a 1 in it somewhere
714 * outside the first `rowsdone' rows.
715 */
716 j = -1;
717 for (i = colsdone; i < wh; i++) {
718 for (j = rowsdone; j < wh; j++)
719 if (equations[j * (wh+1) + i])
720 break;
721 if (j < wh)
722 break; /* found one */
723 /*
724 * This is a column which will not have an equation
725 * controlling it. Mark it as undetermined.
726 */
727 und[nund++] = i;
728 }
729
730 /*
731 * If there wasn't one, then we've finished: all remaining
732 * equations are of the form 0 = constant. Check to see if
733 * any of them wants 0 to be equal to 1; this is the
734 * condition which indicates an insoluble problem
735 * (therefore _hopefully_ one typed in by a user!).
736 */
737 if (i == wh) {
738 for (j = rowsdone; j < wh; j++)
739 if (equations[j * (wh+1) + wh]) {
740 *error = "No solution exists for this position";
741 sfree(equations);
742 sfree(und);
743 return NULL;
744 }
745 break;
746 }
747
748 /*
749 * We've found a 1. It's in column i, and the topmost 1 in
750 * that column is in row j. Do a row-XOR to move it up to
751 * the topmost row if it isn't already there.
752 */
753 assert(j != -1);
754 if (j > rowsdone)
755 rowxor(equations + rowsdone*(wh+1), equations + j*(wh+1), wh+1);
756
757 /*
758 * Do row-XORs to eliminate that 1 from all rows below the
759 * topmost row.
760 */
761 for (j = rowsdone + 1; j < wh; j++)
762 if (equations[j*(wh+1) + i])
763 rowxor(equations + j*(wh+1),
764 equations + rowsdone*(wh+1), wh+1);
765
766 /*
767 * Mark this row and column as done.
768 */
769 rowsdone++;
770 colsdone = i+1;
771
772 /*
773 * If we've done all the rows, terminate.
774 */
775 } while (rowsdone < wh);
776
777 /*
778 * If we reach here, we have the ability to produce a solution.
779 * So we go through _all_ possible solutions (each
780 * corresponding to a set of arbitrary choices of those
781 * components not directly determined by an equation), and pick
782 * one requiring the smallest number of flips.
783 */
784 solution = snewn(wh, unsigned char);
785 shortest = snewn(wh, unsigned char);
786 memset(solution, 0, wh);
787 bestlen = wh + 1;
788 while (1) {
789 /*
790 * Find a solution based on the current values of the
791 * undetermined variables.
792 */
793 for (j = rowsdone; j-- ;) {
794 int v;
795
796 /*
797 * Find the leftmost set bit in this equation.
798 */
799 for (i = 0; i < wh; i++)
800 if (equations[j * (wh+1) + i])
801 break;
802 assert(i < wh); /* there must have been one! */
803
804 /*
805 * Compute this variable using the rest.
806 */
807 v = equations[j * (wh+1) + wh];
808 for (k = i+1; k < wh; k++)
809 if (equations[j * (wh+1) + k])
810 v ^= solution[k];
811
812 solution[i] = v;
813 }
814
815 /*
816 * Compare this solution to the current best one, and
817 * replace the best one if this one is shorter.
818 */
819 len = 0;
820 for (i = 0; i < wh; i++)
821 if (solution[i])
822 len++;
823 if (len < bestlen) {
824 bestlen = len;
825 memcpy(shortest, solution, wh);
826 }
827
828 /*
829 * Now increment the binary number given by the
830 * undetermined variables: turn all 1s into 0s until we see
831 * a 0, at which point we turn it into a 1.
832 */
833 for (i = 0; i < nund; i++) {
834 solution[und[i]] = !solution[und[i]];
835 if (solution[und[i]])
836 break;
837 }
838
839 /*
840 * If we didn't find a 0 at any point, we have wrapped
841 * round and are back at the start, i.e. we have enumerated
842 * all solutions.
843 */
844 if (i == nund)
845 break;
846 }
847
848 /*
849 * We have a solution. Produce a move string encoding the
850 * solution.
851 */
852 ret = snewn(wh + 2, char);
853 ret[0] = 'S';
854 for (i = 0; i < wh; i++)
855 ret[i+1] = shortest[i] ? '1' : '0';
856 ret[wh+1] = '\0';
857
858 sfree(shortest);
859 sfree(solution);
860 sfree(equations);
861 sfree(und);
862
863 return ret;
864}
865
866static bool game_can_format_as_text_now(const game_params *params)
867{
868 return true;
869}
870
871#define RIGHT 1
872#define DOWN gw
873
874static char *game_text_format(const game_state *state)
875{
876 int w = state->w, h = state->h, wh = w*h, r, c, dx, dy;
877 int cw = 4, ch = 4, gw = w * cw + 2, gh = h * ch + 1, len = gw * gh;
878 char *board = snewn(len + 1, char);
879
880 memset(board, ' ', len - 1);
881
882 for (r = 0; r < h; ++r) {
883 for (c = 0; c < w; ++c) {
884 int cell = r*ch*gw + c*cw, center = cell+(ch/2)*DOWN + cw/2*RIGHT;
885 char flip = (state->grid[r*w + c] & 1) ? '#' : '.';
886 for (dy = -1 + (r == 0); dy <= 1 - (r == h - 1); ++dy)
887 for (dx = -1 + (c == 0); dx <= 1 - (c == w - 1); ++dx)
888 if (state->matrix->matrix[(r*w+c)*wh + ((r+dy)*w + c+dx)])
889 board[center + dy*DOWN + dx*RIGHT] = flip;
890 board[cell] = '+';
891 for (dx = 1; dx < cw; ++dx) board[cell+dx*RIGHT] = '-';
892 for (dy = 1; dy < ch; ++dy) board[cell+dy*DOWN] = '|';
893 }
894 board[r*ch*gw + gw - 2] = '+';
895 board[r*ch*gw + gw - 1] = '\n';
896 for (dy = 1; dy < ch; ++dy) {
897 board[r*ch*gw + gw - 2 + dy*DOWN] = '|';
898 board[r*ch*gw + gw - 1 + dy*DOWN] = '\n';
899 }
900 }
901 memset(board + len - gw, '-', gw - 2);
902 for (c = 0; c <= w; ++c) board[len - gw + cw*c] = '+';
903 board[len - 1] = '\n';
904 board[len] = '\0';
905 return board;
906}
907
908#undef RIGHT
909#undef DOWN
910
911struct game_ui {
912 int cx, cy;
913 bool cdraw;
914};
915
916static game_ui *new_ui(const game_state *state)
917{
918 game_ui *ui = snew(game_ui);
919 ui->cx = ui->cy = 0;
920 ui->cdraw = getenv_bool("PUZZLES_SHOW_CURSOR", false);
921 return ui;
922}
923
924static void free_ui(game_ui *ui)
925{
926 sfree(ui);
927}
928
929static void game_changed_state(game_ui *ui, const game_state *oldstate,
930 const game_state *newstate)
931{
932}
933
934static const char *current_key_label(const game_ui *ui,
935 const game_state *state, int button)
936{
937 if (IS_CURSOR_SELECT(button)) return "Flip";
938 return "";
939}
940
941struct game_drawstate {
942 int w, h;
943 bool started;
944 unsigned char *tiles;
945 int tilesize;
946};
947
948static char *interpret_move(const game_state *state, game_ui *ui,
949 const game_drawstate *ds,
950 int x, int y, int button)
951{
952 int w = state->w, h = state->h, wh = w * h;
953 char buf[80], *nullret = MOVE_UNUSED;
954
955 if (button == LEFT_BUTTON || IS_CURSOR_SELECT(button)) {
956 int tx, ty;
957 if (button == LEFT_BUTTON) {
958 tx = FROMCOORD(x), ty = FROMCOORD(y);
959 ui->cdraw = false;
960 } else {
961 tx = ui->cx; ty = ui->cy;
962 ui->cdraw = true;
963 }
964 nullret = MOVE_UI_UPDATE;
965
966 if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
967 /*
968 * It's just possible that a manually entered game ID
969 * will have at least one square do nothing whatsoever.
970 * If so, we avoid encoding a move at all.
971 */
972 int i = ty*w+tx, j;
973 bool makemove = false;
974 for (j = 0; j < wh; j++) {
975 if (state->matrix->matrix[i*wh+j])
976 makemove = true;
977 }
978 if (makemove) {
979 sprintf(buf, "M%d,%d", tx, ty);
980 return dupstr(buf);
981 } else {
982 return MOVE_NO_EFFECT;
983 }
984 }
985 } else if (IS_CURSOR_MOVE(button))
986 nullret = move_cursor(button, &ui->cx, &ui->cy, state->w, state->h,
987 false, &ui->cdraw);
988
989 return nullret;
990}
991
992static game_state *execute_move(const game_state *from, const char *move)
993{
994 int w = from->w, h = from->h, wh = w * h;
995 game_state *ret;
996 int x, y;
997
998 if (move[0] == 'S' && strlen(move) == wh+1) {
999 int i;
1000
1001 ret = dup_game(from);
1002 ret->hints_active = true;
1003 ret->cheated = true;
1004 for (i = 0; i < wh; i++) {
1005 ret->grid[i] &= ~2;
1006 if (move[i+1] != '0')
1007 ret->grid[i] |= 2;
1008 }
1009 return ret;
1010 } else if (move[0] == 'M' &&
1011 sscanf(move+1, "%d,%d", &x, &y) == 2 &&
1012 x >= 0 && x < w && y >= 0 && y < h) {
1013 int i, j;
1014 bool done;
1015
1016 ret = dup_game(from);
1017
1018 if (!ret->completed)
1019 ret->moves++;
1020
1021 i = y * w + x;
1022
1023 done = true;
1024 for (j = 0; j < wh; j++) {
1025 ret->grid[j] ^= ret->matrix->matrix[i*wh+j];
1026 if (ret->grid[j] & 1)
1027 done = false;
1028 }
1029 ret->grid[i] ^= 2; /* toggle hint */
1030 if (done) {
1031 ret->completed = true;
1032 ret->hints_active = false;
1033 }
1034
1035 return ret;
1036 } else
1037 return NULL; /* can't parse move string */
1038}
1039
1040/* ----------------------------------------------------------------------
1041 * Drawing routines.
1042 */
1043
1044static void game_compute_size(const game_params *params, int tilesize,
1045 const game_ui *ui, int *x, int *y)
1046{
1047 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1048 struct { int tilesize; } ads, *ds = &ads;
1049 ads.tilesize = tilesize;
1050
1051 *x = TILE_SIZE * params->w + 2 * BORDER;
1052 *y = TILE_SIZE * params->h + 2 * BORDER;
1053}
1054
1055static void game_set_size(drawing *dr, game_drawstate *ds,
1056 const game_params *params, int tilesize)
1057{
1058 ds->tilesize = tilesize;
1059}
1060
1061static float *game_colours(frontend *fe, int *ncolours)
1062{
1063 float *ret = snewn(3 * NCOLOURS, float);
1064
1065 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1066
1067 ret[COL_WRONG * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 3;
1068 ret[COL_WRONG * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 3;
1069 ret[COL_WRONG * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 3;
1070
1071 ret[COL_RIGHT * 3 + 0] = 1.0F;
1072 ret[COL_RIGHT * 3 + 1] = 1.0F;
1073 ret[COL_RIGHT * 3 + 2] = 1.0F;
1074
1075 ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 1.5F;
1076 ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 1.5F;
1077 ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 1.5F;
1078
1079 ret[COL_DIAG * 3 + 0] = ret[COL_GRID * 3 + 0];
1080 ret[COL_DIAG * 3 + 1] = ret[COL_GRID * 3 + 1];
1081 ret[COL_DIAG * 3 + 2] = ret[COL_GRID * 3 + 2];
1082
1083 ret[COL_HINT * 3 + 0] = 1.0F;
1084 ret[COL_HINT * 3 + 1] = 0.0F;
1085 ret[COL_HINT * 3 + 2] = 0.0F;
1086
1087 ret[COL_CURSOR * 3 + 0] = 0.8F;
1088 ret[COL_CURSOR * 3 + 1] = 0.0F;
1089 ret[COL_CURSOR * 3 + 2] = 0.0F;
1090
1091 *ncolours = NCOLOURS;
1092 return ret;
1093}
1094
1095static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1096{
1097 struct game_drawstate *ds = snew(struct game_drawstate);
1098 int i;
1099
1100 ds->started = false;
1101 ds->w = state->w;
1102 ds->h = state->h;
1103 ds->tiles = snewn(ds->w*ds->h, unsigned char);
1104 ds->tilesize = 0; /* haven't decided yet */
1105 for (i = 0; i < ds->w*ds->h; i++)
1106 ds->tiles[i] = -1;
1107
1108 return ds;
1109}
1110
1111static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1112{
1113 sfree(ds->tiles);
1114 sfree(ds);
1115}
1116
1117static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state,
1118 int x, int y, int tile, bool anim, float animtime)
1119{
1120 int w = ds->w, h = ds->h, wh = w * h;
1121 int bx = x * TILE_SIZE + BORDER, by = y * TILE_SIZE + BORDER;
1122 int i, j, dcol = (tile & 4) ? COL_CURSOR : COL_DIAG;
1123
1124 clip(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1);
1125
1126 draw_rect(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1,
1127 anim ? COL_BACKGROUND : tile & 1 ? COL_WRONG : COL_RIGHT);
1128 if (anim) {
1129 /*
1130 * Draw a polygon indicating that the square is diagonally
1131 * flipping over.
1132 */
1133 int coords[8], colour;
1134
1135 coords[0] = bx + TILE_SIZE;
1136 coords[1] = by;
1137 coords[2] = bx + (int)((float)TILE_SIZE * animtime);
1138 coords[3] = by + (int)((float)TILE_SIZE * animtime);
1139 coords[4] = bx;
1140 coords[5] = by + TILE_SIZE;
1141 coords[6] = bx + TILE_SIZE - (int)((float)TILE_SIZE * animtime);
1142 coords[7] = by + TILE_SIZE - (int)((float)TILE_SIZE * animtime);
1143
1144 colour = (tile & 1 ? COL_WRONG : COL_RIGHT);
1145 if (animtime < 0.5F)
1146 colour = COL_WRONG + COL_RIGHT - colour;
1147
1148 draw_polygon(dr, coords, 4, colour, COL_GRID);
1149 }
1150
1151 /*
1152 * Draw a little diagram in the tile which indicates which
1153 * surrounding tiles flip when this one is clicked.
1154 */
1155 for (i = 0; i < h; i++)
1156 for (j = 0; j < w; j++)
1157 if (state->matrix->matrix[(y*w+x)*wh + i*w+j]) {
1158 int ox = j - x, oy = i - y;
1159 int td = TILE_SIZE / 16 ? TILE_SIZE / 16 : 1;
1160 int cx = (bx + TILE_SIZE/2) + (2 * ox - 1) * td;
1161 int cy = (by + TILE_SIZE/2) + (2 * oy - 1) * td;
1162 if (ox == 0 && oy == 0)
1163 draw_rect(dr, cx, cy, 2*td+1, 2*td+1, dcol);
1164 else {
1165 draw_line(dr, cx, cy, cx+2*td, cy, dcol);
1166 draw_line(dr, cx, cy+2*td, cx+2*td, cy+2*td, dcol);
1167 draw_line(dr, cx, cy, cx, cy+2*td, dcol);
1168 draw_line(dr, cx+2*td, cy, cx+2*td, cy+2*td, dcol);
1169 }
1170 }
1171
1172 /*
1173 * Draw a hint rectangle if required.
1174 */
1175 if (tile & 2) {
1176 int x1 = bx + TILE_SIZE / 20, x2 = bx + TILE_SIZE - TILE_SIZE / 20;
1177 int y1 = by + TILE_SIZE / 20, y2 = by + TILE_SIZE - TILE_SIZE / 20;
1178 int i = 3;
1179 while (i--) {
1180 draw_line(dr, x1, y1, x2, y1, COL_HINT);
1181 draw_line(dr, x1, y2, x2, y2, COL_HINT);
1182 draw_line(dr, x1, y1, x1, y2, COL_HINT);
1183 draw_line(dr, x2, y1, x2, y2, COL_HINT);
1184 x1++, y1++, x2--, y2--;
1185 }
1186 }
1187
1188 unclip(dr);
1189
1190 draw_update(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1);
1191}
1192
1193static void game_redraw(drawing *dr, game_drawstate *ds,
1194 const game_state *oldstate, const game_state *state,
1195 int dir, const game_ui *ui,
1196 float animtime, float flashtime)
1197{
1198 int w = ds->w, h = ds->h, wh = w * h;
1199 int i, flashframe;
1200
1201 if (!ds->started) {
1202 /*
1203 * Draw the grid lines.
1204 */
1205 for (i = 0; i <= w; i++)
1206 draw_line(dr, i * TILE_SIZE + BORDER, BORDER,
1207 i * TILE_SIZE + BORDER, h * TILE_SIZE + BORDER,
1208 COL_GRID);
1209 for (i = 0; i <= h; i++)
1210 draw_line(dr, BORDER, i * TILE_SIZE + BORDER,
1211 w * TILE_SIZE + BORDER, i * TILE_SIZE + BORDER,
1212 COL_GRID);
1213
1214 draw_update(dr, 0, 0, TILE_SIZE * w + 2 * BORDER,
1215 TILE_SIZE * h + 2 * BORDER);
1216
1217 ds->started = true;
1218 }
1219
1220 if (flashtime)
1221 flashframe = (int)(flashtime / FLASH_FRAME);
1222 else
1223 flashframe = -1;
1224
1225 animtime /= ANIM_TIME; /* scale it so it goes from 0 to 1 */
1226
1227 for (i = 0; i < wh; i++) {
1228 int x = i % w, y = i / w;
1229 int fx, fy, fd;
1230 int v = state->grid[i];
1231 int vv;
1232
1233 if (flashframe >= 0) {
1234 fx = (w+1)/2 - min(x+1, w-x);
1235 fy = (h+1)/2 - min(y+1, h-y);
1236 fd = max(fx, fy);
1237 if (fd == flashframe)
1238 v |= 1;
1239 else if (fd == flashframe - 1)
1240 v &= ~1;
1241 }
1242
1243 if (!state->hints_active)
1244 v &= ~2;
1245 if (ui->cdraw && ui->cx == x && ui->cy == y)
1246 v |= 4;
1247
1248 if (oldstate && ((state->grid[i] ^ oldstate->grid[i]) &~ 2))
1249 vv = 255; /* means `animated' */
1250 else
1251 vv = v;
1252
1253 if (ds->tiles[i] == 255 || vv == 255 || ds->tiles[i] != vv) {
1254 draw_tile(dr, ds, state, x, y, v, vv == 255, animtime);
1255 ds->tiles[i] = vv;
1256 }
1257 }
1258
1259 {
1260 char buf[256];
1261
1262 sprintf(buf, "%sMoves: %d",
1263 (state->completed ?
1264 (state->cheated ? "Auto-solved. " : "COMPLETED! ") :
1265 (state->cheated ? "Auto-solver used. " : "")),
1266 state->moves);
1267
1268 status_bar(dr, buf);
1269 }
1270}
1271
1272static float game_anim_length(const game_state *oldstate,
1273 const game_state *newstate, int dir, game_ui *ui)
1274{
1275 return ANIM_TIME;
1276}
1277
1278static float game_flash_length(const game_state *oldstate,
1279 const game_state *newstate, int dir, game_ui *ui)
1280{
1281 if (!oldstate->completed && newstate->completed)
1282 return FLASH_FRAME * (max((newstate->w+1)/2, (newstate->h+1)/2)+1);
1283
1284 return 0.0F;
1285}
1286
1287static void game_get_cursor_location(const game_ui *ui,
1288 const game_drawstate *ds,
1289 const game_state *state,
1290 const game_params *params,
1291 int *x, int *y, int *w, int *h)
1292{
1293 if(ui->cdraw)
1294 {
1295 *x = COORD(ui->cx);
1296 *y = COORD(ui->cy);
1297 *w = *h = TILE_SIZE;
1298 }
1299}
1300
1301static int game_status(const game_state *state)
1302{
1303 return state->completed ? +1 : 0;
1304}
1305
1306#ifdef COMBINED
1307#define thegame flip
1308#endif
1309
1310const struct game thegame = {
1311 "Flip", "games.flip", "flip",
1312 default_params,
1313 game_fetch_preset, NULL,
1314 decode_params,
1315 encode_params,
1316 free_params,
1317 dup_params,
1318 true, game_configure, custom_params,
1319 validate_params,
1320 new_game_desc,
1321 validate_desc,
1322 new_game,
1323 dup_game,
1324 free_game,
1325 true, solve_game,
1326 true, game_can_format_as_text_now, game_text_format,
1327 NULL, NULL, /* get_prefs, set_prefs */
1328 new_ui,
1329 free_ui,
1330 NULL, /* encode_ui */
1331 NULL, /* decode_ui */
1332 NULL, /* game_request_keys */
1333 game_changed_state,
1334 current_key_label,
1335 interpret_move,
1336 execute_move,
1337 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1338 game_colours,
1339 game_new_drawstate,
1340 game_free_drawstate,
1341 game_redraw,
1342 game_anim_length,
1343 game_flash_length,
1344 game_get_cursor_location,
1345 game_status,
1346 false, false, NULL, NULL, /* print_size, print */
1347 true, /* wants_statusbar */
1348 false, NULL, /* timing_state */
1349 0, /* flags */
1350};