Create a version series

Question

The Definition

Given an integer x, a version series is a set of digits (base 10) from which any x-length subset of consecutive members is unique compared to all other possible subsets of the same length (a unique "version").

The Task

Write a function which, when passed some subset length x, produces a version series, considering a scoring determined by the sum of the total number of characters outputted by inputs 1 through 10 (so, f(1) + f(2) + ... + f(10)).

Further rules

• The output must always be the same for a specific x.
• Please do not change your algorithm (except for corrections) after posting and try to avoid using others' work.

Examples

Let f(x) be the function which returns the version series.

>>> f(3)
0010111

Note that this is a valid version series as all possible consecutive subsets of length 3 (001, 010, 011, 111) are unique. This would obviously be a terrible score, however.

>>> f(3)
0123456789876543210

This is another valid version series, with a slightly better score. This is valid for the same reasoning as before.

>>> f(3)
001010011110111

This is clearly not valid; the subsets 001, 010, 101, 111 all occur more than once.

Trivia

I have referred to this as a version series as it may be used to identify a range of compatible versions by taking a larger subset of consecutive values within the full set to identify a range of compatible versions that lie therein.

Verifier (in Java)

import java.util.Scanner;
import java.util.ArrayList;

public class Checker {
    public static void main(String[] args) throws Exception {
        int substringLength = Integer.parseInt(args[0]);

        Scanner sc = new Scanner(System.in);
        sc.useDelimiter("");

        ArrayList<Character[]> active = new ArrayList<Character[]>();

        Character[] current = new Character[substringLength],
            compare, prev;

        for (int i = 0; i < substringLength; i++) {
            current[i] = sc.next().charAt(0);
        }

        for (int index = 0; sc.hasNext(); index++) {
            for (int k = 0; k < index; k++) {
                boolean differ = false;
                compare = active.get(k);
                for (int j = 0; j < substringLength; j++) {
                    differ = differ || compare[j].compareTo(current[j]) != 0; 
                }
                if (!differ)
                    throw new Exception("Match found for subset " + index);
            }
            active.add(current);
            prev = current;
            current = new Character[substringLength];
            for (int k = 1; k < substringLength; k++) {
                current[k - 1] = prev[k];
            }
            current[substringLength - 1] = sc.next().charAt(0);
        }

        System.out.println("Input is a valid version series.");
    }
}

Compile this as Checker.java, and call with program <x> | java Checker <x>, where x is your input (obviously, the input to your program is flexible).

If you are unable (or unwilling) to use Java, you may implement your own verifier, as long as you post it with your answer and show that it works.

Answer 1

Python 2, score: 11111111155

Score: sum(10**x+x-1 for x in range(1,11))

This program obtains the maximum possible score for any given x.

def f(x):
    s="0"*x
    while 1:
        for c in "1234567890":
            p=s+c
            if p[len(p)-x:]not in s:
                s=p
                break
        else:
            break
    return s

Try it online

This takes a long time to run for large inputs (like 6), because it's building strings thousands or millions of characters long. It also maintains a set of substrings and checks if a possible next substring is contained in it. It's not very efficient. I first tried a recursive solution, as well as a solution with a fixed number of iterations or something, but this was my working one.

Explanation:

I solved this by recognizing a pattern in the optimal solutions for x=1,2, which I created by hand as below. I roughly implemented the method I used to create f(2) in the function above, except that I just did zero last altogether.

1   0123456789
2   00102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990

This algorithm tries every number in order, with zero last. Failing to do zero last will result in an early termination. f(2), for example, would stop at 00102030405060708090, because all possible values starting with 0 have been exhausted. When doing this by hand, I simply started with f(1), added zeros between each digit, then went to every combination starting with a 1 (leaving out zero), then twos (leaving out zero and one), etc. Essentially, the algorithm must try the digit that you started with last.

The score is sum(10**x+x-1 for x in range(1,11)).

I used this formula to compute the score, because the output for all values 1-10 would probably take many days (months?) to complete. The highest I received the output for was f(6), which took ~10-15 minutes. It'd take at least 10000 times that for f(10). The lengths of s and p go from 1 to 10**x. The for loop runs exactly 10 times, no matter what.

Output:

They are slightly different than above because zeros are done last:

1   0123456789
2   00112131415161718191022324252627282920334353637383930445464748494055657585950667686960778797088980990
3   000111211311411511611711811911012212312412512612712812912013213313413513613713813913014214314414514614714814914015215315415515615715815915016216316416516616716816916017217317417517617717817917018218318418518618718818918019219319419519619719819919010210310410510610710810910022232242252262272282292202332342352362372382392302432442452462472482492402532542552562572582592502632642652662672682692602732742752762772782792702832842852862872882892802932942952962972982992902032042052062072082092003334335336337338339330344345346347348349340354355356357358359350364365366367368369360374375376377378379370384385386387388389380394395396397398399390304305306307308309300444544644744844944045545645745845945046546646746846946047547647747847947048548648748848948049549649749849949040540640740840940055565575585595505665675685695605765775785795705865875885895805965975985995905065075085095006667668669660677678679670687688689680697698699690607608609600777877977078878978079879979070870970088898808998908098009990900

I was going to make a pastebin of f(6), but it's past the maximum size limit a guest can create.

Validator - Counts how many unique subsets there are. If the result is 10**x, it's correct.

Answer 2

BruteForce

Tries to brute force every single possible combination using luck. Note that it does use the same seed all the time, so output is the same. Takes a single input in the args array to specify i.

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class BruteForce {
    private static Random rand = new Random(123);
    public static void main(String[] args) throws Exception {
        int length = Integer.valueOf(args[0]);
        List<List<Character>> used = new ArrayList<>();
        StringBuilder out = new StringBuilder();
        List<Character> put2 = new ArrayList<>();
        for(int i = 0; i < length-1; i++) {
            char one = (char) rand(48, 57);
            out.append(one);
            put2.add(one);
        }
        used.add(put2);
        long last;
        last = 0;
        for(int i = length-1; ; i++) {
            last = System.currentTimeMillis();
            List<Character> put = new ArrayList<>();
            do {
                if(last+1000 < System.currentTimeMillis()) {
                    System.out.println(out.toString());
                    return;
                }
                put.clear();
                for(int j = i-1; j >= i-length+1; j--) {
                    put.add(out.charAt(j));
                }
                put.add((char) rand(48, 57));
            } while(used.contains(put));
            used.add(put);
            out.append(put.get(length-1));
        }
    }
    public static int rand(int min, int max) {
        return rand.nextInt((max - min) + 1) + min;
    }
}