Piles of Boxes

Several days ago, I’ve joined a Hackathon that sponsored by Facebook.

As qualifying people to this event, they hand out an easy algorithm question. Shortly, you need to calculate how less time to move a bunch of boxes in same heigh.

Here is a solution for reference:

import collections

def box(boxesInPiles):
    sortBoxes = collections.OrderedDict(sorted(collections.Counter(boxesInPiles).items()))
    count = 0
    for index, key in enumerate(sortBoxes):
        count += index * sortBoxes[key]
    return count

print(box([4, 5, 5, 2, 4]))


Let’s say there are two persons, Composer and Performer.

The Composer randomly selects three different Pitch which constructed by two part, Note and Octave. Note in the range of “A” to “G”, Octave in the range of “1” to “3”.

For example, here is a typical Pitch combined by ‘A’ and ‘1’, in which ‘A’ is the Note, and ‘1’ is the Octave.

Once Composer selected a Combination, Performer needs to guess it as quick as possible. After each guess, Performer get a feedback which indicates that:

  • how many pitches in the guess are included in the target (correct pitches)
  • how many pitches have the right note but the wrong octave (correct notes)
  • how many pitches have the right octave but the wrong note (correct octaves)

Now, the question is how to get the corrected answer as less times as possible.

--  Subject  : UniMelb 2019 SM1 COMP90048 Declarative Programming
--  File     : Proj1.hs
--  Author   : Mingzhe Du
--  Origin   : Mon Apr 8 2019 
--  Purpose  : This program for guessing a target chord. In each round of the game,
--             the program will generate a chord from a possible set, and then a feedback 
--             against the guess will be given. Depanding on these feedbacks, the aim of this
--             program is get the correct chord with as less as possible guess times.

module Proj1 (Pitch, GameState, toPitch, feedback, initialGuess, nextGuess) where

-- Pitch structure
data Pitch = Pitch { note :: Char, 
                     octave :: Char   
                   } deriving (Eq)
instance Show Pitch where
    show (Pitch note octave) = [note, octave]

-- Game State
data GameState = GameState { times :: Int,                  -- Guess times
                             cCombinations :: [[[Char]]]    -- Possible set
                           } deriving (Eq, Show)

-- Converting String to Pitch                          
toPitch :: String -> Maybe Pitch
toPitch (a:b:t)
    | not (null t) = Nothing
    | (elem note' ['A'..'G']) && (elem octave' ['1'..'3']) = Just Pitch {note = note', octave = octave'}
    | otherwise = Nothing
    where note' = a
          octave' = b

-- Comparing target chord and guessed chord
feedback :: [Pitch] -> [Pitch] -> (Int,Int,Int)
feedback pitch_a pitch_b
    | (length pitch_a == 3) && (length pitch_b == 3) = (c_p, c_n - c_p, c_o - c_p)
    | otherwise = (0,0,0)
    where get_key key = foldr (\x acc -> key x:acc) []
          c_p = getCounter pitch_a pitch_b 0                              -- Correct pitches
          c_n = getCounter (map note pitch_a) (map note pitch_b) 0        -- Correct notes
          c_o = getCounter (map octave pitch_a) (map octave pitch_b) 0    -- Correct Octaves

-- Initial guess
initialGuess :: ([Pitch], GameState)
initialGuess = (currentGuess, gameState)
    where currentGuess = combinationToPitch  (cGuess)
          gameState = GameState 0 all_combinations 
          all_items = getCombination "ABCDEFG" "123"
          cGuess:all_combinations = subsequencesOfSize 3 all_items        -- New guess and new possible set
          getCombination p_note p_octave = foldr (\x acc -> (map (\y -> y:[x]) p_note) ++ acc) [] p_octave
          combinationToPitch combinations = map (\(Just x) -> x) $ map toPitch combinations     -- Converting String to Pitch

-- Get the next guess
nextGuess :: ([Pitch], GameState) -> (Int,Int,Int) -> ([Pitch],GameState)
nextGuess (pGuess, pGameState) pFeedback = (cGuess, cGameState)
    where cGuess':cCombs = getNewCombination pGuess pCombinations pFeedback
          pCombinations = cCombinations pGameState
          cGuess = toChord cGuess'
          cGameState = GameState ((times pGameState) + 1) cCombs 
          toChord = map (\x -> Pitch (x !! 0) (x !! 1))

-- Help Functions 

-- remove an item from a list
removeItem :: (Eq a) => a -> [a] -> [a]
removeItem _ [] = []
removeItem x (y:ys) 
    | x == y = ys
    | otherwise = y : removeItem x ys 

-- get the number of same elements in two lists
getCounter :: (Eq a) => [a] -> [a] -> Int -> Int
getCounter [] y c = c
getCounter  (x:xs) y c
    | elem x y = getCounter xs (removeItem x y) (c+1)
    | otherwise = getCounter xs y c
-- Generate combinations by a specifc size    
subsequencesOfSize :: Int -> [a] -> [[a]]
subsequencesOfSize n xs = let l = length xs in if n>l then [] else subsequencesBySize xs !! (l-n)
    where subsequencesBySize [] = [[[]]]
          subsequencesBySize (x:xs) = let next = subsequencesBySize xs in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])

-- Converting a string list to pitch list
toChord :: [[Char]] -> [Pitch]
toChord a = map (\x -> Pitch (x !! 0) (x !! 1)) a 

-- retrive a new guess
getNewCombination :: [Pitch] -> [[[Char]]] -> (Int, Int, Int) -> [[[Char]]]
getNewCombination guess allCombinations pFeedback = foldr (\x acc -> if checkFeedback (toChord x) then  x:acc else acc) [] allCombinations
    where checkFeedback nChord = if pFeedback == (feedback guess nChord) then True else False

Haskell moment

Here are some Haskell code chunks, which both are simple recursion algorithms.

Quicksort is a sort of poster child for Haskell because everyone does it to showcase how elegant Haskell is.

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort [a | a <- xs, a <= x]
    biggerSoted = quicksort [a | a <- xs, a > x]
in smallerSorted ++ [x] ++ biggerSoted
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "List is empty!"
maximum' [x] = x
maximum' (x:xs) = (max x (maximum' xs))

