Apple introduced a new HTML tag <canvas> to the world, which endue client-side script language the ability of graphics drawing. Now, Firefox and Opera has implement the <canvas> tag, so the javascript programmer was able to write a rich graphic-based client application.
I've written a simple ball game to show the interactive between javascript graphic app and browser user.
See details : http://ray58750034.googlepages.com/javascriptballgame
See more examples : http://developer.mozilla.org/en/docs/Category:Canvas_examples
Friday, February 23, 2007
Wednesday, February 21, 2007
Topcoder SRM340 DIV II
首先叹一下只能沦落在Div2和Div1的边缘。颇为伤感，以后想做Component了。
多么戏剧性的一场比赛啊，第一题还是很稳健的敲掉了，毕竟DIV２第一题太没搞头了。第二题其实也很简单，但比赛的时候，人就容易犯糊涂。 我把第二题先想成dfs，写完后发觉超时，郁闷。然后越想越复杂，想到了DP，DP的路就越走越远拉。最后是235.85收场。
第二题，其实枚举和贪心就行，巨汗呐。不过在Challenge阶段，表现神勇啊！一路从１８冲进前１０。主要是靠事前准备的对付第二题dfs的数据，哈哈，果然有用dfs还不知情的，连掐３个 ，HOHO。当时排名第10, score 385.85。
最后的System Test是关键！第三题全军覆没，房间里没人过。第二题就第一个人过了。然后，因为我掐了三个人，所以我的总积分排第二！巨汗啊，居然排到了No2，不枉我通宵比赛，呵呵。总结一下，第二题我其实TEST数据早过了，但由于我确定我的程序不完美，所以我一直不交。看来战术是正确的！如果交了被掐掉，那就很尴尬了。
按规则，这场比赛有奖金可以拿，多少无所谓，只要确实有拿就好。拿到钱得请梁大吃饭！梁大应该是说比我做的好，但是最后也是只有一题过了，再加上没掐，所以分数比我差。当然他们房间的整体实力可能还比我这强一点。
多么戏剧性的一场比赛啊，第一题还是很稳健的敲掉了，毕竟DIV２第一题太没搞头了。第二题其实也很简单，但比赛的时候，人就容易犯糊涂。 我把第二题先想成dfs，写完后发觉超时，郁闷。然后越想越复杂，想到了DP，DP的路就越走越远拉。最后是235.85收场。
第二题，其实枚举和贪心就行，巨汗呐。不过在Challenge阶段，表现神勇啊！一路从１８冲进前１０。主要是靠事前准备的对付第二题dfs的数据，哈哈，果然有用dfs还不知情的，连掐３个 ，HOHO。当时排名第10, score 385.85。
最后的System Test是关键！第三题全军覆没，房间里没人过。第二题就第一个人过了。然后，因为我掐了三个人，所以我的总积分排第二！巨汗啊，居然排到了No2，不枉我通宵比赛，呵呵。总结一下，第二题我其实TEST数据早过了，但由于我确定我的程序不完美，所以我一直不交。看来战术是正确的！如果交了被掐掉，那就很尴尬了。
按规则，这场比赛有奖金可以拿，多少无所谓，只要确实有拿就好。拿到钱得请梁大吃饭！梁大应该是说比我做的好，但是最后也是只有一题过了，再加上没掐，所以分数比我差。当然他们房间的整体实力可能还比我这强一点。
Saturday, February 17, 2007
HSB Color Space
java.awt.Color类有根据HSB色彩空间创建Color的静态方法，今天去查了查。了解了HSB是怎么一个色彩空间，它和RGB又有什么区别，分享一下。
下图的圆锥描述的就是HSB如何表示色彩，相当华丽吧：
Hue:描述色彩，其值为 [0,360) ，是圆锥顶部的圆，其0和360均为红色。另外60为黄、120为绿、180为青、240为兰、300为紫。颜色如彩虹~呵呵。
Saturation:描述饱和度，其值为[0,1]之间的小数，图中是圆锥的轴到圆锥的边缘。取0则是纯白，无论Hue取多少。
Brightness:描述明亮度，其值为[0,1]之间的小数，图中可以说是圆锥的高度，自底向上逐渐明亮。当取0时，色彩为纯黑，无论Hue和Saturation取何值。
参考：
http://www.tomjewett.com/colors/
下图的圆锥描述的就是HSB如何表示色彩，相当华丽吧：
Hue:描述色彩，其值为 [0,360) ，是圆锥顶部的圆，其0和360均为红色。另外60为黄、120为绿、180为青、240为兰、300为紫。颜色如彩虹~呵呵。
Saturation:描述饱和度，其值为[0,1]之间的小数，图中是圆锥的轴到圆锥的边缘。取0则是纯白，无论Hue取多少。
Brightness:描述明亮度，其值为[0,1]之间的小数，图中可以说是圆锥的高度，自底向上逐渐明亮。当取0时，色彩为纯黑，无论Hue和Saturation取何值。
参考：
http://www.tomjewett.com/colors/
Friday, February 16, 2007
Javascript Menu 代码
只为了显现一个简单的menu，网上搜了不少代码。 但要么就是太复杂，搞得我改都无从改，要么就是不符合我的需求。结果自己静下心 20分钟就搞定了， -_-b ，找了大概2小时啊，汗呐。
非常简单的要求：
以下是我的代码：
非常简单的要求：
- 必须是js代码，因为我要实现menu在很多页面里都要用，如果掺了html就要用iframe之类的，iframe毕竟不舒服啊。
- 对界面没什么要求，简单的ul和li就行了，css沿用站点的，无须另外配。
- 多级目录结构
- 每层menu可以是链接，也可以是打开子目录
- 可复用，其实就是实现类似jsp的<%@include file="">的作用，只是我没有服务器，所以只好用js啦。
以下是我的代码：
<div id="soya_menus">
</div>
<script language="JavaScript">
var MENU_ITEMS = [
['Ray',{ href : 'http://raythking.blogspot.com/',target : "_blank" }],
['Google',null,[
['Web',{ href : 'http://www.google.com',target : "_blank"}],
['Image',{ href : 'http://images.google.com',target : "_blank"}],
['Video',{ href : 'http://video.google.com',target : "_blank"}]
]
],
['Baidu', null,[
['Index',{ href : 'http://www.baidu.com/',target : "_blank"}],
['Zhidao',{ href : 'http://zhidao.baidu.com/',target : "_blank"}]
]
],
['Sogou',{ href : 'http://www.sogou.com/',target : "_blank"}],
['About',{ href : 'javascript:alert(" This is a simple javascript menu !")',target : "_self"}]
];
function showSubMenu( tolist ){
var sublist = document.getElementById(tolist);
if(sublist.style.display == ""){
sublist.style.display = "none";
}else{
sublist.style.display = "";
}
}
function insertMenu(divarea){
document.getElementById(divarea).innerHTML=createMenu(MENU_ITEMS,"soya_menu");
showSubMenu("soya_menu");
}
function createMenu(menu_it,id_pre){
var html="<ul id='"+id_pre+"' style='display:none;padding-top:8px' >";
for( var i=0 ; i<menu_it.length; ++i){
var sub_id_pre=id_pre+"m"+i;
html += "<li>";
if(menu_it[i][1]){
html += "<a href='"+menu_it[i][1]+"'>";
html += menu_it[i][0];
html += "</a>";
}else if(menu_it[i][2]){
html += "<a href='"+menu_it[i][1].href+"' target='"+menu_it[i][1].target+"'>";
html += menu_it[i][0];
html += "</a>";
html += createMenu(menu_it[i][2],sub_id_pre);
}else{
html += menu_it[i][0];
}
html += "</li>";
}
html +="</ul>";
return html;
}
insertMenu("soya_menus");
</script>
Wednesday, February 14, 2007
不同浏览器下装载js的不同表现
这两天在改blog，因为脑子里又掺了一些杂七杂八的念头，想要实现一下，呵呵。如果这两天有看我blog的话，可能时不时会发觉自动跳框啊或者某个功能怎么没了等等状况。那就是我在改blog，这个时候要找我的话，直接上gtalk就行啦。
为了实现多个浏览器下效果一致，花了不少心血啊。先看看效果吧，见左边的“日程更新”，我的Calendar是以event list形式表示，当然可以有其他选择，这是后话（有空时候再说吧）如果是Firefox的话可以看到边是带弧的，是用的css3，ie和opera下没看出来。ie下还有其他一些css效果也看不出来。不过基本的效果是三个都一样的。
因为涉及要下多个Calendar然后合并的操作，发觉三个浏览器对于js下载和加载的表现各不相同。在做Web可要特别注意了哦，在这我说一下我遇到的情况吧:
情况如下，首先要下载四个Calendar的数据（用Google 的 JSON API），每个下载完回调一个Handle，Handle将数据加入EventList。四个都Handle过了，调用showEventList()。三个浏览器的下载方式应该都是并发的，这点应该没有疑问。每一个Calendar的操作相当于是在一句<script src="****"></script>,加载顺序正好三种浏览器三种方式。
首先是IE，由于对多个Calendar操作，然后用到了一个eventlist，可以想象是多线程在操作一个数据域。IE可以说是完全多线程的，如果给Calendar编号 1 2 3 4，那么在下载完数据后回调的顺序可能是 2 3 1 4 或者 1 3 4 2 等等。另外，用来动态加载这些javascript的那段js与这四个新js也是并发的。这样有两点麻烦：
然后是Opera，Opera不论从哪方面讲都适合年轻人使用，充满了朝气！今天的修改其实主要是针对IE的，Firefox和Opera基本上是一致的。但在最后，Opera的一个反常举动让我调了老半天才调出来。
Opera的js装载好象是完全顺序，与IE截然相反。顺序到一个页面的所有script都得一步一步来，就像只有一个线程。如果以原script为 0，四个数据js文件还是 1 2 3 4，那么Opera的执行顺序将是 0 1 2 3 4 0，最后的0是返回原脚本，感觉就是堆栈式的函数调用。就是最后那个返回原脚本，让我措手不及。楞了老半天才发觉。
最后是Firefox，个人觉得，Firefox 更适合用来开发 web 程序。就在今天的修改过程中，无论我怎么改，只要基本的逻辑是对的，那么Firefox的效果始终是如预期的。
以Opera那种假设下来说，Firefox的执行顺序是 0 1 2 3 4。我觉得这样理解好了，Firefox是把script放在页面文件中。装载顺序是从头到尾依次装载的（严格按照js在页面中出现的顺序），js的运行不并发，装一个运行一个结束后再装。几个好处吧：
其实单就用户体验来说，IE可能更受欢迎，毕竟是多线程的，不会因为一个js的错误而导致整个页面僵死。而且就三个浏览器看我blog的速度来说，IE应该是比较快的（除了Opera在有缓存的情况，其缓存给我的印象颇深刻~）。但我还是比较喜欢Firefox，毕竟咱是做“写”工作的人嘛，而且速度这个是可以用不同手段提高的。
最后赞一下Firebug，开发人员的福音啊！
为了实现多个浏览器下效果一致，花了不少心血啊。先看看效果吧，见左边的“日程更新”，我的Calendar是以event list形式表示，当然可以有其他选择，这是后话（有空时候再说吧）如果是Firefox的话可以看到边是带弧的，是用的css3，ie和opera下没看出来。ie下还有其他一些css效果也看不出来。不过基本的效果是三个都一样的。
因为涉及要下多个Calendar然后合并的操作，发觉三个浏览器对于js下载和加载的表现各不相同。在做Web可要特别注意了哦，在这我说一下我遇到的情况吧:
情况如下，首先要下载四个Calendar的数据（用Google 的 JSON API），每个下载完回调一个Handle，Handle将数据加入EventList。四个都Handle过了，调用showEventList()。三个浏览器的下载方式应该都是并发的，这点应该没有疑问。每一个Calendar的操作相当于是在一句<script src="****"></script>,加载顺序正好三种浏览器三种方式。
首先是IE，由于对多个Calendar操作，然后用到了一个eventlist，可以想象是多线程在操作一个数据域。IE可以说是完全多线程的，如果给Calendar编号 1 2 3 4，那么在下载完数据后回调的顺序可能是 2 3 1 4 或者 1 3 4 2 等等。另外，用来动态加载这些javascript的那段js与这四个新js也是并发的。这样有两点麻烦：
- 时间上难掌握：程序是非顺序的，对于需要顺序完成的任务实现时要加不少辅助变量。
- 空间上易出错：由于好几个Calendar的Handle是同一个Handle，这样就要手动控制好变量的同步，容易出现脏数据。
然后是Opera，Opera不论从哪方面讲都适合年轻人使用，充满了朝气！今天的修改其实主要是针对IE的，Firefox和Opera基本上是一致的。但在最后，Opera的一个反常举动让我调了老半天才调出来。
Opera的js装载好象是完全顺序，与IE截然相反。顺序到一个页面的所有script都得一步一步来，就像只有一个线程。如果以原script为 0，四个数据js文件还是 1 2 3 4，那么Opera的执行顺序将是 0 1 2 3 4 0，最后的0是返回原脚本，感觉就是堆栈式的函数调用。就是最后那个返回原脚本，让我措手不及。楞了老半天才发觉。
最后是Firefox，个人觉得，Firefox 更适合用来开发 web 程序。就在今天的修改过程中，无论我怎么改，只要基本的逻辑是对的，那么Firefox的效果始终是如预期的。
以Opera那种假设下来说，Firefox的执行顺序是 0 1 2 3 4。我觉得这样理解好了，Firefox是把script放在页面文件中。装载顺序是从头到尾依次装载的（严格按照js在页面中出现的顺序），js的运行不并发，装一个运行一个结束后再装。几个好处吧：
- 更贴近web开发者的正常逻辑。web开发者一般是写页面的时候嵌js，而不是写js的时候嵌页面 。这样Firefox显然比Opera更适合web开发者。
- 脚本并行处理(IE)考虑了一块js一个用途的方式时候的效率，但是不适合多个js联合工作，特别是需要时间上和空间上控制的工作。
其实单就用户体验来说，IE可能更受欢迎，毕竟是多线程的，不会因为一个js的错误而导致整个页面僵死。而且就三个浏览器看我blog的速度来说，IE应该是比较快的（除了Opera在有缓存的情况，其缓存给我的印象颇深刻~）。但我还是比较喜欢Firefox，毕竟咱是做“写”工作的人嘛，而且速度这个是可以用不同手段提高的。
最后赞一下Firebug，开发人员的福音啊！
Monday, February 12, 2007
GNU主页，无语了
看了GNU的主页，无语了。
Orz Orz Orz
Orz Orz Orz
http://badvista.fsf.org/
网站 logo ，太牛了，汗呐。
其实学得越多，就越是看到微软的黑手扼杀了多少开放、有活力、有想法的人才和思想。某种程度上，我是满崇拜Gates的，但有时候看到微软做的事情实在是不得不让人发横。
用了这么久了，也该换了~。
Orz Orz Orz
Orz Orz Orz
http://badvista.fsf.org/
网站 logo ，太牛了，汗呐。
其实学得越多，就越是看到微软的黑手扼杀了多少开放、有活力、有想法的人才和思想。某种程度上，我是满崇拜Gates的，但有时候看到微软做的事情实在是不得不让人发横。
用了这么久了，也该换了~。
Saturday, February 10, 2007
API地图应用大赛
51地图举办的地图API比赛，API确实好用！赞一下51地图。
主要是看中了参与奖是一年的免费《程序员》，不过比赛要五月结束，准确地是说是半年多的《程序员》 -_-b 。
从吃完晚饭到现在，简单地实现了一个idea，先暂时搁在blog上。idea是从新闻里看到现在维修服务（包括小区物业、也包括马路边的公共设施等）讨论得特别多，什么水龙头漏水、空调坏啦、还有道路不方便等等都要报修，好的十几分钟就到，差的搁了几个月也没人管。
所以，我想是不是可以利用地图来做一个“我要修”（不是我要秀）的网站。服务流程如下：
主要是看中了参与奖是一年的免费《程序员》，不过比赛要五月结束，准确地是说是半年多的《程序员》 -_-b 。
从吃完晚饭到现在，简单地实现了一个idea，先暂时搁在blog上。idea是从新闻里看到现在维修服务（包括小区物业、也包括马路边的公共设施等）讨论得特别多，什么水龙头漏水、空调坏啦、还有道路不方便等等都要报修，好的十几分钟就到，差的搁了几个月也没人管。
所以，我想是不是可以利用地图来做一个“我要修”（不是我要秀）的网站。服务流程如下：
- 客户端提供报修，报修人必须提供身份认证，不能让我们的维修工人白忙活，要保证可信度。（认证方法可以替换掉我的sample的身份确认那个输入框，可以用手机号码做为输入）
- 身份认证后，报修人标明地点、填写报修详细。标明，可以是输入地点自动标明（比如输入东方明珠，地图可以自动标到东方明珠），也可以手动标记（手动标记就不显示地点名了，改成坐标）。
- 确认填写信息无误，发送给服务器端。
- 报修中心可以固定时间来看报修情况（比如在人员有充沛的时候），然后选择距离该中心近的点派职工去维修。
- 对于报修成功的用户给以虚拟奖励......这是后话。
Friday, February 09, 2007
看《落叶归根》后感
说实话，很值得一看，很值得深思的电影。
看过《十面埋伏》、《英雄》、《无极》、《夜宴》，这都什么呀，除了大把大把的丢钱，道具买最贵的，地点找最好的（爽一下，然后留个烂滩），然后讲的都是一些不伦不类的、神经质的、莫名其妙的。最近的《满城尽带黄金甲》可谓是此类影片的颠峰，在帝皇身上乱伦、钱花得看着就心疼。最后一段父亲抽儿子尸体那一段，我气得真想上去抽发哥。不谈也罢，看完之后一点都不想再碰这东西。我说拍艺术么关着门自己看你的艺术不就好了吗，我就一coder有闲的时候才去看看最近宣传什么大片（其实我就看过几部宣传力度比较大的影片），管他艺术不艺术、能让人看了喜欢就好，却看到这么恶心的东西，气死，活活气死。但李连杰在《黄金甲》首映式上的慈善宣传另当别论（艺人，就是要告诉大家什么是好的）。
《落叶归根》的故事就是这么一个感人的故事（明星很多，都是很讨人喜欢的明星），我也是先知道了故事再去看的电影。对原故事里加了许多，特别加了不同的人和不同的事。草草的开头、草草的结尾，故事本身已经很感人的，开头和结尾没什么必要多谈（其实头和结尾就这么回事，能拍什么脚指头也想得出，不拍反而到觉着干净），省下更多的时间给更多的故事。公路电影，就是一边走一边拍，电影的分类就决定了遇到很多人很多事儿。影片中冷漠的人群是一个频繁出现的主题，有时甚至将主角逼到了死胡同，这是社会普遍存在的现象，不好多说什么，因为中国本来人就多、又杂、而且无信仰者居多。所以有那么点现象理论上是成立的，只是叫人心理不舒服。
影片的亮点是好人，并不是所有的好人都是好人。影片开头的劫匪就不是好人，但仗义，坏人或多或少应该有那么一种品格，这样就算是坏但也算是个人了。给自己办葬礼的老头，没有什么特别出挑的看头，不过就是农村人的朴素和真诚，无形之中给人亲切的感觉(让我想起了爷爷和他的老家人，其实本土的上海人基本上都是是乡下人的后代)。去西藏的青年，体现是新青年豁达开朗、乐于助人的一面。轮子，可以说是一个喜剧的片段，导演似乎要告诉人们，人虽然生活在底层，但一样有思想、一样有生活情趣。养蜂人，讲爱情，养蜂人孩子的诗歌，讲爱国情，理发店的打工妹，讲思乡情，和捡破烂的之间的黄昏情，都是一些至真至切的感情。还有双簧，可以说是高潮，之后捡破烂的儿子的故事，让人心酸，也不说什么了，好好爱父母吧。影片中警察的形象一直是公正、正义的。不是说什么拍谁马屁，有两点：其一，现在社会上执法人员丑陋的事情批得太多了（说明某种程度社会进步了），但思考问题不应当片面，只有把好的形象立出来，丑陋的地方才有机会改过来；其二，我想影片主要的收看对象是工农阶级的，如果把执法人员的形象再坏掉，那他们心中的未来、理想何去何从？影片有个小细节，车上的孩子给老赵递了瓶水，是和其他人的一个反差，人性还是善良一点的好呀。
最后要赞一下的沿路的美景，公路电影的一个重要的因素！赞一下祖国山水。比《黄金甲》里那种景色要美得多了，而且不容易产生视觉疲劳等不良影响。
最后搜了一下电影网上的反映，好象票房已经紧逼《黄金甲》了，好评如潮。另外国外应该也有市场，除了主题适合各地华人，毕竟这也是一部真材实料的电影。
看过《十面埋伏》、《英雄》、《无极》、《夜宴》，这都什么呀，除了大把大把的丢钱，道具买最贵的，地点找最好的（爽一下，然后留个烂滩），然后讲的都是一些不伦不类的、神经质的、莫名其妙的。最近的《满城尽带黄金甲》可谓是此类影片的颠峰，在帝皇身上乱伦、钱花得看着就心疼。最后一段父亲抽儿子尸体那一段，我气得真想上去抽发哥。不谈也罢，看完之后一点都不想再碰这东西。我说拍艺术么关着门自己看你的艺术不就好了吗，我就一coder有闲的时候才去看看最近宣传什么大片（其实我就看过几部宣传力度比较大的影片），管他艺术不艺术、能让人看了喜欢就好，却看到这么恶心的东西，气死，活活气死。但李连杰在《黄金甲》首映式上的慈善宣传另当别论（艺人，就是要告诉大家什么是好的）。
《落叶归根》的故事就是这么一个感人的故事（明星很多，都是很讨人喜欢的明星），我也是先知道了故事再去看的电影。对原故事里加了许多，特别加了不同的人和不同的事。草草的开头、草草的结尾，故事本身已经很感人的，开头和结尾没什么必要多谈（其实头和结尾就这么回事，能拍什么脚指头也想得出，不拍反而到觉着干净），省下更多的时间给更多的故事。公路电影，就是一边走一边拍，电影的分类就决定了遇到很多人很多事儿。影片中冷漠的人群是一个频繁出现的主题，有时甚至将主角逼到了死胡同，这是社会普遍存在的现象，不好多说什么，因为中国本来人就多、又杂、而且无信仰者居多。所以有那么点现象理论上是成立的，只是叫人心理不舒服。
影片的亮点是好人，并不是所有的好人都是好人。影片开头的劫匪就不是好人，但仗义，坏人或多或少应该有那么一种品格，这样就算是坏但也算是个人了。给自己办葬礼的老头，没有什么特别出挑的看头，不过就是农村人的朴素和真诚，无形之中给人亲切的感觉(让我想起了爷爷和他的老家人，其实本土的上海人基本上都是是乡下人的后代)。去西藏的青年，体现是新青年豁达开朗、乐于助人的一面。轮子，可以说是一个喜剧的片段，导演似乎要告诉人们，人虽然生活在底层，但一样有思想、一样有生活情趣。养蜂人，讲爱情，养蜂人孩子的诗歌，讲爱国情，理发店的打工妹，讲思乡情，和捡破烂的之间的黄昏情，都是一些至真至切的感情。还有双簧，可以说是高潮，之后捡破烂的儿子的故事，让人心酸，也不说什么了，好好爱父母吧。影片中警察的形象一直是公正、正义的。不是说什么拍谁马屁，有两点：其一，现在社会上执法人员丑陋的事情批得太多了（说明某种程度社会进步了），但思考问题不应当片面，只有把好的形象立出来，丑陋的地方才有机会改过来；其二，我想影片主要的收看对象是工农阶级的，如果把执法人员的形象再坏掉，那他们心中的未来、理想何去何从？影片有个小细节，车上的孩子给老赵递了瓶水，是和其他人的一个反差，人性还是善良一点的好呀。
最后要赞一下的沿路的美景，公路电影的一个重要的因素！赞一下祖国山水。比《黄金甲》里那种景色要美得多了，而且不容易产生视觉疲劳等不良影响。
最后搜了一下电影网上的反映，好象票房已经紧逼《黄金甲》了，好评如潮。另外国外应该也有市场，除了主题适合各地华人，毕竟这也是一部真材实料的电影。
Thursday, February 08, 2007
Topcoder Marathon 11
Marathon的System Test也是Marathon式的，等了好久。
第一次做Marathon，这次的题目是贪吃蛇，郁闷...是比较没新意的题目...个人感觉贪吃蛇运气因素较大（测试数据多的话，当然可以降低偶然性），没有觉得能在每盘上都赢得最高分的算法，但确实应该有能保证在大多数情况下表现出色的算法。
我的算法可以说是偶然性十足 -_-b，我也很纳闷，但就是没法解释，所以只能说偶然。Example Test 15次，Submittion 4次， Submittion的成绩是 30.76 -> 28.44 -> 28.13 -> 27.43 一个比一个差 -_-b （但我的想法好象是一个比一个周密才对呀）。
我的算法的思路是这样的：
Step 1. 将Snake的一次行为（调用 moveSnake()）划分为三个小算法， 即计算路径、选路径、移动。
Step 2. 初始化地图我不算在算法里，因为太简单了。计算路径是指，用搜索类的算法，搜索出从Snake到Food的可能路径。
在这一步，我起初使用的是最简单的bfs（就是我得分最高的时候 -_-b）。优点是找到的豆路径最短，缺点是Snake老是擦豆而过，因为路径只关心最短的问题，如果路径上没有经过某个豆，那么即使该豆可以顺便吃掉，Snake也会置之不理。
然后，我改进了算法，使用pfs，以吃到的豆的个数为优先级别进行路径搜索。这样每次都是从吃豆最多的路径继续往下搜，就可以保证将顺路的豆子都能吃掉。结果是，这个pfs每次比bfs走的步数要少，从虚拟程序上看，Snake聪明了许多，但就是吃豆数不见长。
我这有一个我没去实现的算法（因为后面两天都有事），想法是使用多端bfs：Snake头和各个Food各准备一个队列，然后每个循环，依次对每个队列进行扩展。当某个Food队列扩展的路径碰到了Snake的路径，那么Snake到该Food有路；若是Food队列碰到Food队列，那么这两个Food有路。且所有路径最短。改算法的好处是能求出所有最短路径、而复杂度与bfs相同，只是实现有点复杂。
Step 3.选路径，在我自己测试的时候发觉，选路径对于整体结果影响最大！也可以说是偶然性最大的一块。依据Step2中的bfs或者pfs所得到的结果，应该说Snake到Food的路径是固定的，所以就可以说是选下一个受吃的Food。怎么选Food呢？
我给每个Food设置了三个值：
在这里，Area的关系十分重要，很明显的，因为Area表示Snake存活概率高，只要活着就不怕没Food吃。
比如下面两个情况：
很明显，这些Food是DeathFood，优先级要最低，也就是说实在没Food可吃才吃他们。
对于多端bfs，选择的就不是Food了，而是真正的Path。这个就可能和前面的算法完全不同了，我又没实现多端bfs，而且这个貌似更加复杂，就没深入。。。另一方面是被偶然性搞怕了，深怕花了大半天写的程序结果还不如以前的好。
Step 4.移动，即与平台交互，这个只要认真看看平台文档就行了。另外，为了保持Snake和Food位置与平台同步，自己也要模拟Snake的移动。
附加一个想法，由于Step3提到，Snake吃到Food后的Area问题。所以我考虑是否可以通过预广搜一次，标记所有的Area（或者这里称Prison，也就是整个Area有一个格子负责与外界连着，其他格子均与非此Area的格子无连接）。起算法是，由任意一点，开始bfs，但搜索到的格子只有一个目（类似于围棋的目，就是下面这种情况，X是搜索过的格子，#是障碍物，@就是只有一个目）：
这种情况下，将@放入一个Door队列（初始为空）。若搜索第二次遇到@，则@不是Door，标记为搜索过的格子。在待搜索队列为空时，若Door个数大于1，则Area不是Prison，可以再扩展；否则该Area为Prison，同时去除该Door。然后任取一个外面一个没有搜索过的格子再bfs，同样，若搜索到某个Door则取消它Door的资格，否则搜索完再计算Door个数。
可能出现这种情况： Prison - Door - 2个Door的Area - Door ，此时，2个Door的Area不是Prison，但它加上里面的Door和Prison就是一个Prison。可以说是有层次关系的。
总之，算法很复杂，当时摆着电脑楞了许久，最后还是决定先暂时把这个想法搁着 -_-b 。
第一次做Marathon，这次的题目是贪吃蛇，郁闷...是比较没新意的题目...个人感觉贪吃蛇运气因素较大（测试数据多的话，当然可以降低偶然性），没有觉得能在每盘上都赢得最高分的算法，但确实应该有能保证在大多数情况下表现出色的算法。
我的算法可以说是偶然性十足 -_-b，我也很纳闷，但就是没法解释，所以只能说偶然。Example Test 15次，Submittion 4次， Submittion的成绩是 30.76 -> 28.44 -> 28.13 -> 27.43 一个比一个差 -_-b （但我的想法好象是一个比一个周密才对呀）。
我的算法的思路是这样的：
Step 1. 将Snake的一次行为（调用 moveSnake()）划分为三个小算法， 即计算路径、选路径、移动。
Step 2. 初始化地图我不算在算法里，因为太简单了。计算路径是指，用搜索类的算法，搜索出从Snake到Food的可能路径。
在这一步，我起初使用的是最简单的bfs（就是我得分最高的时候 -_-b）。优点是找到的豆路径最短，缺点是Snake老是擦豆而过，因为路径只关心最短的问题，如果路径上没有经过某个豆，那么即使该豆可以顺便吃掉，Snake也会置之不理。
然后，我改进了算法，使用pfs，以吃到的豆的个数为优先级别进行路径搜索。这样每次都是从吃豆最多的路径继续往下搜，就可以保证将顺路的豆子都能吃掉。结果是，这个pfs每次比bfs走的步数要少，从虚拟程序上看，Snake聪明了许多，但就是吃豆数不见长。
我这有一个我没去实现的算法（因为后面两天都有事），想法是使用多端bfs：Snake头和各个Food各准备一个队列，然后每个循环，依次对每个队列进行扩展。当某个Food队列扩展的路径碰到了Snake的路径，那么Snake到该Food有路；若是Food队列碰到Food队列，那么这两个Food有路。且所有路径最短。改算法的好处是能求出所有最短路径、而复杂度与bfs相同，只是实现有点复杂。
Step 3.选路径，在我自己测试的时候发觉，选路径对于整体结果影响最大！也可以说是偶然性最大的一块。依据Step2中的bfs或者pfs所得到的结果，应该说Snake到Food的路径是固定的，所以就可以说是选下一个受吃的Food。怎么选Food呢？
我给每个Food设置了三个值：
- 吃到该Food的路径上顺便可以吃到的Food
- 假设Snake吃该Food，那么吃到Food后，Snake的可移动空间，即一次bfs从Food点开始计算空间（要先模拟好Snake吃到Food的位置）。
- 该区域内还有多少未吃的Food，即如果Snake逃不出该Area，可能还有多少Food可以吃。
在这里，Area的关系十分重要，很明显的，因为Area表示Snake存活概率高，只要活着就不怕没Food吃。
比如下面两个情况：
# ###
#O # #
# #O#
很明显，这些Food是DeathFood，优先级要最低，也就是说实在没Food可吃才吃他们。
对于多端bfs，选择的就不是Food了，而是真正的Path。这个就可能和前面的算法完全不同了，我又没实现多端bfs，而且这个貌似更加复杂，就没深入。。。另一方面是被偶然性搞怕了，深怕花了大半天写的程序结果还不如以前的好。
Step 4.移动，即与平台交互，这个只要认真看看平台文档就行了。另外，为了保持Snake和Food位置与平台同步，自己也要模拟Snake的移动。
附加一个想法，由于Step3提到，Snake吃到Food后的Area问题。所以我考虑是否可以通过预广搜一次，标记所有的Area（或者这里称Prison，也就是整个Area有一个格子负责与外界连着，其他格子均与非此Area的格子无连接）。起算法是，由任意一点，开始bfs，但搜索到的格子只有一个目（类似于围棋的目，就是下面这种情况，X是搜索过的格子，#是障碍物，@就是只有一个目）：
XX#
XX@
XX#
这种情况下，将@放入一个Door队列（初始为空）。若搜索第二次遇到@，则@不是Door，标记为搜索过的格子。在待搜索队列为空时，若Door个数大于1，则Area不是Prison，可以再扩展；否则该Area为Prison，同时去除该Door。然后任取一个外面一个没有搜索过的格子再bfs，同样，若搜索到某个Door则取消它Door的资格，否则搜索完再计算Door个数。
可能出现这种情况： Prison - Door - 2个Door的Area - Door ，此时，2个Door的Area不是Prison，但它加上里面的Door和Prison就是一个Prison。可以说是有层次关系的。
总之，算法很复杂，当时摆着电脑楞了许久，最后还是决定先暂时把这个想法搁着 -_-b 。
Sunday, February 04, 2007
07年2月3日
昨天发生了好多事情，实在不得不记录一下。
早晨9点多，手机铃声把我吵醒了，是我母亲打电话过来叫我快点整理东西，他们马上就到，要接我回家了。回家，家离学校不是很远，但第一次感到这么温馨啊，这次是真正的回家了，要开始准备工作、面对家人、步入社会了。
11点多回到家，首先要把小房间整理一下，乱七八糟的东西实在太多了。已经有三年没有怎么动过小房间了，理出了不少回忆。虽然在进大学之前很贪玩，许多回忆之后都让我颇感悔意，但毕竟这是我的历史，不能像日本人那样，咱该承认的就得承认，以下是罪证：
第一张是追星历史，当时特喜欢欧美的组合和歌手，一有他们的新闻就剪下来 -_-b ，最大的那张美女照是至今都满红的小甜甜Britney，收集了最多的是Backstreet Boys的，还有N' sync、Moffatt和HANSON家庭组合，现在把这些剪报都整理在一张小信封里，准备丢了，回想起来当时确实满幼稚的。除了剪报（其实是很小一部分，小得我发现他们的时候都有点惊讶），CD（正版哦，花了不少父母的血汗啊，悔过ing）和海报（基本也撕光了）才是最多的。CD要留着，老价钱的呀，或许将来可以卖个好价钱（嘿嘿）。
第二张是游戏历史，游戏好比毒品...深有体会，高中一直沉迷游戏，单机游戏玩过一点（和游戏大老leaderz比起来实在很少），而毒我的要属网络游戏，而毒得最深的莫过于《石器时代》和《魔力宝贝》了。图片上的红龙盒子是《石器时代》当时榨取人民财富的罪证，当时这样的包还是限量的，我特别预定才买到，记得那时候这东西炒得很热，黑市上200一个都有。结果等热潮过了之后才发现，原来到处都有买，根本不是限量版。而盒子里的东西很少，就是安装必须的东西，再加一个充气玩具，其主打的是虚拟商品，就是包里的抽奖号码可以中一个游戏中的宠物。地上的点卡30元一张啊，照片里应该是1/5都不到的一部分，而我所有的点卡还不到我另一个好朋友的1/5，对不起父母啊 :( 。
最后的一张是小时侯很喜欢玩的四驱车，益智的，满不错，就是要让车子跑得快、跑得稳还是得花钱...
整理完了一大堆的历史遗留问题后，我去邮局把SCJP的证书拿了出来。东西不多，但很考究，用信封里塑料套着，证书底下一块纸板，保证证书不褶皱，摸上去十分平整。一张证明通过认证的卡（现在什么都有卡，不知道是不是带芯片的）、一个SCJP徽章（很小，一不小心就会掉了）、一张证书、一封恭贺信、还有一份使用SCJP LOGO的协议书。最近看SCWCD（只是看看，如果它不出优惠价格，暂时不会想去考，也许等2年SCJP效力快过的时候去考一下），难度也颇低-_-b，像中国应试能力这么强的民族，应该是随考考的。
正看着SCJP LOGO协议，接到肖和立的电话说晚上六点上大ACM聚餐-_-b（4点出头），匆忙给陈胖子等人电话。衣毕，赶上公交前往。真是一年一度的聚餐，去年是殷老大主办的，今年由Larva主办。
晚上来的主要是前辈4人、我们这一届4人、学弟3人。大家因为ACM而聚在一起，虽然都不是很标准的ACM出生，但一起奋斗过，而且都是有能力有干劲的热血青年，而且除了ACM，我们之间也有许多开心或不开心的往事。餐桌上，学弟们说得很少，主要是前辈们给我们解就业之惑及讨论一些热点技术和未来问题。开头的主要新闻是梁老大的女朋友和他拿了Intel多线程比赛冠军，虽然他表现得很低调，但我抢着把他的事情抖了出来。然后谈论殷老大在SAP的经验，还是这么的健谈，学到了不少经验啊。李签的是SAP最大的partner之一，估计下次聚餐或许是小青年请或者是李和殷请啦。张大依然在为中国之崛起而奋斗，赞一下。肖的就业问题成了下一个讨论热点，我对肖的能力认可而不赞同，我和他的关系有点像在大学里我感觉他压着我，而他感觉我压着他。但我不认为我和他有对手关系，这样满无聊的，我觉得人只有把自己作为竞争对手才能发展得更健壮，所以我迫切希望脱离Larva（可能是暂时的）寻求下一个自我的突破点，所以我搬回了家。
ICPC的未来问题上，两位前辈始终在谈论计算机学院的老师和学生关系。而我觉得应该把上大ACM/ICPC推向全校，因为市场和资源在那里，而且只要能拉到赞助，再改变一点形式。这么高端的竞赛一定很有市场（其实就是奥林匹克从一个民族的运动发展到全世界运动的过程）。至于什么要尊重ACM/ICPC选手啦，ACM/ICPC就是尖子的比赛啦都是废话。竞赛的目的不是选尖，选尖是一种针对性很强的活动，大可不必花费如此多的人力就能选出顶尖的人才（比如直接办个招聘会什么的，写明编码速度要多快，算法熟练度要多高，然后拉批人现场考试就行了。更重要的，选尖要突出的是酬金，而不是奖状或什么荣誉，因为没有荣誉可言，对社会并没推动作用，纯粹是个人与主办方之间的事情）。竞赛的潜在意义是交流，特别是高端与低端的交流（因为容易产生鸿沟，就更需要交流）。而交流的目的是为了发展，通过竞赛给参赛者指定一个虚拟目标，所有参赛者为了目标而奋斗，当达到目标的时候社会就进了一步，竞赛可以衍生或扩展原目标。机器人足球竞赛其实是很成功的竞赛，如果50年后，真的能有机器人踢赢人，那它功不可莫，即使没有实现，他对推动人类进去也有重要作用，而他的参赛者都是走在时代前面的人。Topcoder也是很成功的，它的意义有两层，第一层是商业意义（商业是推动社会进步的最大源动力），第二层是他的交流平台，十分开放，对于培养人才相当有帮助。ACM/ICPC初衷很好，花这么大力气举办一次比赛无非是希望能有更多有才华的人加入进来，一起研究和讨论更高效更准确的算法或者代码实现方法。ACM现在不只是美国计算机协会，而是Association for Computing Machinery，就说明其实它的眼光十分远！这一点是美国值得我们学习的。
扯着扯着就扯远了，聚餐始终很愉快，聚餐结束的时候我忘记给各位拜早年了，乘新年还没来，在这里给所有上大ACM新老成员拜个早年，也给能耐心看完我blog的您拜个早年，祝新年身体健康、心想事成。
早晨9点多，手机铃声把我吵醒了，是我母亲打电话过来叫我快点整理东西，他们马上就到，要接我回家了。回家，家离学校不是很远，但第一次感到这么温馨啊，这次是真正的回家了，要开始准备工作、面对家人、步入社会了。
11点多回到家，首先要把小房间整理一下，乱七八糟的东西实在太多了。已经有三年没有怎么动过小房间了，理出了不少回忆。虽然在进大学之前很贪玩，许多回忆之后都让我颇感悔意，但毕竟这是我的历史，不能像日本人那样，咱该承认的就得承认，以下是罪证：
第一张是追星历史，当时特喜欢欧美的组合和歌手，一有他们的新闻就剪下来 -_-b ，最大的那张美女照是至今都满红的小甜甜Britney，收集了最多的是Backstreet Boys的，还有N' sync、Moffatt和HANSON家庭组合，现在把这些剪报都整理在一张小信封里，准备丢了，回想起来当时确实满幼稚的。除了剪报（其实是很小一部分，小得我发现他们的时候都有点惊讶），CD（正版哦，花了不少父母的血汗啊，悔过ing）和海报（基本也撕光了）才是最多的。CD要留着，老价钱的呀，或许将来可以卖个好价钱（嘿嘿）。
第二张是游戏历史，游戏好比毒品...深有体会，高中一直沉迷游戏，单机游戏玩过一点（和游戏大老leaderz比起来实在很少），而毒我的要属网络游戏，而毒得最深的莫过于《石器时代》和《魔力宝贝》了。图片上的红龙盒子是《石器时代》当时榨取人民财富的罪证，当时这样的包还是限量的，我特别预定才买到，记得那时候这东西炒得很热，黑市上200一个都有。结果等热潮过了之后才发现，原来到处都有买，根本不是限量版。而盒子里的东西很少，就是安装必须的东西，再加一个充气玩具，其主打的是虚拟商品，就是包里的抽奖号码可以中一个游戏中的宠物。地上的点卡30元一张啊，照片里应该是1/5都不到的一部分，而我所有的点卡还不到我另一个好朋友的1/5，对不起父母啊 :( 。
最后的一张是小时侯很喜欢玩的四驱车，益智的，满不错，就是要让车子跑得快、跑得稳还是得花钱...
整理完了一大堆的历史遗留问题后，我去邮局把SCJP的证书拿了出来。东西不多，但很考究，用信封里塑料套着，证书底下一块纸板，保证证书不褶皱，摸上去十分平整。一张证明通过认证的卡（现在什么都有卡，不知道是不是带芯片的）、一个SCJP徽章（很小，一不小心就会掉了）、一张证书、一封恭贺信、还有一份使用SCJP LOGO的协议书。最近看SCWCD（只是看看，如果它不出优惠价格，暂时不会想去考，也许等2年SCJP效力快过的时候去考一下），难度也颇低-_-b，像中国应试能力这么强的民族，应该是随考考的。
正看着SCJP LOGO协议，接到肖和立的电话说晚上六点上大ACM聚餐-_-b（4点出头），匆忙给陈胖子等人电话。衣毕，赶上公交前往。真是一年一度的聚餐，去年是殷老大主办的，今年由Larva主办。
晚上来的主要是前辈4人、我们这一届4人、学弟3人。大家因为ACM而聚在一起，虽然都不是很标准的ACM出生，但一起奋斗过，而且都是有能力有干劲的热血青年，而且除了ACM，我们之间也有许多开心或不开心的往事。餐桌上，学弟们说得很少，主要是前辈们给我们解就业之惑及讨论一些热点技术和未来问题。开头的主要新闻是梁老大的女朋友和他拿了Intel多线程比赛冠军，虽然他表现得很低调，但我抢着把他的事情抖了出来。然后谈论殷老大在SAP的经验，还是这么的健谈，学到了不少经验啊。李签的是SAP最大的partner之一，估计下次聚餐或许是小青年请或者是李和殷请啦。张大依然在为中国之崛起而奋斗，赞一下。肖的就业问题成了下一个讨论热点，我对肖的能力认可而不赞同，我和他的关系有点像在大学里我感觉他压着我，而他感觉我压着他。但我不认为我和他有对手关系，这样满无聊的，我觉得人只有把自己作为竞争对手才能发展得更健壮，所以我迫切希望脱离Larva（可能是暂时的）寻求下一个自我的突破点，所以我搬回了家。
ICPC的未来问题上，两位前辈始终在谈论计算机学院的老师和学生关系。而我觉得应该把上大ACM/ICPC推向全校，因为市场和资源在那里，而且只要能拉到赞助，再改变一点形式。这么高端的竞赛一定很有市场（其实就是奥林匹克从一个民族的运动发展到全世界运动的过程）。至于什么要尊重ACM/ICPC选手啦，ACM/ICPC就是尖子的比赛啦都是废话。竞赛的目的不是选尖，选尖是一种针对性很强的活动，大可不必花费如此多的人力就能选出顶尖的人才（比如直接办个招聘会什么的，写明编码速度要多快，算法熟练度要多高，然后拉批人现场考试就行了。更重要的，选尖要突出的是酬金，而不是奖状或什么荣誉，因为没有荣誉可言，对社会并没推动作用，纯粹是个人与主办方之间的事情）。竞赛的潜在意义是交流，特别是高端与低端的交流（因为容易产生鸿沟，就更需要交流）。而交流的目的是为了发展，通过竞赛给参赛者指定一个虚拟目标，所有参赛者为了目标而奋斗，当达到目标的时候社会就进了一步，竞赛可以衍生或扩展原目标。机器人足球竞赛其实是很成功的竞赛，如果50年后，真的能有机器人踢赢人，那它功不可莫，即使没有实现，他对推动人类进去也有重要作用，而他的参赛者都是走在时代前面的人。Topcoder也是很成功的，它的意义有两层，第一层是商业意义（商业是推动社会进步的最大源动力），第二层是他的交流平台，十分开放，对于培养人才相当有帮助。ACM/ICPC初衷很好，花这么大力气举办一次比赛无非是希望能有更多有才华的人加入进来，一起研究和讨论更高效更准确的算法或者代码实现方法。ACM现在不只是美国计算机协会，而是Association for Computing Machinery，就说明其实它的眼光十分远！这一点是美国值得我们学习的。
扯着扯着就扯远了，聚餐始终很愉快，聚餐结束的时候我忘记给各位拜早年了，乘新年还没来，在这里给所有上大ACM新老成员拜个早年，也给能耐心看完我blog的您拜个早年，祝新年身体健康、心想事成。
Subscribe to:
Posts (Atom)