aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-08-17 18:30:08 -0600
committerJack Sangdahl <[email protected]>2025-08-17 18:30:08 -0600
commit6c5db50fce3a14a2205e7d927c8adaf829aa6280 (patch)
treef768527878f85565a3670dbe4f85082255edf6e7
parent5d449e06b0ccf99ad3d10e2ed2c37e6e902bab1c (diff)
downloadleetcode-6c5db50fce3a14a2205e7d927c8adaf829aa6280.tar.gz
leetcode-6c5db50fce3a14a2205e7d927c8adaf829aa6280.zip
679. 24 game
-rw-r--r--24_game.c133
1 files changed, 44 insertions, 89 deletions
diff --git a/24_game.c b/24_game.c
index 9d38dc5..03f6cd3 100644
--- a/24_game.c
+++ b/24_game.c
@@ -15,100 +15,55 @@
* otherwise.
*/
-float calculate(float n1, float n2, char operand) {
- switch (operand) {
- case '+':
- return n1 + n2;
- case '-':
- return n1 - n2;
- case '*':
- return n1 * n2;
- case '/':
- if (!n2)
- return -1;
- return n1 / n2;
- }
- return 0;
-}
+#define EPSILON 0.00000001
-bool judgePoint24(int *cards, int cardsSize) {
- int i, j, k, l;
- int x, y, z;
- int t;
- int opersSize = 4;
- int sum = 6;
- float cal[3];
- int sign[3];
- float ans;
- char oper[4] = {'+', '-', '*', '/'};
- for (i = 0; i < cardsSize; i++)
- for (j = 0; j < cardsSize; j++) {
- if (j == i)
- continue;
- for (k = 0; k < cardsSize; k++) {
- if (k == i || k == j)
- continue;
- l = sum - (i + j + k);
- for (x = 0; x < opersSize; x++) {
- sign[0] = 0;
- if (x <= 1)
- sign[0] = 1;
- for (y = 0; y < opersSize; y++) {
- sign[1] = 0;
- if (y <= 1)
- sign[1] = 1;
- for (z = 0; z < opersSize; z++) {
- sign[2] = 0;
- if (z <= 1)
- sign[2] = 1;
- if ((sign[0] ^ sign[1]) || (sign[0] ^ sign[2]) ||
- (sign[1] ^ sign[2])) {
- cal[0] = calculate(cards[i], cards[j], oper[x]);
- cal[1] = calculate(cal[0], cards[k], oper[y]);
- cal[2] = calculate(cal[1], cards[l], oper[z]);
- ans = cal[2] > 24 ? cal[2] - 24 : 24 - cal[2];
- if (ans < 0.0001)
- return true;
- cal[0] = calculate(cards[i], cards[j], oper[x]);
- cal[2] = calculate(cards[k], cards[l], oper[z]);
- cal[1] = calculate(cal[0], cal[2], oper[y]);
- ans = cal[1] > 24 ? cal[1] - 24 : 24 - cal[1];
- if (ans < 0.0001)
- return true;
- cal[1] = calculate(cards[j], cards[k], oper[y]);
- cal[0] = calculate(cards[i], cal[1], oper[x]);
- cal[2] = calculate(cal[0], cards[l], oper[z]);
- ans = cal[2] > 24 ? cal[2] - 24 : 24 - cal[2];
- if (ans < 0.0001)
- return true;
- cal[1] = calculate(cards[j], cards[k], oper[y]);
- cal[2] = calculate(cal[1], cards[l], oper[z]);
- cal[0] = calculate(cards[i], cal[2], oper[x]);
- ans = cal[0] > 24 ? cal[0] - 24 : 24 - cal[0];
- if (ans < 0.0001)
- return true;
- cal[2] = calculate(cards[k], cards[l], oper[z]);
- cal[1] = calculate(cards[j], cal[2], oper[y]);
- cal[0] = calculate(cards[i], cal[1], oper[x]);
- ans = cal[0] > 24 ? cal[0] - 24 : 24 - cal[0];
- if (ans < 0.0001)
- return true;
- } else {
- cal[0] = calculate(cards[i], cards[j], oper[x]);
- cal[1] = calculate(cal[0], cards[k], oper[y]);
- cal[2] = calculate(cal[1], cards[l], oper[z]);
- ans = cal[2] > 24 ? cal[2] - 24 : 24 - cal[2];
- if (ans < 0.0001)
- return true;
- }
- }
- }
- }
- }
+bool backtrack(double *cards, int cardsSize) {
+ if (cardsSize == 1)
+ return fabs(cards[0] - 24) < EPSILON;
+ double *new = NULL;
+ for (int i = 0; i + 1 < cardsSize; i++)
+ for (int j = 0; j < cardsSize; j++) {
+ int n = cardsSize - 1, newSize = 0;
+ new = (double *)calloc(sizeof(double), n);
+ for (int k = 0; k < cardsSize; k++)
+ if (k != i && k != j)
+ new[newSize++] = cards[k];
+ new[newSize++] = cards[i] + cards[j];
+ if (backtrack(new, newSize))
+ return true;
+ newSize--;
+ new[newSize++] = cards[i] - cards[j];
+ if (backtrack(new, newSize))
+ return true;
+ newSize--;
+ new[newSize++] = cards[j] - cards[i];
+ if (backtrack(new, newSize))
+ return true;
+ newSize--;
+ new[newSize++] = cards[i] * cards[j];
+ if (backtrack(new, newSize))
+ return true;
+ newSize--;
+ new[newSize++] = cards[i] / cards[j];
+ if (backtrack(new, newSize))
+ return true;
+ newSize--;
+ new[newSize++] = cards[j] / cards[i];
+ if (backtrack(new, newSize))
+ return true;
}
+ if (new)
+ free(new);
return false;
}
+bool judgePoint24(int *cards, int cardsSize) {
+ double *newCards = (double *)calloc(sizeof(double), cardsSize);
+ bool ans = backtrack(newCards, cardsSize);
+ free(newCards);
+ return ans;
+}
+
int main() {
int c1[] = {4, 1, 8, 7}, c2[] = {1, 2, 1, 2};
printf("%d\n", judgePoint24(c1, ARRAY_SIZE(c1))); // expect: 1