Question: https://codility.com/demo/take-sample-test/dwarfs_rafting/
Question Name: Dwarfs-Rafting or DwarfsRafting
Need some simple mathematical knowledge. The code is unnecessarily long. A 2-d array is better to write much shorter code. However, I keep the long version for better readability.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | def solution(N, S, T): quadrant_left_front = (N // 2) * (N // 2) quadrant_left_back = (N // 2) * (N // 2) quadrant_right_front = (N // 2) * (N // 2) quadrant_right_back = (N // 2) * (N // 2) boundary = N // 2 # Compute how many slots are available in each quadrant. for barrel in S.split(): # Adjust to 0-based index. row = int(barrel[:-1]) - 1 column = ord(barrel[-1]) - ord("A") if row < boundary: # The barrel is in the front. if column < boundary: # The barrel is in the left. quadrant_left_front -= 1 else: # The barrel is in the right. quadrant_right_front -= 1 else: # The barrel is in the back. if column < boundary: # The barrel is in the left. quadrant_left_back -= 1 else: # The barrel is in the right. quadrant_right_back -= 1 # lf is short for left front, etc. # To keep balance, we need: # 1. weight_lf + weight_lb = weight_rf + weight_rb # 2. weight_lf + weight_rf = weight_rf + weight_rb # Solve the equations and we can get the answer: # 1. weight_lf = weight_rb # 2. And weight_rf = weight_lb allowance_lf = min(quadrant_left_front, quadrant_right_back) allowance_rb = min(quadrant_left_front, quadrant_right_back) allowance_lb = min(quadrant_left_back, quadrant_right_front) allowance_rf = min(quadrant_left_back, quadrant_right_front) # Minus the seats, which are already occupied by dwarfs. for dwarf in T.split(): # Adjust to 0-based index. row = int(dwarf[:-1]) - 1 column = ord(dwarf[-1]) - ord("A") if row < boundary: # The dwarf is in the front. if column < boundary: # The dwarf is in the left. allowance_lf -= 1 if allowance_lf < 0: return -1 else: # The dwarf is in the right. allowance_rf -= 1 if allowance_rf < 0: return -1 else: # The dwarf is in the back. if column < boundary: # The dwarf is in the left. allowance_lb -= 1 if allowance_lb < 0: return -1 else: # The dwarf is in the right. allowance_rb -= 1 if allowance_rb < 0: return -1 return allowance_lf + allowance_rb + allowance_lb + allowance_rf |
100% in Python
This is weird, I try to code your solution in golang, but it didn’t work.
well~ I do not know much golang…. But my solution should be language independent 🙂
I am interested what is the technique you used to come up with the solution.
I have taken data and structures class in college.
I just do not seem to have the skills to think up a solution.
Can you suggest some courses , or links that would help me figure out the algorithms like you do?
Open course Algorithms from Princeton University is a wonderful start point. Then practice, practice, and practice more.
slightly modification to simplify the if else part
Can someone explain what is wrong with my solution in C++ ?
Ok fixed it. gives 100%: