N times program for the N-th number

Question

Given an array of positive integers A as the input, generate a program that, when repeated for k times, output the kth(1-index) value of the array.

For example, if the array is [1,11], the output should be a program that outputs 1, and when repeated twice, output 11. Code like print(end="1"); in Python 3 works: print(end="1"); prints 1 and print(end="1");print(end="1"); prints 11

Smallest sum of code lengths to solve all test cases win. Your meta code should solve 500 test cases in 60s, and each of your solution code should return in 10s. Meta code and solution code needn't be in the same language, but all solutions your meta-program generates should be in same language.

Pretest data and generator can be seen here. 7 days later will use the sum of submission time(e.g. 12:34 mean 1234) to be the random seed and generate another test case as the final test case.

---

The final seed is 7335 in GMT+8, so the final test data is here

Answer 1

Python 3, generates Stax

This uses a variety of strategies. Most strategies only apply under certain conditions, but there's one fallback strategy that is always usable. At the end, the smallest candidate program is selected.

from functools import reduce
from math import sqrt

symbols = " !#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_abcdefghijklmnopqrstuvwxyz{|}"

def uncycle(arr):
    for size in range(1, len(arr)):
        if all(e == arr[i % size] for (i, e) in enumerate(arr)):
            return arr[:size]
    return arr

def constant(val):
    return "A" if val == 10 else str(val)

def shift(val):
    if not val: return ""
    return constant(abs(val)) + "+-"[val < 0]

def encode(a, offsetMode):
    result = "";
    if offsetMode:
        for i in range(len(a) - 1, 0, -1):
            a[i] -= a[i - 1]
    for i in range(len(a)):
        parts = []
        signBit = (a[i] < 0) * 2
        continuing = (offsetMode and i == len(a) - 1) * 1
        remain = abs(a[i])
        while remain > 22:
            parts.insert(0, remain % 46 * 2 + continuing);
            remain //= 46
            continuing = 1

        parts.insert(0, remain * 4 + signBit + continuing)
        result += "".join(symbols[p] for p in parts)
    
    return result

def cram(arr):
    flat = encode(arr, False)
    offset = encode(arr, True)
    return offset if len(offset) < len(flat) else flat;

def issquare(num):
    root = int(sqrt(num))
    return root * root == num

def isgeometric(arr):
    r = arr[0]
    return all(r ** (i + 1) == e for (i,e) in enumerate(arr))

def generateProgram(arr):
    candidates = []
    rotated = uncycle(arr)
    rotated = rotated[-1:] + rotated[:-1]

    deltas = [b - a for a,b in zip(arr, arr[1:])]

    # single constant strategy
    if len(arr) == 1:
        candidates.append(constant(arr[0]))

    # repeated constant
    elif len(set(arr)) == 1:
        num = arr[0]
        if num == 10: candidates.append("A")
        if num % 2 == 0: candidates.append(constant(num // 2) + "H")
        if issquare(num): candidates.append(str(int(sqrt(num))) + "J")
        candidates.append(constant(num - 1) +  "^")

    # repdigit
    if len(arr) == 2 and 10 < arr[1] == arr[0] * 11 < 100:
        candidates.append(str(arr[0]) + "p")

    # single digits
    if max(arr) < 10:
        candidates.append("".join(map(str, rotated)) + "E|X@")

    # max 10
    if max(arr) == 10 and rotated[0] != 1:
        candidates.append("".join(str(e - 1) for e in rotated) + "E|X@^")

    fns = [
        ("", lambda x: x),
        ("H", lambda x: 2 * x),
        ("^", lambda x: x + 1),
        ("J", lambda x: x * x),
        ("Hv", lambda x: 2 * x - 1),
        ("H^", lambda x: 2 * x + 1),
        ("^H", lambda x: 2 * x + 2),
        ("HJ", lambda x: 4 * x * x),
        ("JH", lambda x: 2 * x * x),
        (":T", lambda x: x * (x + 1) / 2),
        ("|F", lambda x: reduce(lambda a, b: a*b, range(1, x+1))),
        ("J^", lambda x: x * x + 1),
        ("^J", lambda x: x * x + 2 * x + 1),
    ]
    for (stax, fn) in fns:
        if all(fn(i + 1) == e for (i,e) in enumerate(arr)):
            candidates.append("|X" + stax)

    # fixed delta
    if len(set(deltas)) == 1:
        delta = deltas[0]
        start = arr[0] - delta
        if start == 0:
            candidates.append(shift(delta))
        if delta == 1:
            candidates.append("|X" + shift(start))
        elif delta == -1:
            candidates.append("|x" + shift(start))
        elif delta > 1:
            candidates.append("|X" + constant(delta) + "*" + shift(start))
        elif delta < -1:
            candidates.append("|x" + constant(-delta) + "*" + shift(start))

    # geometric series
    if isgeometric(arr):
        candidates.append(constant(arr[0]) + "*")

    # prefix
    if len(arr) == 2 and arr[1] // 10 == arr[0] < 10:
        candidates.append("." + str(arr[1]) + "|X(")

    # suffix
    if len(arr) == 2 and arr[0] % 10 == arr[1] < 10:
        candidates.append("." + "".join(map(str, arr)) + "|X)")

    # uncycled cram
    candidates.append('"' + cram(rotated) + '"!|X@')
    
    candidates.sort(key=len)
    return candidates[0]

while True:
    arr = eval(input())
    prog = generateProgram(arr)
    print(prog)

Try it online!

Update: Validation It will be time consuming to execute each multiplicity of each program separately. It's possible to run them all at the same time. In order to do this, a small piece of code must be used. It's responsible for a few things.

1. Do implicit output if any. Normally, at the end of a stax program, the top of stack is printed if there has been no other output. When running multiple programs in the same source file, this must be done explicitly.

2. Clear both stacks.

3. Reset registers. For these programs only the x register is used.

This boilerplate should be applied after every individual program to be executed.

|d{P}{zP}?0XLd

For example, the input [5,2,7,3] produces the stax program 3527E|X@. All four multiplicities can be tested at once.

3527E|X@
|d{P}{zP}?0XLd

3527E|X@3527E|X@
|d{P}{zP}?0XLd

3527E|X@3527E|X@3527E|X@
|d{P}{zP}?0XLd

3527E|X@3527E|X@3527E|X@3527E|X@
|d{P}{zP}?0XLd

Try it online!

In this way, it's possible to test all the multiplicities of all the program in the same run, assuming nothing breaks. It would probably be the largest stax program ever executed if all 500 are done.

Answer 2

Perl 5 -p, generates Perl 5 -p, overhead 19 17 13

-1 thanks to @Dom Hastings

The score for one input will be length of the input + 13. Can obviously be improved by generating self-decompressing programs for larger inputs, but I won't bother.

Give the input array separated by commas on one line on STDIN.

#!/usr/bin/perl -p
chomp;$_="}{\$_=($_)[\$%++]"

Try it online!

Run the output concatenated n times with no input (e.g. redirect from /dev/null)

Sample way to run it for input 2,6,4,7 and the resulting program repeated 4 times:

perl -p '}{$_=(3,6,4,7)[$%++]}{$_=(3,6,4,7)[$%++]}{$_=(3,6,4,7)[$%++]}{$_=(3,6,4,7)[$%++]' < /dev/null

Try it online!

If you don't like the resulting program trying to read from STDIN use this version with overhead 17:

#!/usr/bin/perl -p
chomp;$_="1/!say+($_)[\$-++],"

Try it online!

Sample way to run it for input 2,6,4,7 and the resulting program repeated 4 times:

perl -E '1/!say+(2,6,4,7)[$-++],1/!say+(2,6,4,7)[$-++],1/!say+(2,6,4,7)[$-++],1/!say+(2,6,4,7)[$-++],'

Try it online!

This version crashes after printing the required output

Answer 3

05AB1E, generates 05AB1E

¸»“"ÿ"#.g<“ƵƒçJ

Try it online!

The generated program for the input [5,17,7,13,2] is "5 17 7 13 2"#.g<è.

Test suite for [5,17,7,13,2]

The length of the generated program is len(input) + 5

Answer 4

APL (Dyalog Unicode)

Anonymous prefix lambda. Returns a program body.

 {
     1=≢⍵:⍕⍵ ⍝ single element

     (2=≢⍵)∧(⍵[2]=11×⍵[1]):⍕⍵[1] ⍝ 2, 22 etc.

     1=≢∪⍵:'⊢',⍕⊃⍵ ⍝ all the same

     (⊢≡⊃×⍳∘≢)⍵:'+',⍕⊃⍵ ⍝ linear

     ((⌊=⊢)!⍣¯1⊢⊃⍵)∧(1∧.=1↓⍵):'!',⍕!⍣¯1⊃⍵ ⍝ factorial followed by all 1s

     (⍵[2]∧.=1↓⍵)∧(⍵[1]=10|2⊃⍵):(⍕⊃⍵),'⌈',(⊃⍕2⊃⍵) ⍝ b ab ab ab

     e←{∊⍉2 2⍴'+×',⍕¨⍵}¨⍸(⊃⍵)=∘.×⍨⍳10
     b←⍵∘≡¨e(({0::⍬ ⋄ ⍎⍵}¨,\)⍴∘⊂)¨⍨(≢⍵)
     ∨/b:⊃b/e

     Q←{'''',⍨⍵/⍨1+''''=⍵}
     (5∧.≤⍵)∧(≢⍕⍵)>6+(+/14=⍵)+≢⍵:'{⍺←⎕AV⍳⊃⋄1⌽⍺⊢⍵}''',Q ⎕AV[⍵] ⍝ string fallback

     (≢⍕⍵)>9+(+/5=⍵)+≢⍵:'{⍺←¯4+⎕AV⍳⊃⋄1⌽⍺⊢⍵}''',Q ⎕AV[4+⍵] ⍝ offset string fallback

     '{⍺←⊃⋄1⌽⍺⊢⍵}',⍕⍵ ⍝ fallback
 }

Try it online!

Methods

This explores various methods and returns the first usable one, eventually falling back to a universally applicable method.

Single element

If the list has only one element, it is returned as-is.

2, 22 etc.

A single digit can just be repeated to generate the number 11 times bigger,

All the same

We just return the rightmost (⊢) number.

Linear

f(n) = k×n sequences just insert a plus before the first term.

Factorial followed by all 1s

When the first number n=!m and subsequent numbers are 1, then !m is a solution because !m is n and m!m is 1 and !1 is 1.

b ab ab ab

Since all two-digit numbers are larger than all single-digit numbers, a running maximum, where the front of the first number is glued to the back of the second number, is a solution.

The three-line-code

Check whether any formula of the type +a×b is valid.

String fallback

Long sequences with no numbers under 5 (because 4 is a line break) can be encoded as characters of the SBCS.

Offset string fallback

If there are numbers under 5, we shift up by 9 to avoid those.

Fallback

Simple string concatenation of the string "{⍺←⊃⋄1⌽⍺⊢⍵}" and the stringified (⍕) input. E.g. [3,1,4] returns the program body {⍺←⊃⋄1⌽⍺⊢⍵}3 1 4.

The part in braces is an ambivalent function which means it can be either a prefix function or an infix function. Thus the leftmost instance of it will run in prefix mode, and all the others in infix mode. The difference between the modes is whether ⍺, signifying the left argument, has a value. If it doesn't then it will be assigned the function ⊃ (first).

Explanation of fallback method

{…} anonymous lambda:

 ⍺←⊃ If there is no left argument (⍺) assign the function ⊃ (first) to ⍺

 ⋄ then:

At this point, the following code means two different things depending on whether ⍺ is a list of numbers (infix call) or the function "first" (prefix call).

 If ⍺ is a list of numbers:

  ⍺⊢⍵ discard the left argument in favour of the right argument

  1⌽ rotate that one step left

 If ⍺ is the function "first":

  ⊢⍵ yield the right argument

  ⍺ pick the first element of that

  1⌽ rotate it one step (a no-op on a scalar)

Example run of fallback method

Executing 3 1 4's code, {⍺←⊃⋄1⌽⍺⊢⍵}3 1 4, assigns the "first" function to ⍺ and thus returns the first element; 3.

Executing {⍺←⊃⋄1⌽⍺⊢⍵}3 1 4{⍺←⊃⋄1⌽⍺⊢⍵}3 1 4 lets the rightmost lambda "capture" the left 3 1 4 as its left argument, so ⍺ has a value which is discarded in favour of 3 1 4 which is then rotated one step left and yields 1 4 3 as result. This is then used as sole argument to the leftmost lambda, where ⍺ becomes the "first" function, causing the result to be the first element; 1.

Executing {⍺←⊃⋄1⌽⍺⊢⍵}3 1 4{⍺←⊃⋄1⌽⍺⊢⍵}3 1 4{⍺←⊃⋄1⌽⍺⊢⍵}3 1 4 lets the rightmost lambda "capture" the middle 3 1 4 as its left argument which is then discarded in favour of the right argument, 3 1 4, which when rotated one step left is 1 4 3. This is then used as right argument of the middle lambda together with the leftmost 3 1 4 as left argument. The left argument is discarded for the right, which rotated one step left yields 4 3 1. This then becomes the sole argument of the leftmost lambda, so ⍺ becomes the "first function", returning the first element; 4.

Scoring

When it becomes time to test using actual data, use this test harness (linked populated with pretest data). The test cases go in the Input field, and the Output will be the total byte count of all 500 programs together. (It will also throw an error, but that's just because it afterwards tries to evaluate the Input as-is.)

Answer 5

Charcoal

´⎚´§´⪪⪫ＩＡ ”y¦ Ｌυ⊞υω

Try it online! Link is to verbose version of code. Explanation:

´⎚´§´⪪

Output the literal string ⎚§⪪.

⪫ＩＡ 

Cast the input array to string, join with spaces, and print.

”y¦ Ｌυ⊞υω

Output the literal string ¦ Ｌυ⊞υω.

Output of for example 5,17,7,13,2 is ⎚§⪪5 17 7 13 2¦ Ｌυ⊞υω. Try it online! Explanation:

⎚

Clear the canvas, so that only the last output is visible.

§⪪5 17 7 13 2¦ Ｌυ

Take the length of the predefined list u. Use that to index into the list of integers that have been split on spaces and output the selected element.

⊞υω

Push a dummy variable to the predefined list u, so that the next copy will output the next element of the list.

Total output length = (length of all integers in all lists) + (number of integers in all lists) + (number of lists * 9) characters (SBCS).

Answer 6

Haskell, generates Haskell

main = interact $ ("main=print$("++) . (++"!!)$ -1\n +1--")

Try it online! For the first testcase [5,2,7,3,2,3,15,10,7,2,14,11,16,16,3,3,4,3,8,4] it produces the following program:

main=print$([5,2,7,3,2,3,15,10,7,2,14,11,16,16,3,3,4,3,8,4]!!)$ -1
 +1--

Try it once, doubled and trippled. This uses the same approach as my Haskell answer to I double the source, you double the output.

The length of each generated program is the length of the input list as string plus 25, thus the score for the currently available testcases is 12266 + 500 * 25 = 24766. This shows that the code to data ratio is basically equal, and I doubt it is possible to write small enough decompression code which will decreases the score. It might be possible if the lists where much larger.

Answer 7

Python 2, generates Python 2

import sys
a=`input()[::-1]`.replace(' ','')
sys.stdout.write('print%s[-open(__file__,"a").tell()/%s]#'%(a,len(a)+37))

Try it online!

For the input

[10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]

the generated program is

print[29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10][-open(__file__,"a").tell()/98]#

which is 98 bytes.

Adapted from this solution in "I double the source, you double the output!".

Dammit, two shorter answers popped in before I finished writing this answer.

Answer 8

Java 8, generates Python 2

interface M{static void main(String[]a){int l=a[0].length();System.out.print("print"+a[0]+"[open(__file__,'a').tell()/"+(l+35+(l+"").length())+"]#");}}

Try it online.

I.e. [3,4,5,6,7] generates this Python 2 program:

print[3,4,5,6,7][open(__file__,'a').tell()/48]#

Try it online once; Try it online twice; Try it online three times.

Generated Python program is based on @Mr.Xcoder's answer for the Third time the charm challenge.

Explanation:

Java 8 code:

interface M{                    // Class
  static void main(String[]a){  //  Mandatory main-method
    int l=a[0].length();        //   The length of the first argument
                                //   (Note that this is the length of the input as String,
                                //   not the size of the array)
    System.out.print(           //   Print:
      "print"                   //    Literal "print"
      +a[0]                     //    Appended with the argument
      +"[open(__file__,'a').tell()/"
                                //    Appended with literal "[open(__file__,'a').tell()/"
      +                         //    Appended with an integer that is formed by:
       (l                       //     Getting the length we got earlier
       +35                      //     +34 for the rest of the Python 2 code + 1
       +(l+"").length())        //     + the length of the length (<10→1; 10-99→2; etc.)
       +"]#");}}                //    Appended with literal "]#"

Python 2 code:

print                        # Print
 [3,4,5,6,7]                 #  From this array
 [                           #   The `k`'th item,
  open(__file__,'a').tell()  #   where `k` is the length of its own source code
  /                          #   divided by
  48                         #   the length of its own source code (once) + 1
 ]#                          # With a trailing comment, so we can repeat the program
 

Answer 9

Python 2, Generates C++

This isn't going to beat any records, I was mainly interested in thinking about if I could figure out how to do it :) Use the fact that global variables are run before main, and so can increment a global variable, then using a #ifdef to ensure main is only defined once.

import sys
print("""#include <stdio.h>
#ifndef A
#define A
int v;
int d[]={""" + sys.argv[1] + """};
struct C{C(){v++;}};
int main(void){ printf("%d",d[v]); }
#else
C c1;
#endif
""")

Answer 10

Bash, outputs programs in Perl 5

Bash program can be called like script.sh 1,2,3.

Perl program should be called with the -E flag.

echo "shift@a;@a=($1)unless@a;END{say\$a[0];exec'true'}"

The generated perl code for an input of 4,7,8 is:

shift@a;@a=(4,7,8)unless@a;END{say$a[0];exec'true'}

Pretty brute force. Removes an element of the array (perl doesn't care that the array doesn't exist at first), sets it if it is not already set. It then echoes the first element of the array at the end. (The END block is run last). The exec 'true' quits the program, so that the further END blocks are not executed.

Example:

#Once
$ perl -E "$(bash script.sh 4,7,8)"
4

#Duplicated twice
$ perl -E "$(bash script.sh 4,7,8)$(bash script.sh 4,7,8)"
7

#Duplicated thrice
$ perl -E "$(bash script.sh 4,7,8)$(bash script.sh 4,7,8)$(bash script.sh 4,7,8)"
8

Answer 11

Runic Enchantments, generates Runic

74akw94/85akw
R32B~~?US' Sqq1Ky1Ky
\i<{1[lil1-{S{)]{{1KyB
D'0$'´$$' $     Rl0) ?
R"{Zs$;|1|l;|y"@
"UwR'10<|I+}"$~ /' Su0
       Rakwc4akw/

Try it online!

Takes input as a space-separated list of values.

Output done once
Output done twice
Output done four times

Utilizes the continuous numerical read mode command, ´ that was committed on Jan 12 and I found this question on the 14th. This command allows arbitrary length values can be encoded as without this feature it would be very difficult to do so (e.g. 1392 would need to be represented as 1X3+X9+X2+, necessitating an additional loop at a minimum); precisely the problem I wanted to solve when I created the ´ command.

In the original code, the | in the strings "{Zs$;|1|l;|y" and "UwR'10<|I+}" are replaced with \n (which sit in the grid and not modify it, as they normally would) with write commands: 74akw, 94/Rakw, c4akw, and 85akw. The original characters can be literally anything. | was chosen to be a symbolic placeholder that visually represented what I wanted. Several bytes saved (if unscoring ones) by not having to reflectively add an entry point, as wR'10< writes an R into a location where one already exists (position 0,1), and then proceeds to fill its stack with junk before running out of mana, following a looping sequence U"'i34.

The resulting output code works by using the write command to change the first character on the second line to a Right redirection (so only one IP executes a print statement), with clever use of stack length resulting from taller and taller programs to determine which index to read. Every other IP changes that same location to the same instruction and terminates. Everything else goes unused.

_{Image is out of date, but sufficient for flow explanation.}

Each execution of 1Iy maintains the IP's ability to handle a larger and larger stack (caused by the l command), the size of which allows the program to determine how many copies of the base source code there are. The final 1 is used to increment the previous l to the required number when rotating the stack (created next) in order to arrive at the correct value. The Z command negates this value so that the stack rotates in the correct direction.

The original input array is then encoded using continuous read mode, primed with a 0 to avoid incrementally modifying the same value, to read the original inputs. The space NOP is required to exit continuous read mode and allow the subsequent 0 to prime the stack again.

Score should equal approximately 3+v.toString().length, for each array entry v, +23 for each array. Approximately (2.55*total length of input) or 33837 for the sample input, if I did things right.

Minor changes were introduced into my expected final program due to side effects introduced in the same build regarding the s command, however it resulted in a better score at the same time.