补全程序题目详解（Season 1）

· · 科技·工程

前言

补全程序题比较难，一方面是因为要对程序逻辑本身有比较深的理解（从而也需要一定的代码阅读能力），一方面又要能够在有限的空间内（比如一个小小的空）精准完成任务。

比如这个：https://alf.nu/ReturnTrue?world=true。

这是一个考察 JavaScript 语言特性的小游戏，名副其实：题干给定函数，传入参数，使得函数的返回值为 true（似乎必须是布尔值的 true，数字之类的真值是不行的）。

另外：很多题目都有多种解法，可以自行 codegolf（探索长度最短的解）。受限篇幅这里就不进行 codegolf 了。所有答案以简洁而且原理清晰为主。

id

function id(x) {
    return x;
}

帮助了解游戏规则用的，填写 true。

reflexive

function reflexive(x) {
    return x != x;
}

这个答案的原理 C 和 C++ 里也成立。填写 NaN。

NaN 全称 Not A Number，是一种特殊的实数，一般在零除以零的时候出现（在 Unity 里编写运动的时候天天被这玩意烦）。NaN 并不是一个确定的值，它自己和自己是不相等的。

transitive

function transitive(x,y,z) {
    return x && x == y && y == z && x != z;
}

开始上难度了。如果没有基础，或许很难理解，JavaScript 里其实存在两种等于，通俗地讲可以是“弱等于”（宽松等于）和“强等于”（严格等于），同样也有对应的不等于版本。强等于，写法是三个等号 ===，要求等号两边类型和值均相同。这里用的是两个等号，是弱等于。

JavaScript 的弱等于是出了名的复杂与令人啼笑皆非。这里先给出本题答案：[[1]], "1", [1]。

理由如下：

弱等于的迷惑性就在于它会根据等号两边元素的类型来进行隐式类型转换。所以行为有时候看上去很迷惑，具体请见下图：

peano

function peano(x) {
    return (x++ !== x) 
        && (x++ === x);
}

本题的答案是 9007199254740991。

没什么特别的原理，JavaScript 的实数是双精度实数（C++ 的 double 类型），数值达到 9007199254740992 时，保存的精度误差将比 1 大，意味着整数也不再精确。

所以传入上面这个值减一，&& 号左边先计算，把 x 打到临界状态；右边再计算，x 超临界了就无法分辨正负一的误差了。

顺便说一下，本题答案就是 JavaScript 里“能安全保存的整数的最大值”，可以使用 Number.MAX_SAFE_INTEGER 调用出来。

counter

function counter(f) {
    var a = f(), b = f();
    return a() == 1 && a() == 2 && a() == 3
        && b() == 1 && b() == 2;
}

JavaScript 的函数可以返回函数（称作闭包，closure），所以 f() 的返回值得是函数，从而 a() 能正常运行。

题目已经给出本题解法了。给出答案（自行压行）：

function f() {
  let c = 0;
  return () => ++c; // lambda 写法
}

f 返回一个函数，这个函数是个计数器：每次调用后加一并返回调用过的次数。多次调用函数 f 可以产生多个计数器函数，而且每个计数器函数的 c 是独立保存的。这就能通过本题。

关于 c 这种“内部函数访问外部函数的局部变量”的原理可以展开专门写一篇博客了，它有个专门的名字：upvalue。感兴趣的读者可自行查资料。

array

function array(x,y) {
    return Array.isArray(x) && !(x instanceof Array) &&
          !Array.isArray(y) &&  (y instanceof Array);
}

这份代码要求：传入是列表又不是列表的 x 和 y。isinstanceof 运算符其实取的是 prototype，所以可以用 Object.setPrototypeOf 来过这个题。代码如下：

Object.setPrototypeOf([], {}), Object.setPrototypeOf({}, Array.prototype)

很简单：把一个列表的 prototype 设置成其他什么东西，这样列表还是列表，但是 isinstanceof 不认这个列表了；反之也可以把其他东西的 prototype 设置为列表，让 isinstanceof 误判。

isinstance、isinstance2

function instance(x,y) {
  return x instanceof y && y instanceof x && x !== y;
}
function instance2(a,b,c) {
  return a !== b && b !== c && a !== c
      && a instanceof b
      && b instanceof c 
      && c instanceof a;
}

这两题可以用同一个原理解决。这次不搞 prototype，直接把 hasInstance 方法给重载了就行。让这个方法返回 true，就可以做到“到处认祖”。

第一题答案 {[Symbol.hasInstance](){return true}}, {[Symbol.hasInstance](){return true}}；

第二题答案 {[Symbol.hasInstance](){return true}}, {[Symbol.hasInstance](){return true}}, {[Symbol.hasInstance](){return true}}。

