Starry to zabawny ezoteryczny język programowania, w którym kod składa się tylko z tego, +*.,`'gdzie rzeczywiste polecenie reprezentowane przez każdy z tych znaków jest określone przez liczbę spacji przed nim. To sprawia, że ​​jest to trudne nawet dla golfowych wyzwań o stałym wyjściu, ponieważ różne polecenia mogą uwzględniać bardzo różną liczbę bajtów. W szczególności literały liczbowe mają jednoznaczną reprezentację, co powoduje, że konieczne jest budowanie większych liczb, operując na mniejszych.

Dlatego wyzwanie polega na napisaniu programu, który może zagrać w golfa w takich programach Starry.

Jak działa Starry?

(Kilka szczegółów pozostało nieokreślonych w esolangach, więc idę z zachowaniem interpretera Ruby .)

Starry to język oparty na stosie, z pojedynczym stosem liczb całkowitych o dowolnej dokładności (który początkowo jest pusty).

Jedynymi znaczącymi postaciami są:

+*.,`'

i spacje. Wszystkie pozostałe znaki są ignorowane. Każda sekwencja spacji, po której następuje jeden z tych spacji, reprezentuje pojedynczą instrukcję. Rodzaj instrukcji zależy od znaku spacji i liczby spacji.

Instrukcje są następujące:

Spaces  Symbol  Meaning
0         +     Invalid opcode.
1         +     Duplicate top of stack.
2         +     Swap top 2 stack elements.
3         +     Rotate top 3 stack elements. That is, send the top stack element
                two positions down. [... 1 2 3] becomes [... 3 1 2].
4         +     Pop and discard top of stack.
n ≥ 5     +     Push n − 5 to stack.
0 mod 5   *     Pop y, pop x, push x + y.
1 mod 5   *     Pop y, pop x, push x − y.
2 mod 5   *     Pop y, pop x, push x * y.
3 mod 5   *     Pop y, pop x, push x / y, rounded towards -∞.
4 mod 5   *     Pop y, pop x, push x % y. The sign of the result matches the sign of y.
0 mod 2   .     Pop a value and print it as a decimal number.
1 mod 2   .     Pop a value and print it as an ASCII character. This throws an error
                if the value is not in the range [0, 255].
n         `     Mark label n.
n         '     Pop a value; if non-zero, jump to label n. 

Zauważ, że interpreter skanuje kod źródłowy w celu znalezienia etykiet przed rozpoczęciem wykonywania, więc można przeskakiwać zarówno do przodu, jak i do tyłu.

Oczywiście Starry ma również komendy wejściowe (przy użyciu ,analogicznej metody .), ale są one nieistotne dla tego wyzwania.

Wyzwanie

Biorąc pod uwagę ciąg, wygeneruj program Starry, który nie pobiera danych wejściowych i drukuje dokładnie ten ciąg do STDOUT.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Możesz założyć, że łańcuch nie ma więcej niż 128 znaków i że będzie się składał tylko z drukowalnych znaków ASCII (punkty kodowe od 0x20 do 0x7E).

Twoje rozwiązanie powinno przetworzyć takie dane w mniej niż 5 minut na rozsądnej maszynie stacjonarnej (istnieje pewna swoboda; jeśli zajmie to jeszcze kilka minut na moim laptopie, nie mam nic przeciwko, ale jeśli zajmie to 15, zdyskwalifikuję to).

Twoje rozwiązanie zostanie przetestowane na kilku różnych ciągach wymienionych poniżej. Twój wynik to całkowita liczba bajtów odpowiednich programów Starry. W przypadku remisu wygrywa najkrótszy metagolfer. Oznacza to, że nie zawracaj sobie głowy graniem własnym kodem, chyba że jest remis (co, jak sądzę, nastąpi tylko w przypadku, gdy możliwe jest optymalne rozwiązanie).

Nie wolno optymalizować kodu pod kątem konkretnych przypadków testowych wymienionych poniżej. W szczególności nie powinieneś tworzyć dla nich ręcznie opracowanych rozwiązań. Optymalizacja w kierunku klas ciągów, których struktura jest podobna do danej ciągów, jest w porządku. Jeśli podejrzewam kogokolwiek o rozwiązania na sztywno, zastrzegam sobie prawo do zastąpienia niektórych lub wszystkich przypadków testowych (ciągami porównywalnych struktur).

Przypadki testowe

Każda linia to osobny przypadek testowy:

Hello, World!
pneumonoultramicroscopicsilicovolcanoconiosis
.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.
Hickory, dickory, dock. The mouse ran up the clock. The clock struck 1. The mouse ran down. Hickory, dickory, dock.
36912059868043514648560046917066768694455682545071266675083273015450033938555319356951628735735013250100789433961153496780296165
bVZ48121347GLtpYnt76CZSxTpMDs6791EJE808077eySXldY162424ddTB90707UupwlWGb63618542VhA252989453TXrWgqGm85899uHOAY2oAKE198GOVUttvW63
7MYxoWBNt180CDHS5xBGvU70HHVB17bh8jYzIIiU6n6g98Rose1nOe8Svcg56nax20q30kT3Ttb2jHl5q2Iuf1vPbjPxm9cyKXwxc0OUK8pr13b2n7U9Y7RwQTc26A1I
n9}unwxVa}[rj+5em6K#-H@= p^X/:DS]b*Jv/_x4.a5vT/So2R`yKy=in7-15B=g _BD`Bw=Z`Br;UwwF[{q]cS|&i;Gn4)q=`!G]8"eFP`Mn:zt-#mfCV2AL2^fL"A

