When defining grammars, it is useful to know whether they are ambiguous, ie. whether the same output can be attained by two separate paths through the syntax tree. For example, given the grammar S := aS, aaS, ε, the string “aa” can be obtained either by applying the 1st rule twice or the 2nd rule once.
There is no general purpose algorithm to determine whether a grammar is ambiguous or not, and so here is a brute-force approach which enumerates all the words up to a certain depth (say, 5 rule applications) and determines whether the grammar is definitely ambiguous or potentially not.
The Sieve of Eratosthenes is a well known algorithm for finding primes. Typically, it is performed on a bounded set of N numbers to yield all primes less than N however with a few compromises, it is possible to make an infinite generator.
There is a solution floating around the code-scape using generator expressions which (on top of choking with python’s recursion depth) doesn’t properly follow the algorithm. This is the fake sieve:
Django Rest Framework provides a fast way to build APIs, expressing them as a set of serializers and views. I recently ran into a case where I wanted user-specific data to be included when a user is authenticated, but default to the generic serializer in all other cases.
/api/v1/items/2 (anonymous) 1 2 3 4 5 { "name": "Cannonball", "item_id": 2, "store_price": 5 } /api/v1/items/2 (authenticated) 1 2 3 4 5 6 { "name": "Cannonball", "item_id": 2, "store_price": 5, "favorited": true } This lead to two separate but similar serializers, only differing with the inclusion of the favorited field.
This simple decorator can significantly speed up recursive functions in python by storing solutions in a dictionary as it runs. The code uses the new typing library introduced in python 3.5 but it isn’t strictly necessary. It supports functions with any number of input parameters.
note: that the solution dictionary is tied to the function itself so multiple calls to the same function will reuse cached solutions from any previous calls.