Tema de clasa a 3-a :D

Workflow & Best Practices Code Review
1

Cerinta:

Write a program that outputs all possibilities to put + or - or nothing between the numbers 1,2,…,9 (in this order) such that the result is 100. For example 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100.

Este luata random de pe Interwebs (nu, nu vad dau sursa, mwa ha ha) - voi posta si eu solutia soon, fara copy paste de data asta :slight_smile: (pinky swear)

Reguli:

  • don’t be an asshole
  • il puteti scrie in ce limbaj vreti (chiar recomand in cat mai multe)
  • o implementare per post
  • comments unde codul este smarty-pants sau obscur
  • O(n) ?
3 Likes
2

E o problema clasica :slight_smile:

var numbers = [1,2,3,4,5,6,7,8,9];
var sum = 100;
var signs = ['+', '-', '&'];
var numbersInnerLength = numbers.length-1;
var cLength = Math.pow(signs.length, numbersInnerLength);
var combinations = [];
 
for (var i = 0; i < cLength; i++) {
    var newArray = [];
    for (var j = 0; j < numbers.length; j++) {
        newArray[j*2] = numbers[j];
    }
    combinations.push(newArray);     
}
 
for (var k = 0; k < numbersInnerLength; k++) {
    var periodLength = cLength / Math.pow(signs.length, k+1);
    var signIndex = 0;
    for (var i = 0; i < cLength; i+=periodLength) {
        for (var j = 0; j < periodLength && i+j < cLength; j++) {
            combinations[i+j][k*2+1] = signs[signIndex];
        }
        signIndex = (signIndex+1)%signs.length;
    }
}
 
for (var i = 0; i < combinations.length; i++) {
    var combination = combinations[i];
    var cstr = combination.join("").replace(/&/g, "");
    if (eval(cstr) == sum) {
        console.log(cstr);
    }
}

Nu e solutia optima din punct de vedere O(n), dar e cea mai usoara de inteles.

Screenshot from 2016-11-12 17-41-18.png1366×768 140 KB

3 Likes
3

Si in Erlang!

-module(plusminus).
-export([compose/1, splitList/1, solve/1]).

% integer recursive pow
pow(_, 0) -> 1;
pow(X, Y) -> X*pow(X,Y-1).

% [[1,2,3],[4,5,6]] -> [123,456]
compose([]) -> [];
compose({L1,L2}) -> {compose(L1),compose(L2)};
compose([{L1,L2}|[]]) -> {compose(L1),compose(L2)};
compose([{L1,L2}|T]) -> [compose({L1,L2}),compose(T)];

% [1,2,3] -> 123
compose([H]) -> H;
compose([H|T]) -> H*pow(10,length(T))+compose(T).

% [1,2,3] -> [  {[1],[2,3]},
%                {[1,2],[3]},
%                {[1,2,3],[]} ]
% A se citi: toate sublistele splituite la indexul S,
%    cu proprietatea ca S apartine {1,2...length(L)}
splitList(L) -> [lists:split(S,L)||S<-lists:seq(1,length(L))].

% suma/diferenta recursiva
sum([],_, _) -> done;
% printeaza daca suma cu ultimul element este 100
sum([H], Sum, List) when H+Sum==100 ->  io:format("~w~n", [[H|List]]);
% nu lasa primul element sa fie negativ
sum([H], Sum, List) when Sum-H==100, H/=1 ->  io:format("~w~n", [[-H|List]]);
% aduna/scade pe stiva
sum([H|T], Sum, List) -> sum(T,H+Sum,[H|List]),sum(T,Sum-H,[-H|List]).

solve([],[]) -> done;
% lista cu numerele este inversata
solve([], [H|T]) ->
    if
        % doar daca ultima cifra este 9
        (H rem 10)==9 ->
            sum([H|T],0,[]);
        true ->
            done
    end;
% genereaza fiecare sublista eficient
solve([{L1,L2}|T], List) ->  solve(splitList(L2),[compose(L1)|List]), solve(T,List).
solve(L) -> solve(splitList(L),[]).

Output generat:

[1,2,3,-4,5,6,78,9]
[1,2,34,-5,67,-8,9]
[1,23,-4,5,6,78,-9]
[1,23,-4,56,7,8,9]
[12,-3,-4,5,-6,7,89]
[12,3,4,5,-6,-7,89]
[12,3,-4,5,67,8,9]
[123,-4,-5,-6,-7,8,-9]
[123,4,-5,67,-89]
[123,45,-67,8,-9]
[123,-45,-67,89]
done
3 Likes
4

Abordarea mea este aceea de a folosi o funcție recursivă pentru a sparge problema în probleme mai mici, pornind de la dreapta la stânga.
O reprezentare vizuală a ce se întâmplă:

[1,2,3,4,5,6,7,8,9] = 100
    [[1,2,3,4,5,6,7,8] + 9] = 100
        [[[1,2,3,4,5,6,7] + 8] + 9] = 100
            [[[[1,2,3,4,5,6] + 7] +  8] + 9] = 100
            [[[[1,2,3,4,5,6] - 7] +  8] + 9] = 100
            ...
            ... [[[[[[[[1] + 2] + 3] - 4] + 5] + 6] + 78] + 9] = 100
            ...
        [[[1,2,3,4,5,6,7] - 8] + 9] = 100
            [[[[1,2,3,4,5,6] + 7] - 8] + 9] = 100
            [[[[1,2,3,4,5,6] - 7] - 8] + 9] = 100
        ...
    [[1,2,3,4,5,6,7,8] - 9] = 100
        [[[1,2,3,4,5,6,7] + 8] - 9] = 100
        [[[1,2,3,4,5,6,7] - 8] - 9] = 100
    ...
    [[1,2,3,4,5,6,7] + 89] = 100
        [[[1,2,3,4,5,6] + 7] + 89] = 100
        [[[1,2,3,4,5,6] - 7] + 89] = 100
        ...
    [[1,2,3,4,5,6,7] - 89] = 100
        [[[1,2,3,4,5,6] + 7] - 89] = 100
        [[[1,2,3,4,5,6] - 7] - 89] = 100

Codul este un pic optimizat prin faptul că nu încearcă toate combinațiile posibile și sare peste cele rezultate atunci când numărul maxim ce poate fi obținut dintr-un subset este mai mic decât cel necesar pentru a obține rezultatul dorit. De exemplu, codul nu mai încearcă combinațiile pentru subsetul [1,2,3,4] unde

[[1,2,3,4] - 56789] = 100

sau [1,2,3] unde

[[[1,2,3] + 567] - 89] = 100

Asta a dus execuția la ~30 ms față de ~500 ms cât îi ia codului lui @asdfilesystem pe laptop-ul meu (nu e nici un reproș sau altceva, doar o comparație :slight_smile:).

function _sum(numbers, total) {
    // numărul maxim ce poate fi obținut prin concatenarea elementelor
    let max = parseInt(numbers.join(''), 10);
    let combinations = [];

    // dacă numărul maxim este mai mic decât totalul,
    // nu există nici o combinație posibilă
    if (max < Math.abs(total)) {
        return [];
    }

    // dacă numărul maxim este egal cu totalul,
    // se returnează singura combinație posibilă
    if (max == total) {
        return [[max]];
    }

    // se împarte recursiv setul în subseturi mai mici, de la dreapta la stânga
    for (let cursor = numbers.length - 1; cursor > 0; cursor--) {
        // rezultatul concatenării numerelor din dreapta
        let target = parseInt(numbers.slice(cursor).join(''), 10);
        // subsetul rămas după eliminarea numerelor de după cursor
        let values = numbers.slice(0, cursor);

        // suma subsetului trebuie să fie `total +/- target`
        for (let sign of [-1, 1]) {
            let right = target * sign;
            let left  = _sum(values, total - right);

            for (let subset of left) {
                // la fiecare combinație posibilă din subset se adaugă
                // elementele din dreapta cursorului
                combinations.push(subset.concat([right]));
            }
        }
    }

    return combinations;
}

let results = _sum([1,2,3,4,5,6,7,8,9], 100);

// =============================================================================
// afișare rezultate
// =============================================================================
console.log('Combinații posibile:', results.length);

for (let result of results) {
    console.log(result, result.reduce((carry, value) => carry + value, 0));
}

// Combinații posibile: 11
// [ 123, -4, -5, -6, -7, 8, -9 ] 100
// [ 123, 45, -67, 8, -9 ] 100
// [ 1, 23, -4, 5, 6, 78, -9 ] 100
// [ 1, 2, 34, -5, 67, -8, 9 ] 100
// [ 1, 23, -4, 56, 7, 8, 9 ] 100
// [ 12, 3, -4, 5, 67, 8, 9 ] 100
// [ 1, 2, 3, -4, 5, 6, 78, 9 ] 100
// [ 123, 4, -5, 67, -89 ] 100
// [ 12, 3, 4, 5, -6, -7, 89 ] 100
// [ 12, -3, -4, 5, -6, 7, 89 ] 100
// [ 123, -45, -67, 89 ] 100

Dacă tot punem și screenshot-uri… :slight_smile:

clasa-a-3-a.png1024×1047 107 KB

4 Likes