12
\$\begingroup\$

We've had Meta Regex Golf and Display OEIS Sequences. Now, it is time for Meta OEIS Golf.

Challenge

Given a sequence of integers, your program/function should output a program/function in the same language that then outputs the same sequence.

A simple example in Python would be

def f(sequence):
  # generate a dictionary/table lookup
  dc = {index: element for (index, element) in enumerate(sequence)}
  s = "lambda n: " + repr(dc) + "[n]"
  # at this point, eval(s) gives a lambda function, so
  # eval(s)(n) = sequence[n] = n-th element of sequence 
  # as required
  return s

The function f takes as input a sequence of integers and outputs the source code to a lambda function. When the lambda function is called on an index n, it outputs the n-th element of that sequence.

Try it Online

Output

The program that is output should be able to be submitted as an entry on this site for a challenge. Hence, it could be a program or function and can use one of the following input/output methods (from the tag):

  • Indexing: Allowed are both 0- and 1-based indexing, and the following rules can be applied with both these types of indexing.
  • Output:
    • Given some index n it can return the n-th entry of the list.
    • Given some index n it can return all entries up to the nth one in the sequence.
    • Without taking any index, it can return a (potentially infinite) lazy list or generator that represents the whole sequence.

Behavior past the final given term in the sequence is undefined. For example, your program may be given A000004 as

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

This consists of 101 0s. The generated program must then output 0 for each n from 1 to 101 (assuming 1-indexing), but it can output anything (even a string or non-integer) for n=102 and onward. Consequently, the generated program can output an infinite generator, as long as the first 101 terms are right.

Scoring

Your score will be the sum of your program's length and the length of all 100 programs it generates from the A000001 to A000100 sequences (the program does not necessarily have to work for other sequences). This file has sequence A000001 on line 6, A000002 on line 7, in order up to A000100 on line 105, so each sequence is one line. The sequences have varying number of terms; for example, A000066 (line 71) only has 10 terms.

The ungolfed Python example above would score 46713 + 261 = 46974 points.

