kolakoski.ipynb

{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"kolakoski.ipynb","version":"0.3.2","views":{},"default_view":{},"provenance":[]},"kernelspec":{"display_name":"Python [default]","language":"python","name":"python3"}},"cells":[{"metadata":{"id":"hoLI1gnCIAoE","colab_type":"text"},"cell_type":"markdown","source":["# [Kolakoski Sequence](https://en.wikipedia.org/wiki/Kolakoski_sequence)\n","lets start with the two numbers `(1, 2)` that we will cycle through; i.e. they will be used in this order:<br>\n","`1,2,1,2,1,2,....`\n","\n","1. We start the sequence `s` with the first item from the cycle `c`:<br>\n","`1`\n","\n","2. An index, `k`, into the, (expanding), sequence will step, or index through each item of the sequence 's' at its own rate.<br>\n","We will arrange that the `k`'th item of `s` states how many *times* the *last* item of `s`should appear at the end of `s`.\n","\n","We started `s` with `1` and therefore `s[k]` states that it should appear only the `1` time.<br>\n","\n","3. Increment `k`\n","\n","4. Get the next item from `c` and append it to the end of series `s`. `s` will then become:<br>\n","`1, 2`\n","\n","5. `k` was moved to the second item in the list and `s[k]` states that it should appear two times, so append another of the last item to the series `s`:<br>\n","`1, 2,2,` \n","\n","6. Increment `k`\n","\n","7. Append the next item from the cycle to the list:<br>\n","`1, 2,2, 1`\n","\n","8. `k` is now at the third item in the list that states that the last item should appear twice so add another copy of the last item to the series `s`:<br>\n","`1, 2,2, 1,1`\n","\n","9. increment k\n","\n","..."]},{"metadata":{"id":"mmfwF9RgIAoJ","colab_type":"text"},"cell_type":"markdown","source":["## Cycle\n","Lets cyclicly access the members of a tuple, in turn."]},{"metadata":{"id":"rgwN4P01IAoM","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}}},"cell_type":"code","source":["import itertools\n","\n","start_items = (1, 2)\n","\n","c = itertools.cycle(start_items).__next__"],"execution_count":0,"outputs":[]},{"metadata":{"id":"myYxnRcbIAoV","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"8c12532f-5012-46c7-c711-7d4e1b43c2f5"},"cell_type":"code","source":["# quick example\n","for _ in range(8):\n","    print(c(), end=', ')\n","print()\n","#"],"execution_count":0,"outputs":[{"output_type":"stream","text":["1, 2, 1, 2, 1, 2, 1, 2, \n"],"name":"stdout"}]},{"metadata":{"id":"Hfs7bmdqIAoe","colab_type":"text"},"cell_type":"markdown","source":["## Lets code"]},{"metadata":{"id":"A2c9p1NdIAoh","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"c9482e88-da36-4ff8-95c6-49626bceb4cc"},"cell_type":"code","source":["MIN_SIZE = 22\n","c = itertools.cycle(start_items).__next__\n","s, k = [], 0\n","while len(s) < MIN_SIZE:\n","    s.append(c())\n","    if s[k] > 1:\n","        s += s[-1:] * (s[k] - 1)\n","    k += 1\n","    print(k, s)\n"],"execution_count":0,"outputs":[{"output_type":"stream","text":["1 [1]\n","2 [1, 2, 2]\n","3 [1, 2, 2, 1, 1]\n","4 [1, 2, 2, 1, 1, 2]\n","5 [1, 2, 2, 1, 1, 2, 1]\n","6 [1, 2, 2, 1, 1, 2, 1, 2, 2]\n","7 [1, 2, 2, 1, 1, 2, 1, 2, 2, 1]\n","8 [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2]\n","9 [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1]\n","10 [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2]\n","11 [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1]\n","12 [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2]\n","13 [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1]\n","14 [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2]\n","15 [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1]\n"],"name":"stdout"}]},{"metadata":{"id":"ybVuyhqLIAon","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"61189b91-4425-468a-834b-fa0400602b2a"},"cell_type":"code","source":["s"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1]"]},"metadata":{"tags":[]},"execution_count":4}]},{"metadata":{"id":"-IYeyFjOIAov","colab_type":"text"},"cell_type":"markdown","source":["## Special property: Its own RLE\n","The sequence that gives counts of the runs of each number gives the number itself:\n","\n","I.e: In `s` there is `1` one then `2` twos, then `2` ones, then `1` two ... which gives 1, 2, 2, 1, ...; which is also the original series`s`."]},{"metadata":{"id":"Onw3-3otIAow","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"f5d042fb-8685-48ea-f652-c407d3788c9d"},"cell_type":"code","source":["def run_len_encoding(truncated_series):\n","    rle, count, last = [], 0, None\n","    for this in truncated_series:\n","        if this != last and count:\n","            rle.append(count)\n","            count = 0\n","        last = this\n","        count += 1\n","    return rle[:-1]  # Not sure of last element in RLE so remove it\n","print(run_len_encoding(s))"],"execution_count":0,"outputs":[{"output_type":"stream","text":["[1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1]\n"],"name":"stdout"}]},{"metadata":{"id":"Pzx2wLaAIAo3","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}}},"cell_type":"code","source":["rle = run_len_encoding(s)\n","assert s[:len(rle)] == rle, 'Whoops RLE != original series'"],"execution_count":0,"outputs":[]},{"metadata":{"id":"l-zIIF16IAo9","colab_type":"text"},"cell_type":"markdown","source":["## Lets package things up a bit better"]},{"metadata":{"id":"wVJa5oxsIApA","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}}},"cell_type":"code","source":["def kolakoski_gen(start_items):\n","    c = itertools.cycle(start_items).__next__\n","    s, k = [], 0\n","    while True:\n","        c_next = c()\n","        s.append(c_next)\n","        sk = s[k]\n","        yield sk\n","        if sk > 1:\n","            s += [c_next] * (sk - 1)\n","        k += 1\n","\n","def kolakoski(start_items=(1, 2), length=22):\n","    return list(itertools.islice(kolakoski_gen(start_items), length))"],"execution_count":0,"outputs":[]},{"metadata":{"id":"IDB_P5QaIApK","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"30a9867d-aaa3-4a58-9ede-7d62cd1311e2"},"cell_type":"code","source":["k = kolakoski()\n","k"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1]"]},"metadata":{"tags":[]},"execution_count":8}]},{"metadata":{"id":"z44qngVdIApQ","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}}},"cell_type":"code","source":["def is_series_eq_its_rle(series):\n","    rle = run_len_encoding(series)\n","    return series[:len(rle)] == rle"],"execution_count":0,"outputs":[]},{"metadata":{"id":"0h363tOEIApV","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"9e656148-2a50-4644-e5e0-7b7478ef47c3"},"cell_type":"code","source":["is_series_eq_its_rle(kolakoski())"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["True"]},"metadata":{"tags":[]},"execution_count":10}]},{"metadata":{"id":"HS4kjuMKIApe","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"abf1dd12-8a23-49a1-ae77-b29d93efa550"},"cell_type":"code","source":["def run_len_encoding2(truncated_series):\n","    # alternate implementation\n","    return [len(list(group)) for grouper, group in itertools.groupby(truncated_series)][:-1]\n","run_len_encoding(k)"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1]"]},"metadata":{"tags":[]},"execution_count":11}]},{"metadata":{"id":"BHc_P8E2IApm","colab_type":"text"},"cell_type":"markdown","source":["# Starting from other cycles\n","\n","Other series, with that same property of being their run length encoding can be created by starting from a cycle of other integers, (subject to a few rules).\n","\n","There is really only the one rule\n","* the *cycle* should not produce the same integer more than *once* in succession.\n","\n","The above rule, when applied to the original tuple of items `start_items` becomes:\n","1. No integer should appear twice or more in succession, in the the order of `start_items`\n","2. The first and last items of `start_items` must be different."]},{"metadata":{"id":"DLWEQ7RBIApo","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}}},"cell_type":"code","source":["def items_ok(start):\n","    return len(start) >= 2 and all(run_length==1 for run_length in run_len_encoding(start + start))"],"execution_count":0,"outputs":[]},{"metadata":{"id":"0pfuUWoPIApr","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"1a29ece1-28a9-4fdd-9c4c-89d92cd88c9c"},"cell_type":"code","source":["# What we have tried\n","items_ok((1, 2))"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["True"]},"metadata":{"tags":[]},"execution_count":13}]},{"metadata":{"id":"1C8F_RrGIApw","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"67a832c3-61f2-4002-ea4a-6857701c4886"},"cell_type":"code","source":["# will this work?\n","start_items = (2,1)\n","items_ok(start_items)"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["True"]},"metadata":{"tags":[]},"execution_count":14}]},{"metadata":{"id":"SeUn3qPnIAp6","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"a19a74b9-e0a7-419e-856f-2db174e43a43"},"cell_type":"code","source":["# Lets see it\n","k2 = kolakoski(start_items)\n","k2"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1]"]},"metadata":{"tags":[]},"execution_count":15}]},{"metadata":{"id":"2LRW_auyIAqN","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"c8413351-56aa-4068-d0b8-ce7c53ca50f1"},"cell_type":"code","source":["rle2 = run_len_encoding(k2)\n","rle2"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1]"]},"metadata":{"tags":[]},"execution_count":16}]},{"metadata":{"id":"hebImDt8IAqV","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"b125269f-8b88-4a1d-b200-35b0115ec12c"},"cell_type":"code","source":["is_series_eq_its_rle(k2)"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["True"]},"metadata":{"tags":[]},"execution_count":17}]},{"metadata":{"id":"VJcx17E-IAqb","colab_type":"text"},"cell_type":"markdown","source":["So (2, 1) was OK.\n","\n","## A longer cycle: (1, 3, 1, 2)"]},{"metadata":{"id":"bZarHGE5IAqd","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"1c1628d0-56ff-4b5f-f865-7a96c0050052"},"cell_type":"code","source":["start_items = (1, 3, 1, 2)\n","# Should it work?\n","items_ok(start_items)"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["True"]},"metadata":{"tags":[]},"execution_count":18}]},{"metadata":{"id":"nMi2N8ptIAqt","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"2294ce61-b8cd-48c8-a340-63fa48e88d7e"},"cell_type":"code","source":["# Lets see it\n","k3 = kolakoski(start_items, 128)\n","print(k3)"],"execution_count":0,"outputs":[{"output_type":"stream","text":["[1, 3, 3, 3, 1, 1, 1, 2, 2, 2, 1, 3, 1, 2, 2, 1, 1, 3, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 1, 3, 3, 3, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 2, 1, 1, 1, 3, 3, 3, 1, 2, 1, 1, 3, 1, 1, 1, 2, 2, 2, 1, 1, 1, 3, 1, 2, 1, 1, 3, 1, 2, 2, 2, 1, 1, 1, 3, 1, 2, 2, 1, 3, 1, 2, 2, 2, 1, 1, 1, 3, 3, 3, 1, 2, 2, 1, 3, 1, 1, 1, 2, 1, 3, 1, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 1, 1, 2, 1, 3, 3, 3, 1, 2, 2, 1]\n"],"name":"stdout"}]},{"metadata":{"id":"QZ_uL5StIAqx","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"6e45a39d-015b-4fff-a49a-15700b08f3ea"},"cell_type":"code","source":["rle3 = run_len_encoding(k3)\n","print(rle3)"],"execution_count":0,"outputs":[{"output_type":"stream","text":["[1, 3, 3, 3, 1, 1, 1, 2, 2, 2, 1, 3, 1, 2, 2, 1, 1, 3, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 1, 3, 3, 3, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 2, 1, 1, 1, 3, 3, 3, 1, 2, 1, 1, 3, 1, 1, 1, 2, 2, 2, 1, 1, 1, 3, 1, 2, 1, 1, 3, 1]\n"],"name":"stdout"}]},{"metadata":{"id":"RG4XHgBUIAq0","colab_type":"code","colab":{"autoexec":{"startup":false,"wait_interval":0}},"outputId":"ccbd2e2c-b9c8-4c4e-d922-0441cb2dd48b"},"cell_type":"code","source":["is_series_eq_its_rle(k3)"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["True"]},"metadata":{"tags":[]},"execution_count":21}]},{"metadata":{"id":"BKQ2wNixIAq9","colab_type":"text"},"cell_type":"markdown","source":["\n","\n","# END."]}]}