출력 세트에 일치하는 수식을 입력하는 수식을 작성하는 프로그램 작성

Question

난 그냥 StackOverflow에서 Obfuscated C 설명에 대한 내용을 보았습니다. 나는 새로운 C를 배울 때마다 콘테스트를 매우 흥미롭게 찾으며, 매일 새로운 프로그래밍 지식을 배우게됩니다.

흥미로운 것은시피 Explain 1-liner party of a US President from IOCCC 2013

은 프로그램 모듈의 일련의 기능을 사용하여 (즉. (정수) % 4,796% 2백75% 4) 두 개의 출력 중 하나를 형성하는 입력 번호를 해시 번호. 이 "해시"기능은 제한된 입력 집합에 대해 올바르게 작동하도록 시행 및 오류가 발생했습니다.

여러분이 프로그램의 크기를 최소화해야만 한 결과를 다른 것으로 매핑 할 수 있다는 것이 좋은 생각입니다. 예를 들어 숫자로 변환되어 함수를 통과하면 {apple, lettuce, carrot, pear, orange, asparagus}를 가질 수 있으며 {1,0,0,1,1,0}이됩니다. 공간을 검색하여 문자열을 검색하고 열매를 확인하십시오.

제 질문은 ... 주어진 입력 세트와 출력 세트 모두에서 작동 할 수있는 무차별 대항력 모듈로 함수를 작성하는 방법에 대해 어떻게 생각하십니까?

과일 예를 계속, 당신과 같이 숫자로 과일의 첫 두 글자를 변환 할 수 있습니다 : -> AP - 사과> 0x6170

그래서 목록 {된다 0x6170, 0x6c65, 0x6361, 0x7065, 0x6f72는 0x6173}

그래서 당신은 매핑을 반복 modulos의 포함하는 함수를 생성 할 {0x6170, 0x6c65, 0x6361, 0x7065, 0x6f72, {1,0,0,1,1,0}

에 0x6173}

어떻게 그렇게 할 것입니까?

Answer 1

재미있는 도전이지만 내 수학 스킬을 뛰어 넘습니다. 그래서, 여기에 일반 C의 무력 구현이 :P

내가 증명이없는 등 항상 해결책을 찾을 것입니다 이것을 증명할 수 있지만,이 입력을 사용할 수 있습니다. '과일' '클린턴'과 '야채' '매케인'을 추가하면 조금 더 오래 사용할 수 있습니다. "살구"를 추가하면 충돌이 발생합니다! (어떤보고가 있지만 어디서 말을하지 않습니다. 과일 - 과일 또는 야채와의 충돌이 실제로 허용되어야합니다.이 코드는 작성하지 않았지만 상대적으로 간단해야합니다.)

더 긴 순서를 보려면 "banana"를 추가하십시오. 웬일인지 163,13,2까지 올라야합니다. 재미있게, 그 다음 "kumquat"(내가 과일을 다 쓰고있다)를 더하는 것은 더 오랫동안 잡지 않는다. 그리고 심지어 다른 "코코넛"과 더불어 그것은 더 많은 시간을 잡지 않는다.

구현시주의 사항 : mod 기능은 더 큰 숫자 아무것도하지 않을 것이기 때문에

당신은, 최대 입력 2 바이트 코드로 검색을 제한 할 수 있습니다. 일관성을 유지하기 위해이 C 코드는 모든 1-mod 값을 테스트하는 것으로 시작합니다 (유용한 것은 없었지만). 그런 다음 2-mod 값과 3-mod 값을 테스트합니다. 값을 찾지 못하면 4-mod 및 5-mod 긴 시퀀스를 찾기 위해 값을 확장 할 수 있지만 검색 시간은 대수적으로 증가합니다 (!).

두 개 이상의 값으로 범주화 할 수 있어야합니다. 그 코드의 아주 작은 재 작성이 필요합니다. 나는 모두를위한 성냥을 찾는 것이 훨씬 더 오래 걸릴 것이라고 의심한다.

0 및 1보다 다른 '색인'을 반환 할 수도 있습니다. 이 글을 쓰면서, 나머지 CPU는 2과 0에 열심히 노력하고 있습니다. 그래도 꽤 시간이 걸릴 것 같습니다. 2 및 0의 원하는 출력

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

늦은 결과, :

C 구현, 무력 : 원래 3 과일

#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 야채 목록

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