# 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: backtracking^{1}.

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: