ᕦʕ •ᴥ•ʔᕤ

CCBC16 总结

简介

已经大半年都没参加 PH, 但是 CCBC 不能不参加. 今年的题目真是一言难尽, 一度以为没法完赛, 后来出题组调整了提示币的速度, 每道题都可以开提示做, 最终又是提前一天但 177 名完赛.

image

最近用 obsidian 比较多, 特别是新版的 Base 功能. 所以也把之前的博客迁移了过来, 花了一些时间改善之前的格式, 效果更好了, 而且在 obsidian 中更容易读写了, 要暂时告别 Emacs 了. 希望接下来有时间把之前做过的 hunt 也都整理过来.

这次的比赛印象最深的就是 代入演算 这道题了, 函数式编程、λ-演算都是我非常感兴趣的东西, 所以这回就讲下这一道题.

代入演算

例

将下两行代入甲、乙：「甲；「甲；乙」」；  
将下两行代入甲、乙：「甲；「甲；乙」」；  
将本段演算中用于提取的数字加一；  
得到数字：0  
↓  
「将下两行代入甲、乙：「甲；「甲；乙」」；「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」」；  
得到数字：0  
↓  
将下两行代入甲、乙：「甲；「甲；乙」」；  
「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；  
得到数字：0  
↓  
「「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；「「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；得到数字：0」」  
↓  
「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；  
「「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；得到数字：0」  
↓  
将下两行代入甲、乙：「甲；「甲；乙」」；  
将本段演算中用于提取的数字加一；  
「「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；得到数字：0」  
↓  
「将本段演算中用于提取的数字加一；「将本段演算中用于提取的数字加一；「「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；得到数字：0」」」  
↓  
将本段演算中用于提取的数字加一；  
「将本段演算中用于提取的数字加一；「「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；得到数字：0」」  
↓  
「将本段演算中用于提取的数字加一；「「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；得到数字：1」」  
↓  
将本段演算中用于提取的数字加一；  
「「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；得到数字：1」  
↓  
「「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；得到数字：2」  
↓  
「将下两行代入甲、乙：「甲；「甲；乙」」；将本段演算中用于提取的数字加一」；  
得到数字：2  
↓  
将下两行代入甲、乙：「甲；「甲；乙」」；  
将本段演算中用于提取的数字加一；  
得到数字：2  
↓  
「将本段演算中用于提取的数字加一；「将本段演算中用于提取的数字加一；得到数字：2」」；  
↓  
将本段演算中用于提取的数字加一；  
「将本段演算中用于提取的数字加一；得到数字：2」  
↓  
「将本段演算中用于提取的数字加一；得到数字：3」  
↓  
将本段演算中用于提取的数字加一；  
得到数字：3  
↓  
得到数字：4

将下两行代入甲、乙：「甲；「甲；「甲；乙」」」；
将下两行代入甲、乙：「甲；「甲；乙」」；
将下两行代入甲、乙：「甲；「甲；「甲；乙」」」；
将本段演算中用于提取的数字加一；
根据字母表顺序每两位提取：-4656

将下一行代入甲：「甲；甲；甲；「甲；甲；甲；甲」；甲；甲」；
将下三行代入甲、乙、丙：「甲；「乙；丙」」；
将下两行代入甲、乙：「甲；「甲；「甲；「甲；「甲；「甲；乙」」」」」」；
将下两行代入甲、乙：「甲；「甲；乙」」；
将下两行代入甲、乙：「甲；「甲；「甲；乙」」」；
将下两行代入甲、乙：「甲；「甲；「甲；「甲；「甲；「甲；「甲；「甲；「甲；「甲；「甲；乙」」」」」」」」」」」；
将本段演算中用于提取的数字加一；
根据字母表顺序每两位提取：12

