cpp_shinjuku : a translation of Shinjuku into C++

[vilc]

In the past month I have been working on a partial translation of the code of Freywa's Shinjuku from python to C++, in order to improve the performance of search programs based on it, starting with transfer.py. This lacks almost all features from search.py.

I worked especially hard on improving transfer, by adding multithreading support and several new options for selecting templates (modified triples) before the search starts, plus some more technical optimisations.

Here is a script (requires python Shinjuku) for displaying or filtering results by cost. Save in the root of Shinjuku under the name "filter_results.py".

Code: Select all

# a rudimentary script for displaying components
# or filtering them for immediate improvements

from shinjuku.search import dijkstra, lookup_synth, read_components
from shinjuku.transcode import decode_comp, realise_comp
from shinjuku import lt
from sys import argv
import os
from math import sqrt, ceil

MAX_COMP = 1000 # maximum number of components allowed for a stamp collection

def make_stamp(comp_list, spacing=150):
    stamp = lt.pattern("")
    wh = ceil(sqrt(len(comp_list)))
    count = 0
    for comp in comp_list:
        stamp += realise_comp(comp)((count // wh) * spacing, (count % wh)* spacing)
        count += 1
    return stamp

def num_bits(apgcode):
    if apgcode.startswith("xs"):
        return int(apgcode.split("_")[0][:2])
    return 0
        
def filter_by_cost(files):
    print("Invoking dijkstra(). This may take a while ...")
    min_paths = dijkstra()

    def get_cost(apgcode):
        if apgcode in min_paths:
            return min_paths[apgcode][0]
        return 9999

    for filename in files:
        print("Reading components from file", filename)

        comps = read_components([filename])
        count = 0

        results = {}
        for comp_str in comps:
            start, ng, end = decode_comp(comp_str)
            new_cost = get_cost(start) + ng
            if new_cost < get_cost(end):
                if end in results:
                    if new_cost < results[end][0]:
                        results[end] = (new_cost, comp_str)
                else:
                    results[end] = (new_cost, comp_str)

        if len(results) < MAX_COMP:
            pat = make_stamp([comp[1] for comp in results.values()])
            print(pat.rle_string())
        else:
            print("Too many results to print rle. Storing in out_filter_results.sjk")
            with open("out_filter_results.sjk", "w") as f:
                for comp in results.values():
                    f.write(comp[1]+"\n")
        print(f"Found {len(results)} improved objects.\n\n")


def no_filter(files):
    comps = list(read_components(files))
    
    if len(results) < MAX_COMP:
        pat = make_stamp(comps)
        print(pat.rle_string())
    else:
        print("Too many results to print rle. Storing in out_filter_results.sjk")
        with open("out_filter_results.sjk", "w") as f:
            for comp in comps:
                f.write(comp+"\n")
    print(f"Found {len(comps)} components.\n\n")
    
def expand_directories(paths):
    files = []
    for path in paths:
        if os.path.isdir(path):
            files += [os.path.join(path, file) for file in os.listdir(path)]
        else:
            files.append(path)
    return files

#---------------------------------------------

if "-c" in argv:
    print("Filtering by improved cost.")
    files = argv[1:]
    files.remove("-c")
    # replace directories with their contents, not recursive
    files = expand_directories(files)
    print("Found", len(files), "files.")
    filter_by_cost(files)
else:
    print("No filtering.")
    no_filter(argv[1:])

Example search :
Compile transfer as explained in readme.txt. If you have a local copy of the database, you can place the executable at the root of Shinjuku, along with the templates-xxx.txt file.

Lets say that you want to append the boat in xs19_062sgc453z253.

Code: Select all

x = 37, y = 16, rule = LifeHistory
18.2D$17.D2.D$20.D$19.D$18.D2$18.D2$6.2A27.2A$2A5.A11.D9.2A5.A$A.A.3A
13.D8.A.A.3A$2.A.A10.7D9.A.A$2.2A16.D10.2A$19.D9.2A$28.A.A$29.A!

Create in the same directory as transfer a file named "apgcodes.txt" containing :

Code: Select all

xs19_062sgc453z253

Then run (replace templates-xxx.txt with the name of your template file) :

Code: Select all

transfer templates-xxx.txt apgcodes.txt out.sjk -d 5 5 -c . 7

"-d 5 5" means that the population difference should be between 5 and 5 inclusive, because that is what we need. "-c . 7" means that the cost in gliders should be between 1 (default) and 7, because we do not want our solution to be too expensive. Thanks to these restrictions, the search is only a couple of seconds long, against several minutes for the python version.

Filter the output with :

Code: Select all

python filter-results.py out.sjk

You should obtain this RLE, which contains four ways of doing this conversion :

Code: Select all

#CLL state-numbering golly
x = 285, y = 210, rule = B3/S23
249bobo$249b2o$103bo146bo$102bo$82b2o18b3o127b2o$82bo5b2o142bo5b2o
$83b3obobo143b3obobo$85bobo147bobo$86b2o148b2o4$88b2o$87bobo$89bo
3$83bo149bo$77b3o2b2o143b3o2b2o$79bo2bobo144bo2bobo$78bo149bo$87b
3o147b3o$87bo14b2o133bo14b2o$88bo12b2o135bo12b2o$103bo149bo5$87bo
149bo$86b2o148b2o$86bobo147bobo84$134bobo$134b2o148bo$135bo146b2o$
283b2o36$82b2o148b2o$82bo5b2o142bo5b2o$83b3obobo143b3obobo$85bobo
69bo77bobo$bo84b2o68bo79b2o$2bo2bobo148b3o$3o2b2o$6bo2$159bo$153b
3o2b2o$3b3o149bo2bobo$3bo150bo$4bo33$281bo$195bo84b2o$132b2o61b2o
83bobo$43b2o86b2o61bobo$44b2o87bo$43bo234b2o$278bobo$129b3o146bo$
129bo$130bo!

If you have more apgcodes, it becomes interesting to set the number of threads with "-t" and the size of chunks with "-s". More information in readme.txt and the help message.

Please report any bug or suggestion here, including for the name : "cpp_shinjuku" is admittedly not great.