Tag Archives: python

Writing a Python Script to be Used in Vim

It is no secret that I love vim. I’ve written and helped maintain a variety of vim plugins, but I’ve mostly restricted my attention to direct use of vimscript or to call external tools and redirect their output to a vim buffer.

Only recently did I learn how easy it is to use python to interact directly with vim objects through the vim-python package. And it was so easy that this felt a bit like writing a quick shell script to facilitate some immediate task — it allows quick and dirty work.

In this note, I’ll review how I recently wrote a quick python function (to be used in vim) to facilitate conversion of python f-strings (which I love) to python 3.5 (which I also love, but which is admittedly a bit behind).

Of course the real reason is to remind future me just how easy this is.

Description of the Problem

In python 3.7+, one can use f-strings to format strings. This syntax looks like

x = 4
print(f"Python has at least {x} many ways to format strings now.")

I love them, they’re great. But they are not backportable since they are a change to fundamental syntax. Thus systems relying on previous versions of python (be it python2 or even python3.5) can’t parse python files containing f-strings.

The goal is this: given a line containing an f-string, write an equivalent line containing no f-string.

The formula I choose is simple: use .format() instead. Thus given

s = f"string with {some} {variables}"

we will convert this to

s = "string with {} {}".format(some, variables)

I will assume that the string takes place on one line for simplicity (and because in my application this was almost always true), but that there are any number of variables included in the line.

Background on python in vim

Some good insight is gained through reading :h python-vim. In fact, this is essentially the only documentation on the python-vim interface (though it is pretty good documentation — perhaps the actual best source of learning this interface is to read some plugins which leverage the python connection).

I will assume that vim has been compiled with python3 support (which can be checked by looking for +python3 in vim --version). Then the key idea is that one can use :py3 to call python functions. For example,

:py3 print("Hello")

Being restricted to one line is inconvenient, and it is far more useful to use the form

:py3 << EOF
def say_hello():
  print("Sup doc.")
EOF
:py3 say_hello()

In this way, we can define and use python functions. Right now, the output of these functions simply appears in the status lines at the bottom of the screen. This is of limited value. Often, we will really want to interact directly with the vim buffer. The key to do this is the vim module for python.1

The vim module for python can be used through

import vim

# do vim things

This is what :h python-vim actually documents, and I defer to the list of methods there. The important thing is that it provides direct access to vim buffers.

Today, we will use only the direct access to the current line, vim.current.line.

A Solution

I very routinely open scratch buffers (i.e. buffers that I call scratch.tmp). Sometimes I momentary notes, or I edit vim macros in place, or I define vim functions for short-term use. I will assume that we have opened up a scratch buffer and our pythonfile withfstrings.py. (In fact, I usually open it in a vsplit). I also very routinely assign Q to do whatever convenient function I have written in my scratch buffer (or whatever macro I want to repeat most simply). Of course, these are my idiosyncratic habits — the ideas are easy enough to translate.

In our scratch buffer, we can write a vim function, which is internally a python function, and map the symbol Q to call it.

function! Convert()
py3 << EOF

import vim

import re
bracketed = re.compile("{.*?}")

def convert():
    line = vim.current.line
    single = line.find("'")
    double = line.find('"')
    if single == -1:
        sep = '"'
    elif double == -1 or single < double:
        sep = "'"
    else:
        sep = '"'

    # l sep inner sep post
    l, _, m = line.partition(sep)
    inner, _, post = m.partition(sep)

    #get rid of f
    l = l[:-1]

    ret = ""
    var_names = bracketed.findall(inner)
    var_names = list(map(lambda x: x[1:-1], var_names))

    ret += l + sep + inner + sep
    ret += ".format("
    for var in var_names:
        ret += "{}={}, ".format(var, var)
    ret = ret[:-2]
    ret += ")" + post
    vim.current.line = ret

convert()
EOF

endfunction

com! Conv call Convert()
nnoremap Q :Conv<CR>

To use, one sources the scratch buffer (either directly, like :source scratch.tmp, or through navigating to its split and using :so %). Then one can find a line containing an f-string and hit Q (or alternately use :Conv).

Why is this good?

Although nontrivial, writing a simple python script like this takes only a few minutes. And then converting f-strings became the least important part of my backporting project.2

And more broadly, this is such an easy process. Off-loading the mental burden of repeating annoying tasks is valuable. The most revelatory aspect of this experience for me is that it’s easy enough to allow throwaway functions for momentary ease.

In my recent application, I converted 482 f-strings using this function. A few of them were multiline strings and my (admittedly simple) function failed — and so I did those by hand. But it took me less than 10 minutes to write the function (maybe even less than 5, though my first function expected double quotes only). Overall, this was a great gain.

Keeping the Script

Having come this far, it’s worth considering how we might keep the script around if we wanted to.

One good approach is to separate the python from the vim (allowing, for instance, testing on the python itself) and have a thin vim wrapper. We’ll look at this in two possible levels of encapsulation.

  1. Separate the python from the vim.
  2. Make the function a plugin. (Presumably for slightly more meaningful functions than this one).

Separate the Files

Let’s separate the python from the vim. In this was we can approach the python as proper little python script, merely waiting for a thin vim wrapper around it at the end.

We can separate the python out into the following file, convert_fstring.py.

# convert_fstring.py
import re
bracketed = re.compile("{.*?}")

def convert(line):
    single = line.find("'")
    double = line.find('"')
    if single == -1:
        sep = '"'
    elif double == -1 or single < double:
        sep = "'"
    else:
        sep = '"'

    # l sep inner sep post
    l, _, m = line.partition(sep)
    inner, _, post = m.partition(sep)

    # get rid of f
    l = l[:-1]

    ret = ""
    var_names = bracketed.findall(inner)
    var_names = list(map(lambda x: x[1:-1], var_names))

    ret += l + sep + inner + sep
    ret += ".format("
    for var in var_names:
        ret += "{}={}, ".format(var, var)
    ret = ret[:-2]
    ret += ")" + post
    return ret

if __name__ == "__main__":
    test_input = 'mystr = f"This {is} an {f}-string".reverse()'
    expected  = 'mystr = "This {is} an {f}-string".format(is=is, f=f).reverse()'
    assert expected == convert(test_input)

This is a raw python file. I included a mock unit-test (in case one was testing the function while writing it… I didn’t compose the function like this because I didn’t think about it, but in the future I probably will).

Now let’s write a thin vim wrapper around it.

" convert_string.vim

let s:script_dir = fnamemodify(resolve(expand('<sfile>', ':p')), ':h')

function! Convert()
py3 << EOF

import sys
import vim

script_dir = vim.eval('s:script_dir')
sys.path.insert(0, script_dir)

import convert_fstring

def convert():
  out = convert_fstring.convert(vim.current.line)
  vim.current.line = out

convert()
EOF

endfunction

com! Conv call Convert()
nnoremap Q :Conv<CR>

This is mostly pretty clear, with (I think) two exceptions concerning s:script_dir.

The problem comes from trying to import convert_fstring — it’s not in our PYTHONPATH, and the current working directory for python from within vim is a bit weird. It would be possible to directly code in the current directory into the PYTHONPATH, but I think it is more elegant to have convert_fstring.vim add the location of convert_fstring.py to python’s path.3 One can do that through

There are two additions of note that address this import. The first is the line

let s:script_dir = fnamemodify(resolve(expand('<sfile>', ':p')), ':h')

This sets a script-local variable (the prefix s:) containing the directory in which the script was sourced from. (This is where we use the assumption that the vimfile is in the same directory as the python file. If they’re in relative directories, then one much change the path addition to python appropriately).

