[Hackathon] API Hackday SF

 

    早上八點頂著貪睡的慾望，硬是跟Stan殺到舊金山參加API Hackday SF. 比賽場地在Parisoma，也就是那種專門給宅宅們週未coding取暖的空辦公室。街道充斥著酒後狂歡嘔吐物的臭味，不用咖啡就很提神，算是很酷的地方。

    API Hackday比的是看誰利用別人的API，拼出最酷的產品，也就是看誰二次創作的能力最強，就像比誰站在巨人的 肩膀上跳得更高一樣。Sponsor的APIs主要有幾類：
1. 提供e-mail API, 讓你不用自己架SMTP mail server的 SendGrid, context.io
2. communication: VOIP的twilio, video streaming的open-tok
3. API manager: 上面放著其它一堆公司的API, 如Mashery, Mashape。基本上有open你想得到的廠商的API都有。
4. 不知道來幹麻的，應該說只有sponsor但是沒派人來，而且api也不清不楚：Apiphany，BigCommerce,

   經過一番討論後，我們決定利用open-tok來架一過即時拍賣網。簡單說就是針對很希望把垃圾趕快清掉的賣家，讓他開一個限時的 video conference room。買家們可以挑選有興趣的房間加入參與拍賣，一起來享受趁火打劫的樂趣。理想中的互動是賣家用video streaming跟買家們介紹他這個蟠龍花瓶多古老多名貴，買家不斷的挑毛病殺價說你這花瓶怎麼看起來像花盆，或是互想競標加價。最後買家321成交，結案。出發點是讓拍賣過程變得即時刺激有趣，增加互動。合理性商業可能性全不在考慮，反正hackathon重視的是創意！

   實作過程不像想像中那麼順利，首先我們到12點在開工，距離結束只剩6小時。再加上我貧弱的front end，還有完全不熟悉的node.js跟express, 要不是有stan大大，恐怕這個idea會一直都只是idea。話雖如此，進度也是嚴重落後，到了四點時只把最基本的首頁(商品頁)做好.…不過工程師的效率一向都是exponential的，越到最後關頭越強大，越到最後關頭越隨便....來不及做的server push也只好砍了。甚至slide是最後一分鍾做的....

   demo過程尚稱順利，該動的都會動，presentation也還ok，台下應該有聽懂我們是來hackathon不是來賣藥的。結束的時候還有人鼓掌跟吹口哨，工程師們果然都是好人！最後如預料的與前三名無緣，不過open-tok看到我們的努力，加上是唯一兩組用他們API的，把best open-toke prize給了我們...好吧也算是肯定了，誰叫另一組不爭氣呢？

   做個檢討的話，就是
1. hackathon是比好玩的，但是要贏就要偷跑。今天得獎的作品莫不是精美異常，有些參加人還是ceo拿自己公司的產品來介紹。
2. presentation大概佔七成吧，設計的好的簡報還是蠻有利的，雖然我認為今天報得都不怎麼樣。
3. UI, front end 真的很重要...最後關頭UI是投資報酬率最高的。好的首頁一秀出來，自己吹牛也吹得有自信起來。
4. 自己的T-shirt的size要記牢，女朋友的T-shirt size要記得更牢。

 行文至此，倍感勞累。古人有 云, no pain no gain!

 https://www.hackerleague.org/hackathons/api-hackday-sf-2013/hacks/live-bid

[UVA] 198 Peter's Calculator

題目：http://uva.onlinejudge.org/external/1/198.html

code & tests:
https://github.com/wilson100hong/UVAOJ/tree/master/Volume_1/198

想法：一行一行parse，根據三種不同的指令做如下動作
1. Assign
    含有 ":=" (assign operator) 的line都執行Assign。:=的左邊是variable name，右邊會是一個Expression。由於Expression內含recursive的桔構，我這裡使用tree來存儲Expression內的每一個Term，而每一個Term也是一個tree，包含著子Factor。由於題目的input皆是合法輸入，對於tree的每個children可以recursive parse。
    這個命令執行完時，我們會產生/取代一組variable name -> Expression的key value pair，也就是變數的定義。把定義存在global的map裡。

2. Reset
   去空白後，以RESET開頭的line皆執行Reset。把 variable name -> Expression map 清掉即可。

3. Print
    去空白後，以PRINT開頭的line皆印出變數evaluation出的數值。由於我們必需考慮undefined variable 和cyclic dependency的情況，我們必需先
  a. 確認當前變數被定義過
  b. 從當前變數往源頭變數們(":=" 右邊的變數們)迴溯，它們也必需被defined過。不斷迴溯，直到所有involved的變數為
   b1. 所依賴的變數皆定義過    或
   b2. 不依賴其它變數 (eg. a:=3)
   c. 如果符合，那麼所有會被evaluate到的變數都有被定義過了。第二步是check cyclic dependency，這一步用DFS即可。有cycle就是UNDEF

  排除undefined之後，就是evaluate變數。我這裡是用topological sort把所有involved變數的依賴性排序後，依ts order做evaluate。每次evaluate完一個變數後就存進cache裡來reuse。這樣的好處是evaluate一個變數時它依賴的變數們都有值了，可以值接從cache取出來，免除重複計算。


GY：
  這一題考的就是coding而已。不過還是有GY之處，而且都非常賤：
1. 空白行是合法的，跳過即可
2. token之間是可以沒有空白的。簡單起見，一開始就把空白trim掉
3. RESET 跟 PRINT 的前面也可以有空白 <-- waste me 4 hours

[UVA] 171 Car Trialling

這一題是很典型的語法分析題目。由於此題只需要判別句型是否合文法，最簡單的作法就是依照文法的優先序，不斷把token們組合成更高level的token。最後檢查是不是只剩一個類型為"instruction"的token即可。舉例來說：

//  組合結果     (粗體為token，細體為普通字符, ___ 為待組合tokens，// 文法)           

GO FIRST RIGHT AT "SMITH ST." AND CAS TO 20 KMH 

=> GO FIRST RIGHT AT sign AND CAS TO 20 KMH    

=> GO FIRST RIGHT AT sign AND CAS TO nnn KMH    // CAS -> cas

=> GO FIRST RIGHT AT sign AND cas TO nnn KMH    // cas TO nnn KMH -> change

=> GO FIRST RIGHT AT sign AND change            // AT sign -> where

=> GO FIRST RIGHT where AND change              // change -> time-keeping

=> GO FIRST RIGHT where AND time-keeping         

=> GO when RIGHT where AND time-keeping

=> GO when direction where AND time-keeping     // GO when -> how

=> how direction where AND time-keeping     // how direction where -> directional

=> directional AND time-keeping            

=> navigational AND time-keeping  // navigational AND time-keeping -> instruction

=> instruction

如此一來，題目就變成字串匹配及取代的問題。每次從文法庫中，選一個最優先的文法。從字串中尋找一組符合文法的tokens( -> 的左邊)組，找到的話該刪除該tokens 組，並插入新的token (->的右邊)。文法的優先性從下到上，即從 nnn 跟signwords做到instruction。有recursive定義的文法可以拆成兩組取代:

navigational = directional  navigational AND THEN directional

可以變為：

direction -> navigational

navigation AND THEN navigational -> navigational

有分崎的文法 :

instruction = navigational  time-keeping  navigational AND time-keeping

要先做

navigational AND time-keeping -> instruction

再做

time-keep -> instruction

跟

navigational -> instruction

可以自己想想看。

這一題讓我吃了史無前例的七個WA。最主要的原因又是不小心看題目：

"There will be one or more spaces between items except before a period (.), after the opening speech marks or before the closing speech marks."

要ok, 也就是說要特別check 

1. ""裡面不能是空的

2. 左"後不能直接空白

3. 右"後不能是空白

4. period " . " 前不能是空白

非常靠盃。

如果你還是WA，那麼這個從UVA forum偷來的test case 可能可以幫到你。t2.out是sample output.

May the AC be with you.

[UVA] 150 Double Time

這一題不難，只是麻煩。總之把新曆跟舊曆元年一月一日各是星期幾找出來，然後每次都從元年元旦當基準點推即可。我基本上是參考這裡。

debug的話，就直接把萬年曆印出來吧，新曆可以跟這裡比。舊曆的話，這裡有dropbox 的link:
https://www.dropbox.com/s/dti6vrcdxy18h19/old.out

[UVA] 179 Code Breaking

思路：這個目題有兩部份，一部份是求k，即encode的period。另一部份是求encode的permutation。
我求k的作法比較暴力，即從 k = 1開始，試到 k = n (n為cypher字串長，而非plain text長度)。如果中間遇到可以用的permutation，就可以結束迴圈作decode了。其中又可以發現，k必為 n 的因數 (n % k == 0)，所以可以跳過不可能的k值。

求permutation就比較講究。最直接的作法是做 k 窮舉，即 1234, 1243, .... 4321然後一一驗證。不過經由上次facebook hackercup 的教訓後，我發現這種匹配的問題，只要能將plain text與cypher的關係建構成二分圖，都可以用Bipartie match來解。只要能找到完全匹配，即為合格的permutation。建構二分圖的步驟如下：
1. 把plain text (P) 與 cypher (C) 每 k 個字元切一個chunk。cypher一定會沒有餘數，而plain text呢？只要在後面補?即可。如:  k = 3, plain text = abcd  --->  abc, d??。補問號可以讓P 與 C 的長度相同，把matching的邏輯簡化，也不失一般性，算是實作的一個trick。

2. 對 P 與 C 的第一個chunk，每個相同的 P[i] 與 C[j] 建一條邊，代表它們有潛力被匹配。於是我們得到左右兩邊各為 k 個 vertex的二分圖，而其上的邊代表相同字位交換位置的可能性。如果P或C有vertex沒被邊連到，那代表無法完全匹配，即此 k 不可行。

3. 對 P 和 C 之後的chunk，一次處理一個chunk。讓offset 代表 目前這個chunk離字串首的位移，對每個不同的P[offset + i] 與 C[offset + j]，如果之前有邊的話 (因為前幾個chunk該位置都可以match) , 便把邊移掉，不然無視。這一步是確保在每個chunk 中，P_chunk的第i 個字元 都可以匹配到 C_chunk的第j 字元。注意，我們的二分圖一直都是 兩個各有k點。


void BuildGraph(string text, string cypher, int k, vector< set<int> >&graph) {
   graph.clear();
   // Add edges
   for (int i = 0; i < k; ++i) {
      set<int> edges;
      for (int j = 0; j < k; ++j) {
         if (text[i] == cypher[j])
            edges.insert(j);
      }
      graph.push_back(edges);
   }

   // Remove invalid edges
   int len = text.length();
   for (int start = k; start < len; start += k) {
      for (int i = start; i < start + k; ++i) {
         int gi = i - start;
         for (int j = start; j < start + k; ++j) {
            int gj = j - start;
            if (text[i] != cypher[j]) {
               if (graph[gi].find(gj) != graph[gi].end()) {
                  graph[gi].erase(gj);
               }
            }
         }
      }
   }
}



最後把二分圖丟到Bipartie matching。完全匹配即為合格的k。permutation即為匹配。

有用的測資：

Input:
------
aaaaabbbbbcccccdddddeeeeefffff
aaaabacbbbcbddccdceeededfffeff
1234567890

aaaabbccuvwxuvwx
aaaaccbbxwuvxwuv
ABCD
#

OUTPUT:
-------
4632150?987?
CDBA

[UVA] 157 Route finding

思路： 利用Dijkstra求起點到終點的最短路徑。同一條線上相鄰的車站距離為1，不同線相交轉車的距離為3，接著求最短路徑。parse input時同時建立graph。

Dijkstra在C++的實作要點在於，relax distance需要一個支援update value (decrease key) 的 min heap。常見作法有二，一是用priority_queue，每次relax 時塞一個新的(node, relaxed_distance)進heap。由於relax後的同node一定有比較小的distance，所以一定會在heap的較上方。舊的distance就會被擠到下面，而在pop時被忽略。

另一個作法是用set 配合pair (node, distance)。每當要update node時，先把(node, old_distance)從set中移除 ，再新增一個pair (node, new_distance)。也就是用 delete/insert來達到 decrease key的目的。Top coder有非常完整的解說。

這一題有一個蠻有趣的陷阱，害我吃了一個WA。這是從forum上copy下來的範例:

5 
A:ab=Bbcdefghijk 
B:abc=Ajdef=Cb 
C:ab 
D:cd=Eg 
E:fg=Bf 
AaAk 
AcAk 
AbBb 
BaDd 
# 

The correct output is: 
9: Aab=Bbc=Ajk 
8: Acdefghijk 
3: Ab=Bb 
8: Babcdef=Dd 

WA output:
9: Aab=Bbc=Ajk 
8: Acdefghijk 
3: Ab=Bb 
11: Babcdef=Eg=Dd
陷阱在於，可能有複數個stations同為一個connection set，但是input沒有窮舉set中的任兩兩。如上題中，connection should be:
  Bf=Cb=Dd=Eg
但是題目只列出部份:
  Bf=Cb  Bf=Eg  Eg=Dd
也就是 Cb=Dd (以及 Cb=Eg, Bf=Dd)是需要程式自己推導出的。這種集合的驗證蠻麻煩的，所以我用了一些trick: 當'x=y'出現，可以知道x車站與y車站相連。製造出一個虛擬車站 C1，
且有邊： cost(x, C1) = cost(y, C1) = 3, cost(C1, x) = cost(C1, y) = 0 這樣 x 到 y, y 到x 的cost都是3。
接著當 y=z出現時，由於 y 已經連到 C1了，所以可以直接讓z 也連到 C1。如果z 之前連到另一個虛擬車站C2，那我們可以把C1跟C2連起來: cost(C1, C2) = cost(C2, C1) = 0，於是z 到 x 也是 cost = 3了。

[UVA] 172 Calculator Language

思路：

   算式中有三種token。分別為正負整數，變數 (A ~ Z) 和運算元 ( +, -, *, /, =, (, ) )。前二種哥以統括為運算子。在parse算式時，運算元放一個stack (S1)，運算子放另一個stack (S2)。為了保證括號的優先性，當遇到算式結尾或是右括號時，不斷pop這S1 與 S2 直到S1空了，或是S1頂部為左括號。值得注意的是，'='會改變變數的值，所以要維持一個變數的mapping。

   題目本身不難，吃了三個wa的原因主要有二：

1. 所有變數default為0

2. 比較變數有無更動要在算式做完才比對

eg,

A = 2

B = (A = 3) - (A = 2)

ans:

A = 2

B = 1