整數集合找出最長連續數列長度

例子：

(1) { 1, 2, 3, 4 } returns 4

(2) { 4, 5, 6, 10, 11 } returns 3

(3) { 1, 2, 4, 5, 7, 8 } returns 2



我的想法來自於 DFS 的經典題目：grafixMask



這是演算法教學系列文章：

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index

裡面有一篇不錯，雖然大學有教 graph algorithms，可惜當時沒有熱情，

我說的就是這篇：

Introduction to Graphs and Their Data Structures

((現在有熱情的理由也是很瞎，Candy Crush Saga 激起我解決問題的衝動，

數學問題太難，演算法問題可難可易，很適合我解決問題))

總之以 C# 的語言來說，

先把 int[] input 丟到 HashSet<int> numberSet = new HashSet<int>(input)，

O(n)。

接著 iterate hash set，把每個整數點 p 當做一個 Node，

Edge 就是 p-1 或是 p+1，這個查詢只要 O(1)，因此我們可以建出一個 graph，

space O(n)

((上班說錯更正一下，直接用 linked list 實做 graph 就可以了))

接著 grafixMask 技巧用下去，直接結束。

time complexity O(n)

space complexity O(n)

不過這比起 Candy Crush Saga Level 361，簡直小巫見大巫，

這關有夠機車的。

Dijkstra's algorithm 及其他

1. Breadth-first Search ((BFS)) 加強版，原本的 queue 要改成 priority queue ((也就是 heap，heap 有分 min heap 或 max heap))


2. 問題的關鍵都是「如何抽象化成數學模型」，哪些是點 ((狀態，哪些 factors 該計入狀態？))，哪些是邊 ((有向或是無向，數字權重代表的意義是甚麼？))


3. 如果 N 不大，可以考慮用 Floyd-Warshall Algorithm，使用前思考一下為什麼使用這個演算法？這是對的演算法嗎？如何保證答案就是演算法算出來的答案？


4. DFS 與 BFS 是否可以互相取代？

Candy Crush Saga Level 361 -- 果子不會對齊

扭蛋機只是幌子，果子不一定會從扭蛋機出來，

當果子從最邊邊下來時，雖然可以移到旁邊但很辛苦根本就是整人。

多玩幾次，總有機會好運氣，

基本就是狂刷下面，拿條紋＋包裝狂刷，

很多關都是如此技巧 ((例如今天示範的181))，

條紋＋彩色糖適合大範圍消果凍亂消，但這關要刷四個綠色箭頭孔道。



這關是新單元最難的一關。

同場加映 Level 365，這關也很難，剛好最後一步過關，只要消掉綠色就可以了，

至少有四種移法，這種關就要盡量把糖果滅掉，

不管是怎樣的糖果，只要消的越多，

新出來的某色糖果也越多 ((當然包括藍色與綠色))，

倒數十步再來專心蒐集某種顏色糖果，

這是這類型關卡的要點。

Candy Crush Saga Level 181 -- 中文介面幫解

實驗證明，包裝＋條紋消的效果最棒，

彩色＋條紋的方向太難掌握，不過如果有現成的可以消，

當然先消先贏。

Candy Crush Saga Level 356

今天 Candy Crush Saga 發表新單元，Level 351 ~ 365 啟動。



剩下十一步，一個條紋糖果在右下角四乘四，

附近又沒有辦法再造另個條紋糖果，這代表一件事，

我得在其他區域再造兩個條紋糖果，再想辦法黏在旁邊。



是該放棄了。




放棄前把糖果炸掉，死也要壯壯烈烈的死去，

刷著刷著，結果掉下來不偏不倚兩個條紋糖果又瞎貓摸耗子黏在旁邊

接著曼尼敲出延長賽兩分砲，不該放棄任何機會。

Depth-First Search

WIKI: http://en.wikipedia.org/wiki/Depth-first_search



實作細節：

1. 比起 Non-recursive implementation, recursive implementation 會佔用較多的 memory stack，無所謂好壞，只要能符合需求的就是好程式。

2. Graph 是有向圖或者是無向圖，這很重要。

例子：http://community.topcoder.com/stat?c=problem_statement&pm=1524&rd=4472 ((可能需要登入帳號))

product 1 competes with 2 => product 2 competes with 1，所以 graph 是無向圖。

using System;
using System.Collections.Generic;

namespace TopCoder.GraphPractice
{
    class Marketing
    {
        public long howMany(String[] compete)
        {
            Dictionary<int, Vertex> graph = GetGraph(compete);

            int arrangedCount = 0;

            foreach (Vertex vertex in graph.Values)
            {
                if (!vertex.Visited)
                {
                    vertex.Consumer = ConsumerGroup.Teenagers;
                    if (HasArrangement(vertex))
                    {
                        arrangedCount++;
                    }
                    else
                    {
                        return -1;
                    }
                }
            }

            return (long)Math.Pow(2, arrangedCount);
        }

        private Dictionary<int, Vertex> GetGraph(String[] compete)
        {
            Dictionary<int, Vertex> graph = new Dictionary<int, Vertex>();
            
            for (int i = 0; i < compete.Length; i++)
            {
                graph.Add(i, new Vertex());
            }

            for (int i = 0; i < compete.Length; i++)
            {
                String[] vertexList = compete[i].Split();
                foreach (String vertex in vertexList)
                {
                    if (!String.IsNullOrEmpty(vertex))
                    {
                        int j = Int32.Parse(vertex);
                        if (!graph[i].Neighborhood.ContainsKey(j))
                        {
                            graph[i].Neighborhood.Add(j, graph[j]);
                        }
                        if (!graph[j].Neighborhood.ContainsKey(i))
                        {
                            graph[j].Neighborhood.Add(i, graph[i]);
                        }
                    }
                }
            }

            return graph;
        }

        private bool HasArrangement(Vertex vertex)
        {
            bool hasArrangement = true;

            Stack<Vertex> stack = new Stack<Vertex>();
            stack.Push(vertex);

            while (stack.Count > 0)
            {
                Vertex top = stack.Pop();
                if (top.Visited)
                {
                    continue;
                }
                top.Visited = true;
                
                foreach (Vertex neighborhood in top.Neighborhood.Values)
                {
                    if (neighborhood.Consumer == ConsumerGroup.Unknown)
                    {
                        if (top.Consumer == ConsumerGroup.Teenagers)
                        {
                            neighborhood.Consumer = ConsumerGroup.Adults;
                        }
                        else if (top.Consumer == ConsumerGroup.Adults)
                        {
                            neighborhood.Consumer = ConsumerGroup.Teenagers;
                        }
                    }
                    else
                    {
                        if (top.Consumer == neighborhood.Consumer)
                        {
                            hasArrangement = false;
                        }
                    }

                    stack.Push(neighborhood);
                }
            }

            return hasArrangement;
        }

        private class Vertex
        {
            public Dictionary<int, Vertex> Neighborhood { get; set; }

            public bool Visited { get; set; }

            public ConsumerGroup Consumer { get; set; }

            public Vertex()
            {
                Neighborhood = new Dictionary<int, Vertex>();
                Visited = false;
                Consumer = ConsumerGroup.Unknown;
            }
        }

        private enum ConsumerGroup
        {
            Unknown,
            Adults,
            Teenagers
        }
    }
}

受傷的好處

今天是美女復健師幫我拉手，好開心，

這週一定很幸運頭上沒有羊角，早上台股莫名奇妙 (3,000) 那只是個蘊釀，

純種高粱的美味晚上才品嘗的到，

用力握美女的手，右手肌腱沒有炎，但是左手有炎。



為什麼自己摸不到？美女才摸的到！

長時間工作打電腦養成的繩子右手休息兩個月竟然好了，

醫院除了治病還能挖掘病，還是少讓美女復健師摸到，

不然奇奇怪怪的毛病又被摸出來，可怕。

