用三段 140 字符以内的代码生成一张 1024×1024 的图片

Kyle McCormick 在 StackExchange 上发起了一个叫做 Tweetable Mathematical Art 的比赛,参赛者需要用三条推这么长的代码来生成一张图片。具体地说,参赛者需要用 C++ 语言编写 RD 、 GR 、 BL 三个函数,每个函数都不能超过 140 个字符。每个函数都会接到 i 和 j 两个整型参数(0 ≤ i, j ≤ 1023),然后需要返回一个 0 到 255 之间的整数,表示位于 (i, j) 的像素点的颜色值。举个例子,如果 RD(0, 0) 和 GR(0, 0) 返回的都是 0 ,但 BL(0, 0) 返回的是 255 ,那么图像的最左上角那个像素就是蓝色。参赛者编写的代码会被插进下面这段程序当中(我做了一些细微的改动),最终会生成一个大小为 1024×1024 的图片。

// NOTE: compile with g++ filename.cpp -std=c++11
 
#include <iostream>
#include <cmath>
#include <cstdlib>
#define DIM 1024
#define DM1 (DIM-1)
#define _sq(x) ((x)*(x)) // square
#define _cb(x) abs((x)*(x)*(x)) // absolute value of cube
#define _cr(x) (unsigned char)(pow((x),1.0/3.0)) // cube root
 
unsigned char GR(int,int);
unsigned char BL(int,int);
 
unsigned char RD(int i,int j){
   // YOUR CODE HERE
}
unsigned char GR(int i,int j){
   // YOUR CODE HERE
}
unsigned char BL(int i,int j){
   // YOUR CODE HERE
}
 
void pixel_write(int,int);
FILE *fp;
int main(){
    fp = fopen("MathPic.ppm","wb");
    fprintf(fp, "P6\n%d %d\n255\n", DIM, DIM);
    for(int j=0;j<DIM;j++)
        for(int i=0;i<DIM;i++)
            pixel_write(i,j);
    fclose(fp);
    return 0;
}
void pixel_write(int i, int j){
    static unsigned char color[3];
    color[0] = RD(i,j)&255;
    color[1] = GR(i,j)&255;
    color[2] = BL(i,j)&255;
    fwrite(color, 1, 3, fp);
}

Read more…

HATETRIS:故意跟你作对的俄罗斯方块游戏

    大家也许想过,如果玩家足够牛 B 的话,俄罗斯方块游戏是不是永远也玩不死呢?不是的。我曾经在这里介绍过,理论上说,俄罗斯方块游戏是不能永无止境地玩下去的,总有一个时候你会死掉。事实上,如果允许电脑不随机出牌,可以有意为难你的话,电脑可以利用一个简单的算法迅速把你整死。倘若电脑真的能故意陷害你,玩俄罗斯方块会是什么样的呢?
    今天,我还真找到了这么一个在线俄罗斯方块游戏 HATETRIS 。在这个游戏中,下一个方块并不是随机给的,游戏将用一套确定性算法精心为你挑选一个对你最不利的方块,让你感受一下想要什么偏没有什么的痛苦。毫不夸张地说,在这个游戏中,即使想消掉一行也是一件很困难的事。
    游戏是用 JavaScript 写的,你可以在下面这个框架中点 start new game 直接开始游戏。游戏没有重力因素(方块不会自动下落),这可以给你充分长的思考时间。技术细节和高分记录请移步这里
    想让俄罗斯方块更变态一些,方法不止一种。如果喜欢这个游戏,欢迎挑战我自己原创的变态俄罗斯方块 PiTetris

Read more…

