Mindless Garden

Google Code Jam Practice problems 12-Apr-2008

2009-09-23T15:58:00.012+08:00

大部分的題目都有 Contest Analysis，所以就不記下解法了，只是這四題並沒有，就寫一下這樣。要留意的是這些題目並不是新的，早在 08 年的 4 月 12 日就公佈了。另外下面所題到的都是 C++ 語言。

1. Alien Numbers

難度最低的一題，就單純是不同進制的轉換。首先求得輸入字串的 10 進制值，然後再求目前進制下每個位的數值就好。本來希望找出直接轉換的快速方法，不過似乎並沒有那麼好康的…事實上直接寫也並不是那麼複雜，非常簡單的一題。

2. Always Turn Left

典型的 2D 坐標移動問題。留意一下答案要求的格式，大概能想到可以用 bitwise OR 去計算答案。至於移動方面，空間上的移動最普遍的做法是用 dx, dy 兩個 array 來表示上下左右四種移動方式的座標偏移，方向的改變可以用 [(d+1)%4] 來表達，只是由於題目要求的 output 那四個方向並不是順序的，需要多設一個 mapping array。而地圖的資料，最直觀就是用 map 加上 pair 作為坐標去存放資料。

想好資料的存放方法後就是實作分析 input 的部分，應該不會太難，值得注意的主要是由於並沒有給予地圖的大小，所以坐標會出現負數，也需要一些變數來讓你在最後可以算出地圖的 size 就是。最後就只是把地圖以十六進制數的形式顯示，也算是簡單的題目。

3. Egg Drop

這一題的數學成分比較重，而且 input limit 也有一些 tricky 的地方。如果沒有 B 的話其實問題就會簡單得多，那麼現在有 B 要怎麼解題呢？首先怎麼丟蛋並不重要，重要的是如何設公式去找出 F_max。

在已知 D, B 的情況下，最大的 F 假如是 f(D, B)，任意挑一層來丟蛋，假如蛋破了就得往下試，下面的最大層數應該是 f(D-1, B-1)；假如蛋沒破，那上面的層數是 f(D-1, B)，所以 f(D, B) = f(D-1, B) + f(D-1, B-1) + 1。為甚麼加 1 應該可以想到。

找出了公式大概就能弄出 lookup table，D_min 和 B_min也就能查表求出，搞定。但看一下 large input limit，D 和 B 都可以高達 2,000,000,000，要弄那麼大的表似乎不太可能。留意一下公式的數值，就會知道其實 B 不可能比 32 大，因為當 B > D，其實結果跟 B = D 一樣。而當 B = D 時，結果就是 2^D-1，所以 D 比 32 大的就可以 output -1 了。所以其實該表的深度是有限的。然而 D 還是可以很大，所以把表格 run 出來看一下，就會發覺其實 f(D, B) 本身就只是單純的 sum of nCr。而且當 D > 32 時，數值會增長很快(意思就是很多 -1)，事實上當 D 在 600 多時，B 就只有在 3 或以下才不會出現 -1。所以只需要建立一張 600 x 33 (33是因為 0 那一行不用)左右的表就夠用了。當 D 更大時，就用公式直接求值即可。公式就自己找找吧，B=1,2,3 時其實並不複雜，可以自己手動算出來。由於 B 比較小，查找比較容易，linear search 也沒差，D 的話就需要 binary search 這樣。

4. Shopping Plan

最難的一題，事實上我也不會做Orz。這比普通的 shortest path 問題複雜多了，而且購買 ABCD 的最佳路徑並不一定包含 ABC 的最佳路徑，所以只能把所有可能都跑一遍。

首先問題是如何去處理 input。Shopping list 我看大多都是使用 bit mask 去做，因此一開始時，所有東西還沒買的 mask 是 2<<15 - 1 (也就是 15 個 1)。至於哪一件是 Perishable 也可以用一個 mask 去搞定。價格和 store 的座標用 array 就 ok 了。另外 home 也算是一個 store 這樣。有些人用 complex 去作為座標，好處是計算距離比較簡單，不過普通的弄個 function 也不是很難就是了。

資料存好後，實作部分就是 recursive 的計算出最低的 cost，其中的模擬購物部分一般都涉及 bitwise 的運算，這些我以前都很少用到，算是學到不少東西。而基於 large input 的資料量，可以看出不同解法對 run time 有很顯著的影響。一個參賽者用最直觀的做法，就是硬幹的把每一個可能都 run 一次(每去一間店時，都把所有的店作為下一個目標這樣)，大概要 4min 才跑完。我看過比較快的大概只用 15-20sec 就搞定，這裡就提一下作法。

既然是 DP，也就是要用到 lookup table，A[1<<15][51]。前者是 list 後者是地點，這代表了要購買 list 上物品，而又身處某地點時的最佳 cost(包括回家，你也可以看成是由家出發)。由 1 到 1<<15 - 1 loop 下去(這代表考慮所有的組合)，再考慮所有的 store 作為起點這樣把 table 跑出來。而購買的要點是，先把非 perishable 的都買起來。到只剩下 perishable 的東西時，假如可以挑到一間店把所有 perishable 的東西都買起來，就計一下，假如不能，就放棄(把 cost 設到很大)。因此，A 這表裡的，第二個 index 是家那一點時所有值都是完整的路線 cost (即由家出發，再回到家)，差別只在於購物單的不同。

把所有組合考慮過後，就要考慮如何組合它們去得出最佳的 cost，而這個 merge 的作法就是省下最多運算的地方。設一個 B[1<<15] 的 array，B[i] 表示在要購買 list i 時的最佳 cost，我們要求的就是 1<<n-1(n 為物品數)。由 1 到 1<<15-1 的把每個 B[i] 都算出來，計算方法是每一個 i 都考慮它的 bitwise combination，比方說 11 時就考慮 A[10][home] + B[01] 和 A[01][home] + B[10]，這樣的一直比較，最後得出 B[1<<n-1] 就是要求的答案這樣。

找出 component 的算式非常特別，a = ((a | (~i)) +1) & i; 這樣算下去就能弄出 i 所有的組合，最後 a 會等於 i。這有一些情況下還蠻實用的。

マグナカルタ2 DISC2

2009-09-22T08:56:00.004+08:00

前幾天終於把這東西玩完，整體評分算是尚可吧。此作的最大賣點(對我來說)是系統，不過玩到最後，難易度來說實在是普通。從網上的攻略看來，最後 boss 戰拖太久的話是會被轟很慘，只是我根本是秒殺了他，完全看不到甚麼威脅…比起來之前打 Alex 還比較辛苦。

再來多講一些系統的感想。感覺上現今的 RPG 除了自身主題要強調的系統外，還是有一些「必備」的要素。比如那個超陽春的 Item Socket，甚至連裝備系統我也覺得頗為一般。當然如果連這些都沒有，那遊戲系統未免顯得過於單調，但即使有，也好像不怎麼樣啊？除了某幾顆特殊カモンド外，根本就只是單純的亂塞就好，裝備也只要裝上最新的就好了，並沒有需要選擇的情況。當然如果對每一樣東西都有所要求的話，遊戲的設計就會複雜很多(主要是難度)，所以也只能體諒他們了。不過我還是要說，那該死的期間限定任務作得太差了。沒有二週目優惠本來就不鼓勵你再玩，還要弄那些任務出來，要拿 100% 的話就要注意了。

故事方面，先來ネタバレ一下好了，不喜歡的就跳過吧。
故事的世界設定裡有一種被稱為カン的能量，藉著這種東西，人們的生活得到改善，開發了魔法或以カン推動的機器，然而在 N 年前發生的大戰，因消耗過度的カン而導致了一種被稱為災禍種的反物質產生，カン因而瀕臨枯竭。此時一名叫ストラス的傢伙跑出來犠牲自己，以其力量來維持世界的カン量，而他亦被稱為英雄。自那之後人們就生活在充滿著カン的環境，能利用カン能量去改善生活。ストラス事件的背後真相卻是，カン系統並沒有徹底被修正，每一百五十年就需要再犠牲一個擁有強大カモンド的人(被稱為マグナカルタ)來換取暫時性的平穩。而為了鍛練マグナカルタ的カモンド(北京填鴨?)，ストラス的分身將會引發戰爭，最後待カモンド可用時就將人殺掉這樣。

對於故事上的那個問題，主角一行人亦給出了答案，結局上來說也好像證明了他們的決定是正確的。不過現實的問題往往沒有那麼簡單，事實上今天主角可以作出那種決定，也就只因為他們能最後打掉 boss，要是不行呢？(那當然就 Game Over(?))說到底也就單純是實力講話，某程度上跟當年ストラス所作的並沒有分別，每當危機出現時，除了了解事實外，還是需要有實力的人來實行，對群體來說重要的就只有結果。這比起一般的 RPG 故事算是有多一點的反思。回顧一下遊戲的主題，愛と憎しみのRPG，其實玩到後來倒沒有那種感覺了。當發現ジュト的正體後，我還以為他會懷疑一下他對ゼフィ的感情，不過最後並沒有這樣。以劇情來說，其實整體還蠻……平淡的。至於玩到最後，我百思不解的還是為甚麼ジュト的內心世界會有 Save point……

CG 跟人物 model 還算不錯(2D的人設賣點突出(死))，戰鬥的畫面也算華麗，只是戰鬥的動畫好歹也給個 skip 吧…到了後來幾乎都只用大招時真是痛苦的等待。聲優請來了不少名人助陣，質素是有所保證的。川澄的ルゥ實在是太像セイバー了…音樂方面並沒有特別覺得好的。

以這遊戲的發售時期點來看，如果對它的系統有點興趣，又喜愛 RPG 的話是值得一試的，價格也算是合理。但如果是自認 Hardcore 的玩家，這東西的難度和系統就未必乎合需求了。

マグナカルタ2 DISC1

2009-08-21T09:51:00.007+08:00

某日看遊戲發售表時看到的，對那個戰鬥系統感興趣就弄回來玩看看了。ジャンル寫著愛と憎しみのRPG，まあ，雖然對大部分遊戲的故事都不作甚麼期待，但既然是 RPG，就看看故事有多慘(?)好了。

故事等 DISC2 一併解決好了，先來講講系統。基本上是極之接近 MMORPG 的日式 RPG，Skill tree/Item socket 都有，といっても，算是相當簡單的運作。最為特別的是 Chain System，到後期公式化之前其實蠻有新意的。有不少完成遊戲的朋友都說難度偏低，我想這個主要是來自系統方面，沒辦法設太難。戰鬥系統無法讓你靈活的操控小隊(Player/NPC 出招時就是要看完那招)，然而同時間其他 unit 還是在動作，這種情況下如果敵人威力太猛很容易導致被屈死。另外 Chain Drive 時被敵人的招打斷實在是很煩人。屬性カン要跟同系 NPC 爭個你死我活(事實上是根本爭不到)，不過這並不算是很大的問題，就當作特色好了。

本來 BANDAI NAMCO 的作品，我對隊友 AI 有著相當的期待(因為ToV)，教學裡也有提到要活用 AI 指令，但每個人只有三種類的 pattern…まあ，還是靠自己比較實際。

聽聞戰鬥太久會畫面定格當掉，不過還沒試過磨到那麼久。Anyway，系統來說算是力求新意，不用切畫面 loading 的戰鬥也蠻不錯的，3D 畫面也算有一定水準，只是開發了四年多，大概還是可以做更好？還是說花掉太多時間來 DIY，這就不得而知了。就等玩完 DISC2 再說。

Code Refactoring

2009-08-11T15:28:00.003+08:00

Code refactoring 這東西，寫過程式的人大概都應該聽過，甚至不經意之下也會經常去做一些 rename 或者 function merge/split，但有一些(其實應該是很多)情況，人們就是放著爛也不去做。

今天接手了一個簡單的 Java SOAP 程式，在 5000 多行代碼裡，兩個主要的 function 佔了大部分的空間。然而那兩個東西的 output 幾近一樣，我實在很懷疑要怎樣的腦才能想出這種寫法來。更慘的是，由於程式我也只是接手改，導致要依著他的寫法去改。每一個我要改的地方都要改兩次，毫無意義的重覆，今天丟過來的 patch 也一樣，改了兩個地方，但其實一模一樣。當然這樣講大概還是沒意義的，反正會這樣做也只是偏執罷了，但還是不爽。

Computer Science 算是相當年輕的科學，隨著這幾十年的發展加上大量的需求，教出一大堆學生，只是會去重視質量的到底有多少？或許不能全怪他們，畢竟市場上也是這樣，時間就是金錢，沒時間就是寫垃圾出來交，反正拿到錢就行了。這對老闆而言沒錯，但對自己呢？程式越改越多時難道不會覺得煩？與其去訓練自己去從垃圾堆翻東西的能力，倒不如認真點去想如何收拾一下比較好吧。

Oracle SQL Tuning (上)

2009-08-05T14:16:00.001+08:00

嚴格來說我對 DB 的認識並不深，對 Oracle 更加是一知半解，只是正好公司有 Workshop，就把學到的整理一下備忘。

Part 1: Oracle Architecture

Oracle Instance: System Global Area(SGA) + Oracle Background Processes
Oracle Database: All physical files make up a database

簡單來說，就是將記憶體部分統稱為 Instance，實體檔案統稱為 Database。每部分都由不少細部所組成，只是大部分都是設定相關的，是 DBA 的領域，作為 developer 只要知道如何能獲得設定資料就行了。SGA 可以使用show sga去查看共有多大。

Database 部分，redo log files 算是對 developer 比較有影響。雖然 Oracle 並不會在每次修改資料庫時進行實體的檔案更改，但卻必定要對 redo log files 進行寫入，以防突如其來的 DB crash，因此太過頻繁的 commit 會造成大量 file I/O。

以架構來說，除了最單純的記憶體/磁碟容量不足外，每個單元所有機會出現的問題︰

SGA - Latch, Buffer cache, Shared Pool(for SQL parsing), Redo log buffer(for changes)
Background processes - 主要是 Database writer/Log writer 的 I/O 問題。
Data Files - Too much read/write. Small buffer cache in SGA.
Redo Log Files - Frequent log switch due to too many changes or too small redo log buffer in SGA.
Archiver - Too many changes.

Part 2: SQL Tuning Concept & Tracing Methods

一句 SQL 語句由經客戶端輸入到順利執行會經過相當多的階段，了解裡面的運作機制有助加快 SQL 的執行。一般來說，DML 類的都要經歷 Open, Parse, Bind, Excute, Close 的階段，Select 的話還會有 Fetch。

每個階段做的事就不記了，只提一些重點。Parse 複雜的 SQL 時會相當花 CPU 資源，因為 Execution Plan 也是在這階段完成的，而且也應盡量減少 Hard Parse。Sorting 是在 Fetch 階段完成的，要注意的是，縱使要尋找的資料都在記憶體裡面，大量的平行查詢也是會造成影響的，這是因為每次 Fetch 時，Oracle 會對記憶體設置 Latch。

何謂 Execution Plan？就是 DBMS 執行該 SQL 的方法，Oracle 有自己的 Optimizer 去決定採用哪一個 plan，而決定的因素主要是根據過往的 statistic 來決定。(Part 3 再詳述)

要優化 SQL，最首先還是需要知道目標是甚麼，然後下一步就是先知道該 SQL 目前是怎麼運行，這就是 SQL Tracing 的目的。雖然追縱的方法相當多，但 developer 能用的其實就那麼幾個，包括 Explain, Autotrace 和 SQL Trace。

EXPLAIN PLAN [SET STATEMENT ID = 'text'] FOR statement
SELECT PLAN_TABLE_OUTPUT FROM TABLE(DBMS_XPLAN.DISPLAY());

查看語句的 Execution Plan 前要先 EXPLAIN。縮排最大的一行一般都是最先執行的，然而 Index lookup 卻跟它上面的 Table lookup 視為同一個 level。Oracle SQL Developer 可以以 GUI 查詢 Execution Plan。

一試之下發覺我手上的 DB 都沒法玩 Autotrace 和 SQL Trace，只好先跳過了。

Part 3: Oracle Optimizer

上面就提過這東西，它主要是決定如何去執行 SQL，而最顯而易見的就是一個相關的參數 OPTIMIZER_MODE。

RBO - Syntax driven, using no statistics about the data and not considering CPU time or other costs. RBO 主要是用在 index scan，最差是用在 FULL table scan。RBO 已經開始式微。

CBO - Statistics driven, generally better than RBO.

除以上兩種以外還有更多的，比如 FRIST_ROWS[_n]，而且還能用 hints 去影響 optimizer 的決定。另外，由於 statistics 對選擇起了決定性的作用，測試時期所應用的資料應該盡量接近實際情況，否則會導致結果有出入。

小結

其實 SQL Tuning 主要分為人手和自動兩種，自動的有兩種工具分別是 SQL Tuning Advisor/SQL Access Advisor。人手方面做法比較多，有提到的有︰

Object statistics
Hints
Optimizer parameters
Stored outline
SQL profile
Restructure SQLs
Use other structures
Redesign the flow

Test post for testing

2009-08-03T09:53:00.002+08:00

Test post for testing