/dev/random

Vim Window Resizing

Fri Dec 14 14:55:41 2018

Quick reminders for self:

Documentation: Windows

Highlights

" Make only window
Ctrl + w, o

" Open window in new tab
Ctrl + w, T

" Increase current window by 10
10 Ctrl + w, >

brew macvim woes

Sun Nov 11 15:15:04 2018

When you get the lovely library not found errors after installing macos security updates:

$ gvim
$ dyld: Library not loaded: /System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/lib/libruby.2.0.0.dylib

After much heartache and googling, here's how you force brew to install macvim using the ruby version on your PATH:

l00k:~$ brew install --env=std macvim --HEAD
Updating Homebrew...
==> Cloning https://github.com/macvim-dev/macvim.git
Cloning into '/Users/mcadiz/Library/Caches/Homebrew/macvim--git'...
==> Checking out branch master
Already on 'master'
Your branch is up to date with 'origin/master'.
==> ./configure --with-features=huge --enable-multibyte --with-macarchs=x86_64 --enable-perlinterp --enable-rubyinterp --enable-tclinterp --enable-terminal --with-tlib=ncurses --w
==> make
🍺  /usr/local/Cellar/macvim/HEAD-2c43cd6: 2,185 files, 37.9MB, built in 1 minute 12 seconds

Iterated logarithm

Wed Oct 31 13:51:59 2018

The iterated logarithm (written "log*" and read "log star") is: "the number of times the logarithm function must be iteratively applied before the result is <= 1".

Among other things, it's useful in analyzing the running time of the Find and Union operations in the union find datastructure that uses path compression.

Here's a ruby snippet that computes iterated logarithm values for numbers <= 2^65536 (i.e. 2^(2^16)).

def log_star(x)
  return 0 if x <= 0

  count = 0
  while x >= 1 do
    x = Math.log2(x)
    count += 1
  end

  count
end

[0, 1, 2, 3, 4, 15, 16, 65535, 65536, 2**65535, 2**65536].map do |i|
  if i <= 65536
    "log* #{i}: #{log_star(i)}"
  else
    "log* 2^#{Math.log2(i).to_i}: #{log_star(i)}"
  end
end
.tap do |res|
  width = res.map(&:size).max
  puts res.map {|x| x.rjust(width)}
end

$ ruby iterated_logarithm.rb
      log* 0: 0
      log* 1: 1
      log* 2: 2
      log* 3: 2
      log* 4: 3
     log* 15: 3
     log* 16: 4
  log* 65535: 4
  log* 65536: 5
log* 2^65535: 5
log* 2^65536: 6

Bash 'Command' Builtin

Tue Oct 30 12:47:21 2018

According to the manual,

command -v  <command>

...causes a single word indicating the command or file name used to invoke command to be displayed.

Very useful when which foo doesn't work (for example nvm which is a sourced function defined during shell creation).

discrete math

Sun Sep 16 16:19:33 2018

Starting a new GitHub repo with code for theorems, corollaries, and exercises from Discrete Mathematics: Elementary and Beyond.

One thing to note is that all of the code will be written in C++ (trying to get up to speed with C++11!!) and is intended to be run in a docker container. You can find the image here.

The image has all of the necessary dev tools installed (compilers, test libraries, linters, etc) so that you can compile and run the tests as long as you have docker installed.

See the README for more info.

First exercise is straightforward decimal to binary conversion:

std::string dec2bin(int64_t n) {
  if (n < 0) {
    throw std::out_of_range("`n' must be nonnegative");
  } else if (n == 0) {
    return "0";
  }

  std:: string s;

  while (n) {
    auto t = n & 1 ? "1" : "0";
    s.insert(0, t);
    n >>= 1;
  }

  return s;
}

killall Dock

Mon Jul 30 18:27:40 2018

Often, for when unplugging from thunderbolt, the OS X user interface will get borked and be unable to switch Desktops, launch Launchpad, use Spotlight, etc...

To "fix" the issue I was previously just rebooting my machine. But the other I learned another much less painful workaround:

$ killall Dock

Ruby defaultdict

Fri May 25 17:49:43 2018

For those coming from Python, it may be surprising that the new(obj) -> new_hash method doesn't behave like Python's defaultdict.

Ruby

irb(main):001:0> foo = Hash.new([])
=> {}
irb(main):002:0> foo[:bar].push(1)
=> [1]
irb(main):003:0> foo[:baz].push(2)
=> [1, 2]
irb(main):004:0> foo
=> {}

Python

In [1]: from collections import defaultdict
In [2]: foo = defaultdict(list)
In [3]: foo['bar'].append(1)
In [4]: foo['baz'].append(2)
In [5]: foo
Out[5]: defaultdict(list, {'bar': [1], 'baz': [2]})

Instead what you want is the block form new {|hash, key| block } -> new_hash:

irb(main):001:0> foo = Hash.new {|h, k| h[k] = []}
=> {}
irb(main):002:0> foo[:bar].push(1)
=> [1]
irb(main):003:0> foo[:baz].push(2)
=> [2]
irb(main):004:0> foo
=> {:bar=>[1], :baz=>[2]}

Docker detach

Fri May 4 11:30:56 2018

Goal: attach to a running Docker container and then detach without killing it.

Two possbile solutions:

Always remember to spin up (exec/run) containers using the -i -t flags (interactive and pseudo-tty respecively) so that you can use the detach key sequence (ctl-p, ctrl-q by default) to actually detach from the container.
Pass --sig-proxy=false when you attach so that SIGKILL is not proxied to the container and stays in the current shell.

Additive Inverse

Wed Apr 18 19:16:42 2018

Obtaining the additive inverse of a two's complement integer using bitwise negation and addition:

In [1]: x = 2
In [2]: ~x + 1
Out[2]: -2
In [3]: x = -77
In [4]: ~x + 1
Out[4]: 77

Remove from Chrome dropdown

Tue Apr 17 14:01:03 2018

The magic keyboard sequence to remove a saved entry (such as email) from Chrome's dropdown:

1. Select entry from dropdown
2. <fn> + <shift> + <delete>

Database N+1 Queries

Fri Mar 23 19:11:35 2018

Was recently reminded to always be on the lookout for potential n+1 query pitfalls. Take a look at the code before:

index = (string.size-1).downto(0).find {|i| Foo::Model.find_by(bar: string[0..i])}
index ? string[0..index] : nil

Versus the after:

candidates = string.length.times.map {|i| string[0..i]}
Foo::Model.where(bar: candidates).order('length(bar) desc').take&.bar

Much nicer doing 1 trip to the db with the query selecting and sorting instead of searching candidates one by one, up to string.length times.

Book: The Power of Habit (Duhigg)

Wed Mar 7 22:29:51 2018

Just finished The Power of Habit by Charles Duhigg. A great read that I can't recommend enough. As an aside, making a conscious effort to make reading a "habit" =P and will be keeping myself honest here on this blog.

Associative entity

Thu Mar 1 18:44:02 2018

Since I always forget the correct ER name for a "join table", here it is, associative entity.

AWS S3

Mon Jan 29 18:46:26 2018

Copy a file to a new subfolder within an existing s3 bucket (named incoming).

$ aws s3 --profile=admin cp bad-data.log s3://incoming/foo/bar/
$ aws s3 --profile=admin ls s3://incoming --recursive

Recursive Cartesian Product

Mon Dec 4 18:54:47 2017

A recursive approach to Python's iterative method for the Cartesian product:

def product(*args):
    res = []
    product_helper([], args, 0, res)
    return res


def product_helper(prefix, pools, offset, res):
    if offset >= len(pools):
        res.append(tuple(prefix))
        return

    pool = pools[offset]

    for i in range(len(pool)):
        product_helper(prefix + [pool[i]], pools, offset + 1, res)


if __name__ == '__main__':
    import itertools
    L = ['abc', 'def']
    assert product(*L) == list(itertools.product(*L))

Products and trees

Sat Nov 4 16:40:47 2017

def product_others(L):
    """
    Return an array M where the value at each index i is the product
    of all values in L except for L[i]

    Constraint: only use multiplication operator
    """
    product = lambda x, y: x * y

    # value at index i is the product of all prev in L
    before = [
        reduce(product, L[:i], 1)
        for i in range(len(L))
    ]

    # value at index i is the product of all next in L
    after = [
        reduce(product, L[i+1:], 1)
        for i in range(len(L))
    ]

    return [x * y for (x, y) in zip(before, after)]


