Телеграмм чат группы js_noobs

function solve(arr) {
  const sum = arr.reduce((acc, cur) => acc+cur, 0)

  function take(set1, set2, set1sum, set2sum) {
    let result = { set1, set2, set1sum, set2sum }
    for (let i=0; i<set1.length; i++) {
      const x = set1[i]
      const _set1 = [...set1.slice(0, i), ...set1.slice(i + 1)]
      const _set2 = [...set2, x]
      const r = take(_set1, _set2, set1sum - x, set2sum + x)
      if (Math.abs(r.set1sum - r.set2sum) < Math.abs(set1sum - set2sum)) {
        result = r
      }
    }
    return result
  }

  return take(arr, [], sum, 0, sum)
}

const result = solve([8, 7, 6, 5, 4])
console.log(result)

подвис на [0,1,2,2,2,3,4,7,10,40,54,60,120,127]

Denys Mikhalenko in JavaScript Noobs — сообщество новичков

15:41пожаловаться #1

Ну дык перебор же )

15:42пожаловаться #2

не должен так, перебор моментально отработал

15:43пожаловаться #3

🌬М

Denys Mikhalenko

function solve(arr) {
  const sum = arr.reduce((acc, cur) => acc+cur, 0)

  function take(set1, set2, set1sum, set2sum) {
    let result = { set1, set2, set1sum, set2sum }
    for (let i=0; i<set1.length; i++) {
      const x = set1[i]
      const _set1 = [...set1.slice(0, i), ...set1.slice(i + 1)]
      const _set2 = [...set2, x]
      const r = take(_set1, _set2, set1sum - x, set2sum + x)
      if (Math.abs(r.set1sum - r.set2sum) < Math.abs(set1sum - set2sum)) {
        result = r
      }
    }
    return result
  }

  return take(arr, [], sum, 0, sum)
}

const result = solve([8, 7, 6, 5, 4])
console.log(result)

чекну сейчас спс )

Denys Mikhalenko in JavaScript Noobs — сообщество новичков

15:44пожаловаться #4

Chris

не должен так, перебор моментально отработал

Значит где-то лишнего перебирает

15:44пожаловаться #5

Chris

function partition(array, mask) {
    let a = [], b = [], i = array.length;
    while (--i >= 0) {
        if ((mask >> i) & 1) a.push(array[i]);
        else b.push(array[i]);
    }
    return [a, b];
}

function sum(array) {
    let result = 0, l = array.length;
    while (--l >= 0) result += array[l];
    return result
}

function split(array) {
    let len = array.length;
    let i = 2 ** len;
    let results = [];
    let min = Infinity, minidx = 0;
    while (--i >= 0) {
        let [a, b] = partition(array, i);
        let diff = Math.abs(sum(a) - sum(b))
        if (diff < min) {
            if (diff === 0) return [a, b];
            min = diff;
            minidx = i;
        }
        results[i] = [a, b];
    }

    return results[minidx];
}

перебором

@Mary_Kutsarenko 👆

15:46пожаловаться #6

🌬М

Chris

function partition(array, mask) {
    let a = [], b = [], i = array.length;
    while (--i >= 0) {
        if ((mask >> i) & 1) a.push(array[i]);
        else b.push(array[i]);
    }
    return [a, b];
}

function sum(array) {
    let result = 0, l = array.length;
    while (--l >= 0) result += array[l];
    return result
}

function split(array) {
    let len = array.length;
    let i = 2 ** len;
    let results = [];
    let min = Infinity, minidx = 0;
    while (--i >= 0) {
        let [a, b] = partition(array, i);
        let diff = Math.abs(sum(a) - sum(b))
        if (diff < min) {
            if (diff === 0) return [a, b];
            min = diff;
            minidx = i;
        }
        results[i] = [a, b];
    }

    return results[minidx];
}

перебором

☺️🍰 то что нуно )

Denys Mikhalenko in JavaScript Noobs — сообщество новичков

15:49пожаловаться #7

function solve(arr) {
  const sum = arr.reduce((acc, cur) => acc+cur, 0)

  function take(set1, set2, set1sum, set2sum, s=0) {
    let result = { set1, set2, set1sum, set2sum }
    for (let i=s; i<set1.length; i++) {
      const x = set1[i]
      const _set1 = [...set1.slice(0, i), ...set1.slice(i + 1)]
      const _set2 = [...set2, x]
      const r = take(_set1, _set2, set1sum - x, set2sum + x, i)
      const d = Math.abs(r.set1sum - r.set2sum)
      if (d < Math.abs(result.set1sum - result.set2sum)) {
        if (d === 0) return r
        result = r
      }
    }
    return result
  }

  return take(arr, [], sum, 0)
}