Happy Pi Day!一起来挑战俄罗斯方块圆周率版

    早上好!今天是 3 月 14 日,一年一度的圆周率日。为了和大家庆祝这个日子,我下载了一个 JavaScript 俄罗斯方块游戏 Js Tetris 的源代码,并且小小地修改了一下。那 7 种四联骨牌已经不复存在了,你将看到圆周率中的数字一个接一个地依次落下。这恐怕有希望成为史上最变态的俄罗斯方块了吧。
    游戏改造完毕后,我自己居然沉迷了好久。把积木换成数字后游戏变得不是一般的困难,有很多小技巧有待大家慢慢去摸索。我个人的最好成绩是第 32 位。你呢?

    Update: 如果上下左右按钮会带动浏览器的滚动条,可以用 W 、 S 、 A 、 D 代替。如果浏览器不支持框架,也可以直接打开 http://www.matrix67.com/PiTetris/tetris.html 进行游戏。


 

记09年北大ACM校内赛

    大学生活混起来很快,不知不觉又是一年过去了。去年5月10日的ACM校内赛给我留下了许多美好的回忆,因此今年我主动去报了名(上次是被人给拖去的)。今年有点装怪,题目数量不变,但时间缩短为4个小时。原计划是从8:00做到12:00,结果可能是因为我们所在的7号机房迟迟没有开门,时间临时改成了8:15到12:15。总的来说,今年的题目比去年要糟糕得多,但也不乏一些精彩的题目。

    和去年一样,第一题依旧是所有题目中最科学的一道。题目给定一个不超过2000*2000的网格,你在最左下角的位置(即(0,0)点),你的目的地在(x,y)。要求你的路线不得经过同一个交叉点两次,且不允许左转(题目背景让这个条件顺理成章:街道靠右行,左转不方便),问合法的路线共有多少种。题目难点就是你不一定要走最近的路,完全允许你绕上一大圈;这破坏了有序性,很难构造出递推公式或动态规划模型。稍微画一下图,我们发现了一些显然但很有启发性的规律:每一次右转后,你左手边方向的所有区域都不能再走了,这很可能产生出规模更小的子问题来。另外,所有合法路线必然是有如螺旋线一样的一圈一圈绕着终点走,这种隐藏的有序性也为动态规划提供了可能。但顺着这个思路想下去屡屡碰壁,我猜不少队伍都卡在这儿了吧。

 

    后来我完全打翻前面的全部思路,猛然想到了一个具有决定意义的想法:街道的选取唯一地决定了整个路线。例如,假设我想计算转弯恰好11次的路线有多少条。这样的路线一定含有三条向上走的路、三条向右走的路、三条向下走的路和三条向左走的路。除去第一条路和最后一条路的位置都是确定的,其它的路选在哪一行或者哪一列唯一地决定了整个路线。因此,我们可以用排列组合直接计算出答案来。向上走的路是五选二,向右走的路是七选三,向下走的路是四选三,向左走的路是三选二。把它们各自的选取方案数乘起来就得到了拐弯11次的合法路径。于是,计算所有的路线数只需要从小到大枚举拐弯的次数,每一次计算都是常数的,总复杂度是O(n)的;整个算法的瓶颈反倒是O(n^2)的组合数预处理,不过这个复杂度完全可以承受。

Read more…

Harvard-MIT Mathematics Tournament 2009: Guts Round

摘录几道题目。

计算1·2^2 + 2·3^2 + 3·4^2 + … + 19·20^2
原式 = (1^3 + 2^3 + … + 20^3) – (1^2 + 2^2 + … + 20^2) = 44100 – 2870 = 41230

求2^x = 3^y – 1的所有正整数解
x=1时(1,1)是一个解;当x>1时,方程模4后左边永远等于0,右边则是(-1)^y – 1,可知y为偶数。令y=2z,那么有2^x = (3^z – 1)(3^z + 1),这就要求3^z-1和3^z+1都是2的幂;但它们只相差2,因此它们只有可能是2和4,于是z=1,即原方程的另一个解为(3,2)。

圆周上有2008个点。选择两个点连成一条线,再选另外两点连一条线,这两条线段相交的概率为多少?
给定四个点,在三种连接方案中恰有一种会发生相交。取遍所有C(2008,4)种组合,相交的总情况数总是占了1/3,因此所求的概率就是1/3。

Read more…