MashiMaro's Blog: 2008

2008年11月26日星期三

[+/-] : [教學] CrackIt 16: "Get the number!"

張貼者： MashiMaro 於星期三, 11月 26, 2008 0 意見

2008年7月6日星期日

[+/-] : [教學] Exploit 14: "Analyse this III!"

張貼者： MashiMaro 於星期日, 7月 06, 2008 0 意見

觀察 sourcecode.txt，由下面兩段code可以發現

//register
fputs($hfile, ";::".$HTTP_POST_VARS['accessid']."::".$md5_passwd."::;\n");

//login
$datastring = $HTTP_POST_VARS['accessid']."::".$md5_pin;
if(strpos($con_file, $datastring)){
 do check...
}

能夠偽裝成別人登入，
不過好像沒有用.....
再觀察別的地方!

// endsess

if((preg_match("/^[a-zA-Z0-9=]+$/i", $HTTP_GET_VARS['sessid'])==true)){
　$session_file = "xxxxx/".$HTTP_GET_VARS['sessid'];
　if(unlink($session_file)==false){
 　do something...
　}

發現sessid在這邊不像register時候有檢查長度！
於是...DONE!

2008年7月5日星期六

[+/-] : [教學] Java-Applet 5: "Defeat Me"

張貼者： MashiMaro 於星期六, 7月 05, 2008 0 意見

2008年7月4日星期五

[+/-] : [教學] Exploit 17: "RHC 6"

張貼者： MashiMaro 於星期五, 7月 04, 2008 0 意見

2008年7月2日星期三

[+/-] : VMware 中安裝Ubuntu 8.04 後滑鼠滾輪無作用

張貼者： MashiMaro 於星期三, 7月 02, 2008 0 意見

2008年6月29日星期日

[+/-] : [Diary] Way back into love (重新找到愛)

張貼者： MashiMaro 於星期二, 3月 25, 2008 0 意見

2008年3月24日星期一

[+/-] : 演算法課本題目 (Exercise 4.1-5) : 求 Big-O

張貼者： MashiMaro 於星期二, 3月 11, 2008 0 意見

CORMEN聖經本的 Exercise 4.1-5，花了我一整個晚上在解

期間還受不了上網偷拜 Google 大神，因為不會輸入 floor 的符號，一直找不到相關題目的解

後來終於解出來了，發哥卻在旁邊說，"這種題目你怎麼沒上網辜？"

我就照他的指示，輸入關鍵字 "2T(floor(n/2)"，

只出現短短5項連結，其中有一個就是別人的解！

偉哉，發哥！

不過辜出來的解最後有錯，

在此幫忙勘誤一下：


因為前提為 34*c*lgn - n*(0.3*c-1) <= 0
且 34*c*lgn >= 0
=> - n*(0.3*c-1) <= 0
=>   n*(0.3*c-1) >= 0
=>      0.3*c-1  >= 0
=>          c    >= 3.3~

所以他令 c = 1 是錯的

後來我推導了一下，實際上 c 必須大於等於 1 / lg(6/5) ~= 3.802

如果令 c = 4，n 必須大於等於 2048 才符合條件。

這時，如果有講義上的 Hint，n 不必到2048以上才符合條件：

Hint: T(n) = a n lg n - b lg n - c...
read more

[+/-] : [Diary] 星光三首度25分！

張貼者： MashiMaro 於星期二, 3月 11, 2008 0 意見

2008年3月4日星期二

[+/-] : 好句共享

張貼者： MashiMaro 於星期二, 3月 04, 2008 0 意見

2008年3月2日星期日

[+/-] : [XD] 白痴妹第二發XD

張貼者： MashiMaro 於星期日, 3月 02, 2008 0 意見

2008年2月29日星期五

[+/-] : PHP從網頁傳遞變數的改變

張貼者： MashiMaro 於星期五, 2月 29, 2008 0 意見


PHP 自從 4.1.0 開始，支援一種比較安全的變數傳遞方式。原本我們在寫 PHP 程式時，從表單以 POST 方式傳入 PHP 程式時，PHP 可以直接拿來使用。例如，有一個表單是下面這個樣子：

<form action=test.php method=post>
    <input type=text name=username>
    <input type=button value=送出 name=b1>
</form>

當上述的 HTML 按了送出之後，在 test.php 這個程式就會有一個變數名為 $username，其值是我們所填入的名稱。

但是使用者也可以直接在網址列輸入 http://url/test.php?username=myname 來設定 $username 這個變數的值為 myname。

這會有什麼問題呢？讓我們以 PHP 4.1.0 release note 所提出的例子來說明。假設我們有一個程式如下：

<?php
if (authenticate_user()) {
    $authenticated = true;
}
...
?> 

使用者可以經由網址列輸入一個變數 $authenticated=true，這樣一來，不管是否通過 authenticate_user() 的檢查，$authenticated 永遠都是 true。

所以在 4.1.0 之後，有一個新的方式可以讓我們使用，就是將傳進來的變數全部都存在陣列中。以第一個例子而言，我們以 POST 的方式從表單傳來變數 $username，新的取得變數方式是：$_POST["username"]，也就是說所有以 POST 傳遞過來的變數全部存在 $_POST 這個陣列中。詳細說明請參考 http://www.php.net/release_4_1_0.php 。

在 4.2.0 之前，新舊二種方式都可以使用，但是在 4.2.0 之後，Default 只能使用新的方式來傳遞變數。所以如果你安裝的了新 PHP 而發現無法使用舊的 PHP 程式，別驚訝。

如果您還是要以舊的方式來傳遞變數，請修改 php.ini (通常位於 /usr/local/lib/)，將原本的 register_globals = Off 改成下列這個樣子，並移除開頭的註解符號 ";"：

; register_globals = Off

register_globals = On


新的方式下，用來存放變數的陣列有下列七種：

    * $_GET：存放以 GET 傳來的變數
    * $_POST：存放以 POST 傳來的變數
    * $_COOKIE ：包含了存在 HTTP cookie 的變數
    * $_SERVER：存放 server 變數 (如 REMOTE_ADDR)
    * $_ENV：存放環境變數
    * $_REQUEST：存放了 GET、POST、及Cookie 變數，也就是從使用者端傳來的變數。換句話說，這個變數的內容並不可靠。
    * $_SESSION：包含了在 session 已註冊的變數。
    * $_FILES：使用者上傳檔案(input type="file")

$_FILES['userfile']['name'] -- 檔案在客戶端電腦上的檔案名稱
$_FILES['userfile']['type'] -- 檔案的 MIME 類型，例如 "image/gif"
$_FILES['userfile']['size'] -- 上傳檔案的檔案大小，單為為 bytes
$_FILES['userfile']['tmp_name'] -- 上傳檔案儲存在伺服器端的暫存檔案名
$_FILES['userfile']['error'] -- 在 PHP 4.2.0 或更新的片本才有的這個陣列元素，上傳檔案的錯誤號碼 

測試方法：
<?php
    if(count($_POST)>0)
        foreach($_POST as $k=>$v)
            echo $k.'='.$v.'<br>';
?>

...
read more

消息來源

2008年1月28日星期一

[+/-] : [Format]BMP

張貼者： MashiMaro 於星期一, 1月 28, 2008 0 意見

由瘋小貓的華麗冒險轉錄，特此感謝。

*******************************************
《簡介》

點陣圖（bitmap）格式是 Windows 採用的圖像檔案儲存格式，在 Windows 環境下運行的所有圖像處理軟件都支持這種格式。Windows 3.0 以前的 BMP 格式與顯示設備有關，因此稱為設備相關點陣圖（Device-Dependent Bitmap, DDB）格式。Windows 3.0 以後的 BMP 格式則與顯示設備無關（Device-Independent Bitmap, DIB），目的是為了讓 Windows 能夠在任何類型的顯示設備上顯示點陣圖檔案。點陣圖檔案的預設副檔名是 BMP 或 bmp。

*******************************************
《點陣圖檔案結構》

點陣圖檔案由四個部份組成：

Bitmap File Header
Bitmap Info Header
Color Table (Palette)
Bitmap Array

Note: 以下欄位資料皆為 little-endian！ Little-Endian 的意思是：若某個欄位值為 0x1234，當你將BMP檔案用 UltraEdit 之類的純文字編輯器打開時，則你看到的值會是 0x3412，這是 Intel 制定的儲存方式，把值小的位元組（0x34）存在前面；詳情可參考 Big Endian 和 Little Endian 架構的說明

	Shift	Name	Size (bytes)	Content
Bitmap File Header	0000h	Identifier (ID)	2	'BM'【註１】
	0002h	File Size	4	整個點陣圖檔案的大小（單位：byte）
	0006h	Reserved	4	保留欄位
	000Ah	Bitmap Data Offset	4	點陣圖資料開始之前的偏移量（單位：byte）
Bitmap Info Header	000Eh	Bitmap Header Size	4	Bitmap Info Header 的長度【註２】
	0012h	Width	4	點陣圖的寬度，以像素（pixel）為單位
	0016h	Height	4	點陣圖的高度，以像素（pixel）為單位【註３】
	001Ah	Planes	2	點陣圖的位元圖層數【註４】
	001Ch	Bits Per Pixel	2	每個像素的位元數 1：單色點陣圖（使用 2 色調色盤） 4：4 位元點陣圖（使用 16 色調色盤） 8：8 位元點陣圖（使用 256 色調色盤） 16：16 位元高彩點陣圖（不一定使用調色盤） 24：24 位元全彩點陣圖（不使用調色盤） 32：32 位元全彩點陣圖（不一定使用調色盤）【註５】
	001Eh	Compression	4	壓縮方式【註６】： 0：未壓縮 1：RLE 8-bit/pixel 2：RLE 4-bit/pixel 3：Bitfields
	0022h	Bitmap Data Size	4	點陣圖資料的大小（單位：byte）【註７】。
	0026h	H-Resolution	4	水平解析度（單位：像素/公尺）【註８】
	002Ah	V-Resolution	4	垂直解析度（單位：像素/公尺）
	002Eh	Used Colors	4	點陣圖使用的調色盤顏色數【註９】
	0032h	Important Colors	4	重要的顏色數【註10】
Palette	0036h	Palette	N*4	調色盤資料。每個索引值指定一種顏色：0x00RRGGBB 其中最高位元組保留為零
Bitmap Array	-	Bitmap Data	-	點陣圖資料【註11】

【註１】此欄原本有多種識別碼，用來識別點陣圖的類型：
　　　　'ＢＭ'　－　Windows 3.1x, 95, NT, ...
　　　　'ＢＡ'　－　OS/2 Bitmap Array
　　　　'ＣＩ'　－　OS/2 Color Icon
　　　　'ＣＰ'　－　OS/2 Color Pointer
　　　　'ＩＣ'　－　OS/2 Icon
　　　　'ＰＴ'　－　OS/2 Pointer
　　　　不過既然 OS/2 並不普及，目前皆在 Windows 上作業，因此 ID 全都是 'BM'。

【註２】此欄原本有多種數值，依作業系統種類而定：
　　　　28h　－　Windows 3.1x, 95, NT, ...
　　　　0Ch　－　OS/2 1.x
　　　　F0h　－　OS/2 2.x
　　　　以目前 Windows 常用的點陣圖來說，此欄位數值通常是 28h。
　　　　但因為微軟已經制定出了新的點陣圖格式，其中的 Bitmap Info Header 結構變化較大，長度加長，所以最好不要直接使用常數 28h，而是應該從實際檔案中讀取這個數值，才能確保程式相容性。

【註３】高度可能為負值，負值表示掃瞄方向由上而下。
　　　　但若高度是負值時，此點陣圖將不能被壓縮！（也就是說 Compression 欄位總是為 0）

【註４】未知的功能...永遠被設為 1。

【註５】16 及 32 位元點陣圖是否使用調色盤必須由 Compression 欄位的數值決定，
　　　　請參考 Bitfields 的解說。

【註６】點陣圖壓縮方式有以下四種：BI_RGB，BI_RLE8，BI_RLE4，以及BI_BITFIELDS。

None (BI_RGB)
表示此點陣圖資料沒有壓縮，不使用調色盤。

RLE 8bpp (BI_RLE8)
每個像素為 8 bit 的 RLE 壓縮編碼（Run-Length Encoding）（總共可使用 256 色）。
有「編碼模式」（Encoded Mode）和「絕對模式」（Absolute Mode）兩種方法，
可在同一幅圖檔中的任何地方交錯使用。

「編碼模式」：由兩個位元組（byte）組成。
　　　　　　　第一個位元組指定 "Length"（使用相同顏色的像素數目），
　　　　　　　第二個位元組指定 "Run"（此像素使用的調色盤索引）。
　　　　　　　若第一個位元組為零，則表示特殊意義：
　　　　　　　0x0000　－　表示此列結束
　　　　　　　0x0001　－　表示此點陣圖檔案結束
　　　　　　　0x0002　－　表示其後的兩位元組分別表示
　　　　　　　　　　　　　下個像素位置與目前像素位置的水平/垂直偏移量。
　　　　　　　0x000x　－　表示絕對模式。

「絕對模式」：第一個位元組為 0x00，第二個位元組為 0x03 ~ 0xFF 之間的數值。
　　　　　　　其中第二個位元組表示後續資料的長度（單位為 byte），
　　　　　　　後續資料的每個位元組都表示單一像素的調色盤索引值。

每一模式的編碼長度都必須與字邊界對齊（word-aligned），也就是 2 的倍數。
使用「編碼模式」時，由於每組編碼皆為兩個位元組，所以毋需多加處理；
但是使用「絕對模式」時，則必須在最後補上適當的 0x00 以使資料長度對齊 2 的倍數。

下面是一個 BI_RLE8 的例子：

03 01 05 02 00 03 00 01 02 00 02 01 00 02 05 01 02 03 00 00 09 02 00 01

這些資料可解讀為：

壓縮資料	解壓縮之後的資料
03 01	01 01 01
05 02	02 02 02 02 02
00 03 00 01 02 00	00 01 02（最後的 00 是為了 word-aligned 才補上的）
02 01	01 01
00 02 05 01	從目前位置右移 5 像素之後，向下移一列
02 03	03 03
00 00	此列結束
09 02	02 02 02 02 02 02 02 02 02
00 01	此點陣圖結束

上述資料的圖形如下：

RLE 4bpp (BI_RLE4)
每個像素為 4-bit 的 RLE 壓縮編碼（總共可使用 16 色）。
同樣也有「編碼模式」與「絕對模式」，且可以在同一圖檔中任何地方使用任一模式。

「編碼模式」：由兩個位元組組成。
　　　　　　　第一個位元組指定像素數目，
　　　　　　　第二個位元組包含兩個調色盤索引：
　　　　　　　第一個像素使用高 4 位元的索引值、
　　　　　　　第二個像素使用低 4 位元的索引值、
　　　　　　　第三個像素又使用高 4 位元的索引值，以此類推。
　　　　　　　若第一個位元組為零，則表示特殊意義：
　　　　　　　0x0000　－　表示此列結束
　　　　　　　0x0001　－　表示此點陣圖檔案結束
　　　　　　　0x0002　－　表示其後的兩位元組分別表示
　　　　　　　　　　　　　下個像素位置與目前像素位置的水平/垂直偏移量。
　　　　　　　0x000x　－　表示絕對模式。

「絕對模式」：第一個位元組為 0x00，第二個位元組表示後續資料的長度（單位為 byte）。
　　　　　　　後續資料的每個位元組都含有兩個調色盤索引值（高 4 及低 4 位元），
　　　　　　　每個索引值對應一個像素。

每一模式的編碼長度仍然必須與字邊界對齊（word-aligned）。
使用「編碼模式」時，由於每組編碼皆為兩個位元組，所以毋需多加處理；
但是使用「絕對模式」時，則必須在最後補上適當的 0 以使資料長度對齊 2 的倍數。

下面是一個 BI_RLE4 的例子：

03 11 05 02 00 05 01 23 10 00 02 22 00 02 05 01 02 13 00 00 09 10 00 01

這些資料可解讀為：

壓縮資料	解壓縮之後的資料
03 11	1 1 1
05 02	0 2 0 2 0
00 05 01 23 10 00	0 1 2 3 1（最後的 0 00 是為了 word-aligned 才補上的）
02 22	2 2
00 02 05 01	從目前位置右移 5 像素之後，向下移一列
02 13	1 3
00 00	此列結束
09 10	1 0 1 0 1 0 1 0 1
00 01	此點陣圖結束

上述資料的圖形如下：

Bitfileds (BI_BITFIELDS)
只有當「Bit Per Pixel」欄位的數值為 16 或 32 時，才會使用 BI_BITFIELDS 這種格式。
使用 BI_BITFIELDS 時，點陣圖檔中原本的調色盤位置會被三個 DWORD 佔據，
分別代表 R、G、B 三個顏色分量的遮罩（mask）。
例如：
1. Bit_Per_Pixel = 16, Compression = BI_RGB（無壓縮）,
  則每個像素的 16 位元之中：
  最低 5 位元表示藍色分量，
  中間 5 位元表示綠色分量，
  接著的高 5 位元則是紅色分量，
  最高的 1 位元保留不使用。
  此格式即為 RGB555 格式。
2. Bit_Per_Pixel = 16, Compression = BI_BITFIELDS,
  紅、綠、藍的 mask 分別為 0xF800, 0x07E0, 0x001F,
  則每個像素的 16 位元之中：
  最低 5 位元表示藍色分量，
  中間 6 位元表示綠色分量，
  最高 5 位元則是紅色分量，
  此格式即為 RGB565 格式。

【註７】若沒有壓縮（Compression 欄位為 0），則此欄數值可設為 0。
　　　　（我發現許多繪圖軟體根本不看此欄數值，隨便填寫也無所謂，圖檔仍可正常開啟）

【註８】若要換算為 dpi，則將此欄數值要除以39.37（吋/公尺）
　　　　例如，此欄數值若為 2834 (pixels per meter),
　　　　則 2834 ÷ 39.37 = 72 (pixels per inch) = 72 dpi

【註９】此欄表示圖檔實際使用的顏色數目，若數值為 0，表示使用所有調色盤顏色。
　　　　如果此欄數值並非「可用顏色的最大值」或者「零」，則需注意調色盤尺寸的計算。
　　　　例如，在 4 bpp bitmap 中，調色盤預設尺寸應是 16*4 bytes，
　　　　但若 Used Color 欄位數值並非 16 或 0，則調色盤尺寸應是 Used_Color_Number * 4 (bytes)。

【註10】當此欄的值等於「顏色數」或者為 0 時，表示所有顏色都一樣重要。

【註11】緊跟在調色盤之後的就是點陣圖資料陣列。
　　　　每一掃描列的長度取決於圖檔的寬度及顏色深度（Color Depth），
　　　　但是每一掃描列的長度必需是 4 byte 的倍數（DWORD-aligned）！
　　　　正常的點陣圖掃描列是由底向上儲存的：
　　　　陣列中的第一個 byte 表示全圖左下角的像素，而最後一個 byte 則表示全圖右上角的像素。
　　　　但如果是正向掃描（Height 欄位為負值），則掃描方向則是由上而下。

...
read more

消息來源

2008年1月27日星期日

[+/-] : [教學] Programming 8: "The Blacksheep Story Part II"

張貼者： MashiMaro 於星期日, 1月 27, 2008 0 意見

題目網址

題目大意：

給定一地圖，由起點出發，將地圖上所有星號走過一遍，再到終點。

星號上有兩個數值，分別為撿起來時的cost，與之後每一步增加的cost，啟始cost為1。

要求cost最少的路線。

ex. 如下圖，由START開始，往下走兩格(cost 2)，撿起星號(cost 3)，再往右走兩格(cost 10，因每步cost由1增加成5)，撿起星號(cost 7)，最後往上走兩格到END(cost (1+4+8)*2 = 26)。總共cost為48，是最佳解。

解法：

由於不限時間，直接使用暴力破解。

將圖上的點作順序排列(permutation)，並一一嘗試所花費的cost，取出最小值。

以下程式以 Ruby 執行：


# Author      : mashimaro
# Last Modify : 2008/01/27

$MAP = [
'0000000000000000E0',
'011111111111111111',
'000000000000F01000',
'00010000000010101H',
'000100000000001011',
'0I0100010000101000',
'000100010000001001',
'00010001000101001A',
'000000010001s0010e',
'000100010000111000',
'000100000000010000',
'00010100C000100000',
'000001000001000000',
'000001110010000000',
'000100000100010001',
'0111000010001D1G1B',
'00J101100101000100',
'000100000000000000'
];

$COST = [1, 2, 3, 7, 7, 8, 9, 9, 19, 97];

def calculate_path_len(arrDouble, x, y, val)
if($MAP[x][y].chr != '1' && arrDouble[x][y] > val)
  arrDouble[x][y] = val;
  #up
  arrDouble = calculate_path_len(arrDouble, x - 1, y, val + 1) if(x > 0);
  #down
  arrDouble = calculate_path_len(arrDouble, x + 1, y, val + 1) if(x < 17);
  #left
  arrDouble = calculate_path_len(arrDouble, x, y - 1, val + 1) if(y > 0);
  #right
  arrDouble = calculate_path_len(arrDouble, x, y + 1, val + 1) if(y < 17);
end
#if($MAP[x][y])
#puts $MAP;
arrDouble;
end


pathArray = Array.new(11){Array.new(12)};

i = 0;

for s in ['s', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
j = 0;
$MAP.each { |str|
if(str.index(s))
  #puts str + ' ' + str.index(s).to_s;
  arrDouble = Array.new(18){Array.new(18, 99)};
  arrDouble = calculate_path_len(arrDouble, j, str.index(s), 0);

  #output arrDouble
  if(1 == 0)
   x = 0;
   while(x < 18)
    y = 0;
    while(y < 18)
     print arrDouble[x][y].to_s + ' ';
     y = y + 1;
    end
    puts ;
    x = x + 1;
   end
 end

 #calculate pathArray
 m = 0;
 for tmp_s in ['s', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'e']
  n = 0;
  $MAP.each { |tmp_str|
   if(tmp_str.index(tmp_s))
    pathArray[i][m] = arrDouble[n][tmp_str.index(tmp_s)];
    break;
   end
   n = n + 1;
  }
  m = m + 1;
 end
  
  
 break;
end
j = j + 1;
}

i = i + 1;
puts ;
puts ;
end

#output pathArray
if(1 == 1)
x = 0;
while(x < 11)
y = 0;
while(y < 12)
 print pathArray[x][y].to_s + ' ';
 y = y + 1;
end
puts ;
x = x + 1;
end
end

pick_cost = 1+2+5+7+20+15+9+17+35+89;

min_cost = 9999999;

indexArray = [1,2,3,4,5,6,7,8,9,10];

for i1 in indexArray
indexArray.delete(i1);
tmp_cost1 = pick_cost + pathArray[0][i1];
cost1 = 1 + $COST[i1 - 1];
for i2 in indexArray
indexArray.delete(i2);
tmp_cost2 = tmp_cost1 + pathArray[i1][i2] * cost1;
cost2 = cost1 + $COST[i2 - 1];
for i3 in indexArray
 indexArray.delete(i3);
 tmp_cost3 = tmp_cost2 + pathArray[i2][i3] * cost2;
 cost3 = cost2 + $COST[i3 - 1];
 for i4 in indexArray
  indexArray.delete(i4);
  tmp_cost4 = tmp_cost3 + pathArray[i3][i4] * cost3;
  cost4 = cost3 + $COST[i4 - 1];
  for i5 in indexArray
   indexArray.delete(i5);
   tmp_cost5 = tmp_cost4 + pathArray[i4][i5] * cost4;
   cost5 = cost4 + $COST[i5 - 1];
   for i6 in indexArray
    indexArray.delete(i6);
    tmp_cost6 = tmp_cost5 + pathArray[i5][i6] * cost5;
    cost6 = cost5 + $COST[i6 - 1];
    for i7 in indexArray
     break if(min_cost <= tmp_cost6);
     indexArray.delete(i7);
     tmp_cost7 = tmp_cost6 + pathArray[i6][i7] * cost6;
     cost7 = cost6 + $COST[i7 - 1];
     for i8 in indexArray
      break if(min_cost <= tmp_cost7);
      indexArray.delete(i8);
      tmp_cost8 = tmp_cost7 + pathArray[i7][i8] * cost7;
      cost8 = cost7 + $COST[i8 - 1];
      for i9 in indexArray
       #puts 'start->'+i1.to_s+'->'+i2.to_s+'->'+i3.to_s+'->'+i4.to_s+'->'+i5.to_s+'->'+i6.to_s+'->'+i7.to_s+'->'+i8.to_s+'->'+i9.to_s+'->'+indexArray[0].to_s+'->end';
       break if(min_cost <= tmp_cost8);
       indexArray.delete(i9);
       tmp_cost9 = tmp_cost8 + pathArray[i8][i9] * cost8;
       cost9 = cost8 + $COST[i9 - 1];
       tmp_cost10 = tmp_cost9 + pathArray[i9][indexArray[0]] * cost9;
       cost10 = cost9 + $COST[indexArray[0] - 1];
       tmp_cost = tmp_cost10 + pathArray[indexArray[0]][11] * cost10;
       if(min_cost > tmp_cost)
         min_cost = tmp_cost;
         puts 'start->'+i1.to_s+'->'+i2.to_s+'->'+i3.to_s+'->'+i4.to_s+'->'+i5.to_s+'->'+i6.to_s+'->'+i7.to_s+'->'+i8.to_s+'->'+i9.to_s+'->'+indexArray[0].to_s+'->end';
         puts min_cost;
       end
       indexArray.push(i9);
       indexArray.sort!;
      end
      indexArray.push(i8);
      indexArray.sort!;
     end
     indexArray.push(i7);
     indexArray.sort!;
    end
    indexArray.push(i6);
    indexArray.sort!;
   end
   indexArray.push(i5);
   indexArray.sort!;
  end
  indexArray.push(i4);
  indexArray.sort!;
 end
 indexArray.push(i3);
 indexArray.sort!;
end
indexArray.push(i2);
indexArray.sort!;
end
indexArray.push(i1);
indexArray.sort!;
end

puts min_cost;

...
read more

消息來源

2008年1月25日星期五

[+/-] : [Ruby] 圖形介面(GUI by wxruby) & 圖片處理(RMagick)

張貼者： MashiMaro 於星期五, 1月 25, 2008 0 意見

gem install wxruby

#gem install RMagick
Installing RMagick for Ruby 1.8.4 on Windows XP
在Windows XP直接 gem install RMagick 會產生錯誤，解決方法：

1. 到 http://rubyforge.org/projects/rmagick/ 直接下載 rmagick-win32 最新版 (ex.RMagick-2.0.0-ImageMagick-6.3.7-8-Q8.zip)

2. 解壓縮後，命令列切換到解壓縮目錄下執行 local gem install (gem install rmagick --local)

3. 安裝DLL檔，執行解壓縮目錄下dll.exe (ex.ImageMagick-6.3.7-8-Q8-windows-dll.exe)

4. 可到 C:\ruby\lib\ruby\gems\1.8\gems\rmagick-2.0.0-win32\examples 下測試是否安裝成功


require 'wx'
require 'RMagick'
include Magick
include Wx

class MyFrame < Wx::Frame
def initialize(title)
super(nil, -1, title, Point.new(-1,1), Size.new(500,500))
evt_paint { on_paint }

img_file = File.join( File.dirname(__FILE__), 'tmp_new.bmp')
# first load the image into an Image object
image = Wx::Image.new(img_file)
# then create a Bitmap suitable for drawing
@bitmap = Wx::Bitmap.new(image)
end

def on_paint
paint do | dc |
  dc.clear
  dc.draw_bitmap(@bitmap, 0, 0, false)
end
end
end

class ImagesApp < Wx::App
def on_init
frame = MyFrame.new('Title')
frame.show
end
end

a = ImagesApp.new;
a.main_loop();

...
read more

消息來源

2008年1月23日星期三

[+/-] : [教學] 改變Ubuntu 6.x JAVA 預設版本1.4 -> 1.6

張貼者： MashiMaro 於星期三, 1月 23, 2008 0 意見

2008年1月22日星期二

[+/-] : [教學] 解決在ubuntu 7.10下不能將網卡D-link DWL-G650 不能設成監聽模式

張貼者： MashiMaro 於星期二, 1月 22, 2008 0 意見

2008年1月4日星期五

[+/-] : [教學] 在 Ubuntu7.10 安裝 GW-US54GXS USB無線網卡

張貼者： MashiMaro 於星期五, 1月 04, 2008 0 意見

2008年1月2日星期三

[+/-] : [教學] Programming 9: "The Blacksheep Story Part III"

張貼者： MashiMaro 於星期三, 1月 02, 2008 0 意見

題目網址

題目大意：

求出最常共同序列(Longest Common Sequence)

CATCACGCACGCGCCGTTAAGCAACAGATACCAGATGTCGTTTTGGTTAGTGGATTTAGCAGTATGCCTAACAGGACGCAAAACGGAGGGCTATCCGGCGAGGGTCAGCGGGACCCTATACGACCCTCGGAATGTCTTTGTTTACGCACTAAATGAAGTC
ATCGATACTTGGTGATACGTGCCTACGGCACTTCACGCTAGTCACGACTCCCTCTATGCCCCCACCGTATATATCCAGCCAGTCGTGATTAGAGTAATCAGTGGGCTGTACTGTGATGCATACCACTCCCTCACCACGCACCGAGGGCTTTGACGAGGATTTGATTCGCTATGAGAGTTGCGCCCTTTTGCCAAGATTACCACGCTTACTCACGGCCGGCCGACGATGAAATGCACGCGCGGGGGCTCAGCGAGCTGCAAACAGATGTACTATTAAGGCATGATTAAAGATGTAATATAA

解法：

短的可以用畫的...
長的還是讓程式跑吧XD

以下程式以 Ruby 執行

1.遞迴(很慢...)

# Author      : mashimaro
# Last Modify : 2008/01/02

def lcs(str1,str2)
 if(str1.length == 0 || str2.length == 0)
  ''
 else
  if(str1[-1..-1] == str2[-1..-1])
   lcs(str1[0..-2],str2[0..-2]) + str1[-1..-1]
  else
   a=lcs(str1[0..-2],str2)
   b=lcs(str1,str2[0..-2])
   if(a.length>=b.length)
    a
   else
    b
   end
  end
 end
end

str2='ATCACGAATTGGGCAATAATGCTACTTGAGACGTTTGAGCCCTCCGTCGGGCGCCTGTGGATGCCGGATTGGCATCCCGCAACAGAACGCTCTTAGTCCCCGCCTTCGGAGAATATGCCAAGTCGTAAGAGGCGGACGTGCATCACGCACGCGCCGTTAAGCAACAGATACCAGATGTCGTTTTGGTTAGTGGATTTAGCAGTATGCCTAACAGGACGCAAAACGGAGGGCTATCCGGCGAGGGTCAGCGGGACCCTATACGACCCTCGGAATGTCTTTGTTTACGCACTAAATGAAGTC'
str1='ATCGATACTTGGTGATACGTGCCTACGGCACTTCACGCTAGTCACGACTCCCTCTATGCCCCCACCGTATATATCCAGCCAGTCGTGATTAGAGTAATCAGTGGGCTGTACTGTGATGCATACCACTCCCTCACCACGCACCGAGGGCTTTGACGAGGATTTGATTCGCTATGAGAGTTGCGCCCTTTTGCCAAGATTACCACGCTTACTCACGGCCGGCCGACGATGAAATGCACGCGCGGGGGCTCAGCGAGCTGCAAACAGATGTACTATTAAGGCATGATTAAAGATGTAATATAA'
str1=gets
str1.sub!("\n",'')
str2=gets
str2.sub!("\n",'')
puts lcs(str1, str2)

2.展開


# Author      : mashimaro
# Last Modify : 2008/01/02

str2='ATCACGAATTGGGCAATAATGCTACTTGAGACGTTTGAGCCCTCCGTCGGGCGCCTGTGGATGCCGGATTGGCATCCCGCAACAGAACGCTCTTAGTCCCCGCCTTCGGAGAATATGCCAAGTCGTAAGAGGCGGACGTGCATCACGCACGCGCCGTTAAGCAACAGATACCAGATGTCGTTTTGGTTAGTGGATTTAGCAGTATGCCTAACAGGACGCAAAACGGAGGGCTATCCGGCGAGGGTCAGCGGGACCCTATACGACCCTCGGAATGTCTTTGTTTACGCACTAAATGAAGTC'
str1='ATCGATACTTGGTGATACGTGCCTACGGCACTTCACGCTAGTCACGACTCCCTCTATGCCCCCACCGTATATATCCAGCCAGTCGTGATTAGAGTAATCAGTGGGCTGTACTGTGATGCATACCACTCCCTCACCACGCACCGAGGGCTTTGACGAGGATTTGATTCGCTATGAGAGTTGCGCCCTTTTGCCAAGATTACCACGCTTACTCACGGCCGGCCGACGATGAAATGCACGCGCGGGGGCTCAGCGAGCTGCAAACAGATGTACTATTAAGGCATGATTAAAGATGTAATATAA'
#str1='AAC'
#str2='ACAA'
#str1='CATGGCATG'
#str2='ATCATTCAT'
str1=gets
str1.sub!("\n",'')
str2=gets
str2.sub!("\n",'')

#puts str1,str2;

arr = Array.new(str2.length){Array.new(str1.length, 0)};

#arr = Array.new(2,Array.new(3, 1));#不能用Orz

x = 0;
str2.split(//).each { |s2|

 y = 0;

 #puts "\n"+s2;

 str1.split(//).each { |s1|

  #print s1;

  if(s1 == s2)

   if(x > 0 && y > 0)
    arr[x][y] = arr[x - 1][y - 1] + 1;
   else
    arr[x][y] = 1;
   end

   (x + 1).upto(str2.length-1) { |tmp_x|
    break if(arr[x][y] <= arr[tmp_x][y]);
    arr[tmp_x][y] = arr[x][y];
   }


   (y + 1).upto(str1.length-1) { |tmp_y|
    break if(arr[x][y] <= arr[x][tmp_y]);
    arr[x][tmp_y] = arr[x][y];
   }

   (y + 1).upto(str1.length-1) { |tmp_y|

    break if(x + 1 >= str2.length || arr[x][y] <= arr[x + 1][tmp_y]);

    (x + 1).upto(str2.length-1) { |tmp_x|

     break if(arr[x][y] <= arr[tmp_x][tmp_y]);

     arr[tmp_x][tmp_y] = arr[x][y];
    }
   }

  end

  y = y + 1;
 }
 x = x + 1;
}

  print ' ';
  str1.split(//).each { |c|
   print '  ' + c;
  }
  puts '';

  0.upto(str2.length-1) { |a|
   print str2[a..a];
   0.upto(str1.length-1) { |b|
    print ' ' * (3 - arr[a][b].to_s.length) + arr[a][b].to_s;
   }
   puts '';
  }

x = str2.length - 1;
y = str1.length - 1;

path = '';

puts 'arr[x][y] = ' + arr[x][y].to_s;
while(1)
 while(y > 0 && arr[x][y-1] == arr[x][y])
  y = y - 1;
 end
 while(x > 0 && arr[x-1][y] == arr[x][y])
  x = x - 1;
 end
 path = str1[y..y] + path;

 break if(arr[x][y] == 1);

 x = x - 1;
 y = y - 1;
end

puts path;

...
read more

消息來源

[+/-] : [教學] Programming 6: "just another calculation"

張貼者： MashiMaro 於星期三, 1月 02, 2008 0 意見

題目網址

時間限制：1.5秒

題目大意：

給定一等式，算出結果。

Ex. The equation is "[x]29=-[1REa]47+[6D4e]41-[1A8903]14+[HDI1]21-[5SKX]53+[4W77]59+[7NS3]48+[5FSE]29-[1aUa]52"

解法：

基底轉換運算。

以下程式以 Ruby 執行

# Author      : mashimaro
# Last Modify : 2008/01/02

require 'net/http'
require 'net/https'

host = 'www.bright-shadows.net'
path = '/challenges/programming/calculate2/tryout.php'
cookie = 'PHPSESSID=************************************'

http = Net::HTTP.new(host, 80)
#http.use_ssl = true
headers = {
  'Cookie' => cookie,
#  'Referer' => 'http://profil.wp.pl/login.html',
#  'Content-Type' => 'application/x-www-form-urlencoded'
}

resp, data = http.get(path, headers);

data.sub!('The equation is "', '');
data.sub!('"', '');
data.sub!('=[', '=+[');

puts data;

bases = [];
data.scan(/\][0-9]+/).each { |tmp_base|
 bases.push(tmp_base[1..-1].to_i);
}
signs = ['+'];
data.scan(/[+-]\[/).each { |tmp_sign|
 signs.push(tmp_sign[0..0]);
}
nums = [];
data.scan(/\[[0-9a-zA-Z]+\]/).each { |tmp_num|
 nums.push(tmp_num[1..-2]);
}

#puts bases;
#puts signs;
#puts nums;

chrs = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';

i = 1;
sum = 0;

while(i < bases.length)

 num = 0;
 nums[i].split(//).each { |c|
  num = num * bases[i] + (chrs.index(c));
 }

 num = -num if(signs[i] == '-');

 puts signs[i]+'['+nums[i]+']_'+bases[i].to_s+"\t"+num.to_s;

 sum = sum + num;

 i = i + 1;

end

tmp = sum;
(tmp = -tmp) if(tmp < 0);

result = '';

while(tmp > 0)
 x = tmp % bases[0];
 result = chrs[x..x] + result;
 tmp = tmp / bases[0];
end

(result = '-' + result) if(sum < 0);

ret_path = '/challenges/programming/calculate2/solution.php?solution=' + result;

resp, data = http.get(ret_path, headers);

puts data;

...
read more

消息來源

[+/-] : [教學] Programming 13: "Peano Jordan"

張貼者： MashiMaro 於星期三, 1月 02, 2008 0 意見

題目網址

時間限制：4秒

題目大意：

給定一函數p(x)、區間[x1,x2]，求出以"中位數"為基、每0.01單位分割的面積積分。

解法：

利用 Ruby eval函數的特性，做好字串處理後直接交給它處理。
要注意的是必須加入.to_f讓 Ruby 知道是用float進行運算。

以下程式以 Ruby 執行：


# Author      : mashimaro
# Last Modify : 2008/01/02

require 'digest/md5'
require 'net/http'
require 'net/https'

host = 'www.bright-shadows.net'
path = '/challenges/programming/peanojordan/tryout.php'
cookie = 'PHPSESSID=**********************************'

http = Net::HTTP.new(host, 80)
#http.use_ssl = true
headers = {
  'Cookie' => cookie,
#  'Referer' => 'http://profil.wp.pl/login.html',
#  'Content-Type' => 'application/x-www-form-urlencoded'
}

while(true)

 resp, data = http.get(path, headers);

 data.sub!('<pre>', '');
 data.sub!('</pre>', '');

 lines = data.split('<br>');

 exp = lines[0].sub('p(x) = ', '').gsub('/','.to_f/').gsub('^','**');
 a, b = lines[2].scan(/[\-0-9]+/);

 int_1 = a.to_i;
 int_2 = b.to_i;

 puts '';
 puts lines[0];
 puts '';
 puts lines[2];
 puts '';
 puts exp;
 #puts int_1, int_2;
 puts '';

 break if(exp[-1..-1].to_i < 6);

end

sum = 0;
int_1 = int_1 + 0.005;

while(int_1 < int_2)

 sum = sum + eval(exp.gsub('x','('+int_1.to_s+')'));
 puts sum;

 int_1 = int_1 + 0.01;

end

puts (sum * 0.01).round;

digest = Digest::MD5.hexdigest((sum * 0.01).round.to_s);
ret_path = '/challenges/programming/peanojordan/solution.php?solution=' + digest;

resp, data = http.get(ret_path, headers);

puts data;

...
read more

消息來源

[+/-] : Ruby的eval函式 - 最簡單的metaprogramming

張貼者： MashiMaro 於星期三, 1月 02, 2008 0 意見

2008年1月1日星期二

[+/-] : [教學] Programming 12: "Looping"

張貼者： MashiMaro 於星期二, 1月 01, 2008 0 意見

題目網址

時間限制：3秒

題目大意：

有一個5x5方陣，1 <= a ~ y <= 9，已知橫排(5 Rows)、縱列(5 Columns)、對角線(2 Diagonals)之各別總和，求出符合這些條件的 a ~ y。


+-Square------+-Rows----------------+-Cols----------------+-Diagonals----+
|  a b c d e  |  Row 1 = a+b+c+d+e  |  Col 1 = a+f+k+p+u  |  Diagonal 1  |
|  f g h i j  |  Row 2 = f+g+h+i+j  |  Col 2 = b+g+l+q+v  |  = a+g+m+s+y |
|  k l m n o  |  Row 3 = k+l+m+n+o  |  Col 3 = c+h+m+r+w  |              |
|  p q r s t  |  Row 4 = p+q+r+s+t  |  Col 4 = d+i+n+s+x  |  Diagonal 2  |
|  u v w x y  |  Row 5 = u+v+w+x+y  |  Col 5 = e+j+o+t+y  |  = u+q+m+i+e |
+-------------+---------------------+---------------------+--------------+

解法：

以漩渦方式由外而內(a->e->y->u->f->i) iteration 猜測，有時候可能會超過3秒，只要重新執行即可。

以下程式使用 Ruby 執行。


# Author      : mashimaro
# Last Modify : 2008/01/01

require 'net/http'
require 'net/https'

host = 'www.bright-shadows.net'
path = '/challenges/programming/looping/tryout.php'
cookie = 'PHPSESSID=**********************************'

http = Net::HTTP.new(host, 80)
#http.use_ssl = true
headers = {
'Cookie' => cookie,
#  'Referer' => 'http://profil.wp.pl/login.html',
#  'Content-Type' => 'application/x-www-form-urlencoded'
}

resp, data = http.get(path, headers);

data.sub!('<pre>', '');
data.sub!('</pre>', '');

arr = [];

data.split('<br />').each { |line|
 if(line[0..2]=='Sum')
  arr.push(line[-2..-1]);
  puts line[-2..-1];
 end
}

puts '';
# puts arr[0];
# puts arr[1];
# puts arr[2];
# puts arr[3];
# puts arr[4];
# puts arr[5];
# puts arr[6];
# puts arr[7];
# puts arr[8];
# puts arr[9];
# puts arr[10];
# puts arr[11];

[1,2,3,4,5,6,7,8,9].each { |a|
 [1,2,3,4,5,6,7,8,9].each { |b|
  [1,2,3,4,5,6,7,8,9].each { |c|
   [1,2,3,4,5,6,7,8,9].each { |d|
    e = arr[0].to_i - a - b - c - d;
    break if(e < 1);
    next  if(e > 9);

    [1,2,3,4,5,6,7,8,9].each { |j|
     [1,2,3,4,5,6,7,8,9].each { |o|
      [1,2,3,4,5,6,7,8,9].each { |t|
       y = arr[9].to_i - e - j - o - t;
       break if(y < 1);
       next  if(y > 9);

        [1,2,3,4,5,6,7,8,9].each { |x|
         [1,2,3,4,5,6,7,8,9].each { |w|
          [1,2,3,4,5,6,7,8,9].each { |v|
           u = arr[4].to_i - v - w - x - y;
           break if(u < 1);
           next  if(u > 9);

            [1,2,3,4,5,6,7,8,9].each { |p|
             [1,2,3,4,5,6,7,8,9].each { |k|
              f = arr[5].to_i - a - k - p - u;
              break if(f < 1);
              next  if(f > 9);

              [1,2,3,4,5,6,7,8,9].each { |g|
               [1,2,3,4,5,6,7,8,9].each { |h|
                i = arr[1].to_i - f - g - h - j;
                break if(i < 1);
                next  if(i > 9);

                [1,2,3,4,5,6,7,8,9].each { |m|
                 q = arr[11].to_i - e - i - m - u;
                 break if(q < 1);
                 next  if(q > 9);
                 r = arr[7].to_i - c - h - m - w;
                 break if(r < 1);
                 next  if(r > 9);
                 s = arr[10].to_i - a - g - m - y;
                 break if(s < 1);
                 next  if(s > 9);
                 next  if(s != arr[3].to_i - p - q - r - t);

                 l = arr[6].to_i - b - g - q - v;
                 next  if(l < 1 || l > 9);
                 n = arr[8].to_i - d - i - s - x;
                 next  if(n < 1 || n > 9);
                 next  if(n != arr[2].to_i - k - l - m - o);

                 arr2=[];
                 puts [].push(a,b,c,d,e).join(' ');
                 puts [].push(f,g,h,i,j).join(' ');
                 puts [].push(k,l,m,n,o).join(' ');
                 puts [].push(p,q,r,s,t).join(' ');
                 puts [].push(u,v,w,x,y).join(' ');
                 puts '';

                 ret_path = [].push('http://www.bright-shadows.net/challenges/programming/looping/solution.php?solution=',a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y).join('');

                 puts ret_path;
                 resp, data = http.get(ret_path, headers);
                 puts data;

                 exit(0);
                }

               }
              }

             }
            }

           }
          }
         }

       }
      }
     }

   }
  }
 }
}

...
read more

消息來源

[+/-] : [Diary] 2008 Happy New Year !!!

張貼者： MashiMaro 於星期二, 1月 01, 2008 0 意見

訂閱：文章 (Atom)

MashiMaro's Blog

Archives

BloggerAds

WHO'S

About Me

2008年11月26日 星期三

[+/-] : [教學] CrackIt 16: "Get the number!"

2008年7月6日 星期日

[+/-] : [教學] Exploit 14: "Analyse this III!"

2008年7月5日 星期六

[+/-] : [教學] Java-Applet 5: "Defeat Me"

2008年7月4日 星期五

[+/-] : [教學] Exploit 17: "RHC 6"

2008年7月2日 星期三

[+/-] : VMware 中安裝Ubuntu 8.04 後滑鼠滾輪無作用

2008年6月29日 星期日

[+/-] : Youtube or Flash 沒聲音

2008年5月4日 星期日

[+/-] : [BG] Shear Panic 羊羊危機

2008年4月25日 星期五

[+/-] : [BG] Saboteur 矮人礦坑

2008年3月25日 星期二

[+/-] : [Diary] Way back into love (重新找到愛)

2008年3月24日 星期一

[+/-] : [XD] 手太長.....

2008年3月22日 星期六

[+/-] : [Diary]星光三 3/21 徐佳瑩 出口

2008年3月11日 星期二

[+/-] : 演算法課本題目 (Exercise 4.1-5) : 求 Big-O

[+/-] : [Diary] 星光三首度25分！

2008年3月4日 星期二

[+/-] : 好句共享

2008年3月2日 星期日

[+/-] : [XD] 白痴妹第二發XD

2008年2月29日 星期五

[+/-] : PHP從網頁傳遞變數的改變

2008年1月28日 星期一

[+/-] : [Format]BMP

2008年1月27日 星期日

[+/-] : [教學] Programming 8: "The Blacksheep Story Part II"

2008年1月25日 星期五

[+/-] : [Ruby] 圖形介面(GUI by wxruby) & 圖片處理(RMagick)

2008年1月23日 星期三

[+/-] : [教學] 改變Ubuntu 6.x JAVA 預設版本1.4 -> 1.6

2008年1月22日 星期二

[+/-] : [教學] 解決在ubuntu 7.10下不能將網卡D-link DWL-G650 不能設成監聽模式

2008年1月4日 星期五

[+/-] : [教學] 在 Ubuntu7.10 安裝 GW-US54GXS USB無線網卡

2008年1月2日 星期三

[+/-] : [教學] Programming 9: "The Blacksheep Story Part III"

[+/-] : [教學] Programming 6: "just another calculation"

[+/-] : [教學] Programming 13: "Peano Jordan"

[+/-] : Ruby的eval函式 - 最簡單的metaprogramming

2008年1月1日 星期二

[+/-] : [教學] Programming 12: "Looping"

[+/-] : [Diary] 2008 Happy New Year !!!

Labels

Google Search

常逛的網誌

2008年11月26日星期三

2008年7月6日星期日

2008年7月5日星期六

2008年7月4日星期五

2008年7月2日星期三

2008年6月29日星期日

2008年5月4日星期日

2008年4月25日星期五

2008年3月25日星期二

2008年3月24日星期一

2008年3月22日星期六

[+/-] : [Diary]星光三 3/21 徐佳瑩出口

2008年3月11日星期二

2008年3月4日星期二

2008年3月2日星期日

2008年2月29日星期五

2008年1月28日星期一

2008年1月27日星期日

2008年1月25日星期五

2008年1月23日星期三

2008年1月22日星期二

2008年1月4日星期五

2008年1月2日星期三

2008年1月1日星期二