The string <sfile> is populated automatically by vim to contain the filename of the sourcefile. Calling expand with the :p filemodifier returns the complete path of <sfile>. Calling resolve follows symlinks so that the path is absolute. And the final fnamemodify with the :h modifier returns the head, or rather the directory, of the file. Thus the result is to get an absolute path to the directory containing the script (and in this case also the python file).

Then in the python function, we add this location to the path through

script_dir = vim.eval('s:script_dir')
sys.path.insert(0, script_dir)

The first line has vim convert the vim variable into a python string, and the second inserts this directory into the PYTHONPATH.

I have a collection of loosely organized helper scripts in a (creatively named) ~/scripts directory. Some of these were written as pure python shellscripts that I’ve added some vim wrappers around.

Writing a Plugin

To reiterate, I consider this excessive for my sample application. But we’ve covered so many of the ideas that we should touch on it now.

Any plugin should follow Tim Pope’s Pathogen design model, with the ultimate goal of having a structure that looks like

myplugin/
  README.markdown
  LICENSE
  autoload/
    myplugin.vim
    ...
  plugin/
  ...

Pathogen (or Pathogen-compatible plugin managers, which as far as I know means all of them… like Vundle or vim-plug) will allow plugins to be installed in ~/.vim/bundle, and each plugin there will be added to vim’s rtp. 4 Each plugin manager installs plugins (i.e. adds to the runtimepath) in its own way. For Vundle, I include an extra line in my .vimrc.

Suppose I want to package my script as a plugin called fstring_converter. Then I’ll create the directory structure

fstring_converter/
  ftplugin/
    python.vim
    convert_fstring.py

where python.vim is what I called convert_fstring.vim before. Placing fstring_converter in ~/.vim/bundle (or symlinking it, or installing it there through e.g. Vundle) will “install it”. Then opening a python file will load it, and one can either Conv a line or (as it’s currently written) use Q. (Although I think it’s a bit unkind and certainly unsustainable to create this mapping for users).

I note that one should generically use autoload/ when available, but I don’t touch that now.

As an additional note, vim does add some directories to the PYTHONPATH under the hood. For each directory in vim’s runtimepath, vim adds the subdirectory python3 (and also pythonx) to the python module search path. As a result, we could omit the explicit path addition to the python.vim (aka convert_fstring.vim) file if we organized the plugin like

fstring_converter/
  ftplugin/
    python.vim
  python3/
    convert_fstring.py

Regardless, this describes a few ways to make a vim plugin out of our python script.

Posted in Programming, Python, vim | Tagged , , , , | Leave a comment

Extra comparisons in Python’s timsort

Reading through the comp.lang.python mailing list, I saw an interesting question concerning the behavior of the default sorting algorithm in python. This led to this post.

Python uses timsort, a clever hybrid sorting algorithm with ideas borrowing from merge sort and (binary) insertion sort. A major idea in timsort is to use the structure of naturally occuring runs (consecutive elements in the list that are either monotone increasing or monotone decreasing) when sorting.

Let’s look at the following simple list.

10, 20, 5

A simple sorting algorithm is insertion sort, which just advances through the list and inserts each number into the correct spot. More explicitly, insertion sort would

  1. Start with the first element, 10. As a list with one element, it is correctly sorted tautologically.
  2. Now consider the second element, 20. We insert this into the correct position in the already-sorted list of previous elements. Here, that just means that we verify that 20 > 10, and now we have the sorted sublist consisting of 10, 20.
  3. Now consider the third element, 5. We want to insert this into the correct position in the already-sorted list of previous elements. A naively easy way to do this is to either scan the list from the right or from the left, and insert into the correct place. For example, scanning from the right would mean that we compare 5 to the last element of the sublist, 20. As 5 < 20, we shift left and compare 5 to 10. As 5 < 10, we shift left again. As there is nothing left to compare against, we insert 5 at the beginning, yielding the sorted list 5, 10, 20.

How many comparisons did this take? This took 20 > 10, 5 < 20, and 5 < 10. This is three comparisons in total.

We can see this programmatically as well. Here is one implementation of insertion_sort, as described above.

def insertion_sort(lst):
    '''
    Sorts `lst` in-place. Note that this changes `lst`.
    '''
    for index in range(1, len(lst)):
        current_value = lst[index]
        position = index
        while position > 0 and lst[position - 1] > current_value:
            lst[position] = lst[position - 1]
            position = position - 1
        lst[position] = current_value

Let’s also create a simple Number class, which is just like a regular number, except that anytime a comparison is done it prints out the comparison. This will count the number of comparisons made for us.

class Number:
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return self.__str__()

    def __lt__(self, other):
        if self.value < other.value:
            print("{} < {}".format(self, other))
            return True
        print("{} >= {}".format(self, other))
        return False

    def __eq__(self, other):
        if self.value == other.value:
            print("{} = {}".format(self, other))
            return True
        return False

    def __gt__(self, other):
        return not ((self == other) or (self < other))

    def __le__(self, other):
        return (self < other) or (self == other)

    def __ge__(self, other):
        return not (self < other)

    def __nq__(self, other):
        return not (self == other)

With this class and function, we can run

lst = [Number(10), Number(20), Number(5)]
insertion_sort(lst)
print(lst)

which will print

10 < 20
20 >= 5
10 >= 5
[5, 10, 20]

These are the three comparisons we were expecting to see.

Returning to python’s timsort — what happens if we call python’s default sorting method on this list? The code

lst = [Number(10), Number(20), Number(5)]
lst.sort()
print(lst)

prints

20 >= 10
5 < 20
5 < 20
5 < 10
[5, 10, 20]

There are four comparisons! And weirdly, the method checks that 5 < 20 twice in a row. What’s going on there?1

At its heart, this was at the core of the thread on comp.lang.python. Why are there extra comparisons in cases like this?

Poking around the implementation of timsort taught me a little bit more about timsort.2

Timsort approaches this sorting task in the following way.

  1. First, timsort tries to identify how large the first run within the sequence is. So it keeps comparing terms until it finds one that is out of order. In this case, it compares 20 to 10 (finding that 20 > 10, and thus the run is increasing), and then compares 5 to 20 (finding that 5 < 20, and thus that 5 is not part of the same run as 10, 20). Now the run is identified, and there is one element left to incorporate.
  2. Next timsort tries to insert 5 into the already-sorted run. It is more correct to say that timsort attempts to do a binary insertion, since one knows already that the run is sorted.3 In this binary insertion, timsort will compare 5 with the middle of the already-sorted run 10, 20. But this is a list of length 2, so what is its middle element? It turns out that timsort takes the latter element, 20, in this case. As 5 < 20, timsort concludes that 5 should be inserted somewhere in the first half of the run 10, 20, and not in the second half.
  3. Of course, the first half consists entirely of 10. Thus the remaining comparison is to check that 5 < 10, and now the list is sorted.

We count4 all four of the comparisons. The doubled comparison is due to the two tasks of checking whether 5 is in the same run as 10, 20, and then of deciding through binary insertion where to place 5 in the smaller sublist of 10, 20.

Now that we’ve identified a doubled comparison, we might ask Why is it this way? Is this something that should change?

The short answer is it doesn’t really matter. A longer answer is that to apply this in general would cause additional comparisons to be made, since this applies in the case when the last element of the run agrees in value with the central value of the run (which may occur for longer lists if there are repeated values). Checking that this happens would probably either involve comparing the last element of the run with the central value (one extra comparison, so nothing is really saved anyway), or perhaps adding another data structure like a skip list (which seems sufficiently more complicated to not be worth the effort). Or it would only apply when sorting really short lists, in which case there isn’t much to worry about.

Learning a bit more about timsort made me realize that I could probably learn a lot by really understanding an implementation of timsort, or even a slightly simplified implementation. It’s a nice reminder that one can choose to optimize for certain situations or behaviors, and this might not cover all cases perfectly — and that’s ok.

