Golf eine Gehirn-Flak-Ganzzahl

28

Ganzzahlen sind mühsam in Brain-Flak darzustellen . Es gibt 8 Betreiber:

()      Evaluates to 1, but does not push anything on any stack
[]      Evaluates to an indeterminate value for the purposes of this question
{}      Removes the top of the stack and evaluates to it
<>      Switches to or back from the alternate stack and evaluates to zero
(foo)   Pushes the value of the expression foo to the stack and evaluates to it
[foo]   Evaluates to the negation of foo
{foo}   Evaluates the expression foo until the top of the stack is zero
<foo>   Evaluates to zero but executes foo anyway

fookann aus mehreren Operatoren bestehen. In diesem Fall werden sie ausgewertet und summiert. Zum Beispiel (()())drückt 2auf den Stapel (und wertet 2auch aus).

Offensichtlich ist der (()...())Mechanismus in Code Golf nicht nützlich, da große Zahlen n*2+2zur Darstellung Bytes benötigen würden . Ihre Herausforderung besteht daher darin, ein Programm oder eine Funktion zu schreiben, die in möglichst wenigen Bytes ein Brain-Flak-Programm ausgibt, das eine bestimmte positive Ganzzahl nauf den aktiven Stapel überträgt. Dieses Programm darf keine Annahmen über den vorhandenen Inhalt der Stapel machen, darf also die Stapel nicht austauschen oder zusätzliche Werte zu den Stapeln hinzufügen oder daraus entfernen.

Obwohl Ihr Programm oder Ihre Funktion in der Lage sein muss, ein funktionierendes Brain-Flak-Programm für alle Eingaben von 1 bis 1.000.000 zurückzugeben, ist der Gewinner das Programm oder die Funktion, die den kleinsten Satz geeigneter Brain-Flak-Programme für alle 1061 Primzahlen zwischen 1.000 und 1.000 generiert 10.000 . Sie sollten die Gesamtgröße Ihrer Ausgaben für diese 1061 Eingaben als Teil Ihrer Einreichung notieren. Ihr Programm oder Ihre Funktion akzeptiert möglicherweise die Ganzzahl und gibt das (Zeichenfolge-) Brain-Flak-Programm in einem der üblichen zulässigen E / A-Formate zurück. Krawatten werden anhand der Größe Ihres Programms oder Ihrer Funktion getrennt.

Neil
quelle
4
Nur als Anmerkung: die Anzahl der gültigen Programme der Länge 2nist 4^n catalan(n).
Undichte Nonne
2
Hmm, ich mag die Herausforderung, aber ich denke, sie sollte mit unbekannten ganzen Zahlen bewertet werden. Andernfalls können die Ganzzahlenprogramme brachial gezwungen und andere Ganzzahlen einfach belassen werden (()()()...()). Wenn Sie nur Primzahlen verwenden, werden möglicherweise einige Optimierungen für Verbundwerkstoffe verpasst.
DJMcMayhem
Auch, warum ist []für diese Herausforderung undefiniert? Ich finde es seltsam, 7 der 8 Operatoren zu implementieren. Wie auch immer, coole Herausforderung, ich fühle mich geehrt, dass jemand eine Herausforderung schreibt, die von meiner eigenen Sprache inspiriert ist!
DJMcMayhem
2
@DJMcMayhem Ich möchte, dass die Leute ihre eigene Punktzahl berechnen können. Alle relevanten Primzahlen sind eine Zahl mehr als eine zusammengesetzte Zahl, daher sollte es viele mögliche Optimierungen geben. Ich möchte auch nicht, dass sich die Leute []in ihrer Antwort auf einen bestimmten Wert von verlassen .
Neil
1
@YetiCGN Die Größe des Skripts gilt nur als "Unentschieden".
Neil

Antworten:

16

Python 2, 59394 59244 58534 58416 58394 58250

Ok hier ist meine Lösung.

import re
import math

cache = {0:"<()>"}

def find(x,i,j):
    return i*((x**2+x)/2)+(j+1)*((x**2-x)/2)

def solve(x, i, j):
    a = (i + j + 1)/2.
    b = (i - j - 1)/2.
    c = -x
    return (-b + math.sqrt(b**2 - 4*a*c))/(2*a)

def size(i,j=0):
    return 4*(i+j)+14

def polynomials(n):
    upperBound = int(4*math.log(n,2))
    i = 0
    answers = []
    while size(i) < upperBound:
        for j in range(i):
            sol = int(solve(n, i-j, j)+.5)
            if find(sol, i-j, j) == n:
                answers.append((sol, i-j, j))
        i += 1
    return answers

def complement(character):
        dict = {"(":")","{":"}","<":">","[":"]",")":"(","}":"{",">":"<","]":"["}
        return dict[character]

def findMatch(snippet, index):
        increment = 1 if snippet[index] in "({<[" else -1
        stack = []
        if snippet[index] in "(){}<>[]":
                stack.append(snippet[index])
        while len(stack) > 0 and index + increment < len(snippet):
                index += increment
                if snippet[index] in "(){}<>[]":
                        if complement(snippet[index]) == stack[-1]:
                                stack = stack[:-1]
                        else:
                                stack.append(snippet[index])
        return index

def isPrime(n):
    return not [0 for x in range(2,int(n**.5)+1) if n%x==0] and n>1

def getPrimeFactors(n):
    return [x for x in range(2,n/2) if n%x==0 and isPrime(x)]

def divHardcode(n,m):
    assert n%m == 0
    assert m != 1
    assert n != 1
    binary = bin(m)[3:]
    return (binary.count("1")+len(binary))*"("+getBF(n/m)+")"*binary.count("1")+binary.replace("1","){}{}").replace("0","){}")

def isTriangular(n):
    #Triangles must be between sqrt(2n) and cbrt(2n)
    if n < 0: return isTriangular(-n)
    for x in range(int((2*n)**(1/3.)),int((2*n)**.5)+1):
        if (x**2+x) == 2*n:
            return True
    return False

def getTriangle(n):
    if n < 0: return -getTriangle(-n)
    #Triangles must be between sqrt(2n) and cbrt(2n)
    for x in range(int((2*n)**(1/3.)),int((2*n)**.5)+1):
        if (x**2+x) == 2*n:
            return x
    #If we don't find one we made a mistake
    assert False

def getSimpleBF(n):
    if n in cache:return cache[n]
    if n < 0:
        # There is room for better solutions here
        return "["+getSimpleBF(-n)+"]"
    elif n == 0:
        return ""
    elif n < 6:
        return "()"*n
    #Non-edge cases
    solutions = []
    factors = getPrimeFactors(n)
    if n >= 78 and isTriangular(n):
        solutions.append(
           min([push(getTriangle(n))+"{({}[()])}{}","<"+push(getTriangle(n)+1)+">{({}[()])}{}"],key=len)
        )
    polynomialSolutions = polynomials(n)
    for polynomial in polynomialSolutions:
        solutions.append("<%s>{%s({}[()])%s}{}"%(push(polynomial[0]),"({})"*polynomial[1],"({})"*polynomial[2]))
        #Mod 3 tricks
    if n % 3 == 2:
       solutions.append(("((%s)()){}{}")%getBF(n/3))
    elif n % 3 == 1:
       solutions.append(("((%s)()()){}{}")%getBF(n/3-1))
    #Basic solutions
    if isPrime(n):
        solutions.append(getSimpleBF(n-1) + "()")
    else:
        #TODO multithread
        solutions += map(lambda m:divHardcode(n,m),factors)
    return min(solutions,key=lambda x:len(unpack(x)))

def getBF(n):
    if n in cache: return cache[n]
    result = getSimpleBF(n)
    index = n - 1
    while index > n-(len(result)/2):
        score = getSimpleBF(index)+getSimpleBF(n-index)
        if len(score) < len(result):result = score
        index -= 1
    index = n + 1
    while index < n+(len(result)/2):
        score = getSimpleBF(index)+getSimpleBF(n-index)
        if len(score) < len(result):result = score
        index += 1
    cache[n] = result
    return result

def unpack(string):
    reMatch = re.match("\(*<",string)
    if reMatch:
        location =reMatch.span()
        return string[location[1]:findMatch(string,location[1]-1)] +string[:location[1]-1] + string[findMatch(string,location[1]-1)+1:]
    return string

def push(n):
    return unpack("("+getBF(n)+")")

def kolmo(string):
    code = push(ord(string[-1]))
    stringVector = map(ord,string)
    for x,y in zip(stringVector[-1:0:-1],stringVector[-2::-1]):
        code = "("+code+getBF(y-x)+")"
    code = code.replace("<()>)",")")
    return code

def kolmo(stringVector):
    code = push(stringVector[-1])
    for x,y in zip(stringVector[-1:0:-1],stringVector[-2::-1]):
        code = "("+code+getBF(y-x)+")"
    code = code.replace("<()>)",")")
    return code


if __name__ == "__main__":
    import primes
    sum = 0
    for prime in primes.nums:
        print push(prime)
        sum += len(push(prime))
    print sum

Die relevante Funktion ist push(n). Um es aufzurufen, drücken Sie einfach auf die Ganzzahl, die Sie darstellen möchten.

Erläuterung

Die Hauptoptimierung, die das Programm durchführt, ist die Multiplikations-Hardcodierung. Die Idee der Multiplikations-Hardcodierung ist ziemlich einfach. Sie drücken die a-Zahl und dann Pop und Push, um einen neuen Wert zu erstellen. Um beispielsweise mit zwei zu multiplizieren, können Sie den folgenden Code verwenden, ((n){})wobei n Code eine bestimmte Zahl erzeugt. Dies funktioniert, weil beide (n)und {}einen Wert von n haben.

Diese einfache Idee kann für größere Zahlen komplexer gestaltet werden. Nehmen wir zum Beispiel 5, es wurde vor einiger Zeit entdeckt, dass der beste Weg, um mit fünf zu multiplizieren, war (((n)){}){}{}. Dieser Code erstellt zwei Kopien von n, multipliziert eins mit 4 und addiert die beiden. Mit der gleichen Strategie mache ich jede Multiplikation basierend auf der Binärdarstellung einer Zahl. Ich werde jetzt nicht näher darauf eingehen, wie das funktioniert, aber ich mache das, indem ich die erste der binären Darstellung abhacke und 0 durch ){}und 1 durch ersetze){}{}. Es stellt dann sicher, dass n die entsprechende Anzahl von Malen verschoben wird, und gleicht alle Klammern aus. (Wenn Sie wissen möchten, wie das gemacht wird, können Sie sich meinen Code ansehen). Wenn Sie wissen möchten, warum dies funktioniert, fragen Sie mich einfach in einem Kommentar. Ich glaube nicht, dass irgendjemand wirklich alle Aktualisierungen meines Beitrags liest, deshalb habe ich die Erklärung weggelassen.

Wenn der Algorithmus versucht, einen Multiplikations-Hardcode zu finden, versucht er alle Primfaktoren einer Zahl. Sie ignoriert zusammengesetzte Faktoren, da zusammengesetzte Faktoren an einer Stelle immer prägnanter ausgedrückt werden könnten als ihre eigenen Primfaktoren. Es ist nicht bekannt, ob dies immer noch zutrifft.

Der andere Byte-Speichermechanismus ist ein Polynomlösungsfinder. Es gibt bestimmte Formen von Polynomen, die sich mit dekrementierenden Schleifen leicht darstellen lassen. Diese Polynome umfassen, ohne darauf beschränkt zu sein, polygonale Zahlen. Diese Optimierung findet Polynome, die in das Formular passen, und erstellt den Code, mit dem sie erstellt werden.

Ausgabe

Paste-Bin

Weizen-Assistent
quelle
"ob n größer oder kleiner als n + 1 ist" ??
Sparr
@ Sparr, ob die Interpretation ngrößer oder kleiner ist alsn+1
Wheat Wizard
Sie sollten die Zeilen von if n % 3 == 2: bis zum Ende dieser Funktion um eine Ebene aufheben .
user202729
13

Brain-Flak, 64664

Probieren Sie es online!

Hier ist mein kommentierter Code

({}<
 ((((()()()()()){}){}){}()) #41
>)
{
 (({})[()()()()()()])
 ([({}<(())>)](<>)){({}())<>}{}<>{}{}<>(({})){(<{}({}<>)>)}{}({}<>)
 {((< #IF
  {} 
  {({}[()]< #FOR
   ((((()()()()()){}){}){}()) #41
   (({})[()])                 #40
  >)}{}
 >))}{}
 (({}))
 #MOD2
 {(<
  ({}<(())>)({<({}[()]<>)><>(()[{}])<><({}<>)>}{}<({}<>)><>)<>({}<>)
  {((<{}({}< #IF
   {}
   (((()()()()())({})({})({}){})({})({})({}){})  #125
   (({})[()()])                                  #123
   ((((()()()()()){}){}){}())                    #41
   <>
   ((((()()()()()){}){}){})                      #40
   <>
   >)

  >))}{}{}
 >)}{}
 #MOD2 (number 2)
 (({}))
 ({}(())){({}[()]<>)<>(()[{}])<>({}<>)}{}
 (({})<([{}]{})>)
 {
  ({}[()]<<>
    ((((()()()()()){}){}){}) #40
    (({})())                 #41
   <>>)
 }{}
}{}
<>{({}<>)<>}<>((((()()()()()){}){}){})

Erläuterung

Dies implementiert ab sofort nur zwei Regeln:

  • Wenn n durch zwei teilbar ist, wird zurückgegeben (n/2){}

  • Wenn n nicht durch zwei teilbar ist, wird zurückgegeben n-1()

Außerdem werden alle Zahlen kleiner als 6 hartcodiert.

Weizen-Assistent
quelle
Scheint, als würde eine Prüfung der Teilbarkeit durch drei die Punktzahl um einiges verringern
ASCII
@ ASCII-only Ich habe es tatsächlich implementiert und es hat die Byteanzahl erhöht . Ich arbeite daran, eine intelligentere Version der Teilbarkeit durch drei zu implementieren.
Weizen-Zauberer
Ok, benutze Brain-Flak, um ein Programm zu erstellen, das Brain-Frak-Zahlen erzeugt. Nett.
Draco18s
10

Perl, 59222 59156 58460 Zeichen

  • n() (11322660 Zeichen)
  • (n){}() (64664 Zeichen)
  • ((n)){}{} (63610 Zeichen)
  • ((n)()){}{} (63484 Zeichen) - Dies ist eine neuartige Berechnung
  • (n){({}[()])}{} (60748 Zeichen)
  • n[m] (62800 Zeichen)
  • (n){m({}[l])}{} (58460 Zeichen) - Dies ist eine neuartige Berechnung

Die Formel für diese letzte Berechnung lautet n(n/l+1)/2+mn/l. Ich habe einige andere Berechnungen versucht, aber sie sind für die angegebene Ausgabe nicht mehr hilfreich. Das Programm generiert tatsächlich alle Werte bis 9999, listet dann aber die angegebenen Primzahlen und deren Gesamtlänge auf.

@primes = (<list of the 4-digit prime numbers here>);
@numbers = ();
for ($i = 1; $i < 10000; $i++) {
  $numbers[$i] = "()" x $i; # default calculation
}
for ($i = 2; $i < 10000; $i++) {
  for ($j = 1; $j < 8; $j++) {
    &try($i, "$numbers[$i+$j]\[$numbers[$j]]");
  }
  &try($i + 1, "$numbers[$i]()");
  &try($i * 2, "($numbers[$i]){}");
  &try($i * 3, "(($numbers[$i])){}{}");
  &try($i * 3 + 2, "(($numbers[$i])()){}{}");
  for ($l = 1; $l * $l < $i; $l++) { 
    unless ($i % $l) { 
      for ($j = 0; ($k = (($i + $j + $j) * $i / $l + $i) / 2) < 10000; $j++) { 
        &try($k, "($numbers[$i]){$numbers[$j]({}[$numbers[$l]])}{}");
      } 
    } 
  } 
}
$len = 0;
foreach (@primes) {
  print "($numbers[$_])\n";
  $len += 2 + length $numbers[$_];
}
print "$len\n";
sub try {
  ($n, $s) = @_;
  $numbers[$n] = $s if (length($numbers[$n]) > length $s);
}
Neil
quelle
Könnten Sie einen Link zur Ausgabe bereitstellen?
DJMcMayhem
@DJMcMayhem Hoppla, ich habe versehentlich meine Liste der Primzahlen beschädigt und meine Zeichenanzahl ungültig gemacht.
Neil
@Linus ((X) ()) {} {} drückt X, addiert dann 1, drückt das Ergebnis und fügt dann X + 1 und X ein. Insgesamt 3X + 2. Ich glaube, ich habe die andere Formel bei Try It Online ausprobiert, aber ich kann nachprüfen, ob Sie möchten.
Neil
@Neil Mein Fehler ... Diese sehen gut aus, aber was genau korrumpiert dann deine Primzahlen?
Linus
1
@Neil Ich erhalte 58158, wenn ich hinzufüge &try($i * $i, "$numbers[$i]{({})({}[()])}{}");, was zu 58032 hinuntergeht, wenn ich auch hinzufüge &try((3 * $i * $i - $i) / 2, "$numbers[$i]{({})({}[()])({})}{}");(quadratische / fünfeckige Zahlen) - es ist von hier
Nur ASCII
5

Python, 59136 58676 Zeichen

Brainflak Nummer Golffunktion:

m=11111
R=range(0,m)
R[1]="()"
R[2]="()()"
l=2
def a(v,r):
 if v>0 and v<m:
  if isinstance(R[v],int) or len(r)<len(R[v]):
   R[v]=r
   if v<R[0]:
    R[0]=v
def s(v,k):
 S=0
 while v>0:
  S+=v
  v-=k
 return S
p=lambda r:"("+r+")"
w=lambda r:"{({}["+r+"])}{}"
def q(r,v):
 for i in range(1,v):
  r="("+r+")"
 for i in range(1,v):
  r+="{}"
 return r