вот, чуток оптимизировал, чтоб не перебирало все комбинации 👍

Erali in JavaScript Noobs — сообщество новичков

15:59пожаловаться #8

Ребят здесь есть vue.js

Erali in JavaScript Noobs — сообщество новичков

15:59пожаловаться #9

разработчики

Denys Mikhalenko in JavaScript Noobs — сообщество новичков

15:59пожаловаться #10

просто в рекурсии не с нуля надо ходить было, а с того места, где мы закончили на прошлом шаге

16:00пожаловаться #11

evgeny shev in JavaScript Noobs — сообщество новичков

Arch Gear

Привет, вопрос немного не по джаваскрипт, а в целом об общем - что стоит утчить следующим когда освоил и получил опыт с react, react native, redux, saga
Думаю или typescript, или учиться писать юнит тесты.
Сейчас работаю в аутсорс конторе, но целюсь в какой нибудьь продукт или стартапчик.

тебе лучше в просто JS чат наверное. Тут же новички скорее всего никто еще не работает) ну мне так кажется

Denys Mikhalenko in JavaScript Noobs — сообщество новичков

16:04пожаловаться #12

Интересно, что мое находит решение за 549 шагов, а Криса - за 5637 😁

16:08пожаловаться #13

🌬М

Denys Mikhalenko

function solve(arr) {
  const sum = arr.reduce((acc, cur) => acc+cur, 0)

  function take(set1, set2, set1sum, set2sum, s=0) {
    let result = { set1, set2, set1sum, set2sum }
    for (let i=s; i<set1.length; i++) {
      const x = set1[i]
      const _set1 = [...set1.slice(0, i), ...set1.slice(i + 1)]
      const _set2 = [...set2, x]
      const r = take(_set1, _set2, set1sum - x, set2sum + x, i)
      const d = Math.abs(r.set1sum - r.set2sum)
      if (d < Math.abs(result.set1sum - result.set2sum)) {
        if (d === 0) return r
        result = r
      }
    }
    return result
  }

  return take(arr, [], sum, 0)
}

вот, чуток оптимизировал, чтоб не перебирало все комбинации 👍

круто ! ) спс и вам огромное 🧁

Denys Mikhalenko in JavaScript Noobs — сообщество новичков

16:09пожаловаться #14

Но идея с битовыми масками крутая, если бы важна была производительность, это могло бы сильно ускорить процесс

Denys Mikhalenko in JavaScript Noobs — сообщество новичков

16:10пожаловаться #15

Пересоздание массивов - дорогая операция

16:10пожаловаться #16

🌬М

надеюсь тоже начну в этом шарить ) очень помогли спс

16:11пожаловаться #17

Denys Mikhalenko

Интересно, что мое находит решение за 549 шагов, а Криса - за 5637 😁

Гм, оно всё ещё тупит и решает за 18 секунд против 5 мсек. Но это неважно, потому что решение чувака из соседнего чата делает это за 0.5 мс

16:14пожаловаться #18

Переслано от Tahmuras Abdurashido...

Извиняюсь за говнокод, но мне было не до того)), не смог сделать быстрее чем за O(2^n) - но ответ всегда правильный), я загуглил и вроде пока что эту задачу нельзя решать быстрее, но если найду скажу
function eqSum(arr) {
const totSum = arr.reduce((totSum, num) => totSum+=num);
let shit = arr.map(el => 0);
const median = totSum/2;
let mn = median;
function rec(sum, curInd, shitCopy) {
let shitArr = [...shitCopy];
shitArr[curInd] = 1;
const curSum = sum + arr[curInd];
if (mn > Math.abs(median - curSum)) {
shit = [...shitArr];
mn = Math.abs(median - curSum);
}
if (curInd <= arr.length-2) {
rec(curSum, curInd+1, shitArr);
shitArr[curInd] = 0;
rec(sum, curInd+1, shitArr);
}
}
rec(0, 0, shit);
let firstArr = [], secondArr = [];
for ([i, el] of shit.entries()) {
if (el) firstArr.push(arr[i]);
if (!el) secondArr.push(arr[i]);
}
return [firstArr, secondArr];
}

Denys Mikhalenko in JavaScript Noobs — сообщество новичков

16:14пожаловаться #19

А правильно ли оно решает?