Lua 5.3, 57522
I actually started working on this back when the question was posted, but forgot about it until the Brain-Flak anniversary.
-- 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)
Similar idea to the other answers where known-useful functions are used to build up larger numbers from good representations of simpler numbers.
One difference is that instead of solving subproblems in terms of smaller numbers, I'm solving subproblems in terms of numbers with shorter representations. I think this makes it more elegant to take advantage of negative numbers as well as handling the case where smaller numbers are represented in terms of larger numbers.
Also, trying to find all numbers that can be represented in a certain size rather trying to represent a particular number as shortly as possible actually simplifies certain calculations. Instead of working a formula in reverse to see whether it can be applied to a number, the formula can be worked forwards and applied to every number.
Another difference is that known solutions are stored in two pieces -- an (optional) "prefix" and a "suffix" (more like an infix). The valuation of the prefix is expected to be ignored when calculating the given number -- the prefix just contains code that sets up the suffix to run (generally by pushing one or more things to the stack). So, given a prefix and a suffix, the corresponding number can be pushed onto the stack with prefix(suffix)
.
This split basically solves the same problem as the unpack
function in Wheat Wizard's answer. Instead of wrapping code with <...>
only to undo this later, such code is simply added to the prefix.
In a few cases, the prefix actually does get evaluated (mainly for the pseudo-exponentiation operation), so its valuation is also stored. However, this doesn't really cause a big problem, as the generator isn't trying to construct specific numbers. It seem to theoretically imply that there could be two pieces of code of the same length and generating the same number that wouldn't be redundant in the cache due to having different prefix valuations. I didn't bother accounting for this though, as it doesn't seem to matter much (at least in this domain).
I imagine it would be easy to whittle down the byte count just by adding more cases, but I've had enough for the moment.
I've run to 1000000, but only done sanity checking up to 100000.
Pastebin of output on given primes.
4Just as a note: the number of valid programs of length
2n
is4^n catalan(n)
. – Leaky Nun – 2016-08-13T17:34:13.4232Hmm, I like the challenge, but I think it should be scored on unknown integers. Otherwise, the integers programs are scored upon could be brute forced and other integers just left as
(()()()...())
. Plus, if you just use prime numbers, that might miss out on some optimizations possible for composites. – James – 2016-08-13T17:40:54.707Also, why is
[]
undefined for this challenge? I find it strange to implement 7 of the 8 operators. Either way, cool challenge, I'm honored someone would write a challenge inspired by my own language! – James – 2016-08-13T17:43:34.2072@DJMcMayhem I want people to be able to compute their own score. All relevant prime numbers are one more than a composite number, so there should be plenty of potential optimisations. Also, I don't want people to rely on a particular value of
[]
in their answer. – Neil – 2016-08-13T18:00:02.943@EamonOlive I went for pushing
n
to the stack because that way it works as a standalone program that printsn
. – Neil – 2016-08-13T20:51:37.833Is source code compression (specifically Phar) allowed?
– YetiCGN – 2016-08-20T12:48:48.987@YetiCGN How would it be a working Brain-Flak program if you compressed it? – Neil – 2016-08-20T13:03:47.247
You can add a PHP script to a Phar (php archive) with gzip or bzip2 compression that will run and output the Brain-Flak program. It's the PHP script that's compressed, but you can run it with
php brainflak.phar <input>
. Or did I misread the question and it's ONLY the Brain-Flak programs' codesize for each of the prime numbers that counts and not the original language's codesize? – YetiCGN – 2016-08-20T13:17:14.9671@YetiCGN The script's size only counts as a tie-breaker. – Neil – 2016-08-20T15:14:42.437