Automatic backup of users’ files on a NAS device to an external USB HDD

Password feedback for sudo

Defaults pwfeedback

Make syslog-ng at /dev/tty12 colorful

destination console_all { program("ccze -r >> /dev/tty12"); };

cvechecker 3.9 released

Thanks to updates from Vignesh Jayaraman, Anton Hillebrand and Rolf Eike Beer, a new release of cvechecker is now made available.

This new release (v3.9) is a bugfix release.

Improved AppPasswords in Nextcloud 14

Destructuring assignments in TypeScript

Installing Dropbox in Gentoo Linux following the recent restrictions introduced for Dropbox for Linux

Prevent apple OS from creating .DS_Store and other bullshits

How to move a mouse pointer automatically in Linux to simulate user activity

STLM meetup: The Evolution of Database

Lyft Engineer, Lei Chen reviewed the evolution of databases systems in the STLM meetup. Here are the meeting notes with references and my thoughts.

The Principle

The memory hierarchy of the modern computer dictates how fast we can access the data, and how much data can be stored. The database system is designed to leverage the memory hierarchy to optimize for specialized use cases and make tradeoff between the latency, throughput, and capacity.

Single Host Database

Long long ago, the database is designed for single host due to network performance cannot compete with local storage. Using MySQL architecture as an example:

From bottom up, the MySQL composes several tiers:

• File System provided by the OS.
• Storage Engine handles the data layout to optimize for read / write or something between.
• SQL parser, optimizer, executor provides the SQL semantics.
• Connection pool manages the incoming connections, sockets, file descriptors

There several directions for the scalability:

• Separate read / write operations.
• Sharding: push the scalability problem to the business logic.
• Drop the SQL support, use key-value store instead.
• Replace the local file system with distributed file system
• Some or all of above.

Master-Slave replication

The master-slave replication separates the read / write operations:

• The master and all slaves handle the read operations.
• Only the master accepts the write operation, it then replicates to the slaves synchronously or asynchronously.⁵

Strong consistency requires $R+W>N$R+W>N, see the eventual consistency article .

Sharding

With sharding, we can partition the database horizontally across multiple isolated instances to improve the I/O performance. The sharding logic is either handled by a middleware or the application.

Consistent hashing is commonly used to cushion the repercussion when partition is added or removed.

Key-value store

It is not-trivial to support SQL semantics, especially transactions¹, what if we drop the SQL support for scalability? Without the SQL semantics, the storage engines can be simplified as key-value stores. It is like the hash map, but the data is too big to fit into the memory².

Hash Indexes

We can maintain a in-memory hash table to map the key to the offset of the data file. Clearly, we cannot update the value in-place, that requires us to re-index all the succeeding keys. The data file is organized as:

• append only: any put operation will append a new entry, and the index is updated to point to the new entry.
• segmented: the data file is broken into segments, so we can compact the data file to reclaim used space, and keep the service available.

Bitcask (the default storage engine in Riak) takes this approach.

SSTable, memtable, and LSM-Tree

The hash indexes does not support range selection³, and demand all keys MUST fit into the memory. This shortcomings are addressed by the Sorted String Table, aka SSTable:

• We maintain a balanced tree in memory⁴, aka memtable. Once it grows bigger than the threshold, the data is persisted to a segment with sorted keys.
• The read operation first searches the memtable, then the most recent segments.

Thus, we maintain a sparse index in the memory instead of all keys. This data structure is also known as Log-structured merge-tree or LSM tree.

LevelDB and RocksDB take this approach, and HBase and Cassandra use the similar storage engine.

Distributed File System

With network speed increases, we can replace the local disks with distributed file systems, such Google File System, (see paper). There are many benefits:

• Better throughput and reasonable latency⁶.
• Data integrity and availability are decouple from the DB design.

Case Studies

Aurora

Amazon’s Aurora performs better than the RDS with two magic bullets (See Deep Dive on Amazon Aurora for more details):

1. The underlying file system is replaced by EBS(hot data) and S3(cold data).
2. The master only replicate the write-ahead log, aka WAL to avoid massive I/O.

I am kind of confused by the claim that WAL replication is more efficient; as the WAL write amplification is one of main motive that Uber engineer migrated from pgsql to mysql.

BigTable and Spanner

BigTable leverage the Google File System, SSTable, and Paxos consensus protocol (provided by Chubby?)

Spanner is built upon the BigTable, with atomic clock to ensure global consistency.

Un poème pour Didier

July 22nd, 2018

Une fois, Aimé, avec son capitaine, Didier, a tout gagné.

Ensuite Didier, vingt ans après, son objectif à bien fixé.

Parmi tous les joueurs, une équipe il a dû sélectionné.

Il a pas tardé, que tout le monde lui est venu la contesté.

Patiemment, tous les adversaires il les a éliminé.

Même les sublimes croates, ils ont le mieux essayé.

À la fin, quand même, c'est Didier qui a gagné.

Fixing the network device names

OSCON 2018 Notes

I attended the OSCON 2018 in Portland OR on July 18 – 19. Here are my take-away.

Keynote

Tim O’Reilly delivered the keynote, Open source and open standards in the age of cloud AI and asked a profound question: in the age of cloud AI, are the traditional open source allies, — big corporation such as Google, and Amazon, — turning from collaboration to competing against us?

The open source movement emerged from the great minds’ generosity, and endorsed by IBM with other giant corporation. Both parties benefit from the cooperation until the we hit the top of the S-curve. The relationship MAY change from the cooperation to competition. This also happened in the national level, see Why Nation Fails.

Are we there yet? And if so, what shall we do?

The flourishing Kubernetes ecosystem

The Kubernetes has become the de facto container orchestration platform, and the community focuses on other pain points:

Service Mesh

In the microservice era, the monolithic service is decomposed to many smaller, more modular microservices. The complexity of inter-service grows exponentially¹ and the availability of your service is on the mercy of all upstream service². To build a robust distributed system, we have to manage the upstream services with:

• caching
• retry
• timeout
• rate limiting
• circuit breaking, etc

We can certainly build them in the client-side libraries, such as Hystrix; but this approach does not scale in the current polyglot environment. Since deploying services becomes so trivial, why not just wrap our service with a proxy with all good bits?

Envoy and Istio take this approach, aka sidecar pattern, and support more advanced features for continuous delivery, such as traffic shaping, and traffic shadowing. See the demo from Red Hat’s Christian Posta for more details.

Canary in the continuous delivery

Darren Bathgate also discussed the canary in the continuous delivery. These are tools used in the four phases of canary:

1. Blue/Green Deployment: jenkins tags each deployment with BUILD_NUMBER and push the meta data into the kubernetes deployment.
2. Traffic Shifting: istio then tune the envoy to load balance the blue/ green deployments.
3. Observation: Prometheus and Grafana can monitor the error rate for the blue/green developments.
4. Judgement: we can make a decision based on the observation, or automate with tools such as Spinnaker.

Emerging Languages

TypeScript

The TypeScript is highly influenced by the Benjamin C. Pierce’s work, Types and Programming Languages.

• TypeScript can infer the type from local context for better interoperability with javascript.
• It introduces new language constructs to handle the polymorphism in the javascript land, such as FooType | BarType and keyof.

Elixir and Phoenix

Jay Hayes build a phoenix knockoff in dazzling 40 minutes, it highly entertaining and sheds some lights of the framework:

• The handler function is defined as Endpoint.
• The endpoints are plumbed with Phoenix Router DSL, get, post.
• The middleware is composed with Phoenix’s Controller. To be honest, I did not quite follow the meta programming under the hood as my mind halted and the stomach called for the lunch.

Case study

Expedia’s journey to the Cloud

The scalability challenge: 750M searches per day, 15B flight searches annually.

Cloud Migration Strategy

• Invest to drive the rate of change.
• Know the landscape.
• Define your cloud native.
• Form your Guardrail.
• Getting unstuck: eliminate the ambiguity and apply growth mindset.

Migration Tactics

The services to migrate fall into the following categories:

• New services
• Lift and shift: low pain, low gain.
• Deprecate
• Replatform: untangle for high rate of change
• Move and tune: move as quickly as you can, then iterate with new tools.

Understanding the dependency graph is important.

Define your Cloud Native

1. Embracing cloud service ecosystem, Amazon build services faster than you can adopt.
2. Internalizing cloud economics, see Cloud optimization circus.
3. Accommodate security and control from the beginning.
4. Build resilient service, and test with intentional failure, see Vegas rule.

Resources

These are tools and resources mentioned in the talk worthy a look:

• codefresh: a continuous delivery platform for Kubernetes, it simplifies the helm management.
• helm: the package manager for Kubernetes.
• spiffe: some application security framework beyond my understanding.
• johnny-five: A javascript framework for IoT programming.
• Hyperledger: a open source blockchain framework.

Configuring Lubuntu 18.04 to enable hibernation using a swap file

Capitalism Compromises Design

Capitalism is an economic system based upon private ownership of the means of production and their operation for profit.

Software design always has many competing interests that need to be considered, including quality, time and speed, planning, scalability, security, privacy, cost, and profit.

There are many models and methodologies that present preset weightings and preferences for these interests that are generally agreed upon to be acceptable and even good. “Getting Things Done” emphasizes short-term deliverables and speed arguably at the expense of long-term planning, scalability and quality. Agile can be argued to be the same. As models, they aren’t saying don’t plan at all for growth and scaling, and don’t disregard entirely long-term quality, just don’t “overemphasize” them.

Designing and building software is an exercise in making a multitude of design choices at every step and stage, usually informed by overall goals, approaches, and models.

Capitalism, when introduced into the software design and building process, affects almost every facet immediately, and entire solution spaces are thrown away.

Capitalism elevates profit at the expense of every other interest. Arguments such as “We need a way to monetize, we need access to user data, so we can sell it” of which a subset is “we need to monitor user behaviour in our system, with full metrics, so we can know the user and target them with the best ads” become top priorities in design under capitalism and inform all other decisions.

With these arguments and priorities, capitalism throws away entirely most distributed solutions, often calling into question the viability of end to end encryption (especially for data at rest). They compromise privacy dramatically to the point of obliteration and can usually be demonstrated to weaken security.

In an age where we have many examples of the efficiencies of distributed solutions (BitTorrent for data distribution, pre-Microsoft Skype) it’s sometimes a wonder that a decade later from those innovations, P2P and other decentralized designs never come close to even being mentioned in most design discussions.

