RFC-黑暗盃程式魔人賽考題

前陣子在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中就可以跑了。

重點來了,比賽規則如下:

  1. 參賽者請撰寫一個繼承Player的C# Class,以提供Source Code的方式寄到指定Email信箱參賽。
  2. 參賽者提供的Source Code會整合到前述的遊戲主持人程式碼中,以Mini C# Lab於大會指定的機器上執行,比賽場地有個: Q6600+8G RAM實體機(我的旗艦工作機,簡稱香格里拉)、於該實體機上執行的WinXP 1G RAM VM(簡稱惡魔島)
  3. 參賽者程式將於香格里拉與惡魔島進行(maxNum/digits): 10/4, 16/6, 20/8, 32/10, 64/12, 256/16, 1024/32七種難易程度不同的猜數字挑戰,每種題目各跑五次,計算次數及耗用時間取平均值。
  4. 每次猜數字挑戰最長耗用時間不得超過30分鐘,超過即算挑戰失敗。(我不要陷入河內之塔地獄呀)
  5. 由於是x86 OS,Process有2G的記憶體限制,請節約使用記憶體,想出"暴力攻擊"以外的手法。(這才是有挑戰性的趣味所在吧?)
  6. 可使用Multithreading解題加快速度。(香格里拉有4核,惡魔島只有單CPU)
  7. 禁止使用資料庫或檔案作為輔助儲存空間。(禁用的理由是,這麼做很容易又變成另一種暴力攻擊法,但我也擔心會不會禁用後高階的題目就沒解? 我也在猶豫,歡迎大家提供意見)
  8. 名次計算方式: 共會有7(10/4, 16/6...) * 2 (香格里拉+惡魔島) * 2(比次數少、比時間短) 28場比賽,每場比賽取前三名,第一名得10分,第二名得5分,第三名得3分,解出答案得2分,逾時、記憶體用盡、發生錯誤則得0分。以28場比賽的積分總和決定最後名次,第一名就可以將VSTS2008+MSDN抱回家。
  9. 主辦單位也會派出一位DarkPlayer攪局參賽,其積分會列入排名,但無領獎資格。(大家放心,它只算得出10/4, 16/6, 20/8三種,其餘一律Out of memory)

以上就是題目跟比賽規則,給大家七天鑑賞期,有任何意見或想法,請留言提出。(大會保留接受與否的權利,若未被採納請見諒)

另外,想參加的人請在8/17前寄信到"iwantvsts2008  @  darkthread.net"預先報名(為防Spam, 請將其中的空白移除才是電子郵件信箱),讓我掌握參賽人數,或許會調整比賽規則以切合實際狀況。

 

VSTS2008+MSDN在等著各位呢! 加油~~

歡迎推文分享:
Published 09 August 2008 11:57 AM 由 Jeffrey
Filed under: ,
Views: 12,134



意見

# chicken said on 09 August, 2008 05:12 PM

唔... 打了一堆結果 POST ERROR 就不見了 :~~ 有兩個建議:

1. 改用 callback 讓 player 去呼叫 game host

2. 每場比賽的配分,越難的應該得分越高才合理

(1) 我說明一下我的意思,整個解題的演算法或邏輯是一路串下來的,因為程式結構的關係硬是把這邏輯拆成呼叫多次 GuessNext(), 原本的演算法流程都被拆的支離破碎了。

# Eric Tsai said on 10 August, 2008 04:10 AM

可以用unsafe嗎?

# dmwc said on 12 August, 2008 12:08 AM

問一下用 System.Data.DataTable 暫存資料算不算用資料庫?

# ' or 1=1 -- said on 12 August, 2008 02:35 AM

System.Data.DataTable?

記憶體會先吃光吧... ̄▽ ̄

# Z. Zachary said on 12 August, 2008 04:26 AM

希望難度高的題目應該加權計分, 因為那才是邏輯分析之重點所在.

# Z. Zachary said on 12 August, 2008 04:28 AM

希望難度高的題目應該加權計分,因為那才是邏輯分析之重點所在

# someonepoor said on 14 August, 2008 09:37 PM

報名會收到回條嗎...

寄了信好像沒下文XD

# Jeffrey said on 15 August, 2008 04:23 AM

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期間只剩兩天,請大家把握最後時限囉!

# chicken said on 15 August, 2008 05:54 AM

收到! 恕我打個廣告 :P  關於 AsyncPlayer 的說明及用法,我在我的 BLOG 寫了兩篇文章,有需要用的人可以先參考看看。

1. Thread Sync #1. 概念篇 - 如何化被動為主動?

columns.chicken-house.net/.../Thread-Sync-1-e6a682e5bfb5e7af87-e5a682e4bd95e58c96e8a2abe58b95e782bae4b8bbe58b95.aspx

2. Thread Sync #2. 實作篇 - 互相等待的兩個執行緒

columns.chicken-house.net/.../Thread-Sync-2-e5afa6e4bd9ce7af87-e4ba92e79bb8e7ad89e5be85e79a84e585a9e5808be59fb7e8a18ce7b792.aspx

# 好傻、好天真 said on 18 August, 2008 02:33 AM

大哥:

文中提到的好傻好天真挑戰者

「好傻、好天真」這些關鍵字,在影射誰啊?

哈哈哈哈

# can said on 27 August, 2008 02:35 AM

C#.........我試試看好了

沒寫過c#

你的看法呢?

(必要的) 
(必要的) 
(選擇性的)
(必要的) 
(提醒: 因快取機制,您的留言幾分鐘後才會顯示在網站,請耐心稍候)

5 + 3 =

搜尋

Go

<August 2008>
SunMonTueWedThuFriSat
272829303112
3456789
10111213141516
17181920212223
24252627282930
31123456
 
RSS
創用 CC 授權條款
【廣告】
twMVC
最新回應

Tags 分類檢視
關於作者

一個醉心技術又酷愛分享的Coding魔人,十年的IT職場生涯,寫過系統、管過專案, 也帶過團隊,最後還是無怨無悔地選擇了技術鑽研這條路,近年來則以做一個"有為的中年人"自許。

文章典藏
其他功能

這個部落格


Syndication