RFC-黑暗盃程式魔人賽考題
11 |
前陣子在Blog上宣告要辦程式魔人賽的事,還祭出了VSTS2008+MSDN當大獎,說好八月上旬要公佈辦法,結果這陣子也不知在忙什麼,搞得焦頭爛額,連Blog文章都寫沒幾篇,更不用說構思比賽考題的事了。
出來混,遟早要還的。拼了老命,還是把題目給擠出來。先前有提過,遊戲規則會參酌大家的意見,以RFC方式提出,做些微調再定案。所以我先說明草擬的規則並釋出題目程式碼,大家可以開始先玩玩,即日起到2008/08/17 00:00前接受大家留言Call-In給建議,正式規則在8/17後公布。
我寫了一個GameHost的程式,可以指定數字範圍(maxNum)、數字位數(digits),決定題目的困難度,例如: maxNum = 10, digits = 4,可用的數字是0-9,就是我們人腦在玩的1234 2A1B標準猜數字遊戲。要挑戰的人要寫一個Class繼承Player這個Abstract Class:
public abstract class Player
{
protected int _maxNum, _digits;
public virtual int[] StartGuess(int maxNum, int digits)
{
_maxNum = maxNum;
_digits = digits;
return null;
}
public abstract int[] GuessNext(Hint lastHint);
public static Hint Compare(int[] answer, int[] guess)
{
int a = 0, b = 0;
for (int i = 0; i < answer.Length; i++)
for (int j = 0; j < guess.Length; j++)
{
if (answer[i] == guess[j])
if (i == j) a++; else b++;
}
return new Hint(a, b);
}
public string GetPalyerName()
{
return this.GetType().ToString();
}
}
為了示範Player的寫法,我實作了一個只會用亂數胡猜、好傻好天真的DummyPlayer(四位數應該平均要猜5000次才會中吧!)
public class DummyPlayer : Player
{
private int[] _currAnswer = null;
private Random _rnd = new Random();
private void randomGuess()
{
List<int> lst = new List<int>();
for (int i = 0; i < _digits; i++)
{
int r = _rnd.Next(_maxNum);
while (lst.Contains(r))
r = _rnd.Next(_maxNum);
lst.Add(r);
_currAnswer[i] = r;
}
}
public override int[] StartGuess(int maxNum, int digits)
{
base.StartGuess(maxNum, digits);
_currAnswer = new int[digits];
randomGuess();
return _currAnswer;
}
public override int[] GuessNext(Hint lastHint)
{
randomGuess();
return _currAnswer;
}
}
遊戲主持人跟好傻好天真挑戰者的Code可以按這裡下載,放進Mini C# Lab中就可以跑了。
重點來了,比賽規則如下:
- 參賽者請撰寫一個繼承Player的C# Class,以提供Source Code的方式寄到指定Email信箱參賽。
- 參賽者提供的Source Code會整合到前述的遊戲主持人程式碼中,以Mini C# Lab於大會指定的機器上執行,比賽場地有個: Q6600+8G RAM實體機(我的旗艦工作機,簡稱香格里拉)、於該實體機上執行的WinXP 1G RAM VM(簡稱惡魔島)
- 參賽者程式將於香格里拉與惡魔島進行(maxNum/digits): 10/4, 16/6, 20/8, 32/10, 64/12, 256/16, 1024/32七種難易程度不同的猜數字挑戰,每種題目各跑五次,計算次數及耗用時間取平均值。
- 每次猜數字挑戰最長耗用時間不得超過30分鐘,超過即算挑戰失敗。(我不要陷入河內之塔地獄呀)
- 由於是x86 OS,Process有2G的記憶體限制,請節約使用記憶體,想出"暴力攻擊"以外的手法。(這才是有挑戰性的趣味所在吧?)
- 可使用Multithreading解題加快速度。(香格里拉有4核,惡魔島只有單CPU)
- 禁止使用資料庫或檔案作為輔助儲存空間。(禁用的理由是,這麼做很容易又變成另一種暴力攻擊法,但我也擔心會不會禁用後高階的題目就沒解? 我也在猶豫,歡迎大家提供意見)
- 名次計算方式: 共會有7(10/4, 16/6...) * 2 (香格里拉+惡魔島) * 2(比次數少、比時間短) 28場比賽,每場比賽取前三名,第一名得10分,第二名得5分,第三名得3分,解出答案得2分,逾時、記憶體用盡、發生錯誤則得0分。以28場比賽的積分總和決定最後名次,第一名就可以將VSTS2008+MSDN抱回家。
- 主辦單位也會派出一位DarkPlayer
攪局參賽,其積分會列入排名,但無領獎資格。(大家放心,它只算得出10/4, 16/6, 20/8三種,其餘一律Out of memory)
以上就是題目跟比賽規則,給大家七天鑑賞期,有任何意見或想法,請留言提出。(大會保留接受與否的權利,若未被採納請見諒)
另外,想參加的人請在8/17前寄信到"iwantvsts2008 @ darkthread.net"預先報名(為防Spam, 請將其中的空白移除才是電子郵件信箱),讓我掌握參賽人數,或許會調整比賽規則以切合實際狀況。
VSTS2008+MSDN在等著各位呢! 加油~~
Comments
# by chicken
唔... 打了一堆結果 POST ERROR 就不見了 :~~ 有兩個建議: 1. 改用 callback 讓 player 去呼叫 game host 2. 每場比賽的配分,越難的應該得分越高才合理 (1) 我說明一下我的意思,整個解題的演算法或邏輯是一路串下來的,因為程式結構的關係硬是把這邏輯拆成呼叫多次 GuessNext(), 原本的演算法流程都被拆的支離破碎了。
# by Eric Tsai
可以用unsafe嗎?
# by dmwc
問一下用 System.Data.DataTable 暫存資料算不算用資料庫?
# by ' or 1=1 --
System.Data.DataTable? 記憶體會先吃光吧... ̄▽ ̄
# by Z. Zachary
希望難度高的題目應該加權計分, 因為那才是邏輯分析之重點所在.
# by Z. Zachary
希望難度高的題目應該加權計分,因為那才是邏輯分析之重點所在
# by someonepoor
報名會收到回條嗎... 寄了信好像沒下文XD
# by Jeffrey
to chicken, Callback的部分就依你的AsyncPlayer的設計即可,Player會多一個virtual void Stop(),原本的寫法照舊完全不受影響。難度高的給高分的意見很多人提,就順應民意再調整。 to Eric Tsai, 我想C#可以實踐的演算法應該夠用,所以就不開放unsafe囉。 to dmwc, 可以用ADO.NET的DataTable,因為它會受限於Memory,不會造成資源大戰。 to Zachary, 同意,難度高的會加重計分,同時題也會做調整(不少人說1024/32太簡單了,應會改成1024/256) to someonepoor, 信箱有陸續收到報名信,請恕我不一一給回條,會公佈題目時再一併以郵件通知,Blog中也會公佈報名者的代號,發現沒加到的請再出個聲。 RFC期間只剩兩天,請大家把握最後時限囉!
# by chicken
收到! 恕我打個廣告 :P 關於 AsyncPlayer 的說明及用法,我在我的 BLOG 寫了兩篇文章,有需要用的人可以先參考看看。 1. Thread Sync #1. 概念篇 - 如何化被動為主動? http://columns.chicken-house.net/post/Thread-Sync-1-e6a682e5bfb5e7af87-e5a682e4bd95e58c96e8a2abe58b95e782bae4b8bbe58b95.aspx 2. Thread Sync #2. 實作篇 - 互相等待的兩個執行緒 http://columns.chicken-house.net/post/Thread-Sync-2-e5afa6e4bd9ce7af87-e4ba92e79bb8e7ad89e5be85e79a84e585a9e5808be59fb7e8a18ce7b792.aspx
# by 好傻、好天真
大哥: 文中提到的好傻好天真挑戰者 「好傻、好天真」這些關鍵字,在影射誰啊? 哈哈哈哈
# by can
C#.........我試試看好了 沒寫過c#