就是把同一个值复制三遍。注意这个题用 prototype 原型链覆盖是不行的，原型链不能出现环。

proto1

function proto1(x) {
    return x && !("__proto__" in x);
}

只要是个对象就有一些自带的字段，对于任何值，它的原型保存在 "__proto__" 这个键里。这个函数检测的是 x 有没有原型。可以打开浏览器控制台，随便输一点值然后看它的原型，比如 'a'.__proto__。

所以得造一个没有原型的值。答案是 Object.create(null)。

undef

function undef(x) {
    return !{ undefined: { undefined: 1 } }[typeof x][x];
}

typeof 类似 __proto__，可以用来检查一个值的类型，返回的是个字符串。可自行在控制台测试，比如：typeof 'a' 返回 "string"。

这个函数的逻辑是：首先根据 x 的类型，在最外层取字典的键；然后再根据 x 本身取 内层键的值，最后取反后输出。

如果传入 undefined，那么 typeof x 返回 "undefined"，获得了内层字典 {undefined: 1}；然后再取键值 undefined，得到值 1；接着取反，返回 false。

既然有取反，那么就需要在第二步（在内层字典取键值）中获得假值，才能取反为 true。如果访问一个字典里没有的键，那么返回值就是 undefined，是假值没错。但是别忘了，前面取外层字典的键值的时候，唯一的键值是 "undefined"。绕来绕去，需要找到一个满足如下性质的值：

这个题用纯 JavaScript 似乎是没有解法的，因为纯 JavaScript 中只有 undefined 的 typeof 能够返回 "undefined"。但是这个题在浏览器上运行。

而浏览器有个历史遗留：document.all，用 typeof 会得到 "undefined"，但是它自身并不是 undefined。

怎么想到的？之前看过一本讲浏览器的书，提到了这个。所以见识面很重要。不知道就是不知道，就几乎不可能做出这个题。

答案是 document.all。

symmetric

function symmetric(x,y) {
    return x == y && y != x;
}

上面那幅讲 == 的图看上去很乱，但至少有一点：它是对称的，也就是若 x == y 必然有 y == x。但是这里似乎并非如此。

其实比较的时候，如果两边是对象，将会调用 valueOf() 来取对象的原始值。这也是为什么 [[1]] 在比较中被转化成字符串 "1"，因为它的 valueOf() 只是把数组元素转化为字符串返回。

因此只要写一个特殊的对象，它的 valueOf 有副作用，使得每次比较都返回不同的值，就可以通过本题了。

答案是 {c: 0, valueOf: function() { return ++this.c;}}, 1。

ouroborobj

function ouroborobj(x) {
    return x in x;
}

怎么造出一个键值里包含自身的对象？其实真的很简单……

let x = {};
x[x] = 111;

大功告成。不过这个不方便单行写，所以用 C++ 里也有的逗号语法就是答案了：

(x = {}, x[x] = 111, x)

如果利用 JavaScript 的类型转换的话，答案更简单：

[0]

truth

function truth(x) {
    return x.valueOf() && !x;
}

注意 !x 并不会调用 valueOf，写带副作用的 valueOf 行不通。这里再次请出 document.all 即可。由于历史遗留原因，document.all 取逻辑非后得到的是 true。

答案是 (c = document.all, c.valueOf = () => true, c)

wat

function wat(x) {
    return x('hello') == 'world:)' && !x;
}

其实 document.all 是可以调用的，不过现在一般用 document.getElementById 代替。

本题思路就是制造一个 id 为 'hello' 的 html 元素，然后把它的 valueOf 方法给覆盖掉就好了。最后传入 document.all。

(
  document.all[0].id = 'hello', 
  document.all[0].valueOf = () => 'world:)',
  document.all
)

total

function total(x) {
  return (x < x) && (x == x) && (x > x);
}

现在应该已经学到了：遇到矛盾的条件，直接写一个带副作用的 valueOf 覆盖上去就完事了。

{n: 3, valueOf: function() { this.n--; return this.n % 2;}}

json

const secrets = new Uint32Array(2);
crypto.getRandomValues(secrets);
const [key, value] = secrets;
const vault = {
  [key]: value
};

function json(x, y) {
  Object.defineProperty(vault, x, { value: y });
  const secure = JSON.stringify(Object.freeze(vault));
  let copy;
  try {
    copy = eval(`(${secure})`);
  } catch (e) {
    // Try again...
    copy = JSON.parse(secure);
    return key in copy && copy[key] !== vault[key];
  }
  return void vault;
}

代码还是比较长的，但是认真分析一下很容易读懂。它做了下面这些事：

首先肯定要让 eval 失效，否则没办法进入 JSON.parse。

然后……注意到是可以覆盖 JSON.stringify 和 JSON.parse 的，随便选择一个覆盖了，把逻辑改掉就行了。

答案如下：

(
  JSON.stringify = function(g) {
    let s = '{';
    Object.keys(g).forEach(k => { s += '"' + k + '": 111'; });
    return s + '}';
  },
  window.eval = null,
  1
), 2

把 eval 覆盖成 null 就能保证 eval 必定抛出异常；然后前面 JSON.stringify 时，写个类似的逻辑，但是只序列化键不序列化值，这样后面反序列化之后产生的对象肯定是键相同而值不相同了。

evil1

var eval = window.eval;
function evil1(x) {
    return eval(x+'(x)') && !eval(x)(x);
}

开始出现 eval 了，eval 函数是接受一个字符串，返回把这个字符串当成 JavaScript 代码运行的结果。如果不是字符串，直接返回参数本身（不确定这句话是否正确）。

看到后面有 !eval(x)(x)，说明要传入一个函数。前面的 x+(x) 会把函数体与字符串 '(x)' 连接起来。原本想了很复杂的做法，后来发现用 Lambda 函数就可以很快地解决，答案是：() => false。

这个答案为什么成立？后半部分显然成立，前半部分，传给 eval 的是字符串 () => false(x)——没错，在后面连接 (x) 并不一定能形成函数调用。有可能变成表达式的一部分。所以，前半部分变成了一个 Lambda 函数，而 Lambda 函数算真值。

这算是一种注入。

evil2、evil3

var eval = window.eval;
function evil2(x) {
    return eval('('+x+')(x)') && !eval(x)(x);
}
var eval = window.eval;
function evil3(parameter) {
    return eval('('+parameter+')(parameter)') && 
          !eval(parameter)(parameter);
}

加了个括号，就像 C++ 的宏展开的安全措施一样，没办法在语法上搞文章了。怎么办呢？

事实上，既然传入一个函数，那么就能在函数里干任何事情。前半部分和后半部分的 x 的值可以不一样吗？完全可以。只要在前半部分传入的函数中把 x 的值修改了即可：() => x = () => false。

原本这是一个返回“返回函数的函数”的函数，但是前面的 eval 语句会把 x 修改成一个返回函数的函数。从而能在第二步通过检查。这是个简单的套娃（不过确实不好想到）。

evil3 就只是把变量名改了一下，可以用 evil2 的答案通过，把 x 改成 parameter 就行。设立这个题可能是有别的思路能得到比这更短的答案吧。

infinity

function infinity(x, y) {
    return x === y && 1/x < 1/y 
}

再次迎来小清新题目。函数名其实就暗示了答案。在浮点数里，有正 0 和负 0 的存在……答案是 -0, 0。

random1

function random1(x) {
    return Math.random() in x;
}

仍旧小清新，覆盖 Math.random 即可。答案是 (Math.random = () => 0, [0])。

random2

var rand = Math.random();
function random2(x) {
  return rand in x;
}

这里用到一个叫做 Proxy 的东西。可以简单理解成运算符重载（其实是拦截操作）。in 操作会调用 has，所以写一个永远返回 true 的 has 的 Proxy 就好了。

new Proxy({}, { has: () => true, })

random3

var key = crypto.getRandomValues(new Uint32Array(4));
function random3(x) {
    var d = 0;
    for (var i=0; i<key.length; i++) {
        d |= key[i] ^ x[i];
    }
    return d === 0;
}

这个题的代码先是生成了四个随机整数，然后要求输入的参数和这四个整数完全相同。猜是不好猜到的，Proxy 是不能拦截运算符操作的，所以没法对异或下手。

但是，key.length 这个操作有可乘之机。事实上，访问这种带类型的数组 TypedArray 的时候，length 其实是个从它 prototype 继承下来的 getter 方法（getter 的意思就是：它是个函数，但是不需要写出 () 显式调用）。如果把原型链打破，那么求 length 的时候就会因为找不到 length 而返回 undefined。而 undefined 参与任何大小比较运算都会返回 false。也就是说，打破原型链，程序找不到 length 就会直接跳过中间那个循环，从而把本来就是 0 的 d 给直接拿去比较，然后返回 true。

答案是 (Uint32Array.prototype.__proto__ = null, [])。

random4

var rand = Math.random();
function random4(x) {
    return rand === x;
}

这个题是妥妥的猜随机数答案题。

答案是……猜一下答案？

结语

别急，初赛会考 JavaScript 的。

不过一般是那种 IT 企业的面试的初赛（或者叫初试），不是 CSP 初赛和 NOI 笔试之类的。

搜一下“IT 面试题”去看，也有阅读程序也有完善程序。都有的。