#31

StevenPZChan
StevenPZChan
8 min read

Categories

Tags

继续挑战，开始变得美了

第31题地址grandpa.html

  • grandpa.jpg
  • 网页标题是Where am I?，题目内容为空，源码里面有一行隐藏内容：

    <!– short break, this REALLY has nothing to do with Python –>

标题问在哪，图片有个链接grandpa.html，提示要密码，密码提示是island : country。很明显了，要找出图片是哪个国家的哪个岛，我们用Google的搜图：

from io import BytesIO
import requests

with requests.Session() as sess:
    sess.auth = ('repeat', 'switch')
    response = sess.get('http://www.pythonchallenge.com/pc/ring/grandpa.jpg').content
    data = requests.urllib3.encode_multipart_formdata({
        'encoded_image': (None, response)
    })
    header = {'Content-Type': data[1]}
    search_image = sess.post('https://www.google.com/searchbyimage/upload', data=data[0],
                             headers=header, allow_redirects=False)
    print(search_image.headers)

{'Location': 'https://www.google.com/search?tbs=sbi:AMhZZisp2a0LMhliMh47qE2wSFpJ3IbHE3Sm5U8XmVp6FOBfKy0ZymDGthiIjhCsCRRHuNwF2fLyA1Zj6psMCCLNJaCUDCeDI-lBJwZAtPlNJxK89uYEIM3C0fUshJBkMd5hCuCplOVImxTnCsxctt4A1e-PDLY1JlxN4uPhuqCuhUplUHZlAKh7AbJh0vhCg4C0LHxPwWIX754PVr6J9iv0u94CSG2DGHmhHRb4yx1M0w8SBkLb9fj4HJ4YmZzQZInctinkikuk54qqF1xiyFjJ8fRZgU6YgAnXz1DUzdHWtNKoC5DEHCXuKrIyJ3Im9h2EaVxvV6Si', 'Cache-Control': 'public, max-age=21600', 'Date': 'Mon, 03 Feb 2020 15:36:15 GMT', 'Expires': 'Mon, 03 Feb 2020 21:36:15 GMT', 'Content-Type': 'text/html; charset=UTF-8', 'X-Content-Type-Options': 'nosniff', 'Server': 'quimby_frontend', 'Content-Length': '567', 'X-XSS-Protection': '0', 'X-Frame-Options': 'SAMEORIGIN', 'Alt-Svc': 'quic=":443"; ma=2592000; v="46,43",h3-Q050=":443"; ma=2592000,h3-Q049=":443"; ma=2592000,h3-Q048=":443"; ma=2592000,h3-Q046=":443"; ma=2592000,h3-Q043=":443"; ma=2592000'}

打开搜索结果可以看到图片所在地为Koh Samui，位于泰国：

阁沙梅岛（泰语：เกาะสมุย），一译苏美岛、苏梅岛，是泰国的一个岛屿，在行政区划上属于素叻他尼府阁沙梅县。
该岛是泰国第三大岛屿，仅次布吉岛和阁昌岛（象岛）。位于首都曼谷南方约560公里处，长21公里，宽25公里，总面积228.7平方公里，人口约50,000人（2008年）。当地人民以务农为主，其中椰子的生产是重要经济来源，岛上的椰树随处可见，所以此岛又被称为“椰子岛”；近年亦发展为泰国受欢迎的旅游点之一。

From wikipedia.org

打开链接grandpa.html，输入用户名kohsamui，密码thailand，来到了新的页面：

  • mandelbrot.gif
  • 网页标题是UFOs ?，题目内容为That was too easy. You are still on 31...，源码里面没有隐藏内容，但在<img>标签里面放了两个奇怪的标签：

    <window left=”0.34” top=”0.57” width=”0.036” height=”0.027”/>
    <option iterations=”128”/>

看来这里才是这题的重头戏。
图片长得挺好看的，一看图片名叫mandelbrot.gif，原来是一种著名的分形结构：

曼德博集合（Mandelbrot set，或译为曼德布洛特复数集合）是一种在复平面上组成分形的点的集合，以数学家本华·曼德博的名字命名。曼德博集合与朱利亚集合有些相似的地方，例如使用相同的复二次多项式来进行迭代。

曼德博集合可以用复二次多项式来定义：
\(f_{c}(z)=z^{2}+c\)
其中 c 是一个复数参数。
从 \(z = 0\) 开始对 \(f_c(z)\) 进行迭代：
\(z_{n+1} = z_n^2 + c, n=0,1,2,...\)
\(z_0 = 0\)
\(z_1 = z_0^2 + c = c\)
\(z_2 = z_1^2 + c = c^2 + c\)
每次迭代的值依序如以下序列所示：
\((0, f_c(0), f_c(f_c(0)), f_c(f_c(f_c(0))), \ldots)\)
不同的参数 c 可能使序列的绝对值逐渐发散到无限大，也可能收敛在有限的区域内。
曼德博集合 M 就是使序列不延伸至无限大的所有复数 c 的集合。

曼德博集合一般用计算机程序计算。对于大多数的分形软件，例如Ultra fractal，内部已经有了比较成熟的例子。下面的程序是一段伪代码，表达了曼德博集合的计算思路。

For Each c in Complex
 repeats = 0
 z = 0
 Do
  z = z^2 + c
  repeats = repeats + 1
 Loop until abs(z) > EscapeRadius or repeats > MaxRepeats '根据定理三，EscapeRadius可设置为2。
 If repeats > MaxRepeats Then
  Draw c,Black                                            '如果迭代次数超过MaxRepeats，就将c认定为属于曼德博集合，并设置为黑色。
 Else
  Draw c,color(z,c,repeats)                               'colo函数用来决定颜色。
 End If
Next
From wikipedia.org

根据伪代码，对于每一个c都要画上不同的颜色，这个c应该是通过像素坐标来生成的复数，x y坐标分别对应实部和虚部；而画的这个颜色就是根据迭代使得模长超过2的次数决定的。
显然源码中的奇怪标签就是生成这张曼德博图的参数。window里的left top width height是将x y坐标转化成复数c的，而iterations是指求颜色时最大的迭代次数。
现在让我们来生成一个：

from itertools import product
from PIL import Image

def mandelbrot(size, left, top, width, height, max_iter) -> Image:
    img = Image.new('L', size)
    img_data = img.load()
    for x, y in product(range(img.width), range(img.height)):
        c = complex(left + x * width / img.width, top + y * height / img.height)
        z = 0
        for i in range(max_iter):
            z = z * z + c
            if abs(z) > 2:
                break
        img_data[x, y] = i
    return img

mandelbrot((640, 480), 0.34, 0.57, 0.036, 0.027, 128)

png

啊，跟题目原图长得非常得像，需要翻转一下。同时我们将图像差别记录下来：

from io import BytesIO
import requests
from PIL import Image

with requests.Session() as sess:
    sess.auth = ('kohsamui', 'thailand')
    response = sess.get('http://www.pythonchallenge.com/pc/rock/mandelbrot.gif').content
    img = Image.open(BytesIO(response))

left, top, width, height = 0.34, 0.57, 0.036, 0.027
iterations = 128
img_new = mandelbrot(img.size, left, top, width, height, iterations).transpose(Image.FLIP_TOP_BOTTOM)
diff = [(a, b) for a, b in zip(img.getdata(), img_new.getdata()) if a != b]
print('count:', len(diff))
print(diff[:20])

count: 1679
[(43, 59), (48, 64), (44, 60), (40, 56), (45, 61), (36, 52), (67, 51), (39, 55), (84, 68), (70, 86), (83, 67), (37, 53), (71, 55), (40, 56), (49, 65), (51, 67), (36, 52), (48, 64), (69, 85), (36, 52)]

看上去也很有规律，都是相差16。
先用上一题的质因数分解看看：

def prime_factor(n: int) -> tuple:
    factors = []
    while n > 1:
        for i in range(2, n // 2 + 1):
            if n % i == 0:
                factors.append(i)
                n //= i
                break
        else:
            factors.append(n)
            break
    return tuple(factors)

print(prime_factor(len(diff)))

(23, 73)

也是唯一的分解方式：\(1679=23\times73\)，所以图像大小为(23, 73)，差值用二值化表示出来：

from PIL import Image

img_diff = Image.new('L', prime_factor(len(diff)))
img_diff.putdata([(print(f'abs({a} - {b}) != 16!!!') if abs(a - b) != 16
                   else bool(a > b)) for a, b in diff], 256)
img_diff

png

图片非常小，不过我们隐约看到有一个小人和一些象形图案，联系标题UFOs ?可以知道，这是人类向宇宙发射的代表人类文明的著名信息：

阿雷西博信息（Arecibo Message），是于1974年11月16日以距离地球25,000光年的球状星团M13为目标，发送的无线电信息。该信息共有1,679个二进制数字(ASCII)，而且1,679这个数字只能由两个质数相乘，因此只能把信息拆成73条横列及23条直行，这是假设该信息的读者会先将它排成一个长方形。如果把它排成23条横列，它会变成白色噪声，相反如果把它排成73条横列，便可排出图中的一幅信息。 From wikipedia.org

把地址改为arecibo.html，来到了下一题。

总结：这一题需要有将数学表达（或伪代码）转化为实际代码的能力。顺便玩了下Google API的调用。

本题代码地址31_grandpa.ipynb
LinkedIn Reddit