This post is my note for What is seminar on Lambda Calculus.

Lambda calculus was created by Alonzo Church in the 1930s, and was used by him to solve Entscheidungsproblem in 1936, which is related to Hilbert's tenth problem. In the same year, Alan Turing independently solved Entscheidungsproblem using his invention Turing machine. Shortly after, Turing realized that these two models are actually equivalent as models of computation.

In this note, I will first give the formal definition of lambda expressions. Then with the help of Python, I am going to show how to do Boolean algebra and basic arithmetic using lambda calculus, which to some extend gives an illustration that Turing machine and lambda calculus are equivalent.

Definition

Lambda calculus consists of lambda expressions and operations on them. There are three basic elements in Lambda expression:

1. variables: x, y, z, ...
2. symbols in abstraction: λ and .
3. parentheses for association: ()

我现在用的博客生成软件是Hexo。这个软件可以快速将Markdown格式的文章转成html格式，并且包含发布到github page的工具。Hexo是基于Nodejs，所以某天我就在想有没有一个基于Python的博客生成软件。为什么我会这样想？因为

人生苦短，我用Python。

当然会有基于Python的博客生成软件：Pelican是最为突出的一个。事实上，我很喜欢Pelican！其中一个亮点是它的主题都是基于Jinja，这种简单统一的模版格式让用户很容易设计自己喜欢的主题。出于练手的原因，我将我喜欢的一个Hexo主题maupassant移植到Pelican了。

This post is my note for What is seminar on Cassini Ovals.

Definition

An ellipse is a geometric object formed by locus of points which have fixed sum of distances to two fixes foci.

In the above figure, we can express the definition of ellipses in one simple equation:

for some \(c>0\). What if we change the addition in the above equation to multiplication? This comes the definition of Cassini ovals.

这次比赛我表现得比较差，只能做出第一题和第三题。第四题比赛结束之后很快也写出来了，而第二题确实花了我一个多小时才能想出来。

第一题Maximum Product of Three Numbers

先将数组排序，那么最大值必然在下面四种情况中：

1. 第一个数 X 第二个数 X 第三个数
2. 倒数第一个数 X 倒数第二个数 X 倒数第三个数
3. 第一个数 X 倒数第一个数 X 倒数第二个数
4. 第一个数 X 第二个数 X 倒数第一个数

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return max(nums[0]*nums[1]*nums[2],
                    nums[-1]*nums[-2]*nums[-3],
                    nums[0]*nums[-1]*nums[-2],
                    nums[0]*nums[1]*nums[-1])

This post is my note for What is…? seminar on Rademacher function.

For a real number \(x\) in \([0, 1]\), let \((a_1(x), a_2(x), \cdots, a_n(x), \cdots)\) be its binary representation. That is to say, \[\begin{equation} x = \sum_{n=1}^\infty \frac{a_n(x)}{2^n}. \label{20170623-1} \end{equation}\]

For some \(x\), there might be two possible binary representation. Take \(\frac{1}{2}\) for example, it can be represented as \((1, 0, 0, \cdots)\) or \((0, 1, 1, \cdots)\). In this situation, we always prefer the former representation, in which all terms become \(0\) eventually.

This post is my note for What is…? seminar on Lüroth expansion.

Given a system of representation of real numbers in \((0, 1]\), we need to determine whether these representations are 1 to 1 corresponding the numbers in \((0, 1]\). Aslo we should study the (Lüroth) shift map: \[\begin{equation} T: (a_1, a_2, \cdots, a_n, \cdots) \mapsto (a_2, \cdots, a_n, \cdots). \label{20170620-2} \end{equation}\]

我最近入手了一个Raspberry Pi Zero W，作为平时消遣的一个小玩具。因为我主要是想在它上面运行一些小程序，所以我希望将它设置为最简单的服务器，然后通过ssh来访问。这篇文章记录了我从网上搜来的设置步骤，方便下次设置。

制作SD启动盘

首先说明一下：我的系统是Mac OSX。在制作SD启动盘过程中，我们需要修改启动盘的内容，Mac OSX是不支持启动盘的格式的，所以我们需要借助其他途径。我是用VitualBox的Ubuntu来修改启动盘的内容。

第一步：下载raspbian lite，解压得到一个后缀名为img的镜像文件。我得到的是：2017-04-10-raspbian-jessie-lite.img。

第一题Maximum Distance in Arrays

对于第i数组中，取出最大值a，最小值b，然后将(a, i)和(b, i)放进一个数组m里。将数组m按照第一个分量排序，那么对我们有用的只是数组m前面两个元素和后面两个元素。如果第一个元素和最后一个元素来自不一样的数组（第二个分量不一样），那么答案就是这两个元素的第一个分量的差。否则，我们要比较两种情况：第一个元素与倒数第二个元素，第二个元素与最后一个元素。

class Solution(object):
    def maxDistance(self, arrays):
        """
        :type arrays: List[List[int]]
        :rtype: int
        """
        m = []
        for i, a in enumerate(arrays):
            m.append((a[0], i))
            m.append((a[-1], i))
        m.sort(key=lambda x: x[0])
        if m[0][1]!=m[-1][1]:
            return m[-1][0]-m[0][0]
        return max(m[-2][0]-m[0][0], m[-1][0]-m[1][0])

第一题Can Place Flowers

简单的贪心。

class Solution(object):
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """
        cnt = 0
        for i in xrange(len(flowerbed)):
            if flowerbed[i] == 1:
                continue
            if i-1>=0 and flowerbed[i-1]==1:
                continue
            if i+1<len(flowerbed) and flowerbed[i+1]==1:
                continue
            flowerbed[i] = 1
            cnt += 1
        return cnt>=n

就着Gin的酒劲，我还能一次不WA的过了这次比赛哈哈。

第一题Longest Harmonious Subsequence

既然最大值与最小值恰好相差1，那么此子数组必定恰好有两个不一样的元素。我们只要统计每个元素出现的次数，然后枚举找出相邻两个元素出现次数之和的最大值就好。

class Solution(object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cnt = {}
        for n in nums:
            cnt[n] = cnt.get(n, 0) + 1
        ans = 0
        for k, v in cnt.items():
            if k-1 in cnt:
                ans = max(ans, v+cnt[k-1])
            if k+1 in cnt:
                ans = max(ans, v+cnt[k+1])
        return ans