Last active
October 14, 2019 03:29
-
-
Save kirkdrichardson/1df653a9a71a17e78e58397c040033ca to your computer and use it in GitHub Desktop.
Multiple Pointer Pattern (closing walls variation) - algorithm challenge
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Multiple Pointer Pattern Challenge 👻 closing in on the middle 👻 | |
| * | |
| * see live at https://dartpad.dartlang.org/1df653a9a71a17e78e58397c040033ca | |
| * | |
| * Write a fx called sumZero which accepts a sorted array of integers. | |
| * The fx should find the first pair where the sum is 0. | |
| * | |
| * | |
| * sumZero([-3, -2, -1, 0, 1, 2, 3]); // [-3, 3] | |
| * sumZero([-2, 0, 1, 3]); // no match | |
| * sumZero([1, 2, 3]); // no match | |
| * | |
| * */ | |
| void main() { | |
| Function pass = (bool shouldFindMatch, bool didFindMatch) => shouldFindMatch == didFindMatch ? 'Pass' : 'Fail'; | |
| Function formatMessage = (int testNumber, bool shouldPass, Optional<List<int>> result) { | |
| print("""Test $testNumber: ${pass(shouldPass, result.present)}! | |
| Match was ${result.present ? 'found: ${result.value}' : 'not found'} | |
| """); | |
| }; | |
| Optional<List<int>> result; | |
| result = sumZero([-3, -2, -1, 0, 1, 2, 3]); | |
| formatMessage(1, true, result); | |
| result = sumZero([-3, -2, -1, 0, 1, 4, 5, 6, 88, 90]); | |
| formatMessage(2, true, result); | |
| result = sumZero([-2, 0, 1, 3]); | |
| formatMessage(3, false, result); | |
| result = sumZero([1, 2, 3]); | |
| formatMessage(4, false, result); | |
| result = sumZero([88, -88]); | |
| formatMessage(5, true, result); | |
| result = sumZero([99]); | |
| formatMessage(5, false, result); | |
| result = sumZero([-5, -4, -3, -2, -1, 0, 1, 22, 33, 44, 55]); | |
| formatMessage(6, true, result); | |
| result = sumZero([-5, -4, -3, -2, 0, 1, 22, 33, 44, 55]); | |
| formatMessage(7, false, result); | |
| } | |
| Optional<List<int>> sumZero(List<int> list) { | |
| // Create our return value with a default | |
| Optional<List<int>> container = Optional(false, null); | |
| // If the passed list is null or less than 2 items, early return. | |
| if (list == null || list.length < 2) return container; | |
| int beginning = 0; | |
| int end = list.length -1; | |
| int sum; | |
| // For the following list, our pointers will begin in the positions below. | |
| // [-3, -2, -1, 0, 1, 2, 3, 4] | |
| // ^ ^ (starting position) | |
| // ^ ^ (if sum is greater than 0, move end pointer left) | |
| // ^ ^ ( if sum is less than 0, move beginning pointer right) | |
| while (beginning < end) { | |
| sum = list[beginning] + list[end]; | |
| if (sum == 0) { | |
| container.present = true; | |
| container.value = [list[beginning], list[end]]; | |
| return container; | |
| } else if (sum > 0) end--; | |
| else if (sum < 0) beginning++; | |
| else throw new Exception('Error traversing list!'); | |
| } | |
| return container; | |
| } | |
| class Optional<T> { | |
| bool present; | |
| T value; | |
| Optional(bool present, T value) { | |
| this.present = present; | |
| this.value = value; | |
| } | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment