Forem: S. Sharma

Plotting Reddit Comment Trends With Pandas

S. Sharma — Thu, 10 Sep 2020 01:58:05 +0000

Hey there!

I wanted to learn more about Pandas, a Python library for data analysis, so I decided to embark on a mini-project to experiment with it. If you use Reddit, you've probably seen a chain of comments like below:

Clearly, you can see that there's a pattern in the number of upvotes. Every reply to the parent comment receives less upvotes compared to the previous reply. It would be interesting to create a bar graph, comparing the number of upvotes the parent comment received, the number of upvotes the first reply received, the number of upvotes the second reply received, ..., the number of upvotes the nth reply received. Using Reddit's API and Pandas, I implemented a program that would do just that. You can find it on GitHub here.

First, we need to import the following:

import praw
import pandas as pd
import matplotlib.pyplot as plt
import sys
import math
from concurrent.futures import ThreadPoolExecutor

PRAW is a Python wrapper for Reddit's API. matplotlib is a library for creating static, animated, and interactive visualizations in Python. These imports will become clearer as we move on.

Next, we need to define authenticate to Reddit's API. PRAW allows us to do this pretty easily with OAuth2:

# Authenticate using our client secret
def authenticate():
    with open('client_secret.txt', 'r') as f:
        data = f.read().split()
        CLIENT_ID = data[0]
        CLIENT_SECRET = data[1]

    return praw.Reddit(client_id=CLIENT_ID,
                    client_secret=CLIENT_SECRET,
                    user_agent=USER_AGENT)

In this case, the client ID and client secret is stored in a file (called client_secret.txt). We read this and return an instance of PRAW's Reddit class, which allows us to interact with Reddit's APIs.

Now, we break down what we have to do in logical chunks. First, we need to get a list of submissions, so that we can look at the comments under each post. PRAW allows us to get a list of the hottest submissions from r/all, which is basically an amalgamation of a bunch of submissions from different subreddits:

def get_submission_upvotes(reddit, m, n):
    upvotes_list = []
    submissions = list(reddit.subreddit('all').hot(limit=m))
    with ThreadPoolExecutor() as executor:
        futures = [executor.submit(count_upvotes, submissions[i], n) for i in range(0, m)]
        [upvotes_list.append(future.result()) for future in futures]
    return upvotes_list

The reason we use concurrent.futures is because, depending on the length of the comment chain we are examining, we might end up taking very long to collect upvotes on one submission but a very short time to collect upvotes on another submission (we will see what the count_upvotes function does next). Here, m represents the number of submissions to look at and n represents the number of comments in a comment chain to examine.

Next, we need to count the number of upvotes of each comment in a comment chain in each submission. This can be done as follows:

def count_upvotes(submission, n):
    upvotes = []
    submission.comments.replace_more(limit=0)

    count = 0
    comment = submission.comments[0]
    while count < n:
        upvotes.append(comment.score)
        count += 1
        if len(comment.replies) > 0:
            comment = comment.replies[0]
        else:
            break

    while len(upvotes) < n:
        upvotes.append(float('nan'))
    return upvotes

In essence, we get the top comment and keep examining each reply until we have gotten n comments or until the comment chain ends (to get more comment chains of length n, we can increase m). If the comment chain ends prematurely, we add nan (Not a Number) to indicate that no data was collected for the particular reply in the comment chain because that reply did not exist (the comment chain ended, so there were no more upvotes to count).

After counting the upvotes of each comment in the top comment chain, we only have to process the data. First, we compute the average number of upvotes for the top comments, the 1st reply, the 2nd reply, etc:

def compute_data(upvotes_list):
    avg_upvotes = []
    for col in range(0, len(upvotes_list[0])):
        avg = 0.0
        n = len(upvotes_list)
        for row in range(0, len(upvotes_list)):
            if math.isnan(upvotes_list[row][col]) == False:
                avg += upvotes_list[row][col]
            else:
                n -= 1
        if n > 0:
            avg_upvotes.append(avg / n)
        else:
            avg_upvotes.append(0)
    return avg_upvotes

