CyberSpy

Rantings from a guy with way too much free time

Recursion Revisited

Recursion, from more than one point-of-view.

A common programming idiom in computer science is solving a problem by self-reference, also known as recursion. In this post, we look at two different implementations of the same problem.

Solve a recursive problem in two different programming language paradigms

Let's look at the solution to a simple problem, compute $f(x)=e^{x}$.

We will illustrate two separate solutions - one in a procedural language (python), and the other in a functional language (elixir).

Let's start off with the functional language. Were does recursion come into play?

We define the function $f(x)=e^x$ as the infinite sum, $\text{ }f(x) = \sum_{n=0}^\infty{\frac{x^n}{n!}}$

In our solution below, we define two separate recursive functions, exp/2 and fac/1. What's interesting to note here is how each of these functions has two separate definitions. This is an aspect of programming in elixir that elegantly uses pattern-matching to return different results depending upon the input. Our two functions nicely dovetail into the base-case and recursive case of a recursive algorithm.

For example, looking at exp/2, the first function definition returns 1 for any value of x (as indicated by the _ preceding the variable) and returns 1. This is the mathematical equivalent of $x^0=1\text{ for any }x$.

The second definition of exp/2 is the recursive case. for any value of $n\gt0$. Moreover, we define exp(x, n) as $\frac{e^x}{n!}$ + exp(x, n-1).

Similarly for the definition of fac/1 we see two definitions; one for $n=0$ and another for all values of $n\gt0$.

Continue reading

Visualizing the News: Grab your PILlow

2017-11-12 python programming
A Picture's Worth a Gazillion Bits newsapi This weekend, I tripped over a neat news REST-ful api called newsapi. Grab an API key and you're off to the races. There are tons of live headlines - News API can provide headlines from 70 worldwide sources. There are basically two api endpoints: GET https://newsapi.org/v1/articles GET https://newsapi.org/v1/sources Register for an account and generate an api-key and let's get started. Accessing the API with Python newsapi can easily be accessed using a browser since the REST-ful method used is a GET method. Continue reading

Making Heads or Tails out of Recursion and Combinatorial Math

2017-11-09 programming math python
GNU — GNU's Not Unix I thought I'd take a look at two topics at once and make some fun by mashing them together. Today's topic is recursion. In computer science (and in math, although we call the equation a recurrence relation) recursion is an often misunderstood concept causing lots of panic and anxiety. In reality - it's pretty easy once you wrap you head around the idiom. What is recursion? Continue reading

Getting Visual With It

Time to Get Vizzy With It! Like Will says: Gettin vizzy wit it Na na na na na na na nana Na na na na nana Gettin vizzy wit it… Plot thickens Time to turn on the lights and see what our data objects look like when we turn them into visualized plots. Sure, we can use the print function to see the numbers within our numpy objects. Better yet, let's turn our objects into pretty graphical images. Continue reading

Do the Numpy

2017-11-07 programming python

Do the Numpy Dance, Is your Chance to do the Nump!

Sir Numpy says:

The Numpy Dance is your chance to do the nump Do the Numpy Nump, come on and do the Numpty Nump Do the Numpy Nump, just watch me do the Numpty Nump Do ya know what I'm doin’, doin’ the Numpty Nump Do the Numpy Nump, do the Numpty Nump

Start at the beginning: NumPy

The first library that we will investigate is numpy. Simply put, numpy allows us to represent mathematical objects like arrays and matricies of different datatypes and performs operations on those objects thereby easing the burden of writing the tedious code within your applications to do the mundane representations and operations.

Diving right in, let's look at some examples of types of objects we can create and how we can operate on them using the library.

creation of arrays

The most basic thing we can do is create a one-dimensional array (also known as a vector):

import numpy as np

v = np.array([1,2,3,4])

Here we've created a row vector containing for elements. Numpy objects are typed and implicitly, we've created an int64 type by passing in the integers. We can verify the type of our array:

>>> v.dtype
dtype('int64')

We can also verify the dimensions of our array (i.e. the shape):

>>> v.shape
(4,)

Rather than implicitly typing our array object, we can explicitly specify it when we create or array:

v = np.array([1,2,3,4], dtype=float)

We can also turn a list into an array by shaping it from an array range:

>>> v = np.arange(16).reshape(4,4)
array([[ 0,  1,  2,  3],
       [ 4,  5,  6,  7],
       [ 8,  9, 10, 11],
       [12, 13, 14, 15]])

arange works semantically like our built-in range function, creating an array ranging over the given value. So long as the reshaping integers, n and m are factors of the len(arange(a,b,c)), then we can reshape our range into an n by m array. For example:

>>> v = np.arange(0,32,2).reshape(4,4)
array([[ 0,  2,  4,  6],
       [ 8, 10, 12, 14],
       [16, 18, 20, 22],
       [24, 26, 28, 30]])

We can even create complex-valued arrays:

 >>> c = np.array( [ [1+2.j,2+1.j], [3+5.j,4+1.j] ], dtype=complex )
 array([[ 1.+2.j,  2.+1.j],
       [ 3.+5.j,  4.+1.j]])

operations on arrays

So you created an array, now what? We can perform operations on them that are familair, like addition subtraction, multiplication, and division resulting in the expected semantics for arrays. For example:

# given two arrays, a and b, and vector c
a = np.array([[1,2],[3,4]])
b = np.array([[4,3],[2,1]])
c = np.array([0.5,2])

# add two arrays
>>> a + b
array([[5, 5],
       [5, 5]])
# multiply two arrays
>>> a * b
array([[4, 6],
       [6, 4]])

# inverse
>>> 1/a
array([[ 1.        ,  0.5       ],
       [ 0.33333333,  0.25      ]])

# sin of all values in array a
>>> np.sin(a)
array([[ 0.84147098,  0.90929743],
       [ 0.14112001, -0.7568025 ]])

There are nearly 600 functions in the numpy library - this is a brief sample of only the basic ones. Check out the documentation to learn more. To give you a sense of how extensive the library is, here are the top-level categories of functions:

  • Array creation routines
  • Array manipulation routines
  • Binary operations
  • String operations
  • C-Types Foreign Function Interface (numpy.ctypeslib)
  • Datetime Support Functions
  • Data type routines
  • Optionally Scipy-accelerated routines (numpy.dual)
  • Mathematical functions with automatic domain (numpy.emath)
  • Discrete Fourier Transform (numpy.fft)
  • Financial functions
  • Functional programming
  • NumPy-specific help functions
  • Indexing routines
  • Input and output
  • Linear algebra (numpy.linalg)
  • Logic functions
  • Masked array operations
  • Mathematical functions
  • Matrix library (numpy.matlib)
  • Miscellaneous routines
  • Random sampling (numpy.random)
  • Set routines
  • Sorting, searching, and counting
  • Statistics

Go experiment with the library and get more familiar with function of interest to you. Now that we have a basic undertanding, let's move on to visualizing data representations and transformations within numpy objects.

Data Science with Python: Let there be Light

2017-11-05 programming
Data-Science - Clueless? No prob. We got you dude. So you've likely heard all the hype about “data-science” - and if you're not among the cool kids, it might be a wee-bit overwhelming to you. Where to even start? What does it all mean? How do you even begin to understand what you need to know to begin learning more and making progress in the field. Let's start off with a few definitions: Continue reading

Conway's Game of Life

2017-11-03 programming

Conway's Game of Life

In 1970, British mathematician John Horton Conway invented a cellular automaton called The Game of Life. This simple game is governed by its initial cellular state and four simple rules:

  • Any live cell with fewer than two live neighbors dies, as if caused by underpopulation.
  • Any live cell with two or three live neighbors lives on to the next generation.
  • Any live cell with more than three live neighbors dies, as if by overpopulation.
  • Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The rules are applied to all the cells in the grid, starting with the initial grid populated with the starting live cells. After many iterations, the grid comes to an end-state which can be unexpected given the initial seed state.

To make this cellular automaton more interesting, I've forked and modified a gist that uses pygames, a nice python module that aids in the development of python-based interactive visual games.

Here's the gist for the code. I won't go through it line-by-line, as it's pretty obvious, but a few points worth mentioning. Take a lool at how the Ben Nuttall (the person from whom I forked the initial code) solves the neighbor index bounds problem. It's novel. There are three ways count neigbors.

  • wrap the grid with an outward perimeters of zeros that are not visible so that the bounds of all eight neighbors will be valid and will not result in an index bounds error
  • preceed each of the eight neighbors with a conditional statement verifies the bounds are valid
  • use a try and except clause to attempt to index our grid and pass if the resulting index would cause an index bounds error.

Take a look:

def count_neighbors(grid, position):
    x,y = position
    neighbour_cells = [(x - 1, y - 1), (x - 1, y + 0), (x - 1, y + 1),
                       (x + 0, y - 1),                 (x + 0, y + 1),
                       (x + 1, y - 1), (x + 1, y + 0), (x + 1, y + 1)]
    count = 0
    for x,y in neighbour_cells:
        if x >= 0 and y >= 0:
            try:
                count += grid[x][y]
            except:
                pass
    return count

Pretty cool. He creates a list of neighbors enumerating all eight (and leaving a blank in the middle where we live!) We then iterate over the list by x and y coordinates and attempt to index grid[x][y] inside a try clause. if the resulting indexing is invalid it throws an except and it's simply ignored.

The foked version that I created parameterizes a few things and adds a title screen that dynamically shows the current iteration.

Have some fun and experiment with big and little numbers for block_size. The bigger the block_size, the less number of cells on the grid. Also experiment with different sizes for iteration count. The larger the number, the higher the probability that you'll exhaust the cellular state from its initial seed state.

Installation Instructions

Here's a quick summary of how to setup your environment to run the gist:

python3 -m venv sandbox
source sandbox/bin/activate
pip install pygame

Next copy the raw file below into conway.py:

Older posts