def e(r,v,k):
 for i in range(0,k):
  r=q(r,v)
 return r
while l<m:
 R[0]=l+1
 a(l*2,q(R[l],2)) 
 a(l*3,q(R[l],3))
 a(l*5,q(R[l],5))
 a(l*7,q(R[l],7))
 for i in range(1,l):
  a(l+i,R[l]+R[i])
  a(l-i,R[l]+"["+R[i]+"]")
  if l%i==0:
   t=s(l-i,i)
   a(s(l,i),p(R[l])+w(R[i]))
   a(l+2*t,p(R[l])+q(w(R[i]),2))
   a(l+4*t,p(R[l])+e(w(R[i]),2,2))
   a(l+8*t,p(R[l])+e(w(R[i]),2,3))
   a(l+16*t,p(R[l])+e(w(R[i]),2,4))
   a(l+32*t,p(R[l])+e(w(R[i]),2,5))
   a(l+64*t,p(R[l])+e(w(R[i]),2,6))
   a(l+128*t,p(R[l])+e(w(R[i]),2,7))
   a(l+3*t,p(R[l])+q(w(R[i]),3))
   a(l+9*t,p(R[l])+e(w(R[i]),3,2))
   a(l+27*t,p(R[l])+e(w(R[i]),3,3))
   a(l+5*t,p(R[l])+q(w(R[i]),5))
   a(l+6*t,p(R[l])+q(q(w(R[i]),3),2))
   a(l+10*t,p(R[l])+q(q(w(R[i]),5),2))
   a(l+15*t,p(R[l])+q(q(w(R[i]),5),3))
   a(l+12*t,p(R[l])+q(q(q(w(R[i]),3),2),2))
   a(l+18*t,p(R[l])+q(q(q(w(R[i]),3),3),2))
   a(l+20*t,p(R[l])+q(q(q(w(R[i]),5),2),2))
   a(l+24*t,p(R[l])+q(q(q(q(w(R[i]),3),2),2),2))
   a(l+36*t,p(R[l])+q(q(q(q(w(R[i]),3),3),2),2))
   a(l+40*t,p(R[l])+q(q(q(q(w(R[i]),5),2),2),2))
 l=R[0]
f=lambda v:p(R[v])

Primzahl-Iteration:

def isPrime(v):
 i=2
 while i*i<=v:
  if v%i==0:
   return False
  i+=1
 return True

for i in range(1000,10000):
 if isPrime(i):
  print f(i)

Ausgabe:

Pastebin

Erläuterung:

Wir füllen eine Liste R der Brain-Flak-Repräsentation vor, die einzelne ganze Zahlen über einen größeren als den erforderlichen Bereich [1, m -1] auswertet , um unsere Funktion f zu definieren . Die Darstellungen werden gebildet, indem die niedrigste unbenutzte Darstellung (mit l indiziert ) genommen und viele neue Darstellungen daraus gebildet werden, wobei nur die kürzeste beibehalten wird. Die niedrigste ungenutzte Darstellung setzt voraus , dass alle Nummer 1 bis l eine Darstellung zugeordnet wurde und daß diese Darstellungen sind bereits verwendet worden , um neue Zahlen zu erzeugen. Wenn ein Wert kleiner als l eine kürzere Darstellung erhält, müssen wir zurückgehen und Zahlen reproduzieren, die an diesem Punkt beginnen. Die Funktion f Erzeugt ein Programm, das die Nummer durch Hinzufügen von Klammern im Stapel speichert.

Ich kannte keinen Brainflak, als ich damit anfing, und ich schätze die Antwort von Eamon Olive sehr, dass er die Formel für Dreieckszahlen aufgezeigt hat. Meistens habe ich die Summe verallgemeinert und mich unerbittlich darum gekümmert, Summen und Differenzen zu überprüfen. Das Hinzufügen vieler Vielfacher von Summen hatte einen großen Effekt.

Für diejenigen, die sich interessieren, ist hier der Scratch-Code, mit dem ich herausgefunden habe, welche Formeln sich gelohnt haben.

Darstellungsformeln:

  1. Multiplikation mit kleinen Primzahlen:
    (X){}
    ((X)){}{}
    ((((X)))){}{}{}{}
    ((((((X)))))){}{}{}{}{}{}
  2. Zusatz X + Y :
    XY
  3. Subtraktion X - Y :
    X[Y]
  4. Summation bis einschließlich X von Inkrement Y :
    (X){({}[Y])}{}
  5. Vielfache von Summierungen zu X von Inkrement Y plus X :
    (X)({({}[Y])}{}){}
    (X)(({({}[Y])}{})){}{}
    (X)(({({}[Y])}{}){}){}
    etc ...
Linus
quelle
Ich dachte, 5 * wäre nicht hilfreich, aber jetzt werden 10 Zeichen in meiner Antwort gespeichert. Ich dachte, ich hätte es mit diesen Summierungen versucht, aber ich werde es noch einmal überprüfen!
Neil
Summierungen von Inkrementen plus Vielfachen sparen mir weitere 46 Bytes, und selbst dann muss ich dreimal nachspülen und wiederholen, um sie alle einzufangen.
Neil
Es stellt sich heraus, dass ich, wenn ich Subtraktion verwende, nicht wieder 5 * verwende.
Neil
4

Lua 5,3, 57522

Ich habe tatsächlich angefangen, daran zu arbeiten, als die Frage veröffentlicht wurde, habe sie aber bis zum Brain-Flak-Jubiläum vergessen.

-- 64 gives all results through 10000 (should run in about 1 second)
-- 78 gives all results through 100000 (should run in about 20 seconds)
-- 90 gives all results through 1000000 (should run in about 200 seconds)
-- Note: Timings may not be accurate, as the are not updated every time new cases are added.

local k_max_len = 64
local k_limit = 10000

local pre = os.clock()

local function compute_multiplier_helper(prefix, suffix, m)
  if m == 2 then
    prefix[#prefix + 1] = "("
    suffix[#suffix + 1] = "){}"
  elseif m % 2 == 0 then
    prefix[#prefix + 1] = "("
    compute_multiplier_helper(prefix, suffix, m // 2)
    suffix[#suffix + 1] = "){}"
  else
    suffix[#suffix + 1] = ")"
    compute_multiplier_helper(prefix, suffix, m - 1)
    prefix[#prefix + 1] = "("
    suffix[#suffix + 1] = "{}"
  end
end

local function compute_multiplier(m)
  local prefix = {}
  local suffix = {}
  compute_multiplier_helper(prefix, suffix, m)
  return table.concat(prefix), table.concat(suffix)
end

local multipliers = {}
for m = 2, k_limit do
  -- Including all factors, not just primes.
  -- This did improve a few numbers, although none in the ppcg test set.
  local prefix, suffix = compute_multiplier(m)
  local mult = {prefix = prefix, suffix = suffix, m = m, cost = #prefix + #suffix}
  table.insert(multipliers, mult)
end
table.sort(multipliers, function(a, b) return a.cost < b.cost end)

local poly_multipliers = {}
poly_multipliers[1] = {m = 1, s = "({})", l = 4}
for m = 2, k_limit do
  local prefix, suffix = compute_multiplier(m)
  local s = prefix .. "({})" .. suffix
  assert(#s <= 4 * m)
  poly_multipliers[m] = {m = m, s = s, l = #s}
end
poly_multipliers[k_limit + 1] = {m = 0, s = "", l = 0}

table.sort(poly_multipliers, function(a, b) return a.l < b.l end)

local pcache = {}
local plen_cache = {}

local function register_push(prefix, suffix, value, pvalue)
  if value > 1500000 or value < -1500000 then return end
  local old_res = pcache[value]
  if old_res == nil then
    local res = {prefix = prefix, suffix = suffix, value = value, pvalue = pvalue}
    pcache[value] = res
    local length = #prefix + #suffix
    local lcache = plen_cache[length]
    if lcache == nil then
      lcache = {}
      plen_cache[length] = lcache
    end
    lcache[#lcache + 1] = res
  end
end

local function get_pushes(length)
  return ipairs(plen_cache[length] or {})
end

register_push("", "()", 1, 0)
register_push("", "<()>", 0, 0)

local function triangle(n)
  return (n * (n + 1)) // 2
end

local function process(length)
  -- basic
  for _, res in get_pushes(length - 2) do
    register_push(res.prefix, res.suffix .. "()", res.value + 1, res.pvalue)
    register_push(res.prefix, "[" .. res.suffix .. "]", -res.value, res.pvalue)
  end

  -- multiplication by constant (precomputed)
  for _, mult in ipairs(multipliers) do
    local cost = mult.cost
    if length - cost >= 4 then
      local m, prefix, suffix = mult.m, mult.prefix, mult.suffix
      for _, pus in get_pushes(length - cost) do
        local name = prefix .. pus.suffix .. suffix
        register_push(pus.prefix, name, pus.value * m, pus.pvalue)
      end
    else
      break
    end
  end

  -- residue 2 mod3 trick (Neil)
  -- ((n)()){}{}
  --  (n)        -- push n
  -- (   ())     -- push n + 1
  --        {}{} -- (n + 1) + (n + 1) + n
  if length - 10 >= 2 then
    for _, res in get_pushes(length - 10) do
      local name = "((" .. res.suffix .. ")()){}{}"
      register_push(res.prefix, name, 3 * res.value + 2, res.pvalue)
    end
  end

  -- residue 1 mod3 trick (Wheat Wizard)
  -- ((n)()()){}{}
  --  (n)          -- push n
  -- (   ()())     -- push n + 2
  --          {}{} -- (n + 2) + (n + 2) + n
  -- not useful, but fast...
  if length - 12 >= 2 then
    for _, res in get_pushes(length - 12) do
      local name = "((" .. res.suffix .. ")()()){}{}"
      register_push(res.prefix, name, 3 * res.value + 4, res.pvalue)
    end
  end

  -- residue 2 mod5 trick (tehtmi)
  -- (((n)){}()){}{}
  --   (n)           -- push n
  --  (   )          -- push n
  -- (     {}())     -- push 2n + 1
  --            {}{} -- (2n + 1) + (2n + 1) + n
  -- [[
  if length - 14 >= 2 then
    for _, res in get_pushes(length - 14) do
      local name = "(((" .. res.suffix .. ")){}()){}{}"
      register_push(res.prefix, name, 5 * res.value + 2, res.pvalue)
    end
  end
  -- ]]

  -- residue 4 mod5 trick (tehtmi)
  -- (((n)()){}){}{}
  --   (n)           -- push n
  --  (   ())        -- push n + 1
  -- (       {})     -- push 2n + 2
  --            {}{} -- (2n + 2) + (2n + 2) + n
  -- [[
  if length - 14 >= 2 then
    for _, res in get_pushes(length - 14) do
      local name = "(((" .. res.suffix .. ")()){}){}{}"
      register_push(res.prefix, name, 5 * res.value + 4, res.pvalue)
    end
  end
  -- ]]

  -- residue 6 mod7 trick (tehtmi)
  -- ((((n)())){}{}){}{}
  --    (n)              -- push n
  --   (   ())           -- push n + 1
  --  (       )          -- push n + 1
  -- (         {}{})     -- push 3n + 3
  --                {}{} -- (3n + 3) + (3n + 3) + n
  -- [[
  if length - 18 >= 2 then
    for _, res in get_pushes(length - 18) do
      local name = "((((" .. res.suffix .. ")())){}{}){}{}"
      register_push(res.prefix, name, 7 * res.value + 6, res.pvalue)
    end
  end
  --]]

  -- residue 4 mod7 trick (tehtmi)
  -- ((((n))()){}{}){}{}
  --    (n)              -- push n
  --   (   )             -- push n
  --  (     ())          -- push n + 1
  -- (         {}{})     -- push 3n + 2
  --                {}{} -- (3n + 2) + (3n + 2) + n
  -- [[
  if length - 18 >= 2 then
    for _, res in get_pushes(length - 18) do
      local name = "((((" .. res.suffix .. "))()){}{}){}{}"
      register_push(res.prefix, name, 7 * res.value + 4, res.pvalue)
    end
  end
  --]]

  -- residue 2 mod7 trick (tehtmi)
  -- ((((n))){}{}()){}{}
  --    (n)              -- push n
  --   (   )             -- push n
  --  (     )            -- push n
  -- (       {}{}())     -- push 3n + 1
  --                {}{} -- (3n + 1) + (3n + 1) + n
  -- [[
  if length - 18 >= 2 then
    for _, res in get_pushes(length - 18) do
      local name = "((((" .. res.suffix .. "))){}{}()){}{}"
      register_push(res.prefix, name, 7 * res.value + 2, res.pvalue)
    end
  end
  --]]

  -- triangle numbers (?)
  --(n){({}[()])}{}
  --(n)              -- push n
  --   {        }    -- sum and repeat
  --    (      )     -- push
  --     {}[()]      -- top - 1
  --             {}  -- pop 0
  if length - 14 >= 2 then
    for _, res in get_pushes(length - 14) do
      if res.value > 0 then
        local code = "{({}[()])}{}"
        register_push(res.prefix .. "(" .. res.suffix .. ")", code, triangle(res.value - 1), res.pvalue + res.value)
        register_push(res.prefix, "(" .. res.suffix .. ")" .. code, triangle(res.value), res.pvalue)
        register_push("", res.prefix .. "(" .. res.suffix .. ")" .. code, triangle(res.value) + res.pvalue, 0)
      end
    end
  end

  -- negative triangle numbers (tehtmi)
  --(n){({}())}{}
  --(n)            -- push n
  --   {      }    -- sum and repeat
  --    (    )     -- push
  --     {}()      -- top + 1
  --           {}  -- pop 0
  if length - 12 >= 2 then
    for _, res in get_pushes(length - 12) do
      if res.value < 0 then
        local code = "{({}())}{}"
        register_push(res.prefix .. "(" .. res.suffix .. ")", code, -triangle(-res.value - 1), res.pvalue + res.value)
        register_push(res.prefix, "(" .. res.suffix .. ")" .. code, -triangle(-res.value), res.pvalue)
        register_push("", res.prefix .. "(" .. res.suffix .. ")" .. code, -triangle(-res.value) + res.pvalue, 0)
      end
    end
  end

  -- cubic (tehtmi)
  -- (n){(({}[()])){({}[()])}{}}{}
  -- (n^3-3*n^2+8*n-6)/6
  -- (-6 + n*(8 + n*(-3 + n)))/6
  --[[ superceded by negative cubic because 
       it is the same cost of -ncubic(-n)
  if length - 28 >= 2 then
    for _, res in get_pushes(length - 28) do
      if res.value > 0 then
        local code = "{(({}[()])){({}[()])}{}}{}"
        local v = res.value + 1
        v = (-6 + v*(8 + v*(-3 + v)))//6
        register_push(res.prefix .. "(" .. res.suffix .. ")", code, v - res.value, res.pvalue + res.value)
        register_push(res.prefix, "(" .. res.suffix .. ")" .. code, v, res.pvalue)
        register_push("", res.prefix .. "(" .. res.suffix .. ")" .. code, v + res.pvalue, 0)
      end
    end
  end
  --]]

  -- negative cubic (tehtmi)
  -- (n){(({}())){({}())}{}}{}
  -- (n^3-3*n^2+8*n-6)/6
  -- (-6 + n*(8 + n*(-3 + n)))/6
  -- [[
  if length - 24 >= 2 then
    for _, res in get_pushes(length - 24) do
      if res.value < 0 then
        local code = "{(({}())){({}())}{}}{}"
        local v = -res.value + 1
        v = (-6 + v*(8 + v*(-3 + v)))//6
        v = -v
        register_push(res.prefix .. "(" .. res.suffix .. ")", code, v - res.value, res.pvalue + res.value)
        register_push(res.prefix, "(" .. res.suffix .. ")" .. code, v, res.pvalue)
        register_push("", res.prefix .. "(" .. res.suffix .. ")" .. code, v + res.pvalue, 0)
      end
    end
  end
  --]]

  -- polynomial (Wheat Wizard, modified by tehtmi)
  -- <(n)>{A({}[()])B}{} where A, B are ({})({})({})... repeated a, b times
  -- <(n)>                -- push n (without adding)
  --      {          }    -- repeat until top is zero
  --       A              -- top * a
  --        ({}[()])      -- top = top - 1; += top - 1
  --                B     -- (top - 1) * b
  --                  {}  -- pop 0
  -- triangular numbers are with a = b = 0
  -- from B and base:
  -- (n - 1) * (B + 1) * (n - 2) * (B + 1) * ...
  -- (B + 1) * (1 + ... + n - 1)
  -- (B + 1) * n * (n - 1) / 2
  -- from A:
  -- n * A + (n - 1) * A + ...
  -- A * (1 + ... n)
  -- A * (n + 1) * n / 2
  -- total: (B + 1) * n * (n - 1) / 2 + A * (n + 1) * n / 2
  --        [(A + B + 1) * n^2 + (A - B - 1) * n] / 2
  -- S := 4 * (A + B)
  -- [[
  if length - 18 >= 2 then
    for S = 4, length - 14, 4 do
      for _, res in get_pushes(length - 14 - S) do
        if res.value > 0 then
          for _, A in ipairs(poly_multipliers) do
            if A.l > S then
              break
            end
            for _, B in ipairs(poly_multipliers) do
              if A.l + B.l < S then
                -- continue
              elseif A.l + B.l > S then
                break
              else
                local a = A.m
                local b = B.m

                local logic = "{" .. A.s .. "({}[()])" .. B.s .. "}{}"
                local v = res.value
                v = ((a + b + 1) * v * v + (a - b - 1) * v) // 2
                register_push(res.prefix .. "(" .. res.suffix .. ")", logic, v, res.pvalue + res.value)
                register_push(res.prefix, "(" .. res.suffix .. ")" .. logic, v + res.value, res.pvalue)
                register_push("", res.prefix .. "(" .. res.suffix .. ")" .. logic, v + res.value + res.pvalue, 0)
              end
            end
          end
        end
      end
    end
  end
  --]]

  -- negative polynomial (tehtmi)
  -- <(n)>{A({}())B}{}
  -- [[
  if length - 16 >= 2 then
    for S = 4, length - 12, 4 do
      for _, res in get_pushes(length - 12 - S) do
        if res.value < 0 then
          for _, A in ipairs(poly_multipliers) do
            if A.l > S then
              break
            end
            for _, B in ipairs(poly_multipliers) do
              if A.l + B.l < S then
                -- continue
              elseif A.l + B.l > S then
                break
              else
                local a = A.m
                local b = B.m

                local logic = "{" .. A.s .. "({}())" .. B.s .. "}{}"
                local v = -res.value
                v = ((a + b + 1) * v * v + (a - b - 1) * v) // -2

                register_push(res.prefix .. "(" .. res.suffix .. ")", logic, v, res.pvalue + res.value)
                register_push(res.prefix, "(" .. res.suffix .. ")" .. logic, v + res.value, res.pvalue)
                register_push("", res.prefix .. "(" .. res.suffix .. ")" .. logic, v + res.value + res.pvalue, 0)
              end
            end
          end
        end
      end
    end
  end
  --]]

  -- addition
  -- [[
  if length >= 4 then
    for part1 = 4, length // 2, 2 do
      for _, res1 in get_pushes(part1) do
        for _, res2 in get_pushes(length - part1) do
          register_push(res2.prefix .. res1.prefix, res1.suffix .. res2.suffix, res1.value + res2.value, res1.pvalue + res2.pvalue)
        end
      end
    end
  end
  --]]

  -- pseudo-exponentiation (tehtmi)
  -- (n)<>(m){({}[()])<>(({}){})<>}{}<>{}
  -- (n)<>(m)                             -- push n and m on opposite stacks
  --         {                    }       -- sum and repeat
  --          ({}[()])                    -- top(m) - 1
  --                  <>(({}){})<>        -- n = 2*n; += n
  --                               {}     -- pop 0
  --                                 <>   -- swap to result
  --                                   {} -- pop and add n
  -- [[
  if length - 34 >= 4 then
    local subl = length - 34
    for part1 = 2, subl - 2, 2 do
      for _, res2 in get_pushes(part1) do
        local b = res2.value
        if b > 0 and b < 55 then -- overflow could be a problem, so bound...
          for _, res1 in get_pushes(subl - part1) do
            -- 2n + 4n + 8n + ... + (2^m)*n + 2^m * n
            -- n( 2 + 4 + 8 + .. 2^m + 2^m)
            -- n( 3 * 2^m - 2 )
            local a = res1.value
            local body = "(" .. res1.suffix .. ")<>" .. res2.prefix .. "(" .. res2.suffix .. "){({}[()])<>(({}){})<>}{}<>{}"
            local v = a * (3 * (1 << b) - 2) + b * (b - 1) // 2 + a + b + res2.pvalue
            register_push(res1.prefix, body, v, res1.pvalue)
            register_push("", res1.prefix .. body, v + res1.pvalue, 0)
          end
        end
      end
    end
  end
  --]]
end

--print(os.clock(), "seconds (startup)")

local start = os.clock()
for i = 2, k_max_len - 2, 2 do
  --print(i)
  process(i)
end

plen_cache = nil

local final = {}
for i = 1, k_limit do
  if pcache[i] ~= nil then
    final[i] = pcache[i].prefix .. "(" .. pcache[i].suffix .. ")"
  end
end

pcache = nil

-- hard coded to 10000 for ppcg test
local sieve = {}
for i = 1, 10000 do sieve[i] = true end
for i = 2, 10000 do
  for j = i * i, 10000, i do
    sieve[j] = false
  end
end

--print(os.clock() - start, "seconds (calculation)")

--local bf = require("execute2")

local count = 0
local sum = 0
local sum2 = 0
local maxlen = 0
local pcount = 0
for i = 1, k_limit do
  local res = final[i]
  final[i] = nil
  --print(i, #res, res)
  --local ev = res and bf.eval1(bf.compile(res)) or -1; assert( res == nil or ev == i, string.format("Failed %d %s %d", i, res or "", ev))
  if sieve[i] and i > 1000 then
    sum = #res + sum
    pcount = pcount + 1
  end
  if res then
    sum2 = #res + sum2
    maxlen = math.max(maxlen, #res)
    count = count + 1
  end
end
print("sum", sum)
--print("coverage", count / k_limit, "missing", k_limit - count)
--print("sum2", sum2)
--print("maxlen", maxlen)
assert(pcount == 1061)

Eine ähnliche Idee wie bei den anderen Antworten, bei denen bekanntermaßen nützliche Funktionen zum Aufbau größerer Zahlen aus guten Darstellungen einfacherer Zahlen verwendet werden.

Ein Unterschied besteht darin, dass ich Teilprobleme nicht in Form kleinerer Zahlen, sondern in Form von Zahlen mit kürzeren Darstellungen löse. Ich denke, dies macht es eleganter, negative Zahlen zu nutzen und den Fall zu behandeln, in dem kleinere Zahlen als größere Zahlen dargestellt werden.

Der Versuch, alle Zahlen zu finden, die in einer bestimmten Größe dargestellt werden können, und der Versuch, eine bestimmte Zahl so kurz wie möglich darzustellen, vereinfacht tatsächlich bestimmte Berechnungen. Anstatt eine Formel in umgekehrter Reihenfolge zu bearbeiten, um festzustellen, ob sie auf eine Zahl angewendet werden kann, kann die Formel vorwärts bearbeitet und auf jede Zahl angewendet werden.

Ein weiterer Unterschied besteht darin, dass bekannte Lösungen in zwei Teilen gespeichert werden - einem (optionalen) "Präfix" und einem "Suffix" (eher wie ein Infix). Es wird erwartet, dass die Bewertung des Präfixes bei der Berechnung der angegebenen Zahl ignoriert wird. Das Präfix enthält lediglich Code, der das auszuführende Suffix festlegt (in der Regel durch Verschieben eines oder mehrerer Elemente in den Stapel). So kann mit einem Präfix und einem Suffix die entsprechende Nummer auf den Stapel geschoben werden prefix(suffix).

Diese Aufteilung löst im Grunde das gleiche Problem wie die unpackFunktion in der Antwort des Weizen-Assistenten. Anstatt Code <...>nur umzubrechen, um dies später rückgängig zu machen, wird dieser Code einfach zum Präfix hinzugefügt.

In einigen Fällen wird das Präfix tatsächlich ausgewertet (hauptsächlich für die Pseudoexponentierungsoperation), sodass seine Bewertung ebenfalls gespeichert wird. Dies ist jedoch kein großes Problem, da der Generator nicht versucht, bestimmte Zahlen zu konstruieren. Es scheint theoretisch zu implizieren, dass es zwei Codeteile mit der gleichen Länge und der gleichen Anzahl geben könnte, die aufgrund unterschiedlicher Präfixbewertungen nicht redundant im Cache wären. Ich habe mich jedoch nicht darum gekümmert, das zu berücksichtigen, da es (zumindest in diesem Bereich) nicht sehr wichtig zu sein scheint.

Ich stelle mir vor, es wäre einfach, die Byteanzahl durch Hinzufügen weiterer Fälle zu verringern, aber ich habe im Moment genug.

Ich bin auf 1000000 gelaufen, habe aber nur die Vernunft auf 100000 überprüft.

Pastebin der Ausgabe für gegebene Primzahlen.

tehtmi
quelle
Was machen k_limitund k_max_lentun? Ich bin nicht sicher, ob ich den Header verstehe.
Weizen-Assistent
1
Anstatt zu versuchen, bestimmte Zahlen zu berechnen, berechne ich alle nützlichen Programme (dh nicht zu große Zahlen kürzer als jedes andere gefundene Programm) bis zu einer bestimmten Länge k_max_len. Es konnte genauso leicht überprüft werden, ob alle von Ihnen nach der Verarbeitung der einzelnen Längen angeforderten Zahlen gefunden wurden, aber es war für mich hilfreich, die maximale Länge während des Tests einschränken zu können, damit das Programm schneller ausgeführt werden konnte. (Das Verarbeiten größerer Längen kann sehr langsam sein.) k_limitDies ist im Grunde der Eingabeparameter - er gibt Programme für Zahlen bis zu diesem Wert aus - vorausgesetzt, er ist k_max_lengroß genug, um sie zu finden.
Tehtmi
4

Rubin, 60246 Bytes

$brain_flak = Hash.new{|h, k|
    a = []
    a.push "()"*k
    if k > 1
        if k > 10
            # Triangle Numbers:
            n = (Math.sqrt(1+8*k).to_i-1)/2
            if (n*n+n)/2 == k
                a.push "("+h[n]+"){({}[()])}{}" 
                a.push  h[n+n]+")({({}[()])}{}"
            end
        end
        (k**0.51).to_i.downto(2){|i|
            # multiplication:
            if k%i==0
                a.push "("*(i-1) + h[k/i] + ")"*(i-1)+"{}"*(i-1)

            end
        }
        (k/2).downto(1){|i|
            # Addition
            a.push h[k-i] + h[i]
        }
    end

    h[k] = a.min_by{|x|x.length}
}
$brain_flak[0] = "<><>"

def get_code_for (i)
  "(#{$brain_flak[i]})"
end

Ich benutze einen Hash. Ich finde den besten Golf für eine gegebene Zahl und benutze die kleineren, um die größeren zu finden.

Rekursive Hashes machen so viel Spaß!

MegaTom
quelle
2

Python, 64014 Zeichen

Ich wusste vor dieser Herausforderung nichts über Brainflak und habe nur ein bisschen an Tryitonline herumgespielt, sodass es offensichtliche Abkürzungen geben könnte, die ich verpasst habe. Dies ist eine recht langweilige Lösung, bei der nur die Eingabe in x=x/2+x%2oder aufgeteilt wird x=x/3+x%3, je nachdem, welcher Wert kürzer ist.

k=lambda x:"(("+o(x/3)+")){}{}"+(x%3)*"()"if x>3else"()"*x
m=lambda x:"("+o(x/2)+"){}"+(x%2)*"()"if x>6else"()"*x
o=lambda x:min(k(x),m(x),key=len)
b=lambda x:"("+o(x)+")"

Nenne es so: b(42)

Ausgabe auf Pastebin

KarlKastor
quelle
1

Lua, 64664 Bytes

Programm druckt die Gesamtlänge der Programme und des Programms für die 203. Primzahl (es gibt eine Zeile, die Sie ändern können, um die zu druckende Zeile zu ändern, oder eine Zeile aus dem Kommentar entfernen, um alle Programme zu drucken).

Im Moment ist die einzige Optimierung x = 2 * n + 1

Hoffentlich habe ich Zeit, weitere Optimierungen hinzuzufügen, um die Punktzahl zu senken.

local primeS = [[<INSERT PRIMES HERE>]]

local primes = {}

for num in primeS:gmatch("%d+") do
    table.insert(primes, num+0)
end

local progs = {}
progs[0] = ""
progs[1] = "()"
progs[2] = "()()"

local function half(n)
    if progs[n] then return progs[n] end
    local p = ""
    local div = math.floor(n/2)
    local rem = n%2 == 1 and "()" or ""
    return "("..progs[div].."){}"..rem
end

for i = 3, 10000 do

    local bin = half(i)

    progs[i] = progs[i-1] .. "()"

    if #bin < #progs[i] then
        progs[i] = bin
    end

    if i % 1000 == 0 then
        print(i)
    end

end

local n = 203 -- This is the program it outputs
print(n..", ("..progs[203]..")")

local len = 0
for i,v in ipairs(primes) do
    len = len + #progs[v] + 2
    --print(v.." ("..progs[v]..")\n")
end
print("Total len: "..len)
PiGuy
quelle