[C#] Depth First Search

Problem Statement for grafixMask

Tutorial: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs2

using System;
using System.Collections.Generic;

namespace TopCoder.GraphPractice
{
    class grafixMask
    {
        public int[] sortedAreas(String[] rectangles)
        {
            bool[,] visited = GetBlockedPixels(rectangles);

            List<int> areas = new List<int>();

            for (int row = 0; row < 400; row++)
            {
                for (int col = 0; col < 600; col++)
                {
                    if (!visited[row, col])
                    {
                        areas.Add(GetConnectedArea(row, col, ref visited));
                    }
                }
            }

            areas.Sort();
            
            return areas.ToArray();
        }

        private bool[,] GetBlockedPixels(String[] rectangles)
        {
            bool[,] blocked = new bool[400, 600];

            foreach (String rectangle in rectangles)
            {
                String[] coordinates = rectangle.Split();
                int topLeftRow = Int32.Parse(coordinates[0]);
                int topLeftCol = Int32.Parse(coordinates[1]);
                int bottomRightRow = Int32.Parse(coordinates[2]);
                int bottomRightCol = Int32.Parse(coordinates[3]);

                for (int row = topLeftRow; row <= bottomRightRow; row++)
                {
                    for (int col = topLeftCol; col <= bottomRightCol; col++)
                    {
                        blocked[row, col] = true;
                    }
                }
            }

            return blocked;
        }

        // Depth first search.
        private int GetConnectedArea(int row, int col, ref bool[,] visited)
        {
            int area = 0;

            Stack<Vertex> stack = new Stack<Vertex>();
            stack.Push(new Vertex(row, col));

            while (stack.Count > 0)
            {
                Vertex top = stack.Pop();

                if (top.Row < 0 || top.Row >= 400) 
                {
                    continue;
                }
                if (top.Col < 0 || top.Col >= 600)
                {
                    continue;
                }

                if (visited[top.Row, top.Col])
                {
                    continue;
                }

                visited[top.Row, top.Col] = true;

                area++;

                stack.Push(new Vertex(top.Row + 1, top.Col));
                stack.Push(new Vertex(top.Row - 1, top.Col));
                stack.Push(new Vertex(top.Row, top.Col + 1));
                stack.Push(new Vertex(top.Row, top.Col - 1));
            }

            return area;
        }

        private class Vertex
        {
            public int Row { get; set; }

            public int Col { get; set; }

            public Vertex(int row, int col)
            {
                Row = row;
                Col = col;
            }
        }
    }
}

Gods often contradict our fondest expectations

Euripides, Medea

莫言，紅高粱家族



事情的發展總與想像相反，中間夾雜的人性，

非得自我毀滅不蒸饅頭爭口氣。

七星山苗圃登山口土地吸滿腫脹的雨水，那是起點，

尋找那兒噗噗拉屎神秘小徑，屎兒早已被雨水沖到山腳，

回到自來水廠，再給山下都市人們喝，

水有細菌不乾淨，拉屎回到土地，再用另一個方法回到石門水庫。

狗吃人肉，人再來吃狗肉。



現在台灣不吃狗肉，不文明，台灣尊重狗本，

不買狗認養狗，PIZZERIA OGGI 旁冰淇淋店拉布拉多小乖很饞嘴，

那家比薩店可好吃的，小乖不知有無吃過那軟細餅皮沾上張牙舞爪芝麻葉？



狗本注重以認養代替購買，也注重狗的體型，

減肥不是女生話題，而是狗本問題。

那些年我們錯過的運動，現在只能委屈的躲在健身房踩跑步機，

國北師操場比跑步機好上千萬倍，

有打排球的妹，有打籃球的妹，有跑步的妹，

真不曉得是流口水還是流汗水。



4000M、4000M、陽明山公車總站與苗圃登山口0.7K的來回。

Candy Crush Saga 每次看廣告的訊息

King.com da las gracias a sus anunciantes por ayudarnos a ofrecer unos juegos gratuitos geniales.

¡Recibirás tu recompensa cuando finalice el mensaje patrocinado!

Google翻譯：

King.com is grateful to our advertisers for helping to offering great free games.

You will receive your reward when you finish the message sponsored!

You've Broken Faith with Me

https://records.viu.ca/~johnstoi/euripides/medea.htm



如果就這麼繼續五年，

就這麼忍耐欣賞不想看的電影，任憑悲慘世界無聲無息，

就這麼沒有自己，

就這麼踏上多數人嚮往又噁爛的婚姻。



或許不提不會知道，帶上帽子羊角不會長出，

但他告訴我，在一起的時候你們就在一起，

我沒有潔癖，我沒有自我都無所謂，

但我想就這麼完成一件誰也沒辦法阻止我的事情，

這點要求並不過份，這點任性也很天真。



偶爾大方，不代表有義務請客，

與其說請客，不如說想做自己開心的事，

我又不是小丑，沒必要事事如人所願。



May I die a happy man.

Candy Crush Saga Level 153

先把上面石頭清掉，上面要造彩色糖機率不高，

((下面石頭就清一些，兩旁就別清了))

就算造了，滑到下面也有可能被消掉，

顏色不多，不必刻意消掉稀少的糖果，

只要留意一點：彩色糖只能隨重力一直往下，彩色糖不能移動。

所以只有兩種湊法：在同一直排，或是在兩相鄰的直排。

往下的走法就是清彩色糖下面的糖果，只能這樣子走。

窖藏的腐爛蘿蔔

《紅高粱家族》第一章就那麼噁扯、淚催，越讀越是心揪在一起，

莫言寫故事自然有股霸氣，與 Virginia Woolf 餘音婉娩徹底的不同，

畢竟我的母語是中文，不是英文，

英文怎麼看就是一團便秘卡在肚子裡，只能憑藉好心翻譯家為我們娓娓道來。

草嬰翻譯《戰爭與和平》堪稱一絕，希望未來翻譯作品能與草嬰相比擬。

會這麼看莫言，一方面是摸摸託我買《檀香刑》，想必有可觀之處，

另一方面，諾貝爾文學獎加持，不跟點潮流哪行，而且我也並非盲目追求流行，

幾千年前 Euripides 寫的《Medea》也是照啃不誤，好東西總是不能放過，

放過是小孩子的遺憾，沒那麼遺憾，但總是記住一輩子。

《檀香刑》，寫是古代的噁扯，但心態是現代，

並不是不在意劊子手的行刑手法，而是現代人的行刑心態，

跟以前投機事業一樣，以前人瘋鬱金香，現在人瘋黃金還是房地產，心態都是現代的。



復健已經摸不到自己的指紋，壓迫的指頭漸漸生出指甲，

角度五十九度，竊以為八十度，醫生用儀器量果然殘酷的準。

跑步每周 6000~8000 公尺，以為沒事的腳其實是有事的，

只是爬山會有股真氣硬撐上去，但活動不停歇的跑步會透露真相，

右腳就是比較不愉快。



但也不是如此悲觀，Candy Crush Saga 無道具過完 350 關，堪稱一項成就，

偉大、不凡、壯烈、無力、生氣、翻滾、吶喊、冷靜、瘋狂、暗喜、埋怨，

這就是天殺的 Candy Crush Saga。

Candy Crush Saga Level 135

這關技巧蠻重要的，步數多，

壞的開局可以靠五十步來彌補。

這關要求湊兩組「包裝糖 + 包裝糖」

開始兩的底角有巧克力，如果沒有太過份，我是不會去清巧克力的。



包裝糖一定要五個才成組在一起，比條紋糖果多一個糖果，

跟巧克力糖一樣多，但因為巧克力糖方向只有兩種，

所以湊包裝糖比巧克力糖簡單。



假如我們要湊綠色包裝糖，綠色糖果自然是越多越好，湊包裝糖的機率才會高。

如果整個畫面只有四個綠色糖果，自然不容易湊綠色包裝糖。

因此大原則就是消去數量稀少的顏色糖果。

((之後湊其他特殊糖果也是遵照如此原則))



除了基本形 L 跟 T 湊法，也可趁糖果掉下來的時候湊十字糖果。

移動前先想三十秒，說不定我們能夠找到更美妙的走法，加油！！！

Candy Crush Saga Level 154 -- 完全的運氣

消果凍，果凍在巧克力底下，共有兩層。

當我用「包裝糖+條紋糖」組合技消巧克力時，

糖果落下時先消三格果凍，

消完就變上圖，喵的，運氣超好，只要再移動一次藍色糖果就可以惹。



完全的運氣。

Candy Crush Saga Level 219 霸氣的消法

兩個巧克力球交換可以清光所有的糖果 ((及一層果凍))

Medea

Link: https://records.viu.ca/~johnstoi/euripides/medea.htm

¡Sí, he completado el nivel 325 en Candy Crush Saga!

這關的難，

只有靠運氣來能解決，巧克力鍋真是天殺的臭，

中間一排迴紋針，這簡直是南北韓中間那條北緯三十八度線，

要想辦法跨越。



清明節前段被卡死，用一個棒棒糖先敲掉，

直到今天才補完，整整卡十多天 = ="

有兩次只剩最後一個糖果，

不過最常發生的是被巧克力卡在最上面，

十個果子沒半個完成，就知道巧克力有多臭了。

不過清明節後段改卡 342，這關也是天殺的難，

魚要咬下面三層很難打到的果凍，

還好最上面一層可以硬爆沒問題。

¡Sí, he completado el nivel 325 en Candy Crush Saga!

Acabo de completar el nivel 325, he obtenido 134 214 puntos y conseguí 1 estrellas.

¡Haz clic aquí para seguir mi progreso!

¡Sí, he completado el nivel 350 en Candy Crush Saga!

¡Sí, he completado el nivel 350 en Candy Crush Saga!

Acabo de completar el nivel 350, he obtenido 325 860 puntos y conseguí 2 estrellas.

¡Haz clic aquí para seguir mi progreso!



終於無道具完成這關。



這關就是狂轟猛炸，兩邊有令人畏懼的倒數十二步炸彈糖果，

沒在怕的。

如果躲太嚴，60步不足以清完所有果凍，

有三次只剩最後一格果凍，

在最下面的角落，殘念。



總計使用「巧克力糖 + 條紋糖果」各兩次，

炸彈出來就出來吧。



舒服！

[FWD] Japón retira 3,4 millones de autos por airbag defectuoso

Link: http://www.bbc.co.uk/mundo/ultimas_noticias/2013/04/130411_ultnot_japon_retiro_autos_airbag_defectuoso_jp.shtml


Japón retira 3,4 millones de autos por airbag defectuoso

11.04.13

Cuatro fabricantes de automóviles japoneses anunciaron el retiro de casi 3,4 millones de automóviles del mercado debido a un posible defecto en los airbags.

Un funcionario japonés aseguró que el problema con los airbags, fabricado por la firma japonesa Takata, afecta 1,73 millones de autos de Toyota (fabricados entre 2000 y 2004), 1,13 millones de Honda, 480.000 de Nissan y 45.000 de Mazda.

Una portavoz de Toyota dijo que se registraron cinco incidentes de mal funcionamiento del airbag en sus vehículos pero que no se habían registrado accidentes ni lesiones.

Una pieza defectuosa, agregó esta compañía, "podría hacer que el inflador del airbag se rompa y desplegarlo de forma anormal en un accidente".

Un portavoz de Nissan le dijo a la BBC que estaban "llevando a cabo un retiro voluntario de seguridad para enfrentar el problema y reemplazar el inflador del airbag del asiento del acompañante".

[MSSQL] IF EXISTS

最近看到一個不太直覺的 stored procedure

CREATE PROCEDURE OneProcedure (...)
AS
IF (SELECT COUNT(*) FROM OneTable) = 0
RETURN 0;
ELSE
RETURN 1;
GO



其實可以用 EXISTS 改寫。

IF EXISTS (SELECT * FROM OneTable) ...



如果只是要下 SQL:

select case when exists(select 1 from OneTable) then 1 else 0 end

[FWD] ¿Está China lista para abandonar a Corea del Norte?

純粹就是拿來練西語。

Link: http://www.bbc.co.uk/mundo/noticias/2013/04/130409_internacional_corea_norte_china_abandono_tsb.shtml


解釋就慢慢補，畢竟我真的太弱了。

但就如文中所說，No tiene miedo ((不要害怕))

China no tiene miedo de ser invadido o rodeado por ningún país.

依照文法，invadido 意思大約等於 rodeado，

invadir = to invade，從字面可以猜出其意。

En febrero, el periódico Financial Times de China publicó una columna de opinión bajo el título "China debería abandonar a Corea del Norte".

這就不難看出來了。

Su autor, el editor Deng Yuwen, argumentó que Pekín debería apoyar la reunificación coreana.

apoyar = to support，聲音很像 ((誤))

Pero ninguno de nosotros puede vivir sin ellos. 

很多句子看不懂，就挑看的懂得看唄，像上面這句就很簡單，但，沒有，我們，能，生活，沒有，他們。

大笨鳥，黑冠麻鷺

介紹 (http://www.wretch.cc/blog/daponachung/12033306)

黑冠麻鷺（學名Gorsachius melanolophus）主要分佈於亞洲南部、東南亞一帶，多棲息於森林中，成鳥頭頂有黑色羽毛，眼睛周圍有明顯的藍色毛色，色彩相當繽紛亮麗。而幼鳥身體翅膀上則有星星般的白色斑點，體型較小。

台大森林系教授袁孝維表示，黑冠麻鷺出生後約四周離巢，再二周便離開父母親獨立生活，可活到十歲左右。一般在都市中見到的黑冠麻鷺，白天會到草地上找蚯蚓吃，常站在地上一動也不動，也不畏懼人類，看起來就是呆呆的，才會有「大笨鳥」的稱號。

目前大笨鳥在家裡雨豆樹棲息，淨挑粗枝粗葉築巢，

好大一隻鳥兒停在門口發猛呆。



白頭翁就機靈多了，一對在桂花樹上築小巢孵蛋，

一隻窩著發熱，

另一隻遠端警戒。

Candy Crush Saga Level 347

不好意思，我的 Facebook 介面是西班牙語。

Level 347 算是很噁心的一關，整個就是靠運氣而已。


最後一步。

((

非常仰賴第一次彩色糖 + 包裝糖爆完的盤勢，那可以迅速湊出想要的糖果，
如果沒把握住，那只能下一次再連絡了。

))

第一個組合完全是靠運氣，

彩色糖往下滑到中間，

接著包裝糖黏著厚實的奶油一路滑到彩色糖旁邊，

剛開始可以靠這招黏在一起，一旦釋出巧克力鍋內蘊的殺傷力後，

根本就很難玩。

當然這也是玩了好多次的技巧。

最接近的一次就是第二組包裝糖跟巧克力糖差一格 = ="

整個就是快崩潰了。

The Epic of Gilgamesh

Link: http://www.ancienttexts.org/library/mesopotamian/gilgamesh/