{"id":1107,"date":"2011-12-27T22:22:41","date_gmt":"2011-12-28T05:22:41","guid":{"rendered":"http:\/\/thesmithfam.org\/blog\/?p=1107"},"modified":"2019-08-12T07:15:07","modified_gmt":"2019-08-12T13:15:07","slug":"fun-python-solution-to-euler-problem-79","status":"publish","type":"post","link":"https:\/\/thesmithfam.org\/blog\/2011\/12\/27\/fun-python-solution-to-euler-problem-79\/","title":{"rendered":"Fun Python Solution to Euler Problem 79"},"content":{"rendered":"

Nothing says Merry Christmas like Project Euler.<\/p>\n

Here’s a nifty solution to Problem 79<\/a> that uses Python and Graphviz.<\/p>\n

The problem is to identify a user’s password given a bunch of successful logins (taken from some kind of nefarious keylogger–those crafty devils). The \u00c3\u00a7atch is that each login is actually a subset<\/b> of the actual password. Of course, they give you a sample of 50 successful logins<\/a>.<\/p>\n

So I decided to whip up some Python code to ingest each login and store a list of digit precedence. Then, the code prints out a Dot file<\/a> which we turn into an image using the “dot” command. I ran this on Mac OS X, but it should work just fine on any Linux box (hint: install the “graphviz” package).<\/p>\n

Here’s the Python code:<\/p>\n

problem79.py:<\/b><\/p>\n

\r\ndigit_precendence = dict()\r\n\r\nfor line in [line.strip() for line in open(".\/keylog.txt")]:\r\n    for index, char in enumerate(line):\r\n        digits = digit_precendence.setdefault(int(char), set())\r\n        if index < len(line)-1:\r\n            digits.add(int(line[index+1]))\r\n\r\nprint "digraph problem79 {"\r\nfor (digit, subsequent_digits) in digit_precendence.iteritems():\r\n    for subsequent_digit in subsequent_digits:\r\n        print "   %d -> %d;" % (digit, subsequent_digit)\r\nprint "}"\r\n<\/pre>\n
Save that as problem79.py<\/b>, download keylog.txt<\/b> into the same folder, and run the program like this:<\/p>\n
python problem79.py | dot -Tpng > problem79.png<\/pre>\n
Then view problem79.png<\/b>, and voila! Graphviz just put the answer right in front of your nose: 73162890<\/b>.<\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Nothing says Merry Christmas like Project Euler. Here’s a nifty solution to Problem 79 that uses Python and Graphviz. The problem is to identify a user’s password given a bunch of successful logins (taken from some kind of nefarious keylogger–those crafty devils). The \u00c3\u00a7atch is that each login is actually a subset of the actual […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-1107","post","type-post","status-publish","format-standard","hentry","category-code-and-cruft"],"_links":{"self":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/1107","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/comments?post=1107"}],"version-history":[{"count":21,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/1107\/revisions"}],"predecessor-version":[{"id":1508,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/1107\/revisions\/1508"}],"wp:attachment":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/media?parent=1107"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/categories?post=1107"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/tags?post=1107"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}