CODEWITHSUNDEEP
c++algorithmvectorstl
sunny
sunny

Reputation: 3891

Ways to 'vectorize' this repetitive C++ code?

I saw this code in a HackerRank challenge solution, and I'm wondering whether there's a way to make it more efficient and/or aesthetically appealing. It's counting all the permutations of a bunch of digits, where there are x 4's, y 5's, and z 6's. For this reason, the code gets quite repetitive:

int cnt[101][101][101];

int solve1(int x,int y,int z){
    if(x <= 0 && y <= 0 && z <= 0)
        return 1 ;
    int &ret = cnt[x][y][z] ;
    if(ret != -1) return ret ;
    ret = 0 ;
    if(x)
        ret += solve1(x-1,y,z) ;
    if(ret >= mod) ret -= mod ; 
    if(y)
        ret += solve1(x,y-1,z) ;
    if(ret >= mod) ret -= mod ; 
    if(z)
        ret += solve1(x,y,z-1) ;
    if(ret >= mod) ret -= mod ; 
    return ret ;
}

Do STL containers or algorithms offer a way to make this less repetitive and/or more efficient?

Considered and rejected: Pass a vector to solve() rather than many integers and then use accumulate to collect ret while modifying each vector element (x, y, z as vector elements) and recalling solve on modified copy of original vector input. But this just creates a whole bunch of vectors without any clear counterbalancing improvement. Also, I haven't thought out the accumulate application so presumably that part is way off/not possible.

Thanks for any suggestions.

Upvotes: 0

Views: 147

Answers (2)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275385

Sort the x y z, and the memoization is far more effective:

int cnt[101][101][101]={0};
int solve1(std::array<int,3> idx){
  std::sort(idx.begin(),idx.end());
  int x=idx[0],y=idx[1],z=idx[2];

  if(x <= 0 && y <= 0 && z <= 0) return 1;
  int &ret = cnt[x][y][z];
  if(ret != -1) return ret;
  ret = 0;
  auto f=[&](int x,int y,int z){
    ret += solve1({{x-1,y,z}});
    if(ret >= mod) ret -= mod;
  };
  if(x)f(x-1,y,z);
  if(y)f(x,y-1,z);
  if(z)f(x,y,z-1);
  return ret;
}
int solve1(int x,int y,int z){
  return solve1({{x,y,z}});
}

Upvotes: 0

David Schwartz
David Schwartz

Reputation: 182763

With c++11, you can replace:

if(x)
    ret += solve1(x-1,y,z) ;
if(ret >= mod) ret -= mod ; 
if(y)
    ret += solve1(x,y-1,z) ;
if(ret >= mod) ret -= mod ; 
if(z)
    ret += solve1(x,y,z-1) ;
if(ret >= mod) ret -= mod ;

With:

auto func = [](int&ret, int x, int y, int z)
{
    ret += solve1(x, y, z);
    if (ret >= mod) ret -= mod;
    return ret;
};
if (x) func (ret, x-1, y, z);
if (y) func (ret, x, y-1, z);
if (z) func (ret, x, y, z-1);

You could also just use a function.

Upvotes: 2

Related Questions