将下四行代入甲、乙、丙、丁：「甲；丙；「乙；丙；丁」」；
「将下两行代入甲、乙：「甲；「甲；「甲；「甲；「甲；「甲；乙」」」」」」；将下两行代入甲、乙：「甲；「甲；乙」」」；
「将下两行代入甲、乙：「甲；「甲；乙」」；将下两行代入甲、乙：「甲；「甲；「甲；乙」」」」； 将下三行代入甲、乙、丙：「乙；「甲；乙；丙」」；
「将下两行代入甲、乙：「甲；「甲；「甲；乙」」」；将下两行代入甲、乙：「甲；「甲；「甲；「甲；「甲；乙」」」」」」；
将本段演算中用于提取的数字加一；
根据字母表顺序每两位提取：5

「将下两行代入甲、乙：「甲；「甲；「甲；「甲；「甲；「甲；乙」」」」」」；将下两行代入甲、乙：「甲；「甲；「甲；乙」」」」；
将下三行代入甲、乙、丙：「甲；将下两行代入丁、戊：「戊；「丁；乙」」；将下一行代入丁：「丙」；将下一行代入丁：「丁」」；
「将下两行代入甲、乙：「甲；「甲；「甲；「甲；「甲；「甲；「甲；「甲；「甲；「甲；「甲；乙」」」」」」」」」」」；将下两行代入甲、乙：「甲；「甲；乙」」」；
将本段演算中用于提取的数字加一；
根据字母表顺序每两位提取：2

将下三行代入甲、乙、丙：「甲；「乙；丙」」；
将下三行代入甲、乙、丙：「甲；将下四行代入丁、戊、己、庚：「戊；「丁；己；庚；戊」」；将下三行代入丁、戊、己：「丙」；乙；将下一行代入丁：「丁」；将下一行代入丁：「丁」」；
将下两行代入甲、乙：「甲；「甲；「甲；乙」」」；
「将下三行代入甲、乙、丙：「甲；「乙；丙」」；将下两行代入甲、乙：「甲；「甲；乙」」；将下两行代入甲、乙：「甲；「甲；「甲；「甲；「甲；「甲；「甲；乙」」」」」」」」；
将本段演算中用于提取的数字加一；
根据字母表顺序每两位提取：4

将下三行代入甲、乙、丙：「甲；「乙；丙」」；
将下三行代入甲、乙、丙：「甲；「乙；丙」」；
将下一行代入甲：「甲；「将下两行代入乙、丙：「将下三行代入丁、戊、己：「丁；「戊；己」」；丙；「乙；「将下三行代入丁、戊、己：「戊；「丁；戊；己」」；丙」」」」；将下两行代入乙、丙：「丙」；将下一行代入乙：「乙」」；
将下两行代入甲、乙：「甲；「甲；「甲；「甲；「甲；「甲；乙」」」」」」；
将下两行代入甲、乙：「甲；「甲；「甲；乙」」」；
将本段演算中用于提取的数字加一；
根据字母表顺序每两位提取：-155

解析

看完题目后马上打开了我的 scheme, 想着这不是翻译一下直接就运行出答案了吗. 比如例题可以这样写:

((lambda (a b) (a (a b)))
 (lambda (a b) (a (a b)))
 (lambda (x) (+ x 1))
 0)

结果运行后程序报错, 当时感觉没有时间调试错误, 就换别的方法去解题了. 完赛后发现, 原来是忽略了柯里化, 导致参数对不上. 其实应该这样写:

((((lambda (a) (lambda (b) (a (a b))))
   (lambda (a) (lambda (b) (a (a b)))))
  (lambda (x) (+ x 1)))
 0)

成功地返回了 4, 本来写 scheme 的本意是可以直接把原题的括号照搬下来, 但是现在这样写并不能很好地匹配, 为了柯里化要多加好多括号, 所以为了下面的题目写的方便, 先定义几个辅助的宏.

; 每段话倒数第二行的加一操作
(define (inc x) (+ 1 x))

; 直接生成丘奇数, 而不需要写一堆括号和甲, 避免出错
(define-macro (make-number n)
  (define (build-nested-expr count)
    (if (= count 0)
        'b
        `(a ,(build-nested-expr (- count 1)))))
  `(lambda (a) (lambda (b) ,(build-nested-expr n))))

; 把一个函数变成柯里化的函数, 写出来的代码更像题目给的样子
(define-macro (curry-lambda params . body)
  (if (null? params)
      `(begin ,@body)
      (let ((param (car params))
            (rest-params (cdr params)))
        `(lambda (,param)
           ,(if (null? rest-params)
                `(begin ,@body)
                `(curry-lambda ,rest-params ,@body))))))

; 最后把 (f1 f2 f3 f4 f5) 转成 ((((f1 f2) f3) f4) f5) 这样每次只拿一个参数的调用
(define-macro (chain . args)
  (define (process-arg arg)
    (if (and (list? arg)
             (not (eq? (car arg) 'lambda))
             (not (memq (car arg) '(quote if define let let* letrec cond case)))
             (not (and (symbol? (car arg)) 
                       (memq (car arg) '(chain make-number curry-lambda)))))
        `(chain ,@arg)
        arg))
  (if (null? args)
      (error "chain requires at least one argument")
      (let ((first (process-arg (car args)))
            (rest (cdr args)))
        (if (null? rest)
            first
            (let loop ((expr (list first (process-arg (car rest))))
                       (rest (cdr rest)))
                 (if (null? rest)
                     expr
                     (loop (list expr (process-arg (car rest)))
                           (cdr rest))))))))

这样每道题就很好写了:

; Liii Scheme by LiiiLabs
; 第一题 1905
(let ((f1 (make-number 3))
      (f2 (make-number 2))
      (f3 (make-number 3))
      (f4 inc)
      (f5 -4656))
  (chain f1 f2 f3 f4 f5))

; 第二题 2124
(let ((f1 (lambda (a) (chain a a a (a a a a) a a)))
      (f2 (curry-lambda (a b c) (a (b c))))
      (f3 (make-number 6))
      (f4 (make-number 2))
      (f5 (make-number 3))
      (f6 (make-number 11))
      (f7 inc)
      (f8 12))
  (chain f1 f2 f3 f4 f5 f6 f7 f8))

; 第三题 203
(let ((f1 (curry-lambda (a b c d) (chain a c (b c d))))
      (f2 ((make-number 6) (make-number 2)))
      (f3 ((make-number 2) (make-number 3)))
      (f4 (curry-lambda (a b c) (chain b (a b c))))
      (f5 ((make-number 3) (make-number 5)))
      (f6 inc)
      (f7 5))
  (chain f1 f2 f3 f4 f5 f6 f7))

; 第四题 1321
(let ((f1 (chain (make-number 6) (make-number 3)))
      (f2 (curry-lambda (a b c)
                        (chain a
                               (curry-lambda (d e) (e (d b)))
                               (lambda (d) c)
                               (lambda (d) d))))
      (f3 ((make-number 11) (make-number 2)))
      (f4 inc)
      (f5 2))
  (chain f1 f2 f3 f4 f5))

; 第五题 919
(let ((f1 (curry-lambda (a b c) (a (b c))))
      (f2 (curry-lambda (a b c)
                        (chain a
                               (curry-lambda (d e f g)
                                             (chain e (d f g e)))
                               (curry-lambda (d e f) c)
                               b
                               (lambda (d) d)
                               (lambda (d) d))))
      (f3 (make-number 3))
      (f4 (chain (curry-lambda (a b c) (a (b c)))
                 (make-number 2)
                 (make-number 7)))
      (f5 inc)
      (f6 4))
  (chain f1 f2 f3 f4 f5 f6))

; 第六题 2005
(let ((f1 (curry-lambda (a b c) (a (b c))))
      (f2 (curry-lambda (a b c) (a (b c))))
      (f3 (lambda (a) (chain a
                             (curry-lambda (b c)
                                           (chain (curry-lambda
                                                   (d e f) (d (e f)))
                                                  c
                                                  (b ((curry-lambda
                                                       (d e f) 
                                                       (chain e (d e f)))
                                                      c))))
                             (curry-lambda (b c) c)
                             (lambda (b) b))))
      (f4 (make-number 6))
      (f5 (make-number 3))
      (f6 inc)
      (f7 -155))
  (chain f1 f2 f3 f4 f5 f6 f7))

最后再附上 python 版本的, 可以对比下两者的区别.

# 第一题
f1 = lambda a: lambda b: a(a(a(b)))
f2 = lambda a: lambda b: a(a(b))
f3 = lambda a: lambda b: a(a(a(b)))
f4 = lambda x: x + 1
f5 = -4656
print(f1(f2)(f3)(f4)(f5))

# 第二题
f1 = lambda a: a(a)(a)(a(a)(a)(a))(a)(a)
f2 = lambda a: lambda b: lambda c: a(b(c))
f3 = lambda a: lambda b: a(a(a(a(a(a(b))))))
f4 = lambda a: lambda b: a(a(b))
f5 = lambda a: lambda b: a(a(a(b)))
f6 = lambda a: lambda b: a(a(a(a(a(a(a(a(a(a(a(b)))))))))))
f7 = lambda x: x + 1
f8 = 12
print(f1(f2)(f3)(f4)(f5)(f6)(f7)(f8))

# 第三题
f1 = lambda a: lambda b: lambda c: lambda d: a(c)(b(c)(d))
f2_1 = lambda a: lambda b: a(a(a(a(a(a(b))))))
f2_2 = lambda a: lambda b: a(a(b))
f2 = f2_1(f2_2)
f3_1 = lambda a: lambda b: a(a(b))
f3_2 = lambda a: lambda b: a(a(a(b)))
f3 = f3_1(f3_2)
f4 = lambda a: lambda b: lambda c: b(a(b)(c))
f5_1 = lambda a: lambda b: a(a(a(b)))
f5_2 = lambda a: lambda b: a(a(a(a(a(b)))))
f5 = f5_1(f5_2)
f6 = lambda x: x + 1
f7 = 5
print(f1(f2)(f3)(f4)(f5)(f6)(f7))

# 第四题
import sys
sys.setrecursionlimit(10000)
f1_1 = lambda a: lambda b: a(a(a(a(a(a(b))))))
f1_2 = lambda a: lambda b: a(a(a(b)))
f1 = f1_1(f1_2)
f2 = lambda a: lambda b: lambda c: a(lambda d: lambda e: e(d(b)))(lambda d: c)(lambda d: d)
f3_1 = lambda a: lambda b: a(a(a(a(a(a(a(a(a(a(a(b)))))))))))
f3_2 = lambda a: lambda b: a(a(b))
f3 = f3_1(f3_2)
f4 = lambda x: x + 1
f5 = 2
print(f1(f2)(f3)(f4)(f5))

# 第五题
import sys
sys.setrecursionlimit(10000)
f1 = lambda a: lambda b: lambda c: a(b(c))
f2 = lambda a: lambda b: lambda c: a(lambda d: lambda e: lambda f: lambda g: e(d(f)(g)(e)))(lambda d: lambda e: lambda f: c)(b)(lambda d: d)(lambda d: d)
f3 = lambda a: lambda b: a(a(a(b)))
f4_1 = lambda a: lambda b: lambda c: a(b(c))
f4_2 = lambda a: lambda b: a(a(b))
f4_3 = lambda a: lambda b: a(a(a(a(a(a(a(b)))))))
f4 = f4_1(f4_2)(f4_3)
f5 = lambda x: x + 1
f6 = 4
print(f1(f2)(f3)(f4)(f5)(f6))

# 第六题
f1 = lambda a: lambda b: lambda c: a(b(c))
f2 = lambda a: lambda b: lambda c: a(b(c))
f3 = lambda a: a((lambda b: lambda c: (lambda d: lambda e: lambda f: d(e(f)))(c)(b(((lambdad: lambda e: lambda f: e((d(e)(f))))(c))))))(lambda b: lambda c: c)(lambda b: b)
f4 = lambda a: lambda b: a(a(a(a(a(a(b))))))
f5 = lambda a: lambda b: a(a(a(b)))
f6 = lambda x: x + 1
f7 = -155
print(f1(f2)(f3)(f4)(f5)(f6)(f7))