_{Kredyty za drugi przypadek testowy trafiają do Dennisa . Kredyty za czwarty przypadek testowy trafiają do Sp3000.}

Rozwiązanie referencyjne

Oto naprawdę podstawowe rozwiązanie referencyjne w CJam:

q{S5*\iS*'+S'.}%

Możesz uruchomić go tutaj dla całego zestawu testów. Wyniki są następujące:

1233
5240
4223
11110
7735
10497
11524
11392
Total: 62954

Jest to najprostsze możliwe podejście: przesuń punkt kodowy każdego znaku dosłownie, a następnie wydrukuj go. Nie wykorzystuje małych różnic między kolejnymi znakami, drukowania liczb całkowitych, powtarzających się części łańcucha itp. Zostawię to wam.

Uważam, że jest wiele miejsca na ulepszenia. Dla porównania, najkrótszy ręcznie „Witaj, świecie!” ma tylko 169 bajtów.

Ruby, 13461 10997

$s = {};
def shortest a,b=nil
    return $s[[a,b]] if $s[[a,b]]
    l = []
    if b
        if a == b
            return $s[[a,b]] = ""
        elsif a > b
            l.push shortest(a-b)+" *"
            l.push " +   *"+shortest(1,b) if a > 1
            l.push " + *"+shortest(0,b) if a > 0
            l.push "    +"+shortest(b)
        elsif a < b
            l.push " +  *"+shortest(a*a,b) if a*a>a && a*a<=b
            l.push " +*"+shortest(a+a,b) if a+a<=b && a+a>a
            l.push shortest(b-a)+"*"
            l.push " +"+shortest(a,b/a)+"  *" if a>2 && b%a == 0
            l.push " +"+shortest(a,b-a)+"*" if a>1 && b>a*2
        end
    else
        l.push ' '*(a+5)+'+' #if a < 6
        (1..a/2).each {|n|
            l.push shortest(n)+shortest(n,a)
        }
    end
    return $s[[a,b]] = l.min_by{|x|x.length}
end

def starry(str)
    arr = str.bytes.map{|b|
        if b>47 && b<58
            b-48# change digets to numbers
        else
            b
        end
    }

    startNum = (1..128).min_by{|x|arr.inject{|s,y|s + [shortest(x,y).length+2,shortest(y).length].min}+shortest(x).length}
    #one number to be put on the stack at the start.

    code = shortest(startNum)
    code += [
        shortest(arr[0]),
        " +"+shortest(startNum, arr[0])
    ].min_by{|x|x.length}

    arr.each_cons(2) do |a|
        pr = a[0]<10?'.':' .'
        code += [
            pr+shortest(a[1]),
            " +"+pr+shortest(a[0], a[1]),
            pr+" +"+shortest(startNum, a[1])
        ].min_by{|x|x.length}
    end
    code += arr[-1]<10?'.':' .'
end

a = ["Hello, World!",
"pneumonoultramicroscopicsilicovolcanoconiosis",
".oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.",
"Hickory, dickory, dock. The mouse ran up the clock. The clock struck 1. The mouse ran down. Hickory, dickory, dock.",
"36912059868043514648560046917066768694455682545071266675083273015450033938555319356951628735735013250100789433961153496780296165",
"bVZ48121347GLtpYnt76CZSxTpMDs6791EJE808077eySXldY162424ddTB90707UupwlWGb63618542VhA252989453TXrWgqGm85899uHOAY2oAKE198GOVUttvW63",
"7MYxoWBNt180CDHS5xBGvU70HHVB17bh8jYzIIiU6n6g98Rose1nOe8Svcg56nax20q30kT3Ttb2jHl5q2Iuf1vPbjPxm9cyKXwxc0OUK8pr13b2n7U9Y7RwQTc26A1I",
"n9}unwxVa}[rj+5em6K#-H@= p^X/:DS]b*Jv/_x4.a5vT/So2R`yKy=in7-15B=g _BD`Bw=Z`Br;UwwF[{q]cS|&i;Gn4)q=`!G]8\"eFP`Mn:zt-#mfCV2AL2^fL\"A"]
c = a.map{
    |s|
    starry(s).length
}
p c.inject(0){|a,b|a+b}

Metoda starryodpowiada na zadane pytanie.

Wyniki:

230
639
682
1974
1024
1897
2115
2436
Total: 10997

Jak to działa

shortestjest głównym algorytmem. Pobiera jedną liczbę i znajduje najkrótszy sposób, aby umieścić ją na stosie, lub bierze dwie liczby i zwraca kod, aby umieścić drugą na stosie, zakładając, że pierwsza jest już włączona. $sto skrót, który przechowuje wyniki tych operacji do dalszego wykorzystania.

starrypobiera ciąg i dzieli go na tablicę kodów znaków (lub liczb dla skrótów). Rozpoczyna kod od jednej cyfry na dole stosu. Następnie oblicza najkrótszy sposób, w jaki może wygenerować każdy kolejny numer, prawdopodobnie kopiując ostatni numer lub używając liczby umieszczonej na stosie na początku.

Python 3, 17071 11845

from functools import lru_cache
import heapq
import time

cases = r"""
Hello, World!
pneumonoultramicroscopicsilicovolcanoconiosis
.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.
Hickory, dickory, dock. The mouse ran up the clock. The clock struck 1. The mouse ran down. Hickory, dickory, dock.
36912059868043514648560046917066768694455682545071266675083273015450033938555319356951628735735013250100789433961153496780296165
bVZ48121347GLtpYnt76CZSxTpMDs6791EJE808077eySXldY162424ddTB90707UupwlWGb63618542VhA252989453TXrWgqGm85899uHOAY2oAKE198GOVUttvW63
7MYxoWBNt180CDHS5xBGvU70HHVB17bh8jYzIIiU6n6g98Rose1nOe8Svcg56nax20q30kT3Ttb2jHl5q2Iuf1vPbjPxm9cyKXwxc0OUK8pr13b2n7U9Y7RwQTc26A1I
n9}unwxVa}[rj+5em6K#-H@= p^X/:DS]b*Jv/_x4.a5vT/So2R`yKy=in7-15B=g _BD`Bw=Z`Br;UwwF[{q]cS|&i;Gn4)q=`!G]8"eFP`Mn:zt-#mfCV2AL2^fL"A
""".strip().splitlines()

@lru_cache(maxsize=128)
def shortest_m_to_n(m, n):
    if m is None:
        L = []
    else:
        L = [m]

    to_search = [[0, "", L]]
    seen = set()

    while True:
        length, code, stack = heapq.heappop(to_search)

        if len(stack) == 1 and stack[-1] == n:
            return code

        seen.add(tuple(stack))
        options = []

        for i in range(1, 11):
            new_stack = stack[:] + [i]
            new_code = code + ' '*(i+5) + '+'
            options.append([len(new_code), new_code, new_stack])

        if stack:
            new_stack = stack[:] + [stack[-1]]
            new_code = code + " +"
            options.append([len(new_code), new_code, new_stack])

        if len(stack) >= 2:
            x, y = stack[-2:]

            for i, op in enumerate(['+', '-', '*', '//', '%']):
                try:
                    new_elem = eval("{}{}{}".format(x, op, y))
                    new_stack = stack[:-2] + [new_elem]
                    new_code = code + ' '*i + '*'
                    options.append([len(new_code), new_code, new_stack])

                except ZeroDivisionError:
                    pass

        for op in options:
            if tuple(op[2]) in seen or len(op[2]) > 4 or op[2][-1] > 200:
                continue

            heapq.heappush(to_search, op)

def lcs(s1, s2):
    dp_row = [""]*(len(s2)+1)

    for i, c1 in enumerate(s1):
        new_dp_row = [""]

        for j, c2 in enumerate(s2):
            if c1 == c2 and not c1.isdigit():
                new_dp_row.append(dp_row[j] + c1)
            else:
                new_dp_row.append(max(dp_row[j+1], new_dp_row[-1], key=len))

        dp_row = new_dp_row

    return dp_row[-1]

def metagolf(s):
    keep = ""
    split_index = 0

    for i in range(1, len(s)):
        l = lcs(s[:i], s[i:][::-1])
        if len(l) > len(keep):
            keep = l
            split_index = i

    code = []
    stack = []
    keep_ptr = 0
    i = 0

    while i < len(s):
        c = s[i]
        n = ord(c)

        if c in "0123456789":
            code += [" "*(int(c)+5) + "+."]
            i += 1
            continue

        if stack:
            if stack[-1] == n:
                code += [" +", " ."]
            elif len(stack) >= 2 and stack[-2] == n:
                for j in range(len(code)):
                    if code[~j] == " +":
                        code[~j] = ""
                        break

                code += [" +", " ."]
                stack.pop()
            else:
                code += [shortest_m_to_n(stack[-1], n), " +", " ."]
                stack[-1] = n

        else:
            code += [shortest_m_to_n(None, n), " +", " ."]
            stack.append(n)

        while i < split_index and keep[keep_ptr:][:1] == c:
            code += [" +"]
            keep_ptr += 1
            stack.append(n)

        i += 1

    code = "".join(code)

    if code[-4:] == " + .":
        code = code[:-4] + " ."

    return code

total = 0

for case in cases:
    start_time = time.time()

    s = metagolf(case)
    print(len(s), time.time() - start_time)
    total += len(s)
    print(s)
    print('='*50)

print(total)

Odpowiednia funkcja to trafna nazwa metagolf.

Wyniki są następujące:

210
676
684
2007
1463
2071
2204
2530
Total: 11845

Pełną moc można znaleźć tutaj .

Krótkie wyjaśnienie

Wyjaśnię to krótko, ponieważ jest jeszcze wiele rzeczy do poprawienia.

Podstawowy algorytm po prostu patrzy na pary znaków i znajduje optymalny sposób przejścia z jednego znaku do drugiego za pomocą BFS. Cyfry są obecnie wypychane i drukowane natychmiast, choć zostanie to później zmienione.

Trwa również najdłuższa podsekwencja, aby pozostawić kilka elementów na stosie do ponownego wykorzystania później. Nie jest tak dobry jak powtórzenie, ale zapewnia przyzwoite oszczędności.

JavaScript, 25158 23778

Teraz kompatybilny z ES5!

String.prototype.repeat = String.prototype.repeat || function (n) { return Array(n+1).join(this); }

function starrify(x) {
  function c(x){return x.charCodeAt()}
  var char = x[0], result = ' '.repeat(c(char)+5)+'+ + .';
  x=x.slice(1);
  for(var i in x) {
    if (char < x[i]) {
      result += ' '.repeat(c(x[i])-c(char)+5)+'+* + .';
    } else if (char > x[i]) {
      if(c(char)-c(x[i]) < c(x[i])) {
        result += ' '.repeat(c(char)-c(x[i])+5)+'+ * + .';
      } else {
        result += ' '.repeat(c(x[i])+5)+'+ + .';
      }
    } else {
      result += ' + .';
    }
    char = x[i];
  }
  return result;
}

Wyniki:

432
949
2465
3996
1805
3551
5205
5375
Total: 23778

Moim zdaniem dobry początek, ale oczywiście nie skończony. Zamiast tworzyć każdy znak osobno, dodaje lub odejmuje poprzedni kod znaków. Dodam pełne wyjaśnienie, kiedy skończę grać w golfa.