replicate' :: Int  -> b -> [b]
replicate' n x
    | n <= 0 = []
    | otherwise = (x:(replicate' (n-1) x))

take' :: Int -> [a] -> [a]
take' n (x:xs)
    | n <= 0 = []
    | otherwise = x:(take' (n-1) xs)

reserve' :: [a] -> [a]
reserve' [] = []
reserve' (x:xs) = (reserve' xs) ++ [x]



这是在 St Kilda拍的 远处就是Melbourne City
这张也是在St Kilda拍的 不过不是同一次
这张其实就是上面那张的加长版 去玩完几天之后 Google Assistant自动帮我把照片给合成在了一起
这张实在 Swinburne University的理工主教学楼上拍的 那天忘记带钥匙了 去房东小哥工作的地方去钥匙 偶遇了火烈一般的晚霞
这张是在Poole St家门口拍的 有一种很南国的感觉 看到这张照片总会想到一个人
Flemingtion的公寓有一个漂亮的天台 North Melbourne的景色尽收眼底
Royal park的巨大草坪 每天早上和晚上都会有很多人来这里遛狗和跑步
之前在郊区住的时候 每天晚上都有这样的景色 旁边就是墨尔本电车博物馆
第一次去St Kilda海边的时候拍的 那个时候还在上语言班
Flinder Station的晚霞 那天刚从图书馆出来 感觉整个人都沐浴在光里

BERT based sentence scenario detector

前两天用简单的多层感知器搭建了一个Word-level的detector模型。在模型的最后一次是用来Softmax,将Output Layer进行了分类。

对于场景识别这个问题,我目前先规定了可选的类别(比如Forest/ Ocean/ River/ College/ Suburb/ etc.)。这样一方面来说,可以简化detector的工作流程,另外也比较适应我们组目前的资源情况(识别场景之后需要提取事先准备好的Background,如果提取出了新的element也是无法获取到background resource的)。

上周我的想法是先使用Word embedding将Sentence转化为Sequence,然后使用Bi-LSTM或者直接使用Linear CRF对Sequence进行Sequence Tagging,以提取Sentence中涉及场景的Word。最后通过Word-level detector分析所选的Word,得到Sentence-level Scenario。

不过经过实验我发现,由于我手上只有不到500个短篇的儿童故事,还是没有标注的那种。就算我全部拿来进行标注,也只能生成不到5000个Phases。因为Labeler的资源比较紧张,我先用第一版的词表Detector模型生成了Labeling data,丢到CRF里面之后发现出了Person-entities,其他的类别基本无法有效识别出来。


周五晚上在公司发呆,突然觉得可以试一试力大砖飞的方法,直接使用Sentence-level embedding来作为Input。在这个模型里加入了CNN Layer,但其实单靠Dense Full connect Layer就已经可以在这个数据集上达到同样的效果了。

# 模型构建
model = Sequential([
Conv1D(filters=5, kernel_size=5, strides=1, padding='valid', input_shape=(768, 1), name="Convolution_Layer_1"),
AveragePooling1D(pool_size=5, strides=1, padding="valid", name="Pooling_Layer_1"),

Conv1D(filters=5, kernel_size=5, strides=1, padding='valid', name="Convolution_Layer_2"),
AveragePooling1D(pool_size=5, strides=1, padding="valid", name="Pooling_Layer_2"),


Dense(256, input_dim=3760, name="Dense_Layer_1"),

Dense(32, input_dim=256, name="Dense_Layer_2"),

Dense(11, input_dim=32, name="Dense_Layer_3"),



由于Sequence Tagging需要大量的标注数据,我这边暂时没有数据源,所以今天下午就先用现有的标注数据集做了一个场景Softmax分类器。

原理十分简单,使用Word2vec (之后可能会考虑换成BERT,但是这两天BERT在我这里表现还不是很理想,所以先用顺手的工具搭建一下Demo)生成词向量。之后通过标注数据集合,将词表里所有的词分成以下几个大类(类别可以由具体的使用场景确定,我这里的分类主要是为了适配童话故事的情况)。

# 模型构建
model = Sequential([
Dense(32, input_dim=200),

Dense(16, input_dim=32),

Dense(9, input_dim=32),


 test loss:  0.09276254528926478
test accuracy: 0.9666666666666667

现在这套模型已经可以识别任意词的场景类别了。下一步就是使用Sequence Tagging找出描述场景的位置了。

Virtualenv pip update failure




If you can’t understand Chinese, and just want to update your pip in the virtialenv. Please ignore these blather, typing the following command and hit the Enter:

python -m pip install -U --force-reinstall pip


How to recapture my Oculus Home of Gear VR when I came back China

It has been more than one month that I came back my home country.

However, I recognized I have carried a Samsung Gear VR back until yesterday. It is a fancy equipment, but I met a bunch of trouble when I wanna restart it in China.

Firstly, everything looks normal…

I tried into the virtual space, and got something new. the scenario was seem like the old one, but only two applications can be shown (Samsung Gallery and Internet Browser).

The worst thing is that my library and App Store were vanished, which means I can’t download anything. So I uninstalled all applications and services which are VR-related. Technically, the behavior has been proved as a stupid idea…

Through some very struggle working, I finally recapture the original version of Oculus Home (Or the international version, in another word). Following are what I does:

  1. If you inserted a Chinese SIM card which was activated, the Oculus Home would identify it and then you will be forced updating to the Chinese version. That is the source of this problem.
  2. Now, inserting a oversea SIM card and deactivated your Chinese SIM card (If your phone has two slots of SIM card), and disabling your GPS.
  3. Open your VPN in order to downloading relevant applications and services.
  4. Inserting your phone to Gear VR. All the VR-related services would be updated to international version.
  5. The familiar picture will come back!