py-in-the-sky

"""
https://code.google.com/codejam/contest/4284486/dashboard

Key insight: any digit in S_googol is ultimately a reversal/switch
of a zero that was inserted between two strings. If we can somehow
count the number of switches, then we'll know whether the digit is
a 1 or 0.

Knowing the position of these middle zeros and reverse-engineering
the reversals from a given index to an index of one of the middle

py-in-the-sky

"""
Lucky Dip: https://codejam.withgoogle.com/codejam/contest/9234486/dashboard#s=p1

Concept Inventory:

* Optimal Play: To play optimally, you choose to redip if your current
dip's value is less than the expected value of redipping. Otherwise,
you stick with your current draw.
* Expected Value of a Dip: The expected value of a dip, given that the player
plays optimally, depends on the probability of drawing a value that is less

py-in-the-sky

"""
My implementation of a branch-and-bound solution to the Knapsack problem.

See section 3.8 of the book Computer Science Distilled by Wladston Ferreira Filho.
"""


from my_abstract_data_types import *

py-in-the-sky

"""
Best Trade

Given a list of prices of some stock, determine the maximum
money that could be made from buying and then selling once.
That is, find the value (prices[sell_index] - prices[buy_index])
such that len(prices) > sell_index >= buy_index >= 0 and for all
other such index pairs (sell_index_2, buy_index_2), it is
the case that:

py-in-the-sky

"""
Written after seeing a similar program in the MIT/EDX course
Advanced Software Construction in Java.
"""


def convert(n, base):
    assert 2 <= base <= 16

    if n == 0:

py-in-the-sky

"""
My variation of the Python bisect functions, inspired by my reading
of chapter 4 of Beautiful Code.

Studying the source code of Python's bisect module has been
very enlightening for me, both about binary search and about
setting up and reasoning about loop invariants in order to
ensure the correctness of a program.

Chapter 4 of Beautiful Code introduced me to slightly different

py-in-the-sky

"""
Very Simple Integer-arithmetic Evaluator


Grammar:

    ARITHMETIC  =>  TERM | TERM [+-] ARITHMETIC
    TERM        =>  FACTOR | FACTOR [*/] TERM
    FACTOR      =>  INT | '(' ARITHMETIC ')' | [+-] FACTOR
    INT         =>  [1-9][0-9]*

py-in-the-sky

"""
The parser below is a predictive, recursive-descent parser. The use of a predictive parser
is possible because JSON has an LL(k) grammar. Specifically, JSON has an LL(1) grammar,
a fact that is hinted at in the `parse_json` function: `parse_json` looks ahead by only
one character (not even a whole JSON token) in order to decide how to parse the string.
See: https://en.wikipedia.org/wiki/Recursive_descent_parser

JSON definition: http://www.json.org/
JSON-Python type mapping: https://docs.python.org/2/library/json.html#encoders-and-decoders

py-in-the-sky

/*
Needed to mock a promise for a test just so that chaining `then`s
and `catch`es wouldn't throw an error.  The actual execution of
those `then`s and `catches` could be no-ops since the test wasn't
concerned with their functionality.

The mocked promise (`returnMockThenable()`) was returned from a mock
`fetch` call.
*/

py-in-the-sky

// Works in Chrome devtools console.
/* Yields each non-array element from a potentially nested array. */
function* lazyFlatten (element) {
    if (!Array.isArray(element))  
        yield element;  // yield non-array element
    else
        for (var element2 of element)  // unpack array into sub-elements
            for (var element3 of lazyFlatten(element2))  // flatten each sub-element...
                yield element3;  // and yield its elements
}