Biorąc pod uwagę liczbę, znajdź wyrażenie w słowach równe tej liczbie, o długości tej liczby.

Tak więc na wejściu 15możesz wyprowadzać danesixteen minus one , który ma piętnaście znaków (nie licząc spacji). Jeśli istnieje wiele rozwiązań, wydrukuj, co chcesz. Jeśli nie istnieje, wydrukujimpossible

Stosować tylko operatorzy plus, minus, times, idivided by . Operatory są oceniane od lewej do prawej.

Sformatuj 1234 jako one thousand two hundred thirty four . Zwróć uwagę na brak „i” oraz brak myślników i przecinków.

Dane wejściowe i wszystkie liczby użyte na wyjściu muszą być dodatnimi liczbami całkowitymi mniejszymi niż 10 000.

Dane wejściowe zostaną podane jako argument wiersza poleceń. Drukuj na standardowe wyjście.

Przykłady

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

JavaScript, 434 znaki

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'))}

Daje funkcję w globalnej przestrzeni nazw, Sktóra przyjmuje dowolną nieujemną liczbę całkowitą i zwraca wymagany ciąg znaków lub"Invalid" jeśli liczba całkowita nie może być reprezentowana w specyfikacjach.

Wydaje mi się, że zastosowałem takie samo podejście jak @optokopper, dokonując tego samego spostrzeżenia "plus six plus nine" jest najkrótszym możliwym ciągiem wypełniającym, i że wszystkie liczby większe niż 27 można wyrazić poprzez połączenie jednego z 15 ciągów podstawowych z powtarzanymi kopiami podkładki.

To powiedziawszy, tabele ciągów bazowych, których używamy, różnią się, a moje rozwiązanie opiera się na skręcaniu bitów i operatorze reszty ( %). Obejmuje również "multiplied by"jako możliwą operację. I oczywiście mechanika budowy łańcuchów jest zupełnie inna z powodu odmienności między C i Javascript.

W każdym razie to moja najlepsza próba. ;)

Specjalne podziękowania dla @chiru, którego dyskusja o tym, które liczby były osiągalne, pomogła zapobiec bezowocnemu wyszukiwaniu.

JS, 1719/1694

Teoria

Niestety zestaw reguł, który podajesz, może nie być mądrą decyzją z matematycznego punktu widzenia. W rzeczywistości, stosując mniejszy podzbiór reguł, możesz znaleźć rozwiązanie dla każdej liczby w danym przedziale

z wyjątkiem

dla którego nie ma rozwiązania.

Zredukowany zestaw reguł

Zastanów się nad następującym podzbiorem zasad:

• Używaj wyłącznie podmiotom plus, minusa times.
• Nie musisz implementować wielu wystąpień pluslub minuswyrażeń.
• Nie musisz implementować ani divisionani operator associativity(ponieważ ich zestaw rozwiązań jest już objęty pierwszą regułą).

Powodem, dla którego to działa, jest to, że, jak omówiono wcześniej w @Qwix, pozwalasz na nudne odpowiedzi , czyli wyrażenia kończące się wyrażeniem regularnym ( times one)+$ . Dzięki temu każda liczba w danym przedziale będzie miała rozwiązanie.

Gdy odpowiedziałeś w jednym ze swoich komentarzy,

@Qwix Tak; nudne odpowiedzi są dopuszczalne, chociaż nie działa w przypadku 104, 105, 106, 107, 108, 109, 110 lub 111. -

miałeś całkowitą rację: to nie działa, gdy próbujesz zbudować wyrażenie zaczynając od samych liczb, tj one hundred four times one times one … lub jakiejkolwiek innej z tych liczb.

Jeśli jednak twoje wyrażenie zaczyna się od wyrażenia, którego ocena jest równa jednej z podanych liczb, nie masz szczęścia. Na przykład zauważmy, że 17 + 87tak jest 104, abyśmy mogli napisać 104jako:

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

Aby sprawdzić, czy ten podzbiór działa, zapisz ten plik jako num.jsi upewnij się, że SpiderMonkey, silnik JavaScript dla linii poleceń, jest zainstalowany w twoim systemie.

Algorytm

