Numery StickStack

22

StickStack to bardzo prosty język programowania oparty na stosie, zawierający tylko dwie instrukcje:

  • | wypycha długość stosu na stos
  • -wysuwa dwa górne elementy ze stosu i odsuwa ich różnicę ( second topmost - topmost)

Szczegóły języka

  • Stos jest pusty na początku programu.
  • Wszystkie instrukcje są wykonywane sekwencyjnie od lewej do prawej.
  • Jeśli na stosie jest mniej niż 2 liczby, -instrukcja jest nielegalna.
  • Pod koniec wykonywania stos powinien zawierać dokładnie jedną liczbę .

Każda liczba całkowita może być generowana przez program StickStack. Na przykład:

|||--||-- generates the number 2 through the following stack states:

[]
[0]
[0, 1]
[0, 1, 2]
[0, -1]
[1]
[1, 1]
[1, 1, 2]
[1, -1]
[2]    

Aby ocenić kod StickStack, możesz skorzystać z tego narzędzia do oceny online (CJam) . (Dzięki za @Martin za kod.)

Zadanie

Powinieneś napisać program lub funkcję, która jako liczbę wyjściową podaje liczbę całkowitą lub zwraca ciąg znaków reprezentujący program StickStack, który wypisuje podaną liczbę.

Punktacja

  • Twój wynik główny to całkowita długość programów StickStack dla poniższych przypadków testowych. Niższy wynik jest lepszy.
  • Twoje zgłoszenie jest ważne tylko wtedy, gdy uruchomiłeś program na wszystkich testowych przypadkach i policzyłeś swój wynik.
  • Drugi wynik (remis rozstrzygający) to długość programu lub funkcji generującej.

Wprowadź przypadki testowe

(Każda liczba to inny przypadek testowy).

-8607 -6615 -6439 -4596 -4195 -1285 -72 12 254 1331 3366 3956 5075 5518 5971 7184 7639 8630 9201 9730

Twój program powinien działać na wszystkich liczbach całkowitych (które może obsłużyć Twój typ danych), a nie tylko na danych przypadkach testowych. Rozwiązania dla numerów testowych nie powinny być zakodowane na stałe w twoim programie. Jeśli pojawią się wątpliwości co do twardego kodowania, numery testowe zostaną zmienione.

randomra
źródło
Sugeruję dodanie klauzuli z napisem „I biegnie w rozsądnym czasie”, aby zapobiec brutalnej sile.
@Retyczność, która implikuje „ważne tylko, jeśli uruchomiłeś program na wszystkich testowych przypadkach”
edc65

Odpowiedzi:

7

Python 2 - 5188

Dość wydajny pod względem czasowym i wydaje się (prawdopodobnie) optymalnym rozwiązaniem. Zauważyłem, że wzór taki jak

|||||-|||-|-|-|------ (optymalne rozwiązanie dla 25 osób)

można określić jako

 0  |
-1  |                  
+2   |                 -
-3    |               -
+4     | |           -
-5      - |         -
+6         | | | | -
-7          - - - -

gdzie każda całkowita wartość na końcu jest sumą (wartość każdego poziomu pomnożona przez liczbę „|”). Na przykład powyżej mamy -1*1 + 2*1 - 3*1 + 4*2 - 5*1 + 6*4 = 25. Korzystając z tego, napisałem to rozwiązanie, które daje wyniki podobne do innych odpowiedzi, w bardzo trywialnym czasie.

Uważam, że jest to optymalne rozwiązanie, ponieważ testuję każdą możliwą optymalną wysokość (faktycznie testuję o wiele więcej niż to konieczne) i jestem prawie pewien, że rozwiązanie zawsze obejmuje co najwyżej jedną warstwę z dwoma znakami „|” oprócz ostatniej (mogę zagwarantuj to dla liczb dodatnich, ale nie 100% pewności co do negatywów).

def solution(num):
    if num == 0:
        return '|'

    neg = num<0
    num = abs(num)
    high = int(num**0.5)

    def sub(high):
        counts = [1]*high
        total = num - (high+neg)/2

        if total%high == 0:
            counts[-1] += total/high
        else:
            counts[-1] += total/high
            if (total%high)%2==1 and not neg:
                counts[-1] += 1
                counts[-(total%high)-1] += 1
            elif (total%high)%2==0 and neg:
                counts[(total%high)-2] += 1
                counts[0] += 1
            else:
                counts[total%high-1] += 1

        string = ""
        for c in counts[::-1]:
            string = '|-'*(c-1)+'|'+string+'-'
        return '|'+string

    return min((sub(h) for h in range(2-neg,2*high+2,2)), key=lambda s: len(s))

Oto kod, którego użyłem do przetestowania

string = "-8607 -6615 -6439 -4596 -4195 -1285 -72 12 254 1331 3366 3956 5075 5518 5971 7184 7639 8630 9201 9730"
total = 0

def string_to_binary(string):
    total = 0
    for i,char in enumerate(string[::-1]):
        total += (char=='|')*(2**i)
    return total

def stickstack(bits,length):
    stack = []
    for i in range(length):
        d,bits = divmod(bits,2**(length-i-1))
        if d == 1:
            stack.append(len(stack))
        else:
            stack[-2] -= stack[-1]
            stack = stack[:-1]
    return stack

for num in string.split():
    s = solution(int(num))
    print '%s:' % num
    print s
    result = stickstack(string_to_binary(s),len(s))
    print 'Result: %s' % result
    print 'Length: %s' % len(s)
    total += len(s)
    print

print 'Total length: %s' % total
KSab
źródło
2
Świetne rozwiązanie! Uważam, że wynik jest optymalny (na podstawie moich obliczeń siły) i na podstawie twojego opisu myślę, że twój algorytm zawsze daje najlepsze rozwiązania.
randomra
@randomra Myślę, że to prawdopodobne, ale byłem brutalnie zmuszony do około +/- 100, więc nie byłem gotowy powiedzieć, że to był koniecznie najlepszy, ale teraz, gdy o tym myślę, nie widzę jak można to zrobić lepiej.
KSab
+1 bardzo fajnie. Jak mogę tego spróbować? Jaki pyton? (Nie jestem pythonistą, po prostu przypadkowo mam zainstalowanego Pythona 3.4 na moim laptopie).
edc65
@ edc65 Dodałem kod, aby go przetestować; także to używa Python 2.7, więc rzeczy takie jak instrukcje print nie będą działać z Python 3
KSab
Za to, co warto, mogę potwierdzić, że ten wynik jest optymalny: wypróbowałem rozwiązanie brutalnej siły (rzeczywiście BFS), weryfikując do długości 450 (i nadal działa). Te same wyniki twoje.
edc65
12

Java, 5208 5240 5306 6152

Jest to funkcja rekurencyjna, która zbliża się do celu, z podstawowymi przypadkami, gdy osiągnie wartość 5 (co często jest tylko jednym krokiem).

Zasadniczo, można uzyskać (a*b)+(a/2)na (a+b)*2kije z prostego wzoru. Jeśli ajest nieparzysty, wynik będzie ujemny, co prowadzi do dziwnej logiki.

Zajmuje to około minuty dla 2 31 -1, w rezultacie o długości 185 367. Działa prawie natychmiast dla wszystkich przypadków testowych. To 4*(sqrt|n|)średnia ocena. Najdłuższy indywidualny przypadek testowy 9730, co daje stos o długości 397 kijów:

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||-|||||||||||||||||||||-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|--------------------------------------------------------------------------------------------------|-

Aktualizacja:

Znaleziono krótszy sposób dodawania / odejmowania od podstawowego wzorca. Z powrotem na czele (na razie)!


Z uprzężą i walizkami testowymi:

import static java.lang.Math.*;

public class StickStacker {

    public static void main(String[] args){
        StickStacker stacker = new StickStacker(); 
        int tests[] = {-8607,-6615,-6439,-4596,-4195,-1285,-72,12,254,1331,3366,3956,5075,5518,5971,7184,7639,8630,9201,9730};
        int sum = 0;
        for(int test : tests){
            String sticks = stacker.stickStack3(test);
            sum += sticks.length();
            System.out.println("In: " + test + "\t\tLength: " + sticks.length());
            System.out.println(sticks+"\n");
        }
        System.out.println("\n\nTotal: "+sum);          
    }

    String stickStack3(int n){return"|"+k(n);}
    String k(int n){
        String o="";
        int q=(int)sqrt(abs(n)),a,b,d=1,e=0,c=1<<30,
        z[]={232,170,42,10,2,0,12,210,52,844,212};
        a=n>0?q:-q;
        a-=n>0?a%2<1?0:1:a%2<0?0:-1;

        for(b=0;b<abs(a)+10;b++)
            if(abs(n-(a*b+a/2-(n>0?0:1)))<abs(a)&&abs(a)+b<c){
                    c=abs(a)+b;
                    d=a;e=b;
            }

        for(a=0;a++<e;)o+="-|";
        for(a=0;a++<abs(d);)o="|"+o+"-";

        c=n-(d*e+d/2-(n>0?0:1));
        if(c>0&&c<abs(d)){
            if(c%2==0)
                o=o.substring(0,c)+"-|"+o.substring(c);
            else
                o=o.substring(0,c+1)+"-|"+o.substring(c+1)+"|-";
            c=0;
        }else if(c<0&-c<abs(d)){
            if(c%2!=0)
                o=o.substring(0,-c)+"-|"+o.substring(-c);
            else
                o=o.substring(0,-c-1)+"-|"+o.substring(-c-1)+"|-";  
            c=0;
        }

        return n==0?"":n<6&&n>-6?
                Long.toBinaryString(z[n+5])
                .replaceAll("0","-")
                .replaceAll("1","|"):
                o+k(c);
    }
}

