emu in blogjava

現在不是流行pk嘛。

呵呵我是技術理想主義者，sean是實用主義者。

不欣賞gmail的ajax理由是沒有充分利用到xml帶來的好處，后臺必須為前臺的每一個請求度身定做一個返回的（超）文本或者腳本，因此也在后臺帶來了混合編程的問題。

如果實用純xml來做ajax，后臺開發人員可以非常大的被解放出來，更多的關注業務而不是表現，我認為這是ajax帶來的另一個方面的好處。有興趣可以看看
http://qzone-search.qq.com/web/tag/tt_search.html
這個頁面就是接收標準的xml數據來顯示的。比如頁面中間的“最近更新”部分來自于http://qzone-search.qq.com/client/tag/newtags.xml ，而搜索功能的實現則依賴于ajax加載。而tencent公司正在開發中的tm版qzone干脆用ajax技術解析rss數據來生成頁面，這樣后臺開發人員只需要做一套提供rss訂閱的cgi就可以了。

但是在gmail這樣對跨瀏覽器要求比較高的場合上，這是很必然的選擇，跨瀏覽器的xml解析始終是一個麻煩的東東，我現在也還搞不定。打算過一段有時間了再好好研究，實在不行就用純javascript寫一個簡單一點的xml解析器，跨平臺行還更好一些呵呵。

jiniboy ： 本來打算hack掉gmail的腳本來分析gamil的來往數據的，這段時間忙沒有辦法去做，過陣子吧。至于更詳細的技術實現，我認為沒有進一步探究的價值了，我認識的網友有超過一打都可以實現得出來。

todogoingmm ：沒有仔細研究過其中的差別，其實網上的資料很多了。我認為主要差別是不同瀏覽器支持的不同版本的xml控件，但是我們盡量向下兼容，使用最通用的功能。

不如講講你是怎么定位到com.atlassian.license.DefaultLicense.class這個類上面的？

呵呵你也來啦。我再強能有莊老大強？更不要說現在坐在我隔壁位子的廖大哥了。

是嗎？你看到的具體是什么內容呢？關于什么事件的？方舟子的哪些言論你覺得過了？

《上海晨報》網上搜不到它的網站噢，不是據說是華東“最有影響力”的報紙嘛，怎么好像網上沒什么影響力。

百度有進步了，我認錯。
今天中午再搜百度 http://www.baidu.com/s?wd=%D7%DF%CF%F2%B6%F8%C1%A2%D6%AE%C4%EA+emu&cl=3 已經有我的文章了，不過鏈接是指向blogjava首頁的。


同時 yahoo上原來搜到的rss鏈接的結果也更新成我的文章的鏈接了，而且有兩個結果。
http://cn.websearch.yahoo.com/search/web_cn?stype=&p=%D7%DF%CF%F2%B6%F8%C1%A2%D6%AE%C4%EA+emu&scch=on&ei=gb

這次兩個搜索引擎更新這么快顯然和我昨天新發了一篇 Gmail 使用的AJAX技術研究 在blogjava首頁上。

而備受我推崇的google今天表現就讓人失望了，今天中午還是沒有鏈接到我的文章。
http://www.google.com/search?num=100&hl=zh-CN&newwindow=1&q=emu+%E8%B5%B0%E5%90%91%E8%80%8C%E7%AB%8B%E4%B9%8B%E5%B9%B4&btnG=%E6%90%9C%E7%B4%A2&lr=

哈哈你也在盯著google啊

何必繞這么大一圈呢？還要包裝一個exe文件。javaservice其實沒有那么難搞的。

我用javaservice把james安裝成服務之要寫一句：

JavaService.exe -install "James" {JAVA_HOME}\jre\bin\server\jvm.dll -Djava.class.path=C:\james-2.2.0\bin\phoenix-loader.jar; -Djava.ext.dirs=C:\james-2.2.0\lib -start org.apache.avalon.phoenix.launcher.Main -err C:\james-2.2.0\james_error.log

卸載也只要一句

JavaService.exe -uninstall "James"

javaservice自帶的文檔和示范都很詳細的，現在中文資料應該也不難搜到了。

搜了一下，你的文章轉載的地方很多呀。看來現在這方面的中文資料真的是太缺乏了。
可惜很多網站都沒有給出你的原文鏈接。以后寫技術文章也寫一個版權聲明上去好了。

哈哈你要寫就趕快哈，我也在醞釀中。

document.getElementById(currentPos).innerHTML = http_request.responseText;

不如叫AJAH算了。如果你知道我在說什么，我想你會同意我的說法的。

呵呵不用看了，我天天在內部試用新版的foxmail呢。

引用文章不給原文連接不好。我昨天就在donews上面找這篇的原文了，不過找不到。原文連接 http://home.donews.com/donews/article/8/84823.html 早已被刪除。

謠言散播出來了以后源出處卻已毀尸滅跡死無對證，這個槍手手段果然高明。現在網上到處都有轉這篇文章的，反正誰也不用負責任。

我們還是來看看文章本身吧。文章的前面一大部分都是舊內容了，作者顯然相信危言聳聽一萬遍就可以變成真理，值得一看的只有后面最新的幾句：

---------------------------------------------------------------------------
我想肯定是QQ安全中心(和金山毒霸合作搞的)拿我們用戶當試驗品,而騰訊公司為了逃避責任,力圖欺騙QQ大眾不懂技術,用"動態文件名"來蒙我們.沒有一點誠意!

同時我警告一些殺毒軟件公司不要干一些違背職業道德的事,會遭到大眾的漫罵的.

---------------------------------------------------------------------------

槍手的這個“肯定”有任何依據嗎？他憑什么這么肯定呢？
槍手號稱“我已經把這病毒程序提交給了諾頓、卡巴司機等多個病毒廠商”，這么多天過去了，有否哪一個殺毒軟件廠商（這個槍手居然管人家叫“病毒廠商”呵呵）發布了相關的安全公告呢？按照槍手的意思，騰訊不但“和金山毒霸合作搞的”，而且還和諸多病毒廠商共同策劃了這樣一個病毒散播事件，大家可以想想有沒有這樣的可能性呢？

木秀于林，風必催之。中國一共才做出來幾個可以和微軟較勁的軟件，幾個IM卻居然要在這里窩里斗，讓人心寒。

>>這個好像不是groovy的問題
呵呵就象朋友經常批評的，這是人品問題。我覺得這個問題上groovy沒有提供一個簡單的解決方案。

>>類似的東西，偶屢試不爽
是指的什么？import嗎？怎么做呢？

>>前面那個Dog.groovy并不需要編譯
是指的運行不需要編譯還是被其他groovy腳本import之前不需要編譯呢？

不但腳本不是用來“做計算密集型的東西”的，java也不是c#也不是。正兒八經說，高級語言都不是，匯編語言也只是勉強算是。不是用來“做計算密集型的東西”并非就可以把運行效率完全丟開一邊了。我們犧牲一些運算效率來換開發效率是可以接受的，但是犧牲的太多了就不得不要斟酌一下了。

秋水無恨解 http://www.aygfsteel.com/emu/category/2769.html 也是用的腳本呢。

>但對3721，我覺得確實不能原諒
理解理解，當年我也是不勝其煩。
這次國慶回家，發現家里的計算機的主頁也是hao123呵呵。我單位里面用的電腦的主頁是加加在線，沒有辦法，只要一啟動拼音加加2它就幫我重設一變，我干脆把hosts文件改了，把加加在線映射到我喜歡的地址上，由它去改吧。

其實這個事情國慶前就已經辟謠了，病毒廠商和專家的看法和評論在網上也很容易看到。幾個IM廠商和門戶網站收買槍手造謠中傷，平常已極，朋奕何苦摻和？

動態文件名、自我隱藏和自我保護是對付木馬的無奈之舉，而且對用戶沒有造成傷害和不便，卸載也不象當年的3721那么困難（3721后來其實也改正了，何必念念不忘當年的舊帳呢？），“除了破壞數據之外所有病毒的特性都有了”言重了吧？它造成機器變慢？占用額外的資源和帶寬？有傳染性？

至于實名制，那是政策要求。上個月的南方周末有過評論了。

呵呵，我現在不做java了，只能在js上干這些事情了。

JK手腳真快，一下發現了兩個bug：

1 從一個textbox把文字拖放到另一個textbox的情況下不能undo，因為ie沒有觸發兩個onchange事件給我，不能全怪我啊。

2 修改值后我的undo功能和IE自帶的ctrl-z有沖突，呵呵。

Robert Frost顯然不明白世界是由懶人創造的。

幸運的人都是相似的，不幸的人各有各的不幸啊！

相信我，在課本上編造這個謊言的人自己根本就不相信。

要不怎么說多事之秋呢

1 防民之口，甚于防川

2 水至清則無魚

3 政府和網民意見相左的時候，ISP成了夾心餅，偏哪邊都不對，最好悶聲發大財。

好文章，值得一看！

suite可以通過自嵌套來實現分層次遞降的測試每個包，用可變參數來管理的話能實現同樣的目的嗎？

真的是好久了哦。我到深圳來了，忙完了聯系。

原來ｆｏｘｍａｉｌ在３月份被收購了，消息真是遲鈍。

沒有發現現成的IDE哦，其實用記事本也可以開放阿，我是用ｅｄｉｔｐｌｕｓ。ｊｃｒｅａｔｏｒ好像不支持ｊａｖａ之外的語言吧？沒用過。

Office ??

這是誰啊？肖慶來？甄繼業？

遺憾的很，我這個答案沒有通過google的系統測試。

遺憾的很，我這個答案沒有通過google的系統測試。

敗給這一組數據了：
{"8 0 7 51", "47 22 26 30 46", "41 4 9 10 20","33 5 28 39 42", "31 12 56 57", "13 6 17 24 27 36 54","58 32 34 45", "19 2", "3 11 15 25 38 48", "23 1 18 21 29 44 55","40 16 35 43 49 52 53 59", "37 14 50"}
期待結果：50

這是誰啊？回復錯地方了？

google的比賽誰都可以參加啊，為什么一定要來中國辦呢？考場里面也見到不少中國人。

3.11版過時很久啦！
http://www.aygfsteel.com/emu/archive/2005/08/09/9653.html

居然系統測試失敗
Failed system test 10 on the 375-point problem with args: [8, 1, 1]
EXPECTED: 96
RECEIVED: 48

Failed system test 5 on the 375-point problem with args: [50, 50, 50]
EXPECTED: 9200
RECEIVED: 3360

這個題基本上就是我以前寫的 java版本的escape和unescape函數 的簡化版了。
public class URLParser {
    public static void main(String[] args)
    {
        URLParser u = new URLParser();
            System.out.println(u.parse("%48%65%6C%6C%6F%20%57%6F%72%6C%64%21"));
    }
    public String parse(String url){
        StringBuffer tmp = new StringBuffer();
        tmp.ensureCapacity(url.length());
        int lastPos = 0, pos = 0;
        char ch;
        while (lastPos < url.length()) {
            pos = url.indexOf("%", lastPos);
            if (pos == lastPos) {
    ch = (char) Integer.parseInt(url.substring(pos + 1, pos + 3),16);
    tmp.append(ch);
    lastPos = pos + 3;
            } else {
                if (pos == -1) {
                    tmp.append(url.substring(lastPos));
                    lastPos = url.length();
                } else {
                    tmp.append(url.substring(lastPos, pos));
                    lastPos = pos;
                }
            }
        }
        return tmp.toString();
    }
}

public class NewStation {
    public static void main(String[] args) {
        NewStation ns = new NewStation(); ;
        String[] grid = {"2312",
 "0233"};
        String[] stations = {"1 1", "1 1"};
        System.out.println(ns.location(grid, stations));
    }

    public String location(String[] grid, String[] stations) {
        int[][] iGrid = new int[grid.length][grid[0].length()];
        for (int i = 0; i < grid.length; i++) {
            String s = grid[i];
            for (int j = 0; j < s.length(); j++) {
                iGrid[i][j] = s.charAt(j) - 48;
            }
        }
        boolean[][] iStations = new boolean[iGrid.length][iGrid[0].length];
        for (int i = 0; i < stations.length; i++) {
            String[] s = stations[i].split(" ");
            iStations[Integer.parseInt(s[0], 10)][Integer.parseInt(s[1], 10)] = true;
        }
        int minDistanceCount = count(iGrid, iStations);
        String result = "";
        for (int x = 0; x < iGrid.length; x++)
            for (int y = 0; y < iGrid[0].length; y++) {
                int c = count(iGrid, iStations, x, y);
                if (c < minDistanceCount) {
                    result = x + " " + y;
                   minDistanceCount = c;
                }
            }
        return result;
    }

    private int count(int[][] iGrid, boolean[][] iStations) {
        int result = 0;
        for (int i = 0; i < iGrid.length; i++)
            for (int j = 0; j < iGrid[0].length; j++)
                if (!iStations[i][j] && iGrid[i][j] > 0) {
                    int minCount = 99999;
                    for (int x = 0; x < iGrid.length; x++)
                        for (int y = 0; y < iGrid[0].length; y++)
                            if (iStations[x][y] &&
                                (Math.abs(x - i) + Math.abs(y - j) * iGrid[i][j]) <
                                minCount)
                                minCount = Math.abs(x - i) +
                                           Math.abs(y - j) * iGrid[i][j];
                    result += minCount;
                }
        return result;
    }

    private int count(int[][] iGrid, boolean[][] iStations, int x, int y) {
        boolean[][] tmpStations  = new boolean[iStations.length][iStations[0].length];
        for (int i=0;i<iStations.length;i++)
            for (int j=0;j<iStations[0].length;j++)
                tmpStations[i][j]=(x==i&&y==j)?(true):(iStations[i][j]);
        return count(iGrid, tmpStations);

    }

}

import java.util.*;
public class SalesFigures {
   
    public static void main(String[] args)
    {
        String[] sales =   {"GEORGE 999 PETS"};
        // CLIENT_ID CNT_1 PRODUCT_1 CNT_2 PRODUCT_2 ...
        String client = "BOB";
        String product = "SHOE";
        System.out.println(new SalesFigures().getCount(sales,client,product));

    }

    public int getCount(String[] sales, String client, String product){
        HashMap salesHsmp = new HashMap();
        for (int i=0;i<sales.length;i++){
            String[] saleDetail = sales[i].split(" ");
            String clientName = saleDetail[0];
            if (!salesHsmp.containsKey(clientName)) salesHsmp.put(clientName,new HashMap());
            HashMap clientHsmp = (HashMap)salesHsmp.get(clientName);
            for (int j=1;j<saleDetail.length;j+=2){
                int unit = Integer.parseInt(saleDetail[j],10);
                String tmpProduct = saleDetail[j+1];
                if (clientHsmp.containsKey(tmpProduct)){
                    Integer productUnit = (Integer)clientHsmp.get(tmpProduct);
                    unit += productUnit.intValue();
                }
                clientHsmp.put(tmpProduct,new Integer(unit));
            }
        }
        HashMap clientHsmp = (HashMap)salesHsmp.get(client);
        if (clientHsmp == null) return 0;
        Integer unitInteger = (Integer)clientHsmp.get(product);
        return unitInteger==null?0:unitInteger.intValue();
    }

   
}

這也太容易了吧？


import java.util.*;

public class SongFilter {
    public static void main(String[] args) {
        String[] collection, filterInfo, result;
        SongFilter sf = new SongFilter();
        collection = new String[] {"jazz-joe pass-virtuoso-cherokee",
                     "rock-led zeppelin-ii-lemon song",
                     "country-dwight yoakam-long way home-things change",
                     "metal-iron maiden-powerslave-aces high",
                     "pop-supremes-more hits-ask any girl",
                     "rock-faith no more-angel dust-rv",
                     "jazz-chuck mangione-feels so good-feels so good",
                     "rock-van halen-ii-spanish fly"};
        filterInfo = new String[] {"genre=rock", "album=ii"};
        result = sf.filter(collection, filterInfo);
        for (int i = 0; i < result.length; i++)
            System.out.println(result[i]);
    }

    String[] filterPrefix = new String[] {"genre=", "artist=", "album=",
                            "song="};
    int filterPrefixLength = filterPrefix.length;
    public String[] filter(String[] collection, String[] filterInfo) {
        String[] filter = new String[filterPrefixLength];
        for (int i = 0; i < filterInfo.length; i++)
            for (int j = 0; j < filterPrefixLength; j++)
                if (filterInfo[i].startsWith(filterPrefix[j]))
                    if (filter[j] == null)
                        filter[j] = filterInfo[i].substring(filterPrefix[j].
                                length());
                    else if (!filter[j].equals(filterInfo[i].substring(
                            filterPrefix[j].length())))
                        return new String[0];
        ArrayList tmpResult = new ArrayList();
        for (int i = 0; i < collection.length; i++) {
            String[] collectionDetail = collection[i].split("-"); //genre-artist-album-song
            boolean match = true;
            for (int j = 0; j < filterPrefixLength; j++)
                if (filter[j] != null &&
                    !collectionDetail[j].equals(filter[j]))
                    match = false;
            if (match)
                tmpResult.add(collection[i]);
        }
        String[] result = new String[tmpResult.size()];
        tmpResult.toArray(result);
        return result;
    }
}

import java.util.*;
public class ImageLayers {
    public static void main(String[] args) {
        String[] macro = new String[] {"OPEN sky",
                         "OPEN clouds",
                         "OPEN ground",
                         "MERGE 0-1",
                         "OPEN grass",
                         "MERGE 0-2",
                         "OPEN trees",
                         "OPEN leaves",
                         "OPEN birds",
                         "MERGE 1-2",
                         "MERGE 0-1"}
;
        ImageLayers il = new ImageLayers();
        String[] contents = il.contents(macro);
        for (int i=0;i<contents.length;i++)
            System.out.println(contents[i]);
                        

    }

    public String[] contents(String[] macro){
        ArrayList layers = new ArrayList();
        for (int i=0;i<macro.length;i++){
            String command = macro[i];
            if (command.startsWith("OPEN")){
                ArrayList layer = new ArrayList();
                layer.add(command.split(" ")[1]);
                layers.add(layer);
            }
            else if (command.startsWith("MERGE")){
                String[] l = command.split(" ")[1].split("-");
                int layer1 = Integer.parseInt(l[0],10);
                int layer2 = Integer.parseInt(l[1],10);
                ArrayList tmpLayers = (ArrayList)layers.get(layer1);                
                for (int j=layer2;j>layer1;j--)
                    tmpLayers.addAll((ArrayList)layers.remove(j));
            }
        }
        String[] result = new String[layers.size()];
        for (int i=0;i<result.length;i++){
            Object[] stAr = ((ArrayList)layers.get(i)).toArray();
            Arrays.sort(stAr);
            String s =  Arrays.toString(stAr).replace(',',' ');
            result[i] = s.substring(1,s.length()-1);
        }

        return result;
    }

}

public class DiskDefrag {

    public static void main(String[] args) {
        String[] disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
        int size = 20;
        assertEquals(new DiskDefrag().minMoves(disk, size), 5);

        disk = new String[] {"0 1 2 3 5 4 6 7 8 9"};
        size = 10;
        assertEquals(new DiskDefrag().minMoves(disk, size), 2);

        disk = new String[] {"1 3 5 7", "0 2 4 8", "6 9"};
        size = 100;
        assertEquals(new DiskDefrag().minMoves(disk, size), 7);

        disk = new String[] {"31 32 30","27 28 29", "13 24 5",  "19 10 21", "12 3 34",
               "15 6 17", "18 9 0","16 7 8","11 22 23","20 1 2","4 25 26","33 14 35"};
        size = 38;
//        assertEquals(new DiskDefrag().minMoves(disk, size), 17);

        disk = new String[] {"8 0 7 51", "47 22 26 30 46", "41 4 9 10 20",
               "33 5 28 39 42", "31 12 56 57", "13 6 17 24 27 36 54",
               "58 32 34 45", "19 2", "3 11 15 25 38 48", "23 1 18 21 29 44 55",
               "40 16 35 43 49 52 53 59", "37 14 50"};
        size = 60;
//        assertEquals(new DiskDefrag().minMoves(disk, size), 50);
        System.out.println("All passed!");

    }

    private static void assertEquals(int a, int b) {
        if (a != b)
            throw new RuntimeException("assert failed!! Expected " + b +
                                       " but got " + a);
    }

    private int fileCount = 0;
    private int secCount, diskSize;
    private Object[] srcDiskElms;
    private int[][] destDiskElms;
    int maxSuperpositionCount = 0;
    public int minMoves(String[] disk, int size) {
        fileCount = disk.length;
        diskSize = size;
        // 整理String數據建立int數組
        srcDiskElms = getDiskElms(disk);
        // 計算全部文件占用的扇區數
        for (int i = 0; i < fileCount; i++)
            secCount += ((int[]) srcDiskElms[i]).length;
        destDiskElms = new int[fileCount][4];
        //[0]==文件在srcDiskElms中的編號
        //[1]==文件的起始位置
        //[2]==文件的最后一個扇區的位置+1
        //[3]==文件和原始狀態的重合區塊計數

        getMaxSuperpositionCount(0, 0, 0, 0);
        return secCount - maxSuperpositionCount;
    }

    private void getMaxSuperpositionCount(int n, int tmpSecCount,
                                          int tmpSuperpositionCount,
                                          int tmpMoveCount) {
        // 找重合程度最高的文件存儲方式
        if (n < fileCount) {
            for (int i = 0; i < fileCount; i++) {
                // 找到一個還沒有放進destDiskElms的文件（的編號）
                int k = 0;
                for (; k < n; k++)
                    if (destDiskElms[k][0] == i)
                        k = fileCount + 1;
                if (k < fileCount) {
                    int[] srcFile = (int[]) srcDiskElms[i];
                    destDiskElms[n][0] = i;
                    int fileSize = srcFile.length;
                    int lastFileEndOffset = (n == 0) ? 0 :
                                            destDiskElms[n - 1][2]; //上一個文件結束的位置+1。
                    int maxOffset = diskSize - secCount + tmpSecCount; //文件起始位置不可能超過這個位置
                    for (int fileOffset = lastFileEndOffset;
                                          fileOffset <= maxOffset; fileOffset++) {
                        destDiskElms[n][1] = fileOffset;
                        destDiskElms[n][2] = fileOffset + fileSize; //文件的最后一個扇區的位置+1
                        int superpositionCount = 0;
                        for (int j = 0; j < fileSize; j++)
                            if (srcFile[j] == fileOffset + j)
                                superpositionCount++;
                        int moveCount = fileSize - superpositionCount;
                        if (tmpMoveCount + moveCount<secCount - maxSuperpositionCount){
                            destDiskElms[n][3] = superpositionCount;
                            getMaxSuperpositionCount(n + 1,
                                    tmpSecCount + fileSize,
                                    tmpSuperpositionCount +
                                    superpositionCount,
                                    tmpMoveCount + moveCount);
                        }
                    }
                }
            }
        } else {
            int superpositionCount = 0;
            for (int i = 0; i < n; i++)
                superpositionCount += destDiskElms[i][3];
            if (maxSuperpositionCount < superpositionCount)
                maxSuperpositionCount = superpositionCount;

        }

    }

