# Perl Weekly Challenge 191

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]

return -1
else:
return 1

def test_twice_largest(self):
self.assertEqual(self.twice_largest(self.cases), -1, 'example 1')
self.assertEqual(self.twice_largest(self.cases),  1, 'example 2')
self.assertEqual(self.twice_largest(self.cases),  1, 'example 3')
self.assertEqual(self.twice_largest(self.cases), -1, 'example 4')

if __name__ == "__main__":
unittest.main(verbosity=True)
``````

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 = 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: