(回覆 Andric) -_-a 有這回事 ... 強烈懷疑 這是蒙面人 幕後操盤的結果 ....

看原本的題目描述一直以為 phantom 會很邪惡地出個幾百成幾百的壞心大地圖，或是 box 數超多的邪惡地圖，
於是討論結果選擇較簡單之演算法配上 multi-threading 企圖偷機地賺幾分算幾分，但真正題目一出，
馬上重演偷雞不著蝕把米的故事...
從這次的比賽我學到了：
1. phantom 並沒有想像中的邪惡，我們都錯怪他了，什麼 multi-threading、動態記憶體配置、時間配置，
都太小人之心度君子之腹了
2. 做人做事還是要實在點好，或許應該先來個暴力樹展開，加減砍樹，不要繞圈圈就好了
3. 投機都是會自食惡果的，以後應該要投機的跟實在的兩種方法雙管齊下，才會效果好！ :p
最後，一定要感謝合作愉快的 eric 及 sylvia 讓我有個這麼樣有趣的參賽經驗！ :P

剛剛被 Solos 指正，說我機率部份沒有算好....

我現在更正一下..
=> 三屆以來...共有 12 組獲得前三名....其中單數組包辦了 11/12 的....
=> 如果你今天是分到單數組的話，
在 2004 年，你有 2/3 機率可以得到獎
在 2005 年，你有 3/5 機率可以得到獎
在 2006 年，全部單數組都有獎～

九月一日 記者節當日時況報導：~鬼月的倉庫番 之 死亡筆記版~

11:57 P老大終於公佈了令大家一片驚嘆的題目：倉庫番。

記者P：對於本次的題目您個人有什麼看法。
L：這個題目我之前有想過會出！....
眾人S：快回去加碼
L：(停了一下).....但是我覺得這題目很難, 我做不出來

13:30 收集網路上的資料後，本組討論初步的架構，這時會議室門外頻頻探出關切的目光。
讓大家驚異的是我們從溝通到分工，都出奇的和協愉快。

由於 L 和 E 探員都是箇中高手，一開始 E 就將 BoxWorld 的13個案子全破了，當我們看到
Iterative Deepengin A* Algorithm, Breadth-first search (BFS) 對 L 來說雖有挑戰性，
各門派 Solver 的演算法掌握度卻很高，很快的 L 就在白板畫出架構圖、分工定案。

18:00 P老大幫我們寫裁判程式，一邊寫一邊說:『下次不要出這種題目了，這根本是在折磨我自己。』
不過路克口中雖然唸唸有詞，他還是熱心的連出三個版本，讓我們有標準的晝面可以檢查對照。

22:00 時間 咻~ 就過去了，眼看其他組都已經陸續有執行模擬的雛型了，大家互相分享他們的作戰機制，
L 跟 E 只好商量就現有的資源盡快包出我們的 "Sokoban奇樂" 版。
九月二日

00:00 L 決定留下挑燈夜戰，我們這組的 "Sokoban奇樂" 也大致底定。

03:00 L 把大致想到的功能補完及初步測試，準備小睡片刻。這時大熱門 A 和 H 還在努力中

07:30 L 心想: "我怎麼小睡了五個小時"，下樓前瞄了一眼, A 和 H 維持相同的姿勢仍在努力中。

phantom, 有沒有可能下次別人出題, 然後你也下場比賽?

如同 P 老大所說, Sokoban 和圍棋一樣，是屬於很難量化優劣程度的遊戲，然而以目前 game search
的發展，程式要搜得快、搜得準的話，大置上需要的就是，讓電腦有能力很明確的能計算得出何步較好、
何步較差，否則，只能選擇暴力展開的方法，程式也就無法有效率地解決較大的測試資料。
這次與蛋哥和 Peggy 合作，也許是因為覺得我對這方面比較有經驗，所以讓我有組織整個流程的機會。
雖然結果論，我們幸運的摸到了第三名，但是我自己仍有很多有待加強的地方。
這中間要感謝蛋哥的提醒，讓我沒有浪費太多時間在試著想偷用小氣的 takaken 的那個不給原始碼的程式；
也要感謝 peggy 辛苦的幫我們張羅測試題目、測試那些明明知道再怎麼改進也跑不完的測試資料。
其實我們合作得很好，只是我沒有趁著這個氣勢，嘗試多包幾個模組到程式裡，實在有點可惜呀！
就最後的這幾個測試資料，我想應該會有好解法，也許有時間我可以試試看。如果 P 老大好人做到底，
一早就公布各題的 size 的話，相信各組很有可能都會自己動手做了!

應觀眾要求推出 "鬼月的倉庫番 之 死亡筆記版~(完)~"

九月二日
10:30 沙盤推演 30x30 之內的佈局幾乎都在 L 的掌握之中，但是 "Sokoban奇樂"
的反應確是出乎 L 意料。 L 本想在短短一個半小時內啟用殺手程式，經與 E 討論後覺得風險頗大，
還是維持原案應戰。

12:00 在這場 L 與 奇樂 的鬥智之役，雙方陷入了難分軒輊的局面。看過正版死亡筆記本就知道，
其實幕後最大的贏家是坐觀者無常。

聽說去年的比賽結束後, 有人開會, 檢討過程
的確讓人欽佩

我也來檢討檢討......
回想一下, 我花了多長的時間, 結果還是原地踏步.
回想一下, 我亂撞亂找了, 到底撞出多少用得上的東西.
今年的比賽, 前面好長的時間, 都在狀況外.
最嚴重的.
該作 "基礎建設" 的時間, 被拿來找 "可以用的基礎建設".
比方說, 盤面的 scoring, 記下走過盤面狀況,
找一定不能讓箱子進去"死地"........
這些都是讓我們順利完賽的重要部分.
當然了, 找"可以用的基礎建設", 我並沒能秤心如意.
過去的時間, 長得讓自己驚訝時, 才又乖乖地作該作的苦功
沒辦法, 你知道的呀! 人在走錯路時, "要不要回頭" 這事, 是很讓人苦惱的!

在"狀況外"時,
也不是都沒警覺, 只是一直找不到路回到 "狀況內".
或許, 問問其他人, "狀況內" 的人, 也是一條路吧!
一開始, 我在找 trick! 曾想著集合這些trick, 或許就不會輸了吧!
於是努力地找, 期望它們都成為這一組的勝利方程式.
結果....有些trick, 看起來都很直覺, 但是寫給電腦知道郤不容易,
所以, "勝利方程式" 成員數, 過了一天, 依舊零零落落.
我依舊狀況之外. 星期日的清晨, 我想, 我會對不起, 那下注看好我們的人.
比賽當然有比賽的影響力,
我不清楚我自己有百分之幾為了獎金, 百分之幾為了榮譽.
總之, 它讓我安安份份地坐在電腦前, 甚至熬了一夜
這我得好好想想, 近來常有的倦怠吧!
好像很久都沒有贏過昨天的自己了!

結束之後, 覺得很好笑, 花了一天一夜, 只換到了失望.
不過再想想, 再一次見識到其他人的可敬可愛, 也值了.
能跟你們一齊比賽, 最讚!

一開始要比賽的時候真的很興奮，畢竟我還是新人~以前也沒比過acm什麼的~所以感覺格外的新鮮~XD
因為真的很有衝勁，所以逼迫大家要搬電腦~ 留下來過夜奮鬥~
在這裡真的至上一點點歉意以及滿滿的敬意~^0^
這次跟大家合作的感覺真的很棒~ 尤其認識到大家更多不同的那一面~

林彥谷：之前真的不太熟~~也沒講過什麼話~XD 不過後來發現彥谷人真的很好~~能力強~
脾氣好~ 不時也會冒出幾句很好笑的話(應該是悶騷的C型吧XD)，而且後來也真的留下來過夜，
雖然我知道你有努力的想要掙扎一下~~XD
隆正：跟隆正已經是老戰友了，不算第一次合作，不過隆正真的是很細心的一個人，因為它的測試資料讓我們發現
我們之前的solution到最後都會雞婆多走一兩步，好險有改過來，不然每題都輸別人一兩步結果一定很慘..Orz

榮譽隊友：吳哲慶、Jenny、Calvin
這是一次愉快的結盟經驗，有Jenny滿滿的活力，吳哲慶的沉穩，Calvin的耍冷，讓整個董事長室充滿了歡樂及活力，
有機會的話一定要再偷偷聯盟搞個小團體之類了~~ 哈

雖然比賽結果跟我們預期的有一點點差..:pp(不知道測試資料如果難一點的話，結果會不會不一樣~~)，
雖然我們的榮譽隊友在Demo的時候愛吸引人家注意力，硬是要跑到timeout結果才要出來，害我們跟著提心吊膽，
不過這一切都比不上大家共同努力，一起革命培養出來的情感~~^^，夥伴們！！
一起來個愛的鼓勵吧~！！ 拍！拍！拍拍拍！拍拍拍拍！後嘿！！

by Irene~~

這次能以這種方式來玩程式設計比賽真是愉快. 覺得這次結盟和在同一地點工作的方式非常成功，至少過程很 fun。
有資訊，就可以分享；有 bug 或注意事項，就一起通知；自己的測試資料和結果，還可以請盟友也測一次來核對。
在同一間，討論是即時的，想法是可以畫出來一起看的。嬉笑怒罵、愛的鼓勵、Irene, Calvin 鬥嘴，也都是即時的。
謝謝隊友們，有實力又有士氣，實在太感動了；第七組組員也是，分享讓大家更有效率，過程也更有趣。
也要謝謝 Phantom 尊重我們的集會自由，讓我們在沒事先申請的情況下進駐，晚上十點也沒強制驅散 :P
以下呢，就是這 24 小時在董事長室發生的一些有的沒的事情。

24 推箱任務

12
投影放映倉庫番的畫面... 大家知道題目了
我跟 Irene 說第 7 組跟我們相似，組員也是平常會一起去吃飯的人，可以考慮結盟，一起去吃午餐也好。
午餐時，6人開始計畫待會要在哪裡，怎麼溝通合作。
大家都沒有筆記型電腦...
Irene: "我覺得一定要大家在同一個地方，比較好講話。" 意思是這樣她能一直對人講話吧?
大家考慮 ORIS team, QA, search deliver.. 哪裡方便?
C 型的我提到董事長室，I 型的 Irene 就把它推廣出去。

13
6人走進董事長室察看。Irene 認為這裡就對了，其他人懷疑，真的要搬電腦過來嗎?
幾分鐘的猶豫後，我想想覺得這麼做，沒贏也輸得有 style，而且比較不孤單，我說：
"現在 Irene 怎麼決定我就完全贊成" ，彥谷也只能配合。搬了電腦，開始網路搜尋。

14
論文, 範例, 程式... source code 勒?

15
終於 Calvin 找到一份 source code. 也真奇怪，只有他能 download 下來，我們去 download 就失敗。
開始修改.

17
彥谷已經把程式修改成可以讀 Phantom 的 input 格式，加上外牆，找出正確解答。也幫忙結盟的第7組。

18
彥谷說吃完飯就可以回家了，當然我們不會這麼容易放過他。

20
Calvin: "笨蛋打我啊"
Irene 跑過去打人

22
Jenny 帶大家喊愛的鼓勵..
Jenny, Irene, 隆正: "拍！拍！拍拍拍！拍拍拍拍！後嘿！！"
喔~ 原來喊 "後嘿" 時要雙手要先點肩再高舉成 V 字呀！

23
捷運接近末班車，大家討論要不要過夜。在 Irene 的熱情激勵之下，居然大家都留下了。

既然要留，我就想到了民生問題。
C 型的我只是提供資訊: "古亭捷運站旁的麥當勞好像開到12點"
I 型的 Irene 馬上推廣: "隆正你要去買麥當勞回來嗎? (大聲說) ㄟ 隆正要幫大家買麥當勞!"
於是踏上往麥當勞的旅途。

1
訪客 Ledia 出現，說他的程式幾秒鐘就能跑出結果。
那時我們的程式還在幾分鐘跑不出結果...

3
"啊！~~ 這麼這麼快！" 第七組忽然大叫。
原來第七組發現有另一份 source code, 找出解答的速度快多了。
再 run 一個更大更複雜的測試題目，Calvin 又驚呼: "怎麼這麼快就出來"
這些突來的叫聲，不知道房間外的 Felka 腦中有沒有閃過什麼週刊標題：
"深夜董事長室6P轟趴，驚叫:怎麼這麼快就出來"
ㄟ… 是程式只要 run 個幾秒解法就出來… 別想多了。
大家開始用新的這一份修改… 原本那份以暴力演算法為基礎，修了"半天", 12小時的那一份，就被擱在一邊了。

