길이와 같은 표현 된 표현식을 찾으십시오. 따라서의

숫자가 주어지면 해당 숫자와 길이가 같은 숫자로 된 표현식을 찾으십시오.

따라서의 입력에 15 개의 문자 (공백 제외)가 15있는을 출력 할 수 있습니다 sixteen minus one. 여러 가지 해결책이 있으면 원하는 것을 인쇄하십시오. 존재하지 않는 경우 인쇄impossible

만 사용 사업자 plus, minus, times,와 divided by. 작업자는 왼쪽에서 오른쪽으로 배출됩니다.

1234를로 형식화하십시오 one thousand two hundred thirty four. “and”가없고 대시 또는 쉼표가 없습니다.

출력에 사용 된 입력 및 모든 숫자는 10,000보다 작은 양의 정수 여야합니다.

입력은 명령 행 인수로 제공됩니다. 표준 출력으로 인쇄하십시오.

1: impossible
4: four
7: impossible
13: eight plus five (you could also output "five plus eight")
18: one plus two times six (note that operators are evaluated from left to right)
25: one thousand divided by forty


답변

자바 스크립트, 434 자

function f(s){return s.replace(/[A-Z]/g,function(t){return{O:'one',T:'two',H:'three',F:'four',I:'five',S:'six',E:'seven',G:'eight',N:'nine',Z:'ten',P:' plus ',M:' minus ',U:' times ',X:'teen',A:'thir',B:'twenty'}[t]})}A='TPAX|GeenMT|EXUO|B FMS|F|GPSUT|ZPHPG|BPFMT|AXPFPS|BPGMF|EUOPGeen|NPT|B GMSPI|GPI|EPE'.split('|');O=26640;function S(n){return n<15&&!(O>>n&1)?'Invalid':f(A[v=n%15])+(new Array(~~(n/15)+(O>>v&1))).join(f('PSPN'))}

S음수가 아닌 정수를 허용하고 필요한 문자열을 리턴하거나 "Invalid"정수가 스펙 내에 표시 될 수없는 경우 , 전역 네임 스페이스에서 함수를 생성합니다 .

@optokopper와 동일한 접근 방식을 사용하여 "plus six plus nine"가능한 가장 짧은 패딩 문자열 인 동일한 관찰을 수행 했으며 27 개보다 큰 모든 숫자는 15 개의 기본 문자열 중 하나를 반복되는 패드 사본에 연결하여 표현할 수 있습니다.

말했듯이, 우리가 사용하는 기본 문자열 테이블은 다르며 내 솔루션은 비트 twiddling과 나머지 연산자 ( %) 에 의존합니다 . 또한 "multiplied by"가능한 작업을 포함 합니다. 그리고 자연스럽게 문자열이 어떻게 구성되는지에 대한 메커니즘은 C와 Javascript의 비 유사성으로 인해 완전히 다릅니다.

그것은 어쨌든 내 최선의 시도입니다. 😉

달성 할 수있는 숫자에 대한 토론에 도움이되는 @chiru에게 특별한 감사를 전합니다.


답변

JS, 1719/1694

이론

불행히도, 귀하가 제공 한 규칙 세트는 수학적 관점에서 현명한 결정이 아닐 수 있습니다. 실제로 더 작은 규칙의 하위 집합을 사용하면 지정된 간격으로 모든 숫자에 대한 솔루션을 찾을 수 있습니다

제외하고

해결책이 없습니다.

축소 된 규칙 세트

다음과 같은 규칙을 고려하십시오.

  • 단지 연산자를 사용 plus, minus하고 times.
  • 당신은 구현하지 않아도 여러 번 plus또는 minus당신의 표현에있다.
  • 당신은 구현할 필요가 없습니다division아니다 operator associativity(그들의 솔루션 세트가 이미 첫 번째 규칙에 의해 덮여로)을.

이것이 작동하는 이유는 앞에서 @Qwix에서 논의했듯이 지루한 답변 , 즉 정규 표현식으로 끝나는 표현식을 허용하기 때문입니다
( times one)+$. 이를 허용하면 주어진 간격의 각 숫자에 해결책이 있습니다.

당신이 당신의 의견 중 하나에 대답했을 때,

