over 2 years ago

忘記是從哪裡看來CodeFights這網站了,這網站的概念很簡單,就是試著把寫程式變成挑戰遊戲一樣,印象中剛開始玩時,是每題有n秒解題,看能連續在時間內解多少題,玩了幾次常常在第七或第八題就超過時間了(當然有時候第一題或第二題就掛了XD),後來一忙也就沒再光顧了。

最近看到CodeFights的信,似乎有點不一樣,於是再次到CodeFights玩玩,多了幾種模式:挑戰最少程式碼解題、對戰(這好像之前也有,只是沒玩過),對戰就是隨機配對,然後解相同的題目數題,越早完成分數越高,全部結束後比誰分數高,目前只玩一次,挺刺激的。

另外就是網友發挑戰,給予特定的獎金,在特定實現之前解出來可以獲得獎金(獎金可以在挑戰結束後用來看別人的答案),若在特定語言用最少字元(扣除空白)完成,另可得到最短優勝者,其實挺有意思的,所以連續玩了幾天,有些感想。第一個想法是,沒想到數學題蠻多的,然後雖然要想比較久,但我還蠻喜歡用遞迴解題。

最近一個我覺得有意思的題目是Doubling

Lonerz got some crazy growing plants and he wants to grow them nice and well. Initially, the garden is completely barren. Each morning, lonerz can put any number of plants into the garden to grow. And at night, each plant mutates into two plants. lonerz really hopes to see n plants in his garden.

Your task is to find the minimum number of plants lonerz has to plant to get n plants one day?

Example:
Doubling(5) = 2
Lonerz hopes to see 5 plants. He adds 1 plant on the first morning and on the third morning there would be 4 plants in the garden. He then adds 1 more and sees 5 plants. So, lonerz only needs to add 2 plants to his garden.

Doubling(8) = 1
lonerz hopes to see 8 plants. Thus, he just needs to add 1 plant in the beginning and wait for it to double till 8.

一開始確實想用遞迴去解題,但在幾次排列後,突然發現根本沒有那麼複雜:

1 -> 1 (第一天種就得到1)
2 -> 10 (第一天種,第二天就得到2)
3 -> 11 (第一天種,第二天再種就得到3)
4 -> 100 (第一天種,第三天就得到4)
5 -> 101 (第一天種,第三天再種就得到5)
6 -> 110 (第一天種,第二天再種,第三天就得到6)
7 -> 111 (第一天種,第二天再種,第三天再種一次就得到7)

到這裡,我想學過二進制的都已經看出來,這題該怎麼解了,只需要算出n的二進制表示中有幾個1即可,本來想自己寫算1的數量,但後來想到Java有內建的Integer.bitCount(n)可以用,於是把答案送交了,當時還以45個字元與很多人並列最少字元,隔陣子收到信說挑戰結束了,看看誰是最少字元,沒想到還有42個字元的答案,當時花了金幣去看對方的答案,看到後有點傻眼,想法一樣,但確實比我短,有興趣的人就猜猜看吧!

看完答案的感想是,追求卓越的人還真的不少,到目前為止,我最有把握拿到最少字元的解就這題,其他不是比領先者多一倍,或是差個位數個字元,例如這題計算數字金字塔某一列的總和,我已經找出數學式,但並沒有拿到最少字元,差2個字元,這挑戰還沒結束,所以暫時我也不知道對方是怎麼完成的。

第三個感想是,問題的表達方式可以很有趣,如果剛剛所列的問題直接寫成:計算出某個整數在二進制表示中1的數目,我想應該不會有人覺得很有趣吧!雖然CodeFights中也有很平舖直述的挑戰題目,但我特別喜歡這類有趣的題目,例如這題摺紙

話說摺紙題當初也是用遞迴的方式解,但中了陷阱,CodeFights也是有TDD概念的,只是測試是CodeFights幫大家寫好了,但寫完即跑的和送交答案的測試案例數量不同,當初寫完跑測試一下就過了,於是很高興地送交,結果被退,看了好久才發現少考慮一個條件,因此,真的,測試案例的數量和品質很重要!

不過既然問題的表達方式可以有很多種,是不是也表示,當面臨一個問題時,有時候想的太複雜了,有時候又沒有真正理解背後的問題,不管是客戶開的需求也好,或是自己創業從客戶得到的回饋也好,若只考量到問題的表象,事實上不見得能真正地幫助到客戶,甚至會用很複雜的方式去處理一個問題。

最後,曾經有人用不可思議的短程式解決某個問題,在好奇心驅使下,我花了金幣去看對方的答案,第一個瞬間是三字經,看了很久後終於懂了,但對我來說,我寧願寫長一點,讓我的語意清楚一點,讓以後維護的人好懂一點。程式是寫給人看的,簡單易讀比較重要!

← Waterfall 陰魂不散 使用TestFX測試JavaFX應用程式 →