    private Object[] getDiskElms(String[] disk) {
        Object[] result = new Object[disk.length];
        for (int i = 0; i < disk.length; i++) {
            String[] d = disk[i].split(" ");
            int[] ar = new int[d.length];
            for (int j = 0; j < d.length; j++)
                ar[j] = Integer.parseInt(d[j], 10);
            result[i] = ar;
        }
        return result;
    }

}

EP和UE也有groovy語法支持的：
http://www.aygfsteel.com/emu/archive/2005/05/18/4781.html

8月10號jira又發布了3.3版。releasenotes在這里：

http://confluence.atlassian.com/display/JIRA/JIRA+3.3+Release+Notes

檢討了上面的A*算法，其中存在著兩個基本錯誤：
每擴展一個節點就把它從隊列中刪掉，造成下次構造出相同的狀態的時候沒有辦法知道。
用toString來判斷兩個狀態是否相同，但是toString里面除了基本的sector數據之外還有評分的數據，所以不同情況下生成的相同狀態會被判斷成不同狀態。

修正后的A*算法，可以計算出一個比較合理和可行的整理過程，但是沒有辦法保證找到最好的一種（擴展過多的可能性會造成運算超時）。

理論上說只要修改評估策略（countStatus函數）就可以保證算法總是朝正確的方向擴張，但是創造一個合理的評估函數本身就是一個難題。

也許A*算法根本就不是這道題的正解。




import java.util.*;

// 節點增長方式：
// 1、如果內存區域為空，讀取任一塊數據
// 2、如果內存區域非空，寫一個內存塊到任意一個空白的位置

public class DiskDefrag {
public static void main(String[] args) {

String[] disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
int size = 20;
assertEquals(new DiskDefrag().minMoves(disk, size), 5);

disk = new String[] {"1 2 3 5 4 6 7 8"};
size = 10;
assertEquals(new DiskDefrag().minMoves(disk, size), 2);

disk = new String[] {"1 3 5 7", "0 2 4 8", "6 9"};
size = 100;
assertEquals(new DiskDefrag().minMoves(disk, size), 8);

System.out.println("All passed!");

}

private static int countRate = 1000; //為了方便處理評分，把評分值放大一個倍數后取整。
private static int memorySector = 2; //內存可存放的數據
private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public int minMoves(String[] disk, int size) {
DiskStatus d = new DiskStatus(disk, size);
// System.out.println(d.countSecotrOrder());
int countAim = disk.length * countRate;
if (countAim == d.countSecotrOrder())
return 0;
ArrayList diskStatus = new ArrayList();
diskStatus.add(d);
while (true) {
d = getMostHopefulStatus(diskStatus);
// System.out.println(d);
if (d.countSecotrOrder() == countAim) {
int result = d.operationCount / 2;
System.out.print("-----------------------------------------\n" +
d);
while (d.parentStatus != null) {
d = d.parentStatus;
System.out.print("\n" + d);
}
return result;
}
d.expanded = true;
for (int i = 0; i < d.files.length; i++) {
int[] file = (int[]) d.files[i];
for (int j = 0; j < file.length; j++) {
if (file[j] >= 0) {
if (d.memoryAvalible > 0) {
DiskStatus newStatus = new DiskStatus(d, i, j, -10);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
} else {
for (int k = 0; k < d.sectorFill.length; k++) {
if (!d.sectorFill[k]) {
DiskStatus newStatus = new DiskStatus(d, i, j,
k);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
}
}
}
}
}
}

private boolean checkExist(ArrayList statusList, DiskStatus status) {
String map = status.getDiskMap();
for (int i = 0, n = statusList.size(); i < n; i++) {
if (map.equals(((DiskStatus) statusList.get(i)).getDiskMap()))
return true;
}
return false;
}

private DiskStatus getMostHopefulStatus(ArrayList list) {
// System.out.println(list);
DiskStatus result = null;

for (int i = 0, n = list.size(); i < n; i++) {
DiskStatus tmpStatus = (DiskStatus) list.get(i);
if (!tmpStatus.expanded) {
if (result == null) {
result = tmpStatus;
} else {
if (result.countStatus() < tmpStatus.countStatus())
result = tmpStatus;
}
}
}
return result;
}

class DiskStatus {
DiskStatus parentStatus;
boolean expanded = false;
Object[] files;
boolean[] sectorFill;
int order = -1;
int operationCount = 0; //操作次數記數
int memoryAvalible = memorySector;
public DiskStatus(DiskStatus d, int fileIndex, int sectorIndex,
int newSector) {
parentStatus = d;
// d.expanded = true;
files = d.files.clone();
sectorFill = d.sectorFill.clone();
int[] file = ((int[]) files[fileIndex]).clone();
memoryAvalible = d.memoryAvalible;
if (file[sectorIndex] >= 0)
sectorFill[file[sectorIndex]] = false;
else
memoryAvalible++; //轉移一個塊到硬盤上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //轉移一個塊到內存上
order = -1;
operationCount = d.operationCount + 1;
}

public DiskStatus(String[] disk, int size) {
files = new Object[disk.length];
sectorFill = new boolean[size];
for (int i = 0; i < disk.length; i++) {
String[] tmp = disk[i].split(" ");
int[] fileSectors = new int[tmp.length];
for (int j = 0; j < tmp.length; j++) {
int k = Integer.parseInt(tmp[j], 10);
fileSectors[j] = k;
sectorFill[k] = true;
}
files[i] = fileSectors;
}
}

public int countSecotrOrder() {
if (files == null)
return -1;
if (order >= 0)
return order;
order = 0;
for (int i = 0; i < files.length; i++) {
int[] fileSectors = (int[]) files[i];
int lastSector = fileSectors[0];
int fileOrder = 0, orderedSecCount = 0;
for (int j = 1; j < fileSectors.length; j++) {
int sector = fileSectors[j];
if (sector == lastSector + 1)
orderedSecCount++;
else
orderedSecCount = 0;
if (orderedSecCount > fileOrder)
fileOrder = orderedSecCount;
//統計最多的連續塊作為這個文件順序性的評估標準
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 順序度的評估值，每個文件最高countRate分，即整理完成。order=文件個數×countRate時全部排序完成。
}
return order;
}

public int countStatus() {
return countSecotrOrder() - operationCount * 20;
}


public String toString() {
StringBuffer result = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
if (j > 0)
result.append('\t');
if (file[j] >= 0)
result.append(file[j]);
else
result.append('*');
}
result.append("\t\t");
}
result.append('\n');
// result.append("(order:").append(countSecotrOrder())
// .append(")(count:").append(countStatus())
// .append(")(operation:").append(operationCount).append(')')
// .append(
// '\n');
return result.toString();
}

private String diskMap = null;
private String getDiskMap() {
if (diskMap != null)
return diskMap;
StringBuffer map = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
map.append(file[j]).append(',');
}
map.append(';');
}
diskMap = map.toString();
return diskMap;
}
}
}

