1
\$\begingroup\$

you can find the challenge here for more details, but the subject says it all;

Check a provided list of entries for 2 numbers which sum to 2020, return the product of those addends.

I waited until the event was over to keep things fair.

/*This will search for 2 numbers in the `list that sum to `target` 
  Assumption;
  * We only get integers in a string that are new-line separated
  * The sum is there, so we dont stop searching even if it doesnt make sense
*/
function findTargetSum(listAsString, target){
  const list = entries.split('\n').map(s => s*1);
  const set = new Set(list);
  for (const i of set) {
     if(set.has(target - i)){
       return i * (target - i);
     }
  }
}

function findTargetSum3(listAsString, target){
   
  const list = entries.split('\n').map(s => s*1);
  const set = new Set(list);
  for (const i of set){
    for(const i2 of set){
      if(i != i2){
        if(set.has(target -i - i2)){
          return i * i2 * (target -i - i2);
        }
      }
    }
  }
}

const entries = `1780
1693
1830
1756
1858
1868
1968
1809
1996
1962
1800
1974
1805
1795
170
1684
1659
1713
1848
1749
1717
1734
956
1782
1834
1785
1786
1994
1652
1669
1812
1954
1984
1665
1987
1562
2004
2010
1551
961
1854
2005
1883
1965
475
1776
1791
262
1912
1227
1486
1989
1857
825
1683
1991
1875
1982
1654
1767
1673
1973
1886
1731
1745
1770
1995
1721
1662
1679
1783
1999
1889
1746
1902
2003
1698
1794
1798
1951
1953
2007
1899
1658
1705
62
1819
1708
1666
2006
1763
1732
1613
1841
1747
1489
1845
2008
1885
2002
1735
1656
1771
1950
1704
1737
1748
1759
1802
2000
1955
1738
1761
1765
1853
1900
1709
1979
1911
1775
1813
1949
1966
1774
1977
1757
1992
2009
1956
1840
1988
1985
1993
1718
1976
1078
1997
1897
1792
1790
1801
1871
1727
1700
1485
942
1686
1859
1676
802
1952
1998
1961
1844
1808
1703
1980
1766
1963
1849
1670
1716
1957
1660
1816
1762
1829
526
359
2001
1874
1778
1873
1511
1810
1699
1970
1690
1978
1892
1691
1781
1777
1975
1967
1694
1969
1959
1910
1826
1672
1655
1839
1986
1872
1983
1981
1972
1772
1760`;

console.log(findTargetSum(entries, 2020));
console.log(findTargetSum3(entries, 2020));

\$\endgroup\$
1
\$\begingroup\$

Bugs

There are 3 bugs, or two depending on input.

  1. Both functions use an undefined variable. entries which should be either listAsString or change the argument listAsString to entries

  2. The second function does not return the correct values. This function is not at all worth considering because you are iterating the set for each item in the set. Sets use generated hash keys to locate items, they eliminate the need to do this type of search.

  3. Will 1010 appear alone in the input list?

    If yes, then your code does not work as it may return 1010 * 1010 === 1020100 because your search will find the match set.has(target - i).

    If no, then this is not a bug.


Review

As your question is tagged "programming challenge" this review focuses on performance,

Programming challenges

The main purpose of programming challenge sites is to provide problems to gain experience programming. The challenge is to complete the task and provide the correct return. Thus the focus is much less on how you write the code and much more about what the code does.

Apart from the correct return value these sites use performance to rate the code. (I am not a member of linked site so it is unclear if this is true for that site)

There is no other non subjective metric to rate code apart from code length and as there is no mention of code golf on the site, code length is not being considered in this review.

One assumes that as you are member you are interested in the rating system and getting the best scores for submissions. Thus an eye for performance will be important in your solutions.

Avoid unneeded processing

There is no need to create the Set for all numbers before you start testing each number. Adding a number to a Set though not complex is not quick as there is a overhead associated with calculating the hash.

The same with the conversion of the string into a number. This can also be done while you iterate.

Number from a string

There are many ways to coerce a string value to a number. The most perform-ant standard way is to use Number("1234"). Though there are special cases where this can be improved (see Rewrite 2)

It is unclear what type the target value is. If it is a string then you will need to ensure you convert it to a number before you use it inside a loop. Using it as a string inside a loop will mean it is converted to a number each iteration, an unneeded overhead.

Best, Average and Worst cases

The rewrite (below) is tuned for performance, to ensure that there are no cases where performance is degraded too much, the functions is tested for the best and worst case data sets. Then the final estimate of performance is on a random set of inputs

  • Average performance. If we assume that the string of numbers has the two values randomly inserted and then test performance over a large number of these random arrays the performance increase of the rewrite is 132% faster.

  • For worst possible case (values summing to 2020 as last two items in the input list) there is no significant performance gain.

  • For the best case (values are first 2 items in the list) the improvement is a huge, ruining 5200% faster than your original.

If the argument target is a string and you convert it to a number once before the loops you gain another 5% reduction in time to complete.


Rewrite 1

The rewrite assumes that target is also a string.

There is no need for long names in functions. The size of the scope dictates the size of the variable name. This is why we have scope. The rewrite uses shorter names.

set is never a good name for a Set name it for what it holds, not what it is.

Rewrite assumes that 1010 may appear only once in the list. The optimization of adding to the set of values inside the loop will prevent a false positive match for single 1010.

function findTargetSum(list, target){
    list = list.split("\n");
    target = Number(target); // only if target is type string
    const values = new Set();
    for (const str of list) {
        const num = Number(str), val = target - num;
        if (set.has(val)) { return val * (target - val ) }
        set.add(num);
    }
}


Is there a quicker way?

Yes.

Javascript is bad at handling strings. Assigning a string to a variable requires that the string is copied, which unlike an object, that just needs a reference, the copied string needs iteration as well.

The line for (const str of list) creates a copy of each string. This can be avoided, in fact all the string copying can be avoided by decoding the numbers using String.charCodeAt

Assuming positive values only in the list the following function is 400% faster than your first function on a set of random arrays, the second function that includes negative values is 350% faster.

Rewrite 2

This rewrite is tightly focused on performance. It avoids the slow string.split by decoding the numbers one character at a time. Each time it encounters a newline (char code 10) it checks the number decoded, exits if values found, or continues.

As only the characters "0-9" and "\n" are expected the function can run very fast.

On a random set of numbers with the two values randomly inserted the following function is 400% faster than your original code.

function test(list, target) {
    var i = 0, num = 0;
    const numbers = new Set();
    while (i < list.length) {
        const code = list.charCodeAt(i++) - 48;
        if (code === -38) {
            if (numbers.has(target - num)) { return num * (target - num) }
            numbers.add(num);
            num = list.charCodeAt(i++) - 48;
        } else { num = num * 10 + code }
    }
}

Negatives

The input set may contain negative values some numbers will have a "-" (code 45) to avoid too much overhead the test for negative need only be done once per number. As the list does not contain to new lines in a row we know that after a new line is either a "-" or digit "0"-"9".

As the check for negative bites into that parts of the code that give the above function its performance advantage the following function on a random set of numbers is 350% faster. Still a significant performance increase.

function test(list, target) {
    var i = 0, code = list.charCodeAt(i++);
    var num = code === 45 ? -(list.charCodeAt(i++) - 48) : code - 48;
    const numbers = new Set();
    while (i < list.length) {
        code = list.charCodeAt(i++) - 48;
        if (code === -38) {
            if (numbers.has(target - num)) { return num * (target - num) }
            numbers.add(num);
            code = list.charCodeAt(i++);
            num = code === 45 ? -(list.charCodeAt(i++) - 48) : code - 48;
        } else { num = num * 10 + code }
    }
}

One could make the negative test a function, but this could reduce performance, because in-lining the function will only happen after the JS optimizer has seen the function run many times. For a small set of runs < ~100 the optimizer will not get a chance to do its magic.

Including constants rather than magic numbers

function test(list, target) {
    const CHAR_0 = 48, CHAR_NEWLINE_SUB_0 = -38, CHAR_NEG = 45;
    const startNumber = () => [
        const code = list.charCodeAt(i++);
        return  code === CHAR_NEG ? -(list.charCodeAt(i++) - CHAR_0) : code - CHAR_0;
    }
    var i = 0, num = startNumber();
    const numbers = new Set();
    while (i < list.length) {
        const code = list.charCodeAt(i++) - CHAR_0;
        if (code === CHAR_NEWLINE_SUB_0 ) {
            if (numbers.has(target - num)) { return num * (target - num) }
            numbers.add(num);
            num = startNumber();
        } else { num = num * 10 + code }
    }
}


Notes

  • All code run on Chrome 87 Win x64.

  • Code used your original data as posted moving the matching values from top to bottom of list to determine best and worst cases.

  • The second rewrite used a similar input set of number (3 - 4) characters long. It is unclear what size ints the inputs could be. Performance for rewrite2 will be effected more by long numbers than the first (or your original)

  • The random data sets were created as follows. (two version on positive only values)

    const SUM = 2020;
    const LENGTH = 200;
    const MIN = 900;
    const MAX = 4000;
    const POSITIVE = true;
    function createTestData() {
        const a = $setOf(LENGTH, () => $randI(MIN, MAX));
        var find = true;
        while (find) {
            v = a[$randI(LENGTH)];
            if (v < SUM || !POSITIVE) {
                a.splice($randI(LENGTH), 0, SUM - v)
                break;
            }
        }
        return [a.join("\n"), SUM];
    }


