Add 3.3 challenge

1 files changed, 96 insertions, 0 deletions

diff --git a/3.3.py b/3.3.py
new file mode 100644
index 0000000..663d6f1
--- /dev/null
+++ b/3.3.py
@@ -0,0 +1,96 @@
+#!/usr/bin/python2
+
+# Find the Access Codes
+# =====================
+
+# In order to destroy Commander Lambda's LAMBCHOP doomsday device, you'll need
+# access to it. But the only door leading to the LAMBCHOP chamber is secured
+# with a unique lock system whose number of passcodes changes daily. Commander
+# Lambda gets a report every day that includes the locks' access codes, but
+# only she knows how to figure out which of several lists contains the access
+# codes. You need to find a way to determine which list contains the access
+# codes once you're ready to go in.
+
+# Fortunately, now that you're Commander Lambda's personal assistant, she's
+# confided to you that she made all the access codes "lucky triples" in order
+# to help her better find them in the lists. A "lucky triple" is a tuple (x, y,
+# z) where x divides y and y divides z, such as (1, 2, 4). With that
+# information, you can figure out which list contains the number of access
+# codes that matches the number of locks on the door when you're ready to go in
+# (for example, if there's 5 passcodes, you'd need to find a list with 5 "lucky
+# triple" access codes).
+
+# Write a function solution(l) that takes a list of positive integers l and
+# counts the number of "lucky triples" of (li, lj, lk) where the list indices
+# meet the requirement i < j < k. The length of l is between 2 and 2000
+# inclusive. The elements of l are between 1 and 999999 inclusive. The answer
+# fits within a signed 32-bit integer. Some of the lists are purposely
+# generated without any access codes to throw off spies, so if no triples are
+# found, return 0.
+
+# For example, [1, 2, 3, 4, 5, 6] has the triples: [1, 2, 4], [1, 2, 6], [1, 3,
+# 6], making the answer 3 total.
+
+
+# Test cases
+# ==========
+# Your code should pass the following test cases.
+# Note that it may also be run against hidden test cases not shown here.
+
+# Input:
+# solution.solution([1, 2, 3, 4, 5, 6])
+# Output:
+#     3
+
+# Input:
+# solution.solution([1, 1, 1])
+# Output:
+#     1
+    
+## O(n^2)
+def solution(l):
+    c = [0] * len(l)
+    count = 0
+    for i in range(0, len(l)):
+        for j in range(0, i):
+            if l[i] % l[j] == 0:
+                c[i] = c[i] + 1
+                count = count + c[j]
+    return count
+
+## O(n^3)
+def solution2(l):
+    c = 0
+    while len(l) > 2:
+        t = l[1:]
+        for id,i in enumerate(t):
+            if i % l[0] == 0:
+                for j in t[(id + 1):]:
+                    if j % i == 0:
+                        c += 1
+        l = l[1:]
+    return c
+
+## Way too much memory, it's not even funny
+## python is supposed to do list comprehension in a good way, lol
+def solution3(l):
+    return len([(i, j, k)
+                for id,i in enumerate(l)
+                for jd,j in enumerate(l[(id+1):])
+                for k in l[(id+jd+2):]
+                if j%i==0 and k%j==0])
+
+def solve(l):
+    print(l)
+    print(solution(l))
+
+solve([1, 2, 3, 3, 5, 2])
+solve([1, 2, 3, 4, 5, 6])
+solve([1, 2, 3, 3, 2, 1])
+solve([1 for x in xrange(2000)])
+solve([1, 1, 1])
+solve([])
+solve([2])
+solve([2, 5])
+solve([1, 5, 6])
+solve([1, 999999, 2])