nilknarf

For example in this problem https://codeforces.com/contest/1285/problem/E, one solution is to parse and count the number of top-level parentheses after small modifications. For example the original string might be "(()())()". Then "(()())" is 1, "(())()" is 2, "()()()" is 3.

This is solved with the following monoid to make incremental reparsing fast:

    neutral = Node(0, 0, 0)


    def combine(x, y):
        # Each node tracks numClose, numCount, numOpen:
        # e.g., )))) (...)(...)(...) ((((((
        if x.open == y.close == 0:
            ret = x.close, x.count + y.count, y.open
        elif x.open == y.close:
            ret = x.close, x.count + 1 + y.count, y.open
        elif x.open > y.close:
            ret = x.close, x.count, x.open - y.close + y.open
        elif x.open < y.close:
            ret = x.close + y.close - x.open, y.count, y.open
        return Node(*ret)

Monoid cached trees are extremely popular in competitive programming, but never by that name. It's always referred to as a "segment tree" without using any mathematical terminology more advanced than "associativity".

Due to its popularity, all kinds of crazy monoid states have already been explored (though you need to squint a bit to see them due to the terminology mismatch): https://codeforces.com/blog/entry/15890. I've never seen stack used though. You almost always want to compress the state as much as possible and the problems I've seen only needed stack depth (aka the bicyclic semigroup), not contents. Requiring O(N) to merge also highly limits its use cases.

Anyway, not sure how relevant this is to you since the use of monoids in data structures and for parallelism is slightly different (binary merges all the way down versus stopping at some chunk size).

"Automatic Inversion Generates Divide-and-Conquer Parallel Programs": https://core.ac.uk/download/pdf/192663016.pdf

which is based on "The Third Homomorphism Theorem": http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/th...

The motivating example is whether you can generate a mergesort (where the monoid is combine two sorted lists) given an implementation of an insertion sort (where the sequential program is inserting one element by one into a sorted list).

I remember being disappointed by the answer after reading these papers but in the citation graph there are a bunch of relatively recent program synthesis papers. Maybe there's something better now.

I lost interest in this approach because it was way more practical to give up on serverless in exchange for only scanning in one direction instead of both ways (e.g., scan a QR code once on mobile to both open the webpage and join a websocket channel, then use it to upgrade to a webrtc connection). It's a neat trick for use cases like AR.js where this is natural to do: https://github.com/jeromeetienne/AR.js

The flow is very similar to yours, down to the flashing QR codes! https://youtu.be/rw4f9LfqqpI?t=8

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45....

Off-topic: Can you fill out your profile? I am not active on HN but I sometimes go by the initials fta elsewhere

[1]https://www.cs.cmu.edu/~venkatg/teaching/CStheory-infoage/

[2]https://www.cs.cornell.edu/jeh/book2016June9.pdf

Flashing qr codes was just a quick hack and actually doesn't work super well. I think if I had more time I would try compressing and stripping down the message more so it would fit in a single qr code instead (like in https://webrtchacks.com/the-minimum-viable-sdp/).

Someone then asked whether it is also possible in Chrome and Node: https://github.com/fta2012/ReplicatedRandom/issues/2. After examining the MWC1616 code I saw the same “two concatenated sub-generators” problem explained in this post. The implication of it is that you can brute force the top and bottom 16 bits independently. So it is also easy since that’s just doing 2^16 possibilities twice! Code: https://gist.github.com/fta2012/57f2c48702ac1e6fe99b

I had a demo for the 'inverse' transform also: http://codepen.io/fta/pen/LHonf

Here is the same thing except using the video from this post: http://codepen.io/fta/pen/JoGybG

I used Lazarsoft's javascript QR code scanner which worked, but it wasn't very robust since it was a manual port of an early version of zxing. It is pretty easy to compile the c++ branch of zxing v2.3 using emscripten but it is a pain to optimize: https://github.com/fta2012/zxing-emscripten (or demo link: http://fta2012.github.io/zxing-emscripten/).