How to split text into chunks minimizing the solution?
<p><strong>OVERVIEW</strong> </p>

<p>I got a set of possible valid chunks I can use to split a text (if possible).</p>

<p>How can i split a given text using these chunks such as the result will be optimized (minimized) in terms of the number of resulting chunks?</p>

<p><strong>TEST SUITE</strong></p>

<pre><code>if __name__ == "__main__":
    import random
    import sys

    random.seed(1)

    # 1) Testing robustness
    examples = []
    sys.stdout.write("Testing correctness...")
    N = 50
    large_number = "3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481"
    for i in range(100):
        for j in range(i):
            choices = random.sample(range(i), j)
            examples.append((choices, large_number))

    for (choices, large_number) in examples:
        get_it_done(choices, large_number)
    sys.stdout.write("OK")

    # 2) Testing correctness
    examples = [
        # Example1 -&gt;
        # Solution ['012345678910203040506070', '80', '90', '100', '200', '300', '400', '500', '600', '700', '800', '900']
        (
            [
                "0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
                "10", "20", "30", "40", "50", "60", "70", "80", "90",
                "100", "200", "300", "400", "500", "600", "700", "800", "900",
                "012345678910203040506070"
            ],
            "0123456789102030405060708090100200300400500600700800900"
        ),
        # Example2
        ## Solution ['100']
        (
            ["0", "1", "10", "100"],
            "100"
        ),
        # Example3
        ## Solution ['101234567891020304050', '6070809010020030040050', '0600700800900']
        (
            [
                "10", "20", "30", "40", "50", "60", "70", "80", "90",
                "012345678910203040506070",
                "101234567891020304050",
                "6070809010020030040050",
                "0600700800900"
            ],
            "10123456789102030405060708090100200300400500600700800900"
        ),
        # Example4
        ### Solution ['12', '34', '56', '78', '90']
        (
            [
                "12", "34", "56", "78", "90",
                "890",
            ],
            "1234567890"
        ),
        # Example5
        ## Solution ['12', '34']
        (
            [
                "1", "2", "3",
                "12", "23", "34"
            ],
            "1234"
        ),
        # Example6
        ## Solution ['100', '10']
        (
            ["0", "1", "10", "100"],
            "10010"
        )
    ]

    score = 0
    for (choices, large_number) in examples:
        res = get_it_done(choices, large_number)
        flag = "".join(res) == large_number
        print("{0}\n{1}\n{2} --&gt; {3}".format(
            large_number, "".join(res), res, flag))
        print('-' * 80)
        score += flag

    print(
        "Score: {0}/{1} = {2:.2f}%".format(score, len(examples), score / len(examples) * 100))

    # 3) TODO: Testing optimization, it should provide (if possible)
    #          minimal cases
</code></pre>

<p><strong>QUESTION</strong></p>

<p>How could I solve this problem on python without using a brute-force approach?</p>

<pre><code>def find_shortest_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if start not in graph:
        return None
    shortest = None
    for node in graph[start]:
        if node not in path:
            newpath = find_shortest_path(graph, node, end, path)
            if newpath:
                if not shortest or len(newpath) &lt; len(shortest):
                    shortest = newpath
    return shortest


def get_it_done(choices, number):
    mapping = {}
    graph = {} 

    for choice in choices:
        if choice in number:
            _from = number.index(choice)
            _to = _from + len(choice)
            mapping.setdefault((_from, _to), choice)

    items = sorted(mapping.items(), key=lambda x: x[0])
    for _range, value in items:
        _from, _to = _range
        graph.setdefault(_from, []).append(_to)
    start = 0
    end = _range[1] #this is hack, works only in python 2.7
    path = find_shortest_path(graph, start, end) 
    ranges = [tuple(path[i:i+2]) for i in range(len(path) - 1)]
    if len(ranges) == 1:
        return [mapping[(start, graph[start][-1])]]
    return [mapping[_range] for _range in ranges]


if __name__ == "__main__":
    examples = [
        # Example1 -&gt;
        # Solution ['012345678910203040506070', '80', '90', '100', '200', '300', '400', '500', '600', '700', '800', '900']
        (
            [
                "0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
                "10", "20", "30", "40", "50", "60", "70", "80", "90",
                "100", "200", "300", "400", "500", "600", "700", "800", "900",
                "012345678910203040506070"
            ],
            "0123456789102030405060708090100200300400500600700800900"
        ),
        ## Example2
        ## Solution ['100']
        (
            ["0", "1", "10", "100"],
            "100"
        ),
        ## Example3
        ## Solution ['101234567891020304050', '6070809010020030040050', '0600700800900']
        (
            [
                "10", "20", "30", "40", "50", "60", "70", "80", "90",
                "012345678910203040506070",
                "101234567891020304050",
                "6070809010020030040050",
                "0600700800900"
            ],
            "10123456789102030405060708090100200300400500600700800900"
        ),
        ### Example4
        ### Solution ['12', '34', '56', '78', '90']
        (
            [
                "12", "34", "56", "78", "90",
                "890",
            ],
            "1234567890"
        ),
        ## Example5
        ## Solution ['12', '34']
        (
            [
                "1", "2", "3",
                "12", "23", "34"
            ],
            "1234"
        )
    ]

    for (choices, large_number) in examples:
        res = get_it_done(choices, large_number)
        print("{0}\n{1}\n{2} --&gt; {3}".format(
            large_number, "".join(res), res, "".join(res) == large_number))
        print('-' * 80)
</code></pre>

python string algorithm split computer-science