If the program outputs an auxiliary file (I'm not sure how this could help, but it might come into play), then follow the part of this ruling before the horizontal line.

Lowest score wins, as usual.

\$\endgroup\$
  • 1
    \$\begingroup\$ @FryAmTheEggman Not all sequences are the same length. It's whatever oeis.org/stripped.gz had available. I'll mention the file format in the question \$\endgroup\$ – fireflame241 Jun 21 at 22:30
  • \$\begingroup\$ Should I/O methods be the same for all generated programs? \$\endgroup\$ – Arnauld Jun 21 at 23:21
  • \$\begingroup\$ @Arnauld Not necessarily. Think of each generated program as a separate, independent code golf submission, so one could be 0-indexed and return the n-th element, another could be 1-indexed and return the first n elements, etc. \$\endgroup\$ – fireflame241 Jun 21 at 23:27
  • \$\begingroup\$ I assume if the program writes a file to disk which is used by the others, that file gets counted 100 times? \$\endgroup\$ – Steve Bennett Jun 22 at 3:04
  • \$\begingroup\$ Does the program have to behave correctly on inputs other than those 100 sequences? \$\endgroup\$ – Steve Bennett Jun 22 at 3:06
5
\$\begingroup\$

JavaScript (Node.js),  15604 15329 15204  944 + 14168 = 15112

Saved 2 bytes thanks to @Neil

The main program expects an array of BigInt's. Each generated program expects a 0-indexed integer and returns the nth term as a Number, a BigInt or a string.

a=>eval(require('zlib').inflateRawSync(Buffer.from('lZRNb9pAEIZ/CxHYO94PbFfJwWKxVNpKPbSXHh1LXn8IUicTBDRKheG3d3ZtCKW5VELGO/vO+JnZ185Qz0NBF7bUtZ7XnsdwUs8i4EtWywiAcY4wCFo9x3RJkVag1H1GO5GypmANST2LgbUASQsshiBQt50rzUc4FGAoWo1AWVLSk1aaGVHSskxXrBRmUkJibBGSWQD7RwseOYDIXXhfC7nvQxbmQ2wSuxvPbSLn8sjQAnB163Lj4MzwX01cc4/aDmdhGia2BAWlGxTKlkiTiFih6xynH/lq06wbszvzUx1Dz5aSUjND7JwdjyaLc88zWZSDtKsozoVSyuQ0CZIAszsnin5YfQUaF7fjAhaKYT48DoJTl9h3KSXSQcQoCRJ4hEmMwD4+LL8icYFLo/Odsm9mt1KfZQxd+P6YVq6i541WDD10xhiGFF3hHd/jk9GFSFQXXVRWx6tBeerlrBT1X9q6V/P6rD9lXPRO6MfW2YvWI+w6DIjaMSNM7W0ctDCljJZWzmltvzuf98XIO9HJvRjQCX4g+RWXaK7IGhEHDa9lReVLaS4JRQy52j4/NeyLnhvVvDSb34y9CGupF63ZQn+xbADpgnydFPSk8b7UoVjoIhvvjXoya0bB77+eymZjj9L3tcYUEz989Tmq3fOP3eYBCUVHd7SLPqifzw9YiOKQF6JMF0nW+6+v97ZnXfpoqoZNWTob3dedBKYE7O/EQbFU33+C6VJsqfOt3r5pBQXpBYQsDvO0IMOGr+P94KstvOEQzMG+qkViRTfj/fZwU9Ckje576hsiIy5ZH6j0XLI1/XRF0bUOgbo57ay55pUL+pcJg/wftdSD2M5+s2ODQY16bHC5W8lyuLHfkUOGefEH','base64'))+'')

Try it online!

How?

Most sequences are stored as arrays, using several compression strategies:

  • Large integers are stored as BigInt's in hexadecimal notation.

    /* before */ 805381710463762432000n
    /* after  */ 0x2ba8ea9e9255100000n
    
  • Spread syntax is used on lists of at least 7 consecutive single-digit, positive entries. If there are more than 20 digits, the string is turned into a BigInt in hexadecimal notation.

    /* before */ 1,0,1,0,1,1,1,1,1,1,3,1,3,1,3,3,3,3,3,3,6,3,6,3,6,6,6,6,6,6
    /* step 1 */ ..."101011111131313333336363666666"
    /* step 2 */ ...0x146626ecaafee6bfa04ca8cean+''
    
  • Positive or negative delta-encoding is used if it turns out to be shorter.

    [...].map(c=>p+=+c,p=0) /* or */ [...].map(c=>p-=c,p=0)
    

Dedicated functions are used for a couple of easy sequences:

/* A000004 */ n=>0
/* A000005 */ n=>(g=d=>d&&(n%d<1)+g(d-1))(++n)
/* A000006 */ n=>(g=k=>n?g(++k,n-=(g=d=>k%--d?g(d):d<2)(k)):k)(2)**.5|0
/* A000007 */ n=>+!n
/* A000010 */ n=>(g=(n,k=n)=>k--&&(h=(a,b)=>b?h(b,a%b):a<2)(n,k)+g(n,k))(n+1)
/* A000012 */ n=>1
/* A000027 */ n=>1+n
/* A000030 */ n=>(n+'')[0]
/* A000034 */ n=>1+n%2
/* A000035 */ n=>1&n
/* A000037 */ n=>n++-~(n**.5+.5)
/* A000038 */ n=>2*!n
/* A000040 */ n=>(g=k=>n?g(++k,n-=(g=d=>k%--d?g(d):d<2)(k)):k)(2)
/* A000041 */ n=>(g=(n,k=n)=>!k|n<0?0:n?g(n,k-1)+g(n-k,k):1)(n)||1
/* A000042 */ n=>'1'.repeat(n+1)
/* A000044 */ n=>(g=a=>n--?g([a[0]+(~~a[2]&&a[1])-~~a[12],...a]):a[0])([1])
/* A000045 */ n=>(g=(a,b)=>n--?g(b,a+b):a)(0,1)
/* A000051 */ n=>1+2**n
/* A000058 */ n=>(g=n=>n?g(--n)**2n-g(n)+1n:2n)(BigInt(n))
/* A000062 */ n=>++n/(Math.E-2)|0
/* A000069 */ n=>(g=k=>n?g(++k,n-=(h=n=>n&&!h(n&n-1))(k)):k)(1)
/* A000071 */ n=>(g=(a,b)=>~n--?g(b,a+b):a)(0,1)-1
/* A000073 */ n=>(g=(a,b,c)=>n--?g(b,c,a+b+c):a)(0,0,1)
/* A000078 */ n=>(g=(a,b,c,d)=>n--?g(b,c,d,a+b+c+d):a)(0,0,0,1)
/* A000079 */ n=>2**n
/* A000085 */ n=>(g=k=>~k&&(h=n=>!n||n*h(n-1))(n)/h(n-2*k)/2**k/h(k)+g(k-1))(n>>1)
/* A000093 */ n=>n**1.5|0
/* A000096 */ n=>n*(n+3)/2
/* A000100 */ n=>(g=(a,b,c,d,e)=>n--?g(b,c,d,e,2*e+d-c-2*b-a):a)(0,0,0,1,2)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I think A000007 is n=>+!n and A000038 is n=>2*!n, if it helps. \$\endgroup\$ – Neil Jun 22 at 9:24
  • \$\begingroup\$ TIL: zlib is a standard part of node. \$\endgroup\$ – Steve Bennett Jun 23 at 10:55
  • 1
    \$\begingroup\$ @SteveBennett And so is Brotli in more recent versions. Brotli compresses this code more effectiently, but it's not supported on TIO. (As you mentioned earlier, this could be optimized endlessly anyway.) \$\endgroup\$ – Arnauld Jun 23 at 11:42
  • \$\begingroup\$ What if you brotli or zlib compress the resulting programs as well? :) \$\endgroup\$ – the default. Jun 24 at 13:27
  • \$\begingroup\$ @mypronounismonicareinstate Given the length of the decompression code and the base-64 encoding overhead, that would basically make everything longer, unfortunately. \$\endgroup\$ – Arnauld Jun 24 at 13:36
2
\$\begingroup\$

05AB1E, score 20925 11038 10270 (110 + 10160 output bytes)

ÙgiнëW0‹iWÄDU+}¬_iÌ2U}Z>©β®X)I‚εNVεƵ0ƵÿŸyåiƵ0-₅B‘Ƶ‘ìë₅Byт‹Y≠*iyëDg<i‘Ž‘ìë‘•‘.ø}}}}YiJ')«ë`'вsXi\ë'-}J}}éн}„IèJ

-768 score thanks to a tip of @JonathanAllan.

Takes each input sequence as a list of integers.

Resulting programs take an integer \$n\$ as input and output the 0-based \$n^{th}\$ value in the sequence (although outputting the first \$n\$ values instead of \$n^{th}\$ value would be the same byte-count by replacing the trailing è with £ in all output programs).

Test suite to verify the results or try a single output program with \$n\$ input (which currently uses the first A1 program).

Explanation of the generator program:

Ùgi                            # If all values in the (implicit) input-list are the same:
   н                           #  Only leave that unique value
  ë                            # Else:
   W                           #  Get the minimum (without popping)
    0‹i     }                  #  If this minimum is negative:
       WÄ                      #   Take the absolute value of this minimum
         DU                    #   Store a copy in variable `X` (1 by default)
           +                   #   And add it to each value in the list
   ¬_i   }                     #  If the first value is 0 (without popping)
      Ì                        #   Increase each value in the list by 1
       2U                      #   And store 2 in variable `X` (1 by defaul)
   Z                           #  Get the maximum of this new list (without popping)
    >                          #  Increase this maximum by 1
     ©                         #  Store it in variable `®` (without popping)
      β                        #  Convert the list from base-`®` to an integer
       ®                       #  Push `®`
        X                      #  Push `X`
         )                     #  Wrap all three values into a list
   I‚                          #  Pair it with the input-list
     ε                         #  Map both inner lists to:
      NV                       #   Store the outer map-index in variable `Y`
      ε                        #   Map all three values to:
       Ƶ0ƵÿŸ                   #    Push a list in the range [101,355]
            yåi                #    If the current value is in this list:
               Ƶ0-             #     Subtract 101 from the value
                  ₅B           #     Convert that to a base-255 string
                    ‘Ƶ‘ì       #     And prepend a "Ƶ"
              ë                #    Else:
               ₅B              #     Convert it to a base-255 string
                 yт‹           #     If the current value is less than 100
                 Y≠*i          #     and `Y` is NOT 1:
                     y         #      Just leave the current value as is
                    ë          #     Else:
                     Dg<i      #      If the length of the base-255 string is 2:
                         ‘Ž‘ì  #       Prepend a "Ž"
                        ë      #      Else:
                         ‘•‘.ø #       Surround the base-255 string with "•"
     }}}}                      #   Close the inner map and three if-else statements
         Yi                    #   If `Y` is 1 (thus the second map-iteration):
           J                   #    Join all individual compressed strings together
            ')«               '#    And append a trailing ")"
          ë                    #   Else (thus the first map-iteration):
           `                   #    Dump all three values separated to the stack
            'в                '#    Push "в"
              s                #    Swap the top two values on the stack
               Xi              #    If `Y` is still the default 1:
                 \             #     Discard the mapped value of `Y`
                ë              #    Else:
                 '-           '#     Push a "-"
                }J             #    After this if-else statement: join the stack together
     }}                        #  Close the if-statement and outer map
       é                       #  Take the shortest compressed list by first sorting on length
        н                      #  and then pop and pushing its first (shortest) string
   }                           # Close the outer if-statement
    „IèJ                       # And append "Iè" at the end of the string
                               # (after which the generated program is output implicitly)

This will result in one of the following programs:

  1. abвIè: This is the base program template, where a and b are both a (compressed) integer, in one of the following forms:
    1. d/dd: A hard-coded integer, where d is a digit (when below 100)
    2. •...•: A large compressed integer, where ... are three or more 05AB1E characters (when above 65024)
    3. Ƶ.: A small compressed integer, where . is a single 05AB1E character (when within the range [101, 355])
    4. Ž..: A medium compressed integer, where .. are both 05AB1E characters (when within the range [356, 65024])
  2. abвc-Iè: Similar as above, but c is a (compressed) integer as well.
  3. dIè: Where d is a digit.
  4. abc...xyz)Iè: Where [a,z] are each compressed integers in the form of 1.2, 1.3, or 1.4. And we also use compression method 1.2 instead of hard-coded 1.1 integers, since we join everything together at the end.

The third program type is used for the two sequences of the same integer. I could have also just used 0 instead, but the generator program would increase by more than it would save in that case.
See sequences A4 and A12.
The second program type is used for sequences that either start with a leading 0, or contain negative values. Neither of which can be compressed by the 05AB1E base-conversion list compression I'm using.
See sequences A1; A25; A30; A35; A36; A39; A45; A65; A71; A72; A76; A93; A94; A96; and A100.
The fourth program type is used for if that method is shorter for the sequence than any of the other three program types.
See sequences A11; A14; A18; A21; A22; A23; A24; A33; A42; A49; A50; A55; A58; A60; A63; A75; A78; A80; A81; A83; A84; A85; A87; A88; and A90.
All other sequences use the default first program type.
See sequences A2; A3; A5; A6; A7; A8; A9; A10; A13; A15; A16; A17; A19; A20; A26; A27; A28; A29; A31; A32; A34; A37; A38; A40; A41; A43; A44; A46; A47; A48; A51; A52; A53; A54; A56; A57; A59; A61; A62; A64; A66; A67; A68; A69; A70; A73; A74; A77; A79; A82; A86; A89; A91; A92; A95; A97; A98; and A99.

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) for a bit more in-depth information of how the compressed integers and compressed lists work.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You can probably save quite a few output bytes if you replace the output program with something like the following if it is shorter: get the nth item from a list of base 255 integers (or if the separator between elements takes more than one byte consider spliting a compressed strings on 0 bytes and then converting each from base 254) For example A33 has 179 bytes between the first compressed value indicators, but the sum of the lengths of all 22 items in base 254 is only 87, and only 21 0s would be required. There seem to be a fair few sequences that would benefit from this strategy. \$\endgroup\$ – Jonathan Allan Jun 22 at 18:07
1
\$\begingroup\$

Javascript (Node) 40 + 21058 = 21098

z=>`i=>[${z.map(x=>x===+x+''?x:x+'n')}]`

Takes inputs as arrays of strings, outputs a program which outputs an array containing numbers and BigInts.

Javascript (Node) 14 + 20852 = 20866

z=>`i=>[${z}]`

It seems to be acceptable for the generated programs to return an array?

Javascript (Node) 17 + 21152 = 21169

z=>`i=>[${z}][i]`

I'm not sure I entirely understood the challenge? Given an array ([1,2,3]), it outputs:

i=>[1,2,3][i]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is a valid program, but it (probably) doesn't get a very good score. \$\endgroup\$ – the default. Jun 22 at 2:55
  • \$\begingroup\$ I guess it's yet another challenge for the languages with built in compression/decompression routines. \$\endgroup\$ – Steve Bennett Jun 22 at 2:59
  • 2
    \$\begingroup\$ Yeah. It feels like a challenge with an extraordinarily long series of possible optimisations of diminishing returns. Every single one of the 100 sequences is a candidate for detecting and outputting a generator (and then golfing each of those). \$\endgroup\$ – Steve Bennett Jun 22 at 3:17
  • 1
    \$\begingroup\$ @SteveBennett Name a good [code-golf] challenge that doesn't have an extraordinarily long series of possible optimisations of diminishing returns. \$\endgroup\$ – the default. Jun 22 at 11:15
  • 1
    \$\begingroup\$ In my experience, after a couple of hours on most of them, it quickly becomes hard to find further optimisations. They might exist, but finding them is the challenge. Whereas here, it could take a very long time to get to that point. \$\endgroup\$ – Steve Bennett Jun 22 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.