<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Calvin Li on Medium]]></title>
        <description><![CDATA[Stories by Calvin Li on Medium]]></description>
        <link>https://medium.com/@FallingForFallacies?source=rss-4df6101d1879------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*3LXgTlR_ke_22mEr.jpg</url>
            <title>Stories by Calvin Li on Medium</title>
            <link>https://medium.com/@FallingForFallacies?source=rss-4df6101d1879------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 11:53:27 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@FallingForFallacies/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Adventures in Software Engineering Interviews: “Optimal” Longest Palindromic Substring]]></title>
            <link>https://medium.com/@FallingForFallacies/adventures-in-software-engineering-interviews-optimal-longest-palindromic-substring-89d31ec79e2b?source=rss-4df6101d1879------2</link>
            <guid isPermaLink="false">https://medium.com/p/89d31ec79e2b</guid>
            <category><![CDATA[tech]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[interview-questions]]></category>
            <dc:creator><![CDATA[Calvin Li]]></dc:creator>
            <pubDate>Tue, 25 May 2021 15:02:31 GMT</pubDate>
            <atom:updated>2021-05-25T15:02:31.339Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*EFn7KULWmZ4fm_FP__F2Qg.png" /><figcaption>Spoiler: This is how it ends.</figcaption></figure><p><em>Here is the first article in the series: </em><a href="https://medium.com/hackernoon/adventures-in-programming-interviews-misleadingly-difficult-np-hard-problem-43092597018c"><em>Misleadingly (NP-)Hard Problem</em></a></p><p>This is my friend’s story.</p><p>My friend’s pretty good at coding, having competed multiple times in the International Collegiate Programing Contest (it’s how we met). This interview was for an internship at a well-known tech company that is currently valued at north of a trillion dollars.</p><p>The interviewer asked “write a method that finds the longest palindromic substring”, and this was my friend’s thought process:</p><blockquote>Okay, I can think of four solutions:</blockquote><blockquote>1. The naive O(n³) solution where you iterate through all substrings O(n²) and check if each is a palindrome O(n).<br>2. The more clever O(n²) solution where you take each letter and space between letters, O(n), and scan outwards to find the longest palindrome with that letter or space as the palindrome’s center, O(n).<br>3. There’s a O(n) solution after you build <a href="https://en.wikipedia.org/wiki/Suffix_tree">Suffix Trees</a>, and there is an <a href="https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm">O(n) method</a> of building suffix trees, but I only know the O(n log²n) method for suffix trees off the top of my head.<br>4. <a href="https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher&#39;s_algorithm">Manacher’s Algorithm</a>, which is optimal at O(n), but I don’t know it.</blockquote><blockquote>I’ll start with #2 and work towards the asymptotically faster O(n log²n) solution with suffix trees.</blockquote><p><strong>Friend:</strong> “Here’s an O(n²) solution” [Proceeds to describe approach #2]</p><p><strong>Interviewer:</strong> “Can you code it up?”</p><p><strong>Friend:</strong> “Sure” [Whiteboards approach #2 pretty quickly, mentally preparing for approach #3]</p><p><strong>Interviewer:</strong> [With over half the allotted time remaining] “Unfortunately, you started with the <em>Optimal</em>™<em> </em>solution”</p><p><strong>Friend:</strong> “…”</p><blockquote>What.</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=89d31ec79e2b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Reverse Rents: How to Fix Rent Control]]></title>
            <link>https://medium.com/@FallingForFallacies/reverse-rents-how-to-fix-rent-control-e9c551017bc?source=rss-4df6101d1879------2</link>
            <guid isPermaLink="false">https://medium.com/p/e9c551017bc</guid>
            <category><![CDATA[housing]]></category>
            <category><![CDATA[cities]]></category>
            <category><![CDATA[urban-planning]]></category>
            <category><![CDATA[economics]]></category>
            <category><![CDATA[rent-control]]></category>
            <dc:creator><![CDATA[Calvin Li]]></dc:creator>
            <pubDate>Tue, 24 Sep 2019 15:01:01 GMT</pubDate>
            <atom:updated>2019-09-24T15:01:01.483Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/600/0*WUNkxSWv9oFWwhCx" /></figure><p>Reverse Rents offer a simple win-win solution to rent control, benefitting both tenants and homeowners. Reverse rents curtail the harms of rent control <strong>without</strong> weakening existing tenant protections.</p><h3>The Simple Solution: Reverse Rents</h3><p>Reverse rents are when homeowners pay a monthly “rent” for a period of time to tenants to move out, ie to not live in the unit. This monthly fee is either a fixed base amount or a percentage of the rental income of the next tenant, whichever is higher for that month.</p><h4>An example</h4><p>The numbers here are illustrative.</p><p>Alice owns a rent controlled property. Bob is the current tenant and pays far below market-rate at $1000/month. Alice believes the market rate is closer to $3000/month. Alice offers Bob a reverse rent of the higher of either $1200/month or 50% of what the next tenant is paying for 3 years if Bob moves out. If Alice’s next tenant pays $3000/month, Bob gets 50% or $1500. If Alice’s next tenant pays only $2000/month, Bob gets $1200, since 50% is only $1000.</p><p>Bob agrees and moves out.</p><p>At a minimum, Bob will collect $43,200 from Alice in reverse rent payments the next 3 years.</p><p>If Alice quickly finds a tenant for market rate, then Bob gets an additional $10,800, or $54,000 in total. Alice makes an additional $36,000 over the same time because of this arrangement. After 3 years, Alice makes significantly more indefinitely.</p><p>Truly win-win.</p><h3>What is rent control?</h3><p>There are different types of <a href="https://en.wikipedia.org/wiki/Rent_control_in_the_United_States">rent control</a>, but the main tenet of rent control, or rent regulation, is to restrict how much homeowners can increase prices over time.</p><p>Reverse rent addresses the type of rent control where homeowners are only restricted from increasing prices for the current tenants, but are free to set any price for the next tenants. This form of rent control is called <strong><em>vacancy decontrol</em></strong> or <strong><em>soft rent control</em></strong>.</p><p>Much of the aggravation from homeowners and economists are when existing tenants pay significantly less than the market rate, ie what new tenants will likely be paying.</p><h3>Why rent control?</h3><p><a href="https://en.wikipedia.org/wiki/Rent_control_in_the_United_States">Rent control</a> is one of the most contentious elements of modern cities. Ending the policy would displace a significant number of families, while keeping the policy decreases overall housing affordability, reduces tenant mobility, and damages real estate value.</p><p>Reverse rent allows tenants to capture some of the market value by “selling” their rent control rights to homeowners. Reverse rents do not weaken existing tenant protections from rent control, while enabling homeowners and tenants to both benefit from these mutually beneficial arrangements. This will not solve all the problems of rent control, but will help address the worst rent control situations: when current tenants pay significantly less than the market rate.</p><h3>How Reverse Rent differs from Buyouts</h3><p>A <a href="https://www.sftu.org/buyouts/">buyout</a> is when a homeowner offers a one-time lump sum to move out, instead of a recurring dynamic amount based on what the market rate. Reverse rent solves many of the problems in the existing buyout process.</p><p>Compared to buyouts, reverse rents are <strong>less predatory</strong> for tenants. Homeowners are incentivized to withhold information to gain leverage and lowball the buyout. When what tenants get is tied to market rates, tenants are protected against asymmetric or imperfect information, making the value tenants receive fairer.</p><p>Compared to buyouts, reverse rents are <strong>cheaper</strong> for homeowners because the cost is spread out over time and homeowners can back the payouts with revenue from the next tenants. Much fewer reverse rents will require a bank loan and the accompanying interest because all of the money is upfront. Homeowners might even be able to write off reverse rents as an investment expense on their taxes. Because reverse rents are cheaper for homeowners, more homeowners will be able to afford reverse rents, which means reverse rents will do a better job of assuaging the market distortions rent control causes.</p><p>Compared to buyouts, reverse rents net tenants <strong>more money</strong> because reverse rents are cheaper for homeowners, and tenants are better protected from getting cheated out of market rate. Tenants will receive more money because homeowners can now offer more money because that money is cheaper to homeowners (spread out over time, payments are less risky, do not require loans), and more tenants will be offered reverse rents because of the relative affordability. Tenants take on some risk in case of market downturns, but are overall protected by the minimum base payout.</p><h3>How does this affect Tenants?</h3><p>Reverse rents offer tenants new and potentially significant revenue sources they can use to benefit their lives, eg pay down debts, cover major expenses like surgery, or otherwise invest in their livelihoods. The reverse rents would also help cover the burden and cost of moving.</p><p>Unfortunately, tenant coercion, harassment, and abuse are all too ubiquitous and well-publicized. Reverse rents offer a much more amicable outcome to those existing situations where homeowners are aggressively trying to claw back the housing value.</p><p>Beyond violent landlords, some tenants simply do not want to stay in those units, but find themselves financially trapped from finding better situations. Many units have not been updated or renovated in decades, and many units’ locations do not or no longer make sense for the tenants and their lives.</p><p>It’s important to emphasize that tenants can choose to reject homeowners’ reverse rent offers, so tenants are strictly better off for having this option available. <strong>All the existing protections for tenants would still exist and remain unaffected by reverse rents.</strong></p><p>Financially, tenants are protected from homeowners defaulting on their reverse rents, since homeowners own considerable assets in the form of property to back up these financial commitments. Overall, reverse rents should facilitate significant wealth transfers to existing tenants.</p><h3>How does this affect Homeowners?</h3><p>Reverse rents offer homeowners modest increases in rents short term and significant increases in rents long term. Homeowners could take this opportunity to invest in the unit in the form of renovations and improvements.</p><p>Homeowners are exposed to risk in reverse rents; even if homeowners misappraise market value, if the housing market takes a downturn, or if homeowners struggles to find new tenants, homeowners are still responsible for the regular reverse rent payments. Risk averse homeowners might suggest lower minimum base amount in exchange for a higher percentage cut when the next tenants are found.</p><p>Homeowners are incentivized to fill their units quickly to help pay for the reverse rents. Currently, cities have many empty units, <a href="https://www.mintpressnews.com/empty-homes-outnumber-the-homeless-6-to-1-so-why-not-give-them-homes/207194/">some more units than there are homeless people</a> in part because homeowners would rather leave units empty than to fill them with sub-market rents they cannot raise. With reverse rents, homeowners have another tool at their disposal if the market rates skyrocket.</p><p>This format can also work if homeowners decide to take the unit off the market; the reverse rent contract should offer a separate rate for this scenario to prevent homeowners from deceiving tenants.</p><p>It’s important to emphasize that homeowners are never forced to offer reverse rents, <strong>so homeowners are strictly better off for simply having this option available.</strong></p><h3>How does this impact the city?</h3><p>This increases the supply of available rental units in the city, which could lower rent and improve overall affordability. Housing prices are extremely complex and so movements are difficult to predict from still theoretical mechanisms like reverse rent.</p><p>Homeowners will now be freed to invest in their property, improving the overall livability and property values of the city, one home at a time.</p><p>This might impact the local demographics and culture, but those effects are far less certain and predictable.</p><h3>Can we do this now?</h3><p>Current homeowners and tenants can create a reverse rent contract right now.</p><p>However, since this would be a new form of legal contract, it will not be easy to draw up from scratch that would be resilient to anything going awry. Having a standardized contract, similar to how many housing contracts are standardized, can help reduce uncertainty and error, as well as reduce potential exploitation on the part of homeowners.</p><p>Reverse rents would benefit from institutional/governmental support to ensure that the reverse rent contracts are carried through successfully. For example, homeowners need to be able to prove how much their new tenants are paying to calculate the reverse rent rates, and it is not clear what a legal solution would look like.</p><p>If homeowners and tenants can maintain good faith, then reverse rents should be fairly simple to implement and execute.</p><h3>Missing details</h3><p>This article presents a high level overview of reverse rents, but there are a lot of devils in the details taking something from concept to reality. Some missing details include:</p><ul><li>How do homeowners approach tenants regarding the reverse rent situation in a way that best ensures fair and equitable outcome?</li><li>When homeowners with reverse rents sells their homes, what happens to the reverse rent contracts?</li><li>How does renovations affect reverse rents, especially when the number of rooms in the unit changes/with multiple tenants?</li><li>How does renovations affect reverse rents, especially when renovations affect the number of rooms?</li><li>Which legal avenues are the best to resolve disputes surrounding reverse rents?</li><li>How does reverse rents change the demographic makeup of a city and what role would it play in gentrification?</li></ul><p>In addition to these open questions, there are city-specific questions that are not easy to comprehensively address. However, none of these are insurmountable barriers, just questions worth answering on execution.</p><p>Despite these missing details, at a high level, reverse rents are a simple monthly payment between two consenting parties.</p><h3>I would love feedback!</h3><p>I would love any and all feedback on this! Thank you so much for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e9c551017bc" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[All* perfect pangrams of English]]></title>
            <link>https://medium.com/@FallingForFallacies/all-perfect-pangrams-of-english-8c8d0f621bee?source=rss-4df6101d1879------2</link>
            <guid isPermaLink="false">https://medium.com/p/8c8d0f621bee</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[english-language]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[computational-linguistics]]></category>
            <dc:creator><![CDATA[Calvin Li]]></dc:creator>
            <pubDate>Thu, 07 Jun 2018 14:26:01 GMT</pubDate>
            <atom:updated>2018-07-29T22:03:52.102Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PzTjHGYdWZTZCFee7wyufA.png" /></figure><p>An English pangram is a sentence that contains all 26 letters of the English alphabet. The most well known English pangram is probably “The quick brown fox jumps over the lazy dog”. My favorite pangram is “Amazingly few discotheques provide jukeboxes.”</p><p>A <strong><em>perfect</em></strong> pangram is a pangram where each of the letters appears only once. I have found some <a href="http://clagnut.com/blog/2380/">sources</a> online that list the known perfect pangrams. Nobody seems to have endeavored successfully to produce all of them exhaustively, so I took it on as a fun challenge. This is how I found all* of the perfect pangrams of English. I will explain the asterisk later.</p><h3>Here are some of my favorite perfect pangrams I discovered</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/0*ywdCxSgXoJGB_U2O.jpg" /><figcaption>A crwth. <a href="https://en.wikipedia.org/wiki/Crwth">Source</a>.</figcaption></figure><ul><li><a href="https://www.merriam-webster.com/dictionary/crwth"><em>Crwth</em></a><em> vox zaps qi gym </em><a href="https://www.merriam-webster.com/dictionary/fjeld"><em>fjeld</em></a><em> bunk</em>. (The sound of a <a href="https://en.wikipedia.org/wiki/Crwth">Celtic violin</a> strikes an eastern spiritual forces-focused fitness center situated in a barren plateau of Scandinavia.) This one is all Scrabble legal words!</li><li><a href="https://www.merriam-webster.com/dictionary/squdgy"><em>Squdgy</em></a><em> kilp job </em><a href="https://en.wiktionary.org/wiki/zarf"><em>zarf</em></a><em> nth </em><a href="https://en.wikipedia.org/wiki/cwm%20(landform)"><em>cwm</em></a><em> vex</em>. (The ill-formed kelp buys an ornamental cup warmer that one of many half-open steep-sided hollows at the head of a valley or mountainside has irritated.)</li><li><em>Jock nymphs waqf drug vex blitz</em>. (The charitable endowment intoxicated the forest spirits, who frustrated the athlete, who engages in an attack.)</li><li><em>Hm, fjord waltz, cinq busk, pyx veg</em>. (Let’s see, a long narrow deep inlet dances, the five on the dice makes music on the street, and the small round container for the sick and unable rests.) Also Scrabble legal, but has an interjection (<em>Hm</em>).</li></ul><p>Unfortunately, these are some of the most legible sentences I could find*. All perfect pangrams generated from the Official Tournament and Club Word List 3 (OWL3) for Scrabble without interjections include either the word <a href="https://en.wikipedia.org/wiki/cwm%20(landform)"><em>cwm</em></a> or <a href="https://www.merriam-webster.com/dictionary/crwth"><em>crwth</em></a>. <em>Waqf</em> is Scrabble tournament legal outside of North America.</p><h3>How to find all of the perfect pangrams</h3><p>The method for finding perfect pangrams comes in two steps. The first is to find all sets of words that contain each letter of the English alphabet once. The second step is to see which of those sets can be rearranged into valid English sentences.</p><h4>Step 1: Finding sets of words for the perfect pangram</h4><p>To start finding sets of words that span the English alphabet requires a list of English words. Finding and maintaining a high quality list of words was much harder than I had anticipated. Originally, I thought this project would take two days, but it ended up taking two weeks as a result of this data quality problem.</p><p>I started with the Unix dictionary, which is a freely available list of English words that comes with almost all Unix-based operating systems. I noticed immediately that the list had quality issues. First, each letter of the alphabet was considered a word in the Unix dictionary, and it included a lot of non-words, like “<em>vejoz</em>”. This demonstrated the need of a blacklist to manage the lists of words found online. Second, the Unix dictionary lacked plurals for words, so the dictionary would include the word “<em>orange</em>” but not “<em>oranges</em>”. The word list is so restrictive, in fact, that no previously known perfect pangrams include only words from the Unix dictionary. I still found some, such as “s<em>qudgy kilp job zarf nth cwm vex”</em>.</p><p>I then turned to the internet to find larger sets of words. I found very large word sets that were huge, but when I started digging for perfect pangrams from those lists, I found that they were way too polluted with low quality words that aren’t valid English words. Even after many rounds of iteration, I still failed to pare down the list to find any reasonable or manageable pangrams. I tried to clean it up by creating a whitelist of words of certain lengths, but the list was still extremely low quality.</p><p>Finally, after many iterations, I paid $15 to buy a trial membership of the <a href="https://www.scrabbleplayers.org/">North American Scrabble® Players Association</a>, which gave me access to the proprietary and copyrighted OWL3, which is the source of <a href="http://www.slate.com/articles/life/gaming/2014/09/major_scrabble_brouhaha_can_you_copyright_a_list_of_words.html">some controversy</a>. Even then, I had to add in some known words in English, such as the single-letter words “a” and “I”.</p><p>Armed with a proper list of words, I implemented an algorithm to produce all sets of words from that list that each contains one of each letter of the English alphabet. I will describe the algorithm at depth in <strong>“The Algorithm”</strong> section below.</p><h4>Step 2: Forming English sentences from a bag of words</h4><p>Given a set of words, figuring out whether a valid English sentence is possible with all the provided words is a non-trivial problem, but it is easier than most other natural language processing (NLP) problems.</p><p>There are useful heuristics for weeding out ineligible sentences; I was able to form valid English sentences from the remaining words after following those heuristics. The sentences were often nonsensical, but still valid. Here are the heuristics I used:</p><ol><li>There needs to be at least one verb.</li><li>There can only be one more noun than there are verbs unless there is a conjunction or a preposition, both of which are very rare.</li><li>If there are adjectives, there must also be nouns.</li></ol><p>The heuristic works in part because of the possibility of implied subjects (neither perfect nor a pangram, but “<em>move quietly and speak softly”</em> is a sentence with two verbs and no nouns, with the implied subject of “<em>you</em>”).</p><p>Since the space of words that can possibly participate in perfect pangrams is small, it’s easy enough to manually tag each individual word with its eligible <a href="https://www.aims.edu/student/online-writing-lab/grammar/parts-of-speech.php">parts of speech</a> and see if the set of words obeys those three simple heuristics. Whether or not you like the quality of the sentences produced is a matter of taste.</p><h3>The Algorithm</h3><p><em>This section is a bit technical, but hopefully still easy to follow. Feel free to skip to the “Results &amp; Learnings” section.</em></p><h4>High Level Strategy</h4><p>The goal is to produce all possible sets of words from the given list of words that spans the English alphabet “perfectly”.</p><ol><li>Clean the list of words to drastically reduce search space, e.g. remove words that have repeated letters, like “letters”.</li><li>Use bit masks to represent words efficiently and map them back to the original sets of words.</li><li>Search through all possible states, each representing a possible letter combination, by repeatedly iterating through the list of bit masks. Performance is dramatically improved with dynamic programming.</li><li>Draw arrows (directed edges) from the perfect pangram state, the final state that has all the English letters, to the intermediary states that composed it. Do that again with the intermediary states to create a data structure that can reconstruct the sets of words that are possible perfect pangrams. This is called backtracking.</li><li>Output the discovered sets of words that are possibly perfect pangrams as trees.</li></ol><h4>1. Cleaning the list, aka Canonicalization</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*CCVbBOp2R2ztWXky9jjM-w.png" /></figure><p>First step is to clean the original list of words to reduce search space and increase output quality.</p><ol><li>Strip all whitespace around the word and convert it to lower case only</li><li>Make sure the words only contain letters of the English alphabet; I used a simple regular expression filter: /^[a-z]+$/</li><li>Filter against any other lists, e.g. blacklists; if a word is in the blacklist, skip that word</li><li>Remove all words with repeated letters</li></ol><p>This shortened the search space significantly, from lists of 200,000~370,000 words to a much smaller 35,000~65,000 words.</p><h4>2. Using bit masks</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Lk95LG5qWkitLsb9tiVSWw.png" /></figure><p>Bit masks are integer representations of states. There are several advantages of bit masks:</p><ul><li>Bit masks represent this problem well. Letter ordering does not matter, so all combinations of words can be represented as a 26 digit long series of 0’s and 1’s, with each digit representing whether or not a letter exists in the combination. For example. if the set of words contains the letter “e”, the 5th digit will be a 1, otherwise a 0.</li><li>Bit masks are efficient: Since the search space is constant, bit masks offer an efficient storage and representation of all the possible combinations of letters. Furthermore, bitwise-operations are fast; to test if two bit masks can be combined to produce a larger bit mask, check if the <a href="https://en.wikipedia.org/wiki/Bitwise_operation#AND">bitwise AND</a> of the two masks equals 0, both of which are extremely fast operations.</li></ul><p>So, turn each word into a bit mask, which can be represented as an integer. For example, the word “cab” gets mapped to the bit mask of 111, which is the decimal number 7. The word “be” gets mapped to 10010, which is the decimal number 18, and so on. The largest possible bit mask is one with all the letters of the alphabet, the possible perfect pangram state, 11111111111111111111111111, which is the decimal number 67,108,863, or 2²⁶ -1. This fits well within a standard signed 32-bit integer, which can represent up to 2³¹-1.</p><p>Using bit masks further compresses space, as single word anagrams map to the same bit mask. Both “kiln” and “link” map to the mask 10110100000000, which is the decimal number 11520. This further reduces the search space of 35,000~65,000 words to 25,000~45,000 bit masks.</p><p>Retain a mapping of the bit mask back to the set of words they are derived from. This will be useful when outputting the sets of words.</p><h4><strong>3. Searching for the perfect pangram with dynamic programming</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*M-xc_c2EwaPWdT2sEhHbVw.png" /><figcaption>Drawn out toy example for only the first 5 letters of the English alphabet, a-e</figcaption></figure><p>The core of the algorithm is fairly simple:</p><p>Given a possible state (that is composed of valid combinations of existing words), try all of the masks from the initial word list to see if it’s possible to create a new valid state (by checking if the bitwise AND of the state and mask equals 0, which would mean that there are no overlapping letters). Create the new state by using the bitwise OR operation which merges all the 1s together. For each new state discovered, keep repeating until there are no more unexplored states. If this reaches the end, that means that the algorithm has found at least one possible perfect pangram word set. The first possible state that can enumerate all possible states is the empty state or 0, where no letters of the alphabet are included. So start there and then recursively discover which states are possible.</p><p>One huge efficiency gain is to notice that there are many ways to reach an intermittent state and that the work on the state does not change based on how it was reached. So instead of repeating the work when a state is revisited, store the result of each state. This technique is called dynamic programming and turns a complex combinatorial problem into a linear program. The process of storing the intermittent state is called memoization.</p><p>So create an array of size 2²⁶, between 0 and 67,108,863, inclusive. Each index represents a bit mask state as explained before. The value at each index of the array represents what is known about the state. 0 means either that the state is untouched or unreachable. 1 means that the state has found a way to reach the possible perfect pangram state. -1 means that the state has failed to find a way to reach the end.</p><p>Pseudocode below:</p><pre>int PANGRAM_STATE;  // 2^26 - 1 == 67108863</pre><pre>// dp[state] == 0  means the state is untouched or unreachable<br>// dp[state] == 1  means the target is reachable from state<br>// dp[state] == -1 means the target is unreachable from state<br>int solve(int state, int target, int[] dp, List&lt;Integer&gt; masks) {<br>    if (state == target) {  // Base Case: Does it reach the target?<br>        return 1;<br>    }<br>    if (dp[state] != 0) {  // DP: don&#39;t repeat work for a state<br>        return dp[state];<br>    }<br>    boolean reachesTarget = false;<br>    for (int mask : masks) {  // try all masks<br>        if ((state &amp; mask) != 0) {  // check for overlap<br>            continue;<br>        }<br>        int newState = state | mask;  // combine state and masks<br>        dp[newState] = solve(newState, target, dp, masks);<br>        if (dp[newState] == 1) {<br>            reachesTarget = true;<br>        }<br>    }<br>    return reachesTarget ? 1 : -1;<br>}</pre><pre>solve(0, PANGRAM_STATE, dp, masks);</pre><h4>Interlude: Complexity and Practical Runtime Analysis</h4><p>There are 2²⁶ possible bit masks for a series of 26 bits. Since each state is processed only once because of memoization, the runtime of this algorithm is O(<em>n</em> 2^<em>d</em>), where <em>d</em> is the size of the alphabet, 26. The variable <em>n</em> does not stand for the number of words, but the number of bit masks. With 67,108,863 and roughly 45,000 bit masks, this comes out to on the order of 3 trillion, which my MacBook Pro could handle in roughly 45 minutes; tractable for any modern computer. It’s also worth noting that the recursive call stack will never get deeper than 26 (likely never gets deeper than 15), so it’s also very manageable from that dimension as well.</p><p>One advantage of the bit mask approach with only 2²⁶ states is that all the states can be stored in memory. Since there are only 3 values per state (-1, 0, 1), this can be stored in a single byte. At a single bytes per state, 2²⁶ states comes out to around 67 megabytes, which is again very manageable.</p><p>As the alphabet increases, though, the search space increases exponentially and so does the run time, causing the problem to become intractable very quickly. A brief discussion on approaching the perfect pangram for larger alphabets are in the <strong>“Language w/ Larger Alphabets”</strong> section below.</p><h4>4. Dynamically building a Directed Acyclical Graph (DAG)</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*U9_J98WvQ49QREhIs4c_iA.png" /><figcaption>Drawing the DAG only for bit masks with state 1</figcaption></figure><p>Now that we have filled out the bit mask states, time to retrieve the solution!</p><p>To find the sets of words that created the set of possible perfect pangrams, we need to derive which intermediary states were integral to composing the final states. Then, the follow-up question is which other intermediary states composed those intermediary states, and so on until the only thing remaining are the states that map directly to words. This process is called backtracking.</p><p>To keep track of the relationships between states, the goal is to created a Directed Acyclical Graph (DAG), which maintains which intermediary states composes any given state. DAGs are easy to traverse to retrieve outputs, especially due to their non-cyclical nature. To construct, start from the possible perfect pangram state, and create a directed edge (arrow) that points to the intermediary states that compose it. Repeat the process with the intermediary states, and it will produce a DAG. There will never be any cycles because the arrows always point to a state with a smaller value.</p><p>Instead of rebuilding the relationships that were discovered in the search step, which involves traversing again through trillions of possible states combinations, it’s more efficient to build the DAG during the dynamic programming phase. Inside the solve method, if a newly constructed state can reach the possible perfect pangram state, store a directed edge from the newly constructed state to the original state only if the original state is smaller than its complement (to reduce edge duplication).</p><h4>5. Print out the fruits of your labor in tree form!</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/488/1*IB7Ez6ZV-moUUkFLkXVXJw.png" /><figcaption>Output of the toy example</figcaption></figure><p>Likely the easiest format for viewing the resulting sets of words is by listing them as trees with the root node as the perfect pangram state. Given the DAG constructed from above, the best way to unpack it is to do so recursively, writing each state to disk on each step instead of in-memory since the tree is an order of magnitude larger than the DAG.</p><pre>int PANGRAM_STATE;  // 2^26 - 1 == 67108863<br>Map&lt;Integer, List&lt;Integer&gt;&gt; edges;  // DAG edges<br>Map&lt;Integer, List&lt;String&gt;&gt; maskMap;  // Mask back to word list</pre><pre>void outputTree(int level, int state, Map edges, Map maskMap) {<br>    output.indent(level);  // uniformly indent based on level<br>    output.print(state);<br>    if (maskMap.containsKey(state)) {<br>        output.print(&quot;====&gt;&quot;);<br>        output.print(maskMap.get(state));<br>    }<br>    for (int substate : edges.get(state)) {<br>        int composite = state ^ substate;<br>        outputTree(level + 1, substate, edges, maskMap);<br>        outputTree(level + 1, composite, edges, maskMap);<br>    }<br>}</pre><pre>outputTree(0, PANGRAM_STATE, edges, maskMap);</pre><p>An improvement to this form of expansion is to summarize states that have only a single possible combination of words. A state that is a mask to words and no substates that compose it can be trivially summarized. A state can be summarized if its substates and its composites can be summarized, and all masks derived from itself and its children do not have overlapping bits/characters. Printing the summarized DAG improves the readability of the resulting output tree by shortening and simplifying it.</p><p>Since the summarization depends only on the smaller of the two states, iterating through the array from the initial state of 0 upwards and using the rules above to manage the summarization rule allows for this to be completed in linear time.</p><h3>Results &amp; Learnings</h3><h4>Produced Pangram Trees!</h4><p>Feel free to traverse through the perfect pangram trees to see if you can find interesting sentences!</p><blockquote><a href="https://github.com/temporalparts/PerfectPangrams">https://github.com/temporalparts/PerfectPangrams</a></blockquote><h4>There are a lot of possible perfect pangrams</h4><p>I was surprised by the number of perfect possible pangrams. There are a lot! The best strategy for piecing them together does not require a complex natural language processor. Once the candidate words have been labeled as noun or verb eligible, the bag of words must contain at least one noun, one verb, and the right ratio of nouns and verbs.</p><h4>Data Quality is a hard problem</h4><p>The algorithm section took two days, but the data quality problem took two weeks. When I mentioned this finding to my friend who is a senior staff engineer Google, he was not surprised, commenting that data quality issues are some of the hardest problems in engineering. Lesson learned.</p><h4>The Rules of Perfect Pangrams</h4><p>There are a lot of nuances as to what qualifies as a perfect pangram! I wanted to search through pangrams without any interjections (e.g. <em>hm</em>, <em>pht</em>), but there are also other popular restrictions such as abbreviations, acronyms, contractions, initialisms, isolated letters, proper nouns, and Roman numerals. There are also words which are names of letters, like <em>Qoph</em>, which I felt is cheating.</p><p>With some of those constraints relaxed, there are a lot of “perfect” pangrams. In the order of trillions, probably. There are a lot of acronyms and initialisms.</p><h4>The Asterisk</h4><p>The asterisk is in place because the definition of all of the perfect pangrams of English is not well defined. There are nuances related to what should be allowed in perfect pangrams of English. There are also a lot of contentions regarding whether or not some words are even English words. Given these nuances, it is really difficult to say that I have found all of the perfect pangrams. I can make two claims fairly confidently:</p><ol><li>I have found a methodology for producing all of the perfect pangrams of English and other languages with similar or smaller character sets.</li><li>I have enumerated all sets of words that can possibly form perfect pangrams using the official Scrabble tournament dictionary, OWL3.</li></ol><p>Please feel free to produce your own perfect pangrams with the techniques described in this post!</p><h4>Perfect Pangrams’ dependence on words of Welsh and Arabic roots</h4><p>Welsh- and Arabic-derived words were really important for the existence of perfect English pangrams (unless the constraints of the perfect pangram are relaxed). Using the OWL3 word list with strict rules regarding perfect pangrams, there are no perfect pangrams that do not include the words “<em>cwm(s)</em>” or “<em>crwth(s)</em>”, both Welsh words. In international Scrabble, the Arabic derived word <em>“waqf(s)”</em> is a valid word which can produce perfect pangrams without resorting to <em>“cwm(s)”</em> or <em>“crwth(s)”</em>.</p><h4>Work Stream Efficiencies</h4><p>It was important to become more efficient at parallelizing tasks during this project. A full run takes 25 minutes for the Unix dictionary and close to an hour for the really large dictionaries. I had some initial trouble context switching for a 30 minute window, but got better at it as I went along to improve my productivity.</p><h3>Extension/Generalization — Anagram Finder</h3><p>The perfect pangram search is also equivalent to an anagram finder for the string “abcdefghijklmnopqrstuvwxyz”. What if you wanted to build a generic anagram finder?</p><p>The same technique can be used as long as the state representation and management rules for checking word combination validity are updated. Instead of having states be managed as an integer, it would be easier to track the state as a map of the relevant characters. Seeing if combinations are valid is to say that the combination of two maps do not exceed the anagram’s desired character count for each letter. Just make sure that the state space is tractable; with too many letters, the search space can get really big in a jiffy. Also, are you allowed to repeat words? Make sure you define those rules inside your dynamic programming solution.</p><h3>Languages w/ Larger Alphabets</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1015/1*2IXptUugL2K-iFmmebakLQ.png" /><figcaption><a href="https://en.wikipedia.org/wiki/Iroha">Iroha</a> is a famous Japanese perfect pangram poem written in the Heian Period</figcaption></figure><p>This approach and solution are linear in the word-set size, but exponential in alphabet size. This approach may not work with a larger character set, say modern Japanese which has 46 syllabaries. 2⁴⁶ is 70,368,744,177,664; over a million times larger than the English search space of 2²⁶ = 67,108,864.</p><p>It’s not entirely clear whether or not this approach would work for Japanese. If Japanese language has sufficiently low entropy, which is possible, this approach would be viable. Instead of initializing an array of size 2⁴⁶, the states will be kept tracked in a map. Furthermore, the structure of Japanese can be exploited; for example the kana <a href="https://en.wikipedia.org/wiki/Wo_(kana)">を (wo)</a> is almost exclusively used as a post positional participle, and can be excluded from the search, reducing the search space.</p><p>The Cambodian language of Khmer has the largest alphabet with 74. Another possible next step is to explore solutions that are sub-exponential in alphabet size.</p><h3>Inspiration</h3><p>I was inspired by <a href="https://www.wired.com/story/an-anti-aging-pundit-solves-a-decades-old-math-problem/">Aubrey De Grey’s advancement</a> in finding the chromatic number of the plane to be at least 5. This is a significant advancement which was achieved through basic computational methods.</p><p>Needless to say, finding perfect pangrams does not hold a candle to improving the lower bound of the chromatic number of a plane.</p><p>This makes me believe that there are a lot of low hanging fruit problems that have simple computational methods towards solving a problem that is manually intractable. I challenge you to find and solve some of these problems. Please let me know if you find something!</p><h3>Thanks</h3><p>I’m quite thankful for my very excellent friends who helped by proofreading and jamming on this with me, especially Anna Zeng, Catherine Gao, Danny Wasserman, George Washington, and Nick Wu!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8c8d0f621bee" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Adventures in Programming Interviews: Misleadingly (NP-)Hard Problem]]></title>
            <link>https://medium.com/hackernoon/adventures-in-programming-interviews-misleadingly-difficult-np-hard-problem-43092597018c?source=rss-4df6101d1879------2</link>
            <guid isPermaLink="false">https://medium.com/p/43092597018c</guid>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Calvin Li]]></dc:creator>
            <pubDate>Thu, 19 Oct 2017 14:31:01 GMT</pubDate>
            <atom:updated>2021-05-19T05:34:44.882Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/782/1*fUYL09d0lff3BAvvcyp3aQ.png" /><figcaption>A directed graph denoting debts between five participants</figcaption></figure><p>It was late in the day, some would consider it evening, and I have already had five consecutive interviews in a row; this company offered no real respite from it all; some interviewers asked if I needed a break, but those questions tend to have only one “correct” answer. I was really tired. All that was left was an algorithm interview from a pair of interviewers.</p><p>They asked this simply framed problem:</p><blockquote>Given a list of debts between pairs of people, minimize the number of transactions needed to clear all debts.</blockquote><p>I ended up receiving an offer, but I did terribly in this interview. My initial instinct was that this was a graph problem, perhaps <a href="https://en.wikipedia.org/wiki/NP-hardness">NP-Hard</a>. My second instinct was that they would not ask an NP-hard question for a simple software engineering role. This assumed my interviewers understood the problem they were asking fully.</p><h3>Their Solution</h3><p>I befriended one of the interviewers later and learned this was what they had in mind:</p><ol><li>Observe that it only matters that people receive or pay the amount needed for them to be made whole, and not where that money came from. For example, if Alice owed Bob $20, and Bob owed Carl $20, then these debts can be cleared by Alice giving Carl $20, even though Alice never directly owed Carl any money.</li><li>Reduce each individual’s debts into a single number, so for example, if Alice owes 3 people $20 each, and 2 people owe Alice $50 each, then Alice is owed $40 (-$20 x 3 + $50 x 2 = $40). Remove people whose debt is $0.</li><li>Separate the people who owe money and those owed money into separate sorted lists or sorted data structures, and then going from the highest value in each category, start pairing them off, and repeating this until the lists are exhausted.</li></ol><p>I went home that day frustrated, and later analyzed this problem more deeply. This problem was decidedly NP-hard. It’s a fun problem, but inappropriate for a software engineering interview.</p><p>The observation and the reduction are correct. The greedy solution is not. Consider this counterexample after steps 1 and 2 above:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/418/1*lSIO-ACjzFf5rtJDG3qmhw.png" /><figcaption>The optimal perfect groupings are drawn in blue and red</figcaption></figure><ul><li>There are three people who owe amounts of $10, $3, and $3, respectively.</li><li>There are three people who are owed amounts of $6, $5, and $5, respectively.</li></ul><p>The correct solution is 4 transactions, where 6 would be paired with the two 3’s the 10 would be paired with the two 5’s. The greedy approach produces 5 transactions.</p><p>Each transaction can eliminate either 1 or 2 participants. The optimal solution maximizes the number of transactions that can eliminate 2 participants. Let’s call a <strong>perfect grouping</strong> as a group of participants who owe debts and are owed debts that can be paired together without remainder. Each perfect grouping of participants introduces a transaction that can eliminate 2 participants.</p><p>The optimal solution would find the two perfect groupings, ($10 | $5, $5) and ($3, $3 | $6). The greedy solution only ever finds everyone as one perfect grouping ($10 $3 $3 | $6 $5 $5).</p><h3><strong>NP-Hard Proof</strong></h3><p>To prove that this problem is NP-Hard, the well-known <a href="https://en.wikipedia.org/wiki/Subset_sum_problem">subset sum problem</a>, which is <a href="https://en.wikipedia.org/wiki/NP-completeness">NP-Complete</a>, can be <a href="https://en.wikipedia.org/wiki/Reduction_(complexity)">reduced</a> to this problem, thus proving that the problem is at least as hard as subset sum. The subset sum problem is a <a href="https://en.wikipedia.org/wiki/Decision_problem">decision problem</a>, where, given a set of integers <strong><em>S</em></strong> and a target integer <strong><em>s</em></strong>, whether there is a non-empty subset of <strong><em>S</em></strong> that sums to <strong><em>s</em></strong>. This reduction will use the positive variant of the subset problem, where all elements of <strong><em>S</em></strong> and the target integer <strong><em>s</em></strong> are positive.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/442/1*sQsDdLgCGyB5fLAilVfEIg.png" /><figcaption>The subset sum problem reduction visualized</figcaption></figure><p>This is the reduction:</p><ol><li>Transform the set of integers <strong><em>S</em></strong> into participants who owe debt of their respective integer values.</li><li>Add two participants who are owed debts of <strong><em>s</em></strong> and <strong><em>t</em></strong>, where <strong><em>t</em></strong> is the sum of all integers in the set <strong><em>S</em> </strong>minus <strong><em>s</em></strong>. This ensures that the sum of debts and sum of money owed are balanced.</li><li>Compute the minimum number of transactions required to clear all debts. <strong><em>n</em></strong> is the number of participants who owe money, e.g. the size of the set <strong><em>S</em></strong>. There are <strong><em>n + 2</em></strong> participants in the reduced problem. Since there are only two people who are owed money, there can be at most 2 perfect groupings. If 2 are found, then the minimum number of transactions required is <strong><em>n</em></strong>, and there is a non-empty subset of <strong><em>S</em></strong> that sums to <strong><em>s</em></strong>. If it’s <strong><em>n + 1</em></strong>, then there is not.</li></ol><p>Through the above reduction, this problem can decide the subset sum problem, which means this problem is at least as hard as subset sum. This problem is NP-Hard. QED.</p><h3>The Solution</h3><p>The solution is to maximize the number of perfect groupings to minimize the number of transactions, because each perfect grouping reduces the number of transactions needed to clear all debts by 1. When there are no strict subsets that are perfect matchings, the entire solution becomes a single perfect grouping. Rephrased, the solution is to maximize the number of distinct subsets that sum to 0.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kSq9lTnmDTSFmi5IvVc1DA.png" /><figcaption>Stepping through the above counterexample to the greedy solution. Invalid states are not drawn in this visualization (there are 60 undrawn states).</figcaption></figure><p>This is the solution I found:</p><ol><li>Reduce each individual’s debts as a single number of the debt that they owe to the collective, those who are owed debts represent their debts as negative numbers.</li><li>Remove the people whose reduced debt value is 0. Let <strong><em>n</em></strong> represent the number of remaining participants after the removal.</li><li>Use a bit mask to represent the state, which is a series of 0’s and 1’s of length n. 0 at the <strong><em>i</em></strong><em>th</em> digit means that the <strong><em>i</em></strong><em>th</em> participant has not had their debt settled, and 1 would mean that <strong><em>i</em></strong><em>th</em> participant has had their debt settled. There are 2^n such states: all 0’s represent the starting state of no settled debts, and all 1’s represents the end state with all debts settled.</li><li>Each state maps to an integer, representing the maximum number of distinct non-empty subset sums. All 0’s have no non-empty subset sums as there are no settled debts, so the value is 0.</li><li>Create a method that takes in the given state, and all the subset sums from the debts of the unsettled participants. For each subset sum found, flip those bits to 1 to represent that they have been settled, and recursively call the same method with the new state.</li><li>Call the method with an initial state of all 0’s.</li><li>The integer value associated with each state that will be cached/memoized is the maximum depth of recursive call stack from all 0’s that it took to reach that state, representing the longest chain (and the most number of distinct non-empty subset sums groupings found). The cache/memoization will ensure that no state gets computed twice.</li><li>Find the integer value for all 1’s. The solution to this problem is the number of participants minus that number,</li></ol><p>Run time analysis: At each state, there needs 2^k operations, where k is the number of unsettled participants debts to consider. There are (n choose k) states for a given k. Precompute all possible sums and store them into a lookup table O(2^n). Using the precomputed lookup table, there are O(2^k) operations per state, the big O runtime of this algorithm is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/264/1*e4Z65yw6YT7XJozOnSbMLQ.png" /></figure><p>A good explanation of why the two sides are equal can be found <a href="https://math.stackexchange.com/questions/1679305/prove-sumn-k-0n-choose-k-2k-3n">here</a>. This algorithm will take O(2^n) space as there are O(2^n) states and O(2^n) sums.</p><h3>Afterwards</h3><p>The most frustrating part about all of this was that my interviewers thought that the problem was way easier than it actually is, and reported that I was not able to solve such an easy problem in the span of 45 minutes. This specific interview significantly hurt the offer I received. Unfortunately, there’s a lot of luck to the interview process as there is a lot of luck in life. The best things to do are to learn to not assume that the interviewers fully understand their own questions, and write a blog post about it.</p><p><em>Thank you Daniel Wasserman for helping me look over this article!</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=43092597018c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hackernoon/adventures-in-programming-interviews-misleadingly-difficult-np-hard-problem-43092597018c">Adventures in Programming Interviews: Misleadingly (NP-)Hard Problem</a> was originally published in <a href="https://medium.com/hackernoon">HackerNoon.com</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Past Writing: Post 2016 Election Response]]></title>
            <link>https://medium.com/@FallingForFallacies/past-writing-post-2016-election-response-c64b2b6a30c7?source=rss-4df6101d1879------2</link>
            <guid isPermaLink="false">https://medium.com/p/c64b2b6a30c7</guid>
            <dc:creator><![CDATA[Calvin Li]]></dc:creator>
            <pubDate>Tue, 03 Jan 2017 21:25:55 GMT</pubDate>
            <atom:updated>2017-01-03T21:25:55.130Z</atom:updated>
            <content:encoded><![CDATA[<p>Past Writing: Post 2016 Election Response</p><p>I wrote this the morning after the election. Hoping that this will be my blog of sorts, I am putting it here for future reference of my past writings:</p><p>We learned a lot about America recently, and not in the <a href="https://www.facebook.com/hashtag/apocalypse2016?source=feed_text&amp;story_id=10154249237677561">#apocalypse2016</a> kind of way.</p><p>I am devastated by the result, but I can not and will not label blindly half the country as racists, bigots, fascists, what have you, because that means we have learned nothing from this. If we learn nothing from this, things can get worse; it can always get worse.</p><p>I have very strong convictions that a Trump presidency would not have been possible without the racists, bigots, and fascists, but everyone has to recognize that fundamentally good Americans casted their ballot for one of the most unconventional candidates. Why is that?</p><p>The reason I want to highlight is that we have not taken it upon ourselves to solve the divide in our country. It is too simple, too easy, and, to some, too satisfying, to label someone who supported Trump a racist and a bigot. That in itself is a form of bigotry. That attitude only widens the wound in this country and we have paid for it dearly.</p><p>We have not listened to what the other half of the country is saying and I am not sure we have cared. It’s hard to listen to the other side fight against gay marriage and not “believe” in global warming. It’s probably harder to listen past that, and find their concerns and uncertainty they feel in a world that is leaving them behind, with nobody to extend a helping hand.</p><p>The way to heal this divide is to make a friend with someone who supported Trump (or vice versa), and don’t start with politics because that will likely go very poorly. Remember that we are all people and all living in the same country, drinking the same water, watching the same shows. While this partisan divide exists on the highest level of our democracy, that’s only a symptom. We can all begin healing our country by opening up our hearts and creating relationships, friendships, with the other side.</p><p>Then we can hopefully make progress for a better America.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c64b2b6a30c7" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Writing is so hard]]></title>
            <link>https://medium.com/@FallingForFallacies/writing-is-so-hard-b2543c175b63?source=rss-4df6101d1879------2</link>
            <guid isPermaLink="false">https://medium.com/p/b2543c175b63</guid>
            <category><![CDATA[writing]]></category>
            <category><![CDATA[habit-building]]></category>
            <dc:creator><![CDATA[Calvin Li]]></dc:creator>
            <pubDate>Sun, 31 Jul 2016 19:19:01 GMT</pubDate>
            <atom:updated>2016-07-31T19:19:01.301Z</atom:updated>
            <content:encoded><![CDATA[<p>Since writing is so hard, I thought I’d begin with a boring post complaining about how hard it is to do something that millions of people effortlessly do every single day.</p><p>The most impactful changes are those derived from habit; habitual exercise will trump blue-moon gym visits. I’ll try to make writing a habit, but as with most things, I hope this doesn’t fade into a non-habit-forming desire.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b2543c175b63" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>