def reconstruct(inorder, postorder):
    """
    Reconstruct and return the root of the tree that yields the
    passed inorder and postorder traversals
    """
    assert len(inorder) == len(postorder)

    if not inorder:
        return

    # root is always last entry
    root = Node(postorder[-1])
    # find index of root in inorder
    i = inorder.index(root.data)

    # left subtree of tree rooted at root
    inorder_left = inorder[:i]
    # right subtree of tree rooted at root
    inorder_right = inorder[i+1:]

    postorder_left = postorder[:i]
    postorder_right = postorder[len(postorder_left):-1]

    root.left = reconstruct(inorder_left, postorder_left)
    root.right = reconstruct(inorder_right, postorder_right)

    return root


if __name__ == '__main__':
    L = [2, 4, 1, 3]
    assert [12, 6, 24, 8] == product_others(L)

    #
    #           1
    #          / \
    #         2   3
    #        / \ / \
    #       4  5 6  7
    #        \
    #         8
    #
    t1 = Node(1)
    t1.left = Node(2)
    t1.right = Node(3)
    t1.left.left = Node(4)
    t1.left.right = Node(5)
    t1.right.left = Node(6)
    t1.right.right = Node(7)
    t1.left.left.right = Node(8)

    A, B = [], []
    inorder(t1, A)
    postorder(t1, B)

    t2 = reconstruct(A, B)

    C, D = [], []
    inorder(t2, C)
    postorder(t2, D)

    assert A == C
    assert B == D

Git: cleanup merged branches

Mon Oct 23 12:21:57 2017

Delete local branches already merged to develop.

$ git br --merged develop | grep -v 'develop|master' | xargs git br -d

Combinatorics refresher

Sat Oct 21 16:22:01 2017

Power set, permutations, and combinations.

Note that for permutations, can augment to get the k-length permutations by return slices of length k ([v + perm][:k]).

def powerset(S):
    """
    Return the set of all (2^N) subsets of S (including empty set and S itself)
    """
    res = []

    for i in range(2**len(S)):
        T = []
        for j in range(len(S)):
            if (1 << j) & i:
                T.append(S[j])
        res.append(T)

    return res


def permutations(L):
    """
    Return all n! (n-factorial) permutations of elements in L
    """
    if len(L) <= 0:
        return []
    elif len(L) == 1:
        return L

    res = []
    for i, v in enumerate(L):
        prefix = L[:i]
        suffix = L[i+1:]
        for perm in permutations(prefix + suffix):
            res.append(v + perm)

    return res


def combinations(k, L):
    """
    Return all (binomial coefficient) k-length combinations of elements in L
    """
    if k == 0:
        return [[]]

    res = []
    for i, v in enumerate(L):
        for suffix in combinations(k-1, L[i+1:]):
            res.append([v] + suffix)

    return res

Run-length encoding

Wed Oct 18 18:58:31 2017

Given an arbitrary string of fixed length, implement a function that compresses the string by removing repeated characters and providing a count of how many are upcoming instead

def rle(S):
    res, count = [], 1

    for i, s in enumerate(S):
        try:
            lookahead = S[i+1]
        except IndexError:
            lookahead = None

        if s == lookahead:
            count += 1
            continue

        if count > 1:
            res.append(str(count))
            count = 1
        res.append(s)

    return ''.join(res)

assert rle('WB') == 'WB'
assert rle('WWB') == '2WB'
assert rle('WWBB') == '2W2B'
assert rle('WWBW') == '2WBW'
assert rle('WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW') == '12WB12W3B24WB14W'

Last git branch

Tue Oct 17 13:41:29 2017

Note to self: to avoid mass proliferation of already merged local branches:

l00k:~/workspace/src/foo-proj (feature-foo) $ git co develop
l00k:~/workspace/src/foo-proj (develop) $ git br -d @{-1}
Deleted branch feature-foo (was 8169880).

YubiKey All The Things

Fri Sep 29 20:21:59 2017

Mostly notes to self, extracted from the very thorough guide here.

l0st:~$ gpg --recv 0x210583A0ECB0AFA4
gpg: key 0x210583A0ECB0AFA4: public key "Michael Cadiz <mike@cadizm.com>" imported
gpg: Total number processed: 1
gpg:               imported: 1

l0st:~$ gpg --card-status
Reader ...........: Yubico Yubikey 4 OTP U2F CCID
Application ID ...: D2760001240102010006064714440000
Version ..........: 2.1
Manufacturer .....: Yubico
Serial number ....: 06471444
Name of cardholder: Michael Cadiz
Language prefs ...: en
Sex ..............: unspecified
URL of public key : [not set]
Login data .......: mike@cadizm.com
Signature PIN ....: not forced
Key attributes ...: rsa2048 rsa2048 rsa2048
Max. PIN lengths .: 127 127 127
PIN retry counter : 3 0 3
Signature counter : 0
Signature key ....: 937F C389 F454 379B 0AFA  91B7 FFFC 7132 9711 5C2D
      created ....: 2017-09-30 00:56:00
Encryption key....: AE92 FBF9 2649 FA40 6B8E  7E0F 601C 0549 9658 64FF
      created ....: 2017-09-30 00:56:43
Authentication key: 8CDF 1B3D 174B 9516 AFFC  127A 6E4E 403F 1B48 9938
      created ....: 2017-09-30 00:57:04
General key info..: sub  rsa2048/0xFFFC713297115C2D 2017-09-30 Michael Cadiz <mike@cadizm.com>
sec#  rsa2048/0x210583A0ECB0AFA4  created: 2017-09-30  expires: never
ssb>  rsa2048/0xFFFC713297115C2D  created: 2017-09-30  expires: never
                                  card-no: 0006 06471444
ssb>  rsa2048/0x601C0549965864FF  created: 2017-09-30  expires: never
                                  card-no: 0006 06471444
ssb>  rsa2048/0x6E4E403F1B489938  created: 2017-09-30  expires: never
                                  card-no: 0006 06471444

l0st:~$ gpg --list-keys
/Users/mcadiz/.gnupg/pubring.kbx
--------------------------------
pub   rsa2048/0x210583A0ECB0AFA4 2017-09-30 [SC]
      Key fingerprint = 204E 949F 17A5 B8EF E8DB  0571 2105 83A0 ECB0 AFA4
uid                   [ unknown] Michael Cadiz <mike@cadizm.com>
sub   rsa2048/0xFFFC713297115C2D 2017-09-30 [S]
sub   rsa2048/0x601C0549965864FF 2017-09-30 [E]
sub   rsa2048/0x6E4E403F1B489938 2017-09-30 [A]

l0st:~$ gpg --edit-key 0x210583A0ECB0AFA4
gpg (GnuPG) 2.2.1; Copyright (C) 2017 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Secret key is available.

pub  rsa2048/0x210583A0ECB0AFA4
     created: 2017-09-30  expires: never       usage: SC
     trust: unknown       validity: unknown
ssb  rsa2048/0xFFFC713297115C2D
     created: 2017-09-30  expires: never       usage: S
     card-no: 0006 06471444
ssb  rsa2048/0x601C0549965864FF
     created: 2017-09-30  expires: never       usage: E
     card-no: 0006 06471444
ssb  rsa2048/0x6E4E403F1B489938
     created: 2017-09-30  expires: never       usage: A
     card-no: 0006 06471444
[ unknown] (1). Michael Cadiz <mike@cadizm.com>

gpg> trust
pub  rsa2048/0x210583A0ECB0AFA4
     created: 2017-09-30  expires: never       usage: SC
     trust: unknown       validity: unknown
ssb  rsa2048/0xFFFC713297115C2D
     created: 2017-09-30  expires: never       usage: S
     card-no: 0006 06471444
ssb  rsa2048/0x601C0549965864FF
     created: 2017-09-30  expires: never       usage: E
     card-no: 0006 06471444
ssb  rsa2048/0x6E4E403F1B489938
     created: 2017-09-30  expires: never       usage: A
     card-no: 0006 06471444
[ unknown] (1). Michael Cadiz <mike@cadizm.com>

Please decide how far you trust this user to correctly verify other users' keys
(by looking at passports, checking fingerprints from different sources, etc.)

  1 = I don't know or won't say
  2 = I do NOT trust
  3 = I trust marginally
  4 = I trust fully
  5 = I trust ultimately
  m = back to the main menu

Your decision? 5
Do you really want to set this key to ultimate trust? (y/N) y

pub  rsa2048/0x210583A0ECB0AFA4
     created: 2017-09-30  expires: never       usage: SC
     trust: ultimate      validity: unknown
ssb  rsa2048/0xFFFC713297115C2D
     created: 2017-09-30  expires: never       usage: S
     card-no: 0006 06471444
ssb  rsa2048/0x601C0549965864FF
     created: 2017-09-30  expires: never       usage: E
     card-no: 0006 06471444
ssb  rsa2048/0x6E4E403F1B489938
     created: 2017-09-30  expires: never       usage: A
     card-no: 0006 06471444
[ unknown] (1). Michael Cadiz <mike@cadizm.com>
Please note that the shown key validity is not necessarily correct
unless you restart the program.

gpg> quit

l0st:~$ gpg --list-keys
gpg: checking the trustdb
gpg: marginals needed: 3  completes needed: 1  trust model: pgp
gpg: depth: 0  valid:   1  signed:   0  trust: 0-, 0q, 0n, 0m, 0f, 1u
/Users/mcadiz/.gnupg/pubring.kbx
--------------------------------
pub   rsa2048/0x210583A0ECB0AFA4 2017-09-30 [SC]
      Key fingerprint = 204E 949F 17A5 B8EF E8DB  0571 2105 83A0 ECB0 AFA4
uid                   [ultimate] Michael Cadiz <mike@cadizm.com>
sub   rsa2048/0xFFFC713297115C2D 2017-09-30 [S]
sub   rsa2048/0x601C0549965864FF 2017-09-30 [E]
sub   rsa2048/0x6E4E403F1B489938 2017-09-30 [A]

l0st:~$ ssh-add -L
The agent has no identities.
l0st:~$ pkill ssh-agent && pkill gpg-agent && eval $(gpg-agent --daemon --enable-ssh-support  --log-file ~/.gnupg/gpg-agent.log)
l0st:~$ ssh-add -L
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQC5xxrkhC2MnXO2HJzJL7kFPhE71pejZMNZ8SwYDMlQoRCnuvNZ9eDy+ped+nCO+SEyNcMlike6clG6/iepfXNteqpaM4mmH9UyKmbdVLr3Vks1dMUI9TL9DHzIe7KvogmHdV+Fg30m13pKbknFES7HGBjAV6U8EXteT4v17dSZ/P2B3l4EdmTAtgWfsQnSEecd5SKVWpdOovL/h67W4zrgTKcQZB5h3sW7TyPSSgEF30Bdt8gv8/nZJtv2husSZaIRzm7V4Y3ikP1Lh3QdSQenTAjcWRRh/X+9ueXyc5zqGQu/i+PPriZIdIqN2T+ql5FXTdni5W4Se0Fhm7SvHVwd cardno:000606471444

In the event your YubiKey (and backup YubiKey) are lost, to re-import

$ cd $(mktemp -d)
$ chmod 700 .
$ export GNUPGHOME=`pwd`
$ export GPG_TTY=$(tty)
$ wget https://cadizm.com/files/cadizm-pgp-public.key.txt
$ wget https://raw.githubusercontent.com/cadizm/dotfiles/master/gnupg/gpg.conf
$ wget https://raw.githubusercontent.com/cadizm/dotfiles/master/gnupg/gpg-agent.conf
$ pkill gpg-agent
$ gpg --list-keys
$ gpg --import < cadizm-pgp-public.key.txt
# save master and sub-keys to master-sub.key
$ gpg --import < master-sub.key
$ gpg --list-keys

You should then revoke and regenerate your keys.

Send More Money

Thu Sep 14 16:21:05 2017

How can we get MONEY?

  SEND
+ MORE
------
 MONEY

When in doubt, use brute force:

from itertools import permutations

corpus = list(set('SENDMOREMONEY'))

def f(D):
    def g(word):
        return int(''.join(([str(D[c]) for c in word])))
    return g('SEND') + g('MORE') == g('MONEY')


def pretty_print(D):
    print """
  SEND    {S}{E}{N}{D}
+ MORE  + {M}{O}{R}{E}
------  ------
 MONEY   {M}{O}{N}{E}{Y}
""".format(**D)


for perm in permutations(xrange(0, 10), len(corpus)):
    if f(dict(zip(corpus, perm))):
        pretty_print(dict(zip(corpus, perm)))

Map lookup time

Fri Aug 11 16:44:06 2017

Very surprised with the benchmark results of the 2 following parity implementations:

func Uint64(n uint64) int {
    parity := 0
    for i := uint16(0); i < 4; i++ {
        word := uint16(n >> (16 * i))
        parity ^= lookup(word)
    }

    return parity
}

func parity64(n uint64) int {
    var parity uint64 = 0
    for n > 0 {
        parity ^= 1
        n &= (n - 1) // clear lowest set bit trick
    }
    return int(parity)
}

I would have expected to Uint64 to outperform parity64 since it's "just" a whole bunch of map lookup and xor's. But after initial benching and digging in to see where time was spent, apparently map lookups are not really constant time in practice.

$ go test -bench .
BenchmarkParity64-8             2000000000               0.04 ns/op
BenchmarkUint64NoSetup-8        2000000000               0.17 ns/op
BenchmarkUint64WithSetup-8      2000000000               0.17 ns/op
PASS
ok      github.com/cadizm/epi/5.1-compute-parity        10.746s

For reference, here's a link to the source.

jq to the rescue

Mon Jul 31 16:18:08 2017

If you've ever pulled your hair attempting to parse JSON using awk/grep/sed, do your hairline a favor and install jq.

The docs are very good, but to give a non-trivial concrete example, here's processing JSON output from a Jenkins API:

function poll_jenkins {
    url="$JENKINS/job/foo/api/json"
    count=0
    while [ $count -lt $WAIT_COUNT ]; do
        let count=count+1
        echo -n "."
        sleep 1
        response=$(curl -q -S -X GET $url 2>/dev/null)
        if [ $(echo $response | jq ".inQueue") = "true" ]; then
            continue
        fi
        last_successful_build=$(echo $response | jq ".lastSuccessfulBuild.number")
        last_build=$(echo $response | jq ".lastBuild.number")
        if [ "$last_successful_build" = "$last_build" ]; then
            LAST_BUILD=$last_build
            return
        fi
    done
}

Retrieving the offer_id from a list of offers:

$ cat offers-2017-07-31.json | jq '[.offers[].offer_id]' | less

Circular Right Rotate

Wed Jul 26 17:58:06 2017

def rotate_right(L, k):
    """
    Circular right rotation of L, k times
    """
    M = L[:]
    for i, _ in enumerate(L):
        M[(i + k) % len(L)] = L[i]
    return M

RSpec gotcha (err me)

Mon May 8 10:49:09 2017

Spent a good half hour trying to figure out why the following spec was failing:

describe '#create' do
  it 'receives handle_event callback' do
    params[:foo] = 'bar'
    post :create, params: params
    expect(Foo::Bar).to receive(:new)
  end
end

After coming back to it the next day with a clearer head (and more patient googling), I realized that the expectation is that message will be received in the future. Doh!

So this should be:

describe '#create' do
  it 'receives handle_event callback' do
    expect(Foo::Bar).to receive(:new)
    params[:foo] = 'bar'
    post :create, params: params
  end
end

mount bigger /dev/shm

Fri Apr 7 13:50:35 2017

While working on a project that fires up a whole bunch of headless Google Chrome tabs using Selenium Python, I noticed that my program would crash all the time due to a "tab crash" error.

At first I thought it was just a difference between Ubuntu and OS X since it seemed to work fine on my laptop. But after a little googling I came across a docker thread which seemed to be pretty similar to what I was experiencing.

Apparently the default mount size for /dev/shm may not be large enough if Chrome has alot of tabs open (you check how many using $ lsof /dev/shm). To increase the size:

$ sudo umount /dev/shm
$ sudo mount -t tmpfs -o rw,nosuid,nodev,noexec,relatime,size=512M tmpfs /dev/shm

Symmetric Key Encryption with XOR Reciprocal Cipher

Fri Mar 10 17:08:01 2017

For very basic (and weak) encryption (of non-sensitive data) using a shared secret, one might want to consider using an XOR Cipher due to ease of implementation.

Here's 3 implementations I needed for distribution to different code bases:

# cipher.py

def xor(s, t):
    return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(s, t))

def pad(s, char=' ', padlen=16):
    n = len(s)
    if n < padlen:
        s += char * (padlen - n)
    return s

def encrypt(key, text):
    from binascii import hexlify
    return hexlify(xor(key, pad(text)))

def decrypt(key, cipher_text):
    from binascii import unhexlify
    return xor(key, unhexlify(cipher_text)).strip()

if __name__ == '__main__':
    key = 'I|tF&T=RMYmtU|80~N`"16v~&V>D"J|['
    msg = '101237'

    cipher_text = encrypt(key, msg)
    decrypted_text = decrypt(key, cipher_text)

    assert decrypted_text == msg
    print cipher_text, decrypted_text

# cipher.rb

def xor(s, t)
  s, t = t, s if s.size > t.size
  s.chars.zip(t.chars).map { |a, b| (a.ord ^ b.ord).chr }.join
end

def pad(s, char=' ', padlen=16)
  n = s.size
  s = n < padlen ? s + char * (padlen - n) : s
end

def encrypt(key, text)
  xor(key, pad(text)).unpack("H*").join
end

def decrypt(key, cipher_text)
  xor(key, [cipher_text].pack("H*")).strip
end

if $0 == __FILE__
  key = 'I|tF&T=RMYmtU|80~N`"16v~&V>D"J|['
  msg = '101237'

  cipher_text = encrypt(key, msg)
  decrypted_text = decrypt(key, cipher_text)

  raise if decrypted_text != msg
  puts "#{cipher_text} #{decrypted_text}"
end

// Cipher.java

class Cipher {
    private String key;

    public Cipher(String key) {
        this.key = key;
    }

    public String encrypt(String text) {
        return hexlify(xor(this.key, pad(text, ' ', 16)));
    }

    public String decrypt(String cipherText) {
        return xor(this.key, unhexlify(cipherText)).trim();
    }

    private static String xor(String s, String t) {
        int n = s.length() < t.length() ? s.length() : t.length();

        StringBuffer sb = new StringBuffer();

        for (int i = 0; i < n; ++i) {
            int a = (int)s.charAt(i);
            int b = (int)t.charAt(i);

            sb.append((char)(a ^ b));
        }

        return sb.toString();
    }

    private static String pad(String s, char c, int padlen) {
        int n = s.length();

        if (n < padlen) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < padlen - n; ++i) {
                sb.append(c);
            }
            s += sb.toString();
        }

        return s;
    }

    private static String hexlify(String s) {
        String hex = "";
        for (byte b : s.getBytes()) {
            hex += String.format("%02x", b);
        }
        return hex;
    }

    private static String unhexlify(String s) {
        StringBuffer sb = new StringBuffer();

        for (int i = 0; i < s.length(); i += 2) {
            String hex = s.substring(i, i + 2);
            sb.append((char)Integer.parseInt(hex, 16));
        }

        return sb.toString();
    }

    public static void main(String[] args)
        throws Exception
    {
        Cipher cipher = new Cipher("I|tF&T=RMYmtU|80~N`\"16v~&V>D\"J|[");
        String msg = "101237";

        String cipherText = cipher.encrypt(msg);
        String decryptedText = cipher.decrypt(cipherText);

        if (!decryptedText.equals(msg)) {
            throw new Exception();
        }

        System.out.printf("%s %s\n", cipherText, decryptedText);
    }
}

Euclid's algorithm

Sat Feb 18 18:29:03 2017

Since I always forget

// euclid.go

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

func lcm(a, b int) int {
    return (a * b) / gcd(a, b)
}

getting ssl certs

Wed Feb 8 13:20:52 2017

I've known about

$ openssl s_client -connect github.com:443 -showcerts > github.com.crt

for a while, but was always annoyed about having to wait for the connection to timeout and close. Found a cool workaround here:

$ echo | openssl s_client -connect github.com:443 2>&1 | sed --quiet '/-BEGIN CERTIFICATE-/,/-END CERTIFICATE-/p' > github.com.crt

Note: the long form --quiet option infers gnu sed; if you're on os x, you can

$ brew install --with-default-names gnu-sed

sqlite dump to csv

Mon Feb 6 14:05:46 2017

Since I always forget...

$ sqlite3 postal_codes.db
SQLite version 3.8.5 2014-08-15 22:37:57
Enter ".help" for usage hints.
sqlite> .mode csv
sqlite> .output foo.csv
sqlite> .dump postal_codes
sqlite> ^D

Hash comprehension?

Tue Jan 3 17:42:41 2017

The closest I've found to a ruby equivalent for python's dict comprehension.

# python

from pprint import pprint
import string

pprint({i: string.lowercase[i] for i in range(len(string.lowercase))})

# ruby

require 'pp'

lowercase = ('a'..'z').map { |v| v }
pp Hash[lowercase.each_with_index.map { |v, i|  [i, v] }]

custom pry commands

Fri Dec 2 13:42:28 2016

In a previous post I described how I added some aliases to my .pdbrc to dump local vars to a file.

Now that I'm diving deeper into the ecosystem, I wanted to find out how to do the equivalent in ruby and rails. After some quick googling, I came up with the following roughly roughly equivalent snippet (and analagously can go into .pryrc):

Pry::Commands.block_command "dl", "Dump locals to log" do
  vars = target.local_variables.select { |v| !v.to_s.starts_with?('_') }
  foo = Hash[vars.map { |k| [k, target.local_variable_get(k)] }].to_json
  File.open('/tmp/foo.json', 'w') { |f| f.write(foo) }
  output.puts "Dumped locals to \"/tmp/foo.json\""
end

For reference: git commit

ImageMagick identify

Mon Nov 7 17:26:31 2016

To get the "format and characteristics" of one or more images, ImageMagick to the rescue:

$ find . -type f -iname '*.jpg' | xargs identify

date manip

Thu Oct 6 14:17:08 2016

A couple of commands that might be useful for date manipulation:

Change filename's modification date to today at 6 am

$ touch -d "`date "+%D"` 06:00:00" filename

If you install faketime,

Run script as if it were 10 am now

$ faketime "`date "+%D"` 10:00:00" script

Docker snippets

Thu Sep 22 14:39:43 2016

Notes on using Docker Toolbox (not Docker for Mac, since I want to provision Docker hosts on remote machines).

# create a new machine
$ docker-machine create --driver virtualbox shiny-new-machine
$ docker-machine ls
$ eval $(docker-machine env shiny-new-machine)
$ docker-machine ip shiny-new-machine

# run a container
$ docker run -p  8001:80 nginx
$ docker ps
$ curl $(docker-machine ip shiny-new-machine)

# start up a bunch of containers
$ docker-compose -f dev.yml up

# run command in existing container
$ docker exec foo_container python manage.py migrate

elasticsearch bulk api

Tue Jun 21 14:12:16 2016

Snippets for creating an elasticsearch index using its bulk api (and python wrapper).

def bulk_index(infile_csv, index_name):
    from elasticsearch.helpers import bulk

    _create_index(index_name)

    print 'Bulk indexing %s...' % infile_csv,
    sys.stdout.flush()
    bulk(client=_es, actions=_actions(infile_csv, index_name))
    print 'Done'
    pprint(_es.count(index=index_name))


def _create_index(name):
    global _es

    body = {
        'mappings': {
            'teaser': {
                'properties': {
                    'foo': { 'type': 'integer' },
                    'bar': { 'type': 'float' },
                    # defaults to string if not specified
                    'baz': { 'type': 'string' },
                }
            }
        }
    }

    if not _es.indices.exists(name):
        print "Creating index: %s" % name
        _es.indices.create(name, body=body)
    else:
        print "Index: %s already exists" % name


def _actions(infile_csv, index_name):
    """
    Return generator of actions for elasticsearch bulk indexing
    """
    with open(infile_csv) as csv_file:
        reader = csv.DictReader(csv_file)
        for row in reader:
            row.update(
                _index=index_name,
                _type='teaser',
                _op_type='index',
                )
            mapping = {
                'foo': int,
                'bar': float,
            }
            yield {k: mapping[k](v) if k in mapping else v for k,v in row.items()}

Fibonacci Fun Time

Mon May 30 14:31:25 2016

I signed up for Coursera's Algorithmic Toolbox for fun and to dust the cobwebs on some CS FUNdamentals.

The first programming assignment involved a number of different variations on calculating Fibonacci numbers. And although they provided a more efficient solution than the naive recursive implementation, I wanted do some googling and see if there were any other faster implementations.

I came upon Nayuki's fast doubling implementation and wanted to do a quick and dirty benchmark against more common algorithms. Here it is!

## Decorator functions

from functools import wraps

def memoize(func):
    table = {}

    @wraps(func)
    def wrapper(*args):
        if args not in table:
            table[args] = func(*args)

        return table[args]

    return wrapper


def callrange(func):
    @wraps(func)
    def wrapper(n):
        for i in range(n):
            func(i)

        return func(n)

    return wrapper

## Fibonacci functions

def recursive_fibonacci(n):
    if n in (0, 1):
        return n

    return recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2)


@callrange
@memoize
def memoized_fibonacci(n):
    if n in (0, 1):
        return n

    return memoized_fibonacci(n - 1) + memoized_fibonacci(n - 2)


def list_fibonacci(n):
    L = [i for i in range(n + 1)]

    for i in range(2, len(L)):
        L[i] = L[i - 1] + L[i - 2]

    return L[n]


def sum_fibonacci(n):
    if n in (0, 1):
        return n

    i = 2
    j, k = 0, 1

    while i < n + 1:
        j, k = k, j + k
        i += 1

    return k


def fast_doubling_fibonacci(n):
    """
    Fast doubling Fibonacci algorithm

    Copyright (c) 2015 Project Nayuki
    All rights reserved. Contact Nayuki for licensing.
    https://www.nayuki.io/page/fast-fibonacci-algorithms
    """
    def _fib(n):
        if n == 0:
            return (0, 1)
        else:
            a, b = _fib(n // 2)
            c = a * (b * 2 - a)
            d = a * a + b * b
            if n % 2 == 0:
                return (c, d)
            else:
                return (d, c + d)

    return _fib(n)[0]


def test(f):
    solutions = [int(n) for n in open('fibonacci.txt')]

    for i in range(len(solutions)):
        assert f(i) == solutions[i]


def time(f, n):
    import time

    start = time.time()
    f(n)
    end = time.time()

    print "%24s: %12f" % (f.func_name, end - start)  # 1 sec lsb


if __name__ == '__main__':
    F = [
        memoized_fibonacci,
        list_fibonacci,
        sum_fibonacci,
        fast_doubling_fibonacci,
    ]

    for f in F:
        test(f)
        time(f, 10000)

$ python fibonacci.py
      memoized_fibonacci:    22.862408
          list_fibonacci:     0.005365
           sum_fibonacci:     0.002401
 fast_doubling_fibonacci:     0.000047

require 'pry'; binding.pry

Thu Apr 21 13:53:49 2016

Coming from the python world, I'm used to stepping into code by throwing import ipdb; ipdb.set_trace() in my source when I want to debug something.

Note to self: the pry gem seems to be similar in ruby where you can do

require 'pry'; binding.pry

ffmpeg time lapse

Fri Apr 8 17:37:09 2016

Note to self: after some googling and playing around with options, use the following to create time lapses with ffmpeg:

$ ffmpeg -framerate 30 -i '%*.JPG' -q:v 2 -r 30 -pix_fmt yuv420p timelapse.mp4

rlwrap ftw

Mon Feb 29 12:37:11 2016

rlwrap is super nifty. I recently found a need for it when playing around in the ocaml repl:

l00k:~$ ocaml
        OCaml version 4.02.3

# 1 + 2 * 3^A^E^CInterrupted.
# ^D
l00k:~$ rlwrap ocaml
        OCaml version 4.02.3

# 1 + 2 * 3
  ;;
- : int = 7
# ^D
l00k:~$

NGINX proxy_pass to GitHub Pages

Thu Feb 25 11:53:34 2016

I have a digital ocean droplet that I use for my personal website and also as a playground for side projects.

It's been working out well, but after recently migrating this blog to netlify, I decided to host the landing page for my site on GitHub Pages since its content is extremely simple (and static sites are the new hotness).

While GitHub Pages already provides a subdomain (mine is cadizm.github.io) I wanted to preserve my sweet domain name.

I'm running NGINX and decided to proxy to GitHub Pages since it seems to do pretty much what I want to do. One small caveat is that assets need to be qualified using a full url instead of being specified relatively.

Just in case anyone is trying to do the same, here's a snippet of the relevant NGINX config:

    location / {
        proxy_pass https://cadizm.github.io;
        proxy_set_header Host cadizm.github.io;
        proxy_set_header X-Real-IP $remote_addr;
        proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
    }

git gui blame

Wed Feb 17 12:37:09 2016

Though I've been using gitk for years, I've never really found a use for git gui.

One cool git gui command I've recently found useful is git gui blame. With it when you right-click a line you get a few options, two of which are particularly handy: "Show History Context" and "Blame Parent Commit".

Blame Parent Commit is especially practical in that you can recursively blame each successive revision.

xargs with files with spaces

Thu Feb 4 17:52:17 2016

Oldie, but goodie that I had to review manpage because I forgot the flag:

$ find . -type f -iname '*.foo' -print0 | xargs -0 rm -f

screen in screen in screen...

Fri Jan 22 12:16:15 2016

Recently ran into an issue where I was running a screen session in an existing screen.

My usual workflow is to start a new screen session each day using a custom screen startup script (since I have some env vars I'd like to renew each day).

I had to then ssh into a remote machine and run a daemonized job in screen that wrote some output I needed to revisit.

The problem arose in that when I tried to detach from the inner screen, I ended detaching from the original screen I had started on my local machine. After some quick googling, I found this.

Since the inner screen was started on a remote machine that didn't have my .screenrc, the global escape option was still the default ctrl-a, and I didn't need to go through the usual hoops when detaching from the inner screen.

Reference for myself:

local$ screen-start  # start screen session
local$ screen -x  # attach to screen
local$ ssh remote  # in orig screen
remote$ screen -dmS 'foo.sh' foo.sh  # start/attach new daemonized screen
remote$ ^ad  # detach from inner screen
remote$ ^d  # logout from remote machine
local$  # back to local machine in orig screen

Can also do:

$ screen -d -D

Debugging Octave/Matlab

Mon Dec 21 18:16:45 2015

Small note to self: favor keyboard over dbstop in Octave (not sure about Matlab).

During cursory exploration, locals don't seem to be in scope using dbstop.

pdb aliases are your friend

Fri Nov 13 15:17:41 2015

Pretty much every time I drop into ipdb, I end up inspecting locals to see what's going on. Very often I assign what I'm inspecting to a local var foo and then either manipulate it and/or write its contents to disk.

It can become annoying to have to keep writing from pprint import.... and as a result I've found these .pdbrc aliases really helpful.

from pprint import pformat, pprint
_L = locals()
alias pl pprint(_L);
alias dl with open('/tmp/locals.txt', 'w') as f: f.write(pformat(_L))

moreutils::sponge

Thu Nov 5 19:21:53 2015

Just discovered moreutils after searching for "cat file sort and write to same file".

StackExchange told me that sort actually has an option to pseudo edit files "in-place" with the -o, --output options. But one of the more intersting (pun intended) google results described sponge found in moreutils.

Where you can do nifty things like:

$ sort conquest_eligible.txt | sponge conquest_eligible.txt

nvm error: Checksums do not match

Wed Oct 7 15:40:27 2015

If you get a Checksums do not match error while trying to do an nvm install on OS X, do a brew install md5sha1sum.

nvm.sh has the following conditionals in nvm_checksum and sha1 on OS X doesn't accept the -q option.

nvm_checksum() {
  local NVM_CHECKSUM
  if nvm_has "sha1sum" && ! nvm_is_alias "sha1sum"; then
    NVM_CHECKSUM="$(command sha1sum "$1" | command awk '{print $1}')"
  elif nvm_has "sha1" && ! nvm_is_alias "sha1"; then
    NVM_CHECKSUM="$(command sha1 -q "$1")"
  elif nvm_has "shasum" && ! nvm_is_alias "shasum"; then
    NVM_CHECKSUM="$(shasum "$1" | command awk '{print $1}')"
  else
    echo "Unaliased sha1sum, sha1, or shasum not found." >&2
    return 2
  fi

  if [ "_$NVM_CHECKSUM" = "_$2" ]; then
    return
  elif [ -z "$2" ]; then
    echo 'Checksums empty' #missing in raspberry pi binary
    return
  else
    echo 'Checksums do not match.' >&2
    return 1
  fi
}

GPG snippets

Fri Aug 21 19:05:11 2015

Notes to self re: GPG

If brew installs GPG to gpg2, consider symlinking to gpg.

Generate a key

$ gpg --gen-key

Sign and encrypt

$ gpg --armor --sign --encrypt --recipient='foo@bar.com' --output=baz.gpg baz

Decrypt

$ gpg --decrypt baz.gpg

List/export keys

$ gpg --list-keys
$ gpg --armor --output my-public.key --export 'foo@bar.com'
$ gpg --armor --output my-private.key --export-secret-key 'foo@bar.com'

No more sslwrap

Sat Jul 11 19:13:58 2015

If you find that your version of Python no longer has sslwrap and 3rd party library requires it (i.e. gevent), here's a post describing a workaround which worked for me.

It basically boils down to defining and setting the following:

import inspect
__ssl__ = __import__('ssl')

try:
    _ssl = __ssl__._ssl
except AttributeError:
    _ssl = __ssl__._ssl2


def new_sslwrap(sock, server_side=False, keyfile=None, certfile=None, cert_reqs=__ssl__.CERT_NONE, ssl_version=__ssl__.PROTOCOL_SSLv23, ca_certs=None, ciphers=None):
    context = __ssl__.SSLContext(ssl_version)
    context.verify_mode = cert_reqs or __ssl__.CERT_NONE
    if ca_certs:
        context.load_verify_locations(ca_certs)
    if certfile:
        context.load_cert_chain(certfile, keyfile)
    if ciphers:
        context.set_ciphers(ciphers)

    caller_self = inspect.currentframe().f_back.f_locals['self']
    return context._wrap_socket(sock, server_side=server_side, ssl_sock=caller_self)

if not hasattr(_ssl, 'sslwrap'):
    _ssl.sslwrap = new_sslwrap

Git flow bullets/checklist

Mon Jun 8 14:02:19 2015

We use Git flow at work. While the branching strategy makes alot of sense and is easy to follow, it can be easy to forget some steps when executing branch tasks.

Here's sort of a bulleted checklist I use to make sure for the most part I'm adhering to the spirit of the model. It's derived mostly from an Atlassian post describing the workflow.

Git flow branches

master

master stores official release history
tag each commit on master with version/release number
hotfix branches cut from master

develop

develop used to integrate feature branches
feature branches branch from develop
feature branches merged back into develop

release branches

release/xxx branches branch from develop
only release-related tasks (bug fixes, documentation) allowed into release branch after it is cut
once release branch is ready, it is merged into master (which is then tagged with version/release number)
release branch also merged back into develop

hotfix branches

only hotfix/xxx branches may branch from master
once hotfix complete, merge branch into both master and develop
master once again tagged (since each commit to master is tagged)

Markdownify'ing webpages

Sat Jun 6 23:17:33 2015

I needed to convert some webpages to a human-readable format for studing/review at a later time. After some thought I came up with the following:

download pages via curl/wget or good old "save page as"
slugify filenames for easier shell manipulation
convert to markdown using Aaron Swartz's html2text
rename file extensions to reflect new format

# delete directories (handling spaces in filenames)
$ find . -type d -print0 | xargs -0 rm -rf

# slugify, rename, then delete html files
$ ls | xargs -0 | slugify && \
for file in $(ls ); do
    html2text $file > ${file%.html}.md;
done && \
rm *.html

brute force arithmetic

Fri May 22 12:28:08 2015

Came across this puzzle today. Instead of trying to do some fancy multivariate analysis, here's a brute force solution.

"""
Solve the `nam puzzle' using brute force.

See http://goo.gl/8b0ri6 for full problem description.
"""


def main():
    from itertools import permutations
    for p in permutations(range(1, 10)):
        a, b, c, d, e, f, g, h, i = p
        if a + ((13 * b) / c) + d + (12 * e) \
                - f - 11 + ((g * h) / i) - 10 == 66:
            print ':) => {}'.format(p)
            break
    else:
        print ':('


if __name__ == '__main__':
    import sys
    sys.exit(main())

l00k:~/ws/20150522$ python nam_puzzle.py
:) => (1, 2, 3, 4, 6, 5, 7, 9, 8)

host dns lookup

Fri May 15 15:50:48 2015

Why have I not been using this instead of dig?

l00k:~/workspace/src/blog.mcadiz.com (master) $ host google.com
google.com has address 216.58.216.14
google.com has IPv6 address 2607:f8b0:4007:809::200e
google.com mail is handled by 20 alt1.aspmx.l.google.com.
google.com mail is handled by 10 aspmx.l.google.com.
google.com mail is handled by 30 alt2.aspmx.l.google.com.
google.com mail is handled by 50 alt4.aspmx.l.google.com.
google.com mail is handled by 40 alt3.aspmx.l.google.com.

l00k:~/workspace/src/blog.mcadiz.com (master) $ host mcadiz.com
mcadiz.com has address 192.241.207.230
mcadiz.com mail is handled by 20 mx2.zohomail.com.
mcadiz.com mail is handled by 10 mx.zohomail.com.

Though with the verbose flag turned on, it's pretty much dig:

l00k:~/workspace/src/blog.mcadiz.com (master) $ host -d mcadiz.com
Trying "mcadiz.com"
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 25273
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 0

;; QUESTION SECTION:
;mcadiz.com.                    IN      A

;; ANSWER SECTION:
mcadiz.com.             1550    IN      A       192.241.207.230

Received 44 bytes from 10.18.6.11#53 in 24 ms
Trying "mcadiz.com"
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 64794
;; flags: qr rd ra; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 0

;; QUESTION SECTION:
;mcadiz.com.                    IN      AAAA

;; AUTHORITY SECTION:
mcadiz.com.             1543    IN      SOA     ns1.digitalocean.com. hostmaster.mcadiz.com. 1427872864 10800 3600 604800 1800

Received 92 bytes from 10.18.6.11#53 in 1 ms
Trying "mcadiz.com"
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 24704
;; flags: qr rd ra; QUERY: 1, ANSWER: 2, AUTHORITY: 0, ADDITIONAL: 0

;; QUESTION SECTION:
;mcadiz.com.                    IN      MX

;; ANSWER SECTION:
mcadiz.com.             1551    IN      MX      20 mx2.zohomail.com.
mcadiz.com.             1551    IN      MX      10 mx.zohomail.com.

Received 76 bytes from 10.18.6.11#53 in 1 ms

E141: No file name for buffer

Thu Apr 2 14:09:13 2015

If you encounter the vim error messager E141: No file name for buffer and you're not aware of the different buftype's, you can learn more here.

But if you don't care and just want this error to go away, SO to the rescue

:setlocal buftype=nofile
:setl bt=nofile

netlify'ing :)

Tue Mar 31 23:58:12 2015

I came across Netlify today on Hacker News and am trying it out. This is the first trial post set up to use their continuous deployment feature. I'll do a more thorough follow-up post once I have some time to read through their docs a bit more.

Instagram python api Enforce Signed Header

Sat Feb 7 15:34:28 2015

If you have selected Enforce signed header for your Instagram client, you need to make sure to set the X-Insta-Forwarded-For header as described in the developer docs.

I'm using the python-instagram library provided by Instagram itself and couldn't figure out how to set this header. If you know how to do this, please let me know!

The diff below augments python-instagram's OAuth2API class and computes and stuffs the X-Insta-Forwarded-For header arbitrarily on each request. Note that the value is the client ip address concatenated with an HMAC calculated using SHA256 hash function and the client secret as the key and the client ip address as the message.

l0st:~/workspace/src/python-instagram.git (master) $ git df
diff --git a/instagram/oauth2.py b/instagram/oauth2.py
index 56dbd23..7ab0cbd 100644
--- a/instagram/oauth2.py
+++ b/instagram/oauth2.py
@@ -1,3 +1,6 @@
+import hashlib, hmac
+import socket
+
 from .json_import import simplejson
 from six.moves.urllib.parse import urlencode
 from httplib2 import Http
@@ -209,6 +212,14 @@ class OAuth2Request(object):
         headers = headers or {}
         if not 'User-Agent' in headers:
             headers.update({"User-Agent": "%s Python Client" % self.api.api_name})
+        if not 'X-Insta-Forwarded-For' in headers:
+            key = 'put-client-secret-key-here'
+            h = hmac.new(key, digestmod=hashlib.sha256)
+            ipaddr = socket.gethostbyname(socket.gethostname())
+            h.update(ipaddr)
+            v = '{}|{}'.format(ipaddr, h.hexdigest())
+            print v
+            headers.update({"X-Insta-Forwarded-For": v})
         # https://github.com/jcgregorio/httplib2/issues/173
         # bug in httplib2 w/ Python 3 and disable_ssl_certificate_validation=True
         http_obj = Http() if six.PY3 else Http(disable_ssl_certificate_validation=True)

CPython vs C Performance

Mon Dec 22 14:58:49 2014

I've been doing some HackerRank challenges for fun lately. Their platform has support for pretty much every language under the sun, so users are free to use what they're most comfortable with.

Python's been my language of choice for the problem sets since they're not too complicated (at least the warmups) and the solutions typically require only coding up a quick function or two.

Submissions have time/memory limitations based on language, which obviously makes sense since performance will vary depending upon language. But I never really gave language much weight and concentrated on making sure my algorithm had good to decent Big O computational run time complexity (where good to decent means polynomial times of O(n²) or O(n³) or less).

But after spending a bit of time on a particular problem whose straightforward solution had a cubic running time and consistently went over HackerRank's 10 second time limit (for python programs), I decided to poke around the discussion boards and see if I could find out what I was doing wrong and how others were approaching the problem.

To my surprise one of the moderators commented that another poster's C++ solution was `correct' and simply required 3 nested loops over the input; pretty much exactly what I was doing, except in a different language.

I was a bit surprised, and so I translated my python solution to vanilla C and low and behold run times went from ~16 sec to under 1 sec. I'll now concede that language choice does in fact matter for `hot' pieces of code or systems requiring realtime or near-realtime performance. In such cases it probably makes sense to optimize and/or rewrite critical pieces in a more close-to-the metal language like assembly, C, or C++.

But obviously correctness trumps all and gathering data/metrics via profiling and instrumentation should be done first to see which parts may benefit most from an optimized rewrite.

For reference the programs and their associated running times are below. And here is the problem description and one of the sample inputs.

$ time cat input/acm_icpc_team.txt | python acm_icpc_team-v1.py
467
1

real    0m16.264s
user    0m16.176s
sys     0m0.045s

$ time cat input/acm_icpc_team.txt | python acm_icpc_team-v2.py
467
1

real    0m16.954s
user    0m16.874s
sys     0m0.045s

$ time cat input/acm_icpc_team.txt | ./acm_icpc_team
467
1

real    0m0.465s
user    0m0.461s
sys     0m0.005s

# acm_icpc_team-v1.py

import sys

if __name__ == '__main__':
    line = sys.stdin.readline()
    N, M = [int(n) for n in line.split()]
    buf = [line.strip() for line in sys.stdin]

    max_ = 0
    count = 0

    for i in range(N-1):
        for j in range(i+1, N):
            bits = 0
            for k in range(M):
                if buf[i][k] == '1' or buf[j][k] == '1':
                    bits += 1
            if bits == max_:
                count += 1
            elif bits > max_:
                max_ = bits
                count = 1

    print "{0}\n{1}".format(max_, count)

# acm_icpc_team-v2.py

import sys

if __name__ == '__main__':
    line = sys.stdin.readline()
    N, M = [int(n) for n in line.split()]
    buf = [line.strip() for line in sys.stdin]

    max_ = 0
    count = 0

    for i in range(N-1):
        for j in range(i+1, N):
            v = int(buf[i], base=2) | int(buf[j], base=2)
            bits = 0
            while v:
                v &= (v-1)  # clear the least significant bit set
                bits += 1
            if bits == max_:
                count += 1
            elif bits > max_:
                max_ = bits
                count = 1

    print "{0}\n{1}".format(max_, count)

/* acm_icpc_team.c */

#include <stdio.h>

int main(int argc, char** argv)
{
    int N, M;
    scanf("%d %d\n", &N, &M);

    char buf[500][500];
    for (int i = 0; i < N; ++i) {
        scanf("%500s\n", buf[i]);
    }

    int max = 0;
    int count = 0;

    for (int i = 0; i < N-1; ++i) {
        for (int j = i+1; j < N; ++j) {
            int bits = 0;
            for (int k = 0; k < M; ++k) {
                if (buf[i][k] == '1' || buf[j][k] == '1') {
                    bits += 1;
                }
            }
            if (bits == max) {
                count += 1;
            }
            else if (bits > max) {
                max = bits;
                count = 1;
            }
        }
    }

    printf("%d\n%d\n", max, count);

    return 0;
}

Nibble to binary string

Fri Nov 7 15:11:00 2014

I needed to demonstrate converting decimal nibbles to binary and used this:

for i in range(0, 16):
    binary = '{:04d}'.format(int(bin(i)[2:]))

In retrospect, I probably should have taken the time to write a function:

def binary(nibble):
    "Return 0-padded binary string of nibble"
    if nibble < 0 or nibble > 15:
        raise Exception('Invalid input: {0}'.format(nibble))
    bits = []
    for _ in range(4):
        bits.insert(0, str(nibble & 0x1))
        nibble >>= 1
    return ''.join(bits)

Python Package to RPM

Thu Oct 23 18:10:34 2014

Sometimes you need to convert your Python package into an RPM (perhaps for political reasons). If you are using distutils/setuptools, then this is very easy after a bit of setup.

The exapmle that follows assumes a CentOS 6 box, but should work on any Fedora-like distro.

Enable EPEL

$ wget http://download.fedoraproject.org/pub/epel/6/x86_64/epel-release-6-8.noarch.rpm
$ sudo rpm -ivh epel-release-6-8.noarch.rpm

Install dependencies

$ sudo yum groupinstall -y 'Development Tools'
$ sudo yum install -y fedora-packager git python-pip

Setup RPM build envirionment

$ sudo usermod -a -G mock <foo user>
$ rpmdev-setuptree

Create spec, build source tarball

$ python setup.py bdist_rpm --requires='mysql-connector-python,python-pip'

Modify spec as needed

As mentioned in the docs, "there are many options in .spec files that don't have corresponding options in the setup script" so you may need to modify parts by hand. In my case, there's currently no RPM for sqlsoup, so I need to install it during the post step.

# foo.spec
%prep
%setup -n %{name}-%{unmangled_version} -n %{name}-%{unmangled_version}

%build
python setup.py build

%post
pip install sqlsoup

Build RPM

$ rpmbuild -ba ./foo.spec

Install RPM

Hopefully the rpmbuild command completed successfully and all that remains is to install the RPM.

$ sudo rpm -ivh foo-0.1.0-1.noarch.rpm

ssh force IdentityFile

Wed Oct 8 20:29:38 2014

If you're like me and you work with alot of machines or frequently spin up and teardown vagrant boxes, then your ssh config file (e.g. $HOME/.ssh/config) is littered with entries like:

Host 192.168.1.*
  IdentitiesOnly yes
  IdentityFile ~/.ssh/id_rsa-foo

Host 10.10.10.*
  User baz
  IdentitiesOnly yes
  IdentityFile ~/.ssh/id_rsa.bar

When the machine you'd like to ssh into falls within one of the config ip ranges, but you'd like to override the rsa key used:

$ ssh -vvv -o PubkeyAuthentication=no -o IdentitiesOnly=yes -o IdentityFile=~/.ssh/id_rsa.private foo@127.0.0.1

Memoization tests (py edition)

Tue Sep 23 18:28:05 2014

Script execution and abbreviated source below. Full source can be found here.

Note the huge gain after memoization, and that hand-rolled versions still offer small gains over a decorated version.

$ python factorial.py

Running Factorial
Testing correctness...
Success
Timing...
0.240013837814
Success

Running RecursiveFactorial
Testing correctness...
RuntimeError('maximum recursion depth exceeded in cmp',) at iteration 998
Timing...
RuntimeError('maximum recursion depth exceeded in cmp',) iteration 994
RuntimeError('maximum recursion depth exceeded in cmp',) iteration 994
0.569229125977
RuntimeError('maximum recursion depth exceeded in cmp',) at iteration 998

Running MemoizedRecursiveFactorial
Testing correctness...
Success
Timing...
0.000745058059692
Success

Running IterativeFactorial
Testing correctness...
Success
Timing...
0.307121992111
Success

Running MemoizedIterativeFactorial
Testing correctness...
Success
Timing...
0.000705003738403
Success

Timing <function time_test_decorated_recursive_factorial at 0x1004a4c08>
0.00292491912842

#
# Abridged source
#

class memoize(object):
    """Memoization decorator (@memoize).
    """

    def __init__(self, func):
        self.func = func
        self.memo = dict()

    def __call__(self, *args):
        try:
            return self.memo[args]
        except KeyError:
            self.memo[args] = self.func(*args)
            return self.memo[args]


@memoize
def decorated_recursive_factorial(n):
    if n < 0:
        return None
    if n in [0, 1]:
        return 1
    return n * decorated_recursive_factorial(n - 1)


class MemoizedRecursiveFactorial(Factorial):
    """Memoized recursive factorial implementation.
    """

    def __str__(self):
        return "MemoizedRecursiveFactorial"

    def factorial(self, n):
        if n < 0:
            return None
        if n in self.D:
            return self.D[n]
        if n in [0, 1]:
            return 1
        self.D[n] = n * self.factorial(n - 1)
        return self.D[n]


class MemoizedIterativeFactorial(Factorial):
    """Memoized iterative factorial implementation.
    """

    def __str__(self):
        return "MemoizedIterativeFactorial"

    def factorial(self, n):
        if n < 0:
            return None
        if n in self.D:
            return self.D[n]
        m, res = n, 1
        while m > 1:
            if (m - 1) in self.D:
                self.D[m] = self.D[m - 1] * m
                return self.D[m]
            else:
                res *= m
                self.D[m] = res
                m -= 1
        return res


if __name__ == '__main__':
    f = Factorial()
    r = RecursiveFactorial()
    mr = MemoizedRecursiveFactorial()
    i = IterativeFactorial()
    mi = MemoizedIterativeFactorial()

    for instance in [f, r, mr, i, mi]:
        print '\nRunning {0}'.format(instance)

        print 'Testing correctness...'
        if instance.test_correctness():
            print 'Success'

        print 'Timing...'
        print instance.time_test_factorial()

    print '\nTiming {0}'.format(repr(time_test_decorated_recursive_factorial))
    print time_test_decorated_recursive_factorial()

VirtualBox Bridged Network Adapter

Fri Aug 22 14:53:29 2014

To ssh into it a virtualbox vm, set up bridged networking:

Add a bridged adapter similar to this

Spin up your vm and look for the new interface. In my case the interface was not configured automatically:

$ ifconfig -a
eth2      Link encap:Ethernet  HWaddr 08:00:27:2D:73:70  
          BROADCAST MULTICAST  MTU:1500  Metric:1
          RX packets:0 errors:0 dropped:0 overruns:0 frame:0
          TX packets:0 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:1000 
          RX bytes:0 (0.0 b)  TX bytes:0 (0.0 b)
          Interrupt:16 Base address:0xd240

To set up via dhcp, kill any dhclient processes that may attached to the interface and then restart:
```
$ kill $(lsof -tc dhclient)
$ dhclient eth2
```

Assuing dhclient succeeded, you can now find out the ip address assigned:

$ifconfig -a
eth2      Link encap:Ethernet  HWaddr 08:00:27:2D:73:70  
          inet addr:10.10.11.163  Bcast:10.10.15.255  Mask:255.255.248.0
          inet6 addr: fe80::a00:27ff:fe2d:7370/64 Scope:Link
          UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1
          RX packets:34244 errors:15 dropped:0 overruns:0 frame:0
          TX packets:477 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:1000 
          RX bytes:2268686 (2.1 MiB)  TX bytes:60728 (59.3 KiB)
          Interrupt:16 Base address:0xd240

To have the interface configured at boot, in the vm:

$ cd /etc/sysconfig/network-scripts
$ cp ifcfg-eth0  ifcfg-eth2
$ sed -i 's/eth0/eth2/g' ifcfg-eth2

Back on the host OS, you can now:
```
$ ssh 10.10.11.163
```

Mac OS X NFS Client

Tue Aug 19 15:04:48 2014

Show what's mounted on 192.168.1.100 and mount on /nfs/foo

$ showmount -e 192.168.1.100
Exports list on 192.168.1.100:
/export/nfs                         192.168.1.101
$ sudo mount -t nfs 10.10.11.62:/export/nfs /nfs/foo

GTK Emacs Keybindings

Tue Aug 19 14:53:24 2014

Works on Ubuntu 12.04 LTS using Unity/xmonad.

Install gconf-editor and launch. This should create $HOME/.gtkrc-2.0 which has something like:

include "/home/me/.gtkrc.mine"

in which you can add:

gtk-key-theme-name = "Emacs"

Linux Caps Lock to Control

Thu Aug 7 14:00:50 2014

Download: http://goo.gl/pxhZdS

#!/bin/bash

if [[ $EUID -ne 0 ]]; then
    echo "This script must be run as root" 1>&2
    exit 1
fi

if [[ -z `which dumpkeys` ]]; then
    echo "dumpkeys not in PATH" 1>&2
    exit 1
fi

if [[ -z `which loadkeys ` ]]; then
    echo "loadkeys not in PATH" 1>&2
    exit 1
fi

dumpkeys | head -1 > /tmp/foo_keys
echo "keycode 58 = Control" >> /tmp/foo_keys
loadkeys /tmp/foo_keys

SD card dd unbuffered block size write speed

Mon Aug 4 00:00:00 2014

l0st:~/workspace/src/minibian/image$ sudo pv -pterb minibian-2013-10-13-fcs.img.copy | sudo dd of=/dev/rdisk1
75.12MiB 0:05:28 [237kiB/s]
    
l0st:~/workspace/src/minibian/image$ sudo pv -pterb minibian-2013-10-13-fcs.img.copy | sudo dd of=/dev/rdisk1 bs=8m
1.916GiB 0:03:48 [10.7MiB/s]

wtf -__-

CentOS(ish) Static IP

Wed Jul 23 15:00:42 2014

# /etc/resolv.conf
domain foo.bar.com
nameserver 10.10.10.12
nameserver 10.10.10.11

# /etc/sysconfig/network
NETWORKING=yes
HOSTNAME=pi
GATEWAY=10.10.10.1

# /etc/sysconfig/network-scripts/ifcfg-eth0 
DEVICE=eth0
#BOOTPROTO=dhcp
BOOTPROTO=static
HWADDR="aa:bb:cc:11:22:33"
IPADDR=10.10.11.215
NETMASK=255.255.248.0
ONBOOT=yes
GATEWAY=10.10.10.1

$ rm /etc/udev/rules.d/70-persistent-net.rules && reboot

Imaged OS mac address caching

Wed Jul 16 00:00:00 2014

udev caches network interface definitions by mac address. If you are using a cloned image with this (most likely) defined incorrectly, it's probably safe to just delete /etc/udev/rules.d/70-persistent-net.rules.

ssh disable public key authentication

Fri Jul 11 17:18:43 2014

If you have an ssh-agent running and perhaps alias ssh to ssh -A, you can disable agent forwarding and force password prompting with:

$ ssh -o 'PubkeyAuthentication=no' foo@127.0.0.1

or

$ SSH_AUTH_SOCK='' ssh foo@127.0.0.1

as described here.

Modify Raspberry Pi Image

Fri Jul 11 17:18:43 2014

Download your raspberry image of choice. In my case I needed the redsleeve distro.

$ fdisk -l raspi-v2-redsleeve-cli-0.3.img

Disk raspi-v2-redsleeve-cli-0.3.img: 1939 MB, 1939865600 bytes
255 heads, 63 sectors/track, 235 cylinders, total 3788800 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x00014d34

                         Device Boot      Start         End      Blocks   Id  System
raspi-v2-redsleeve-cli-0.3.img1            8192      122879       57344    c  W95 FAT32 (LBA)
raspi-v2-redsleeve-cli-0.3.img2          122880     3788799     1832960   83  Linux

We want to be able to mount/modify the second partition on /mnt. Run:

$ sudo kpartx -a raspi-v2-redsleeve-cli-0.3.img

which should add a loop device in /dev/mapper:

$ ls /dev/mapper
control  loop0p1@  loop0p2@  root@  swap1@

The second partition is now mapped to /dev/mapper/loop0p2. Mount:

$ sudo mount -o rw /dev/mapper/loop0p2 /mnt
$ cd /mnt
$ ls
bin/  boot/  dev/  etc/  home/  lib/  lost+found/  media/  mnt/  opt/  proc/  root/  sbin/  selinux/  srv/  sys/  tmp/  usr/  var/

We can now modify the disk image as we please. Remember to umount and kpartx -d when done.

$ sudo umount /mnt
$ sudo kpartx -d raspi-v2-redsleeve-cli-0.3.img
loop deleted : /dev/loop0

Refresh postfix

Tue Jul 1 18:51:11 2014

From Postfix README

Execute the command:

$ postmap /etc/postfix/virtual

after changing the virtual file, and execute the command:

$ postfix reload

after changing the main.cf file.

Install pip for the current user

Mon Jun 30 14:53:19 2014

$ wget https://bootstrap.pypa.io/get-pip.py
$ python get-pip.py --user

Link: get-pip.py

Apache mod_rewrite `serve backup' file

Tue Jun 10 13:41:44 2014

when we can't find a particular static file in its `usual' location, use its alternate.

RewriteEngine On
RewriteCond %{DOCUMENT_ROOT}%{REQUEST_URI} !-f
RewriteCond %{REQUEST_URI}  ^/foo/bar/baz(.*\.png)$
RewriteRule ^/foo/bar/baz/(.*)$  /nfs/foo/bar/baz/$1

Manage dotfiles with dotfiles-python

Thu May 15 22:12:22 2014

$ workon dotfiles
$ cd ~/workspace/src/dotfiles/
$ dotfiles -R . --list
$ dotfiles -R . --sync --dry-run

git grep with blame

Wed Apr 23 14:47:35 2014

sometimes we want grep and blame

add to git-blame on your PATH

#!/usr/bin/env python

import sys
from subprocess import call

if __name__ == '__main__':
    args = sys.argv[1:]
    assert len(sys.argv[1:]) % 2 == 0
    for (file_line, text) in zip(*[iter(args)] * 2):
        f, n = file_line.strip(':').split(':')
        call(['git', 'blame', '-L', '{0},{1}'.format(n, n), '--', f])

then

$ git grep -i 'error loading order details' | xargs git-blame
76d02b9z (Foo User 2014-03-14 21:05:53 1957)    $self->alert("Error loading order details");
76d02b9z (Foo User 2014-03-14 21:05:53 2053)    $self->alert("Error loading order details");

PostgreSQL Ident Authentication

Sun Apr 6 13:51:23 2014

assumes debian/ubuntu-ish linux flavor

install oidentd

$ sudo apt-get install oidentd

add to /etc/oidentd.conf

user foo_user {
    default {
        deny spoof
        deny spoof_all
        deny spoof_privport
        allow random
        allow random_numeric
        allow numeric
        deny hide
    }
}

add to /etc/postgresql/9.1/main/pg_hba.conf

# TYPE   DATABASE   USER   ADDRESS   METHOD
local    all        all              ident map=my_map

add to /etc/postgresql/9.1/main/pg_ident.conf

# MAPNAME   SYSTEM-USERNAME   PG-USERNAME
my_map      foo_user          pg_user

restart services

$ sudo service oidentd restart
$ sudo service postgresql restart

references