- Prepare
- Data Structures
- Stacks
- Equal Stacks
- Discussions
Equal Stacks
Equal Stacks
+ 0 comments simple js solution
function equalStacks(h1, h2, h3) { let sum1 = sum(h1) let sum2 = sum(h2) let sum3 = sum(h3) let i1 = 0, i2 = 0, i3 = 0; while (sum1 !== sum2 || sum2 !== sum3 || sum3 !== sum1) { if (sum1 >= sum2 && sum1 >= sum3) { sum1 -= h1[i1]; i1++; } else if (sum2 >= sum1 && sum2 >= sum3) { sum2 -= h2[i2]; i2++; } else if (sum3 >= sum1 && sum3 >= sum2) { sum3 -= h3[i3]; i3++; } } return sum1; }
+ 0 comments c# solution
public static int equalStacks(List<int> h1, List<int> h2, List<int> h3) { Queue<int> stack = new Queue<int>(h1); Queue<int> stack2 = new Queue<int>(h2); Queue<int> stack3 = new Queue<int>(h3); int tam1 = stack.Sum(); int tam2 = stack2.Sum(); int tam3 = stack3.Sum(); while(!(tam1 == tam2 && tam2 == tam3 && tam3 == tam1)) { if(tam1 > tam2) { if (stack.Count == 0) { tam1 = 0; } else { tam1 = tam1 - stack.First(); stack.Dequeue(); } } if(tam2 > tam3) { if (stack2.Count == 0) { tam2 = 0; } else { tam2 = tam2 - stack2.First(); stack2.Dequeue(); } } if(tam3 > tam1) { if (stack3.Count == 0) { tam3 = 0; } else { tam3 = tam3 - stack3.First(); stack3.Dequeue(); } } } return tam1; }
+ 0 comments Here are some Python 3 solutions:
#!/bin/python3 from collections import deque from os import environ def equalStacks1(*args) -> int: """Find the maximum possible height such that all stacks are of equal height.""" heights = [*map(sum, args)] while not all(height == heights[0] for height in heights): heights[(i := heights.index(max(heights)))] -= args[i].popleft() return heights[0] def equalStacks2(h1: deque[int], h2: deque[int], h3: deque[int]) -> int: """Find the maximum possible height such that all 3 stacks are of equal height.""" s1, s2, s3 = map(sum, (h1, h2, h3)) while not (s1 == s2 == s3): if s1 == (tallest := max(s1, s2, s3)): s1 -= h1.popleft() elif s2 == tallest: s2 -= h2.popleft() else: s3 -= h3.popleft() return s3 class Stack(deque): """Stack that tracks height""" __slots__ = {"height"} def __init__(self, values: deque[int]) -> None: """Initialize a stack and calculate height.""" super().__init__(values) self.height = sum(values) def __repr__(self) -> str: """Return a representation of a Stack object.""" return f"{self.__class__.__name__}(values={list(self)})" def pop(self) -> int: """Pop the first index and update height.""" try: popped = self.popleft() except IndexError: return None self.height -= popped return popped def equalStacks3(*args) -> int: """Find the maximum possible height such that all stacks are of equal height. Uses a Stack class that tracks height """ stacks: list[Stack] = sorted( map(Stack, args), key=(height := lambda stack: stack.height) ) while (min_height := stacks[0].height) != (max_height := stacks[-1].height): while max_height > min_height: max_height -= stacks[-1].pop() stacks.sort(key=height) return max_height def equalStacks_recursive(*args) -> int: """ Recursively find the maximum possible height such that all stacks are of equal height. Uses a Stack class that tracks height """ height = args[0].height if all(stack.height == height for stack in args): return height args.sort(key=lambda stack: stack.height) args[-1].pop() return equalStacks_recursive(*stacks) def equalStacks4(*args) -> int: """Find the maximum possible height such that all stacks are of equal height. Uses a recursive strategy """ return equalStacks_recursive(*map(Stack, args)) def equalStacks(*args, strategy=equalStacks4) -> int: """ Using the given strategy, find the maximum possible height such that all 3 stacks are of equal height. Also asserts that the strategies return the same result """ assert ( equalStacks1(*args) == equalStacks2(*args) == equalStacks3(*args) == equalStacks4(*args) ) return strategy(*args) if __name__ == "__main__": input() result: int = equalStacks( *map( lambda integers: deque(map(int, integers.rstrip().split())), (input(), input(), input()), ) ) with open(environ["OUTPUT_PATH"], "w") as f: f.write(f"{result}\n")
All four strategies pass all test cases. All strategies except the second are also agnostic to the number of stacks. The third and fourth strategies utilize an OOP approach. The fourth strategy is recursive. The common theme is that stack heights are summed just once and then updated by the cylinder height each time a cylinder is popped from the tallest stack.
I also refactored the
if __name__ == "__main__":
block. Notably,deque.popleft()
is much faster thanlist.pop(0)
.
+ 1 comment A little bit of fun:
public static Integer totalAll(List<Integer> list) { int total = 0; for (Integer num : list) { total += num; } return total; } public static int equalStacks(List<Integer> h1, List<Integer> h2, List<Integer> h3) { if (h1.size() == 0 || h2.size() == 0 || h3.size() == 0) { return 0; } int total1 = totalAll(h1); int total2 = totalAll(h2); int total3 = totalAll(h3); while (total1 != total2 || total2 != total3) { if (total1 > total2 || total1 > total3) { int removed = h1.remove(0); total1 -= removed; } if (total2 > total1 || total2 > total3) { int removed = h2.remove(0); total2 -= removed; } if (total3 > total1 || total3 > total2) { int removed = h3.remove(0); total3 -= removed; } } return total1; }
+ 0 comments include
using namespace std;
string ltrim(const string &); string rtrim(const string &); vector split(const string &);
/* * Complete the 'equalStacks' function below. * * The function is expected to return an INTEGER. * The function accepts following parameters: * 1. INTEGER_ARRAY h1 * 2. INTEGER_ARRAY h2 * 3. INTEGER_ARRAY h3 */ int min3(int a,int b,int c) { a=min(a,b); a=min(a,c); return a; } int equalStacks(vector h1, vector h2, vector h3) { reverse(h1.begin(),h1.end()); reverse(h2.begin(),h2.end()); reverse(h3.begin(),h3.end());
stackc1;
stackc2; stackc3; int th1=0; int th2=0; int th3=0; for(int i=0;i c2.push(h2[i]); } for(int i=0;im) {
th1-=c1.top(); c1.pop(); } while(th2>m) { th2-=c2.top(); c2.pop(); } while(th3>m) { th3-=c3.top(); c3.pop(); } //cout<> return n; }int main() { ofstream fout(getenv("OUTPUT_PATH"));
string first_multiple_input_temp; getline(cin, first_multiple_input_temp); vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp)); int n1 = stoi(first_multiple_input[0]); int n2 = stoi(first_multiple_input[1]); int n3 = stoi(first_multiple_input[2]); string h1_temp_temp; getline(cin, h1_temp_temp); vector<string> h1_temp = split(rtrim(h1_temp_temp)); vector<int> h1(n1); for (int i = 0; i < n1; i++) { int h1_item = stoi(h1_temp[i]); h1[i] = h1_item; } string h2_temp_temp; getline(cin, h2_temp_temp); vector<string> h2_temp = split(rtrim(h2_temp_temp)); vector<int> h2(n2); for (int i = 0; i < n2; i++) { int h2_item = stoi(h2_temp[i]); h2[i] = h2_item; } string h3_temp_temp; getline(cin, h3_temp_temp); vector<string> h3_temp = split(rtrim(h3_temp_temp)); vector<int> h3(n3); for (int i = 0; i < n3; i++) { int h3_item = stoi(h3_temp[i]); h3[i] = h3_item; } int result = equalStacks(h1, h2, h3); fout << result << "\n"; fout.close(); return 0;
}
string ltrim(const string &str) { string s(str);
s.erase( s.begin(), find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace))) ); return s;
}
string rtrim(const string &str) { string s(str);
s.erase( find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(), s.end() ); return s;
}
vector split(const string &str) { vector tokens;
string::size_type start = 0; string::size_type end = 0; while ((end = str.find(" ", start)) != string::npos) { tokens.push_back(str.substr(start, end - start)); start = end + 1; } tokens.push_back(str.substr(start)); return tokens;
}
Sort 1059 Discussions, By:
Please Login in order to post a comment