Problem 4: Get the Cake (100pts)

Problem

Nanami Chiaki heard that you are learning SICP and feel interested in high order functions. She designed the following missions to test your understanding. If you solve the missions correctly, Nanami will give you a "cake" as gift.

The missions function consists of three sub missions: mission1, mission2 and mission3. The inner function mission3_inner returns a variable cake.

Your task is to write a higher order function so that it calls three mission functions in turn and return the hidden cake. Please note that you are not allowed to return variable cake or print the messages directly. A correct solution contains only one expression.

Wish you success!

七海千秋 (Nanami Chiaki) 听说您正在学习 SICP，并对高阶函数很感兴趣。她设计了以下任务来检验您的理解。如果您正确解决了这些任务，七海将送您一块“蛋糕”作为礼物。

任务函数由三个子任务组成：mission1、mission2 和 mission3。内部函数 mission3_inner 返回一个变量 cake。

您的任务是编写一个高阶函数，使其依次调用这三个任务函数并返回隐藏的蛋糕。请注意，您不被允许直接返回变量 cake 或打印任何消息。一个正确的解决方案只包含一个表达式。

祝您成功！

def missions(f):
    """DO NOT EDIT THIS FUNCTION"""
    def mission1(f):
        if f(0) == 0 and f(1) == 2:
            print('MISSION 1 SOLVED')
            return lambda g: mission2(g(f))
        else:
            print('MISSION 1 FAILED')

    def mission2(f):
        if f(0) == 0 and f(1) == 2:
            print('MISSION 2 SOLVED')
            return mission3(0, 0)
        else:
            print('MISSION 2 FAILED')

    def mission3(f, g):
        def mission3_inner(f):
            if f == g:
                return mission3(f, g + 1)

        if g == 5:
            print('MISSION 3 SOLVED')
            return 'The cake is a lie.'
        else:
            return mission3_inner

    return mission1(f)


def get_the_cake(missions):
    """
    Write a higher order function so that it calls three
    mission functions in turn and return the hidden cake.
    You are not allowed to return variable cake or print
    the messages directly. A correct solution contains
    only one expression.

    By the way, do you know that "The cake is a lie" is 
    a catchphrase from the 2007 video game Portal? Visit
    https://en.wikipedia.org/wiki/The_cake_is_a_lie
    if you have never played Portal before!

    >>> the_cake = get_the_cake(missions)
    MISSION 1 SOLVED
    MISSION 2 SOLVED
    MISSION 3 SOLVED
    >>> the_cake
    'The cake is a lie.'
    >>> # check that your answer consists of nothing but an
    >>> # expression (this docstring) and a return statement
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(get_the_cake)).body[0].body]
    ['Expr', 'Return']
    """
    return "*** YOUR CODE HERE ***"

Hints

仔细理解 missions 函数，建议每完成一个 mission 就运行一下。
get_the_cake 的返回值应该形如 missions(arg)(arg)(arg)...。注意每次传入的参数的类型。
注意 mission3 函数的返回值也是函数。为完成任务三，你可能需要多次调用函数。
调用 mission3_inner 函数时，传入的参数 f 会覆盖 mission3 中原有的参数 f。

Solutions

注意 missions 函数返回的是 mission1(f)，我们需要传入一个参数 f，使得 mission1(f) 打印 'MISSION 1 SOLVED'。

为此，我们应使 f(0) == 0 and f(1) == 2，可以让 \(f(x)=2x\)。当然只要满足这个关系就行。

def get_the_cake(missions):
    return missions(lambda x: 2 * x)

注意 mission1 返回了 lambda g: mission2(g(f))，他向 mission2 传入了一个参数 g(f)。

注意 mission1 和 mission2 结构非常相似，要解决 mission2 我们可以让 g(f) 和 f 是同一个函数。

考虑 g = lambda x: x，我们便离成功更近了一步。

def get_the_cake(missions):
    return missions(lambda x: 2 * x)(lambda x: x)

接下来看到任务三，在任务二中我们返回了 mission3(0, 0)，此时的 g 为 0，而我们需要让 g 变成 5。

当什么时候 g 会加一？我们需要当 mission3 返回 mission3_inner 时，让 f == g。

注意这里调用 mission3_inner 函数时，传入的参数 f 会覆盖 mission3 中原有的参数 f。

我们现在可以传入一个 0，这样会有 f == g，那么便返回了 mission3(0, 1)。

现在 g 变成了 1，mission3(0, 1) 又会返回函数 mission3_inner。

我们要让 g 再加一，与前面类似，让 f == g，我们应该传入一个 1，这样就返回了 mission3(1, 2)。

以此类推，当我们传入 4 时，返回的就是 mission3(4, 5)，这时 g == 5，我们终于解决了这个问题。

def get_the_cake(missions):
    return missions(lambda x: 2 * x)(lambda x: x)(0)(1)(2)(3)(4)