Design under capitalism favours centralization over decentralization, and it doesn’t like encryption, generally embracing it only as market demand requires it to keep a product viable.

Decentralization isn’t synonymous with either security or privacy or efficiency, but there is a strong overlap and it can more easily be argued to create a more fertile and easy surface to then build privacy into and efficient systems with. If the user stores their own data, they have control over it and can grant access to it when and only when they consent. Decentralization is more about power, from which privacy can more easily flow. It is still possible to build very inefficient decentralized systems, and even easy to build privacy leaking decentralized solutions. However, it is also possible to build decentralized solutions far more efficient than any centralized solution could ever be and decentralization also lays the groundwork that can allow much stronger privacy systems than a centralized solution can ever guarantee.

It really is very simple. Capitalism wants access to user data, which always degrades privacy. To achieve this it often disregards decentralized solutions entirely, which in-turn can affect many other interests negatively such as scalability and efficiency, favouring “simple” and last decade(s) centralized solutions, which then have to scale awkwardly internally to handle the load demanded of them.

This is why I believe in Open and Free Software. Capitalism and monetization pit the design against users and privacy from the start, and as second-order effects can negatively impact other interests, before the design of a system has even started.

This is why when Open Privacy was deciding how to create itself, we all decided for a nonprofit model over a startup, because there was no viable way we could do the privacy-focused, and user consent enforcing work we wanted to inside of any capitalist model. For us, user privacy had to be the top motivating priority, not profit, and inside capitalism, nothing can trump profit.

The tasting of surströmming

For the uninitiated, Surströmming is an infamous heavily fermented herring.

Below is my experience with it.

Preparations¶

I “smuggled” (more on this below) it from Sweden a few months ago and on the evening before the Swedish national day¹ my brother, a brave (or naïve) soul of a schoolmate of his, and I (not to mention our dog) opened it up near the river. We chose the riverside and the night time strategically, of course.

As was advised to us by a friend, we also took a bucket of water with us. Not – as some may wrongly assume – to vomit into, but to open the tin under water. Due to the fermentation continuing in the tin, it builds up pressure and when you open the tin, it inevitably and violently discharges the bile water. The best way to avoid it spraying your clothes is to open it under water.

The tasting¶

Since this was an impromptu action, – other than the bucket – we came only half-prepared. As condiments we brought only a little bread, a shallot and three pickled gherkins.

The hint with the bucket was greatly appreciated, as the opening of the tin was the most vile part of the whole experience. So if you plan to try it, do get a bucket! It stopped not only the bile spraying us, but also diluted most of the putrid smell that was caught in the tin.

Once opened and aired, the contents of the tin were actually quite recognisable. Fish fillets swimming in brine. The brine was already brownish and a tiny bit gelatinous, but darkness helped us get past that.

As for the taste and texture, if you ever had pickled herrings before – it is like that on steroids, married with anchovies. Very soft, but still recognisable as fish, extremely salty, and with acidity that is very similar to that of good sauerkraut.

Washing the fish in the pickle jar helped take the edge of – both in sense of smell and saltiness. The onion as well as the pickles were a great idea, bread was a must!

In summary, it is definitely an acquired taste, but I can very much see how this was a staple in the past and how it can still be used in cuisine. As a condiment, I think it could work well even in a modern dish.

We did go grab a beer afterwards to wash it down though.

P.S. Our dog was very enthusiastic about it the whole time and somewhat sullen that he did not get any.

The smuggling¶

Well, I did not actually smuggle it, per se, but it took me ¾ of an hour to get it cleared at the airport and in the end the actual carrier still did not know about what I was carrying in my checked luggage. The airport, security, two information desks and the main ground stewardess responsible for my flight were all in on it though. And in my defence, the actual carrier does not have a policy against Surströmming on board (most probably because they have not thought about it yet).

As for acquiring this rotten fish in the first place, I saw it in a shop in Malmö and took the least deformed tin (along with other local specialities). When I came to the cash register with grin like a madman in a sweetshop, I asked the friendly young clerk if she has any suggestion how to prepare it, and she replied that she never had it and knows barely anyone of her generation who did, apart from perhaps as a challenge.

hook out → more fish soon ;)

DFS, BFS and Topological Sort

In this post, we extend the discussion of graph traverse algorithms: breadth-first search, aka bfs; and depth-first search, aka dfs. They try to solve the problem from different angles, more intuitively:

• bfs circulates the neighborhood until our goal is met, we MAY also find the shortest path with DP, see Dijkstra’s shortest path algorithm.
• dfs picks one direction in every crossing until we hits the wall, with appropriate state push / pop, we can backtracking ALL possible solution.

Either way, we build the adjacent list first using collections.defaultdict:

from collections import defaultdict

graph = defaultdict(list)
for start, end in directed_edges:
    graph[start].append(end)
    # For non-directed edges:
    # graph[end].append(start)

It is worthy noting that there exist three states for each vertex:

• not visited: the vertex is unknown in the current state.
• visiting: the vertex is being visited, but its dependencies are not handled.
• visited: all done.

dfs is a typical post-order traversal: the node v is marked as visiting at first encounter, and set as visited only if all its successors are visited. Thus, we can use the dfs to detect the cycle.

def dfs(graph):
    visited = defaultdict(int)  # 0: not visited, -1: visiting, 1: visited.
    return all(do_dfs(graph, visited, v) for v in graph)

def do_dfs(graph, visited, v):
    if visited[v] == -1:
        return False  # cycle detected

    if visited[v] == 1:
        return True  # visited already

    visited[v] = -1
    if all(do_dfs(graph, visited, n) for n in graph[v]):
        visited[v] = 1
        return True
    return False

We can apply the same state transition in bfs, aka the three-color encoding in CLRS P594:

def bfs(graph):
    visited = defaultdict(int)  # 0: not visited, -1: visiting, 1: visited.
    for v in graph:
        if visited[v] == 0:
            do_bfs(graph, visited, v)

def do_bfs(graph, visited, v):
    todo = [v]
    visited[v] = -1  # visiting

    while todo:
        vertex = todo.pop(0)
        for c in graph[vertex]:
            if visited[c] == 0:
                visited[c] = -1
                todo.append(c)
        visited[vertex] = 1

The intermediate visiting state does not help the cycle detection, thus we can simplify the state by visiting the vertex’s children immediately after they are enqueued:

def bfs(graph):
    visited = set()
    for v in graph:
        if v not in visited:
            do_bfs(graph, visited, v)

def do_bfs(graph, visited, v):
    todo = [v]
    visited.add(v)  # visit v

    while todo:
        vertex = todo.pop(0)
        for c in graph[vertex]:
            if c not in visited:
                visited.add(c)  # visit child
                todo.append(c)

In general, bfs is a better choice for graph traverse due to that:

• No recursion, so the size of the problem $\mathrm{\mid }N\mathrm{\mid }$∣N∣ is no longer bound by the maximum stack limit.
• No intermediate visiting state, just visited or not.

Topological Sorting

The topological ordering is defined as reordering the vertices, $u$u and $v$v, $u$u comes before $v$v for every directed edge $uv$uv. More concretely, if vertex $v$v depends on $u$u, then $u$u must be placed before $v$v. There MAY exist more than one solutions, and obviously, the graph MUST not contain cycles.

Topological sorting can be used to fine the critical path in the scheduling problem, and we can attack the problem with the following algorithms:

Depth-first algorithm

This algorithm leverages the dfs: since all my dependencies MUST be placed after me; it is safe to place non-visited vertex $u$u to the head after visiting all its children in the dfs fashion.

Kahn’s algorithm

The Kahn’s algorithm takes the bfs approach:

1. Pick a vertex, $u$u without reverse dependencies, or incoming edge.
2. Find all of adjacent vertices, $v_i$vi​, and remove the edge
3. If vertex $v_k$vk​ no longer has any reverse dependency, add it to the candidate pool.
4. Repeat until the candidate pool is empty. Otherwise, fail due to circular dependencies.

Review of some Vahdam’s Masala Chai teas

Masala chai (commonly and somewhat falsely abbreviated to just “chai”) literally means “spice mix tea” – and this is what this review is about. I got myself a selection of Vahdam’s masala chais and kept notes of each one I tried. Some came in the Chai Tea Sampler and others I either already bought before or were a free sample that came with some other order.

Classical CTC BOP¶

CTC BOP is usually cheaper than more delicately processed whole leaves. Although the common perception is that it is of lower quality than e.g. FTGFOP or even just FOP or OP for that matter, the fact is that they simply a different method with a different outcome. You can get away with breaking cheaper leaves, though, than whole.

Also bare in mind that while BOP is the most common broken leaf grade, there are several more.

It makes for a stronger brew and a more robust flavour– ideal for breakfast teas. The down-side is that it can coat your tongue. But if you want to recycle it, the second steep will be much lighter.

Original Chai Spiced Black Tea Masala Chai¶

The quintessential masala chai – the strength of the CTC BOP, paired with the classic mix of spices. A great daily driver and a true classic, but for my personal taste a tiny bit too light on the spice.

Ingredients: CTC BOP black tea, cardamom, clove, cinnamon, black pepper

Double Spice Masala Chai Spiced Black Tea¶

Same as India’s Original Masala Chai above, but with a bigger amount of spice. Of the two I definitely prefer this one.

Ingredients: CTC BOP black tea, cardamom, clove, cinnamon, black pepper

Fennel Spice Masala Chai Spiced Black Tea¶

Due to the fennel, the overall taste reminds me a lot of Slovenian cinnamon-honey cookies¹, which we traditionally bake for Christmas. The odd bit is the cookies do not include the fennel at all, but most of the other spices in a classic masala chai (minus pepper). I suppose the fennel sways it a bit to the sweet honey-like side.

In short, I really liked the fennel variation – could become firm winter favourite of mine.

Ingredients: CTC BOP black tea, fennel, cardamom, clove, cinnamon, black pepper

Saffron Premium Masala Chai Spiced Black Tea¶

When I saw the package I thought that saffron was more of a marketing gimmick and I would only find a strand or two in the whole 10g package. But no! The saffron’s pungence punches you in the face – in a good way. It felt somewhat weird to put sugar and milk into it, so strong is the aroma.

Personally, I really like it and it does present an interesting savoury twist. It is a taste that some might love and others might hate though.

Ingredients: CTC BOP black tea, cardamom, cinnamon, clove, saffron, almonds

Earl Grey Masala Chai Spiced Black Tea¶

I am (almost) always game for a nice spin on an Earl Grey. In this case, the standard masala complements the bergamot surprisingly well and in a way where none of the two particularly stand out too much.

The combination works so well that it would feel wrong to call it a spiced-up Earl Grey or a earl-grey’d masala chai. It is a pleasantly lightly spiced, somewhat citrusy and fresh blend that goes well with or without milk.

Ingredients: CTC BOP black tea, bergamot, cardamom, cinnamon, clove, black pepper

Cardamom Chai Masala Chai Spiced Black Tea¶

Now, this one is interesting because it only has two ingredients – black tea and cardamom. While not as complex in aroma as most others, it is interesting how much freshness and sweetness a quality cardamom pod can carry.

I found it equally enjoyable with milk and sugar or without any of the two.

Ingredients: CTC BOP Assam black tea, cardamom

Sweet Cinnamon Massala Chai Black Tea¶

Similar to their Cardamom Chai, it is a masala chai with very few ingredients. The cinnamon and cardamom get allong very well and while it lacks the complexity of a full masala/spice mix, it is a very enjoyable blend.

Recommended especially if you like your masala chai not too spicy, but sweet.

Ingredients: CTC BOP Assam black tea, cardamom, cinnamon

Ortodox black¶

What is described with “orthodox” usually means a whole leaf grade, starting with OP. These are much weaker than CTC, but therefore bring out the more delicate flavours. It is a bigger challenge therefore to make sure spices do not push the flavour of the tea too much into the back-seat.

Because the leaves are whole, as a rule you can get more steeps out of them than of broken leaves.

Assam Spice Masala Chai Spiced Black Tea¶

The more refined spin on the classic masala chai – with whole leaves of a quality Assam, it brings a smoothness and mellowness that the CTC cannot achieve. Because of that the spices are a bit more pronounced, which in my opinion is not bad at all. The quality of the leaf also results in a much better second steep compared to the CTC.

Most definitely a favourite for me.

Ingredients: FTGFOP1 Assam black tea, cardamom, cinnamon, clove, black pepper

Tulsi Basil Organic Masala Chai Spiced Black Tea¶

I have not had the pleasure of trying tulsi² and regarding masala chais, this is a very peculiar blend. The taste of the Assam is quite well hidden behind the huge bunch of herbs. In fact, for some reason it reminds me more of the Slovenian Mountain Tea than of a masala chai.

In the end, the combination is quite pleasant and uplifting.

What I found fascinating is that it tastes very similar both with milk and sugar, and without any of the two.

Ingredients: organic Assam black tea, tulsi basil, cinnamon, ginger, clove, cardamom, black pepper, long pepper, bay leaves, nutmeg

Darjeeling Spice Masala Chai Spiced Black Tea¶

As expected, the Darjeeling version is much lighter and works well also without milk, or even sugar. Still, a tiny cloud of milk does give it that extra smoothness and mellowness. It is not over-spiced, and the balance is quite well. The taste of cloves (and perhaps pepper) are just slightly more pronounced, but as a change that is quite fun. It goes very well with the muscatel of the Darjeeling.

Ingredients: SFTGFOP1 Darjeeling black tea, cardamom, cinnamon, clove, black pepper

Oolong¶

Maharani Chai Spiced Oolong Tea¶

Despite the fancy abbreviation, IMHO the oolong tea itself in this blend is not one you would pay high prices as a stand-alone tea. Still, I found the combination interesting. If nothing else, it is interesting to have a masala chai that can be drank just as well without milk and sugar as with them.

Personally, I found the spice a bit to strong in this blend for the subtle tea it was combined with. I actually found the second steep much more enjoyable.

Ingredients: SFTGFOP1 Oolong tea, cardamom, cinnamon, clove, black pepper

Green¶

Kashmiri Kahwa Masala Chai Spiced Green Tea¶

A very enjoyable and refreshing blend, which I enjoyed without milk or sugar. The saffron is not as heavy as in the Saffron Premium Masala Chai, but goes really well with the almonds and the rest of the spices.

When I first heard of Kashmiri Kahwa, I saw a recipe that included rose buds, so in the future I might try adding a few.

Ingredients: FTGFOP1 green tea, cardamom, cinnamon, saffron, almonds

Green Tea Chai¶

As is to be expected, the green variety of the Darjeeling masala chai is even lighter than its black Darjeeling counterpart. The spice is well-balanced, with cinnamon and cloves perhaps being just a bit more accentuated. This effect is increased when adding milk.

It goes pretty well without milk or sugar and can be steeped multiple times. Adding either or both works fine as well though.

Quite an enjoyable tea, but personally, in this direction, I prefer either the Kashmiri Kahwa or the “normal” Darjeeling Spice masala chais.

Ingredients: FTGFOP1 darjeeling green tea, cardamom, cinnamon, clove, black pepper

hook out → hopefully back to blogging more often

Getting the lock screen to work reliably when resuming from suspension in a single-seat, multi-user Lubuntu 18.04 installation

Dynamic Programming Recap

Dynamic Programming, aka DP, “solves the problem by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems is said to have optimal substructure”(see Wikipedia). More concretely, the problem suffice the Principle of Optimality:

Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. (See Bellman, 1957, Chap. III.3.)

