2
\$\begingroup\$

Task:

We have this big list of (signed) integers.
We are interested in finding every index "idx" (zero-based, of course) in this list, that has the following property: The sum of the integers preceding (but not including) index idx is equal to the sum of the integers followin (again not including) idx. i.e.: (Referring to our list of integers for a moment as "A[]" and the number of integers in the list N), then we want every index
idx for which the following is true:
A[0] + A[1] + ... + A[idx-1] == A[idx+1] + A[idx+2] ... + A[N-1]

Note that there is likely to be more than one index "idx" in the list that satisfies this property.

Write code that finds every index in our big list that has this property. Then, sum up every index that you found, and that is the answer to question 1. For reference, given the array [-7,1,5,2,-4,3,0], the answer we are looking for is 9 because indices 3 and 6 have the property we are looking for (-7 + 1 + 5 == -4 + 3 + 0 and -7 + 1 + 5 + 2 + -4 + 3 == 0) and 3 + 6 = 9. satisfies this property. Write code that finds every index in our big list that has this property. Then, sum up every index that you found, and that is the answer to question 1.

For reference, given the array [-7,1,5,2,-4,3,0], the answer we are looking for is 9 because indices 3 and 6 have the property we are looking for (-7 + 1 + 5 == -4 + 3 + 0 and -7 + 1 + 5 + 2 + -4 + 3 == 0) and 3 + 6 = 9.

I wrote two variants of code:

First read the file in std::string, and then parse it in std::list<int>, and finally, count the answer:

#include <iostream>
#include <list>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <sstream>
#include <iterator>
#include <string>
#include <experimental/filesystem>

namespace fs = std::experimental::filesystem;

uint64_t calc_answer(const std::list<int>& list)
{
    int left_sum = 0;
    int right_sum = std::accumulate(list.begin(), list.end(), 0);

    uint64_t index_sum = 0;
    int curr_index = 0;

    std::for_each(list.begin(), list.end(), [&] (int val) {
        right_sum -= val;

        if(left_sum == right_sum)
            index_sum += curr_index;

        left_sum += val;

        ++curr_index;
    });

    return index_sum;
}

std::string read_file(const fs::path& file_path)
{
    if(!fs::exists(file_path))
        return "";

    std::ifstream infile{file_path.string()};

    std::string data{""};

    std::string row{""};
    while(std::getline(infile, row))
        data.append(row);

    return data;
}

struct Facet : std::ctype<char>
{
    using ParentT = std::ctype<char>;

    Facet(std::size_t refs = 0) : ParentT(make_table(), false, refs) {}

    static const mask* make_table()
    {
        static mask char_table[table_size];
        static int fake = (std::copy(classic_table(), classic_table() + table_size, char_table),
                           (void)fake, 0);

        char_table[','] |= space;

        return char_table;
    }
};

std::list<int> parse_raw_data(const std::string& raw_data)
{
    std::istringstream iss{raw_data};
    iss.imbue(std::locale{iss.getloc(), new Facet{}});

    std::list<int> data{};

    using ISIt = std::istream_iterator<int>;
    std::copy(ISIt{iss}, ISIt{}, std::back_inserter(data));

    return data;
}

int main()
{
    const fs::path DATA_PATH{"data.txt"};

    std::string raw_data = read_file(DATA_PATH);

    if(raw_data.empty())
    {
        std::cout << "File 'data.txt' not found or empty. Terminate..." << std::endl;
        return 0;
    }

    std::list<int> data = parse_raw_data(raw_data);

    std::cout << "Sum of indexes that satisfies specified propery: " << calc_answer(data) << std::endl;

    return 0;
}

Read it right away in std::list<int>:

#include <iostream>
#include <list>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <sstream>
#include <iterator>
#include <string>
#include <experimental/filesystem>

namespace fs = std::experimental::filesystem;

uint64_t calc_answer(const std::list<int>& list)
{
    int left_sum = 0;
    int right_sum = std::accumulate(list.begin(), list.end(), 0);

    uint64_t index_sum = 0;
    int curr_index = 0;

    std::for_each(list.begin(), list.end(), [&] (int val) {
        right_sum -= val;

        if(left_sum == right_sum)
            index_sum += curr_index;

        left_sum += val;

        ++curr_index;
    });

    return index_sum;
}

std::list<int> read_file(const fs::path& file_path)
{
    if(!fs::exists(file_path))
        return std::list<int>{};

    std::ifstream infile{file_path.string()};

    std::list<int> data{};

    std::string number{""};
    while(std::getline(infile, number, ','))
        data.push_back(std::stoi(number));

    return data;
}

int main()
{
    const fs::path DATA_PATH{"data.txt"};

    std::list<int> data = read_file(DATA_PATH);

    if(data.empty())
    {
        std::cout << "File 'data.txt' not found or empty. Terminate..." << std::endl;
        return 0;
    }

    std::cout << "Sum of indexes that satisfies specified propery: "
              << calc_answer(data) << std::endl;

    return 0;
}

I'm not sure which version of solution is more effective

\$\endgroup\$
13
  • 4
    \$\begingroup\$ Most of the time std::vector is faster than std::list. I don't spot any reason for using std::list here, I could be wrong. The function std::list<int> read_file(const fs::path& file_path) can be changed to bool read_file(const fs::path& file_path, std::list<int> &data) to avoid making a copy. \$\endgroup\$ Oct 18, 2017 at 7:44
  • 1
    \$\begingroup\$ "allocation of a solid piece of memory of this size is costly" Not on x64; in any case, if that's your concern then you should be using std::deque; std::list is almost never the right answer. \$\endgroup\$
    – ildjarn
    Oct 18, 2017 at 7:57
  • 2
    \$\begingroup\$ Also consider that std::list is going to require 2-3x the memory as std::vector, and the allocations are all going to be very small; in addition to the additional memory consumption, this is terrible for memory fragmentation in real scenarios. Again, never list. ;-] \$\endgroup\$
    – ildjarn
    Oct 18, 2017 at 7:59
  • 1
    \$\begingroup\$ Perhaps edit to be a bit more specific on the input format. From reading the code, it appears that you're expecting comma-separated decimal values, perhaps over several lines, and delimited by end-of-file - is that correct? \$\endgroup\$ Oct 18, 2017 at 9:58
  • 3
    \$\begingroup\$ @sm4ll_3gg : It consumes a lot of memory since it's node-based; it's slow because it's node-based; and it has exactly zero upsides for this problem. You need a compelling reason to use list, not to avoid it – it's good for solving one or two very specific problems, and you don't have those problems here. \$\endgroup\$
    – ildjarn
    Oct 18, 2017 at 10:03

1 Answer 1

1
\$\begingroup\$

The two-pass algorithm looks like a good choice (although it's unclear why you're using std::list - change that to std::vector or add a comment to justify it).

Some comments:

Think about the ranges of the integer types

Since you have many int inputs, you will likely need something larger to store the accumulated sum:

long left_sum = 0;
long right_sum = std::accumulate(list.begin(), list.end(), 0L);

When reading into string, parse each line separately

std::string read_file() could produce a very large string. Instead, we could read a line at a time, and add the elements it contains, much as in the second implementation.

\$\endgroup\$
1
  • \$\begingroup\$ You are right, the list is not needed. I will take into account your recommendations. Thank you very much! \$\endgroup\$
    – sm4ll_3gg
    Oct 18, 2017 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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