Merge pull request #7101 from ealvar3z/challenge-191

pwc191 Go and Python solutions

7 files changed, 158 insertions, 0 deletions

diff --git a/challenge-191/ealvar3z/blog.txt b/challenge-191/ealvar3z/blog.txt
new file mode 100644
index 0000000000..b3e3a7bcb4
--- /dev/null
+++ b/challenge-191/ealvar3z/blog.txt
@@ -0,0 +1 @@
+https://alvar3z.com/posts/reduce--backtrack/
diff --git a/challenge-191/ealvar3z/go/ch-1.go b/challenge-191/ealvar3z/go/ch-1.go
new file mode 100644
index 0000000000..e26e958071
--- /dev/null
+++ b/challenge-191/ealvar3z/go/ch-1.go
@@ -0,0 +1,19 @@
+package main
+
+import (
+	"sort"
+)
+
+func Twice_largest(l []int) int {
+	sort.Ints(l)
+	head := 0
+	for _, v := range l[:len(l)-1] {
+		head += v
+	}
+	tail := l[len(l)-1:][0]
+	if head > tail {
+		return -1
+	} else {
+		return 1
+	}
+}
diff --git a/challenge-191/ealvar3z/go/ch-1_test.go b/challenge-191/ealvar3z/go/ch-1_test.go
new file mode 100644
index 0000000000..2ee08d76ce
--- /dev/null
+++ b/challenge-191/ealvar3z/go/ch-1_test.go
@@ -0,0 +1,23 @@
+package main
+
+import (
+	"testing"
+)
+
+func TestSolution(t *testing.T) {
+	cases := []struct {
+		in      []int
+		out     int
+		example string
+	}{
+		{[]int{1, 2, 3, 4}, -1, "example 1"},
+		{[]int{1, 2, 0, 5}, 1, "example 2"},
+		{[]int{2, 6, 3, 1}, 1, "example 3"},
+		{[]int{4, 5, 3, 2}, -1, "example 4"},
+	}
+	for _, c := range cases {
+		if got := Twice_largest(c.in); got != c.out {
+			t.Errorf("got %d, want %d, on %s", got, c.out, c.example)
+		}
+	}
+}
diff --git a/challenge-191/ealvar3z/go/ch-2.go b/challenge-191/ealvar3z/go/ch-2.go
new file mode 100644
index 0000000000..9a54f60798
--- /dev/null
+++ b/challenge-191/ealvar3z/go/ch-2.go
@@ -0,0 +1,32 @@
+package main
+
+import "fmt"
+
+func cute_list(n int) int {
+	count := 0
+	position := 1
+
+	visited := make([]bool, n+1)
+	backtrack(n, position, &count, visited)
+	return count
+}
+
+func backtrack(n int, pos int, count *int, visited []bool) {
+	if pos > n {
+		*count++
+	}
+
+	for i := n; i >= 1; i-- {
+		if visited[i] || (i%pos != 0 && pos%i != 0) {
+			continue
+		}
+		visited[i] = true
+		backtrack(n, pos+1, count, visited)
+		visited[i] = false
+	}
+	return
+}
+
+func main() {
+	fmt.Println(cute_list(2))
+}
diff --git a/challenge-191/ealvar3z/go/ch-2_test.go b/challenge-191/ealvar3z/go/ch-2_test.go
new file mode 100644
index 0000000000..9e4262b0d1
--- /dev/null
+++ b/challenge-191/ealvar3z/go/ch-2_test.go
@@ -0,0 +1,12 @@
+package main
+
+import "testing"
+
+func TestSolutionII(t *testing.T) {
+	got := cute_list(2)
+	want := 2
+
+	if got != want {
+		t.Errorf("got %d, wanted %d", got, want)
+	}
+}
diff --git a/challenge-191/ealvar3z/python/ch-1.py b/challenge-191/ealvar3z/python/ch-1.py
new file mode 100644
index 0000000000..6785f8112e
--- /dev/null
+++ b/challenge-191/ealvar3z/python/ch-1.py
@@ -0,0 +1,32 @@
+#!/usr/bin/env python3
+from functools import reduce
+import unittest
+
+
+class TestSolution(unittest.TestCase):
+    cases = [
+            [1, 2, 3, 4],
+            [1, 2, 0, 5],
+            [2, 6, 3, 1],
+            [4, 5, 2, 3],
+    ]
+
+    def twice_largest(self, lst):
+        s = sorted(lst)
+        head = reduce(lambda x, y: x+y, s[:-1])
+        tail = s[-1]
+
+        if head > tail:
+            return -1
+        else:
+            return 1
+
+    def test_twice_largest(self):
+        self.assertEqual(self.twice_largest(self.cases[0]), -1, 'example 1')
+        self.assertEqual(self.twice_largest(self.cases[1]),  1, 'example 2')
+        self.assertEqual(self.twice_largest(self.cases[2]),  1, 'example 3')
+        self.assertEqual(self.twice_largest(self.cases[3]), -1, 'example 4')
+
+
+if __name__ == "__main__":
+    unittest.main(verbosity=True)
diff --git a/challenge-191/ealvar3z/python/ch-2.py b/challenge-191/ealvar3z/python/ch-2.py
new file mode 100644
index 0000000000..e013d84da8
--- /dev/null
+++ b/challenge-191/ealvar3z/python/ch-2.py
@@ -0,0 +1,39 @@
+#!/usr/bin/env python3
+import unittest
+
+
+class TestSolutionII(unittest.TestCase):
+
+    def cute_list(self, n):
+        bitset_total = 2**n
+        bitset = [[0 for i in range(bitset_total)] for j in range(n+1)]
+        # set the base case
+        bitset[0][0] = 1
+
+        # iterate over all of the positions
+        for i in range(1, n+1):
+            # iterate over all of the subsets
+            for j in range(bitset_total):
+                # iterate over all of the numbers w/in each subset
+                for k in range(n):
+                    # for each number in the subset
+                    # check if the number exists?
+                    visit = (j & (1 << k))  # is the bit set?
+                    condition_one_holds = ((k+1) % i == 0)
+                    condition_two_holds = (i % (k+1) == 0)
+                    if visit and condition_one_holds or condition_two_holds:
+                        # if one of these conditions hold, and we have seen the
+                        # value, then the list is cute.
+                        # Grab the count of what we've seen and return it.
+                        # if this bit was set, unset it
+                        visited = (j ^ (1 << k))
+                        saw_it = bitset[i-1][visited]
+                        count = bitset[i][j] = bitset[i][j] + saw_it
+        return count
+
+    def test_cute_list(self):
+        self.assertEqual(self.cute_list(2), 2)
+
+
+if __name__ == "__main__":
+    unittest.main(verbosity=True)