生成所有可能的10个字符的方程
生成所有可能的10个字符的方程
提问于 2023-03-02 20:42:20
内德尔是一个词变体，在这个变体中，答案不是单词，而是等式。游戏中输入的每个等式都必须是有效的。
例子：13³-1=2196，(1/1)²*8=8，(((3)))²=9
任务是生成并输出到一个.txt文件，每行一个等式，所有可能的10个字符方程都可以尽快回答游戏(特别是Maxi Nerdle) (注意，代码应该限制在100 as以内，以避免硬编码)。
Maxi Nerdle方程的可能符号是：
- 0，1，2，3，4，5，6，7，8，9，+，-，*，/，2，3，)，(，=
使一个方程成为游戏的可能答案的规则，除了数学上是正确的，还有：
- 没有前导零
- 没有唯一的零(例如，方程中不可能有
+0) - 没有顺序的运算符，也就是说，+，-，*，/不能彼此相邻(例如，
+++----1=1) - 方程的右边必须是一个非负整数。
- 操作必须是显式的，也就是说，
9(10-8)=18是无效的，例如，在9和( - 只能有一个
=符号
还请注意，交换性不适用。如果数字的顺序发生变化，则必须将其视为不同的方程。
预期输出
对于10个字符长方程与Maxi Nerdle符号，应该有2,177,017个方程式。可以查看这里 (这是用一个简单的Python脚本在1小时内生成的)。
评分
由于这是一个最快代码挑战，分数将基于运行它在我的计算机上所需的时间(Windows 10)。这是我的规格：
- Intel(R) Core(TM) i5-9300H CPU 2.40GHz
- 8GB内存，2667 MHz速度
请包括有关如何编译/运行代码的说明。
回答 1
Code Golf用户
回答已采纳
发布于 2023-03-03 21:36:49
C，在我的M1 MacBook Pro
上大约6.3秒
这是个开始。我认为这里还有更多的优化工作要做。
递归下降分析器 to @Henrik的全部功劳。我对它做了轻微的修改，使它可以在双倍而不是整数上操作，并计算出第二和第三次幂。
- 用
cc -O3 nerdle.c -o nerdle编译 - 以
time ./nerdle的身份运行。在当前目录中生成文件nerdle.txt。
在MacOS上，默认的cc是clang。-O3将运行时速度提高了4倍，超过了默认优化。这应该和gcc一起做得很好。
gen_*()函数递归地生成所有有效表达式。然后用递归下降解析器计算这些值，如果数学上正确，则输出。
我注意按照与NerdleMaxi.txt相同的顺序输出结果，因此它们可以很容易地用diff / cmp进行验证。
这段代码并不好看，而且可以从大量的除臭中获益。
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
char * expressionToParse;
FILE *fp;
char peek()
{
return *expressionToParse;
}
char get()
{
return *expressionToParse++;
}
double expression();
double number()
{
double result = get() - '0';
while (peek() >= '0' && peek() <= '9')
{
result = 10*result + get() - '0';
}
return result;
}
double factor()
{
if (peek() >= '0' && peek() <= '9')
return number();
else if (peek() == '(')
{
get(); // '('
double result = expression();
get(); // ')'
return result;
}
else if (peek() == '-')
{
get();
return -factor();
}
return 0; // error
}
double expon()
{
double result = factor();
while (peek() == 's' || peek() == 'c')
if (get() == 's')
result *= result;
else
result *= (result * result);
return result;
}
double term()
{
double result = expon();
while (peek() == '*' || peek() == '/')
if (get() == '*')
result *= expon();
else
result /= expon();
return result;
}
double expression()
{
double result = term();
while (peek() == '+' || peek() == '-')
if (get() == '+')
result += term();
else
result -= term();
return result;
}
static void gen_nz_digit(int level, int br_level, char * buf, int ndigits);
static void gen_digit(int level, int br_level, char * buf, int ndigits);
static inline void gen_oper(int level, int br_level, char * buf, int ndigits);
static inline void gen_squared(int level, int br_level, char * buf, int ndigits);
static inline void gen_cubed(int level, int br_level, char * buf, int ndigits);
static inline void gen_open(int level, int br_level, char * buf, int ndigits);
static inline void gen_close(int level, int br_level, char * buf, int ndigits);
static inline void gen_equals(int level, int br_level, char * buf, int ndigits);
static void
gen_nz_digit (int level, int br_level, char * buf, int ndigits)
{
int i;
if (level >= 8) {
return;
}
int next_level = level + 1;
for (i = 1; i < 10; i++) {
buf[level] = '0' + i;
gen_equals(next_level, br_level, buf, 0);
gen_digit(next_level, br_level, buf, 1);
gen_oper(next_level, br_level, buf, 0);
gen_squared(next_level, br_level, buf, 0);
gen_cubed(next_level, br_level, buf, 0);
if (br_level > 0) {
gen_close(next_level, br_level, buf, 0);
}
}
}
static void
gen_digit (int level, int br_level, char * buf, int ndigits)
{
int i;
if (level >= 8) {
return;
}
if (ndigits >= 4) {
return;
}
int next_level = level + 1;
for (i = 1; i < 10; i++) {
buf[level] = '0' + i;
gen_equals(next_level, br_level, buf, 0);
gen_digit(next_level, br_level, buf, ndigits + 1);
gen_oper(next_level, br_level, buf, 0);
gen_squared(level +1, br_level, buf, 0);
gen_cubed(next_level, br_level, buf, 0);
if (br_level > 0) {
gen_close(next_level, br_level, buf, 0);
}
}
buf[level] = '0';
gen_equals(next_level, br_level, buf, 0);
gen_digit(next_level, br_level, buf, ndigits + 1);
gen_oper(next_level, br_level, buf, 0);
gen_squared(level +1, br_level, buf, 0);
gen_cubed(next_level, br_level, buf, 0);
if (br_level > 0) {
gen_close(next_level, br_level, buf, 0);
}
}
static inline void
gen_oper (int level, int br_level, char * buf, int ndigits)
{
if (level >= 7) {
return ;
}
int next_level = level + 1;
buf[level] = '-';
gen_nz_digit(next_level, br_level, buf, 0);
gen_open(next_level, br_level, buf, 0);
buf[level] = '+';
gen_nz_digit(next_level, br_level, buf, 0);
gen_open(next_level, br_level, buf, 0);
buf[level] = '*';
gen_nz_digit(next_level, br_level, buf, 0);
gen_open(next_level, br_level, buf, 0);
buf[level] = '/';
gen_nz_digit(next_level, br_level, buf, 0);
gen_open(next_level, br_level, buf, 0);
}
static inline void
gen_squared (int level, int br_level, char * buf, int ndigits)
{
if (level >= 8) {
return;
}
int next_level = level + 1;
buf[level] = 's';
if (level >= 3) {
gen_equals(next_level, br_level, buf, 0);
}
gen_oper(next_level, br_level, buf, 0);
if (br_level > 0) {
gen_close(next_level, br_level, buf, 0);
}
}
static inline void
gen_cubed (int level, int br_level, char * buf, int ndigits)
{
if (level >= 8) {
return;
}
int next_level = level + 1;
buf[level] = 'c';
if (level >= 2) {
gen_equals(next_level, br_level, buf, 0);
}
gen_oper(next_level, br_level, buf, 0);
if (br_level > 0) {
gen_close(next_level, br_level, buf, 0);
}
}
static inline void
gen_open (int level, int br_level, char * buf, int ndigits)
{
if (level >= 7) {
return;
}
int next_level = level + 1;
buf[level] = '(';
br_level++;
gen_nz_digit(next_level, br_level, buf, 0);
gen_open(next_level, br_level, buf, 0);
}
static inline void
gen_close (int level, int br_level, char * buf, int ndigits)
{
if (level >= 8) {
return;
}
int next_level = level + 1;
buf[level] = ')';
br_level--;
gen_equals(next_level, br_level, buf, 0);
gen_oper(next_level, br_level, buf, 0);
gen_squared(next_level, br_level, buf, 0);
gen_cubed(next_level, br_level, buf, 0);
if (br_level > 0) {
gen_close(next_level, br_level, buf, 0);
}
}
static inline int
int_len (int n) {
if (n < 10) {
return 1;
} else if (n < 100) {
return 2;
} else if (n < 1000) {
return 3;
} else if (n < 10000) {
return 4;
} else if (n < 100000) {
return 5;
} else {
return 6;
}
}
static inline void
gen_equals (int level, int br_level, char * buf, int ndigits)
{
double result;
double int_part;
double frac_part;
if (br_level > 0) {
return;
}
buf[level] = '\0';
expressionToParse = buf;
result = expression();
frac_part = modf(result, &int_part);
if (frac_part == 0) {
int rhs = (int)int_part;
if (rhs >= 0) {
if (level + int_len(rhs) == 9) {
char out_str[20];
char *ptr = out_str;
char tmp_str[20];
strcpy(out_str, buf);
while (NULL != (ptr = strchr(ptr, 's'))) {
strcpy(tmp_str, ptr + 1);
sprintf(ptr, "²%s", tmp_str);
}
ptr = out_str;
while (NULL != (ptr = strchr(ptr, 'c'))) {
strcpy(tmp_str, ptr + 1);
sprintf(ptr, "³%s", tmp_str);
}
fprintf(fp, "%s=%d\n", out_str, rhs);
}
}
}
}
int
main (int argc, char ** argv)
{
fp = fopen("nerdle.txt", "w");
char buffer[20] = "";
gen_nz_digit(0, 0, buffer, 0);
gen_open(0, 0, buffer, 0);
fclose(fp);
}页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codegolf.stackexchange.com/questions/258710
复制相关文章
相似问题
腾讯云开发者