@Qwix 예; 104, 105, 106, 107, 108, 109, 110 또는 111에서는 작동하지 않지만 지루한 답변은 허용됩니다. –

당신은 절대적으로 옳았습니다 : 이것은 숫자 자체, 즉 one hundred four times one times one …다른 숫자로 시작하여 표현을 만들려고 할 때 작동하지 않습니다 .

그러나 표현식이 주어진 숫자 중 하나와 동일한 표현식으로 시작하면 운이 나빠집니다. 예를 들어, 17 + 87실제로 는 다음과 같이 104쓸 수 104있습니다.

104: seventeen plus eighty seven times one times one times one times one times one times one times one times one times one times one

이 서브 세트가 작동 num.js하는지 확인 하려면이 파일을 다른 이름으로 저장 하고 명령 행을위한 JavaScript 엔진 인 SpiderMonkey가 시스템에 설치되어 있는지 확인하십시오.

알고리즘

  • K양의 정수에 대한 속성 을 N문자와 값을 갖는 숫자의 상태로 정의합시다 N.
  • k ∈ ℕ을 사용한 평가보다 F단어 변환 상태가 8k시간보다 짧기 때문에 식 의 속성 을 추가로 정의하겠습니다 . F“fillable”의 약자이며 표현식의 단어 변환을 길이가 8 인 표현식으로 채울 수 있는지 여부 (즉 " times one", 결과 표현식이 속성을 가져올 수 있는지 여부)를 설명합니다 N.

그런 다음 다음과 같이 진행하십시오.

  • 입력 숫자를 단어로 변환하십시오.
  • 입력 번호에 속성이 있는지 확인하십시오 K.
    • 그렇다면 단어를 반환하십시오 ( 4불행히도이 속성의 유일한 숫자입니다).
    • 그렇지 않은 경우 계속 진행하십시오.
  • 입력 번호를 초래하는 모든 두 피연산자 표현식 (더하기, 빼기 및 곱하기)에 대해 해당 평가에 특성이 있는지 확인하십시오 K.
    • 그렇다면 단어를 반환하십시오.
    • 그렇지 않은 경우 두 피연산자 표현식에 property가 있는지 확인하십시오 N.
      • 있는 경우 표현식을 채우고 " times one"결과 표현식의 평가에 특성이 있는지 확인하십시오 K.
        • 그렇다면 단어를 반환
        • 그렇지 않은 경우 계속 진행
      • 그렇지 않은 경우 계속 진행
  • 커피 마시 러 가자

연습

num.js (SpiderMonkey / 명령 줄용)

function X(e,t){return e+": "+t}function P(e){var n,t;for(n=1;.5*e+(e%2===0?1:0)>n;++n){if(t=C.s(n)+" plus "+C.s(e-n),t.replace(/\s/g,"").length===e)return t;if(F(e,t)&&e>t.length)return G(e,t)}return!1}function M(e){var t,n;for(t=L;t>1;--t){if(0>t-e)return!1;if(n=C.s(t)+" minus "+C.s(t-e),n.replace(/\s/g,"").length===e)return n;if(F(e,n)&&e>n.length)return G(e,n)}return!1}function F(e,t){return(e-t.replace(/\s/g,"").length)%8===0}function G(r,t){var e,i=(r-t.replace(/\s/g,"").length)/8,n="";for(e=0;i>e;++e)n+=" times one";return t+n}function T(e){var t,n,r;if(F(e,C.s(e)))return G(e,C.s(e));for(t=1,n=1;t<Math.floor(Math.sqrt(e));++t){for(;e>tn;)++n;if(tn===e&&(r=C.s(t)+" times "+C.s(n),r.replace(/\s/g,"").length===e))return r}return!1}function Y(e){var n,r,t;return e===C.s(e).length?X(e,C.s(e)):(n=P(e))?X(e,n):(r=M(e))?X(e,r):(t=T(e),t?X(e,t):X(e,"impossible"))}var L=1e4,C=new function(){return this.o=["","one","two","three","four","five","six","seven","eight","nine"],this.t=["","","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"],this.T=["ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"],this.s=function(e){return e?this.m(e):"zero"},this.m=function(e){return e>=1e6?this.m(Math.floor(e/1e6))+" million"+(e%1e6!==0?" "+this.Z(e%1e6):""):this.Z(e)},this.Z=function(e){return e>=1e3?this.h(Math.floor(e/1e3))+" thousand"+(e%1e3!==0?" "+this.h(e%1e3):""):this.h(e)},this.h=function(e){return e>99?this.o[Math.floor(e/100)]+" hundred"+(e%100!==0?" "+this.U(e%100):""):this.U(e)},this.U=function(e){return 10>e?this.o[e]:e>=10&&20>e?this.T[e-10]:this.t[Math.floor(e/10)]+(e%10!==0?" "+this.o[e%10]:"")},this};print(Y(0|arguments[0]))

