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
            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__":

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 {

	for i := n; i >= 1; i-- {
		if visited[i] || (i%pos != 0 && pos%i != 0) {
		visited[i] = true
		backtrack(n, pos+1, count, visited)
		visited[i] = false

func main() {

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__":

Another fun round of challenges, and send your thanks to @cpan_author and the rest of of the PWC team.

Happy hacking!


Back to top