Performance matters

In the real world performance is very important.

CPU cycles have a cost.

  • For server based code, this cost is literal, power, infrastructure.

  • For client based code, it is more subtle as performance equates to quality, low quality apps drain batteries and appears sluggish, which in a competitive market will reduce uptake and ultimately be born as a cost of lost clients.

  • Client costs. Code running on the client will use their power, reducing battery life, and costing them money. Perform-ant code is considerate code.

  • Social and ethical responsibilities. Every CPU cycle will generate some CO2, collectively even small performance gains can make big reductions in CO2 output. Increasing device life reduces waste.

\$\endgroup\$
1
\$\begingroup\$

Looks mostly fine, though there are a few issues:

Argument bug/typo You're referring to top-level variable entries inside the function instead of to the listAsString argument.

Match numbers? Even if it's said that the input will contain line-separated numbers, I'd feel safer matching numeric characters instead of splitting by newlines. It'll be more robust if the input happens to not be formatted perfectly correctly, or at least makes the intent (to extract an array of only digit characters from the input) a bit clearer, without relying on the description.

Maybe use Number? Once you have an array of digit characters, you turn them all into numbers with .map(s => s*1). I think the intent - to cast to numbers - would be a bit clearer by using .map(Number) instead.

i is conventionally used to indicate the index being iterated over. Here, i isn't being used as the index, but as the element being iterated over. Maybe use num instead?

target - i can be saved into a variable instead of repeating it twice, if you want.

Counting bug If the target sum happens to be a sum of two of the same number, eg: 1010 + 1010, those will be matched even if the input only contains one of those numbers, since you're using a Set which doesn't differentiate one occurrence from multiple.

To fix this, you could add an index check to the original array if the two numbers happen to be the same (as I've done below), or count up occurrences into an object, or something like that.


With findTargetSum3, in addition to the above:

Computational complexity is unnecessarily large The first approach is O(n), which is good. This second approach is O(n ^ 2), since you're checking every element against every other element. I'd ditch findTargetSum3 completely.

Prefer strict equality over loose equality - yes, the types are surely the same, so it doesn't make a difference in the logic, but strict equality with !== and === is easier to understand at a glance due to the lack of strange coercion rules. Whenever I see sloppy comparison (especially in professional code), I think: "Why isn't strict comparison being used, is there some possible type coercion weirdness going on that wasn't explicit?" Better to be consistent and use strict equality comparison everywhere.

function findTargetSum(listAsString, target){
  const numbers = listAsString.match(/\d+/g).map(Number);
  const set = new Set(numbers);
  for (const num of set) {
    const otherNum = target - num;
    if (
      set.has(otherNum) &&
      (num !== otherNum || numbers.indexOf(num) !== numbers.lastIndexOf(otherNum))
    ) {
       return num * otherNum;
    }
  }
}

const entries = `1780
1693
1830
1756
1858
1868
1968
1809
1996
1962
1800
1974
1805
1795
170
1684
1659
1713
1848
1749
1717
1734
956
1782
1834
1785
1786
1994
1652
1669
1812
1954
1984
1665
1987
1562
2004
2010
1551
961
1854
2005
1883
1965
475
1776
1791
262
1912
1227
1486
1989
1857
825
1683
1991
1875
1982
1654
1767
1673
1973
1886
1731
1745
1770
1995
1721
1662
1679
1783
1999
1889
1746
1902
2003
1698
1794
1798
1951
1953
2007
1899
1658
1705
62
1819
1708
1666
2006
1763
1732
1613
1841
1747
1489
1845
2008
1885
2002
1735
1656
1771
1950
1704
1737
1748
1759
1802
2000
1955
1738
1761
1765
1853
1900
1709
1979
1911
1775
1813
1949
1966
1774
1977
1757
1992
2009
1956
1840
1988
1985
1993
1718
1976
1078
1997
1897
1792
1790
1801
1871
1727
1700
1485
942
1686
1859
1676
802
1952
1998
1961
1844
1808
1703
1980
1766
1963
1849
1670
1716
1957
1660
1816
1762
1829
526
359
2001
1874
1778
1873
1511
1810
1699
1970
1690
1978
1892
1691
1781
1777
1975
1967
1694
1969
1959
1910
1826
1672
1655
1839
1986
1872
1983
1981
1972
1772
1760`;
console.log(findTargetSum(entries, 2020));
console.log(findTargetSum(`1
3
3
5`, 6));

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.