StickStack-Nummern

22

StickStack ist eine sehr einfache stapelbasierte Programmiersprache mit nur zwei Anweisungen:

  • | Schiebt die Länge des Stapels auf den Stapel
  • -Entfernt die beiden obersten Elemente aus dem Stapel und drückt ihre Differenz zurück ( second topmost - topmost)

Sprachdetails

  • Der Stack ist zu Beginn des Programms leer.
  • Alle Anweisungen werden nacheinander von links nach rechts ausgeführt.
  • Wenn sich weniger als 2 Zahlen auf dem Stapel befinden, ist der -Befehl unzulässig.
  • Am Ende der Ausführung sollte der Stapel genau eine Zahl enthalten .

Jede beliebige Ganzzahl kann von einem StickStack-Programm generiert werden. Beispielsweise:

|||--||-- 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]    

Um Ihren StickStack-Code auszuwerten, können Sie diesen Online-Evaluator (CJam) verwenden . (Danke für @Martin für den Code.)

Die Aufgabe

Sie sollten ein Programm oder eine Funktion schreiben, die eine Ganzzahl als Eingabe ausgibt oder eine Zeichenfolge zurückgibt, die ein StickStack-Programm darstellt, das die angegebene Zahl ausgibt.

Wertung

  • Ihre primäre Punktzahl ist die Gesamtlänge der StickStack-Programme für die unten angegebenen Testfälle. Niedrigere Punktzahl ist besser.
  • Ihre Einreichung ist nur gültig, wenn Sie Ihr Programm für alle Testfälle ausgeführt und Ihre Punktzahl gezählt haben.
  • Ihre sekundäre Punktzahl (Tiebreaker) ist die Länge Ihres Erzeugungsprogramms oder Ihrer Erzeugungsfunktion.

Testfälle eingeben

(Jede Nummer ist ein anderer Testfall.)

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

Ihr Programm sollte für alle Ganzzahlen (die Ihr Datentyp verarbeiten kann) funktionieren, nicht nur für die angegebenen Testfälle. Die Lösungen für die Testnummern sollten nicht in Ihr Programm fest einprogrammiert werden. Im Zweifelsfall werden die Testnummern geändert.

randomra
quelle
Ich schlage vor, eine Klausel hinzuzufügen, die besagt: "Und läuft in angemessener Zeit", um Brute-Force zu verhindern.
@Reticality, die impliziert, dass "nur gültig, wenn Sie Ihr Programm auf allen Testfällen ausgeführt"
edc65

Antworten:

7

Python 2 - 5188

Ziemlich effizient in Bezug auf die Zeit und scheint (wahrscheinlich) die optimale Lösung zu sein. Ich habe beobachtet, dass ein Muster wie

|||||-|||-|-|-|------ (eine optimale Lösung für 25)

kann abgegrenzt werden als

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

Dabei ist jeder der Gesamtwert am Ende die Summe von (der Wert jedes Levels multipliziert mit der Anzahl von '|' s). Also zum Beispiel oben haben wir -1*1 + 2*1 - 3*1 + 4*2 - 5*1 + 6*4 = 25. Auf diese Weise habe ich diese Lösung geschrieben, die eine ähnliche Ausgabe wie andere Antworten liefert, und das in trivialer Zeit.

Ich bin der Meinung, dass dies die optimale Lösung ist, da ich jede mögliche optimale Höhe teste (ich teste tatsächlich viel mehr als nötig) und ich bin mir ziemlich sicher, dass die Lösung immer höchstens eine Schicht mit zwei | neben der letzten umfasst (das kann ich) garantieren dies für positive Zahlen, aber nicht 100% sicher über Negative).

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

Hier ist der Code, den ich zum Testen verwendet habe

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
quelle
2
Tolle Lösung! Ich glaube, die Punktzahl ist optimal (basierend auf meiner Bruteforce-Berechnung) und basierend auf Ihrer Beschreibung. Ich denke, Ihr Algorithmus liefert immer die besten Lösungen.
Randomra
@randomra Ich denke, es ist wahrscheinlich, dass es so ist, aber ich war nur brutal gezwungen, ungefähr +/- 100 zu erreichen, also war ich nicht bereit zu sagen, dass es unbedingt das Beste war, aber jetzt, wo ich darüber nachdenke, kann ich es nicht sehen wie könnte es besser gemacht werden.
KSab,
+1 sehr schön. Wie kann ich es versuchen? Welcher Pyton? (Ich bin kein Pythonist, ich habe nur versehentlich einen Python 3.4 auf meinem Laptop installiert).
edc65
@ edc65 Ich habe Code zum Testen hinzugefügt. Außerdem wird Python 2.7 verwendet, sodass Dinge wie die print-Anweisungen mit Python 3
KSab
Für das, was es wert ist, kann ich bestätigen, dass dieses Ergebnis optimal ist: Ich habe eine Brute-Force-Lösung (in der Tat ein BFS) ausprobiert, die bis zu einer Länge von 450 überprüft (und immer noch ausgeführt wird). Gleiche Ergebnisse bei Ihnen.
edc65
12

Java, 5208 5240 5306 6152

Dies ist eine rekursive Funktion, die näher an das Ziel heranreicht, mit Basisfällen, wenn es innerhalb von 5 liegt (was oft nur ein Schritt ist).

Grundsätzlich kann man bekommen (a*b)+(a/2) nach (a+b)*2Sticks mit einem einfachen Muster suchen. Wenn aungerade ist, ist das Ergebnis negativ, was zu einer seltsamen Logik führt.

Dies dauert ungefähr eine Minute für 2 31 -1 mit einer Länge von 185 367 als Ergebnis. Es funktioniert jedoch fast sofort für alle Testfälle. Es zählt4*(sqrt|n|) im Durchschnitt. Der längste Einzeltestfall ist9730 ergibt einen 397-fachen Stockstapel:

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

Aktualisieren:

Es wurde ein kürzerer Weg gefunden, das Grundmuster zu addieren / zu subtrahieren. Zurück an der Spitze (vorerst)!


Mit einem Geschirr und Testfällen:

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

Wird im unwahrscheinlichen Fall eines genauen Gleichstands (mehr) Golf spielen.

Geobits
quelle
Sind Sie sicher, dass Sie 2 ^ 31 Punkte erzielt haben? Meine Punktzahl für 2 ^ 30 ist 131099 und 185369 für 2 ^ 31-1.
edc65
@ edc65 Ich muss es falsch eingegeben haben. Ich dachte, es scheint ein bisschen leise zu sein ... Trotzdem, danke, dass du es bemerkt hast und ein bisschen Konkurrenz gemacht hast. Jetzt ist es Zeit zu sehen, ob ich es besser machen kann :)
Geobits
4

JavaScript (ES6) 5296 6572

Bearbeiten Wie ich in meiner Erklärung sagte, bin ich nicht gut darin, ganzzahlige Gleichungen zu lösen. Ich habe den b-Wert nicht so gut geschätzt, also habe ich den Wertebereich erweitert, um es zu versuchen. Und (wow) ich führe jetzt.

Edit 2 Bugfix, gleiche Ergebnisse. Ich habe eine Idee, kann sie aber nicht umreißen.

Bytes: ~ 460, ziemlich golfen. Es funktioniert mit 32-Bit-Ganzzahlen, Laufzeit nahe 0.

Der Code ist die F-Funktion (im Snippet versteckt) unten.
Führen Sie das zu testende Snippet aus (in FireFox).

Erläuterung

Zunächst positive Zahlen. Beginnen Sie mit einer "Basis" (versuchen Sie es in CJam, wenn Sie möchten, Leerzeichen erlaubt)

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

Zusammenfassung: 1 Stick, dann b * 2 Sticks, dann b * 2 Striche

Versuchen Sie dann, ein oder mehrere '- |' in der Mitte aufgeteilt. Jedes fügt ein festes Inkrement hinzu, das das Zweifache der Startbasis ist und mehrmals wiederholt werden kann. Wir haben also eine Formel mit b = Basis und r = Inkrement-Wiederholungsfaktor

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

Sehen? Der Additionswert erhöht sich schnell und jede Addition besteht nur noch aus 2 Zeichen. Das Basisinkrement gibt jedes Mal 4 weitere Zeichen.

Wenn v und unsere Formel v = b + r * 2 * b gegeben sind, müssen wir 2 ints b und r finden. Ich bin kein Experte für diese Art von Gleichung, aber b = int sqrt (v / 2) ist eine gute Ausgangsvermutung.

Dann haben wir ein r und ein b, die zusammen einen Wert in der Nähe von v ergeben. Wir erreichen v genau durch wiederholtes Inkrementieren (|| -) oder Dekrementieren (| -).

Folgen Sie der gleichen Argumentation für negative Zahlen, leider ist die Formel ähnlich, aber nicht gleich.

edc65
quelle
1

JavaScript, 398710

94 Byte / Zeichen Code

Ich habe eine Lösung gefunden! ... und dann lies Sparrs Antwort und es war genau das gleiche.

Dachte mir, ich würde es trotzdem posten, da js etwas weniger Zeichen zulässt.

Hier ist eine ungekürzte Version des Codes:

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
quelle
1
ok, wenn wir die 398710-Lösungen zum Golfen nutzen, ist das Spiel an! Jemand kommt mit Cjam oder Pyth durch und schlägt uns beide :(
Sparr
1

Python, 398710 (71 Byte)

Einfachste mögliche Lösung, denke ich. Verwendet 4 * n (+/- 1) Zeichen des Stickstacks, um n darzustellen.

def s(n):return'|'*(n*2+1)+'-'*n*2 if n>=0 else'|'*(n*-2)+'-'*(n*-2-1)
Sparr
quelle