Write a program for finding expressions built out of given numbers and using given operators that evaluate...
arithmetic/digits/equations/find
Problem
Write a program for finding expressions built out of given numbers and using given operators that evaluate to a given value, or listing all possible values.
Show solution
There are five different kinds of binary trees with
exactly four leaf nodes. The program tries all four operators in each
place, and all four values in each of the leaves, guaranteeing that each
is used only once... a fairly quick operation. A small extract from
'numop 8 8 3 3 1' shows the five different shapes of trees:
1.0 = ((3 * 8) / 3) / 8
1.0 = (3 * (8 / 3)) / 8
1.0 = (3 - 3) + (8 / 8)
1.0 = 3 * ((8 / 3) / 8)
1.0 = 3 * (8 / (3 * 8))
Probably FUDGE ought to be set a little lower, for more confidence that
the equality isn't fortuitous. Extensions to other binary operators are
obvious; unary operators and more values are not. For a more general
problem I'd go recursive, use exact rational arithmetic, and have a fine
old time.
Enjoy...
Jim Gillogly <uunet!rand.org!James_Gillogly>
21 Wedmath S.R. 1993, 10:58
----------------------------------------------------------------
/* numop: using elementary operations on 4 numbers, find a
* desired result; e.g. 24.
*
* Don't worry about symmetries resulting in multiple correct answers.
*
* 11 Aug 93, SCRYER
*
* Added some C++.
* Added permutation of arguments.
* Added three ways to call the routine:
* numop a b c d e: print all the ways that a b c d can be combined to form e
* numop a b c d: print all the values that a b c d can form
* numop n m: print the lowest unreachable value > 0 <= m with 4 digits > 0 <= n
* 12 Nov 2002, Chris Cole
*/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define MUL 0
#define DIV 1
#define ADD 2
#define SUB 3
#define FUDGE 0.01
double val[4] = { 8, 8, 3, 3 };
int divzero;
bool verbose;
char
nameop (int op)
{
switch (op) {
case MUL:
return '*';
case DIV:
return '/';
case ADD:
return '+';
case SUB:
return '-';
}
return '?';
}
double
eval (int op, double val1, double val2)
{
switch (op) {
case MUL:
return val1 * val2;
case DIV:
if (val2 == 0.) {
divzero = 1;
#ifdef EXTREMELYVERBOSE
fprintf (stderr, "Division by zero.\n");
#endif
}
return val2 == 0. ? 0. : val1 / val2;
case ADD:
return val1 + val2;
case SUB:
return val1 - val2;
}
return 0.;
}
int
numop (int t)
{
int op1, op2, op3;
int iv1, iv2, iv3, iv4;
int used[4];
int i;
double target;
double e1, e2, e3;
int winner;
target = t;
winner = 0;
for (i = 0; i < 4; i++)
used[i] = 0;
for (op1 = 0; op1 < 4; op1++)
for (op2 = 0; op2 < 4; op2++)
for (op3 = 0; op3 < 4; op3++)
for (iv1 = 0; iv1 < 4; iv1++) {
used[iv1] = 1;
for (iv2 = 0; iv2 < 4; iv2++) {
if (used[iv2])
continue;
used[iv2] = 1;
for (iv3 = 0; iv3 < 4; iv3++) {
if (used[iv3])
continue;
used[iv3] = 1;
for (iv4 = 0; iv4 < 4; iv4++) {
if (used[iv4])
continue;
/* Case 1 */
divzero = 0;
e3 = eval (op3, val[iv3], val[iv4]);
e2 = eval (op2, val[iv1], val[iv2]);
e1 = eval (op1, e2, e3); /* (u + v) * (w - x) */
if (target == 0 || fabs (e1 - target) < FUDGE && !divzero)
if (verbose)
printf ("%.1f = (%.0f %c %.0f) %c (%.0f %c %.0f)\n",
e1, val[iv1], nameop (op2), val[iv2],
nameop (op1), val[iv3], nameop (op3), val[iv4]);
else winner = 1;
/* Case 2 */
divzero = 0;
e3 = eval (op3, val[iv1], val[iv2]);
e2 = eval (op2, e3, val[iv3]);
e1 = eval (op1, e2, val[iv4]); /* ((u + v) * w) - x */
if (target == 0 || fabs (e1 - target) < FUDGE && !divzero)
if (verbose)
printf ("%.1f = ((%.0f %c %.0f) %c %.0f) %c %.0f\n",
e1, val[iv1], nameop (op3), val[iv2],
nameop (op2), val[iv3], nameop (op1), val[iv4]);
else winner = 2;
/* Case 3 */
divzero = 0;
e3 = eval (op3, val[iv2], val[iv3]);
e2 = eval (op2, val[iv1], e3);
e1 = eval (op1, e2, val[iv4]); /* (u + (v * w)) - x */
if (target == 0 || fabs (e1 - target) < FUDGE && !divzero)
if (verbose)
printf ("%.1f = (%.0f %c (%.0f %c %.0f)) %c %.0f\n",
e1, val[iv1], nameop (op2), val[iv2],
nameop (op3), val[iv3], nameop (op1), val[iv4]);
else winner = 3;
/* Case 4 */
divzero = 0;
e3 = eval (op3, val[iv2], val[iv3]);
e2 = eval (op2, e3, val[iv4]);
e1 = eval (op1, val[iv1], e2); /* u + ((v * w) - x) */
if (target == 0 || fabs (e1 - target) < FUDGE && !divzero)
if (verbose)
printf ("%.1f = %.0f %c ((%.0f %c %.0f) %c %.0f)\n",
e1, val[iv1], nameop (op1), val[iv2],
nameop (op3), val[iv3], nameop (op2), val[iv4]);
else winner = 4;
/* Case 5 *//* u + (v * (w - x)) */
divzero = 0;
e3 = eval (op3, val[iv3], val[iv4]);
e2 = eval (op2, val[iv2], e3);
e1 = eval (op1, val[iv1], e2);
if (target == 0 || fabs (e1 - target) < FUDGE && !divzero)
if (verbose)
printf ("%.1f = %.0f %c (%.0f %c (%.0f %c %.0f))\n",
e1, val[iv1], nameop (op1), val[iv2],
nameop (op2), val[iv3], nameop (op3), val[iv4]);
else winner = 5;
}
used[iv3] = 0;
}
used[iv2] = 0;
}
used[iv1] = 0;
}
return winner;
}
int failed;
void
check_perms (int target, int m, int n)
{
int i = m, j;
double t;
if (i < n)
for (; i < n; ++i) {
for (check_perms (target, m + 1, n), t = val[j = m]; j < n; ++j)
val[j] = val[j + 1];
val[j - 1] = t;
}
else if (!numop (target))
failed = target;
}
main (int argc, char *argv[])
{
int target;
if (argc == 3) {
for (val[0] = 0; val[0] <= atof(argv[1]); ++val[0])
for (val[1] = val[0]; val[1] <= atof(argv[1]); ++val[1])
for (val[2] = val[1]; val[2] <= atof(argv[1]); ++val[2])
for (val[3] = val[2]; val[3] <= atof(argv[1]); ++val[3]) {
failed = 0;
for (target = 1; target <= atoi(argv[2]) && !failed; ++target)
check_perms (target, 0, 4);
if (!failed)
cout << val[0] << val[1] << val[2] << val[3] << endl;
else
cout << "fail " << val[0] << val[1] << val[2] << val[3] <<
" at " << failed << endl;
}
} else if (argc == 5) {
val[0] = atof (argv[1]);
val[1] = atof (argv[2]);
val[2] = atof (argv[3]);
val[3] = atof (argv[4]);
verbose = true;
check_perms(0, 0, 0);
} else if (argc == 6) {
val[0] = atof (argv[1]);
val[1] = atof (argv[2]);
val[2] = atof (argv[3]);
val[3] = atof (argv[4]);
target = atoi(argv[5]);
verbose = true;
check_perms(target, 0, 0);
} else {
fprintf (stderr,
"Usage: %s <max_val> <max_target>\n", argv[0]);
fprintf (stderr,
"Usage: %s <val1> <val1> <val3> <val4>\n", argv[0]);
fprintf (stderr,
"Usage: %s <val1> <val1> <val3> <val4> <target>\n", argv[0]);
return 1;
}
return 0;
}
----------------------------------------------------------------------------
Here is the output of "numop 9 100"
fail 0000 at 1
fail 0001 at 2
fail 0002 at 1
fail 0003 at 1
fail 0004 at 1
fail 0005 at 1
fail 0006 at 1
fail 0007 at 1
fail 0008 at 1
fail 0009 at 1
fail 0011 at 3
fail 0012 at 4
fail 0013 at 5
fail 0014 at 2
fail 0015 at 2
fail 0016 at 2
fail 0017 at 2
fail 0018 at 2
fail 0019 at 2
fail 0022 at 3
fail 0023 at 4
fail 0024 at 1
fail 0025 at 1
fail 0026 at 1
fail 0027 at 1
fail 0028 at 1
fail 0029 at 1
fail 0033 at 2
fail 0034 at 2
fail 0035 at 1
fail 0036 at 1
fail 0037 at 1
fail 0038 at 1
fail 0039 at 1
fail 0044 at 2
fail 0045 at 2
fail 0046 at 1
fail 0047 at 1
fail 0048 at 1
fail 0049 at 1
fail 0055 at 2
fail 0056 at 2
fail 0057 at 1
fail 0058 at 1
fail 0059 at 1
fail 0066 at 2
fail 0067 at 2
fail 0068 at 1
fail 0069 at 1
fail 0077 at 2
fail 0078 at 2
fail 0079 at 1
fail 0088 at 2
fail 0089 at 2
fail 0099 at 2
fail 0111 at 4
fail 0112 at 5
fail 0113 at 7
fail 0114 at 7
fail 0115 at 8
fail 0116 at 9
fail 0117 at 3
fail 0118 at 3
fail 0119 at 3
fail 0122 at 7
fail 0123 at 10
fail 0124 at 11
fail 0125 at 13
fail 0126 at 15
fail 0127 at 11
fail 0128 at 12
fail 0129 at 13
fail 0133 at 11
fail 0134 at 10
fail 0135 at 11
fail 0136 at 11
fail 0137 at 12
fail 0138 at 13
fail 0139 at 14
fail 0144 at 6
fail 0145 at 7
fail 0146 at 8
fail 0147 at 9
fail 0148 at 6
fail 0149 at 7
fail 0155 at 3
fail 0156 at 3
fail 0157 at 9
fail 0158 at 10
fail 0159 at 7
fail 0166 at 3
fail 0167 at 3
fail 0168 at 4
fail 0169 at 11
fail 0177 at 3
fail 0178 at 3
fail 0179 at 4
fail 0188 at 3
fail 0189 at 3
fail 0199 at 3
fail 0222 at 5
fail 0223 at 9
fail 0224 at 7
fail 0225 at 11
fail 0226 at 9
fail 0227 at 13
fail 0228 at 11
fail 0229 at 3
fail 0233 at 10
fail 0234 at 13
fail 0235 at 12
fail 0236 at 10
fail 0237 at 16
fail 0238 at 15
fail 0239 at 13
fail 0244 at 5
fail 0245 at 15
fail 0246 at 9
fail 0247 at 12
fail 0248 at 3
fail 0249 at 12
fail 0255 at 4
fail 0256 at 14
fail 0257 at 8
fail 0258 at 12
fail 0259 at 15
fail 0266 at 5
fail 0267 at 16
fail 0268 at 9
fail 0269 at 10
fail 0277 at 4
fail 0278 at 12
fail 0279 at 3
fail 0288 at 5
fail 0289 at 12
fail 0299 at 4
fail 0333 at 5
fail 0334 at 8
fail 0335 at 7
fail 0336 at 4
fail 0337 at 5
fail 0338 at 4
fail 0339 at 5
fail 0344 at 6
fail 0345 at 10
fail 0346 at 11
fail 0347 at 2
fail 0348 at 10
fail 0349 at 11
fail 0355 at 6
fail 0356 at 16
fail 0357 at 11
fail 0358 at 12
fail 0359 at 10
fail 0366 at 5
fail 0367 at 8
fail 0368 at 7
fail 0369 at 4
fail 0377 at 5
fail 0378 at 6
fail 0379 at 8
fail 0388 at 6
fail 0389 at 7
fail 0399 at 5
fail 0444 at 6
fail 0445 at 2
fail 0446 at 3
fail 0447 at 2
fail 0448 at 5
fail 0449 at 2
fail 0455 at 2
fail 0456 at 8
fail 0457 at 10
fail 0458 at 6
fail 0459 at 2
fail 0466 at 7
fail 0467 at 8
fail 0468 at 1
fail 0469 at 8
fail 0477 at 2
fail 0478 at 6
fail 0479 at 1
fail 0488 at 7
fail 0489 at 6
fail 0499 at 2
fail 0555 at 3
fail 0556 at 2
fail 0557 at 4
fail 0558 at 4
fail 0559 at 2
fail 0566 at 2
fail 0567 at 9
fail 0568 at 4
fail 0569 at 7
fail 0577 at 3
fail 0578 at 9
fail 0579 at 1
fail 0588 at 2
fail 0589 at 7
fail 0599 at 2
fail 0666 at 3
fail 0667 at 2
fail 0668 at 5
fail 0669 at 5
fail 0677 at 2
fail 0678 at 3
fail 0679 at 5
fail 0688 at 3
fail 0689 at 4
fail 0699 at 2
fail 0777 at 3
fail 0778 at 2
fail 0779 at 3
fail 0788 at 2
fail 0789 at 3
fail 0799 at 3
fail 0888 at 3
fail 0889 at 2
fail 0899 at 2
fail 0999 at 3
fail 1111 at 5
fail 1112 at 7
fail 1113 at 10
fail 1114 at 11
fail 1115 at 13
fail 1116 at 15
fail 1117 at 2
fail 1118 at 2
fail 1119 at 2
fail 1122 at 10
fail 1123 at 11
fail 1124 at 14
fail 1125 at 17
fail 1126 at 20
fail 1127 at 1
fail 1128 at 1
fail 1129 at 1
fail 1133 at 14
fail 1134 at 19
fail 1135 at 22
fail 1136 at 26
fail 1137 at 26
fail 1138 at 29
fail 1139 at 22
fail 1144 at 22
fail 1145 at 27
fail 1146 at 13
fail 1147 at 8
fail 1148 at 7
fail 1149 at 8
fail 1155 at 7
fail 1156 at 14
fail 1157 at 8
fail 1158 at 7
fail 1159 at 10
fail 1166 at 4
fail 1167 at 9
fail 1168 at 9
fail 1169 at 7
fail 1177 at 4
fail 1178 at 4
fail 1179 at 6
fail 1188 at 5
fail 1189 at 4
fail 1199 at 4
fail 1222 at 11
fail 1223 at 17
fail 1224 at 19
fail 1225 at 23
fail 1226 at 19
fail 1227 at 22
fail 1228 at 23
fail 1229 at 26
fail 1233 at 22
fail 1234 at 29
fail 1235 at 19
fail 1236 at 28
fail 1237 at 25
fail 1238 at 36
fail 1239 at 31
fail 1244 at 21
fail 1245 at 33
fail 1246 at 29
fail 1247 at 38
fail 1248 at 27
fail 1249 at 41
fail 1255 at 29
fail 1256 at 44
fail 1257 at 27
fail 1258 at 52
fail 1259 at 31
fail 1266 at 27
fail 1267 at 23
fail 1268 at 34
fail 1269 at 34
fail 1277 at 18
fail 1278 at 19
fail 1279 at 29
fail 1288 at 20
fail 1289 at 21
fail 1299 at 22
fail 1333 at 14
fail 1334 at 17
fail 1335 at 20
fail 1336 at 23
fail 1337 at 26
fail 1338 at 31
fail 1339 at 13
fail 1344 at 22
fail 1345 at 25
fail 1346 at 34
fail 1347 at 11
fail 1348 at 18
fail 1349 at 19
fail 1355 at 18
fail 1356 at 25
fail 1357 at 18
fail 1358 at 31
fail 1359 at 26
fail 1366 at 20
fail 1367 at 29
fail 1368 at 34
fail 1369 at 14
fail 1377 at 8
fail 1378 at 7
fail 1379 at 16
fail 1388 at 7
fail 1389 at 8
fail 1399 at 8
fail 1444 at 7
fail 1445 at 18
fail 1446 at 17
fail 1447 at 4
fail 1448 at 11
fail 1449 at 4
fail 1455 at 12
fail 1456 at 17
fail 1457 at 11
fail 1458 at 14
fail 1459 at 13
fail 1466 at 20
fail 1467 at 20
fail 1468 at 21
fail 1469 at 22
fail 1477 at 7
fail 1478 at 1
fail 1479 at 17
fail 1488 at 22
fail 1489 at 1
fail 1499 at 9
fail 1555 at 8
fail 1556 at 9
fail 1557 at 20
fail 1558 at 5
fail 1559 at 5
fail 1566 at 13
fail 1567 at 16
fail 1568 at 13
fail 1569 at 5
fail 1577 at 11
fail 1578 at 1
fail 1579 at 13
fail 1588 at 8
fail 1589 at 8
fail 1599 at 8
fail 1666 at 9
fail 1667 at 10
fail 1668 at 15
fail 1669 at 6
fail 1677 at 10
fail 1678 at 11
fail 1679 at 1
fail 1688 at 13
fail 1689 at 1
fail 1699 at 9
fail 1777 at 4
fail 1778 at 3
fail 1779 at 17
fail 1788 at 3
fail 1789 at 13
fail 1799 at 13
fail 1888 at 5
fail 1889 at 3
fail 1899 at 3
fail 1999 at 4
fail 2222 at 7
fail 2223 at 13
fail 2224 at 11
fail 2225 at 17
fail 2226 at 15
fail 2227 at 17
fail 2228 at 13
fail 2229 at 21
fail 2233 at 19
fail 2234 at 17
fail 2235 at 21
fail 2236 at 23
fail 2237 at 23
fail 2238 at 31
fail 2239 at 29
fail 2244 at 11
fail 2245 at 23
fail 2246 at 17
fail 2247 at 25
fail 2248 at 19
fail 2249 at 23
fail 2255 at 23
fail 2256 at 23
fail 2257 at 10
fail 2258 at 29
fail 2259 at 20
fail 2266 at 21
fail 2267 at 25
fail 2268 at 17
fail 2269 at 27
fail 2277 at 20
fail 2278 at 17
fail 2279 at 14
fail 2288 at 19
fail 2289 at 19
fail 2299 at 12
fail 2333 at 13
fail 2334 at 24
fail 2335 at 25
fail 2336 at 26
fail 2337 at 29
fail 2338 at 38
fail 2339 at 14
fail 2344 at 23
fail 2345 at 32
fail 2346 at 27
fail 2347 at 36
fail 2348 at 25
fail 2349 at 34
fail 2355 at 27
fail 2356 at 38
fail 2357 at 26
fail 2358 at 26
fail 2359 at 23
fail 2366 at 23
fail 2367 at 34
fail 2368 at 11
fail 2369 at 32
fail 2377 at 29
fail 2378 at 22
fail 2379 at 25
fail 2388 at 23
fail 2389 at 34
fail 2399 at 11
fail 2444 at 11
fail 2445 at 25
fail 2446 at 15
fail 2447 at 27
fail 2448 at 13
fail 2449 at 29
fail 2455 at 21
fail 2456 at 29
fail 2457 at 22
fail 2458 at 23
fail 2459 at 25
fail 2466 at 17
fail 2467 at 37
fail 2468 at 17
fail 2469 at 19
fail 2477 at 34
fail 2478 at 25
fail 2479 at 26
fail 2488 at 11
fail 2489 at 27
fail 2499 at 15
fail 2555 at 14
fail 2556 at 19
fail 2557 at 18
fail 2558 at 22
fail 2559 at 31
fail 2566 at 20
fail 2567 at 17
fail 2568 at 13
fail 2569 at 28
fail 2577 at 20
fail 2578 at 21
fail 2579 at 11
fail 2588 at 25
fail 2589 at 13
fail 2599 at 20
fail 2666 at 17
fail 2667 at 23
fail 2668 at 19
fail 2669 at 13
fail 2677 at 24
fail 2678 at 30
fail 2679 at 22
fail 2688 at 17
fail 2689 at 17
fail 2699 at 16
fail 2777 at 11
fail 2778 at 19
fail 2779 at 13
fail 2788 at 26
fail 2789 at 23
fail 2799 at 18
fail 2888 at 13
fail 2889 at 22
fail 2899 at 21
fail 2999 at 13
fail 3333 at 11
fail 3334 at 17
fail 3335 at 19
fail 3336 at 13
fail 3337 at 17
fail 3338 at 13
fail 3339 at 14
fail 3344 at 18
fail 3345 at 13
fail 3346 at 29
fail 3347 at 23
fail 3348 at 14
fail 3349 at 17
fail 3355 at 14
fail 3356 at 19
fail 3357 at 14
fail 3358 at 11
fail 3359 at 17
fail 3366 at 14
fail 3367 at 26
fail 3368 at 16
fail 3369 at 13
fail 3377 at 4
fail 3378 at 11
fail 3379 at 19
fail 3388 at 11
fail 3389 at 13
fail 3399 at 14
fail 3444 at 10
fail 3445 at 22
fail 3446 at 29
fail 3447 at 30
fail 3448 at 15
fail 3449 at 31
fail 3455 at 21
fail 3456 at 43
fail 3457 at 7
fail 3458 at 18
fail 3459 at 9
fail 3466 at 17
fail 3467 at 24
fail 3468 at 17
fail 3469 at 19
fail 3477 at 5
fail 3478 at 18
fail 3479 at 13
fail 3488 at 24
fail 3489 at 22
fail 3499 at 5
fail 3555 at 11
fail 3556 at 11
fail 3557 at 12
fail 3558 at 13
fail 3559 at 14
fail 3566 at 11
fail 3567 at 13
fail 3568 at 8
fail 3569 at 20
fail 3577 at 4
fail 3578 at 21
fail 3579 at 28
fail 3588 at 6
fail 3589 at 11
fail 3599 at 4
fail 3666 at 7
fail 3667 at 6
fail 3668 at 13
fail 3669 at 10
fail 3677 at 13
fail 3678 at 14
fail 3679 at 22
fail 3688 at 5
fail 3689 at 32
fail 3699 at 22
fail 3777 at 8
fail 3778 at 1
fail 3779 at 10
fail 3788 at 1
fail 3789 at 15
fail 3799 at 16
fail 3888 at 7
fail 3889 at 1
fail 3899 at 1
fail 3999 at 8
fail 4444 at 10
fail 4445 at 13
fail 4446 at 13
fail 4447 at 1
fail 4448 at 15
fail 4449 at 1
fail 4455 at 3
fail 4456 at 21
fail 4457 at 15
fail 4458 at 17
fail 4459 at 10
fail 4466 at 19
fail 4467 at 11
fail 4468 at 17
fail 4469 at 20
fail 4477 at 3
fail 4478 at 11
fail 4479 at 11
fail 4488 at 13
fail 4489 at 13
fail 4499 at 3
fail 4555 at 7
fail 4556 at 13
fail 4557 at 5
fail 4558 at 9
fail 4559 at 7
fail 4566 at 31
fail 4567 at 30
fail 4568 at 25
fail 4569 at 9
fail 4577 at 3
fail 4578 at 18
fail 4579 at 5
fail 4588 at 13
fail 4589 at 5
fail 4599 at 3
fail 4666 at 7
fail 4667 at 6
fail 4668 at 15
fail 4669 at 11
fail 4677 at 8
fail 4678 at 7
fail 4679 at 15
fail 4688 at 13
fail 4689 at 31
fail 4699 at 5
fail 4777 at 1
fail 4778 at 6
fail 4779 at 7
fail 4788 at 8
fail 4789 at 7
fail 4799 at 8
fail 4888 at 7
fail 4889 at 8
fail 4899 at 7
fail 4999 at 1
fail 5555 at 8
fail 5556 at 13
fail 5557 at 4
fail 5558 at 1
fail 5559 at 1
fail 5566 at 3
fail 5567 at 19
fail 5568 at 16
fail 5569 at 1
fail 5577 at 8
fail 5578 at 12
fail 5579 at 4
fail 5588 at 3
fail 5589 at 4
fail 5599 at 3
fail 5666 at 8
fail 5667 at 15
fail 5668 at 6
fail 5669 at 6
fail 5677 at 17
fail 5678 at 8
fail 5679 at 23
fail 5688 at 3
fail 5689 at 15
fail 5699 at 4
fail 5777 at 8
fail 5778 at 7
fail 5779 at 7
fail 5788 at 6
fail 5789 at 8
fail 5799 at 10
fail 5888 at 1
fail 5889 at 1
fail 5899 at 1
fail 5999 at 1
fail 6666 at 9
fail 6667 at 3
fail 6668 at 5
fail 6669 at 1
fail 6677 at 3
fail 6678 at 9
fail 6679 at 8
fail 6688 at 3
fail 6689 at 7
fail 6699 at 8
fail 6777 at 9
fail 6778 at 4
fail 6779 at 7
fail 6788 at 5
fail 6789 at 6
fail 6799 at 8
fail 6888 at 9
fail 6889 at 8
fail 6899 at 7
fail 6999 at 1
fail 7777 at 4
fail 7778 at 3
fail 7779 at 4
fail 7788 at 3
fail 7789 at 4
fail 7799 at 3
fail 7888 at 3
fail 7889 at 5
fail 7899 at 4
fail 7999 at 4
fail 8888 at 5
fail 8889 at 3
fail 8899 at 3
fail 8999 at 3
fail 9999 at 4