[Programmers] Numero target (Python)

Problema

Si hanno n interi non negativi. Si vuole ottenere un numero target sommandoli o sottraendoli opportunamente. Ad esempio, per ottenere 3 da [1, 1, 1, 1, 1]:

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

Dato un array numbers di numeri disponibili e un numero target, scrivere una funzione solution che restituisca il numero di modi per raggiungere il target sommando e sottraendo.

Vincoli:

• Il numero di cifre fornite e’ compreso tra 2 e 20.
• Ogni numero e’ un naturale compreso tra 1 e 50.
• Il numero target e’ un naturale compreso tra 1 e 1000.

Soluzione

A quanto pare si puo’ risolvere con BFS o DFS. Non lo sapevo e alla fine ho consultato le soluzioni dopo averci sbattuto la testa. Con n caselle da riempire e solo +/- come segni disponibili, l’approccio naive e’ $2^n$. Serve un algoritmo efficiente.

dfs

1
answer = 0
2
def DFS(idx, numbers, target, value):
3
    global answer
4
    N = len(numbers)
5
    if(idx== N and target == value):
6
        answer += 1
7
        return
8
    if(idx == N):
9
        return
10

11
    DFS(idx+1,numbers,target,value+numbers[idx])
12
    DFS(idx+1,numbers,target,value-numbers[idx])
13

14
def solution(numbers, target):
15
    global answer
16
    DFS(0,numbers,target,0)
17
    return answer

La soluzione piu’ facile da capire.

Implementa il processo di risoluzione dell’equazione tramite ricorsione. Le decisioni +/- vengono accumulate in value attraverso le chiamate ricorsive.

La risposta si trova quando tutte le caselle sono state riempite in value e value e’ uguale a target. Se tutte le caselle sono state riempite ma idx e’ uguale a N senza corrispondenza, e’ un vicolo cieco.

A me sembra piu’ BFS che DFS… ma comunque e’ stata la piu’ facile da seguire.

product

1
from itertools import product
2
def solution(numbers, target):
3
    l = [(x, -x) for x in numbers]
4
    s = list(map(sum, product(*l)))
5
    return s.count(target)

product esegue tra liste la stessa operazione di join usata nei database. La lista deve essere spacchettata quando viene passata, da qui l’asterisco su l. https://mingrammer.com/understanding-the-asterisk-of-python/

1. Creare una lista di tuple con segni +/- per ogni elemento di numbers.
2. Usare product per ottenere tutte le combinazioni tra gli elementi di l.
3. Applicare sum a ogni combinazione tramite map.
4. Restituire il conteggio delle combinazioni la cui somma e’ uguale a target.

Il codice piu’ pulito. Non sono sicuro delle garanzie di performance, ma dati i vincoli del problema, le funzioni built-in di Python sembrano sufficienti.

bfs

1
import collections
2

3
def solution(numbers, target):
4
    answer = 0
5
    stack = collections.deque([(0, 0)])
6
    while stack:
7
        current_sum, num_idx = stack.popleft()
8

9
        if num_idx == len(numbers):
10
            if current_sum == target:
11
                answer += 1
12
        else:
13
            number = numbers[num_idx]
14
            stack.append((current_sum+number, num_idx + 1))
15
            stack.append((current_sum-number, num_idx + 1))
16

17
    return answer

Simile all’approccio DFS visto sopra. Aggiorna ripetutamente current_sum, lo passa alla funzione ricorsiva e verifica.