Or mathematically, to solve the problem from t to T optimally, we can solve a sub-problem from t to s given t < s < T and extend s to T.

It is relatively intuitive to reason the optimal substructure for most problems, we will only focus how to build up the optimal solution in this post.

Top-down vs. bottom-up

We are trained to solve the problem in the top-down approach: break down a big problem to several smaller problems, recursively doing so until the smaller problems can be comfortably tackled. CLRS points out that the time complexity of top-down with memoization is the same as the bottom-up approach, but the latter is preferred as the top-down approach requires $O\left(n\right)$O(n) callstacks which caps the problem scope.

Using the #322 Coin Change problem as one example:

Given the amount with different coin denominations, find the fewest coins to make up the amount.

In the top-down approach, the problem can be decomposed as:

f(amount) = min(f(amount - c) for c in coins) + 1

We can convert the recursion to a forward loop with the lookup table, dp:

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for index in range(1, amount + 1):
        for c in coins:
            if index >= c:
                dp[index] = min(dp[index], dp[index - c] + 1)

    return dp[-1] if dp[-1] < float('inf') else -1

Look back vs. Look forward

We solve the DP problems by looking back the sub-problems; on the other hand, some problems require us to look forward: the solution for the current sub-problem depends on the sub-problems in the future. Technically, they SHOULD be categorized as BFS, — the solution space is explored with the breadth first search. They are discussed here just for the reference.

For example, the #55 Jump Game:

Given an array of non-negative integers, each element specifies the maximum jumps at that position, determine whether you are able to reach last index from the first index*.

If we consider positions as a nodes, and the jump as the directed connection; the problem is transformed whether there exists a path from start to the end.

from collections import deque


def can_jump_bfs(nums):
    if len(nums) <= 1:
        return True

    # Push the first position to the queue, and mark it visited.
    queue = deque([0])
    bfs = [False] * len(nums)
    bfs[0] = True

    while queue:
        pos = queue.pop()  # optimization: pop from the end of queue
        for step in range(1, nums[pos] + 1):
            jump_to = pos + step
            if jump_to == len(nums) - 1:
                return True

            # Append to the queue if not visited.
            if not bfs[jump_to]:
                bfs[jump_to] = True
                queue.append(jump_to)

    return False

Multi-dimension DP

In practice, I’ve only seen the two types of problems attacked by the two-dimension DP:

1. the problem space is defined as $m\times n$m×n, such as the Smith-Waterman algorithm.
2. the problem space is linear, but the sub-problem MUST be solved from any arbitrary (i, j) range, such as multiply matrix product.

In this section, let’s discuss the second case with the #312. Burst Balloons:

Given n balloons with designated values, burst balloon i will get nums[left] * nums[i] * nums[right] coins, try to maximize the gain.

If we add two balloons with value of 1 on both sides, the original problem become: with n + 2 balloons from 0 to n + 1 and balloons[0] == balloons[n + 1] == 1, burst balloons from 1 to n, maximize the profit.

If we burst balloons[i] first, the balloons[i - 1] and balloons[i + 1] become adjacent. The solution to the sub-problem grows complicated due to the bookkeeping of adjacent balloons. Instead, we can divide-and-conquer the problem by focusing on the last balloon to burst: if balloons[i] is the last balloon to burst, the accumulated coins are:

$f(0,i)+f(i,n+1)+nums\left[0\right]\times nums\left[i\right]\times nums[n+1]$f(0,i)+f(i,n+1)+nums[0]×nums[i]×nums[n+1]

• The ith balloons is the last balloon too burst, so the last trio is (0, i, n + 1).
• Recall the f method will NOT burst the balloon on the boundary, so only balloon[1] to balloons[i - 1] are bursted in f(0, i).
• The same rule applies to f(i , n + 1).

The problem can be solved by two sub-problems in the top-down fashion. If we build the DP table from the bottom up:

• initialize the dp matrix $(n+2)\times (n+2)$(n+2)×(n+2)
• we can expect minimum 3 balloons for any dp[i][j], apply the logic.
• extend the range of (i, j) until we get (0, n + 1).

def max_coins(nums):
    n = len(nums)
    nums = [1] + nums + [1]
    # dp is (n + 2) * (n + 2) matrix
    dp = [ [0] * (n + 2) for i in range(n + 2)]

    # With nums[0] and nums[n + 1] present, we can expect 3 balloons as minimum
    for gap in range(2, n + 2):
        for first in range(0, n + 2 - gap):
            last = first + gap
            if last - first == 2:
                dp[first][last] = nums[first] * nums[first + 1] * nums[last]
            else:
                dp[first][last] = max(
                    dp[first][j] + dp[j][last] + nums[first] * nums[j] * nums[last]
                    for j in range(first + 1, last)
                )
    return dp[0][n + 1]

Multiple-pass DP

In some special case, we can optimize the multiple-dimension DP to multiple-pass DP. For example, #123 Best Time to Buy and Sell Stock III:

Given the stock price for each day, maximize the profit with two transactions.

Consider we keep tracks the balance[i], we can maximize the balance by:

• find the time to buy low, aka maximize balances[i] - prices[i]
• find the time to sell high, aka maximize balances[i] + prices[i]

We can repeat k times(k = 2 in this case) to fully exploit the market.

