brett.olsen
BAN USERThis sounds immediately like a recursive problem, so let's think about the base cases. First off, if either string is empty, then there are no possible matches. If the two strings are equal, then there's only one match. If the strings have the same length but aren't equal, there's no match. If they're of different lengths, then we must be looking for all the matches of the shorter string in the longer string. So let's call the shorter string the search string and the longer string the target string.
What's the recursion? Well, if the first characters of both strings don't match, then we need to look for the full search string starting at the second character of the target string. In other words, given "act" and "react", we can recurse to ("act", "eact") and then to ("act", "act"). If the first characters do match, then we have two options: match the first character and recurse with both strings shortened by the matched character, or don't match the first character, hoping to find another match later. E.g, given ("act", "acting") we recurse to both ("ct", "cting") and ("act", "cting"). If we ever use up the last character in the search string, we add a match. Let's write up this recursive solution:
def match(search, target):
if not search or not target:
return 0
if search == target:
return 1
if len(search) == len(target):
return 0
if len(search) > len(target):
search, target = target, search
if search[0] == target[0]:
if len(search) == 1:
return 1 + match(search, target[1:])
else:
return match(search[1:], target[1:]) + match(search, target[1:])
else:
return match(search, target[1:])
This gets us the right answer but is unfortunately rather slow on long strings. Why? Because the recursive stack can get very deep - any time there's a character match, we're splitting into two recursive calls, giving us O(N^2) worst case behavior. However, we'll note that there are only M possible search strings and N possible target strings. Our recursive calls must be repeatedly evaluating the same subproblems. That means we can use a dynamic programming approach - we'll store the results of previous calls by allocating an array.
import numpy as np
def match(search, target):
if len(search) > len(target):
search, target = target, search
m, n = len(search), len(target)
#Some base cases
if not search or not target:
return 0
if search == target:
return 1
if m == n:
return 0
#Allocate the array
table = np.zeros((m, n), dtype=int)
#Fill in the bottom row (matching the last character of the search string)
i = m - 1
for j in range(n)[::-1]:
if j < n - 1:
table[i,j] = table[i,j+1]
if search[i] == target[j]:
table[i,j] += 1
#Fill in the rest of the table
for i in range(m - 1)[::-1]:
for j in range(n - 1)[::-1]:
if search[i] == target[j]:
table[i,j] = table[i+1,j+1] + table[i,j+1]
else:
table[i,j] = table[i,j+1]
#Return the final value
return table[0,0]
Now this runs quite fast --- it takes only O(MN) time with the nested loop. However, it also takes O(MN) space to store the table. But we don't actually need the whole table! At each point, we only need the next column over. So we can reduce this to O(M) space by shrinking the table:
import numpy as np
def match(search, target):
if len(search) > len(target):
search, target = target, search
m, n = len(search), len(target)
#Some base cases
if not search or not target:
return 0
if search == target:
return 1
if m == n:
return 0
#Allocate the array
table = np.zeros((m, 2), dtype=int)
#Fill in the bottom right element (match the last two characters)
if search[-1] == target[-1]:
table[-1, 0] = 1 #First column because it will be shifted over in the loop
#Iterate through all the columns
for j in range(n - 1)[::-1]:
#Copy the left column over to the right
table[:,1] = table[:,0]
#Bottom row
if search[m - 1] == target[j]:
table[m - 1, 0] += 1
#Remaining rows
for i in range(m - 1)[::-1]:
if search[i] == target[j]:
table[i,0] = table[i+1,1] + table[i,1]
else:
table[i,0] = table[i,1]
#Return the final value
return table[0,0]
The other big benefit of this approach is that depending on how we implement the "ready" data structure, we can control *which* valid task ordering we pick. We might prefer to have certain tasks finished earlier, while other tasks might not be as important. If we implement the "ready" structure with a priority queue, we can guarantee that the top priority task will get run as soon as possible.
- brett.olsen March 11, 2015OK, I'm going to write this in Python for simplicity with this task interface:
class Task(object):
def run():
pass
def get_dependencies():
pass
So each task has a run method that does something and a get_dependencies method that gives us a list of tasks which need to be run before this task. We're given a list of tasks and asked to run each task only once but respecting the dependencies of each task.
The initial thing to try would be to simply loop through our tasks, run all the dependent tasks for each task, and then run that task. However, we don't want to run any task more than once, so we need to keep track of which tasks we've already run and not run them (or their dependencies) again. We'll use a set (hashmap) to keep track of this - if the task is already in the set, we've run it and we won't need to worry about it.
def run_tasks(tasks):
visited = set()
def sub_run(tasks):
for task in tasks:
if task in visited:
continue
sub_run(task.get_dependencies())
task.run()
visited.add(task)
sub_run(tasks)
This approach works pretty well - in fact, we're only going through each task once, and through each dependency list once (the first time we see it), so the runtime is O(V+E), where V is the number of tasks and E the number of dependencies. However, it's got a big problem. This function works fine as long as the input is good - but if we give it a circular dependency, it'll loop forever rather than failing gracefully. Even if we caught the loop later, we may have already run a number of tasks before hitting the cycle, and we probably want to fail first, before we do anything. So how to solve this?
Well, this is a standard graph problem on directed, acyclic graphs - it's called topological sorting. Before we run any of the tasks, we'll come up with a topological sort of the tasks, or an ordering of the tasks that respects all the dependencies. If we can't come up with a valid ordering, that means there's a cycle in the graph and we'll fail gracefully there. Then once we have the ordering, we can simply run them all in that order.
Here's the method. We'll need several supplementary data structures. First, we'll make a dictionary mapping tasks to their order in the input list so we can quickly look them up. Then we'll make a list that stores a count of how many dependencies (or incoming edges, in graph-speak) each task has. We'll also create a list of lists where each list stores all the tasks that are depending on each task (or an adjacency list, again in graph-speak). Finally, any tasks with no dependencies will get added to a ready list, and we'll initialize an empty ordering list that we'll fill up as we go.
Then we do this: first, pick a ready task from the ready list. Put it in the ordering list as the next task in the order, and then go through each task that is depending on this task and reduce its dependency count by 1. If this reduces it to zero, then that task is ready and we push it into the ready list. Repeat until the ready list is empty. If our final ordering list contains all of the tasks, then we've got a valid order and we'll just go through and run all the tasks in that order. If it doesn't, then the remaining tasks must have a cycle, and we can raise an exception or however we want to deal with the problem. Here's the code:
def run_tasks(tasks):
#Setup
ids = {}
for i, task in enumerate(tasks):
ids[task] = i
incoming = []
adj_list = [[] for task in tasks]
ready = []
ordering = []
for task in tasks:
deps = task.get_dependencies()
incoming.append(len(deps))
for dep in deps:
adj_list[ids[dep]].append(ids[task])
if len(deps) == 0:
ready.append(ids[task])
#Do the sort
while ready:
next_task = ready.pop()
ordering.append(next_task)
for k in adj_list[next_task]:
incoming[k] -= 1
if incoming[k] == 0:
ready.append(k)
#Run the tasks
if len(ordering) < len(tasks):
print 'Cycle Detected!'
else:
for k in ordering:
tasks[k].run()
Oh, nice job! I didn't work out the optimal way to split up cards for sending, I just crammed as many as I could into 32 bits repeatedly, which got me to 228. Looks like you can shave off that extra bit if you're more careful!
- brett.olsen March 03, 2015First off, let's choose a canonical ordering for the deck of cards known by both sender and receiver (for example, order first by suit hearts, spades, diamonds, clubs and then 2-10, J, Q, K, A within each suit) and then replace the standard symbols for each card with an integer between 1 and 52 denoting its order in this canonical order.
Theoretical Minimum
Our sequence or shuffle is an ordering of the integers between 1 and 52. There are 52! permutations of this sequence, and so the minimum number of bits required to send it is simply lg_2(52!), or sum_{n=1}^{52} lg_2(n), which is 225.58, meaning we necessarily need at least 226 bits to send our shuffle.
What's the best approach to do this?
Simple Approach
The simple approach would be to notice that we're trying to send 52 numbers between 1 and 52. We need a 6 bit number (2^6 = 64) to represent an arbitrary number between 1 and 52, so we can use 52 6 bit numbers, for a total of 312 bits. This is OK - compared to our theoretical minimum of 226, we're only using about 40% more space plus there's minimal coding/decoding involved.
Better Approach
We can notice that we don't always have 52 different options for each card - once we've sent a card, we can't send it again. So the last card in the shuffle, for example, will always be determined. It will be the card remaining after the first 51 cards we send. The second to last card has only 2 options, so we only need 1 bit to send that. So for each card we send the number of the card out of the ordered cards that we haven't already sent. If we have, for example, cards 5 and 42 remaining and we want to send card 5, we send the number 1. This gets us sum_{n=1}^{52} ceil(lg_2(n)) - it takes 6 bits for the first 20 cards (52 possibilities to 33 possibilities), 5 bits for the next 16 card (32 possibilities to 17 possibilities), etc. This gets us to a total of 249 bits. This is much better, but still 10% more than the theoretical minimum. Can we get closer?
Best Approach
Suppose we want to send three numbers x, y, z which we know will lie between 1 and 10, 11, 9, respectively. Each of x, y, z would take 4 bits (2^4 = 16) to send independently for a total of 12 bits. There are 990 possible combinations, so the theoretical minimum number of bits to send this triplet is lg_2(990)=9.95, or 10 bits.
Here's how to map sets of x,y,z to a unique number C for each combination. Let's treat C as a number with multiple bases - the lowest order digit will be of base 9, the next lowest of base 11, and the high order bit of base 10. Then we can use each digit to hold one of x, y, and z. We can calculate C as z + z_{max} (y + y_{max} (x)). Then we send C to our receiver in binary as a 10 bit number, and they decode it. The low order digit is z, which can be extracted by z = C % z_{max}. Then they shift C down a digit, so C_{adj} = (C - z) / z_{max}. And we repeat to pull off y, y = C_{adj} % y_{max}. And shift C down again to extract x, x = (C_adj - y) / y_{max}. Done! We've successfully sent our numbers in the theoretical minimum number of bits.
Sample Python encoding/decoding functions w/ an example:
def encode(nums, maxvals):
C = 0
for i in range(len(nums)):
C *= maxvals[i]
C += nums[i] - 1 #Numbers between 1 and maxval inclusive
return C
def decode(C, maxvals):
nums = []
for i in range(len(maxvals))[::-1]:
nums.append(C % maxvals[i] + 1) #Adding 1 to get between 1 and maxval
C = (C - nums[-1] + 1) // maxvals[i]
return nums[::-1]
nums = [9, 9, 9]
maxvals = [10, 11, 9]
C = encode(nums, maxvals)
print C
872
print decode(C, maxvals)
[9, 9, 9]
We can use the same trick with our card problem to send in the theoretical minimum --- in theory. In practice, this requires lots of arithmetic on very large integers (up to 52!) and so we might want to restrict ourself to compositing Cs to be less than, say, 32 bits. Even with this restriction, we can get to as low as 228 bits - less than 1% more than the minimum.
Clever Approach
The theoretical minimum we calculated only applies if all shuffles are equally probable. In the limit, my shuffling algorithm might have a bug in it where it doesn't shuffle at all, in which case 0 bits of data is sufficient to transmit my current shuffle. More practically, if I'm using a pseudo-random number generator to shuffle my deck, the number of distinct possible shuffles is limited by both the period of my random number generator and the number of possible seeds I'm using to shuffle with. If my PRNG has a period of 2^32, then there's only 2^32 possible shuffles - and if the receiver has a copy of my PRNG, they can generate the same shuffle if I send them my 32-bit seed.
Very simple Python generator:
- brett.olsen April 23, 2015