Frenetic Array

A canvas for logic and imagination.

Rearranging Alphabetically-Sorted Lists

As I was rearranging some of playlists in overcast, I settled on a two-playlist scheme:

  1. Main Queue All of my main podcasts I listen to.
  2. Global Queue All of podcasts that either I can’t listen to at this time (spoilers, typically) or a series I am going through a back-catalog of.

This is a very nice scheme, until you look at it in my podcast player.

The playlist I listen to 99% of the time is at the bottom — and this frustrated me. A lot.

Fortunately, I found a way to rearrange alphabetically-ordered lists: paste a leading zero width space in front of items that you want to be lower in the list.

The zero width space comes after alphabetical letters when sorted, so naturally it will be put down further in the list. If there are more than two items on the list, keep adding leading zero width spaces to put the item further down.

An easy way to get a zero width space on the clipboard can be found here.

Sanity restored.

Calculating Euler's Number

We are well aware of Euler’s famous number,

$$e = 2.71828182845$$

There are also quite a few ways of deriving Euler’s Number. There’s the Taylor expansion method:

$$e = \sum _{k=0} ^{\infty} \frac{1}{k!}$$

There is also the classical limit:

$$e = \lim_{n \rightarrow \infty} \left( 1 + \frac{1}{n} \right)^n$$

Then there is a unique way of calculating. Let $R$ be a random number generated between $[0, 1]$, inclusive. Then $e$ is the average of the number of $R$s it takes to sum greater than $1$. In other words, keeping adding a random numbers with bounds $[0, 1]$ together until you exceed one, average a bunch of attempts together, and you should get $e$.

With more rigor, for uniform $(0, 1)$ random independent variables $R_1$, $R_2$, $\ldots$, $R_n$,

$$N = min \left\{ n: \sum_{k=1} ^{\infty} R_i > 1 \right\}$$

then we can calculate $e$ as such:

$$e = Average(N)$$

The proof can be found here, but it is pretty rigorous. Instead, an easier method is to write a program to verify for large enough $n$.

For $n= 1,000,000,000$1, we have the following results

e Sum Solution Limit Solution Random Uniform Variable
2.7182818284 2.7182818284 2.7182820520 2.718250315

Feel free to checkout the code below, or skim the all of the data to see the asymptotic approach towards $e$.

All Data

n Sum Solution Limit Solution Random Uniform Variable
1 2 2 2
10 2.7182818011 2.5937424601 2.5
100 2.7182818284 2.7048138294 2.69
1000 2.7182818284 2.7169239322 2.717
10000 2.7181459268 2.7242
100000 2.7182682371 2.71643
1000000 2.7182804690 2.71961
10000000 2.7182816941 2.7182017
100000000 2.7182817983 2.71818689
1000000000 2.7182820520 2.718250315

Source Code

import random  
import math  
import sys

from decimal import Decimal

def e_sum(upper_bound):  
    if upper_bound < 0:
        return 0

    return Decimal(1.0) / Decimal(math.factorial(upper_bound)) + Decimal(e_sum(upper_bound - 1))

def e_limit(n):  
    return Decimal((1 + 1.0 / float(n))**n)

def find_greater_than_one(value=0, attempts=0):  
    if value <= 1:
        return find_greater_than_one(value + random.uniform(0, 1), attempts + 1)

    return attempts
  1. For all except the sum calculation. Because it is summation, with a factorial inside the summation, calculating takes a long time (and if done recursively, and stack overflow).

House of Cards (Kattis Problem)

It’s not so often I come across a problem that works out so beautifully yet requires so many different aspects in competitive programming. One particular problem, courtesy of Kattis, really did impress me.

The problem was House of Cards, and the problem was this (skip for TL;DR at bottom):

Brian and Susan are old friends, and they always dare each other to do reckless things. Recently Brian had the audacity to take the bottom right exit out of their annual maze race, instead of the usual top left one. In order to trump this, Susan needs to think big. She will build a house of cards so big that, should it topple over, the entire country would be buried by cards. It’s going to be huge! The house will have a triangular shape. The illustration to the right shows a house of height $6$ and Figure 1 shows a schematic figure of a house of height $5$.

Figure 1

For aesthetic reasons, the cards used to build the tower should feature each of the four suits (clubs, diamonds, hearts, spades) equally often. Depending on the height of the tower, this may or may not be possible. Given a lower bound $h_0$ on the height of the tower, what is the smallest possible height $h \geq h_0$ such that it is possible to build the tower?

TL;DR: Using Figure 1 as a reference, you are given a lower bound on a height for a tower of cards. However, there must be an equal distribution of all four suites; clubs, diamonds, hearts, and spades.

This implies that the number of cards have to be divisible by $4$. Seeing as the input was huge $1 \leq h_0 \leq 10^{1000}$, there was no brute forcing this. So, first thought: turn this into a closed-form series, and solve the series.

Getting the values for the first five heights, I got the following set:

$${2, 7, 15, 25, 40, \ldots}$$

I was able to turn this set into a series quite easily:

$$\sum_{n = 1} ^{h_0} \left(3n - 1\right)$$

This turned into the following equation:

$$\frac{1}{2} h_0(3h_0 + 1)$$

So, all I had to do was plug $h_0$ in the equation, and increment while the number was not divisible by $4$. Then, I realized how large the input really was. The input size ($1 \cdot 10^{1000}$) was orders of magnitudes larger than typical, large data types would allow ($1.84 \cdot 10^{19}$).

I realized this couldn’t be tested against a intensive data set, because there is only one number to calculate. I thought, since the series always subtracts one, the minimum times I must increment should roughly be four. Keeping this in mind, I decided to use Python. Python can work with arbitrarily large numbers, making it ideal in this situation.

I sat down, hoped for the best, and wrote the following code.

def getNumberOfCards(x):  
    return (3*pow(x, 2) + x) // 2

height = int(input())  
while (getNumberOfCards(height) % 4 != 0):  
    height += 1


With a run time of 0.02 seconds, it worked.

Avoid Mac App Store via The Terminal

I avoid the Mac App store as much as possible. It’s buggy. It’s slow. Apps are getting pulled from it left and right. But, I could not avoid it permanently because of software updates. As macOS Sierra 10.5 rolled out, I clicked on the App Store, followed by updates, and

I could not get the updates page opened. Killed App Store. Restart computer. Everything.

After doing some research, I discovered there is a way to update software from the terminal: softwareupdate. So, after running one command (sudo softwareupdate -iv), I am writing this for the latest version of macOS Sierra.

Quick Compile in Vim

One of the reasons I kept CodeRunner handy was its ability to quickly compile code. With a single click of a button, I could run any of my frequently used languages. It didn’t matter if it was an interpreted or compiled language, so I could virtually run anything, like:

  • C/C++
  • Python
  • Lua
  • LaTeX
  • Perl

However, in the last few months I started using Vim. Heavily. So much so I was trying to use Vim command in the CodeRunner buffers. So I decided I wanted to have the functionality, and in vim-esque fashion, I mapped to my leader key: <leader>r. The mnemonic <leader>run helped me remember the command on the first few tries.

To get the functionality, just add the following to your .vimrc.

function! MakeIfAvailable()  
    if filereadable("./makefile")
    elseif (&filetype == "cpp")
        execute("!clang++ -std=c++14" + bufname("%"))
    elseif (&filetype == "c")
        execute("!clang -std=c11" + bufname("%"))
    elseif (&filetype == "tex")
        execute("!xelatex" + bufname("%"))
        execute("!open" + expand(%:r) + ".pdf")

augroup spaces  
    autocmd FileType c nnoremap <leader>r :call MakeIfAvailable()<cr>
    autocmd FileType cpp nnoremap <leader>r :call MakeIfAvailable()<cr>
    autocmd FileType tex nnoremap <leader>r :call MakeIfAvailable()<cr>
    autocmd FileType python nnoremap <leader>r :exec '!python' shellescape(@%, 1)<cr>
    autocmd FileType perl nnoremap <leader>r :exec '!perl' shellescape(@%, 1)<cr>
    autocmd FileType sh nnoremap <leader>r :exec '!bash' shellescape(@%, 1)<cr>
    autocmd FileType swift nnoremap <leader>r :exec '!swift' shellescape(@%, 1)<cr>
    nnoremap <leader>R :!<Up><CR>
augroup END