Reduce & Backtrack
Perl Weekly Challenge 191
Task I
Another week, another opportunity to participate in the weekly Perl
Challenge.
The first
task
was self explanatory if you read the code. With use of reduce() from
functools, it makes for very efficient and readable code. The logic is
simple to figure out, since the sum of the n items in the list cannot
be greater than the largest item. For example:
Take the following list: [1, 2, 3, 4]. The largest item on this list
is 4. If the sum of the previous elements is greater than 4 (i.e.
6), then it does not meet the condition of the largest item in the
list being “at least twice as large as each of the other items”.
Here’s the code snippet:
#!/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)
Task II
The second task was a little more involved and I used two different data
structures to solve them: slice of booleans for the golang solution, and
a bitset with the python one. However, I used the same technique for
finding the solution: backtracking1.
For the classical backtracking approach using bool slices, here’s the
golang snippet:
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))
}
With that in mind, I could represent the same boolean values using
bitsets as an alternative approach, as it makes for very efficient
code, since we are constrained to the numbers in the list to be within
the 0 <= n <= 15. My idea was to use bitmasks to check the places
within the bitset that were visited, and for each of the numbers that
were visited in each of the subsets, we toggle off and add it to our
count, after it meets the (2) required conditions. See snippet below:
#!/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.
visited = (j ^ (1 << k)) # if this bit was set, unset it
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)
Another fun round of challenges, and send your thanks to @cpan_author and the rest of of the PWC team.
Happy hacking!
Reference: