Maths Metagolf Mania!

12

4

Mathemania Specs:

Every piece of Mathemania code starts off with the number 2. From the 2, you can do the following operations:

  • e: Exponentiation. This command's default is squaring the number.
  • f: Factorial. This command's default is using the single factorial on the number (using f on 2 = 2! = 2).
  • r: Root. This command's default is square-rooting the number.
  • c: Ceiling function.
  • l: Floor function.

To generate a number in Mathemania, you must string together these commands, which are performed left-to-right on the number 2.

Examples:

ef = (2^2)! = 4! = 24
rl = floor(sqrt(2)) = floor(1.4...) = 1
er = sqrt(2^2) = sqrt(4) = 2
efrrc = ceil(sqrt(sqrt((2^2)!)))
      = ceil(sqrt(sqrt(24)))
      = ceil(sqrt(4.89...))
      = ceil(2.21...)
      = 3

The e, f and r commands can be altered by extra Mathemania commands (which also start off with 2 as its "base" number) to generate different exponentiations, factorials and roots by placing brackets after the altered function and placing the Mathemania commands inside it.

For example, to cube a number instead of squaring it, you can put the command for 3 after e like so:

e(efrrc) -> cube a number, "efrrc" = 3

NOTE: for our purpose, the factorial command (f) start off with 2 as a single factorial. So if you do f(efrrc), that will get evaluated to a double factorial, not a triple factorial.

For n-factorials (e.g. double factorials = 2-factorial, triple factorial = 3-factorial etc.), the base number is multiplied by the number that is n less than it, and n less than that, and so on until the final number cannot be subtracted by n without becoming 0 or negative.

For example:

7!! = 7 * 5 * 3 * 1 = 105 (repeatedly subtract 2, 1 is the last term as
                           1 - 2 = -1, which is negative)
9!!! = 9 * 6 * 3 = 162 (repeatedly subtract 3, 3 is the last term as
                        3 - 3 = 0, which is 0)

For more information, see here.

You can insert it anywhere, and it will get treated by Mathemania as a single function:

e(efrrc)rc = ceil(sqrt(2^3))
           = ceil(2.82...)
           = 3

You're also allowed to nest these inside one another:

e(e(e)) = e(4th power)
        = (2^4)th power
        = 16th power

For an interpreter of Mathemania code, click here (cheers, @BradGilbertb2gills!)

Task:

Your task is to create a program that, when given a positive integer n as input, generates a Mathemania program that when executed, returns n.

However, the Mathemania programs that you generate must be as small (golfed) as possible, and your final score is determined by the sum of the number of bytes in the generated Mathemania programs of the sample, which are the integers 10,000 to 10,100. The lowest score wins.

Rules and specs:

  • Your program must output a valid Mathemania program for any positive integer, but only the numbers between 10,000 and 10,100 will be tested.
  • You are not allowed to output Mathemania programs that do not result in an integer. If you do so, your program is disqualified.
  • For the commands e, f and r, the Mathemania code inside those functions (e.g. e(efrrc), where the efrrc is the code inside the function) must evaluate to a positive integer above 2. If your program doesn't follow this rule, it is disqualified as well.
  • Your program must return a Mathemania program for any one of the 101 test integers in at most 30 minutes on a modern laptop.
  • Your program must return the same solution for any integer every time it is run. For example, when a program is given an input 5 and it outputs efrc, it must output that every time the input 5 is given.
  • You may not hard-code any solutions for any positive integer.
  • In order to fully maximise golfing potential in your output, your program should be able to handle arbitrarily large integers. It is not a requirement, though good luck if your language doesn't support this.

This is , so lowest score wins!

clismique

Posted 2016-12-24T13:42:09.423

Reputation: 6 600

2

I wrote an evaluator for this language in Perl 6 on TIO Nexus.

– Brad Gilbert b2gills – 2016-12-24T20:07:01.797

@BradGilbertb2gills Wow, thanks! I'll put a link in the challenge. – clismique – 2016-12-25T03:29:17.070

If the input is ef for example, is the code allowed to "skip" and just output the result before the ef operation? – devRicher – 2016-12-25T20:56:57.367

@devRicher If you mean that the program "ef" is hard coded beforehand, then under the current rules, yes you're allowed to do that, because "ef" is not in the range of 10,000 to 10,100. I'm not sure that's what you meant though, and I might change the rules because hardcoding makes the challenge way too easy, IMO. – clismique – 2016-12-26T00:45:52.743

1I've been writing a program for this challenge for the past few hours. I think I have working code, but I can't exactly test it properly because some of the numbers generated by factorials are absolutely huge and Python (where I have my program and interpreter) can't take their square root. I'm not quite sure what to do with the program at this point.

On a side note, I originally misread and thought ALL 101 test cases had to fit within the time limit, which seemed near impossible. Any one seems a lot more reasonable. – notjagan – 2016-12-27T03:39:54.387

@notjagan Is your program really slow or unable to function properly when taking the square roots? – clismique – 2016-12-27T03:48:53.507

@Qwerp-Derp The program to generate the Mathmania code itself isn't super slow; out of the few numbers I've tested between 10000 and 10100, it takes at most a few minutes. However, I'm unable to verify the outputted code for the more complex test numbers due to the sheer size of the factorials generated while running. That is, when my interpreter encounters these large numbers and attempts to take the square root, it exceeds the limit for a float in Python. I can post my code as an answer, but I am unsure of whether it totally works because I can't verify a majority of the test cases. – notjagan – 2016-12-27T04:05:16.760

@notjagan Just post your answer along with its score - I included an interpreter in the challenge itself. – clismique – 2016-12-27T04:14:58.007

@Downvoters: can you please explain your reasoning in the comments? Thanks. – clismique – 2016-12-27T09:54:13.100

Answers

1

Python 3.5, Score of ??

As of now I don't have the output for all 101 inputs, but once I run the program for all the test cases I will update with my score.

from math import *

memoized = {}
same = {}

def _(mathmania, n):
    memoized[n] = mathmania
    return mathmania

def is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False
    for divisor in range(3, int(sqrt(n)) + 1, 2):
        if n % divisor == 0:
            return False
    return True

def pair_key(pair):
    low, high = pair
    diff = high - low
    if diff == 0:
        return 100
    low_done, high_done, diff_done = low in memoized, high in memoized, diff in memoized
    if high_done and memoized[high] == None or low_done and memoized[low] == None:
        return -1
    return (high_done + diff_done + (diff + 1 == low)) * 33 + low / high

def major_pairs(n):
    for i in range(n, int(sqrt(n)), -1):
        d = n / i
        if i - d < d - 1:
            break
        if d == int(d):
            yield (int(d), i)

def fact_key(pair):
    i, f = pair
    if i in memoized:
        if memoized[i] == None:
            return -1
        return 1
    return i / f

def near_fact(n, level):
    s = 4
    if n in same:
        s = same[n]
    for i in range(s, n ** 2 ** level):
        f = factorial(i)
        if f > (n - 1) ** 2 ** level:
            if f < (n + 1) ** 2 ** level:
                same[n] = i
                yield (i, f)
            else:
                return

def generate_mathmania(n):
    if n in memoized and memoized[n] != None:
        return memoized[n]
    memoized[n] = None
    binx = log(n, 2)
    if binx == int(binx):
        if binx == 2:
            return _("e", n)
        if binx == 1:
            return _("er", n)
        if binx == 0:
            return _("rl", n)
        return _("e(" + generate_mathmania(int(binx)) + ")", n)
    sq = sqrt(n)
    if sq == int(sq):
        return _(generate_mathmania(int(sq)) + "e", n)
    low, high = max(major_pairs(n), key=pair_key)
    if pair_key((low, high)) == -1:
        level = 1
        while True:
            try:
                i, f = max(near_fact(n, level), key=fact_key)
            except:
                level += 1
                continue
            if fact_key((i, f)) == -1:
                return _(generate_mathmania((n - 1) ** 2 + 1) + "rc", n)
            if f == n ** 2 ** level:
                return _(generate_mathmania(i) + "f" + "r" * level, n)
            if f < n ** 2 ** level:
                return _(generate_mathmania(i) + "f" + "r" * level + "c", n)
            return _(generate_mathmania(i) + "f" + "r" * level + "l", n)
    if low != 1:
        if low == high:
            return _(generate_mathmania(low) + "e", n)
        if high - low == 1:
            return _(generate_mathmania(high) + "f", n)
        return _(generate_mathmania(high) + "f(" + generate_mathmania(high - low + 1) + ")", n)
    good = None
    for i in range(n ** 2 - 1, (n - 1) ** 2, -1):
        if i in memoized:
            return _(generate_mathmania(i) + "rc", n)
        if not is_prime(i):
            good = i
    if good:
        return _(generate_mathmania(good) + "rc", n)
    for i in range((n + 1) ** 2 - 1, n ** 2, -1):
        if i in memoized:
            return _(generate_mathmania(i) + "rl", n)
        if not is_prime(i):
            good = i
    if good:
        return _(generate_mathmania(good) + "rl", n)
    return _(generate_mathmania((n - 1) ** 2 + 1), n)

Additionally, I was unable to verify the outputs of some of the test cases I tried due to sheer number size, and at that point @BradGilbertb2gills's online interpreter times out. Hopefully all the outputs work.

notjagan

Posted 2016-12-24T13:42:09.423

Reputation: 4 011

I have an interpreter in Python 2 (possibly 3) which should be able to handle arbitrary precision here. Copy and paste it into your IDE to run it.

– clismique – 2016-12-27T07:32:29.180

What were some of the outputs so that I could possibly optimize it. – Brad Gilbert b2gills – 2017-01-20T19:31:14.027