def max_profits(prices):
    balances = [0] * len(prices)

    for t in range(2):
        best_buy = float('-inf')
        best_profit = 0

        for i, price in enumerate(prices):
            best_buy = max(best_buy, balances[i] - prices[i])
            best_profit = max(best_profit, best_buy + prices[i])
            balances[i] = best_profit
    return balances[-1]

Conclusion

In this post, we demonstrate several use cases of the dynamic programming from different angles for a better understanding. The cornerstone of DP is how to break down the problem to sub-problems for the optimal solution, then we can build the solution in the bottom-up fashion.

Weather via command line

Worldwide GPS tracks with OpenStreetMaps for urban design analysis

I work as an architect, and one of the data available to us when masterplanning and early phases of an urban design project is GPS track activity. Knowing where people drive, where people walk, and cycle and recreate allows us to make decisions such as where to define architectural axes, where to place retail, and how to extend public transport and pedestrian walkways.

One of the resources available is from a company known as Strava, who runs a proprietary fitness social network, where fitness buffs can track their movements via GPS devices (which can be as simple as your phone) and compare cycling routes, distances run, and so on. Primarily used by runners and cyclists, these GPS logs are voluntarily uploaded to Strava, who then aggregates all the data and resells it to urban design parties, known as their “Strava Metro” initiative.

Publicly without purchasing any data, Strava also hosts a global GPS heatmap where you can visually see the fire of activity by runners and cyclists. Zooming in shows you right down to where people run down various streets. As a high-level overview, this is a great graphic and can immediately pinpoint activity. It also is a fantastic feat of engineering, processing 5 terabytes of raw input data. That’s big data!

Of course, just recently Strava decided to stop showing this public heatmap at high zoom levels and locked it behind a paywall. Thankfully, there are alternatives.

In a previous post, I introduced an open-data initiative known as OpenStreetMaps. Strava is largely based on OpenStreetMaps and uses it as a base layer embedded into MapBox, and also has a fork of the OSM iD editor called “Strava Slide”, to allow people to edit routes based off strava GPS data tracks. However, OSM itself has many active GPS track contributors (used for various purposes, such as mapping new routes and calibrating the map), and we can use this open data in lieu of the proprietary product offered by Strava. Below, we see the world’s GPS tracks from the perspective of OSM visualised by Pascal Neis.

Before I get into the specifics of getting GPS data, I’d like to show you what data is in a GPS track. Here’s some GPS tracks visualised with JOSM. We can see things like speed, direction, and sometimes, elevation, if it is recorded. See those red segments of the line? Those are traffic lights!

OSM has an API and Planet GPS extract available to download GPS data. The Planet GPX is rather unwieldy, and is also very outdated (from 2013). The API is not the best either, in that it only returns 5,000 GPS points per query, and doesn’t quantify the total pages of results, so that you can’t really tell with one query how many points you need to fetch in advance. However, if you query the API and put a page number higher than what is available, it won’t return any points. So using a binary search you can find out how many pages to extract.

For the area of Sydney, there are roughly 750 pages of results, so that means just under 4 million GPS points. Here’s a heat map visualisation of it I made using QGIS (but JOSM also has a heat map visualisation feature). You won’t need huge supercomputers processing the data, either.

Here’s another of Manhattan, New York.

We can couple this visualisation with other OSM data such as all public transport nodes. In this case, railway tracks, bus routes, ferry routes, cycling routes, train stations, and bus stops are shown. This is also created with QGIS.

There are a few pros and cons to using this GPS data. The pro is that it’s more general purpose: it’s not only used by runners and cyclists, it’s used by regular people (well, GIS geeks) doing everyday things like shopping. Unfortunately, OSM isn’t that widely used, and so the data is relatively sparse. In remote areas perhaps no-one has walked that route, or only a few people have. So you don’t get a sense of what they’re doing. The GPS data is also not processed, so you’ll have to do your own cleaning: especially in the city where GPS data goes a bit haywire with all the tall buildings.

Have fun and happy mapping!

The post Worldwide GPS tracks with OpenStreetMaps for urban design analysis appeared first on thinkMoult.

Installing the Onboard on-screen keyboard in Gentoo Linux

Edmondson Park – a retail and residential development by Frasers and HDR

Three weeks ago, 30 kilometers away from the Sydney city centre in the rural suburb of Edmondson Park, Frasers Property Australia opened the doors of their display centre to the public. This brand new town centre development with residential and retail environments was designed by HDR Inc, of which I am part of the team of architects. I haven’t really talked much about my architecture work before, but a brand new town centre in a previously uneventful part of Sydney is perhaps worth a blog article.

Perhaps let’s start with the blurb of the development which I’ve copied directly from the Frasers official Ed Square website:

From the makers of Central Park Sydney, Ed.Square brings inner city edge, but with so much more than you expected.

Ed.Square is a diverse urban neighbourhood of restaurants and cafes; shopping and entertainment; playgrounds and parklands; a market place and Eat Street; adjacent to the Edmondson Park train station and all within walking distance from your own front door.

Ed offers an array of residences crafted by some of the worlds best architects that cater for every lifestyle. Whether you are a first home buyer or a multi-generational family, you’ll always feel at home with Ed.

Sydney’s South West is one of Sydney’s growth trajectories, and so the Edmondson Park development is one of those which will supply the population growth.