• Zdefiniujmy właściwość Kdodatnich liczb całkowitych jako stan liczby mającej Nlitery i posiadającej wartość N.
• Zdefiniujmy dalej właściwość Fwyrażenia jako stan jego konwersji słowa - 8krazy krótszej niż jego ocena za pomocą k ∈ ℕ. Foznacza „do wypełnienia” i opisuje, czy możemy wypełnić konwersję słowa wyrażenia wyrażeniami o długości 8 (tj. " times one") tak, aby wynikowe wyrażenie mogło uzyskać właściwość N.

Następnie postępujemy w następujący sposób:

• Konwertuj liczbę wejściową na słowa.
• Sprawdź, czy numer wejściowy ma właściwość K.
  • Jeśli tak, zwróć słowa ( 4niestety to jedyna liczba w tej właściwości).
  • Jeśli nie, kontynuuj.
• W przypadku wszystkich wyrażeń z dwoma argumentami operacji (dodawania, odejmowania i mnożenia w tej kolejności), które prowadzą do liczby wejściowej, sprawdź, czy ich ocena ma właściwość K.
  • Jeśli tak, zwróć słowa.
  • Jeśli nie, sprawdź, czy wyrażenie z dwoma argumentami ma właściwość N.
    • Jeśli tak, wypełnij wyrażenie " times one"i sprawdź, czy ocena wynikowego wyrażenia ma właściwość K.
      • Jeśli tak, zwróć słowa
      • Jeśli nie, kontynuuj
    • Jeśli nie, kontynuuj
• Idź napić się kawy

Ćwiczyć

num.js (dla SpiderMonkey / linii poleceń)

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 (dla przeglądarek)

Podany powyżej kod nie może działać w przeglądarkach ze względu na jego ostatnie polecenie, które przechwytuje argumenty wiersza poleceń, aby wykonać fajne polecenie z danego skryptu.

Aby uruchomić kod JavaScript bezpośrednio z poziomu przeglądarki, wybierz ten fragment powyższego kodu:

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}

Teraz wklej go do konsoli JavaScript przeglądarki, aby uzyskać takie same wyniki w przeglądarce, na przykład:

Y(1234);

Przykłady (wiersz poleceń)

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

Aby zobaczyć sztuczkę, dzięki której każdy numer może działać, wystarczy spojrzeć na nudną odpowiedź na 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

Dostarczone kody generują prawidłowe rozwiązania dla danego przedziału (i prawdopodobnie nawet powyżej, będziesz musiał tylko podnieść wartość zmiennej L).

Statystyka

Interesowało mnie „jak nudne ” były wyrażenia (lub: ile podciągu times oneużyto na wyrażenie w tym algorytmie), ponieważ ta część była odpowiedzialna za znalezienie rozwiązania dla każdej liczby w danym przedziale. Przekonaj się:

x : n-ty wyraz (min. 0, maks. 10 000)

y : liczba wystąpień podciągu „jeden raz” w obrębie wyrażenia (min. 0, maks. 1245)

Wnioski:

• Wyrażenia stają się coraz bardziej nudne w sposób liniowy.
• Ponad 99% rozwiązań jest nudnych.

C, 450 znaków

Edycja: usunięto zero

Edycja: używając tylko plusiminus

Szukałem najkrótszego wyrażenia, które dodaje znaki i utrzymuje warunek prawdziwy. Znalazłem plus ten plus five15 długich i dodaje 15 do łańcucha.

Potrzebuję tylko wyrażeń dla pierwszych 15 liczb, które nie są niemożliwe, aby wyrazić dowolną możliwą liczbę. 12 jest największą niemożliwą liczbą, dlatego wystarcza do kodów o mniejszym numerze 28.

4 = cztery
11 = sześć plus pięć
13 = osiem plus pięć
14 = dwadzieścia minus sześć
15 = dwadzieścia minus pięć
16 = osiemnaście minus dwa
17 = czternaście plus trzy
18 = dwadzieścia dwa minus cztery
20 = trzydzieści dwa minus dwanaście
21 = dwadzieścia plus dwa minus jeden
22 = dwadzieścia plus cztery minus dwa
23 = trzydzieści minus osiem plus jeden
24 = dwadzieścia plus osiem minus cztery
25 = dwadzieścia plus osiem minus trzy
27 = dwadzieścia osiem minus sześć plus pięć

Możemy zapisać każdą liczbę> 27 jako x * 15 + jedna z powyższych liczb.

Grał w golfa

#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");}

Kod czytelny

#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;
}