4, 5
修呀修呀... Stewart 太累先去瞇了

6
天亮了, 大家累壞了… 開始輪流瞇…

7
彥谷: "原本打算 6 點就回家的" (晚上6點)
隆正: "你已經超過一個小時，可以回家了"

8
Calvin: "笨蛋打我啊"
Irene 跑過去打人

9
訪客 Ledia 再度出現: "你們怎麼還是坐在我上次看到的同樣位子呀"

10, 11
繼續做…

12
測結果囉.
ㄟ… 怎麼跟第七組一樣？不是各自有修嗎？看來有改的地方比賽都沒跑到。
算積分..居然來個並列第三名... 真高興呀! good good~

by Lungchen

Sokoban程式設計有夠high事件簿
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
加入這次的比賽，心情是非常忐忑不安的，
因為上一次寫程式的日子已不可考，誰知道我的腦細胞死掉了多少。
尤其跟隊友都不是很熟，即使我號稱Openfind裝熟第一人，
噗哈哈哈哈哈！

哎呀！扯遠了。

我的兩個苦力隊友們，Stewart跟Calvin，
整個比賽過程不僅任勞任怨，能力卓越，
且十分識相地配合「愛的鼓勵」，
可見兩人之親和、活潑與裝可愛的潛力。
這是在專業之外，更教人驚喜的發現！
隊友們，改天來組支Openfind啦啦隊吧 =)

哎呀！又扯遠了。

跟第九組結為盟友是這次比賽的高潮‧‧‧
跟Irene從一開始大陣仗搬運電腦顛覆董事長室、
利用美人計跟MIS借網路線 (感謝Mars熱情支持，火星人果然是善良的!)，
到後來用碎碎唸威逼、用麥當勞利誘老大們(Stewart/彥谷)瘋狂熬夜，
最後虛張聲勢地對付來刺探軍情的Ledia、Felka‧‧‧

這場仗，打得可真是辛苦啊！

咦？為什麼沒有提到Calvin跟隆正？
噢！因為他們從頭到尾都被不人道虐待，不宜播出。

哎呀！還是扯遠了。

總之，這次比賽不論輸贏，我都覺得自己獲得許多。
因為我會牢牢記住的，不是比賽結果，
而是2006年9月1日到2日，董事長室裡的活力、團結跟歡樂！
講到這裡，讀者應該熱淚盈眶掌聲鼓勵做完美ending。

謝謝大家 =)
Jenny

ｐｓ依稀記得Calvin那晚講了一則沒什麼存在感的冷笑話‧‧‧
　　 隊友盟友們如果記得，請提供以列名為Openfind第八大不思議。

這次Phantom實在是太善良了，除了題目簡單外，
還有一件善良的事蹟，怎麼說呢？
話說....
在我們分配好工作後，大家開始埋頭苦幹，
Honesty負責寫檢查程式，當他寫好程式後讓我測試，
而在我確認檢查程式沒問題後，就偷跑去打桌球，
連贏四罐飲料後，就乖乖回小房間繼續奮戰。
(其實我在刺探軍情，且幫組上隊員爭取福利)
這時，Honesty面無表情的說：你有沒有收信。
我心驚(發生什麼事，早知道不去打桌球)，
原來是Phantom發了一封"檢查程式"的信。
T_T ^_^不得。

謝謝這次辛苦的隊員，
Eric_Chang － 晚上回家邊搖小孩邊coding到早上七點多，眼都花了，哈哈。
Honesty － 都沒回家在小房間待命，準備隨時應付緊急狀況。
Sylvia_Chen － 很有感覺的ㄧ次比賽。
(第八組飲料快點拿來，我們等著喝耶。)

by Sylvia_Chen

關於這次比賽的心情，請容許我從頭緩緩道來...
話說到這次我跟Sorry分到同一組，我兩剛好幾個月前家裡
都多了一個兒子(好巧不巧都還同一天生的呢...)
也正因為這個原因，原本我們兩個奶爸打算放棄這次的比賽，
週末在家好好的帶小孩...