Despite working on the development, I probably don’t have any permission to use any marketing material, so you’ll have to visit the Frasers website to see all the pretty pictures and marketing.

However, I did take some snaps of the display suite, so here it is! Let’s start with the view you get as you enter. To the left are some display town houses. They are three storey products which surround the town centre. If you use some imagination you can read that there is the huge word “Ed.” written in bright yellow in front of it. Ed’s pretty hip, and is the anthropomorphism of the neighbourhood. To the right, you can see a cafe by the display centre itself, which apparently serves some pretty tasty dishes that the local community loves — but it was closed when I arrived.

Here’s what you see as you enter…

And a snap of the physical model…

Let’s zoom in! The orange letter “T” is the train station, so you can see that the town centre is literally adjacent to it. The white buildings have yet to be released, so stay tuned.

Here’s another angle, showing the grand cinema facade.

There’s a display apartment too …

… which shows some of the apartment, such as this fancy kitchen.

Here’s another view from the balcony of one of the town houses looking at the display suite. In the background you can see a huge pit where construction will occur, surrounded by Cumberland Plain Woodland. I hear there could be koalas living there.

If you live in Sydney, feel free to drop by!

The post Edmondson Park – a retail and residential development by Frasers and HDR appeared first on thinkMoult.

OpenStreetMaps – an open-source Maps application

Recently I’ve been interested in an initiative known as OpenStreetMaps. Launched in 2004, OpenStreetMaps is the open-source equivalent of Google Maps, and functions largely like how Wikipedia does (and in fact was inspired by Wikipedia) – it’s a map of the world drawn completely by volunteers and open-source enthusiasts.

You might’ve already seen OSM in action. Below it’s used by default in the privacy-friendly search engine DuckDuckGo, other wiki-based projects like WikiVoyage, and many games use it as a base layer, such as Pokemon Go.

You’ve probably used Google Maps before and have it installed on your phone to help you drive to places with the GPS. You may have also played with Bing Maps which essentially does the same thing. At first glance OpenStreetMaps is purely a clone: you can zoom in and out, look at street names and see buildings, and have it tell you how to drive to a destination. It’s not that exciting, and isn’t worth talking about.

However if you were a user of OSM, occasionally you might notice areas of the map where volunteers have gone above and beyond to draw details of the environment that other maps will not. Things like individual driveways, articulated building outlines, kerbside grass, wheelchair accessible walkways and kerb ramps, and individual bush and tree locations, fences, and parking niches. Zooming in we can identify storm drains, streetlamps, water taps and park benches. This level of detail is possible because the map is created by people who are genuinely interested and express a love and care in their work. The example below is in Brisbane, Australia, largely by a fellow called ThorstenE.

Where OSM really excels is as an open-data resource. Usually, you are only limited to raster map images produced by Google Maps and Bing, but aren’t allowed to access the underlying database of geographic and vector information. In contrast, because the data in OSM’s database is free for everyone, specialist maps can easily be created. Take for example the extensive mapping of skiing and snowboarding tracks in Oslo, Norway provided by OpenSnowMap…

… alternatively there is the Whitewater rafting map in the UK …

… and the OpenCycleMap which maps the world’s bicycle routes, and shows the incredible culture of pedestrian and cycling friendly urban planning in the Netherlands.

OSM also helps lead the way in humanitarian mapping. When a flood, fire, earthquake or other natural disaster occurs, existing maps provided by Google and Bing are no longer current. Mappers need to create new maps to allow disaster relief teams to coordinate their efforts, target houses for rescues efficiently, or to know what routes relief organisations can take to navigate the terrain. This work is done by the excellent Humanitarian OpenStreetMap Team. It also includes non natural disasters, such as mapping demographics and environmental issues related to poverty elimination, gender equality, refugee response strategies, public disease outbreaks, clean energy, and water and sanitation. As one current example, right this minute the Monsoon rains have caused severe flooding in the Kurunagala and Puttalam districts of Sri Lanka. A map is being prepared so that first respondents and aid agencies can deliver relief supplies. A grid of zones with their mapping progress is updated in real time below.

As an open-source creation, it doesn’t data-mine your activity so you can use it as a Maps application without privacy concerns, you can download the raw vector so you can use it offline on your phone, and has a conservative approach to licensing data that allow people who want to embed OSM technologies in their own creations in a much more flexible manner. If you feel strongly about supporting privacy-aware applications (especially after the Cambridge Analytica scandal), and encouraging communities that aren’t motivated by profit, OpenStreetMaps should be something to consider. There are over 1,000,000 mappers who have contributed to OSM, and you can become one of those too.

One of the most amazing things about OSM is that whereas mapping the world is an inherently complex process, it has managed to make it easy and fun and doable by anybody who knows how to draw a rectangle with their mouse. Most of the other open-source initiatives have a high learning curve and lots of technical prerequisites, but OSM is completely the opposite. Just zoom into your city on OSM.org and click the Edit button on the top left. It will give you a short tutorial that lets you draw new roads and buildings within minutes. The thought that has gone into the user-friendliness of this online map editor is absolutely incredible.

I’ll talk about OSM a bit more in upcoming posts, and share some of the more interesting technical sides of things.

The post OpenStreetMaps – an open-source Maps application appeared first on thinkMoult.