What open-source projects have I contributed to Github in 2020?

Today is the last day of 2020, which means it is time to have my 2020 Github Rewind! Last year I've had 1,775 contributions on Github and I got 4,104 contributions as of today. You can see my Github profile [here](https://github.com/wingkwong).  Let's go through what I've worked on one by one in an arbitrary order. ## vote4hk/warsinhk  [warsinhk](https://github.com/vote4hk/warsinhk) is a static website for [covid19.vote4.hk](covid19.vote4.hk). I've developed some components such as alert message boxes, datepicker, share buttons and etc, integreated react-i18next, did some bug fixing and revised the documentation. ## aws/aws-sam-cli [aws-sam-cli](https://github.com/aws/aws-sam-cli) is a CLI tool to build, test, debug, and deploy Serverless applications using AWS SAM.  I've worked on a bug ticket with Jacob who is a senior software engineer at AWS. The bug was about the attribute ``Command.ScriptLocation`` not being updated for ``Glue::Job`` when running ``sam build`` because dot notations were not supported. At the beginning, my implementation was a bit complicated and Jacob suggested to use ``jmespath`` to handle the querying for nested attributes in JSON instead. The pull request was merged after 2-month discussion. ## wingkwong/hk-address-parser [hk-address-parser](https://github.com/wingkwong/hk-address-parser) is an unofficial library for [Hong Kong Address Parser](https://g0vhk-io.github.io/HKAddressParser/#/), designed for Python applications. The usage is pretty simple. ``` from hk_address_parser import AddressParser # Single Query address = AddressParser.parse( "Eaton Hotel, 380 Nathan Road, Jordan") # Batch Query addresses = AddressParser.parse( [ "九龍觀塘海濱道 181號 9樓", "九龍長沙灣道 303號長沙灣政府合署 12樓", "九龍啟德協調道 3號工業貿易大樓 5樓", "香港中環統一碼頭道 38號海港政府大樓 7樓", "香港北角渣華道 333號北角政府合署 12樓1210-11室", "九龍旺角聯運街 30號旺角政府合署 5樓 503室", "九龍觀塘鯉魚門道 12號東九龍政府合署 7樓", "九龍深水埗南昌邨南昌社區中心高座 3樓", "九龍黃大仙龍翔道 138號龍翔辦公大樓 8樓 801室", "新界沙田上禾輋路 1號沙田政府合署 7樓 708-714室", "新界大埔墟鄉事會街 8號大埔綜合大樓 4樓", "新界荃灣大河道 60號雅麗珊社區中心 3樓", "新界屯門震寰路 16號大興政府合署 2樓 201室", "新界元朗橋樂坊 2號元朗政府合署暨大橋街市 12樓" ] ``` Then you can call the [methods](https://github.com/wingkwong/hk-address-parser#methods) to get the corresponding info. ## cli/cli  [cli](https://github.com/cli/cli) is GitHub’s official command line tool written in Go. I've worked on the command ``gh gist create`` which is used to create a new Github gist with given contents. The feature has been released. For the usage, please check out the official documentation [here](https://cli.github.com/manuala/gh_gist_create). ## aws/copilot-cli  [copilot-cli](https://github.com/aws/copilot-cli) is a tool for developers to build, release and operate production ready containerized applications on Amazon ECS and AWS Fargate. I was responsible for a few bug fixing tickets and a feature adding an optional env flag to the command ``app delete`` with test cases. ## wingkwong/k8sgen  [k8sgen](https://github.com/wingkwong/k8sgen), written in Go, is an utility which is designed to guide users to build their Kubernetes resources in an interactive CLI. At that time I was learning k8s and drilling down into the details of its internal designs. It was an experimental project. ```bash k8sgen jumpstart _ ___ | | _( _ ) ___ __ _ ___ _ __ | |/ / _ \/ __|/ _ |/ _ | |_ \ | | (_) \__ | (_| | __| | | | |_|\_\___/|___/\__, |\___|_| |_| |___/ ? What kind of object you want to create? [Use arrows to move, type to filter] ClusterRole ClusterRoleBinding Configmap > Deployment Job Namespace PodDisruptionBudget PriorityClass Quota Role RoleBinding Secret Service ServiceAccount ? What deployment you want to name? my-deployment ? What image you want to name to run? busybox ? Please select an output format yaml json > yaml ? What directory you want to save? /home/wingkwong/deployment.yaml ``` Result: ``` apiVersion: apps/v1 kind: Deployment metadata: creationTimestamp: null labels: app: my-deployment name: my-deployment spec: replicas: 1 selector: matchLabels: app: my-deployment strategy: {} template: metadata: creationTimestamp: null labels: app: my-deployment spec: containers: - image: busybox name: busybox resources: {} status: {} ``` ## cortexlabs/cortex  [Cortex](https://github.com/cortexlabs/cortex) is an open source platform for large-scale inference workloads. I added a feature to support ``.cortexignore`` file to exclude files/directories from cortex project zip and also updated AWS resource metadata. ## wingkwong/react-quiz-component [react-quiz-component](https://github.com/wingkwong/react-quiz-component) is a ReactJS component allowing users to attempt a quiz. I've added some new features and worked on some bug fixing tickets. Currently it got 10K+ downloads in NPM. ## alexellis/k3sup  [k3sup](https://github.com/alexellis/k3sup) is a light-weight utility to get from zero to KUBECONFIG with k3s on any local or remote VM. All you need is ssh access and the k3sup binary to get kubectl access immediately. I've made a pull request with the changes to add ``app info`` sub-command to show post-install instructions for an app and the app homepage link, so that users don't have to unnecessarily install again to see them, which was the only way till now to see post install instructions. The changes were implemented for nginx-ingress, cert-manager, metrics-server, tiller, linkerd, cron-connector, kafka-connector, minio, postgresql, kubernetes-dashboard, istio, and crossplane commands. ## inlets/inlets & inlets/inletsctl  [inlets](https://github.com/inlets/inlets) is a Cloud Native Tunnel written in Go and [inletsctl](https://github.com/inlets/inletsctl) creates inlets tunnel servers in the cloud. The same bug was found in both repository. When running ``get.sh``, the program will fail if the target folder contains a space. Therefore I made the same fix to both repository. The fix was simple enough - just added several double quotes. ## My Self-Learning Playgrounds I learn something new by doing when I feel bored. Here's the list. - [aws-playground](https://github.com/wingkwong/aws-playground) - [azure-playground](https://github.com/wingkwong/azure-playground) - [gcp-playground](https://github.com/wingkwong/gcp-playground) - [qsharp-playground](https://github.com/wingkwong/qsharp-playground) - [nlp-playground](https://github.com/wingkwong/nlp-playground) - [deno-playground](https://github.com/wingkwong/deno-playground) - [gRPC-playground](https://github.com/wingkwong/gRPC-playground) - [argocd-playground](https://github.com/wingkwong/argocd-playground) - [skaffold-playground](https://github.com/wingkwong/skaffold-playground) - [traefik-playground](https://github.com/wingkwong/traefik-playground) - [lxd-playground](https://github.com/wingkwong/lxd-playground) ## wingkwong/competitive-programming [competitive-programming](https://github.com/wingkwong/competitive-programming) contains CP solutions (mostly written in C++) from different OJs and contest sites with explanations. I believe most of the commits come from this repository as I've solved quite a lot of problems this year.  Competitive programming is a mind sport for programmers to solve mathematical or logical problems. I started my CP journey in 2014 and I had a chance to participant in ACM-HK Collegiate Programming Contest in 2015. I took a long break since then. Most of the people practice lots of CP problems just to get into FANNG companies but I only treat it as a hobby. ## Conclusion In 2020, I mainly worked on CLI projects in Go, practiced 1000+ CP problems in C++, and learned cloud native stuff. In the next year, I believe I'll focus on advanced algorithms. Probably I'll try to use different programming languages to solve the CP problems to sharpen my programming skills.

Finding Longest Palindrome in O(n) Using Manacher's Algorithm

You can practice the problem [here](https://cses.fi/problemset/task/1111/). Given a string, your task is to determine the longest palindromic substring of the string. For example, the longest palindrome in aybabtu is bab. A palindrome here is a string which reads the same backward as forward. We can use functions like ``reverse`` to check if the given string is a palindrome or not. ```cpp bool is_palindrome(string s) { string t = s; reverse(t.begin(), t.end()); return s == t; } ``` Or we can use two pointers. ```cpp bool is_palindrome(string s) { int l = 0, r = (int) s.size() - 1; while(l < r) { if(s[l] != s[r]) return false; else l++, r--; } return true; } ``` The first approach is brute force. ```cpp int n = (int) s.size(), start = 0, mx_len = 1; REP(i, n) { REP(j, i) { int ok = 1; REP(k, (j - i + 1) / 2) { if(s[i + k] != s[j - k]) ok = 0; } if(ok && (j - i + 1) > mx_len) { start = i; mx_len = j - i + 1; } } } OUT(s.substr(start, mx_len)); ``` However, the time complexity for this solution is O(n ^ 3) because we need three nested loops to find the longest palindromic substring. It only works when n is really small. The second approach is dynamic programming. The time complexity can be further reduced to O(n ^ 2). We use dp[i][j] to indicate if s[i] .. s[j] is a palindrome or not. Let's think about the transitions. 1. If i == j, that means s[i] == s[j], a single character is a palindrome. Example: a. 2. If i + 1 == j and s[i] == s[j], then s[i] .. s[j] is a palindrome. Example: aa. 3. If dp[i + 1][j - 1] and s[i] == s[j], then s[i] .. s[j] is a palindrome. Example: abba. As we can see, dp[i + 1][j] needs to be calculated before d[i][j]. Therefore, we iterate i from n - 1 to 0 and j from i + 1 to n. ```cpp int n = (int) s.size(); vvi dp(n, vi(n, 0)); string ans; int start = 0, len = 1; REP(i, n) dp[i][i] = 1; FORD(i, n - 1, 0) { FOR(j, i + 1, n) { if(s[i] == s[j]) { if(i + 1 == j || dp[i + 1][j - 1]) { dp[i][j] = 1; if(len < j - i + 1) { start = i; len = j - i + 1; } } } } } OUT(s.substr(start, len)); ``` With dynamic programming, the time cplexity and auxiliary space are O(n ^ 2). However, we can solve the problem in linear time using Manacher's algorithm. As a palindrome has a symmetric property at the center position, it could help us to reduce some unnecessary computations. If there is a palindrome of length N centered at position P, we can avoid the comparisions after position P as we already calculated longest palindromic substring at position before P. However, an even palidrome has two centers, which makes the calculate a little bit different than the one calculating for an odd palindrome. Here's the implementation in C++. ```cpp string manacher(string s) { int n = (int) s.size(); // d1[i]: the number of palindromes accordingly with odd lengths with centers in the position i. // d2[i]: the number of palindromes accordingly with even lengths with centers in the position i. vector d1(n), d2(n); int l1 = 0, r1 = -1, l2 = 0, r2 = -1, mx_len = 0, start = 0; for (int i = 0; i < n; i++) { // ---------------------- // calculate d1[i] // ---------------------- int k = (i > r1) ? 1 : min(d1[l1 + r1 - i], r1 - i + 1); while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++; d1[i] = k--; if (i + k > r1) l1 = i - k, r1 = i + k; if(d1[i] * 2 > mx_len) start = i - k, mx_len = d1[i] * 2 - 1; // ---------------------- // calculate d2[i] // ---------------------- k = (i > r2) ? 0 : min(d2[l2 + r2 - i + 1], r2 - i + 1); while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) k++; d2[i] = k--; if (i + k > r2) l2 = i - k - 1, r2 = i + k; if(d2[i] * 2 > mx_len) start = i - k - 1, mx_len = d2[i] * 2; } // return the longest palindrome return s.substr(start, mx_len); } ``` If you want to count how many palindromic substrings in the given string, simply sum d1[i] and d2[i] where i = 0 .. n - 1. ```cpp int cnt = 0; for(int i = 0; i < n; i++) cnt += d1[i] + d2[i]; ``` This problem can also be solved using fast LCA in O(n) or String Hashing O(nlogn). These methods will not be discussed in this post. You can find the whole solution [here](https://github.com/wingkwong/competitive-programming/blob/09531f2fbfbf03393ba3e744cb77858134463e29/cses/string-algorithms/1111-longest-palindrome.cpp).

BOJ 1890 - 점프

# 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. # 입력 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다. # 출력 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다. # 예제 입력 ``` 4 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0 ``` # 예제 출력 ``` 3 ``` # 정답 ```cpp const int mxN = 105; ll n, dp[mxN][mxN], vis[mxN][mxN], g[mxN][mxN]; int dx[2] = {1, 0}, dy[2] = {0, 1}; ll dfs(int x, int y) { vis[x][y] = 1; if(x == n - 1 && y == n - 1) return 1; if(dp[x][y] || g[x][y] == 0) return dp[x][y]; for(int i = 0; i < 2; i++) { int next_x = x + g[x][y] * dx[i]; int next_y = y + g[x][y] * dy[i]; if(next_x < 0 || next_x >= n || next_y < 0 || next_y >= n || vis[next_x][next_y]) continue; dp[x][y] += dfs(next_x, next_y); vis[next_x][next_y] = 0; } return dp[x][y]; } void solve() { cin >> n; REP(i, n) REP(j, n) cin >> g[i][j]; OUT(dfs(0, 0)); } int main() { FAST_INP; solve(); return 0; } ```

AtCoder - ABC185C. Duodecim Ferra

You can practice the problem Duodecim Ferra [here](https://atcoder.jp/contests/abc185/tasks/abc185_c). ## Problem Statement There is an iron bar of length ``L`` lying east-west. We will cut this bar at 11 positions to divide it into 12 bars. Here, each of the 12 resulting bars must have a positive integer length. Find the number of ways to do this division. Two ways to do the division are considered different if and only if there is a position cut in only one of those ways. Under the constraints of this problem, it can be proved that the answer is less than 2^63. ## Solutions This problem can be solved using Stars and Bars Theorem. Given the lenght ``L``, we have a Diophantine equation ``x[0] + x[1] + ... + x[11] = L`` where x[i] are the lengths of the bars after the division. We need to select 11 positions out of ``L - 1`` positions. For example, if ``L`` is 14, we will have the following possible points to cut. ``` 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 ``` Therefore, the answer is ``` C(n, r) = C(L - 1, r - 1) = C(14 - 1, 12 - 1) = C(13, 11) = 78 ``` We can solve it in O(r) time complexity and O(1) space complexity . nCr can be written as ``` (n)! / (r)!( / (n - r)! = (n * (n - 1) * (n - 2) * ... * 1 ) / (r * (r - 1) * (r - 2) * ... * 1) / ((n - r) * (n - r - 1) * (n - r - 2) * ... * 1) = n * (n - 1) * (n - 2) * ... * (n - (r - 1)) / (r * (r - 1) * (r - 2) * ... * 1) ``` ```cpp // AC - 3 ms void solve() { ll L; cin >> L; ll ans = 1; FOR(i, 1, 12) { ans *= L - i; // n * (n - 1) * (n - 2) * ... * (n - (r - 1)) ans /= i; // r * (r - 1) * (r - 2) * ... * 1 } OUT(ans); } ``` We can turn it to a template for similar problems ```cpp template< typename T > T comb(int64_t N, int64_t K) { if(K < 0 || N < K) return 0; T ret = 1; for(T i = 1; i <= K; ++i) { ret *= N--; ret /= i; } return ret; } // AC - 7 ms void solve() { ll L; cin >> L; OUT(comb<ll>(L - 1, 11)); } ``` We can also use dynamic programming to solve this problem. The recursive formula is ``` C(n, r) = C(n - 1, r - 1) + C(n - 1, r) ``` For ``r == 0`` and ``n == r``, the result would be 1. ```cpp // AC - 10 ms const int mxN = 205; ll c[mxN][mxN]; void solve() { ll L; cin >> L; REP(i, l) { c[i][0] = c[i][i] = 1; FOR(j, 1, i) { c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; } } OUT(c[L - 1][11]); } ```

TLX - TROC17A. Firework Festival

You can practice the question [here](https://tlx.toki.id/contests/troc-17/problems/A). Given two arrays A and B, each of size N. Determine whether the sum of A[i]^B[i] for all 1 <= i <= N, is odd or even. Display the output 0 if the sum is even, or 1 if the sum is odd. Input Format ``` N A[1] A[2] ... A[N] B[1] B[2] ... B[N] ``` Sample Input ``` 5 2 4 6 8 2 1 2 3 4 5 ``` Sample Output ``` 0 ``` Constraints ``` 1 <= N <= 100 1 <= A[i], B[i] <= 100 ``` Usually for Problem A, most of the solutions are brute-force. However, if we take the edge case 100, A[0] ^ B[0] + A[1] ^ B[1] + ... + A[99] ^ B[99] where A[i] and B[i] are 100, the overall result would occur overflow. We can notice that this problem is all about parity. The exponent B[i] of A[i] does not change the parity of A[i] ^ B[i]. Hence, we can conclude that ``` even ^ odd -> even even ^ even -> even odd ^ even -> odd odd ^ even -> odd ``` and we know that ``` even + even -> even odd + odd -> even even + odd -> odd ``` Therefore, we can simply sum all the values and check if it is even or odd. ```cpp int main() { int n; cin >> n; vi a(n), b(n); READ(a); READ(b); int sum = 0; REP(i, n) sum += a[i]; OUT((sum & 1)); return 0; } ```