diff options
author | Franklin Wei <frankhwei536@gmail.com> | 2016-11-20 15:16:41 -0500 |
---|---|---|
committer | Franklin Wei <me@fwei.tk> | 2016-12-18 18:13:22 +0100 |
commit | 1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99 (patch) | |
tree | 8e7f2d6b0cbdb5d15c13457b2c3e1de69f598440 /apps/plugins/puzzles/combi.c | |
parent | 3ee79724f6fb033d50e26ef37b33d3f8cedf0c5b (diff) | |
download | rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.tar.gz rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.zip |
Port of Simon Tatham's Puzzle Collection
Original revision: 5123b1bf68777ffa86e651f178046b26a87cf2d9
MIT Licensed. Some games still crash and others are unplayable due to
issues with controls. Still need a "real" polygon filling algorithm.
Currently builds one plugin per puzzle (about 40 in total, around 100K
each on ARM), but can easily be made to build a single monolithic
overlay (800K or so on ARM).
The following games are at least partially broken for various reasons,
and have been disabled on this commit:
Cube: failed assertion with "Icosahedron" setting
Keen: input issues
Mines: weird stuff happens on target
Palisade: input issues
Solo: input issues, occasional crash on target
Towers: input issues
Undead: input issues
Unequal: input and drawing issues (concave polys)
Untangle: input issues
Features left to do:
- In-game help system
- Figure out the weird bugs
Change-Id: I7c69b6860ab115f973c8d76799502e9bb3d52368
Diffstat (limited to 'apps/plugins/puzzles/combi.c')
-rw-r--r-- | apps/plugins/puzzles/combi.c | 110 |
1 files changed, 110 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/combi.c b/apps/plugins/puzzles/combi.c new file mode 100644 index 0000000000..d39e298405 --- /dev/null +++ b/apps/plugins/puzzles/combi.c | |||
@@ -0,0 +1,110 @@ | |||
1 | #include "rbassert.h" | ||
2 | #include <string.h> | ||
3 | |||
4 | #include "puzzles.h" | ||
5 | |||
6 | /* horrific and doesn't check overflow. */ | ||
7 | static long factx(long x, long y) | ||
8 | { | ||
9 | long acc = 1, i; | ||
10 | |||
11 | for (i = y; i <= x; i++) | ||
12 | acc *= i; | ||
13 | return acc; | ||
14 | } | ||
15 | |||
16 | void reset_combi(combi_ctx *combi) | ||
17 | { | ||
18 | int i; | ||
19 | combi->nleft = combi->total; | ||
20 | for (i = 0; i < combi->r; i++) | ||
21 | combi->a[i] = i; | ||
22 | } | ||
23 | |||
24 | combi_ctx *new_combi(int r, int n) | ||
25 | { | ||
26 | long nfr, nrf; | ||
27 | combi_ctx *combi; | ||
28 | |||
29 | assert(r <= n); | ||
30 | assert(n >= 1); | ||
31 | |||
32 | combi = snew(combi_ctx); | ||
33 | memset(combi, 0, sizeof(combi_ctx)); | ||
34 | combi->r = r; | ||
35 | combi->n = n; | ||
36 | |||
37 | combi->a = snewn(r, int); | ||
38 | memset(combi->a, 0, r * sizeof(int)); | ||
39 | |||
40 | nfr = factx(n, r+1); | ||
41 | nrf = factx(n-r, 1); | ||
42 | combi->total = (int)(nfr / nrf); | ||
43 | |||
44 | reset_combi(combi); | ||
45 | return combi; | ||
46 | } | ||
47 | |||
48 | /* returns NULL when we're done otherwise returns input. */ | ||
49 | combi_ctx *next_combi(combi_ctx *combi) | ||
50 | { | ||
51 | int i = combi->r - 1, j; | ||
52 | |||
53 | if (combi->nleft == combi->total) | ||
54 | goto done; | ||
55 | else if (combi->nleft <= 0) | ||
56 | return NULL; | ||
57 | |||
58 | while (combi->a[i] == combi->n - combi->r + i) | ||
59 | i--; | ||
60 | combi->a[i] += 1; | ||
61 | for (j = i+1; j < combi->r; j++) | ||
62 | combi->a[j] = combi->a[i] + j - i; | ||
63 | |||
64 | done: | ||
65 | combi->nleft--; | ||
66 | return combi; | ||
67 | } | ||
68 | |||
69 | void free_combi(combi_ctx *combi) | ||
70 | { | ||
71 | sfree(combi->a); | ||
72 | sfree(combi); | ||
73 | } | ||
74 | |||
75 | /* compile this with: | ||
76 | * gcc -o combi.exe -DSTANDALONE_COMBI_TEST combi.c malloc.c | ||
77 | */ | ||
78 | #ifdef STANDALONE_COMBI_TEST | ||
79 | |||
80 | #include <stdio.h> | ||
81 | |||
82 | void fatal(char *fmt, ...) | ||
83 | { | ||
84 | abort(); | ||
85 | } | ||
86 | |||
87 | int main(int argc, char *argv[]) | ||
88 | { | ||
89 | combi_ctx *c; | ||
90 | int i, r, n; | ||
91 | |||
92 | if (argc < 3) { | ||
93 | fprintf(stderr, "Usage: combi R N\n"); | ||
94 | exit(1); | ||
95 | } | ||
96 | |||
97 | r = atoi(argv[1]); n = atoi(argv[2]); | ||
98 | c = new_combi(r, n); | ||
99 | printf("combi %d of %d, %d elements.\n", c->r, c->n, c->total); | ||
100 | |||
101 | while (next_combi(c)) { | ||
102 | for (i = 0; i < c->r; i++) { | ||
103 | printf("%d ", c->a[i]); | ||
104 | } | ||
105 | printf("\n"); | ||
106 | } | ||
107 | free_combi(c); | ||
108 | } | ||
109 | |||
110 | #endif | ||