I've been training in Shotokan karate on-and-off for the past 15 years or so. The original Okinawan curriculum, dating back to Itosu in the late 19th century, consisted exclusively of katas. Hence, the katase must be taken as the core representation of the art form and combat system.
The modern curriculum tends to focus on sharp strikes, punches, and kicks. This is great, but the modern curriculum tends to under-emphasize the joint-locks, grappling, throws, and takedowns found throughout the katas. In fact, the kihon [basics] and kumite [sparring] curriculum tends to look quite different from the katas. One interpretation of this discrepancy, is that the katas are antiquated, mysterious, or impractical. My preferred interpretation is that we're missing something in our basics and sparring training. The grappling/throwing aspect is often under-emphasized.
I'm not the originator of this interpretation. Established practitioners and writers like Bruce Clayton, Iain Abernathy, and Kousaku Yokota have been popularizing this under-emphasized portion of the curriculum for many years. The under-emphasis comes from an over-emphasis in training in a way that complies with tournament rules. Throwing an opponent will not gain points under standard karate tournament rules, but punching or kicking him will.
Anyway, from time-to-time, I've started leading classes at my local shotokan dojo. I make sure to emphasize the grappling and throwing, and make sure the students practice these in pairs, as well as practicing how to fall correctly. I'm also taking a beginner's course in Judo, to get a more systematic treatment of throwing.
At the end of the day, there is nothing mystical about martial arts technique. It's just physics and anatomy. This is why there is great commonality in punching technique across art-forms, from boxing to karate to muay thai.
Saturday, December 27, 2014
Friday, November 14, 2014
Pallindromes in C++
Sometimes you come across puzzles or interview questions along the lines of "Find the longest palindrome in a string." To be honest, I've never looked for palindromes in my work, but I think it's a good exercise nonetheless. For one thing, the "best practices" strategies can be applied to other problems. For another, the search for symmetric subsets in datasets of all types definitely does come up.
So, we might start this exercise by first writing a function to classify a string as a palindrome or not. A nice way to do this is to start with a pointer at either end of the string, and iterate them inwards, checking the lower and upper characters against each other at each stage. For example, if the first and last characters are equal, we iterate inwards. If not, we can return "false" immmediately. The following snippet shows this function.
So now, to find the longest palindrome in a string, we could just iterate over the string, looking at all substrings, and calling is_pallindrome() [notice my typo in the function name]. That sounds pretty straight-forward, but searching all substrings becomes O(N^2), kind of cumbersome.
A nice way to use the is_pallindrome() function is to think about strings that are centered at index i. So, we have a pointer that searches left from i, and a pointer that searches right from i, and we stop iterating when input[lower]!=input[upper]. This is very similar to the is_pallindrome() function.
There's another approach that's more efficient than the above. Sometimes a good way to think about such a problem is to find the desired subset that ends at index i. If I'm searching for a palindrome that ends at index i, I can store the longest palindrome that ended at index i-1. Then I simply have to look at the first index of that palindrome, and the character that precedes it in the input string.
The storage/caching can be implemented with a hashmap, so we store the longest palindrome that ends at each index, and then we can look it up at the next step. This means, each additional step only features two more comparisons. The following snippet implements this approach:
This is actually quite a bit more efficient in the searching, more like pseudo-linear instead of quadratic search. [Again notice my mispelling of palindrome.] The only thing is, we are storing a bunch of strings in this hashmap. We don't actually need to do this.
Instead, we can just store the indices or pointers that begin the palindromes that ends at each index in the input string. The following function does this.
So now we have, via dynamic programming, a pseudo-linear search, in that we basically have a linear search over the input string, but we have to store O(N) indices.
Did I really need the hashmap? Not necessarily; I could have used a regular old array, and had some code to check_bounds. On the other hand, the hashmap approach is generalizable to other problems, where the key values might not be simple ordinal numbers.
So, we might start this exercise by first writing a function to classify a string as a palindrome or not. A nice way to do this is to start with a pointer at either end of the string, and iterate them inwards, checking the lower and upper characters against each other at each stage. For example, if the first and last characters are equal, we iterate inwards. If not, we can return "false" immmediately. The following snippet shows this function.
bool is_pallindrome(string input){
int lower=0;
int upper=input.length()-1;
while (upper>lower){
if (input[upper]!=input[lower]) //If we find differing characters, not a pallindrome
return false;
upper--;
lower++;
}
return true;
}
So now, to find the longest palindrome in a string, we could just iterate over the string, looking at all substrings, and calling is_pallindrome() [notice my typo in the function name]. That sounds pretty straight-forward, but searching all substrings becomes O(N^2), kind of cumbersome.
A nice way to use the is_pallindrome() function is to think about strings that are centered at index i. So, we have a pointer that searches left from i, and a pointer that searches right from i, and we stop iterating when input[lower]!=input[upper]. This is very similar to the is_pallindrome() function.
There's another approach that's more efficient than the above. Sometimes a good way to think about such a problem is to find the desired subset that ends at index i. If I'm searching for a palindrome that ends at index i, I can store the longest palindrome that ended at index i-1. Then I simply have to look at the first index of that palindrome, and the character that precedes it in the input string.
The storage/caching can be implemented with a hashmap, so we store the longest palindrome that ends at each index, and then we can look it up at the next step. This means, each additional step only features two more comparisons. The following snippet implements this approach:
string longest_pallindrome_map(string input){
map<int, string> pal; //hashmap from index to longest pallindrome that *ends* at index
int max_length=0; int max_index=0;
for (int i=0; i<input.size(); i++){
int prev_index=i-pal[i-1].length()-1;
if (pal[i-1][0]==input[i]) //Looking for consecutive duplicate letters
pal[i]=pal[i-1]+input[i];
else if (input[i]==input[prev_index])
pal[i]=input[prev_index]+pal[i-1]+input[i]; //Looking at the character prior to previous pallindrome
else
pal[i]=string(input.begin()+i, input.begin()+i+1); //Longest pallindrome is current character
if (pal[i].length()>max_length){
max_index=i;
max_length=pal[i].length();
}
}
return pal[max_index];
}
This is actually quite a bit more efficient in the searching, more like pseudo-linear instead of quadratic search. [Again notice my mispelling of palindrome.] The only thing is, we are storing a bunch of strings in this hashmap. We don't actually need to do this.
Instead, we can just store the indices or pointers that begin the palindromes that ends at each index in the input string. The following function does this.
string longest_pallindrome(string input){
map<int, int> pal; //hashmap from current index, to the begin-index of the longest pallindrome that *ends* here
int max_length=0;
int max_ind=0;
for (int i=0; i<input.size(); i++){
int prev_index=pal[i-1];
if (input[i]==input[prev_index]){ //Looking for consecutive duplicate characters
pal[i]=prev_index;
}
else if (input[i]==input[prev_index-1]) //Looking at the index prior to the last pallindrome
pal[i]=prev_index-1;
else
pal[i]=i; //Longest pallindrome is simply the current character
if ((i-pal[i])>max_length){ //Finding the longest one along the way
max_ind=i;
max_length=i-pal[i];
}
}
return string(input.begin()+pal[max_ind], input.begin()+max_ind+1);
}
So now we have, via dynamic programming, a pseudo-linear search, in that we basically have a linear search over the input string, but we have to store O(N) indices.
Did I really need the hashmap? Not necessarily; I could have used a regular old array, and had some code to check_bounds. On the other hand, the hashmap approach is generalizable to other problems, where the key values might not be simple ordinal numbers.
Thursday, November 6, 2014
Housing Affordability in San Francisco [and the Bay Area]
If you live in the Bay Area, you know that the cost of living is high. By "cost of living," I don't mean food prices, fuel prices, or many other goods and services. I mainly mean the high prices for renting or purchasing property.
While many areas offer an array of low-end to high-end housing solutions, where the renter/buyer can adapt his budget to the options, San Francisco offers almost no availability at the low-end, and almost everything else at high-end prices, with premium-end a growing market share.
There is an array of historical reasons behind this strange, skewed distribution of housing options. The underlying reason is a geographically constrained area, with ample economic opportunities, which attracts a lot of people from all over the world. This underlying problem is exacerbated by Not-In-My-Backyard policies that make it difficult to develop higher-rise, higher-density housing.
Prop 13 severely reduces liquidity in the property market, because if you already own property and decide to move, you stand to increase your tax burden; all property owners stay put. Finally, rent control ensures that renters also stay put.
In 1978, people got tired of property tax increases, so they passed Prop 13 to limit/eliminate property tax increases, and consequences be damned! In 1979, San Franciscans got tired of rent increases, so they passed rent-control, and consequences be damned! Each of these policies are best-described as a "We were here first!" tax on newcomers.
Down where I live, on the Peninsula/Silicon Valley, there is no rent control, but rents are still very high. We have similarly high demand for housing here, and many high-paying employers nearby. One additional reason appears to be monopolistic ownership of rental properties. The same 2-3 companies own all the apartment complexes in town, so they alone control the going rents.
So what's wrong with high rents/home prices? Well, for the lower-income, they're a massive burden. For the middle and higher-income, they're a huge waste of resources. The excess money someone spends on rent or mortgage could go to purchasing other goods and services, creating more economic activity.
In any case, there's a great article on techcrunch that details the housing situation, and historical factors in San Francisco. It's well-researched, and a long but informative read.
While many areas offer an array of low-end to high-end housing solutions, where the renter/buyer can adapt his budget to the options, San Francisco offers almost no availability at the low-end, and almost everything else at high-end prices, with premium-end a growing market share.
There is an array of historical reasons behind this strange, skewed distribution of housing options. The underlying reason is a geographically constrained area, with ample economic opportunities, which attracts a lot of people from all over the world. This underlying problem is exacerbated by Not-In-My-Backyard policies that make it difficult to develop higher-rise, higher-density housing.
Prop 13 severely reduces liquidity in the property market, because if you already own property and decide to move, you stand to increase your tax burden; all property owners stay put. Finally, rent control ensures that renters also stay put.
In 1978, people got tired of property tax increases, so they passed Prop 13 to limit/eliminate property tax increases, and consequences be damned! In 1979, San Franciscans got tired of rent increases, so they passed rent-control, and consequences be damned! Each of these policies are best-described as a "We were here first!" tax on newcomers.
Down where I live, on the Peninsula/Silicon Valley, there is no rent control, but rents are still very high. We have similarly high demand for housing here, and many high-paying employers nearby. One additional reason appears to be monopolistic ownership of rental properties. The same 2-3 companies own all the apartment complexes in town, so they alone control the going rents.
So what's wrong with high rents/home prices? Well, for the lower-income, they're a massive burden. For the middle and higher-income, they're a huge waste of resources. The excess money someone spends on rent or mortgage could go to purchasing other goods and services, creating more economic activity.
In any case, there's a great article on techcrunch that details the housing situation, and historical factors in San Francisco. It's well-researched, and a long but informative read.
Tuesday, October 14, 2014
Matplotlib Animations, Using Stored Data, Writing Video
There are some good matplotlib animations examples floating around the internet, including here and here. These were useful and I gained a great deal from them, but my particular problem was not directly addressed.
The scenario we're looking at today is the following. We have some stored data on disk, that we would like to plot using a Matplotlib animation, and save this animation as a video file. This is a reasonably common occurrence for researchers, but I had trouble finding tutorials online for this problem. Many of the tutorials generated their data via simulations on the fly, which didn't directly map to the case of recorded data.
There were two stumbling blocks I ran into, that had non-obvious solutions. First, Matplotlib's animation takes a function pointer to a user-defined function, for example def animate(i), but the animate function is then controlled by the iterator i. The second major stumbling block I hit, is that your animation function def animate(i): should return the data structures that need to be updated.
In this example, I have saved some data to a file in JSON format; each entry has a position and a velocity parameter. I read this file in line-by-line, and create a scrolling plot of the time series. I save this animated scrolling plot as a video file to disk, using ffmpeg and x264 for video encoding.
So there you go. A basic program that plots animation, and saves the resulting video to disk, using recorded data, stored in JSON on disk.
Edit: Just a quick addendum. I also had some trouble plotting animations of a grid of custom polygons, which could be useful for mapping, occupancy grids, or similar data. Here's a quick demo for how to generate animations of this sort:
The scenario we're looking at today is the following. We have some stored data on disk, that we would like to plot using a Matplotlib animation, and save this animation as a video file. This is a reasonably common occurrence for researchers, but I had trouble finding tutorials online for this problem. Many of the tutorials generated their data via simulations on the fly, which didn't directly map to the case of recorded data.
There were two stumbling blocks I ran into, that had non-obvious solutions. First, Matplotlib's animation takes a function pointer to a user-defined function, for example def animate(i), but the animate function is then controlled by the iterator i. The second major stumbling block I hit, is that your animation function def animate(i): should return the data structures that need to be updated.
In this example, I have saved some data to a file in JSON format; each entry has a position and a velocity parameter. I read this file in line-by-line, and create a scrolling plot of the time series. I save this animated scrolling plot as a video file to disk, using ffmpeg and x264 for video encoding.
import sys
import os
import json
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from time import time
import itertools
from matplotlib.path import Path
import matplotlib.patches as patches
import threading
def init():
plotline.set_data([], [])
dplotline.set_data([],[])
return plotline,dplotline,
def animate(i):
#ax.clear()
global frame_num, buffersize
if (frame_num%100==0):
print frame_num
line=f.readline()
jsondata=json.loads(line)
frame_num+=1
if "Position" in jsondata:
pos= jsondata["Position"]
if "Velocity" in jsondata:
vel=jsondata["Velocity"]
pos_buf.append(pos)
vel_buf.append(vel)
while len(pos_buf)>buffersize:
pos_buf.pop(0)
while len(vel_buf)>buffersize:
vel_buf.pop(0)
x=np.linspace(-len(pos_buf)/framerate,0,len(pos_buf))
dx=np.linspace(-len(vel_buf)/framerate,0,len(vel_buf))
plotline.set_data(x,headpose_buf)
dplotline.set_data(dx,headvel_buf)
return plotline, dplotline,
def folder_from_path(file):
split_path=file.split("/")
folder=split_path[0]
for i in range(1,len(split_path)-1):
folder+="/"+split_path[i]
return folder
#Setting up globals
file=""
frame_num=0
framerate=20.0
buffersize=5*20
vel_buf=[]
pos_buf=[]
fig, ax = plt.subplots()
ax.set_xlim(-5.0,2.0)
ax.set_ylim(-180,180)
my_dpi=96
fig.set_size_inches(640/my_dpi, 360/my_dpi)
plotline, =ax.plot([],[],lw=2,color='b')
dplotline, =ax.plot([],[], lw=2, color='r')
if __name__=='__main__':
if len(sys.argv)<2:
print "Usage:\nplot_data.py file"
exit()
#Parsing command-line arguments, checking the input file exists.
file= sys.argv[1]
print file
if (os.path.isfile(file)==False):
print "Problem with file"
exit()
folder=folder_from_path(file)
#Writing video to same folder
outfile=folder+"/data.avi"
print folder
#Getting number of data points from file. A little hackey, but I couldn't control animate() with the file open()
line_count=0
with open(file, 'r') as f:
for read_data in f:
line_count=line_count+1
print line_count
f=open(file,'r')
Writer = animation.writers['ffmpeg']
writer = Writer(fps=25, metadata=dict(artist='Sayanan'), extra_args=['-vcodec','libx264'])
anim = animation.FuncAnimation(fig, animate,init_func=init, frames=line_count-1,blit=True, interval=1, repeat=False)
anim.save(outfile,writer=writer)
f.close()
#plt.show()
So there you go. A basic program that plots animation, and saves the resulting video to disk, using recorded data, stored in JSON on disk.
Edit: Just a quick addendum. I also had some trouble plotting animations of a grid of custom polygons, which could be useful for mapping, occupancy grids, or similar data. Here's a quick demo for how to generate animations of this sort:
"Demo of a grid of PathPatch objects."
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from time import time
import itertools
from matplotlib.path import Path
import matplotlib.patches as patches
def animate(i):
prob=np.random.rand(np.size(yr)*np.size(xl))
ax.clear()
cells=[]
for i in range(0,len(P1)):
verts=[P1[i], P2[i], P3[i], P4[i], P1[i] ]
path = Path(verts, codes)
patch = patches.PathPatch(path, color=[1-prob[i],prob[i],0], lw=2)
cells.append(ax.add_patch(patch))
return cells
fig, ax = plt.subplots()
fig.set_size_inches(5,20)
width=3.5
height=5.0
xl=np.arange(-8.75,8.75,width)
yr=np.arange(-50.0,50.0,height)
ax.set_xlim(xl[0],xl[np.size(xl)-1]+width)
ax.set_ylim(yr[0],yr[np.size(yr)-1]+height)
cells=[]
print yr[10]
print np.size(yr)
print np.size(xl)
P1=list(itertools.product(xl,yr+height))
P2=list(itertools.product(xl+width, yr+height))
P3=list(itertools.product(xl+width, yr))
P4=list(itertools.product(xl,yr))
prob=np.random.rand(np.size(yr)*np.size(xl))
codes = [Path.MOVETO,
Path.LINETO,
Path.LINETO,
Path.LINETO,
Path.CLOSEPOLY,
]
for i in range(0,len(P1)):
verts=[P1[i], P2[i], P3[i], P4[i], P1[i] ]
path = Path(verts, codes)
patch = patches.PathPatch(path, color=[1-prob[i],prob[i],0], lw=2)
cells.append(ax.add_patch(patch))
anim = animation.FuncAnimation(fig, animate, blit=True, save_count=0,interval=10)
plt.show()
Friday, September 26, 2014
Matplotlib Animation Save with FFmpeg Freezes After N Frames
Matplotlib is a go-to plotting tool in Python, which has a lot of useful features, like compatibility with the Scipy/Numpy stack. Sometimes it's useful to visualize time-series data temporally.
One very useful feature that Matplotlib has is the animations module, which allows you to animate plots with changing data [over time, for example], and save the data as a video file using FFmpeg. There's a great tutorial for Matplotlib animations here.
My only complaint about the Matplotlib animations, is that the documentation and examples are not super-comprehensive. I might create a follow-up post with some sample programs, to add to the documented examples floating around the interwebs.
In any case, once I got the animations working, I wanted to save them as a video for later on-demand viewing. I set up an animation writer with ffmpeg, x264, and let it run. Each time I ran the script, and the video saving would freeze after 820 frames.
It took a fair amount of online searching to find the answer here. It turns out that the stock Ubuntu/Debian FFmpeg and LibAV have branched apart at some point. You can obtain the "real" FFmpeg here. Once you install this, the Matplotlib animations save videos just fine.
One very useful feature that Matplotlib has is the animations module, which allows you to animate plots with changing data [over time, for example], and save the data as a video file using FFmpeg. There's a great tutorial for Matplotlib animations here.
My only complaint about the Matplotlib animations, is that the documentation and examples are not super-comprehensive. I might create a follow-up post with some sample programs, to add to the documented examples floating around the interwebs.
In any case, once I got the animations working, I wanted to save them as a video for later on-demand viewing. I set up an animation writer with ffmpeg, x264, and let it run. Each time I ran the script, and the video saving would freeze after 820 frames.
It took a fair amount of online searching to find the answer here. It turns out that the stock Ubuntu/Debian FFmpeg and LibAV have branched apart at some point. You can obtain the "real" FFmpeg here. Once you install this, the Matplotlib animations save videos just fine.
Sunday, September 14, 2014
USB Serial COM Ports and Python
I was working with a simple device that provides data via USB Serial COM. For whatever reason, the C++ library I was using to read from the device was not working consistently on different machines.
USB Serial COM is akin to socket programming. The routines are somewhat platform-dependent, and today's developer doesn't usually care about the details. Just give me an abstraction that lets me communicate!
Then I realized that Python has PySerial. Using this library, I was easily able to communicate with the device, and send it via localhost socket to my C++ program. Done and done.
Check out the super simple source code:
Python for the win.
USB Serial COM is akin to socket programming. The routines are somewhat platform-dependent, and today's developer doesn't usually care about the details. Just give me an abstraction that lets me communicate!
Then I realized that Python has PySerial. Using this library, I was easily able to communicate with the device, and send it via localhost socket to my C++ program. Done and done.
Check out the super simple source code:
import serial
import socket
IP="127.0.0.1"
PORT=3001
sock=socket.socket(socket.AF_INET,socket.SOCK_DGRAM) #Sending data to localhost via UDP
ser= serial.Serial(2,timeout=2) #COM3 is port number 2.
print ser.name
line=''
while (True):
line=ser.readline()
print line
sock.sendto(line,(IP,PORT))
Python for the win.
Sunday, August 3, 2014
Karate Interpretations: Sport, Fighting, Self-defense
Over the past year, I've gotten back into Shotokan karate. I grew up doing karate, and completed my blackbelt exam when I was 15. There was a great sense of community with my dojo growing up, in Randallstown, Maryland. The training there was pretty intense, and not geared towards tournaments.
Over the years, I've been on and off with it. Practical considerations, like time, or distance to the neareset dojo, obviated my formal training when I was in San Diego. I used to train by myself.
It's great for fitness, teaches you about bio-mechanics and anatomy, and it's solid for self-defense. The full system consists of various punches, strikes, kicks, blocks, joint locks, grappling, throws, and take-downs. The traditional style are tailor made for close-range and medium-range hand-to-hand combat.
A problematic aspect arises when a dojo trains with too much emphasis on tournament competition. Tournaments have an artificial set of rules, that really favor high kicks, and fast punches to the body. These techniques alone are fairly impractical for self-defense.
If a dojo trains with too much emphasis on winning tournaments, it tends to ignore the more practical, self-defense oriented styles and techniques. Common moves like arm-bars, wrist-locks, and throws tend to be completely ignored in such a dojo. This is especially problematic for students, who think they are learning how to defend themselves, but are actually learning how to score points in tournament-style sparring.
There are some voices of reason out there, who train traditional karate, and include the grappling and throwing. A couple are Bruce Clayton, and Iain Abernathy. These two have produced books and dvds on the subject, the historical evolution of modern karate, and even lead practical self-defense karate clinics.
No single self-defense system is comprehensive, and so it's good to keep your eyes open. When I watch elite boxers, I see a lot of the same technique and form. When I watch brazilian jiu-jutsu guys, I see a lot of familiar grappling, but enhanced and taken to the ground-fighting scenario. Martial arts are enjoyable for sure.
Over the years, I've been on and off with it. Practical considerations, like time, or distance to the neareset dojo, obviated my formal training when I was in San Diego. I used to train by myself.
It's great for fitness, teaches you about bio-mechanics and anatomy, and it's solid for self-defense. The full system consists of various punches, strikes, kicks, blocks, joint locks, grappling, throws, and take-downs. The traditional style are tailor made for close-range and medium-range hand-to-hand combat.
A problematic aspect arises when a dojo trains with too much emphasis on tournament competition. Tournaments have an artificial set of rules, that really favor high kicks, and fast punches to the body. These techniques alone are fairly impractical for self-defense.
If a dojo trains with too much emphasis on winning tournaments, it tends to ignore the more practical, self-defense oriented styles and techniques. Common moves like arm-bars, wrist-locks, and throws tend to be completely ignored in such a dojo. This is especially problematic for students, who think they are learning how to defend themselves, but are actually learning how to score points in tournament-style sparring.
There are some voices of reason out there, who train traditional karate, and include the grappling and throwing. A couple are Bruce Clayton, and Iain Abernathy. These two have produced books and dvds on the subject, the historical evolution of modern karate, and even lead practical self-defense karate clinics.
No single self-defense system is comprehensive, and so it's good to keep your eyes open. When I watch elite boxers, I see a lot of the same technique and form. When I watch brazilian jiu-jutsu guys, I see a lot of familiar grappling, but enhanced and taken to the ground-fighting scenario. Martial arts are enjoyable for sure.
Subscribe to:
Posts (Atom)