num.js (브라우저 용)

위의 주어진 코드는 마지막 명령으로 인해 브라우저에서 작동하지 않습니다. 마지막 명령으로 주어진 스크립트에서 멋진 명령을 내리기 위해 명령 줄 인수를 가져옵니다.

브라우저에서 직접 JavaScript 코드를 실행하려면 위 코드 중이 부분을 선택하십시오.

function X(e,t){return e+": "+t}function P(e){var n,t;for(n=1;.5*e+(e%2===0?1:0)>n;++n){if(t=C.s(n)+" plus "+C.s(e-n),t.replace(/\s/g,"").length===e)return t;if(F(e,t)&&e>t.length)return G(e,t)}return!1}function M(e){var t,n;for(t=L;t>1;--t){if(0>t-e)return!1;if(n=C.s(t)+" minus "+C.s(t-e),n.replace(/\s/g,"").length===e)return n;if(F(e,n)&&e>n.length)return G(e,n)}return!1}function F(e,t){return(e-t.replace(/\s/g,"").length)%8===0}function G(r,t){var e,i=(r-t.replace(/\s/g,"").length)/8,n="";for(e=0;i>e;++e)n+=" times one";return t+n}function T(e){var t,n,r;if(F(e,C.s(e)))return G(e,C.s(e));for(t=1,n=1;t<Math.floor(Math.sqrt(e));++t){for(;e>tn;)++n;if(tn===e&&(r=C.s(t)+" times "+C.s(n),r.replace(/\s/g,"").length===e))return r}return!1}function Y(e){var n,r,t;return e===C.s(e).length?X(e,C.s(e)):(n=P(e))?X(e,n):(r=M(e))?X(e,r):(t=T(e),t?X(e,t):X(e,"impossible"))}var L=1e4,C=new function(){return this.o=["","one","two","three","four","five","six","seven","eight","nine"],this.t=["","","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"],this.T=["ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"],this.s=function(e){return e?this.m(e):"zero"},this.m=function(e){return e>=1e6?this.m(Math.floor(e/1e6))+" million"+(e%1e6!==0?" "+this.Z(e%1e6):""):this.Z(e)},this.Z=function(e){return e>=1e3?this.h(Math.floor(e/1e3))+" thousand"+(e%1e3!==0?" "+this.h(e%1e3):""):this.h(e)},this.h=function(e){return e>99?this.o[Math.floor(e/100)]+" hundred"+(e%100!==0?" "+this.U(e%100):""):this.U(e)},this.U=function(e){return 10>e?this.o[e]:e>=10&&20>e?this.T[e-10]:this.t[Math.floor(e/10)]+(e%10!==0?" "+this.o[e%10]:"")},this}

이제 브라우저의 JavaScript 콘솔에 붙여 넣어 다음과 같이 브라우저 내에서 동일한 결과를 생성 할 수 있습니다.

Y(1234);

예 (명령 줄)

chiru@chiru ~ $ js num.js 28
28: fourteen plus fourteen times one
chiru@chiru ~ $ js num.js 7
7: impossible
chiru@chiru ~ $ js num.js 42
42: nine thousand sixty minus nine thousand eighteen

그리고 각 숫자를 사용할 수있는 트릭을 보려면 지루한 답변 을 살펴보십시오 js num.js 1337.

1337: ten plus one thousand three hundred twenty seven times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one times one

제공된 코드는 주어진 간격에 대해 유효한 솔루션을 생성합니다 (그리고 아마도 위의 값은 변수 값을 높여야합니다 L).