Posted in Programming, Python | Tagged , | Leave a comment

Segregation, Gerrymandering, and Schelling’s Model

[This note is more about modeling some of the mathematics behind political events than politics themselves. And there are pretty pictures.]

Gerrymandering has become a recurring topic in the news. The Supreme Court of the US, as well as more state courts and supreme courts, is hearing multiple cases on partisan gerrymandering (all beginning with a case in Wisconsin).

Intuitively, it is clear that gerrymandering is bad. It allows politicians to choose their voters, instead of the other way around. And it allows the majority party to quash minority voices.

But how can one identify a gerrymandered map? To quote Justice Kennedy in his Concurrence the 2004 Supreme Court case Vieth v. Jubelirer:

When presented with a claim of injury from partisan gerrymandering, courts confront two obstacles. First is the lack of comprehensive and neutral principles for drawing electoral boundaries. No substantive definition of fairness in districting seems to command general assent. Second is the absence of rules to limit and confine judicial intervention. With uncertain limits, intervening courts–even when proceeding with best intentions–would risk assuming political, not legal, responsibility for a process that often produces ill will and distrust.

Later, he adds to the first obstacle, saying:

The object of districting is to establish “fair and effective representation for all citizens.” Reynolds v. Sims, 377 U.S. 533, 565—568 (1964). At first it might seem that courts could determine, by the exercise of their own judgment, whether political classifications are related to this object or instead burden representational rights. The lack, however, of any agreed upon model of fair and effective representation makes this analysis difficult to pursue.

From Justice Kennedy’s Concurrence emerges a theme — a “workable standard” of identifying gerrymandering would open up the possibility of limiting partisan gerrymandering through the courts. Indeed, at the core of the Wisconsin gerrymandering case is a proposed “workable standard”, based around the efficiency gap.

 

Thomas Schelling and Segregation

In 1971, American economist Thomas Schelling (who later won the Nobel Prize in Economics in 2005) published Dynamic Models of Segregation (Journal of Mathematical Sociology, 1971, Vol 1, pp 143–186). He sought to understand why racial segregation in the United States seems so difficult to combat.

He introduced a simple model of segregation suggesting that even if each individual person doesn’t mind living with others of a different race, they might still choose to segregate themselves through mild preferences. As each individual makes these choices, overall segregation increases.

I write this post because I wondered what happens if we adapt Schelling’s model to instead model a state and its district voting map. In place of racial segregation, I consider political segregation. Supposing the district voting map does not change, I wondered how the efficiency gap will change over time as people further segregate themselves.

It seemed intuitive to me that political segregation (where people who had the same political beliefs stayed largely together and separated from those with different political beliefs) might correspond to more egregious cases of gerrymandering. But to my surprise, I was (mostly) wrong.

Let’s set up and see the model.

(more…)

Posted in Expository, Mathematics, Politics, Programming, Python | Tagged , , | Leave a comment

Advent of Code: Day 4

This is a very short post in my collection working through this year’s Advent of Code challenges. Unlike the previous ones, this has no mathematical comments, as it was a very short exercise. This notebook is available in its original format on my github.

Day 4: High Entropy Passphrases

Given a list of strings, determine how many strings have no duplicate words.

This is a classic problem, and it’s particularly easy to solve this in python. Some might use collections.Counter, but I think it’s more straightforward to use sets.

The key idea is that the set of words in a sentence will not include duplicates. So if taking the set of a sentence reduces its length, then there was a duplicate word.

In [1]:
with open("input.txt", "r") as f:
    lines = f.readlines()
    
def count_lines_with_unique_words(lines):
    num_pass = 0
    for line in lines:
        s = line.split()
        if len(s) == len(set(s)):
            num_pass += 1
    return num_pass

count_lines_with_unique_words(lines)
Out[1]:
455

I think this is the first day where I would have had a shot at the leaderboard if I’d been gunning for it.

