Tag Archives: technology

Python Partition Calculator

I had been looking to do a little bit more hobby-coding, and I came across this simple math problem which can be solved with a cool recursive Python script.

A partition is a concept in number theory where a positive integer is written as a sum. For example, the only partition of 1 is (1). 2 has (2) and (1+1). 3 has (1+2), (1+1+1), and (3), and so on. Because it’s a sum, order is not important.

The problem of figuring out partitions is not difficult, but it is time-consuming and repetitive once you go beyond calculating all partitions for 4 or 5. Something that makes it a good candidate for automation. It also can be done with some recursion.

The first thing that needs to be done is a recursive call to calculate all the combinations of numbers that would form a partition. I’m going to return a list of lists, where each sublist is a partition. The obvious part to take care of first is the base case:

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])

Next, let’s take a look at when the partition_goal is some number larger than one. The first thing we’d need is to add a list consisting of just that number:

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])

Now we need to loop over all the cases where the lists are more complicated. Let’s take 3, because it’s pretty simple. Once we’ve added the single item list [3] in the step above, we need to add the integer 1 to all lists that add up to 3 – 1, the integer 2 to all lists that add up to 3 – 2 and so on.

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])
        for i in range(1,partition_goal):
            for j in recursive_partition(partition_goal - i):
                j.append(i)
                return_list.append(j)
    return return_list

So for each of the numbers in the i range, we are adding that number to every list we can create recursively (j) where that list sums to partition_goal – i. Lastly, we need to call our recursive method, and then remove all the sublists which are identical when unordered ([1,1,2] and [1,2,1] are just one partition of 4). We do this using the Counter module.

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])
        for i in range(1,partition_goal):
            for j in recursive_partition(partition_goal - i):
                j.append(i)
                return_list.append(j)
    return return_list

list_of_lists = recursive_partition(n)

counted = Counter(tuple(sorted(entry)) for entry in list_of_lists)

print(list(counted.keys()))

The variable counted actually gets a dictionary Python object, so I turned it into a list in the print statement. The keys of a Counter are tuples, so the end result is a list of tuples where every tuple is a partition. Lastly let’s make some interface changes so we can take command line arguments or ask the user for input.

from collections import Counter
import sys

n = 1
# partition goal
if len(sys.argv) > 1:
    n = sys.argv[1]
else:
    n = int(input("What number do you want the partitions for?"))

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])
        for i in range(1,partition_goal):
            for j in recursive_partition(partition_goal - i):
                j.append(i)
                return_list.append(j)
    return return_list

list_of_lists = recursive_partition(n)

counted = Counter(tuple(sorted(entry)) for entry in list_of_lists)

print(list(counted.keys()))

And remember this is Python 3 notation. You can find this little project on Github here.

2016 Predictions

How confident should we be? People tend to be overconfident.  One way to figure out if our confidence levels are correct is to test our calibration levels by making predictions and seeing how many of them pan out. Inspired by Slate Star Codex’s predictions, here are my predictions and accompanying confidence levels. For the sake of convenience I will choose from confidence levels of 50%, 60%, 70%, 80%, 90%, 95% or 99%. All predictions are by December 31, 2016 unless noted otherwise.

World Events

  1. Liberland will be recognized by <5 UN members: 99%
  2. Free State Project to reach goal of 20,000 people in 2016: 50%
  3. ISIS to still exist: 80%
  4. ISIS to kill < 100 Americans 2016: 80%
  5. US will not get involved in any new major war with death toll of > 100 US soldiers: 80%
  6. No terrorist attack in the USA will kill > 100 people: 80%
  7. Donald Trump will not be Republican Nominee: 80%
  8. Hillary Clinton to be Democratic nominee: 90%
  9. Republicans to hold Senate: 60%
  10. Republicans to hold House: 80%
  11. Republicans to win Presidential Election: 50%
  12. I will vote for the Libertarian Presidential Candidate: 70%
  13. S&P 500 level end of year < 2500: 70%
  14. Unemployment rate December 2016 < 6% : 70%
  15. WTI Crude Oil price < $50 : 80%
  16. Price of Bitcoin > $500:  60%
  17. Price of Bitcoin < $1000: 80%
  18. Sentient General AI will not be created this year: 99%
  19. Self-driving cars will not be available this year to purchase / legally operate for < $100k: 99%
  20. I will not be able to rent trips on self-driving cars from Uber/ Lyft: 90%
  21. Humans will not land on moon by end of 2016: 95%
  22. Edward Snowden will not be pardoned by end of Obama Administration: 80%

Personal

  1. Employed in current job:  90%
  2. I will have less than 300 Twitter followers: 60%
  3. I will have authored > 12 more blog posts by June 30, 2016:  50%
  4. michaelelgart.com to have >4,000 page loads 2016: 50%
  5. These predictions are underconfident: 70%

Sports

  1. Miami Heat make playoffs 2016:  80%
  2. Miami Heat will not make Eastern Conference Finals:  90%
  3. Duke basketball wins 1 game or more against UNC: 60%
  4. Duke basketball makes it to Round of 32 in NCAA Tournament: 70%
  5. Duke basketball does not make Final Four: 90%
  6. USA wins Olympic gold medal in basketball: 70%
  7. Kevin Durant will not be highest paid NBA player during 2016-17 season: 70%

New Horizons, Prediction Markets, and other Links

This morning, the New Horizons probe had its closest approach to Pluto.  It’s pretty cool that human ingenuity has gotten to the point where it’s possible to launch a rocket, and then 10 years later get it within a couple thousand miles of a (dwarf) planet orbiting ~6 billion kilometers away from us. But keeping with this blog’s theme, this doesn’t seem very libertarian! Isn’t this a big waste of money and resources for the government to be sending probes to Pluto?  Well, yes, obviously.

 - Public Domain Photo from NASA

This picture of Pluto cost $650M

Continue reading

Homeland

This week I finished reading Homeland by Cory Doctorowauthor and co-editor of Boing Boing.  My immediate reason for reading it was an assignment from my CS seminar class about the internet and technology in society, but I had been meaning to read Little Brother for some time.  Homeland is the sequel to Little Brother, and while I was not familiar with the storyline, the book is a pretty easy read so I jumped right in. Doctorow wrote both Little Brother and Homeland for young adults to be both accessible and educational about technology and civil liberties.  Doctorow is somewhat of an anti-copyright activist and thus the books, like all of his work can be obtained for free from his website, but if you enjoy them, I urge you to buy them as well and support his work.

Homeland undertakes a great deal in a small space and is fairly successful.  Doctorow pursues various themes in his book, while seeking to explain a complex and technical world to an unfamiliar audience, all of which occurs only for the backdrop of a riveting storyline that must keep the reader’s attention.  Having not read the previous story of which Homeland is a sequel to, many of the events and background was not familiar to me, yet it was consistently well-explained. Furthermore, the intense technical nature of many of the plot devices were adequately covered so that the audience not only knew what was occurring, but inevitably learned a great deal about privacy, cryptography, and information security in the process. This  translated into pushing many of the themes of the book, notably that technology can be a force for both good and evil, and if prying eyes want to know what you’re doing, you can’t always stop them.  But Homeland also gives some insight into the hacker culture and catalogs many of the tools that government dissidents can use to hide their activities like secure linux distros, Tor, and VPNs.  And it does all this while maintaining a fascinating plot and interesting characters.

However, it is isn’t perfect. Doctorow’s politics are not particularly subtle, and with the exception of a few anonymous hackers, the vast majority of the characters are pretty starkly divided into “good guy hacktivists” and “bad guy enforcers”.  In some sense, this is due to the limitations of the genre with Homeland aimed at the young adult audience where the appeal of the fighting-the-man scenarios is an excellent plot device.  But it also detracts from the overall message;Homeland paints an incredible story of why civil liberties must be so carefully guarded and how destructive life can become when they are gone–but the story itself might feel too forced to fit that message.

Of course, I would emphasize that while some of the technology itself might not be realistic (although in a couple years that won’t be true anymore), almost every important point in the book has already happened. With the passage of the 2012 NDAAauthorizing the president to detain indefinitely any US citizen suspected of being involved in terrorist activities, the use of water boarding by the US government, and the well-documented use of defense contractors, much of the more unbelievable actions the government took in Homeland have already occurred in real life. Thus, Doctorow’s book offers a sobering outlook on the technologically advanced world we live in, and a powerful message about where the abuses of unbridled authority can lead.  I would highly recommend it to anyone with an interest in cyber security, technology and politics, or anyone who simply wants to know more about the dark world of hackers, crypto, and anonymity.

Bitcoins

Bitcoins are a relatively new form of currency incorporating aspects of cryptology, networking, and economics. For a more in depth understanding, check out this link off of Hacker News.

Bitcoins offer a mix of unique options. Their use is secured like other monetary transactions, but they’re also anonymous, as each bitcoin transaction is linked to unique public bitcoin key.  Furthermore, bitcoins are governed by an open source algorithm, not a government, meaning that they cannot be arbitrarily created or destroyed, affecting the economy due to policy initiatives.

It can be difficult for people to accept that something that has no intrinsic value can work as a currency. While there are lots of fiat currencies, those currencies are often enforced by a government (Federal Reserve Notes must be accepted by law in the United States).  But if enough places begin to accept bitcoins, and many websites are, their value will continue to grow.

The real question right now is whether the meteoric rise in bitcoin value is part of a bubble or not.  Of course, since the value of any currency is based on what people’s perception of the currency is, as well as what you can buy with it, calling it a bubble is pretty easy; bitcoins’ value is of course artificial, there’s no denying that.  The beginning of the rise in bitcoins’ value occurred when more websites started to accept bitcoins as payment. Whether the improved liquidity of bitcoins warrants their value at close to $70/coin is a more difficult question. I know I’m not buying any bitcoins right now, but knowing whether speculators will move out of the bitcoin space in the near future is almost impossible to tell.

Still, this is a very interesting topic, and if you want to learn more, I would check out the bitcoin subreddit as well as bitcoin.org.