통계

나는에 관심이 있었다 “어떻게 지루한 “표현이었다 (또는 : 문자열이 얼마나 times one이 알고리즘 내에서 발현 당 사용),이 부분은 주어진 기간 내의 모든 번호에 대한 해결책을 찾기에 대한 책임이있다. 직접 참조하십시오 :

x : n 번째 표현 (최소 0, 최대 10,000)

y : 표현식 내 하위 문자열 “한 번 1″의 발생 횟수 (최소 0, 최대 1245)

결론 :

  • 표현은 선형 방식으로 점점 더 지루 해지는 경향이 있습니다.
  • 솔루션의 99 % 이상이 지루합니다.

답변

C, 450 자

편집 : 제거 zero

편집 : 사용하는 경우에만 plusminus

문자를 추가하고 조건을 유지하는 가장 짧은 표현식을 검색했습니다. 나는 plus ten plus five15 길이이며 문자열에 15를 더합니다.

가능한 숫자를 표현하기 위해 불가능하지 않은 처음 15 개의 숫자에 대한 식만 필요합니다. 12는 가장 큰 불가능한 숫자이므로 28보다 작은 숫자를 하드 코딩하면 충분합니다.

4 = 4
11 = 6 더하기 5
13 = 8 더하기 5
14 = 스물 빼기 6
15 = 20 마이너스 5
16 = 18--2
17 = 14 더하기 3
18 = 스물 둘 빼기 넷
20 = 서른 두 마이너스 12
21 = 20 더하기 2 빼기 1
22 = 20 더하기 4 빼기 2
23 = 서른 빼기 8 더하기 1
24 = 20 더하기 8 빼기 4
25 = 20 더하기 8 빼기 3
27 = 스물 여덟-6 더하기 5

우리는 27보다 큰 모든 숫자를 x * 15 + 위의 숫자 중 하나로 쓸 수 있습니다.

골프

#define P" plus "
#define M" minus "
#define U"four"
#define F"five"
#define E"eight"
#define W"twenty"
#define A"ten"P F P
*e[]={0,0,0,0,U,0,0,0,0,0,0,F P"six",0,E P F,W M"six",W M F,E"een"M"two",U"teen"P"three",W" two"M U,A U,"thirty two"M"twelve",W P"two"M"one",W M"two"P U,"thirty"P"one"M E,W P E M U,W M"three"P E,A F P"six",W" "E M"six"P F};main(n){n=atoi(1[(int*)1[&n]]);for(printf("%d: ",n);n>27;n-=15)printf(A);puts(e[n]?e[n]:"impossible");}

읽을 수있는 코드

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

// add fifteen to string, both as value and as character count (without spaces)
const char *add_fifteen = "plus ten plus five";

// table with hardcoded expressions
// NOTE: we could calculate 19, 26, 28 and 29 from 4, 11, 13 and 14
// but we would need more logic, so we hardcode those 4 numbers too.
const char *expressions[30]={"impossible", "impossible", "impossible", "impossible",
    "four", "impossible", "impossible", "impossible", "impossible",
    "impossible", "impossible", "five plus six", "impossible",
    "eight plus five", "twenty minus six",
    "fourteen plus one", "eighteen minus two", "fourteen plus three",
    "twenty two minus four", "four plus ten plus five",
    "thirty two minus twelve", "nine plus seven plus five",
    "twenty plus four minus two", "twelve plus seven plus four",
    "twenty plus eight minus four", "twenty plus eight minus three",
    "five plus six plus ten plus five", "twenty eight minus six plus five",
    "eight plus five plus ten plus five", "seven plus seven plus ten plus five"};

int main(int argc,char *argv[])
{
    int n = strtol(argv[1], NULL, 0);
    int fifteens = 0;

    printf("%d: ", n);

    // how many times do we need to add fifteen?
    if(n>29){
        fifteens=(n/15) - 1;
        n -= fifteens*15; // ensure 30 > n >= 15, so we don't get "impossible"
    }

    // look up the expression for n
    printf("%s", expressions[n]);

    // add fifteens till we are done
    while(fifteens-- > 0) {
        printf(" %s", add_fifteen);
    }

    printf("\n");
    return 0;
}