http://befresh.bjug.org/content/view/27/5/

手術情況
作者： Administrator
2005-08-15
手術情況還算順利，他妹妹上周末已出院。

王俊還在住院觀察，需要在這周才能知道更多情況。
我們的募捐活動將在這周得知確切結果后結束。

感謝所有的好心人們。

在8月6日活動上，王俊通過電話向大家介紹了自己的情況，并感謝所有人的幫助。

用A*算法來擴展狀態樹，當問題稍微復雜一點的時候狀態樹生長的太厲害，沒有辦法在規定時間內找到解，失敗！

import java.util.*;

// 節點增長方式：
// 1、如果內存區域為空，讀取任一塊數據
// 2、如果內存區域非空，寫一個內存塊到任意一個空白的位置

public class DiskDefrag {
public static void main(String[] args) {
String[]disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
int size = 20;
assertEquals(new DiskDefrag().minMoves(disk, size), 5);

disk = new String[] {"1 2 3 5 4 6 7 8"};
size = 10;
assertEquals(new DiskDefrag().minMoves(disk, size), 2);
/*
disk = new String[] {"1 3 5 7","0 2 4 8","6 9"};
size = 100;
assertEquals(new DiskDefrag().minMoves(disk, size), 7);
*/
System.out.println("All passed!");

}

private static int countRate = 100; //為了方便處理評分，把評分值放大一個倍數后取整。
private static int memorySector = 2; //內存可存放的數據
private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public int minMoves(String[] disk, int size) {
DiskStatus d = new DiskStatus(disk, size);
// System.out.println(d.countSecotrOrder());
int countAim = disk.length * countRate;
if (countAim == d.countSecotrOrder())
return 0;
ArrayList diskStatus = new ArrayList();
diskStatus.add(d);
while (true) {
d = getMostHopefulStatus(diskStatus);
System.out.println(d);
if (d.countSecotrOrder() == countAim)
return d.operationCount / 2;
diskStatus.remove(d);
for (int i = 0; i < d.files.length; i++) {
int[] file = (int[]) d.files[i];
for (int j = 0; j < file.length; j++) {
if (file[j] >= 0) {
if (d.memoryAvalible > 0) {
DiskStatus newStatus = new DiskStatus(d, i, j, -1);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
} else {
for (int k = 0; k < d.sectorFill.length; k++) {
if (!d.sectorFill[k]) {
DiskStatus newStatus = new DiskStatus(d, i, j,
k);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
}
}
}
}
}
}

private boolean checkExist(ArrayList statusList, DiskStatus status) {
String st = status.toString();
for (int i = 0, n = statusList.size(); i < n; i++) {
if (st.endsWith(statusList.get(i).toString()))
return true;
}
return false;
}

private DiskStatus getMostHopefulStatus(ArrayList list) {
// System.out.println(list);
DiskStatus result = (DiskStatus) list.get(0);
for (int i = 1, n = list.size(); i < n; i++) {
DiskStatus tmpStatus = (DiskStatus) list.get(i);
if (result.countStatus() < tmpStatus.countStatus())
result = tmpStatus;
}
return result;
}

class DiskStatus {
// DiskStatus parentStatus;
// boolean expanded = false;
Object[] files;
boolean[] sectorFill;
int order = -1;
int operationCount = 0; //操作次數記數
int memoryAvalible = memorySector;
public DiskStatus(DiskStatus d, int fileIndex, int sectorIndex,
int newSector) {
// parentStatus = d;
// d.expanded = true;
files = d.files.clone();
sectorFill = d.sectorFill.clone();
int[] file = ((int[]) files[fileIndex]).clone();
memoryAvalible = d.memoryAvalible;
if (file[sectorIndex] >= 0)
sectorFill[file[sectorIndex]] = false;
else
memoryAvalible++; //轉移一個塊到硬盤上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //轉移一個塊到內存上
order = -1;
operationCount = d.operationCount + 1;
}

public DiskStatus(String[] disk, int size) {
files = new Object[disk.length];
sectorFill = new boolean[size];
for (int i = 0; i < disk.length; i++) {
String[] tmp = disk[i].split(" ");
int[] fileSectors = new int[tmp.length];
for (int j = 0; j < tmp.length; j++) {
int k = Integer.parseInt(tmp[j], 10);
fileSectors[j] = k;
sectorFill[k] = true;
}
files[i] = fileSectors;
}
}

public int countSecotrOrder() {
if (files == null)
return -1;
if (order >= 0)
return order;
order = 0;
for (int i = 0; i < files.length; i++) {
int[] fileSectors = (int[]) files[i];
int lastSector = fileSectors[0];
int fileOrder = 0, orderedSecCount = 0;
for (int j = 1; j < fileSectors.length; j++) {
int sector = fileSectors[j];
if (sector == lastSector + 1)
orderedSecCount++;
else
orderedSecCount = 0;
if (orderedSecCount > fileOrder)
fileOrder = orderedSecCount;
//統計最多的連續塊作為這個文件順序性的評估標準
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 順序度的評估值，每個文件最高countRate分，即排序完成。order=文件個數×countRate時全部排序完成。
}
return order;
}

public int countStatus() {
return countSecotrOrder() - operationCount*2;
}

// public int compareTo(Object o) {
// return ((DiskStatus) o).countSecotrOrder() - countSecotrOrder();
// }

public String toString() {
StringBuffer result = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
if (j > 0)
result.append('.');
result.append(file[j]);
}
result.append("(order:").append(countSecotrOrder()).append(")(count:").append(countStatus()).append(')').append(
'\n');
}
return result.toString();
}
}
}

也是送分題。但是要在規定時間內麻利的分析處理全部字符串形成規則和判斷就靠熟練了。
public class SimpleRouter {

public static void main(String[] args) {
SimpleRouter s = new SimpleRouter();
String[] rules = {"FORWARD 192.168.000.* 001-100 192.168.0.10",
"FORWARD 192.168.0.1 80 10.10.95.184 8080",
"ACCEPT 192.168.*.* 25", "REJECT 192.168.5.38 *"
};
String[] packets = {"192.168.0.43 80",
"00192.00168.000.001 00080",
"192.168.0.1 110",
"192.168.1.73 80",
"192.168.1.73 25",
"206.26.210.5 53",
"192.168.5.38 25"
};
String[] result = s.route(rules, packets);

for (int i = 0; i < result.length; i++)
System.out.println(result[i]);
System.out.println("-------------------------------------------------------------------------------");

rules = new String[] {"FORWARD *.*.*.* * 192.168.0.1"};
packets = new String[] {"213.148.161.82 9484",
"172.230.108.145 16627",
"122.141.122.130 46874",
"241.145.145.77 26390",
"139.97.106.125 35305",
"244.131.151.77 26390"
};
result = s.route(rules, packets);
for (int i = 0; i < result.length; i++)
System.out.println(result[i]);
System.out.println("-------------------------------------------------------------------------------");

rules = new String[] {"REJECT *.20-252.114-157.36-91 13171-54085",
"ACCEPT *.*.73-180.* *",
"FORWARD 55.63.173.239 * 168.154.33.25",
"REJECT *.72-73.*.48-191 *",
"REJECT 20.51.*.* 4579",
"ACCEPT 70-166.*.*.86-182 *",
"REJECT 88-190.*.119-157.* 3316-27844",
"FORWARD *.52-221.134-250.66-207 * 116.94.120.82"};
packets = new String[] {"203.11.104.45 44072",
"154.92.128.87 30085",
"20.51.68.55 4579",
"177.73.138.69 14319",
"112.65.145.82 26287",
"55.63.173.239 45899"
};
result = s.route(rules, packets);
for (int i = 0; i < result.length; i++)
System.out.println(result[i]);

System.out.println("-------------------------------------------------------------------------------");

rules = new String[] {"FORWARD *.*.*.* * 00.012.00000.099",
"FORWARD 192.168.0.1 110 00.00.00.00 000001"};
packets = new String[] {"192.168.0.43 80", "00192.00168.000.001 00080",
"192.168.0.1 110", "192.168.1.73 80", "192.168.1.73 25",
"206.26.210.5 53", "192.168.5.38 25"};
result = s.route(rules, packets);
for (int i = 0; i < result.length; i++)
System.out.println(result[i]);

}


public String[] route(String[] rules, String[] packets) {
String[] result = new String[packets.length];
for (int i = 0; i < packets.length; i++) {
result[i] = getRoute(rules, packets[i]);
}
return result;
}


private String getRoute(String[] rules, String packet) {
for (int i = rules.length - 1; i > -1; i--) {
String m = match(rules[i], packet);
if (m != null) {
// System.out.println("match rule"+i+":"+rules[i]);
return m;
}
}
return "REJECT";
}

private String match(String rule, String packet) {
String[] ruleParts = rule.split(" ");
String[] packetParts = packet.split(" ");
String ip = packetParts[0];
String port = packetParts[1];
String[] ipParts = ip.split("\\.");
if ("ACCEPT".equals(ruleParts[0])) {
String ipRange = ruleParts[1];
String portRange = ruleParts[2];
String[] ipRangeParts = ipRange.split("\\.");
return (matchPart(ipRangeParts[0], ipParts[0]) &&
matchPart(ipRangeParts[1], ipParts[1]) &&
matchPart(ipRangeParts[2], ipParts[2]) &&
matchPart(ipRangeParts[3], ipParts[3]) &&
matchPart(portRange, port)) ? "ACCEPT" : null;
}
if ("REJECT".equals(ruleParts[0])) {
String ipRange = ruleParts[1];
String portRange = ruleParts[2];
String[] ipRangeParts = ipRange.split("\\.");
return (matchPart(ipRangeParts[0], ipParts[0]) &&
matchPart(ipRangeParts[1], ipParts[1]) &&
matchPart(ipRangeParts[2], ipParts[2]) &&
matchPart(ipRangeParts[3], ipParts[3]) &&
matchPart(portRange, port)) ? "REJECT" : null;
}
if ("FORWARD".equals(ruleParts[0])) {
String ipRange = ruleParts[1];
String portRange = ruleParts[2];
String[] ipRangeParts = ipRange.split("\\.");
if (!(matchPart(ipRangeParts[0], ipParts[0]) &&
matchPart(ipRangeParts[1], ipParts[1]) &&
matchPart(ipRangeParts[2], ipParts[2]) &&
matchPart(ipRangeParts[3], ipParts[3]) &&
matchPart(portRange, port)))
return null;

String[] forwardIp = ruleParts[3].split("\\.");

return Integer.parseInt(forwardIp[0], 10) + "." +
Integer.parseInt(forwardIp[1], 10) + "." +
Integer.parseInt(forwardIp[2], 10) + "." +
Integer.parseInt(forwardIp[3], 10) + ":" +
Integer.parseInt((ruleParts.length>4?ruleParts[4]:port),10);
}
return null;
}

private boolean matchPart(String range, String data) {
if ("*".equals(range))
return true;
if (range.indexOf('-') > -1) {
String[] r = range.split("-");
int lower = Integer.parseInt(r[0], 10);
int upper = Integer.parseInt(r[1], 10);
int i = Integer.parseInt(data, 10);
return (lower <= i && upper >= i);
}
if (Integer.parseInt(range) == Integer.parseInt(data))
return true;
return false;
}
}

送分題。主要難度是在理解題目的描述上。

public class CellPlans
{
public static void main(String[] args)
{
String [] plans = new String []{"2999 1000 29 T","5999 3000 49 F","999 0 19 F"};
int[] peakMinutes = new int[]{1543,463,754,405,0,30};
int[] offMinutes = new int[]{100,2053,1003,534,2595,3056};
int cheapest = new CellPlans().cheapest(plans,peakMinutes,offMinutes);
System.out.println("cheapest plan is :"+cheapest);

plans = new String []{"10000 0 0 T","10000 0 0 F"};
peakMinutes = new int[]{20000,25000};
offMinutes = new int[]{25000,20000};
cheapest = new CellPlans().cheapest(plans,peakMinutes,offMinutes);
System.out.println("cheapest plan is :"+cheapest);

plans = new String []{"100000 0 1000 F","100000 0 10 F"};
peakMinutes = new int[]{25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000};
offMinutes = new int[]{25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000};
cheapest = new CellPlans().cheapest(plans,peakMinutes,offMinutes);
System.out.println("cheapest plan is :"+cheapest);

}

public int cheapest(String[] plans, int[] peakMinutes, int[] offMinutes){
double min = count(plans[0],peakMinutes,offMinutes);
int result = 0;
for (int i=1;i<plans.length;i++){
double c = count(plans[ i ],peakMinutes,offMinutes);
if (c<min){
min=c;
result = i;
}
}
return result;
}
private double count(String plan,int[] peakMinutes,int[] offMinutes){
String[] ar = plan.split(" ");
double price = Float.parseFloat(ar[0]);
int minutes = Integer.parseInt(ar[1],10);
double costPerMin = Float.parseFloat(ar[2]);
boolean offHours = "T".equals(ar[3]);
double result = peakMinutes.length*price;
for(int i=0;i<peakMinutes.length;i++){
if (offHours){
result += costPerMin*((peakMinutes[ i ]>minutes?(peakMinutes[ i ]-minutes):0));
}else{
result += costPerMin*((peakMinutes[ i ]+offMinutes[ i ])>minutes?(peakMinutes[ i ]+offMinutes[ i ]-minutes):0);
}
}
return result;
}

}

改用BigInteger，decree就可以無限增大了。

import java.math.BigInteger;
public class Alphabet {
public static void main(String[] args) {
long timeMillis = System.currentTimeMillis();
Alphabet a = new Alphabet();
String st = "BABABABABABABABABABABABABABABABABABABABABABABABAB";
System.out.println(st+" = "+a.choices(st));
}

private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public BigInteger choices(String decree) {
BigInteger[] oldPosList = new BigInteger[3];
BigInteger timesCount = BigInteger.ONE;
oldPosList[decree.startsWith("A")?1:2]=BigInteger.ONE;
for (int i = 2; i <= decree.length(); i++) {
timesCount = BigInteger.ZERO;
BigInteger[] newPosList = new BigInteger[i + 2];
char ch = decree.charAt(i - 1);
if (ch == 'A') {
for (int j = 1; j <= i; j++) {
BigInteger times = oldPosList[j];
if (times == null) times = BigInteger.ZERO;
if (i < decree.length())
for (int k = 1; k <= j; k++)
newPosList[k] = (newPosList[k]==null)?times:newPosList[k].add(times);
// timesCount += j*times;
timesCount = timesCount.add(new BigInteger(j+"").multiply(times));
}
} else {
for (int j = 1; j <= i; j++) {
BigInteger times = oldPosList[j];
if (times == null) times = BigInteger.ZERO;
if (i < decree.length())
for (int k = j + 1; k <= i + 1; k++)
newPosList[k] = (newPosList[k]==null)?times:newPosList[k].add(times);
// timesCount += (i-j+1)*times;
timesCount = timesCount.add(new BigInteger((i-j+1)+"").multiply(times));
}
}
oldPosList = newPosList;
// if (timesCount > 1000000000) return -1;
}
return timesCount;
}
}