Part 2

Let’s add in another constraint. Determine how many strings have no duplicate words, even after anagramming. Thus the string

abc bac

is not valid, since the second word is an anagram of the first. There are many ways to tackle this as well, but I will handle anagrams by sorting the letters in each word first, and then running the bit from part 1 to identify repeated words.

In [2]:
with open("input.txt", "r") as f:
    lines = f.readlines()
    
sorted_lines = []
for line in lines:
    sorted_line = ' '.join([''.join(l) for l in map(sorted, line.split())])
    sorted_lines.append(sorted_line)

sorted_lines[:2]
    
Out[2]:
['bddjjow acimrv bcjjm anr flmmos fiosv',
 'bcmnoxy dfinyzz dgmp dfgioy hinrrv eeklpuu adgpw kqv']
In [3]:
count_lines_with_unique_words(sorted_lines)
Out[3]:
186
Posted in Expository, Programming, Python | Tagged , , | 1 Comment

Advent of Code: Day 3

This is the third notebook in my posts on the Advent of Code challenges. The notebook in its original format can be found on my github.

Day 3: Spiral Memory

Numbers are arranged in a spiral

17  16  15  14  13
18   5   4   3  12
19   6   1   2  11
20   7   8   9  10
21  22  23---> ...

Given an integer n, what is its Manhattan Distance from the center (1) of the spiral? For instance, the distance of 3 is $2 = 1 + 1$, since it’s one space to the right and one space up from the center.

Here’s my idea. The bottom right corner of the $k$th layer is the integer $(2k+1)^2$, since that’s how many integers are contained within that square. The other three corners in that layer are $(2k+1)^2 – 2k, (2k+1)^2 – 4k$, and $(2k+1)^2 – 6k$. Finally, the closest spot on the $k$th layer to the origin is at distance $k$: these are the four “axis locations” halfway between the corners, at $(2k+1)^2 – k, (2k+1)^2 – 3k, (2k+1)^2 – 5k$, and $(2k+1)^2 – 7k$.

For instance when $k = 1$, the bottom right is $(2 + 1)^2 = 9$, and the four “axis locations” are $9 – 1, 9 – 3, 9-5$, and $9-7$. The “axis locations” are $k$ away, and the corners are $2k$ away.

So I will first find which layer the number is on. Then I’ll figure out which side it’s on, and then how far away it is from the nearest “axis location” or “corner”.

My given number happens to be 289326.

In [1]:
import math

def find_lowest_larger_odd_square(n):
    upper = math.ceil(n**.5)
    if upper %2 == 0:
        upper += 1
    return upper
In [2]:
assert find_lowest_larger_odd_square(39) == 7
assert find_lowest_larger_odd_square(26) == 7
assert find_lowest_larger_odd_square(25) == 5
In [3]:
find_lowest_larger_odd_square(289326)
Out[3]:
539
In [4]:
539**2 - 289326
Out[4]:
1195

It happens to be that our integer is very close to an odd square.
The square is $539^2$, and the distance to that square is $538$ from the center.

Note that $539 = 2(269) + 1$, so this is the $269$th layer of the square.
The previous corner to $539^2$ is $539^2 – 538$, and the previous corner to that is $539^2 – 2\cdot538 = 539^2 – 1076$.
This is the nearest corner.
How far away from the square is this corner?

(more…)

Posted in Expository, Programming, Python | Tagged , , | Leave a comment

Advent of Code: Day 2

This is the second notebook in my posts on the Advent of Code challenges. This notebook in its original format can be found on my github.

Day 2: Corruption Checksum, part I

You are given a table of integers. Find the difference between the maximum and minimum of each row, and add these differences together.

There is not a lot to say about this challenge. The plan is to read the file linewise, compute the difference on each line, and sum them up.

In [1]:
with open("input.txt", "r") as f:
    lines = f.readlines()
lines[0]
Out[1]:
'5048\t177\t5280\t5058\t4504\t3805\t5735\t220\t4362\t1809\t1521\t230\t772\t1088\t178\t1794\n'
In [2]:
l = lines[0]
l = l.split()
l
Out[2]:
['5048',
 '177',
 '5280',
 '5058',
 '4504',
 '3805',
 '5735',
 '220',
 '4362',
 '1809',
 '1521',
 '230',
 '772',
 '1088',
 '178',
 '1794']
In [3]:
def max_minus_min(line):
    '''Compute the difference between the largest and smallest integer in a line'''
    line = list(map(int, line.split()))
    return max(line) - min(line)

def sum_differences(lines):
    '''Sum the value of `max_minus_min` for each line in `lines`'''
    return sum(max_minus_min(line) for line in lines)
In [4]:
testcase = ['5 1 9 5','7 5 3', '2 4 6 8']
assert sum_differences(testcase) == 18
In [5]:
sum_differences(lines)
Out[5]:
58975

Mathematical Interlude

In line with the first day’s challenge, I’m inclined to ask what we should “expect.” But what we should expect is not well-defined in this case. Let us rephrase the problem in a randomized sense.

Suppose we are given a table, $n$ lines long, where each line consists of $m$ elements, that are each uniformly randomly chosen integers from $1$ to $10$. We might ask what is the expected value of this operation, of summing the differences between the maxima and minima of each row, on this table. What should we expect?

As each line is independent of the others, we are really asking what is the expected value across a single row. So given $m$ integers uniformly randomly chosen from $1$ to $10$, what is the expected value of the maximum, and what is the expected value of the minimum?

 

Expected Minimum

Let’s begin with the minimum. The minimum is $1$ unless all the integers are greater than $2$. This has probability
$$ 1 – \left( \frac{9}{10} \right)^m = \frac{10^m – 9^m}{10^m}$$
of occurring. We rewrite it as the version on the right for reasons that will soon be clear.
The minimum is $2$ if all the integers are at least $2$ (which can occur in $9$ different ways for each integer), but not all the integers are at least $3$ (each integer has $8$ different ways of being at least $3$). Thus this has probability
$$ \frac{9^m – 8^m}{10^m}.$$
Continuing to do one more for posterity, the minimum is $3$ if all the integers are at least $3$ (each integer has $8$ different ways of being at least $3$), but not all integers are at least $4$ (each integer has $7$ different ways of being at least $4$). Thus this has probability

$$ \frac{8^m – 7^m}{10^m}.$$

And so on.

Recall that the expected value of a random variable is

$$ E[X] = \sum x_i P(X = x_i),$$

so the expected value of the minimum is

$$ \frac{1}{10^m} \big( 1(10^m – 9^m) + 2(9^m – 8^m) + 3(8^m – 7^m) + \cdots + 9(2^m – 1^m) + 10(1^m – 0^m)\big).$$

This simplifies nicely to

$$ \sum_ {k = 1}^{10} \frac{k^m}{10^m}. $$

Expected Maximum

The same style of thinking shows that the expected value of the maximum is

$$ \frac{1}{10^m} \big( 10(10^m – 9^m) + 9(9^m – 8^m) + 8(8^m – 7^m) + \cdots + 2(2^m – 1^m) + 1(1^m – 0^m)\big).$$

This simplifies to

$$ \frac{1}{10^m} \big( 10 \cdot 10^m – 9^m – 8^m – \cdots – 2^m – 1^m \big) = 10 – \sum_ {k = 1}^{9} \frac{k^m}{10^m}.$$

Expected Difference

Subtracting, we find that the expected difference is

$$ 9 – 2\sum_ {k=1}^{9} \frac{k^m}{10^m}. $$

From this we can compute this for each list-length $m$. It is good to note that as $m \to \infty$, the expected value is $9$. Does this make sense? Yes, as when there are lots of values we should expect one to be a $10$ and one to be a $1$. It’s also pretty straightforward to see how to extend this to values of integers from $1$ to $N$.

Looking at the data, it does not appear that the integers were randomly chosen. Instead, there are very many relatively small integers and some relatively large integers. So we shouldn’t expect this toy analysis to accurately model this problem — the distribution is definitely not uniform random.
But we can try it out anyway.

(more…)

Posted in Expository, Programming, Python | Tagged , , | Leave a comment

Advent of Code: Day 1

I thoroughly enjoyed reading through Peter Norvig’s extraordinarily clean and nice solutions to the Advent of Code challenge last year. Inspired by his clean, literate programming style and the convenience of jupyter notebook demonstrations, I will look at several of these challenges in my own jupyter notebooks.

My background and intentions aren’t the same as Peter Norvig’s: his expertise dwarfs mine. And timezones are not kind to those of us in the UK, and thus I won’t be competing for a position on the leaderboards. These are to be fun. And sometimes there are tidbits of math that want to come out of the challenges.

Enough of that. Let’s dive into the first day.

Day 1: Inverse Captcha, Part 1

Given a sequence of digits, find the sum of those digits which match the following digit. The sequence is presumed circular, so the first digit may match the last digit.

This would probably be done the fastest by looping through the sequence.

In [1]:
with open('input.txt', 'r') as f:
    seq = f.read()
seq = seq.strip()
seq[:10]
Out[1]:
'1118313623'
In [2]:
def sum_matched_digits(s):
    "Sum of digits which match following digit, and first digit if it matches last digit"
    total = 0
    for a,b in zip(s, s[1:]+s[0]):
        if a == b:
            total += int(a)
    return total

They provide a few test cases which we use to test our method against.

In [3]:
assert sum_matched_digits('1122') == 3
assert sum_matched_digits('1111') == 4
assert sum_matched_digits('1234') == 0
assert sum_matched_digits('91212129') == 9

For fun, this is a oneline version.

(more…)

Posted in Expository, Programming, Python | Tagged , , | 1 Comment

Comments vs documentation in python

In my first programming class we learned python. It went fine (I thought), I got the idea, and I moved on (although I do now see that much of what we did was not ‘pythonic’).

But now that I’m returning to programming (mostly in python), I see that I did much of it all wrong. One of my biggest surprises was how wrong I was about comments. Too many comments are terrible. Redundant comments make code harder to maintain. If the code is too complex to understand without comments, it’s probably just bad code.

That’s not so hard, right? You read some others’ code, see their comment conventions, and move on. You sort of get into zen moments where the code becomes very clear and commentless, and there is bliss. But then we were at a puzzling competition, and someone wanted to use a piece of code I’d written. Sure, no problem! And the source was so beautifully clear that it almost didn’t even need a single comment to understand.

But they didn’t want to read the code. They wanted to use the code. Comments are very different than documentation. The realization struck me, and again I had it all wrong. In hindsight, it seems so obvious! I’ve programmed java, I know about javadoc. But no one had ever actually wanted to use my code before (and wouldn’t have been able to easily if they had)!

Enter pydoc and sphinx. These are tools that allow html API to be generated from comment docstrings in the code itself. There is a cost – some comments with specific formatting are below each method or class. But it’s reasonable, I think.

Pydoc ships with python, and is fine for single modules or small projects. But for large projects, you’ll need something more. In fact, even the documentation linked above for pydoc was generated with sphinx:

The pydoc documentation is  ‘Created using Sphinx 1.0.7.’

This isn’t to say that pydoc is bad. But I didn’t want to limit myself. Python uses sphinx, so I’ll give it a try too.

And thus I (slightly excessively, to get the hang of it) comment on my solutions to Project Euler on my github. The current documentation looks alright, and will hopefully look better as I get the hang of it.

Full disclosure – this was originally going to be a post on setting up sphinx-generated documentation on github’s pages automatically. I got sidetracked – that will be the next post.

Posted in Programming, Python | Tagged , , , , , | Leave a comment