所以在題目還未公佈的比賽前一天，我們這組就有了第一個作戰計畫了，
那就是我跟Sorry舉雙手投降--宣布放棄，好回家陪小孩老婆。
我們兩個奶爸為了此決定，還特別找另一位組員Terry，先行溝通一番，
做好心理建設 (這次比賽Terry你是主角了啦！)。

這個計畫一直到P老大公佈題目後，更加堅定了...
因為年近30的我，竟然沒玩過 "倉庫番" 這個遊戲...
(以後被我兒子知道後，肯定會笑掉大牙...)
所以當其他組一知道題目就開始討論的當時，我們這組卻
異常平靜，甚至還決定散步到師大去吃個午飯，
老實講，我們吃飯時幾乎都在聊天，沒談到啥策略。

一直到回公司之後，發現大家好像早已進度神速，
我們才決定改變計畫，應付應付的生個空殼出來好了。
這時才有了簡單分工，Sorry先作架構，我跟Terry先找資料...

沒想到Sorry實作速度之快，一下子就搞好架構了，
讓一樣身為RD的我有點不好意思，況且Sorry還花了不少心思，
作出了一個很漂亮，能畫出地圖的介面，讓它空有其表實在是太浪費了，
因此我當下就決定姑且先做出一套解法，讓Sorry的架構可以派得上用場...
而已經做好架構的Sorry，也決定自己再做出一套解法，
讓這次的程式更完美...
當然，結果就是靠Sorry的這一套架構及我倆個別的兩套解法，
(當然其中還包括Terry辛苦的找資料，以及測試程式...)
我們的拿到了第二名...

我是...Howard...我是...Howard...我是...Howard...

Phantom 把兩個甫獲麟兒的奶爸編在同一組，大家竟然不顧這兩個傢伙得早早回家抱小孩，還拼命下注，
搞得賠率僅次於強者 Andric。到底該說是本公司同仁們賭性堅強，還是認定他們倆會為了獎金不顧妻小？

　　　　　　　※　　　　　　　※　　　　　　　※

其實一開始真的打算放棄的，我倆的老婆都問了「幾點回來帶小孩？」。不過，讓 Terry 孤軍上陣實在
不夠義氣，空手交差也太對不起其他對手，於是我弄了個美麗的"關卡繪圖功能"－－再怎麼樣，輸也要輸得好看。

大概是種一不做二不休的心情，看到 Howard 跟 Terry 都陸續動手了，我光搞個外框也有點不好意思，
索性又繼續寫下去。有一段沒一段地寫著，三不五時起來晃晃，幫別組打氣（？）。半夜一點多，
當大多數人都下了通宵奮戰的決心時，我搭 Howard 的便車回家了。那時，我的小工人還只會在空地上散步，
完全沒有推箱子的意願。唯一令人安慰的是，他不會踩到牆壁上。

最後，我們這組完成了兩套獨立的解題函式。顧慮到 Phantom 不知道會拿什麼樣的題目來測，
Howard 搞出了一個"解法選擇器"：在正常的盤面，讓他們的函式去取得最好的結果，而遇到怪異的題目時，
則用我的函式隨便推幾個箱子到位，然後早早投降。然而 Howard 的解法選擇器可能不忍見到我沒上場機會，
丟了一個題目過來，結果他拿下 1/3/4/5/6 五場全勝的積分，被我一題搞垮。不過能拿到第二名，已是始料未及，
所以他們兩個也沒太責怪我，真是萬幸。

　　　　　　　※　　　　　　　※　　　　　　　※

事後三個人在 MSN 上閒聊．．

Sorry: 我的部份真是拖累了大家
Howard: 我只做了幾個function罷了...
Terry: 我也沒幫上什麼忙說～
Sorry: 原來我們是因為"奇數組"才拿到第二名的！？囧rz

這次的比賽很榮幸能夠跟Howard和Sorry兩位高手一組，看到他們兩位犧牲了與小寶寶相處的寶貴時間，
而致力於比賽的情形真的是令人感動。這次雖然沒有幫上什麼大忙，不過整個參與的過程卻是一個
令人難忘的寶貴經驗。感謝Howard 和 Sorry的努力與付出～～～ Terry

話說參加這次程式設計比賽，心中也是忐忑不安，
不過既來之則安之，相信應該也會是一次難得的經驗，
Irene提議結盟，一開始還有點懷疑這樣是否恰當:p
而且心中也是百般不願意將電腦大費周章的搬到禁閉室 啊...說的太快 應該是董事長室，
抱著姑且一試的心情，就這樣開始了神奇的鬼月版倉庫番來又翻去之Openfind程式設計比賽。
結盟的確還是有些好處，畢竟人多好辦事，互相討論、除錯、測試，腦力激盪，
加上有經驗豐富的stewart、林彥谷，以及充滿活力的jenny及irene，還有細心的隆正，
看到畫面上一個個的木箱被推到目的地，相信一切的努力都是值得的
最終的結果雖然不是最好的，倒也令人滿意，
希望下次還有更多機會跟不同的同事一起合作: )

calvin

這次 Algorithm 大部份的人 都以 "工人" 為 recursive 的 跑法

其實可以用 箱子 來當主角 Computing time 可能比較少一點

假設 K 個可走的空間 (Ex 30 空白格) 有 6 個箱子
這 6 個箱子 在這空白格 所有推放結果 也不過 P(30,6) = 30 * 29 * 28 * 27 * 26 * 25
移動結果 非常便宜的計算量

一下就可以計算出 Optimize 的 solution

假設 "將來" 知道 下一步 箱子 要放那 這時再 以 shortest available path 走到那一步
去推箱子 就可以走出 最佳 solution

Hector 這次分組實在太幸運了，竟然跟偶像Andric一組，
見識到驚人的設計規劃與時程掌控能力，
而且「整個開發過程沒有任何意外發生」，如有神助。
雖然程式規模並不大，但是以前從來沒發生過這種事。

我是一個相信見微知著的人，在這次合作的過程中，
很多小地方讓我明顯感受到實力的差距，
Andric的思路非常清楚，而且做事情又快又穩，
常常我正在想某件事的時候，他已經做掉了，
還丟function過來給我call。
跟他合作的感覺，讓我想到《少林足球》裡面的一個場景：
大家湊在一起看周星馳對著牆壁練球，大師兄說：
「他一個人踢...就行啦」

一切發生的太快，莫名其妙開發期就結束了，
有一種棒球剛打第三局就下大雨取消比賽的感覺...
我parser寫一寫，程式串一串....什麼？沒了！
幸好後來有得名，不然應該很空虛。

另外本組軟體出廠前測試手法非常粗糙，
程式跟資料丟給Seven手動一筆一筆跑，
只有一個「賽」字可以形容，不過Seven還真的給它測下去，
品管人員的精神非常值得敬佩。

我應該是這次比賽裡面投資報酬率最高的人吧，
什麼都沒幹，還會贏，而且賭盤還押自己，有賭金拿，
就被Phantom說貪得無厭XD

這次比賽的感想：組員裡面有神的話，真的很好做事....

(回覆 HBS) P(30,6) = 30 * 29 * 28 * 27 * 26 * 25
是否還少算到工人所在的位置
最明顯的問題是, 工人的位置可能在箱子所圍出的封閉區域的不同邊

我想到的方法是 BFS (廣度優先搜尋) 的變形

BFS 的對象是各種不同的配置
每次的 transition 則是箱子的直線移動的方向和移動的步數

把原本 BFS 的 queue 改成 priority queue
(weight 是到目前配置一共走了幾步)

再加上一個 hash table
來決定現在的這個配置是否要加進 priority queue 裡
(是否這個配置已經有了夠好的走法)

此外, 是否加進 priority queue 還可以加一些 pattern 判斷
例如存在未達定點但無法再移動的箱子的情況
或是某些定位沒有箱子到得了

以上是假設搜尋中同一層的 node 數不會太多
效果好不好.... 做出來才知道

請大家跟著我唸一次 ==> 公司有個善良的 Phantom 真好!!!

當天早上我繞了一圈以後認定我出的 test case 太難，所以臨時把難度調低。
比賽題目簡單點是對的，可以讓大家高興點，所以明年題目會更簡單。