I am back from Singapore and it was a decent trip. I will be putting up pictures I clicked there soon. But first, while in S’pore, I implemented mergesort in Python.
Mergesort works by diving the given list down to groups of two, sorting them and merging these groups to get the sorted list.
So, the script that divides these lists into groups of two should be pretty straightforward:
”‘Divide given numbers into groups of two’”
lists = []
i = 0
while i < len(num_list):
lists.append(num_list[i:i+2])
i += 2
return lists
def sortTwos(num_list):
”‘sort the lists returned by makeSubLists()’”
try:
if num_list[0] >= num_list[1]:
num_list.reverse()
except IndexError:
pass
return num_list
Next, we need to somehow merge these sorted lists back. I decided to take a recursive approach:
- Suppose that two of the lists we’re merging are [x1, x2] and [y1, y2].
- If our final list can be called “final_list”, we add x1 or y1 whichever is the smaller value. Remove x1 or y1 from the list.
- We now have [x2] and [y1, y2] (I’m assuming that x1 is smaller). Repeat step 2 and keep doing it till one of the lists is reduced to [], the remaining part of the other list can be appended at the end of final_list because it is sorted already.
”‘recursively merge the two given lists’”
if len(list1) == 0:
merged_list += list2
return merged_list
elif len(list2) == 0:
merged_list += list1
return merged_list
else:
if list1[0] <= list2[0]:
merged_list.append(list1[0])
list1.pop(0)
else:
merged_list.append(list2[0])
list2.pop(0)
return recurMerge(list1, list2, merged_list)
The next snippet recursively supplies lists to recurMerge() till a single list containing the sorted numbers is obtained.
”‘supply lists to recurMerge and recursively sort’”
final_list = []
if len(singletons) == 1:
return singletons[0]
else:
i = 0
while i < len(singletons):
final_list.append(recurMerge(singletons[i], singletons[i+1], []))
i += 2
singletons = final_list
return merge(singletons)
You can download this mergesort implementation here.
Next comes the Collatz conjecture which goes something like this:
- Pick a number n.
- If n is even, n = n / 2.
- If n is odd, n = 3n + 1
- Go to step 2.
Do that with any n and you will always end up at 1. So, if n equals 13, the numbers resulting from applying the steps of the conjecture are:
- 40
- 20
- 10
- 5
- 16
- 8
- 4
- 2
- 1
See.
Project Euler has a question based on the Collatz Conjecture which asks you find that number under 1 million which takes the longest number of steps to get to 1.
Here is the code to solve that:
def collatzDepth(number):
collatz_hash = {}
depth = 0
while number > 1:
if number % 2 == 0:
number = number / 2
else:
number = 3 * number + 1
depth += 1
return depth
for i in xrange(1000000):
collatz_dict[collatzDepth(i)] = i
def findMaxDepth(collatz_dict):
val = max(collatz_dict.keys())
return val, collatz_dict[val]
print findMaxDepth(collatz_dict)
In 10 days, I will be at Purdue…. wow…. I just can’t believe how time flew and how I recovered from the MIT admissions result…. I guess I’ve moved on…..
About Collatz…can you find a number (any number, not necessarily the smallest) that has EXACTLY 1000000 steps?
I want to sort kaprekar nunber using if else statement and it is a problem