Another LeetCode problem.

Given an MxN matrix of numbers, find the longest path of strictly increasing numbers.

So for example in this matrix:

You can start with the 1 in the bottom center, go left to the two, then up to the 6, and 9. That’s the longest path, so return a 4.

In this 3x3 case, it’s really easy to just brute force. Calculate all possible paths. An upper bound would be visiting every node exactly once, so \sum_{i=1}^9 \binom{9}{i} = 511 (choose n elements for each of 1 to 9 cases). Not so bad. But if you have a 10x10 matrix, that’s already 1e30–which is freaking gigantic. So we need to do better.

read more...

Okay, let’s take this one step further. Rather than generating just phone words, let’s actually generate phone words. Someone has provided a list of words in English as a package, so we’ll add a filter to add that to our comprehension:

from english_words import english_words_set

def letterCombinations(self, digits: str) -> List[str]:
    if not digits:
        return []

    letters = {
        '1': '',
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
        '0': ' ',
    }

    return [
        word
        for product in itertools.product(*[
            letters[digit] for digit in digits
        ])
        if ((word := ''.join(product)) in english_word_set)
    ]

I think I like the Walrus/assignment operator (:=), but it still is a bit bizarre at times. Basically, what it does is assign a call to a value (word = ''.join(product) in this case), but also returns it and can be used as an expression, which = cannot. So we can immediately check if it is in english_words. Since that’s a set, it should be pretty fast.

read more...

Working through a few problems on LeetCode. I haven’t quite decided what I think of the site, but it’s a fun way to play with simple algorithms. Figured I might as well write up any I find interesting.

First interesting problem:

Given a standard lettered keypad, generate all words from a given phone number.

read more...

Today’s goal: Turn a collection of YouTube links into a podcast.

Start with a config.json like this:

{
  "brandon-sanderson": [
    "https://www.youtube.com/watch?v=H4lWbkERlxo&list=PLSH_xM-KC3ZuOZayK68JAAjj5W9ShnFVC",
    "https://www.youtube.com/watch?v=YyaC7NmPsc0&list=PLSH_xM-KC3ZtjKTR2z8rPWxv1pP6bOVzZ",
    "https://www.youtube.com/watch?v=o3V0Zok_kT0&list=PLSH_xM-KC3ZuteHw3G1ZrCDWQrAVgO0ER"
  ]
}

And it will automatically download all referenced YouTube videos, convert them to MP3 (both using youtube-dl), and serve an RSS feed that’s compatible with most podcast programs.

Tested URLs include:

• Playlist URLs (like the above)
• Single video URLs
• Channel URLs

Most youtube URLs should work though.

read more...

Another quick post.

What feels like a lifetime ago, I wrote a post about finding ec2 instances by name. I honestly use that script just about every day, mostly for automatically finding instances to SSH to (a la SSH config tricks). But there are a few other quick things I’ve done with it:

• ec2-script - Run a script on all instances of a given name
• ec2-disk - A specialization of ec2-script to check main disk usage
• terminate - A script that I use with ec2 to terminate instances from the command line
• ec2-cycle - Slow cycle a given set of ec2 instances by terminating so many per minute

All of which are included in my dotfiles.

read more...

The Sender Policy Framework is one of those things that’s really powerful and useful to help prevent phishing and email spam, but can be a royal pain to work with. Specifically, SPF is a series of DNS TXT records¹ with a specific format that can be looked up by any email service to verify that an email was sent by a server that should be authorized to send email on your behalf. For example

"v=spf1 ip4:192.0.2.0/24 ip4:198.51.100.123 a -all"

• v=spf1 - tells the client this is an SPF record and should always start the record
• {key}[:{value}]? - one of many different key/value pairs that can define the record
  • in the case above a ip4 key species an IPv4 address range that can send emails on your behalf (the value can be optional)
  • the a above is another special case where if the sender domain ([email protected] would be example.com) resolves via a DNS A record to the server that sent the email, it’s allows
• -all is a fallthrough case meaning ‘fail all that didn’t match a previous case

There are a number of other cases, but we’ll get to the other interesting ones in a bit.

read more...

Another thing that came up recently: we have many (many) sidekiq queues. Each has their own admin interface, but sometimes you just want all of the information in one place. Of course, you could bookmark all of the pages. Or make a single page with a lot of frames (remember HTML frames?). Or use their API. But where’s the fun in that? Instead, let’s dig straight into the redis backend and see what we can see!

read more...

One thing that I often need to do is deal with a large collection of database servers in different clusters and in different environments. On top of that, sometimes, I want a UI, sometime I want a CLI to script. And sometimes I’m on a VPN and sometimes I’m not. All together, it’s a rather complicated number of saved connections and CLI switches and everything else. All together, I want:

• Specify the cluster, environment, and mode (read/write/adhoc)
• Specify if I want to run via CLI or via UI
• Specify an optional user with safely stored and used passwords
• Automatically connected via SSH tunnel if I’m not on VPN, but not if I am (for CLI or VPN)

Let’s do it!

read more...

For a number of years now, I’ve been writing down my ‘observations’. Essentially, it’s a semi-structured set of text files that I keep in Dropbox. One for each day, in a folder by month. I record interesting people I see, things I did worth doing, and things my children did which were adorable.

After a while, I started wanting to look back, so first, I wrote a relatively simple script that would go back through my archives and send me everything I did 1/2/3/4/etc years ago. That worked well enough, but it ended up generating a lot of emails to go through some days. So the second generation is a server that can format those pages and display them as a nice webpage.

The most interesting part perhaps was dealing with the tarballs that I keep the archives in (they’re plain text, so they compress very well). I wanted to keep them compressed, so I had to decompress them in memory on the fly.

read more...

If you have a website that allows users to submit URLs, one of the (many many) things people will try to do to break your site is to submit URLs that use the javascript: protocol (rather than the more expected http: or https:). This is almost never something that you want, since it allows users to submit essentially arbitrary code that other users will run on click in the context of your domain (same origin policy).

So how do you fix it?

First thought would be to try to check the protocol:

> safe_url = (url) => !url.match(/^javascript:/)
[Function: safe_url]

> safe_url('http://www.example.com')
true

> safe_url('javascript:alert(1)')
false

read more...