六月 30th, 2010 () Puzzle › ben1222 › No Comments
Lightbot 2.0
继续推荐个小游戏…Lightbot的第二作…
给小机器人设置指令然后让它点亮所有蓝色方块…
乍看之下没什么难度…但是小机器人最多只能放32个指令…这难度就来了…
第一作的时候指令比较少…前进,左转,右转,跳,亮灯,调用函数1,调用函数2…
这一作增加了两种指令…退出当前函数,颜色
可以给每个指令上色,无色或紫或蓝或橙(啊咧…八云紫,八云蓝,橙…?)
如果某个指令不是无色的话,只有当机器人颜色与这个指令颜色相同时才会执行这条指令…
要机器人变色需要站在特殊的色块上亮灯,然后颜色才会变成这个色块上的颜色,如果已经是对应的颜色了,就变回无色…
这个像是if的东西看似不错…但是实际上…非常恶心…
要知道虽然指令种类增加了…可是内存居然还是32个指令的空间…
expert级别的那几关难度真够大…
没记错的话expert的第一关貌似是第一作的最后一关?
最后两关真是绞尽脑汁…
虽然貌似有walkthrough…但…似乎被档在墙外了…
结果就是…最后一关想了好几个小时并且睡了一觉才勉强做出来…
挑战一下吧…
话说睡前和刚睡醒的时候貌似非常容易想出问题的解决方案呢…
最后两关我的解法:(解法应该有很多种…)
Lightbot2 Expert level 5
Lightbot2 Expert level 6
六月 28th, 2010 () Puzzle › ben1222 › No Comments
Doodle God
游戏规则很简单…将两种东西合成…然后会产生新的东西…
最初只有土水火气四种东西…
有些合成虽然不会有新东西产生…但是很有趣…
诸如
石+石=火+石+石…这就是打火石吗…
人+龙=灰+龙…被龙干掉了啊…
战士+龙=英雄+血…把龙干掉了啊…
个人挺喜欢这种类型的小游戏…不同的组合会产生不同的结果…
让人想起了GROW系列的游戏:
GROW1
GROW2
GROW3
GROW RPG
GROW CUBE
GROW TOWER
六月 16th, 2010 () Project Euler › ben1222 › 2 Comments
Project Euler 第294题
Sum of digits – experience #23
d(k)是k的各位和,S(n)表示k<10^n中有多少个k满足:k能被23整除并且d(k)=23
求S(11^12),对10^9取余
下面是我的解题过程:
六月 14th, 2010 () Project Euler › ben1222 › No Comments
Project Euler 第293题
Pseudo-Fortunate Numbers
N是满足这些条件的数:是正偶数,是2的幂或所有质因子是连续的质数
N的伪幸运数是最小的大于1的整数M使得M+N是质数
求 N<10^9的所有不同的伪幸运数的和
下面是我的解题过程:
六月 9th, 2010 () 心血来潮 › ben1222 › No Comments
唔嗯…标题是不是该叫
Range encoding 区间编码
呢…
算术编码经常听到…和huffman编码同样是熵编码
要压缩什么信息的话,熵编码一般来说是最后的杀手锏了…
因为熵编码后得到的信息流的冗余度已经逼近了0…几乎每一位都已经携带了它所能携带的最大信息量了:每个符号出现的概率(次数)几乎相同…
就这个信息流而言,如果当作灰度图像,你将看到雪花屏…
这也就是为什么像rar之类的压缩软件压缩后的文件如果还想压缩一次的话反而会变大…
因此想要获得更高的压缩比的话…在熵压缩之前极尽一切可能利用原信息中数据的内在联系来压缩冗余信息吧…
对每个符号之间没有任何相关性的情况下…可能我们就只剩熵压缩了…
不过现实中大部分信息的各个符号间还是有很强的相关性的…
说一下信息量…一定会出现的事件不携带信息…出现概率越小的事件携带的信息量越大
比如掷硬币…一般情况下每次掷硬币的结果只携带1bit的信息…因为出现正面反面的概率相同…
但是如果真的用1bit来记录每次掷硬币的结果的话…比如0表示正面朝上,1表示反面朝上…
就会有个问题:如果结果是硬币立起来了…用什么符号记录呢?…
假设有2^-30的概率硬币立起来了…
这样的话…一次硬币立起来就携带了30bits的信息量…一次正面或一次反面则携带了略微小于1bit的信息量…
至于用什么方法记录…转义符是个不错的选择…
比如咱用30个0后面跟一个1来表示硬币立起来了,用30个0后面跟一个0表示确确实实刚才抛出了连续30次正面
回到算术编码上来…
先和huffman编码比较一下吧…算术压缩的优势在哪里呢…
能用小于1bit的长度来存那些信息量小于1bit的信息
huffman编码就是这里弱了…对于信息量小于1位的信息,huffman 编码方式最小也要消耗1位来表示
结果如果要用huffman编码来编上面的投掷硬币结果的信息的话…就会变成用0表示正面,10表示反面,11表示硬币立起来了…
这样平均下来…要用1.5bits来记录1次投掷…不合算啊…
算术编码的话平均下来可以以接近1bit来记录1次投掷…
一些基本原理的话很多地方都有…
比如维基百科
这篇文章也不错
上图像通信课的时候老师说过…算术编码虽然有优势…但因为有专利的原因…当时并没得到广泛应用
倒是都用huffman编码来实现熵编码…毕竟普通情况下huffman编码也不必算术编码差多少…
至于现在…不知道还有什么限制没…
在看了上面的维基百科之后,发现了这个区间编码
和算术编码用长小数表示信息的方法不同,这用的是大整数表示…
看了一下感觉实际上和算术编码的本质是一样的…只不过小数被避免了…
而且感觉更合我口味…
然后说说我心血来潮想要把这算法实现出来…(终于进入正题?了)
虽然很早就对此有所耳闻…原理也很易懂…但是一直没有动手写过…
先撇开高阶的和带转义码的编码方法不谈…光是0阶,256符号(1字节)初始概率1/256的自适应方式就让人碰壁了…
当然…我用的方法更像区间编码而不是算术编码…因为我用整数区间而不是小数区间…
我目前还没深入理解过浮点数…发明浮点数的人真伟大…
每压缩一个字节,该字节表示的符号的频次就加一,随着数据量的增加,这个频次就越来越接近其出现的真实概率,这就是普通的自适应…
计算某个字符b对应的新区间大小就是frequency[b]*range/count
新区间下界是sum{frequency[i],i=0..b-1}*range/count+low
这里count是之前处理过的字节数加上初始的256,low是当前区间的下界
这里为止都是很容易想到的…
至于怎么以有限搞定无限精度…
最初的想法是计算到新区间之后,看看这个新区间的上界和下界的最高位是否相同,相同则输出该位,然后区间变大一倍(最高位丢弃,其余左移,上界加1),继续判最高位是否相同,直到不相同就停止输出…
最后当前区间就设为这个新区间,然后读入下一个字节继续压缩…
然后问题出现了…数据量大了之后就会出现压缩错误的情况(解压后的数据在后半段全乱了,只有前面一部分才是正确的)
原因是当新区间大小很小,但是却正好在1000..00B(MAX/2)上下的时候…无法通过输出位来扩大区间大小,因为最高位不相同,但是压缩下一个字节的时候因为当前区间太小,导致这回的新区间大小为0了…
自己想了几种方案…但还是解决不了…
后来找到了这份代码
仔细读了之后才恍然大悟…原来还能这样做…
因为当新区间正好在1000..00B(MAX/2)上下的时候,上界的前缀一定是1后面跟很多0,而下界的前缀一定是0后面跟很多1…
所以可以先记录下待输出多少位(在上面的代码里叫bits_outstanding),然后扩展区间大小(下界减去MAX/4,区间大小加倍)…直到区间大小超过MAX/4为止
当然如果遇到上下界的最高位相同的时候,终于可以输出了
但是别着急,还有 bits_outstanding个位没有输出呢,如果当前这个最高位是1,那么就输出一个1然后bits_outstanding-1个0,然后再输出当前这个最高位1
否则则是一个0,bits_outstanding-1个1,然后0
因为:
好了…到这里压缩的主要部分就搞定了…留下接口,让代码细节从眼中消失吧…
现在无论符号数有多少个,都可以随心所欲的压缩了…
因为输入一个新区间,就能输出正确的压缩后比特流,同时更新当前区间
至于输入一个符号你用什么方式转换成什么样的区间,多少个区间,采用几阶模型,用不用转义符,都是上面一层的事情…
六月 7th, 2010 () Project Euler, 图片 › ben1222 › No Comments
Project Euler 第292题
Pythagorean Polygons
毕达哥拉斯多边形定义为:
凸多边形,至少3个顶点,没有3个顶点在一条线上,每个顶点坐标都是整数,每条边长都是整数
P(n)表示周长是<=n的毕达哥拉斯多边形的个数
平移的算同一个,旋转镜像缩放什么的不算同一个
求P(120)
下面是我的解题过程:
RSS订阅