用三段 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…

神秘常量复出!用0x077CB531计算末尾0的个数

    大家或许还记得 Quake III 里面的一段有如天书般的代码,其中用到的神秘常量 0x5F3759DF 究竟是怎么一回事,着实让不少人伤透了脑筋。今天,我见到了一段同样诡异的代码。
    下面这个位运算小技巧可以迅速给出一个数的二进制表达中末尾有多少个 0 。比如, 123 456 的二进制表达是 1 11100010 01000000 ,因此这个程序给出的结果就是 6 。

unsigned int v;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

    熟悉位运算的朋友们可以认出, v & -v 的作用就是取出右起连续的 0 以及首次出现的 1 。当 v = 123 456 时, v & -v 就等于 64 ,即二进制的 1000000 。怪就怪在,这个 0x077CB531 是怎么回事?数组 MultiplyDeBruijnBitPosition 又是什么玩意儿呢?

Read more…

TLE比赛结束 经典题目回顾

    创意C/C++编程挑战赛Time Limit Exceeded结束,题目果然非常有创意。大家可以在这里看到比赛题目和获胜选手的代码。其中两道题很有意思,我特别喜欢。

    一道叫做Compile Error的题目要求你写一个叫做multiply的类,里面包含一个mult(int a,int b)的函数,该函数用于打印出a和b的乘积。代码中不允许出现空格、“/”和“#define”。

    第一个问题就是,定义一个类的语句是class multiply{…},这个空格要怎么避免?只要你知道typedef int foo也可以写成int typedef foo,我们就可以利用typedef来消除空格,把类的定义写成class{…}typedef multiply。但这下后面又冒出一个空格来,这个空格怎么消呢?一个巧妙的方法就是利用int typedef foo,bar的语句,把类定义语句写成class{…}typedef*foo,multiply,其中*foo是一个不会用到的类型,但是它帮助我们奇迹般地消除了一个空格。巧妙利用星号可以消除很多空格,例如我们在定义mult函数时就可以写成void*mult(…){…}。最后一个难题就是,定义函数mult(int a,int b),参数表里面的两个空格怎么办?其实办法依然很多。不少网友都用到了typeof,这样便可以把int a写成typeof(int)a了。完整的类定义如下:

class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;

    在gcc下,即使警告全开,下面这个程序编译时也一声不吱。

#include <iostream>
using namespace std;
 
class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;
 
int main()
{
    multiply foo;
    foo.mult(23,67);
}

Read more…

比比谁的代码短:TLE测试赛结束

    上次提到,我非常关注一个即将举办的另类编程挑战赛Time Limit Exceeded,这个比赛的得分算法很另类,它将根据你代码的总长度和特定字符的多少而定。在刚刚结束的测试赛中,有几个题目非常具有挑战性,参赛者提交的代码也是牛气冲天。

 
Power of 2
问题:
    输入数据含有多行,每行一个正整数。对每个数,检查看它是否是2的幂,是则输出yes,不是则输出no。
    你的程序不允许使用分号。
    规定0也是2的幂。

得分:
    S= length of code + number of whitespaces;
    score = (250000)/(S^2);

Read more…