There Are Many Duplicate Answers

Computer Science Level 3

$\large 67\, \square \, 97\, \square \, 95\, \square \, 99\, \square \, 60\, \square \, 50\, \square \, 55\, \square \, 37\, \square \, 70\, \square \,61$

We can fill the squares above with $+$ and/or $-$ , how many distinct results could we get?

The answer is 337.

5 solutions

展豪張
Jul 15, 2016

Here is my code in python:

from itertools import *  
from operator import *  
a=[67,97,95,99,60,50,55,37,70,61]  
b=[[1]]+[[1,-1]]*9  
print(len(set(sum(map(mul,a,i))for i in product(*b))))

The answer is 337.

Wow, that is some clever use of itertools

Agnishom Chattopadhyay - 4 years, 11 months ago

Haha actually a lazy use of itertools

展豪張 - 4 years, 11 months ago

Can you briefly explain what the code is doing? This seems an advance use of Python.

Christopher Boo - 4 years, 11 months ago

I think the most worth-explaining part in my code is the last line, so I will only explain this line.

Let's tear it into parts:
At the last part there is a product(*b) .
Referring to line 4, b is a two-layer array: [[1],[1,-1],...,[1,-1]] .
Each $1,-1$ represents a $+$ or $-$ filled into the box.
The first is not [1,-1] because we cannot fill a $-$ in front of $67$ .

The * 'flattens' the array and so product(*b) means product([1],[1,-1],...,[1,-1] .
product is a itertool producing an iterator which gives all elements of the Cartesian product of its argument, for example (1,1,-1,-1,1,1,1,-1,-1,1) .

So the i fed into the map(mul,a,i) are tuples of length $10$ with $1$ s and $-1$ s.
map(func,a,b) will take one from a , one from b , apply func on them and put it into the map object until the iterator is exhausted. mul is the multiplication function.
So for example, map(mul,[67,97,95,99,60,50,55,37,70,61],(1,1,-1,-1,1,1,1,-1,-1,1)) will produce a map object (which is an iterator) containing (67,97,-95,-99,60,50,55,-37,-70,61) .

sum takes an iterator and return its sum (duh), in this case, $67+97-95-99+60+50+55-37-70+61=89$

now sum(map(mul,a,i))for i in product(*b) is a iterator with all possible results (with repetition) in it.
set(iterator) turns the iterator into a set, which does not have repetition.
len , when applied to a set , measures the size of the set , which is the number of all possible results without repetition, which is the answer we want ;)

展豪張 - 4 years, 11 months ago

Rushikesh Jogdand
Jul 19, 2016

Binary manipulation and use of python's exec function.

numbers=['67', '97', '95', '99', '60', '50', '55', '37', '70', '61']
d={'1':'-','0':'+'}                  #manipulate 1s and 0s as - and +
results=[]
for i in range(0,512):
    e=numbers[0]
    op=list(('000000000'+bin(i)[2:])[-9:])        #'000000000' s for numbers whose binary representation is shorter than 9 digits.
    for j in range (0,9):
        e+=d[op[j]]
        e+=numbers[j+1]
    exec('result='+e)
    results.append(result)
print(len(set(results)))

Gopinath No
Jul 23, 2016

st = set()
lst = [67, 97, 95, 99, 60, 50, 55, 37, 70, 61]

def res(a, lst):
    if len(lst) == 1:
        st.add(a+lst[0])
        st.add(a-lst[0])
        return
    res(a+lst[0], lst[1:])
    res(a-lst[0], lst[1:])

res(lst[0], lst[1:])
print len(st)

Terry Smith
Jul 27, 2016

Ruby

A = %w(67 97 95 99 60 50 55 37 70 61).map{|l|l.to_i}

$a = []

def recAdd(l, sum)
    if l == 10
        $a << sum
        return
    end
    recAdd(l + 1, sum + A[l])
    recAdd(l + 1, sum - A[l])
end

recAdd(1, 67)
$a.uniq!
p $a.length

Christopher Boo
Jul 19, 2016

We iterate through every binary string of length 9. If bit $i$ is 1, then the $i$ -th column is $+$ , otherwise $-$ . How can we generate all binary string of length 9? Simply loop through every integers from $0$ to $2^9-1$ , which binary representation are $000000000$ and $111111111$ respectively.

set is used to avoid duplicates.

Here is my code in C++:

#include <bits/stdc++.h>
using namespace std;

int main() {

    int a[] = {67,97,95,99,60,50,55,37,70,61};

    set<int> s;
    for (int i = 0; i < (1<<9); i++) {
        int val = a[0];
        for (int j = 0; j < 9; j++) {
            if (i & (1<<j))
                val += a[j+1];
            else
                val -= a[j+1];
        }
        s.insert(val);
    }

    cout << s.size() << endl;

    return 0;
}

Relevant: bit manipulation hacks

Agnishom Chattopadhyay - 4 years, 11 months ago

What's wrong with my code?

li = []              #will contain all possible binary strings of length 9.

for i in range(0,512):  


    a = len(bin(i).split('0b')[1])


    if a==9:


        li.append(bin(i).split('0b')[1])


    else:


        de = 9-a


        c = bin(i).split('0b')[1]


        b = '0'*de+c


        li.append(b)



nos = [67,97,95,99,60,50,55,37,70,61]


nosu = [97,95,99,60,50,55,37,70,61]   #We don't need 67 because it will always be positive. 


ans = set()

for j in range(0,len(li)):  #going through each binary string and comparing each element of nosu with corresponding bit


    x = list(int(k) for k in li[j]) #makes a list of individual digits in int(binary_string)


    for i in range(0,9):

        if x[i]==1: 


            nosu[i]=nosu[i] #sign of nosu[i] will be positive


        else:


            nosu[i]=nosu[i]*(-1) #sign of nosu[i] will be negative

    new_nosu_sum = sum(nosu)        
    ans.add(new_nosu_sum) 

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
>>>len(ans)
201
>>>

I was using the same approach as you, that is makin 1=+1 and 0=-1 and then multiplying it with the numbers.

Harsh Shrivastava - 4 years, 11 months ago

Please cleanup your code and briefly describe what the code is doing. It's hard for us to view a code without any comments.

Christopher Boo - 4 years, 11 months ago

There Are Many Duplicate Answers

The answer is 337.

5 solutions

0 pending reports