"How do you explain Diffie–Hellman key exchange to a child?"

個比喻邊個諗出黎, 太神了

From Wikipedia

Source: http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

蛋撻

心血來潮想食蛋撻
上網查看要甚麼材料, 很多都已經有/常見: 麵粉, 蛋, 牛油, 砂糖
有些則比較難買/不知道 svenska 名, 例如花奶, icing sugar, vanilla extract
不過花奶可以用牛奶代替, 亦成功憑直覺一次買對 icing sugar, 唯獨找不到 vanilla extract
最後找到最接近的 vanilla socker

然後就是模具
很多都是 for muffin 的, for tart 的又不夠深
最後在 Åhlens 找到

經過一系列和麵團的奮鬥, 總算可以開始焗
採用先焗撻皮, 焗到一半才加入蛋漿的做法
製成品:

下次撻皮要做得薄一些

KTH Exchange 42: 在 Stockholm 看極光

從冰島回來, 在巴士上上網一看, 極光指數竟然是從未見過的 7kp!
(上次在挪威看時是 1kp, 在冰島時 3kp)
雖然非常遺憾如果在冰島多留一天就可以看到超強的極光, 但 7kp 加上 Stockholm 天氣好代表在 Stockholm 也有機會看到!
搭 metro 到 Farsta 時是 22:50, 下一班巴士是 23:14, 於是果斷走回去
突然下了一個決定, 就是不回房放行李而是直接到湖邊, 最後證明這個決定是正確的

到了湖邊, 北面雖然有光害, 但竟然出現了肉眼也看到的極光!!!

雖然沒有在冰島看到的亮, 但這裏是南很多而且又有光害的 Stockholm!!! 太震撼了!!!
可惜只持續了 5-10 分鐘, 幸好沒有等巴士, 也沒有先回房放行李, 真是太好運了
這種強度一年可能只有一次呢...

Iceland Day 5

回程之前最後一站, 是 Blue Lagoon 藍色溫泉
雖然入場費要 30Euro, 但在零下三, 四度浸溫泉實在難得

然後直接去機場:

每次見到比 Stockholm 便直的餐廳便忍不住:

免稅店, 當然少不了:

正由機場回去時, 上網發現極光指數竟上升至 7

到底 RP 低到一個怎樣的地步才會發生這種事...
然後在冰湖竟然也看到極光

只維持了十分鐘
幸好沒有等巴士, 否則連最後一次機會也錯過..

Iceland Day 4 - Golden Circle

今天 join 了「官方」團, Golden circle
就是以 Reykjavík 為起點做一個 close loop, 以 efficient 的方法 visit 景點
直接去圖:

其中一個是間歇泉, 每隔數分鐘便噴一次熱水, 很有趣:

Þingvellir National Park
其中這道裂縫是歐亞大陸板塊和北美洲板塊的交匯處, 非常有趣:

低人口密度的國家風景真是無敵, 也不用成本去維護, 只要不動他就是

晚上預報有日冕物質拋射, 簡單來說極光理論會很強
但是, 非常可惜地, 原本 forecast 是 clear 的晚上竟然變成了 100% cloud cover
而且極光活動也沒有增強..
由於是最後一晚留在冰島, 還以為短時間內不會再看到極光, 但反例很快便會出現...

Iceland Day 3 - Aurora

forecast 預測今晚的天氣好, 很適合去看極光

白天則是隨昨天的日本人和另一個香港人夾錢租車

放眼數十公里皆不見人跡的感覺, 用照片也難以體會:

就是這座火山兩年前爆發, 使歐洲航空大亂:

晚上則是今天的重點, 極光

一直向東駛了約半小時, 遠離首都的光害

之後駛入了一條沒有街燈的分叉路

習慣了黑暗後, 已經隱約看到綠色極光:

第一張相就成功

把 ISO 調高至 1600 (本來是 800), 更拍到紫色!

有點多雲, 於是再上車駛至較北的地方避開雲
直接去圖:

事後查看, 今天的極光強度是 3

Iceland Day 2 - South coast

今天的 plan 是沿著冰島南部, 遠至離首都 300km 的地方
全團共 4 人, 除我以外還有兩個日本人和一個美國人, 全部都是來到才認識的
不過今天天氣不太好, 早上不時下雨和下雪
中途經過的瀑布:

平均駕駛半小時才到經過一個小鎮, 其餘時間都是一大片苔原, 以及遠處的雪山, 十分荒涼
小鎮的人口是以千來做單位, 可見人口之稀疏

早上八時半出發, 下午二時終於到達原本的目標
不知明的現象:

冰川

遇到一個日本團, 得知附近有個「黑色瀑布」

可以隱約看到地球的弧度:

之後開始回程, 回到 hostel 已經晚上九時

Iceland Day 1 - Reykjavík

今次終於是午機, 不用凌晨三, 四點搭車到機場
坐 IcelandAir, 不是廉航, 還有電視, 也是第一次坐 B757
到達後第一件事不是 claim luggage, 而是到 duty free shop 尋寶
發現不太貴的 Pilsner Urquell 4 罐裝 (~1000ISK):

到達市區和 hostel 已經快日落, 不過冰島首都市中心不大, 很快便可行完

世界奇觀

Reykjavík 和其它北歐首都相比很不像首都, 幾乎沒有高於 10 層的大樓
物價比 Stockholm 略低, 所以在 subway 把晚餐解決
晚上在 hostel 被一個日本人邀請明天租車遊 south coast, share 租車錢和油費
雖然 forecast 明天的天氣不太好, 但也不想留在首都, 於是便答應了

判斷 AOC 終局

基本上 RTS 都是 PSPACE-hard, 看這裏
不過今天打機時想到比較直接的 reduction, 也好像未看過類似的

判斷 AOC 終局
給出現時的遊戲情況, 判斷 player 1 能否勝出

True Quantified Boolean Formula
判斷一條這樣的 boolean formula 是否 true: ∃x₁∀x₂ ∃x₃∀x₄.....∃x_n-1∀x_n φ(x₁, x₂, x₃, x₄, ..., x_n-1, x_n)
可以假設條 formula 是 CNF

例如: ∃x ∀y ∃z ((x ∨ y) ∧ (y ∨ z) ∧ (¬y ∨ ¬z)) 是 true
因為可以 set x = T, 當 y = F 則 z = T, y = T 則 z = F

這個問題可以 reduce 為一個 2 player game:
- 順序 assign T/F 給每一個 variable
- player 1 負責 assign ∃ 的 variable
- player 2 負責 assign ∀ 的 variable

Assign 完後:
- player 2 選擇一個他認為沒有 satisfy 的 clause, 例如 (x₁ ∨ ¬x₅ ∨ x₈)
- player 1 選擇他認為這個 clause 其實是 true 的 variable, 例如 ¬x₅
- check 這個 variable 是否為之前的選擇, 即 test x₅ 是否選了 false, 是的話 player 1 勝出

假設雙方 play optimally, 如果 player 1 勝出即是 formula 為 true

AOC gameplay setup
Player 1 需要在限時內收集少量的木材, 否則 Player 2 勝出
具體做法是 player 2 有足夠多的兵力, 但被 player 1 的層層石牆圍著, 只要時間把石牆破壞便可以清場勝出
而 player 1 有接近無限肉和金, 但沒有木, 若可興建軍營便有足夠的兵力清場
而 player 1 能否成功收集少量的木便是勝出的關鍵

player 1 能否成功收集木材, 則取決於條 QBF 是否 true
遊戲流程與 player 1 村民的路徑:

如果 verify 成功, 則 player 1 的村民可以收集到木材
否則 player 1 只能等死

以下的圖中的 label:
藍色: player 1
紅色: player 2
淺藍: 海
淺綠: 陸地

Assumption:  player 1 的村民若試圖徒手破壞 player 2 的建築, 會花費太多時間而讓 player 2 勝出

Single use & directed road (P1/P2)
一方由左邊進入, 坐船到右邊
運輸船的 hp 剛好只能通過一次, 所以既不能往回走 / 到右邊接人到左邊

Player 1's choice (∃)
player1 的村民由左方進入, 炸藥筒的數量剛好足夠炸開其中一邊的石牆
炸開石牆除了可以繼續前進, 還要 assign 相應的的 T/F 給 x_i (後述)

Player 2's choice (∀)
如果沿用上述的 design, player 2 可以甚麼也不做, player 1 也無可奈何
所以要強制 player 2 作出選擇, 否則 player 1 可以任選一邊, 設計如下

player 2 可以做的是選擇一邊用塔封掉;
player 1 只能經沒有封掉的一邊通過並 assign 相應的的 T/F 給 x_i (後述)


Verify test
首先 player 2 choose clause 和 player 1 choose variable 用上面的 construction 可以構造
之前的 choose 和 verify 構造如下:



如果之前選擇了某 variable, 便可以在藍色圓圈處興建箭塔, 把 player 2 的遊俠射殺
這樣 player 1 的村民稍後在上方進入便可以安全伐木, 否則會被 player 2 的遊俠砍死

Planarization
按照原本的構造,  個 graph 可能不 planar
而 AOC 是 planar 的遊戲, 所以要做一做手腳
假設原本的路是左至右及下至上相交, 則改成:

如果 player 1 的村民由左方進入, 必需把左邊擋路的伐木場自爆掉才可繼續前進
在十字路口, 如果 player 1 選擇「正確」方向向右, 則 player 2 只可:
A) 開右邊的路, 讓 player 1 照目標前進
B) 開向下的路, player 1 就可以伐到木勝出

在十字路口, 如果 player 1 選擇「錯誤」方向向上, player 2 可以封掉向上的路
則 player 1 只能轉左, 雖然伐到樹, 但是原本的伐木場已經自爆掉, player 1 也 stuck 了

由於 TQBF 是 PSPACE-Complete, 由此得出判斷 AOC 終局是 PSPACE-Hard
參巧: 圍棋是 PSPACE-Complete 的 proof

KTH Exchange 41

連續一星期日間溫度在零度以上, 把雪融掉不少
冰湖上的雪深也減少至容易在上面行的程度
順便試了影 panorama 的 app:

KTH Exchange 40

由於 course schedule 的關係, 連續三個星期沒有 lecture

而且又未融雪, 所以大部份時間都在室內

不過窗口向東, 可以看到日出和月出, 順便試相機的 interval shot function:

近來傾向「看」和「想」題目, 很少真正 code 出來
不過今天晚飯前看到一條想驗証一下想法, 打算過題後煮飯
題目 reduce 做 graph 問題, 其中我的 construction 為 |V| = 4000000, |E| = 8000000

memory 非常的 tight, 在其它地方用了很多技巧還是不夠
逼不得已要在 edge linked list 下手:
每個 node 可以用 44 bit 表示, 用一個 int + short int 有 48 bit
先轉成 destination*|E| + next_address, 再分拆成一個 int 和 short int
memory 終於夠用, 結果是 TLE
最後要用到 bitwise operation: destination << 23 + next_address

結果花了差不多 2 小時, 凌晨一點半才吃「晚餐」, 太熱血了...
今天嘗試新菜式: 白酒蕃茄意粉, 海鮮和白酒可是佔了成本旳 70% 呢