We return a list called avg_upvotes, which contains the average number of upvotes for the top comment, first reply, second reply, etc. We now convert this list into a bar graph:

def render_data(avg_upvotes, n):
    # Solution from https://stackoverflow.com/questions/9647202/ordinal-numbers-replacement
    ordinal = lambda n: "%d%s" % (n,"tsnrhtdd"[(n//10%10!=1)*(n%10<4)*n%10::4])
    x = [str(ordinal(i)) for i in range(0, n)]
    df = pd.DataFrame({'Comment Reply Number': x, 'Average Upvotes': avg_upvotes})
    df.plot.bar(x='Comment Reply Number', y='Average Upvotes', rot=0, legend=False)
    plt.xlabel('Comment Reply Number')
    plt.ylabel('Average Upvotes')
    plt.xticks(size=4)
    plt.yticks(size=4)
    plt.show()

Now all we have to do is put it together:

if __name__ == '__main__':
    if len(sys.argv) < 3:
        print('./comment_analyzer.py [number of submissions to analyze] [number of comments]')
        exit()
    m = int(sys.argv[1])
    n = int(sys.argv[2])
    reddit = authenticate()
    upvotes_list = get_submission_upvotes(reddit, m, n)
    avg_upvotes = compute_data(upvotes_list)
    render_data(avg_upvotes, n)

The program takes two parameters: the number of submissions to look at and the "depth" of the comment chain we have to look at.

Running the program (assuming you have the necessary libraries installed with Python 3.6+), you get a bar graph like so:

(The "0th" comment represents the top comment).

The above graph allows us to visualize the distribution of upvotes on comments on Reddit. Clearly, the distribution is right-skewed: the number of upvotes diminish as we get deeper down the reply chain. This is to be expected, since the top comment tends to be seen first.

Hopefully, you can see how tools like Pandas and PRAW allow us to collect data and visualize it.

How to use Hugo and GitHub Pages

S. Sharma — Sun, 06 Sep 2020 02:37:34 +0000

Hey there!

I just moved my blog from Jekyll to Hugo and I wanted to give a quick tutorial on how to use Hugo with GitHub pages.

Installation

First, you'll need to install Hugo:

MacOS: brew install hugo

Linux: brew install hugo (Here's a link on how to install brew for Linux)

Windows: choco install hugo -confirm or scoop install hugo

Note: You may need to install Go.

Hugo on GitHub Pages

Installing Hugo for GitHub Pages is pretty simple. First, we will create a new directory (I'll refer to this directory as mysite). Then, type the following commands:

> hugo new site mysite
> cd mysite

If you type ls, you'll see a bunch of files in this directory. The only one we care about for now is config.toml. Go to config.toml and find the line that says publishDir = public (or add it somewhere if it's not present). Set publishDir to docs. This will be the root directory that GitHub pages will use to deploy our site. Also, find the line with the parameter baseURL and set baseURL = https://<YOUR-USERNAME>.github.io where <YOUR-USERNAME> is your GitHub username.

Now, type the following:

> hugo server -D

Go to https://localhost:1313/ and confirm that your site is running properly. Then, go to GitHub and make a new repository called <YOUR-USERNAME>.github.io. Once you do that, go to the Settings tab and scroll down to the section that says GitHub Pages. Under the Source heading, use the dropdown to select the /docs option. This will inform GitHub Pages that the root directory for your site is under the docs subdirectory. Finally, click the Save button.

All we have to do now is push your site to the repository. Type the following commands (you're still in the mysite/ folder at this point):

> cd ../
> git clone https://<YOUR-USERNAME>.github.io
> cp -r mysite/ <YOUR-USERNAME>.github.io
> rm -rf mysite/
> cd <YOUR-USERNAME>.github.io
> hugo
> cd docs
> git add .
> git commit -m "My Hugo Site" # or whatever you want your commit message to be...
> git push origin master

...and that's it! The above commands clone your repository, copy the files from mysite/ to <YOUR-USERNAME>.github.io/, generate the root directory (docs) using the Hugo command, and then commit and push your site to the master branch.

Likely, you'll be making a lot of changes to your Hugo site. In that case, you'll want a shell script to streamline the process. The following bash script does that:

#!/bin/sh

# If a command fails then the deploy stops
set -e

printf "\033[0;32mDeploying updates to GitHub...\033[0m\n"

# Build the project.
hugo # if using a theme, replace with `hugo -t <YOURTHEME>`

# Go To docs folder
cd docs

# Add changes to git.
git add .

# Commit changes.
msg="rebuilding site $(date)"
if [ -n "$*" ]; then
    msg="$*"
fi
git commit -m "$msg"

# Push source and build repos.
git push origin master

The above was taken from a post by Hugo for deploying your website to GitHub pages, which I recommend reading for more information on how to add posts, customize/create themes, and write your own templates.

Leetcode: Middle Node in Linked List

S. Sharma — Thu, 27 Aug 2020 04:20:44 +0000

Problem

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Code

I came up with the following solution in C++ to the problem:

ListNode* middleNode(ListNode* head) {
  ListNode *fast = head, *slow = head;
  while (fast && fast->next) {
      fast = fast->next->next;
      slow = slow->next;
  }
  return slow;
}

The algorithm above uses two pointers, a slow pointer and a fast pointer. The fast pointer moves twice as fast as the slow pointer. Below I'll explain why the algorithm works.

Explanation

The input we are given is a non-empty, singly linked list. We must show that the algorithm finds the middle node for all non-empty singly linked lists. A linked list can have an odd length or and even length. If the list has an odd length, that means there is exactly one node in the middle. If the list has an even length, then there are two nodes in the middle and we are required to return the second one.

Let's first consider the odd case. Let's assume there are 2m+1 nodes where m is a positive integer. Both pointers start at node 1. After the first iteration, the fast pointer is at node 3 and the slow pointer is at node 2. After the second iteration, the fast pointer is at node 5 and the slow pointer is at node 3. After the third iteration, the fast pointer is at node 7 and the slow pointer is at node 4. Let's place the values in a table to understand the trend.

`fast` position	`slow` position	iteration
1	1	0
3	2	1
5	3	2
7	4	3
9	5	4
11	6	5
13	7	6
15	8	7
17	9	8

If you notice, the fast pointer has position 2*(position of slow pointer) - 1. Thus, when the slow pointer is at the middle of the list (position m+1) the fast pointer is at position 2*(m+1) - 1 = 2m + 1. So, if the fast pointer moves at twice the speed of the slow pointer, then the slow pointer will point to the middle node by the time the fast pointer arrives at the end of the list.

On a similar vein, we can prove that this algorithm works for an even length list. Let there be 2m nodes. Since the pattern is the exact same, we determine that when the slow pointer arrives at the position m+1 (the second middle node), the fast pointer is at position 2*(m+1) - 1 = 2m + 1. However, since there are only 2m positions, that means that the fast pointer has already finished traversing the entire list (NULL). Thus, the code above still works and the algorithm solves the problem.

Cost Models for Algorithmic Analysis

S. Sharma — Wed, 15 Jan 2020 19:35:21 +0000

Recently, I read a post on HN by Gregory Gundersen on why they keep a research blog. I think the idea of having a place where you can explain things to yourself (and to others in the process) sounds quite useful. So, today I'm going to talk about cost models, an important part of algorithmic design and the theory of algorithms.

What is a Cost Model?

A cost model is essentially a model to describe what operations we consider when analyzing an algorithm. For example, when stating the performance of sorting algorithms, we tend to consider comparisons and array accesses as operations that incur a cost when we execute them, so we take them into consideration when analyzing the performance of sorting algorithms. Additionally, when analyzing data-structures like LIFO stacks and FIFO queues, we tend to consider push and pop (or enqueue and dequeue) operations since these operations incur a cost. Technically, any operation (even assigning a variable) incurs a cost, but generally we're interested in operations that are complex enough that they could cause the program to slow down if executed excessively.

Knuth defined the total cost of a certain number of operations to be computed as follows:

Total Cost = Frequency × Time

The frequency refers to the number of times the operation occurs, and the time refers to how long it takes for the operation itself to execute. For example, if a comparison took 5 seconds on average, and we did 200 comparisons, then the total cost would be 1000 seconds.

Generally, when talking about algorithmic performance, we don't talk in terms of seconds, minutes, or any unit of time, but in terms of the frequency. This is because the time it takes for an operation to be executed varies depending on the system you're running a program on. The frequency of an operation is not variable, it's well-defined. Therefore, if we know the frequency of operations, then all we need to know is the system-specific time variable to calculate the total cost (we can usually do this by just timing the operation to execute by itself).

So, when we say that an algorithm's running time is N^2 or O(N^2), what does that mean? The latter is a bit more specific (and I may talk about it another time), but, to put it simply, an algorithm that has a running time of N^2 executes N^2 operations. What are these operations? These operations are defined by the cost model. If a sorting algorithm has a running time of N^2 that means that, given an array of size N, the algorithm requires N^2 comparisons (or array accesses, depending on what we care about) to sort the array.

Why use a Cost Model?

I'll be honest, theoretical computer science is usually not applicable in practical situations. However, though you may not be doing any mathematical analysis, it's useful to know what operations are expensive and what operations aren't. Identifying what operations are the bottleneck in your application allows you to avoid premature optimization (the root of all evil) and, of course, allows you to speed up your program. Additionally, having a "mental cost model" can enable you to be more selective in your choice of algorithm or data-structure for a particular task. For example, if you're writing an IRQ handler, then a ring buffer would probably be a better than a linked-list queue since space is a premium. If you're sorting complex data types (like linked lists), then merge sort would be a better option than quick sort. If you're making a symbol table, you need to decide what underlying data-structure you will use according to whether your program will be performing more inserting/removing operations or accessing operations.

The idea of a cost model naturally leads to many questions pertaining to the theory of algorithms. I've listed some links below for anyone who wants to learn more.

Resources

Busy? Try Todoist

S. Sharma — Sat, 11 Jan 2020 16:05:05 +0000

Source: doist.com

This is a weird post because it’s sort of an app promotion but I’m not being paid for it. Either way, I think this app deserves a little bit of attention.

Everyone needs a to-do list. Keep in mind that this is coming from a person who’s pretty flexible when it comes to task completion. For a long time, I rarely ever used to-do lists because I was usually pretty good at remembering what I had to do. As time went on, however, I needed a better way to keep track of things. So, naturally, I turned to software. That’s when I found Todoist, a simple app for keeping track of things.

The reason I’m promoting this app and not others is because it’s free(ish) and it has a nice interface that allows for me to keep track of the specific tasks I have to do. Additionally, I use the app to keep track of project ideas that I want to try out over the weekend since I usually don’t get time to experiment on the weekdays. The app allows me to plan out what I have to do today, tomorrow, and for the next week, which is extremely useful since some to-do list apps are only useful for planning what you want to do on that day. As you add and complete tasks, Todoist measures your progress by providing daily summary reports of the number of tasks you are completing, which other apps don’t do. Speaking of completing tasks, the final — and perhaps best — aspect of the app is that it “rewards” you for completing tasks. Todoist has a feature called “karma” where you earn points for completing more tasks. By gaining a certain number of points, you go to a different level. This feature makes Todoist quite good for productivity, and motivates me to complete the pending — and often boring — tasks that I have to complete in a day.

Of course, every app has a downside. Todoist operates on a freemium model, meaning that certain features like weekly summary reports and labels, are not accessible if you don’t upgrade to their premium version. The biggest problem with this app is that reminders are a premium feature. I usually don’t need reminders to complete tasks, I just need to remember what they are, so this isn’t a problem for me. However, if you need reminders, then maybe upgrading to the premium version or getting a different app would be a good choice.

Thoughts? Opinions? Concerns? Leave a comment below! 😀

5 Projects To Do When You're Offline

S. Sharma — Sun, 05 Jan 2020 03:46:48 +0000

Recently, I went on a camping trip with family and I got really bored. The outdoors isn't really my thing (which is why I decided that programming and mathematics suit me more than, say, being a gym instructor), so I naturally brought my computer and phone along with me. Of course, I had no service and no Wi-Fi meaning that I was limited in terms of what I could do. The only real form of entertainment I had was my downloaded music and my text editor.

A lot of code written nowadays requires some sort of Internet connection. Building a web server? Internet. Developing a vast neural network? Internet. Making an app? Internet. Creating a website? Internet.

Many of the tools that typical developers make require an Internet connection. Additionally, I assume there are some developers that — like me — would prefer to spend a weekend inside rather than let the sun touch their face or would just like to spend some time doing something productive.

If you're that type of person, then this article (might) interest you if you (might) find yourself in this situation. If being Internet-isolated is not a problem for you, then please don't recommend that I go outside more because — and this might be a shocker — I don't care. At all.

Without further ado, the following are 5 projects to when you're do offline.

A Basic Calculator

I was looking at my phone thinking about what I could do. The calculator app is one of the only functional apps on your phone. I thought I would make a basic calculator on the terminal (like bc) that could perform addition, subtraction, multiplication, division, and exponentiation according to the order of operations. Additionally, I wanted it to be able to evaluate parenthesized expressions. After a little bit of thinking, I created a basic calculator in C.

A File Search Program

Since I can't access any data on the cloud, I only have the files on my local machine to deal with. So, logically, making a file search program makes sense. I wanted it to be simple, so I decided to ignore character files, symbolic links, and block devices. With a majority of the file system minutiae out of the way, we only have to consider directories and regular files. If we come across a directory, then we put all the contents of the directory into a queue. Otherwise, if we come across a regular file, we check to see that the regular file's name matches the user's search query. In a little bit of code, I made a crude file search program (again, in C).

Any UNIX Tool

There are a lot of UNIX tools: less, grep, du, cat, rm, ld, and ps, to name only a few. If you're on a UNIX system, then pick a UNIX tool to recreate. Generally, most of the knowledge needed to recreate these tools can be found within a few man pages or with just a bit of basic programming knowledge. If you're on Windows, then this task can be especially challenging. I chose to make a basic version of grep (with highlighting).

Play with Mazes

Generating random mazes is surprisingly fun and a real algorithmic challenge. The only reason I'm even suggesting this is because of Jamis Buck's Mazes for Programmers, a thrilling book (that I should have taken with me when I was camping) on maze algorithms. The book is entirely in Ruby, but it can be done in any language. I wrote some basic code to generate a maze of arbitrary size according to user input and output it to the terminal screen using the Binary Tree algorithm (Disclaimer: OK, so I didn't write this code, the author of the book did, but that's besides the point). If you're ever feeling uncreative (like I was when thinking of a project to do), then I would recommend just going through this book. So far, it's been quite entertaining.

Recreate Basic Programming Language Features

Another project is to recreate basic features of your programming language of choice in that programming language. I didn't "recreate" malloc() and calloc() per se, but I did implement a simple, dumb variant of the two functions that allocates memory off of a fixed memory pool. Of course, there's many other features you can recreate: slices, vectors, lists, dictionaries, even for and while loops. The choice just depends on what seems interesting to you.

Conclusion

Again, all the projects I did above are available in this repository. Some of them can obviously be improved. For example, the calculator could have its own GUI (maybe not in C, but in another language) or handle more complex functions like sin and square root. The file search program is single-threaded and synchronous. Could an async/threaded approach be faster? The alloc program is a really dumb implementation of a memory allocation system. There's not even a way to free up memory. Maybe a binary heap would be better (or a Fibonacci heap) rather than a linear, fixed memory pool? The list of improvements are endless.

Of course, there's many, many more offline projects you can do. Pong, Chess, a JSON parsing library, or even an entirely new programming language are all examples of offline projects that you can embark on.

Have you done any interesting projects while offline? Have any thoughts? Opinions? Concerns? Ideas? Write a comment below! 😁

5 Git Commands Everyone Should Know

S. Sharma — Wed, 25 Dec 2019 03:24:30 +0000

Git is an amazing tool for version-control and open-source collaboration (though many companies are now using it too!). I think that most people should be able to use Git, especially if it's a requirement for them at work or school. Below are 5 Git commands everyone should know.

git reset --hard [commit hash] — This is fantastic as a last resort for when you've really screwed up. Generally, I've only used this when I've tried out a dumb idea (thinking it was good), merged it into my main branch, and then realized that it was, in fact, a dumb idea in the first place. You might want to read more about this.
git checkout -- [filename] — If you're ever in a situation where you've made so many changes to a file that you think it's just better to scrap them all, this is the command. git checkout -- [filename] will undo any uncommitted changes to a file (or a set of files). You might want to read more about this.
git rm [filename] — This command gets git to stop tracking a file or a set of files. It's pretty useful for removing a file from the working directory and removing it from git's tracking. You might want to read more about this.
git config --global alias.[aliasname] [command] — This is very helpful if you hate typing a lot. git alias allows you to create short-hands for common git commands. For example, git config --global alias.nbr "checkout -b" allows you to do git nbr my-branch to create a new branch called my-branch instead of git checkout -b my-branch(I made this exact alias myself). You might want to read more about this.
git revert — OK, so I'll admit, I've never used this once, but I think the command is pretty useful. Given a set of commits, it'll undo those changes and record that revert in a commit. Again, I've never used it, but I can think of many cases where development can go so awry that it's necessary. You might want to read more about this.

Opinions? Thoughts? Praises? What are some useful git commands for you? Leave a comment below! 😀

Question: How to make a personal blog that looks good?

S. Sharma — Thu, 19 Dec 2019 23:23:08 +0000

I just started using Jekyll and GitHub pages to host my website. While I'm mainly interested in writing posts about math and documenting any interesting programming projects I do, I want to make my website look appealing and interesting. Right now it's a little bit bland.

If anyone more experienced in this area can help, that would be awesome.

Thanks!

How To Read A Computer Science Book

S. Sharma — Thu, 19 Dec 2019 04:49:49 +0000

New Year's is coming up and I kind of wanted to give a couple basic tips that I learned before we head into the next decade.

Don't read it like a novel — One of the mistakes I made trying to read computer science books is that I tended to read it like a storybook. When we're reading in "storybook" mode, we're in a cognitively passive mode. That is, we're not engaging with the content, just absorbing it as we go, forgetting the minute details that may be really important for understanding. The key thing to do here is to start reading actively, which leads me to my next bullet point.
Understand exactly what's going on — Say you're reading a book about sorting algorithms and they're talking about merge sort. Instead of reading the description of merge sort (and doing any potential practice problems), try to work each example out in your head or, if you must, on paper. That way, you'll fully understand how the algorithm works and already have some exposure to using the algorithm, making practice problems (and real-world problems) easier to solve.
Take notes — Look, notes aren't easy for most of us, but taking notes is great for summarizing large amounts of information. If you're taking an online course, then this is an especially good idea. Don't just think, "Oh, I'm not in a classroom, so I can just watch the video." You're going to forget everything once the unit is over. Writing down the important stuff helps our memory.
Don't try to do every practice problem — This might seem counter-intuitive at first. However, trying to do everything is time-consuming. If you're able to do every problem in a timely manner, great! That's the optimal scenario. But let's face it, not every one of us is going to be brilliant right off the bat. Some topics are hard, and applying the concepts can be difficult. Additionally, sometimes you just don't want to do all or even a majority of the exercises because it feels like so much work. Relax. You don't have to be the next Albert Einstein. Just do as much as you can. Any amount is worth something.
ALWAYS challenge yourself — Doing easy problems is fine. Those types of problems can help reinforce certain concepts or skills. However, don't just glance at a problem and say "that's too easy." If it is, why not solve it? I used to do this sometimes out of laziness and sometimes to make myself feel better. If a problem is hard, however, don't just avoid it. Even if you have an instinctual feeling to avoid it, remember: you're not a genius, and you'll never become a better computer scientist/programmer/mathematician/whatever if you don't try. I know it sounds cliché, but it's worth saying again.

All of the stuff above are habits that I used to have. In fact, to a certain extent, I still do these things. However, one of my goals for next year (and for the rest of my computer science career) is to make myself less vulnerable to these behaviours and instill more productive habits.

How do you read technical books? Leave a comment below. Happy Holidays! 🎁