「攻略」JetBrains Quest S1E3
书接上回，续 JetBrains Quest S1E2 之后，3月13日 JetBrains Quest 发布了本次最后一个挑战。因为感冒的原因，休息了一天，在周六深夜才发现题目已经出来了，又精神了起来。迷面如下：
Last Quest #JetBrainsQuest ⚔
SGF2ZSB5b3Ugc2VlbiB0aGUgcG9zdCBvbiBvdXIgSW5zdGFncmFtIGFjY291bnQ/
¶Stage 1
观察密文，只包含了大小写字母、数字以及符号/，是很典型的 Base64 编码，我们可以用 Node.js 的 Buffer 类直接进行解码，得到明文：
new Buffer.from("SGF2ZSB5b3Ugc2VlbiB0aGUgcG9zdCBvbiBvdXIgSW5zdGFncmFtIGFjY291bnQ/", 'base64').toString()
// 'Have you seen the post on our Instagram account?'
在 JetBrains 的主页 Footer 可以找到他们的 Instagram 帐号。最新的一篇 Post 链接在此。官方在此 Post 的留言如下：
Welcome to the final Quest! You should start on the Kotlin Playground: https://jb.gg/kotlin_quest
P.S. If you don’t know about the #JetBrainsQuest, it’s not too late to find out.
¶Stage 2
进入留言中的页面，会看到一个 Web IDE，需要完成一个 Kotlin 语言的挑战：
fun main() {
val s = "Zh#kdyh#ehhq#zrunlqj#552:#rq#wkh#ylghr#iru#wkh#iluvw#hslvrgh#ri#wkh#SksVwrup#HDS1#Li#zh#jdyh#|rx#d#foxh/#lw#zrxog#eh#hdv|#dv#sl1"
val n: Int = TODO()
for (c in s) {
print(c - n)
}
}
这和之前解的凯撒密码一样，只不过需要我们猜出 n 是多少，并填到 TODO() 处。不过如果做过之前的题目，可以发现这里一样是 # 对应了（空格），即 n = 3，或者直接使用 n = '#' - ' ' 也可以（省得查 ascii 表），我猜 kotlin 应该支持这样的语法。果不其然，运行后得到结果：
We have been working 22/7 on the video for the first episode of the PhpStorm EAP. If we gave you a clue, it would be easy as pi.
根据提示，我们可以找到 JetBrains 为 Phpstorm EAP 发布的视频介绍 Episode 1。在第 3:14 的时候，视频会 glitch 闪过一个画面，其中的 homepage 链接变成如下：
{
"name": "vendor_name/phpstorm2020.1",
"description": "description",
"homepage": "https://jb.gg/31415926",
...
}
¶Stage 3
打开链接，进入一个问答页。每次出现的问题都会不一样，不过所有的问题答案都可以在上一期的 20 周年年报中找到答案。我整理了一部分小抄：
JetBrains Quest Quiz
---
What year was JetBrains founded?
> Founded in February of 2000
What is the name of the newest JetBrains product?
> the recently announced integrated team environment, JetBrains SpaceTM.
Which country had the highest growing rate of downloads for 2019?
> Burkina Faso has been the fastest growing country 2,587% YoY
How much external funding have JetBrains received?
> Without any external funding!
How many people founded JetBrains?
> 3 as in this photo: 
Where is JetBrains headquarters?
> JetBrains has grown from a small startup in Prague (Capital of the Czech Republic)
How many employees does JetBrains have?
> 1,256 Team members across nine offices
How many developers use our products?
> 8M Developers use and trust our tools.
From the Forbes Top 100 digital companies, how many use our products?
> 95 Forbes Top 100 Digital Companies are our customers.
回答正确所有问题后，可以得到进入最后一关的提示：
You chose wisely.
Almost there! The last challenge is in the Tips of the Day of a specific IntelliJ IDEA Community version from our latest build page in Confluence, but… there is a catch. You have to know which version to look for. To find the build number, you need sight beyond sight:
. Not Everything Today Does All You Could Ask. Lessons Learned From Other Relevant Solutions, Possibly Even Another Kind Emerge. Risking Sometimes Being Liberal Or Generous Proves Ordinary Simple Tests Infinitely More Annoying. Get Examining Hidden Initial Designated Early Symbols. They Have Everything Needed, Except Xerox, To Completely Level Up Everything.
根据提示，我们需要找到某个特定版的社区版 IntelliJ IDEA，从它的每日贴士中找到线索。
首先我们从 JetBrains 的 Confluence 站点，找到 IDEADEV > Latest Build。在侧边栏的最下面，展开所有 Latest Builds 子面页。可以找到最后一项：IDEA 2020.1 Quest Build Edition
这里找得有点快，没有用到下面那段文字的线索。估计是因为很多人卡在这一步，JetBrains 直接简化了题目。不过如果仔细看下面那段话，每个单词的首字母都是大写，而不像上面那段话使用正常的拼写。于是我把首字体提取出来：
const secret = ". Not Everything Today Does All You Could Ask. Lessons Learned From Other Relevant Solutions, Possibly Even Another Kind Emerge. Risking Sometimes Being Liberal Or Generous Proves Ordinary Simple Tests Infinitely More Annoying. Get Examining Hidden Initial Designated Early Symbols. They Have Everything Needed, Except Xerox, To Completely Level Up Everything.";
const message = secret.split(' ').map(word => word[0]).join('');
// .NETDAYCALLFORSPEAKERSBLOGPOSTIMAGEHIDESTHENEXTCLUE
稍微分词一下：
.NET DAY CALL FOR SPEAKERS BLOG POST IMAGE HIDES THE NEXT CLUE
找到最新一期 .Net day call for speakers，查看以下图片的源码：
可以看到信息：
you_are_looking_for_build_201-6303
以上线索一样可以找到这个版本。
下载自己系统对应的版本。我选的是 macOS 的 dmg 包，735M！国内的朋友估计得慢慢下载了。安装后，打开并创建新项目，会弹出每日贴士。快速点击 Next Tip，最终你会看到这一条：
JETBRAINS QUEST: LAST PUZZLE
You have discovered our JetBrains Quest! If you don’t know what this is, you should start from the beginning.
This is it. The last puzzle. You are just one step away from glory!
Now you just need the Key to unlock the Quest page(https://www.jetbrains.com/promo/quest/).
The Key is the first and last 4 digits of the 50 * 10^6 position of the Fibonacci sequence (F(50 Million)).
As you may know by now, not all that glitters is gold, and to solve this puzzle you should not go straight for the obvious answer. May you make a glorious choice.
Remember that you have until the 15th of March 12:00 CEST.
¶Stage 4
最后一题要我们给出「Fibonacci 数列」第五千万位数字的前后各四位数字，组合的密码解锁最后的奖励。
那么这个数字有多大？虽然题目说希望我们不要直接去找答案，不过我们可以通过 Wolfram Alpha 这个知识搜索引擎给我们一个比较直观的答案。通过搜索 Fibonacci[50000000]，我们得到如下结果：
Fibonacci[50000000] ~= 4.602... * 10^10449381
这个天文数字奇大无比，竟然有 10,449,382 位（4 后面 10,449,381 个 0）。这意味着我们如果我们要自己写程序来解决这个问题，没办法用普通 Integer 或者 IEEE754 浮点型来表示。不过好再 Javascript 在 ES6 之后引入了 BigInt 大整型数，能够表达任意位数的整数，并进行计算。
除了精度问题，我们还需要一个比较高效的算法来解决这个数列。这里有一篇关于计算 Fibonacci Numbers 的论文。里面提到了一种分治算法，可以以 O(n) = Log(n) 的时间复杂度来计算 Fabonacci 数列通项。
另外我们还可以借助 lodash 的 _.memoize() 函数来避免 Fabonacci 数列递归过程中的重复计算。
作为前端开发者，我深知单线程的 Javascript 并不擅长运算密集型任务，不过我还是乐意试一试。以下是 node.js 代码：
const _ = require('lodash');
const fib = _.memoize((n) => {
if (n <= 1) return n;
if (n % BigInt(2) === BigInt(1)) {
const a = fib(n >> BigInt(1));
const b = fib((n >> BigInt(1)) + BigInt(1));
return a * a + b * b
}
const a = fib(n >> BigInt(1));
const b = fib((n >> BigInt(1)) - BigInt(1));
return a * (a + BigInt(2) * b);
});
console.log(fib(BigInt(process.argv[2])));
由于 nodejs 12.x 还不支持最新的 BigInt 语法 1000n，所以这里手动用 BigInt 封装了一下所有数字。还需要把 1 / 2 * n 用位运算代替 n >> 1，因为 BigInt 不支持除法以及浮点数相乘。另外需要注意位运算结果不保留浮点数部分。调试完毕后，运行并等待结果：
$ node fib 50000000 > result.txt
这将是一个漫长的等待，于是我做了 Plan B。刚才的 Wolfram 查询其实已经给了我们前四位的答案了：4.602...。
其实 Wolfram 还支持比较高级的查询，例如the first 4 digits of fabonacci[50000000]。可惜运行后一直在等待计算，由于免费用户的计算时间比较短，最后超时了。如果数字比较小，这个查询是可以比较快得出结果的。可想而知 the last 4 digits of fabonacci[50000000] 也一样超时了。
难道我们无计可施了吗？其实还有一个办法，我试求了 fibonacci[50000000] mod 10000。模运算，将 fib-50000000 除以 10000 取余数，即可得后四位。Wolfram 很快给出了答案：3125。
至此我们已经得到了问题的答案：46023125。不过答题的期限是 15th of March 12:00 CEST （中欧夏令时），即墨尔本的 15 日晚上 10 点，时间还有得是。于是我准备上床去睡一觉，也许第二天早上醒来结果就出来了。
早上起来给曦仔换完尿布，跑来摸了一下电脑，已经冰凉。CPU 肯定已经完成工作在睡大觉了。解锁电脑，看到命令行正在等待输入。而 result.txt 已经躺在硬盘里。
$ ll -lt result.txt
20416 -rw-r--r-- 1 mutoo staff 10M 15 Mar 02:28 result.txt
这是一个有 10M 大小的文件。检查一下头尾：
$ head -c 10 result.txt
4602713413%
$ tail -c 10 result.txt
39453125n
很好，头尾四位正是 4602 与 3125，最后 n 表示 BigInt。对这个数字结果有兴趣的朋友，可以查看我提交的这个 gist。
通过一些日志，我得知这个代码在我的 2016 年 Macbook（2.9GHz i5, 16G Memory）上跑了近两个小时（6827679.554ms / 1000 / 60 / 60 ~= 1.90hours）。
单线程的 Javascript 还是没有辜负我的期望。不过如果使用一些多线程的算法，应该可 极大的压缩这个时间。
最后的奖品是 JetBrains 全家桶包年订阅 8 折优惠劵一张，助（祝）大家编码愉快！