Gra w golfa (więcej) w mało prawdopodobnym przypadku dokładnego remisu.

Geobity
źródło
Czy jesteś pewien swojego wyniku za 2 ^ 31? Mój wynik dla 2 ^ 30 to 131099, a 185369 dla 2 ^ 31-1.
edc65
@ edc65 Musiałem źle wpisać. Pomyślałem, że to wydaje się trochę niskie ... W każdym razie dzięki za zauważenie i trochę konkurencji. Czas sprawdzić, czy dam radę :)
Geobits
4

JavaScript (ES6) 5296 6572

Edytuj Jak powiedziałem w moim wyjaśnieniu, nie jestem dobry w rozwiązywaniu równań całkowitych. Moje przypuszczenie wartości b nie było tak dobre, więc poszerzyłem zakres wartości do wypróbowania. I (wow) Teraz prowadzę.

Edytuj 2 Poprawka błędu, te same wyniki. Mam pomysł, ale nie mogę go dopracować.

Bajty: ~ 460, dość golfa. Działa na 32-bitowych liczbach całkowitych, czas działania zbliżony do 0.

Kod to funkcja F (ukryta we fragmencie) poniżej.
Uruchom fragment, aby przetestować (w FireFox).

Wyjaśnienie

Na początek liczby dodatnie. Zacznij od „podstawy” (spróbuj w CJam, jeśli chcesz, spacje dozwolone)

| gives 0  
||| -- gives 1
||||| ---- gives 2
||||||| ------ gives 3 

Podsumowanie: 1 drążek, następnie b * 2 drążki, a następnie b * 2 kreski

Następnie spróbuj dodać jeden lub więcej „- |” w środkowym splocie. Każdy z nich dodaje stały przyrost, który stanowi dwukrotność podstawy początkowej i może być powtarzany wiele razy. Mamy więc wzór, w którym b = podstawa ir = współczynnik powtarzania przyrostu

v=b+r*2*b

b=1, r=0 to 3, inc=2
| || -- 1 
| || -| -- 3 
| || -| -| -- 5 
| || -| -| -| -- 7

b=3, r=0 to 3, inc=6
| |||||| ------ 3
| |||||| -| ------ 9
| |||||| -| -| ------ 15
| |||||| -| -| -| ------ 21

Widzieć? Wartość dodana szybko wzrasta, a każdy dodatek nadal ma tylko 2 znaki. Przyrost podstawowy daje za każdym razem 4 dodatkowe znaki.

Biorąc pod uwagę v i naszą formułę v = b + r * 2 * b, musimy znaleźć 2 ints bi r. Nie jestem ekspertem w tego rodzaju równaniach, ale b = int sqrt (v / 2) to dobry początek.

Następnie mamy rib, które razem dają wartość bliską v. Osiągamy v dokładnie z powtarzanym przyrostem (|| -) lub zmniejszeniem (| -).

Stosuj to samo rozumowanie liczb ujemnych, niestety formuła jest podobna, ale nie równa.

edc65
źródło
1

JavaScript, 398710

94 bajty / znaki kodu

Wymyśliłem rozwiązanie! ... a potem przeczytałem odpowiedź Sparra i było dokładnie tak samo.

Pomyślałem, że i tak to opublikuję, ponieważ js pozwala na nieco mniej znaków.

Oto nieuprawniona wersja kodu:

function p(a){
    s = "";
    if(a<=0){
        for(i=0; i<-2*a-1;i++)
            s="|"+s+"-";
        return "|"+s;
    }
    return "|"+p(0-a)+"-";
}
Nate Young
źródło
1
ok, jeśli gramy w golfa z rozwiązaniami 398710, gra trwa! ktoś przejdzie przez cjam lub pyth i pokona nas oboje :(
Sparr
1

Python, 398710 (71 bajtów)

Najprostsze możliwe rozwiązanie, tak myślę. Używa 4 * n (+/- 1) znaków stickstack do reprezentowania n.

def s(n):return'|'*(n*2+1)+'-'*n*2 if n>=0 else'|'*(n*-2)+'-'*(n*-2-1)
Sparr
źródło