剛開始學寫程式的時候,都會聽過,程序等於算法加數據結構。但因為我不是CS出生,而是Finance,一開始看到這句話也沒什麼感覺,直到我寫的東西越來越多,而且發現實現一個功能,很多人的寫法都不一樣,而且自己的常常是又長又沒效率,於是就決定開始關注算法了。
可以練習算法的地方
- TopCoder – 來自美國,常常舉辦比賽,有Client進行算法的驗證(Judge)和進行比賽。
每次比賽的題目也都會有留下算法題目給大家看。 - CodeForces – 來自俄羅斯(介面支持俄羅斯語和英文),基於Web的服務,每週都有算法比賽,因為他支持PHP的Judge,所以我主要都是在codeForces上玩….畢竟我目前只會PHP和Objective-C。
也會留下每次比賽的算法題目,隨時可以看,也可以進行Judege.
上面有位來自俄羅斯的Google員工Peter,聽說為人低調又非常厲害。 - 其實各個地區都會有很多學校有算法題目的收集和線上Judge的功能,網上搜索還滿多的。
CFTool-PHP小爬蟲,抓取CodeForces的題目
寫這個工具的一些情況:
- 選擇CodeForces,因為它支持PHP的Judge,我才能做題目。
- 用PHP寫爬蟲,因為PHP支持本地讀寫文件,我可以通過正則表達式,抓取我要的部分,然後在本地保存成htm文件,方便瀏覽(一開始我打算寫個iOS的客戶端用UIWebView來瀏覽)。
- CodeForces有API,但是API沒有提供題目的正文,只是題目的ID、Index、題目名字之類的。
CFTool的運行方式
- CodeForces每個題目都有個固定的網誌格式例如:http://codeforces.com/problemset/problem/507/E
數字應該就是第幾次的比賽,英文字母表示難度的不同(應該吧…)。 - 通過CodeForces的API下載他的題目列表,
- 讀出所有的題目ID,Index,根據固定網址/ID/Index就可以讀取所有題目的html文件了
- 利用正則表達式(RegularExpress)抓取自己要的內容,包括正文和圖片在本地保存。
CFTool的實現
首先,通過他的API下載CodeForces的題目列表 (http://codeforces.com/api/problemset.problems)
(當然也可以利用工具裡面的isNeedUpdate()去下….哈
CFProblems是一個類,裡面寫了些方法可能有尚未使用到的
- isNeedUpdate() -先判斷本地有沒有CFProblemsList.JSON這個文件,
存在則比較題目的數量是否相同。
不存在,則通過API地址下載。 - getProblemList()-就是下載CFProblemList.JSON
- getProblem()-就是根據ID和Index來瀏覽Problem的html,裡面就有具體抓取我要的正文方法。
- css文件我是手動下載的….每個題目用到的css文件相同,我放在Problems資料夾下(style.css)。
- 程序class CFProblems以外的內容是我自己的調用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
<?php //http://dev.devdon.com class CFproblems{ public $addressAPI; public $CFProblemsListName; function __construct(){ $this->addressAPI = "http://codeforces.com/api/problemset.problems"; $this->CFProblemsListName = "CFProblemsList.json"; } //compare localal problems list to CF API problems list amount. function isNeedUpdate(){ //check CFProblemList exists or not if(!file_exists($this->CFProblemsListName)){ echo "updating....\n"; $this->getCFProblemList(); }else{ //local problem list count $fpLoc = fopen($this->addressAPI, "r"); $contentLocal = ""; while(!feof($fpLoc)){ $contentLocal .= fgets($fpLoc); } fclose($fpLoc); $resultLoc = json_decode($contentLocal,ture); $problemsLocCount = count($resultLoc); //CF api problem list count $fpCF = fopen($this->addressAPI, "r"); $contentCF = ""; while(!feof($fpCF)){ $contentCF .= fgets($fpCF); } fclose($fpCF); $resultCF = json_decode($contentCF,ture); $CFProblems = $resultCF["result"]["problems"]; $problemsCFCount = count($CFProblems); if($problemsLocCount==$problemsCFCount){ echo "updating....\n"; $this->getCFProblemList(); }else{ echo "dont't need update"; } } } //use CF API to download problem list in JSON function getCFProblemList(){ $fp = fopen($this->addressAPI, "r"); $content = ""; while(!feof($fp)){ $content = fgets($fp); } fclose($fp); $content = json_decode($content,true); $CFProblems = $content["result"]["problems"]; $CFProblemsInJSON = json_encode($CFProblems); file_put_contents($this->CFProblemsListName, $CFProblemsInJSON); } function getProblem($number,$index){ $address = "http://codeforces.com/problemset/problem/".$number."/".$index; $fp = fopen($address, "r"); $content = ""; while(!feof($fp)){ $content .= fgets($fp); } fclose($fp); //problem $problemPattern = "/<div class=\"problem-statement\">([\s\S]*)<\/div><\/div>/"; preg_match($problemPattern, $content,$problemMatch); $problem = $problemMatch[1]; //img localization $imgPattern = "/<img class=\"[\S]*\" src=\"([\S]*)\" \/>/"; preg_match_all($imgPattern, $problem, $imageMatch); $imageURLArray = $imageMatch[1]; $imageNameLocArray = array(); if(count($imageURLArray)>0){ for($i=0;$i<count($imageURLArray);$i++){ $imageURL = $imageURLArray[$i]; $explodedArray = explode(".", $imageURL); $suffixPos = count($explodedArray)-1; $suffix = $explodedArray[$suffixPos]; $imageName = $number.$index."-".$i.".".$suffix; $imageNameLocArray[] = "images/".$imageName; $ch = curl_init($imageURL); $fp = fopen("problems/images/".$imageName, "w"); curl_setopt($ch, CURLOPT_FILE, $fp); curl_setopt($ch, CURLOPT_HEADER, 0); curl_exec($ch); curl_close($ch); fclose($fp); } } //use local img instead of codeForces img if(count($imageURLArray)>0){ for($j=0;$j<count($imageURLArray);$j++){ $imgNameCF = $imageURLArray[$j]; $imgNameLoc = $imageNameLocArray[$j]; $problem = str_replace($imgNameCF, $imgNameLoc, $problem); } } //write html document $problemFileName = $number.$index."."."html"; $fp = fopen("problems/".$problemFileName, "w"); fwrite($fp, "<html>\n<head>\n"); fwrite($fp, "<meta http-equiv=\"content-type\" content=\"text/html; charset=UTF-8\">\n"); fwrite($fp, "<link rel=\"stylesheet\" href=\"style.css\" type=\"text/css\" charset=\"utf-8\">\n"); fwrite($fp, "</head>\n<body>\n"); fwrite($fp, "<div class=\"problem-statement\">\n"); fwrite($fp, $problem."\n"); fwrite($fp, "</div>\n"); fwrite($fp, "</body>\n</html>\n"); fclose($fp); } } $api = new CFProblems; // 從CFProblemLst中取得題目的ID+Index $fp = fopen("CFProblemsList.json", "r"); $jsonFile = ""; while(!feof($fp)){ $jsonFile .= fgets($fp); } fclose($fp); $problems = json_decode($jsonFile,ture); $problemFileNames = array(); for($i = 0;$i<count($problems);$i++){ $problemFileNames[$i]["id"] = $problems[$i]["contestId"]; $problemFileNames[$i]["index"] = $problems[$i]["index"]; } //根據ID+Index開始抓題目 $api = new CFProblems; for($j=0;$j<count($problemFileNames);$j++){ $api->getProblem($problemFileNames[$j]["id"],$problemFileNames[$j]["index"]); } ?> |
CFTool的缺陷(我是邊學邊做所以沒完善…)
- 題目下載後沒有進行資料夾的劃分,以至於2000多個題目都放在一個資料夾裡面。
- 圖片和上面情況一樣,不過圖片沒那麼多。
- 一些手動的事情其實也可以寫到CFProblems這個類裡面,比如CSS的下載等。
- 少寫個功能,可以把這些功能結合起來,只要外部執行checkUpdate()然後就自動去判斷是否需要下載CSS檔、JSON檔案等等。
我沒有這麼做還有個原因,就是因為我沒來(懶)得(的)及(去)查PHP的多線程用法,如果每次一直行他就開始跑了…那要下好久阿=_________=…於是我乾脆手動設定要下載幾個這樣…
寫CFTool過程有上的網站
- 30分鐘學會正則表達式-讀到最後就會看到作者道歉,30分鐘根本學不完哈哈。
- w3school PHP FileSystem-其實我也不太會PHP ,所以邊做邊查。
有關PHP怎麼創建Class,怎麼調用Class方法之類的,我就是下載個有這功能的php檔案,然後依樣畫葫蘆就學好了,PHP很簡單…
最後,這篇文章只是我自己記錄用的,因為工具算是一次性的嘗試,所以我就…隨心一點了。
所有的代碼以及2000多個題目都放在GitHub上了。