编写一个程序来创建一个匹配输入集的公式匹配输出集

Question

我刚刚在StackOverflow上看到了一个对混淆C解释的解释。我发现这个比赛非常有趣，因为我学习新的C，而且每天都有新的编程知识。

一个有趣的一个是Explain 1-liner party of a US President from IOCCC 2013

正如你可以看到，该程序使用了一系列的模函数（即（整数）％4796％275％4）来散列的输入数，以形成两个输出中的一个数字。这个“散列”功能已经过测试并出现错误，以便对一组有限的输入正确工作。

我认为这将是一个伟大的事情，必须尽量减少程序的大小，以便您可以将一个结果映射到另一个。例如，当转换为数字并通过函数时，可以将{apple，生菜，胡萝卜，梨，桔子，芦笋}变为{1,0,0,1,1,0}，并且此函数所需的时间更少空间比完整的数据库搜索一个字符串，并确定其果实。

所以我的问题是......你如何去创建一个程序来蛮力堆叠的模函数，将适用于所有给定的输入集和输出集？

继续水果例如，可以将水果的前两个字母转换为一个数字，像这样： 苹果 - > AP - > 0x6170

所以列表变成{0x6170，0x6c65，0x6361，0x7065， 0x6f72，0x6173}

所以，你想生成功能，包括重复modulos的映射{0x6170，0x6c65，0x6361，0x7065，0x6f72，0x6173}到{1,0,0,1,1,0}

怎么会这样做呢？

Answer 1

有趣的挑战，但超越我的数学技能的方式。所以，这里是纯C蛮力实现:P

我没有一个数学证明，因此不能证明这总是找到一个解决方案，但它工作在您的输入。添加'水果''克林顿'和'蔬菜'“麦卡因”使它运行一段时间;加入“杏”会发出冲突！ （这是报道，但不说在哪里。注意类似项目 - 水果或冲突里面的冲突 - 实际上应该允许。我没有写代码，但它应该是相对简单的。 ）

要查看更长的序列，请添加“香蕉”。出于某种原因，这需要高达163,13,2。有趣的是，加入“金橘”（即将用完的水果）并不需要太长的时间，即使使用另一种“椰子”，也不需要太多时间。

实现注意事项：

您可以限制搜索到的最大输入2个字节的代码，因为mod功能将永远不会做较大的数字什么。为了一致性，这个C代码从测试所有1-mod值开始（尽管我没有发现任何有用的东西）。然后它测试2-mod值，最后测试3-mod值。如果它没有找到一个值，你可以扩展它来寻找4-mod和5-mod长序列，但是搜索时间将以对数形式增加（！）。

应该可以对超过2个值进行分类;这需要对代码进行很小的重写。我怀疑为所有人寻找比赛会花费更长的时间。

还应该可以返回其他“索引”，而不是0和1;正如我正在写这篇文章，其余的CPU正在努力工作在2和0。但似乎需要相当长的一段时间。

C实现，蛮力：

#include <stdio.h> 
#include <stdlib.h> 

int main (void) 
{ 
    char *fruits[] = { "apple", "pear", "orange"} ; //, "clinton" }; 
    char *veggies[] = { "lettuce", "carrot", "asparagus" }; // , "mccaine" }; 
    int num_f, num_v, found_match; 
    unsigned short *code[2], max_code = 0; 

    int i,j, mod_value1, mod_value2, mod_value3; 

    num_f = sizeof(fruits)/sizeof(fruits[0]); 
    num_v = sizeof(veggies)/sizeof(veggies[0]); 

    code[0] = malloc((num_f+num_v)*sizeof(short)); 
    code[1] = malloc((num_f+num_v)*sizeof(short)); 

    for (i=0; i<num_f; i++) 
    { 
    code[0][i] = (fruits[i][0]<<8)+fruits[i][1]; 
    code[1][i] = 1; 
    if (code[0][i] > max_code) 
     max_code = code[0][i]; 
    } 
    for (i=0; i<num_v; i++) 
    { 
    code[0][num_f+i] = (veggies[i][0]<<8)+veggies[i][1]; 
    code[1][num_f+i] = 0; 
    if (code[0][num_f+i] > max_code) 
     max_code = code[0][num_f+i]; 
    } 

    for (i=0; i<num_f+num_v; i++) 
    { 
    for (j=i+1; j<num_f+num_v; j++) 
    { 
     if (code[0][i] == code[0][j]) 
     { 
     printf ("clash!\n"); 
     exit(-1); 
     } 
    } 
    } 

    printf ("calculating...\n"); 
    for (mod_value1=1; mod_value1<max_code; mod_value1++) 
    { 
    found_match = 1; 
    for (i=0; i<num_f+num_v; i++) 
    { 
     if (code[0][i] % mod_value1 != code[1][i]) 
     { 
     found_match = 0; 
     break; 
     } 
    } 
    if (found_match) 
    { 
     printf ("mod %d should work\n", mod_value1); 
     break; 
    } 
    } 
    if (found_match) 
    { 
    for (i=0; i<num_f; i++) 
    { 
     printf ("%s -> %d\n", fruits[i], code[0][i] % mod_value2 % mod_value1); 
    } 
    for (i=0; i<num_v; i++) 
    { 
     printf ("%s -> %d\n", veggies[i], code[0][num_f+i] % mod_value2 % mod_value1); 
    } 
    } else 
    { 
    for (mod_value1=1; mod_value1<max_code; mod_value1++) 
    { 
    for (mod_value2=mod_value1+1; mod_value2<max_code; mod_value2++) 
    { 
     found_match = 1; 
     for (i=0; i<num_f+num_v; i++) 
     { 
     if (code[0][i] % mod_value2 % mod_value1 != code[1][i]) 
     { 
      found_match = 0; 
      break; 
     } 
     } 
     if (found_match) 
     { 
     printf ("mod %d mod %d should work\n", mod_value2, mod_value1); 
     break; 
     } 
    } 
    if (found_match) 
     break; 
    } 

    if (found_match) 
    { 
    for (i=0; i<num_f; i++) 
    { 
     printf ("%s -> %d\n", fruits[i], code[0][i] % mod_value2 % mod_value1); 
    } 
    for (i=0; i<num_v; i++) 
    { 
     printf ("%s -> %d\n", veggies[i], code[0][num_f+i] % mod_value2 % mod_value1); 
    } 
    } else 
    { 
    for (mod_value1=1; mod_value1<max_code; mod_value1++) 
    { 
     for (mod_value2=mod_value1+1; mod_value2<max_code; mod_value2++) 
     { 
     for (mod_value3=mod_value2+1; mod_value3<max_code; mod_value3++) 
     { 
      found_match = 1; 
      for (i=0; i<num_f+num_v; i++) 
      { 
      if (code[0][i] % mod_value3 % mod_value2 % mod_value1 != code[1][i]) 
      { 
       found_match = 0; 
       break; 
      } 
      } 
      if (found_match) 
      { 
      printf ("mod %d mod %d mod %d should work\n", mod_value3, mod_value2, mod_value1); 
      break; 
      } 
     } 
     if (found_match) 
      break; 
     } 
     if (found_match) 
     break; 
    } 

    if (found_match) 
    { 
     for (i=0; i<num_f; i++) 
     { 
     printf ("%s -> %d\n", fruits[i], code[0][i] % mod_value3 % mod_value2 % mod_value1); 
     } 
     for (i=0; i<num_v; i++) 
     { 
     printf ("%s -> %d\n", veggies[i], code[0][num_f+i] % mod_value3 % mod_value2 % mod_value1); 
     } 
    } 
    } 
    } 
    return 0; 
} 

结果为原来的3水果，3蔬菜列表：

mod 25 mod 2 should work 
apple -> 1 
pear -> 1 
orange -> 1 
lettuce -> 0 
carrot -> 0 
asparagus -> 0 

远期疗效，为2和0通缉输出：

mod 507 mod 8 mod 3 should work 
apple -> 2 
pear -> 2 
orange -> 2 
lettuce -> 0 
carrot -> 0 
asparagus -> 0 

后来的结果呢，与“争议的”“番茄”添加为一个类别2：

mod 103 mod 7 mod 3 should work 
apple -> 1 
pear -> 1 
orange -> 1 
lettuce -> 0 
carrot -> 0 
asparagus -> 0 
tomato -> 2