Balanced Brackets

Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).

For example, given the string "([])", you should return true.
Given the string "([)]" or "((()", you should return false.

Business Rules/Errata

• The only characters considered to be 'brackets' are (, ), [, ], {, and }.
• Your input will always be a string.
• An empty string is considered balanced (return true).
• Your string may contain characters that are not brackets.

Examples

balanced_brackets("[[]]({}[])");       // true
balanced_brackets("[[({}[])");         // false
balanced_brackets("");                  // true
balanced_brackets("(5 * 3) + 4");  // true

Square Maze

Given a square (NxN) matrix of '0's and '1's, determine how many ways the matrix can be traversed from the top left element to the bottom right element.

Business Rules/Errata

• Data Structure Required: 2D Matrix
• Assume the matrix represents a 2-dimensional map.
• You may only move up, down, left, and right in the matrix, not diagonally.
• You may only traverse matrix elements that are '0' (representing an empty space). A '1' represents an impassible barrier.
• The top left and bottom right corner will always be '0'.
• If there is no path from the top left to the bottom right, return 0. Otherwise, return the number of viable paths as an integer.

Examples

input = [[0, 0, 1],
         [0, 0, 1],
         [1, 0, 0]]

count_paths(input)  // 2

In this case, there are two viable paths, starting at the top left:

• right, down, down, right
• down, right, down, right

Potential Palindrome

Given a string, determine whether any permutation of it is a palindrome. A palindrome is any string that can be read the same both forwards and backwards, such as "kayak".

Business Rules/Errata

• You only need to determine whether it is possible to make a palindrome, you do not need to return an example of the palindrome.
• Any input that is not a string should be treated as a string, if possible.
• An empty string is not a palindrome.

Examples

can_make_palindrome("carrace");  // True

The string carrace can be rearranged to make racecar, a palindrome.

Single and Ready to Mingle

Given an array of integers in which two elements appear exactly once and all other elements appear exactly twice, find the two elements that appear only once.

Business Rules/Errata

• You can assume that the input will always include at least two and exactly two elements that appear only once.
• You may not assume that the list will be sorted ahead of time.
• Extra Challenge: Can you complete this puzzle in linear time and constant space?
• Extra Extra Challenge: Can you make your solution generic over other input types?

Examples

input = [2, 4, 6, 8, 10, 2, 6, 10];
find_singles(input)  // [4, 8]

input = [1, 2, 3, 2, 1, 4, 4, 6, 7, 8, 7, 6, 9, 9];
find_singles(input)  // [3, 8]

A Box in a Box

Given a pair of rectangles, determine whether one of the rectangles is completely contained within the other rectangle. You will be given each rectangles top-left coordinate in an x/y plane, the rectangle's width, and the rectangle's height. One rectangle is "completely contained" by a rectangle that completely covers it, if viewed from above the plane. This puzzle should be solved using an Object-Oriented approach.

Business Rules/Errata

• Data Structure Required: Rectangle You should produce and compare Rectangle objects in your solution, not the raw rectangle measurements.
• The rectangle dimensions will be given in an array, in the format [(top left x coordinate), (top left y coordinate), (width), (height)].
• The units of width and height are irrelevant and can be ignored.
• The coordinate system for this challenge is 2-dimensional, with x increasing from left to right, and y increasing from top to bottom.
• Your final result should include a function that, given two sets of rectangle dimensions, returns a boolean value,
• Your function should return false if the two rectangles only partially overlap.

Examples

Example 1

rectangle1 = [1, 4, 3, 3]
rectangle2 = [0, 3, 2, 1]
rectanglesOverlap(rectangle1, rectangle2)  // false

Example 2

rectangle1 = [1, 4, 3, 3]
rectangle2 = [0, 3, 4, 4]
rectanglesOverlap(rectangle1, rectangle2)  // true

Example 3

rectangle1 = [1, 4, 3, 3]
rectangle2 = [0, 3, 3, 3]
rectanglesOverlap(rectangle1, rectangle2)  // false

Sum of Squares

Given a positive integer n, find the smallest number of squared integers which sum to n (i.e. n = x² + y² should yield 2).

Business Rules/Errata

• Any attempt to provide non-integer, non-positive input should return an error.
• Return only the count of squared integers that sum to n, not the list of integers.
• Remember that 1² = 1.

Examples

count_squared_addends(13);  // 2
count_squared_addends(27);  // 3

• For n = 13: 3² + 2² = 9 + 4 = 13
• For n = 27:
  • 3² + 3² + 3² = 9 + 9 + 9 = 27
  • 5² + 1² + 1² = 25 + 1 + 1 = 27

Coin Counter

You are given n fair coins, and you flip all at the same time. Every time a coin comes up 'tails', it is removed from play. The ones that come up 'heads', you will flip again on the next round. Write a function that, given n, returns the number of rounds you'd expect to play until only one coin remains.

Business Rules/Errata

• Each coin is fair, meaning it is equally likely to come up as either side on any given round.
• Your answer should be rounded to the nearest whole number, since it is impossible to play part of a round.
• Extra Challenge: What is the most time-efficient solution you can devise?
• Extra Challenge: Can you implement this game for dice, instead of coins?

Examples

count_coin_rounds(2)        // 1
count_coin_rounds(100)    // 7
count_coin_rounds(1000)  // 10

Jump Around

Starting from 0 on a number line, you would like to make a series of jumps that lead to the integer N. On the ith jump, you may move exactly i places to the left or right (1st jump -> 1 place, 2nd jump -> 2 places, etc.). Determine the smallest number of jumps needed to get from 0 to N.

Business Rules/Errata

• The number line should be assumed to extend infinitely in both directions. N may be either positive or negative.
• Keep in mind that you should identify the number of jumps, not the path. The result of your function should be a positive integer.
• There is no guarantee that all the jumps to reach a given number will be in the same direction.
• All test cases return an answer, you should assume that every number can be reached using this strategy.

Examples

This section should provide examples of expected inputs/outputs like so:

jump_to(0)   // 0: start at 0
jump_to(1)   // 1: 0 -> 1
jump_to(2)   // 3: 0 -> 1 -> -1 -> 2
jump_to(-2)  // 3: 0 -> -1 -> 1 -> -2
jump_to(175) // 21

Boustrophedon

In Ancient Greece, it was common to write text with the first line going left to right, the second line going right to left, and continuing to go back and forth. This style was called "boustrophedon".

Given a binary tree, write an algorithm to print the nodes in boustrophedon order.

Business Rules/Errata

• Data Structure Required: Binary Tree
• Your function should take a binary tree as an input and output a list of the values in the binary tree.
• The values in the binary tree will be single characters.
• The input binary tree will have three member variables or fields that are accessible to you: value, left, and right.
  • value will contain the value in that tree node, and will be the value you output in your result.
  • left will contain the tree node to the left of the current node.
  • right will contain the tree node to the right of the current node.
• You may assume that your tree is 'complete' and symmetrical, that is, that each level of the tree contains values at each position (no blank spaces).
• The nodes in the bottom-most 'layer' of the tree will not contain a left or right value.

Examples

//       a
//      / \
//     b   c
//   / |   | \
//  d  e   f  g

input = {'a', {'b', {'d'}, {'e'}}, {'c', {'f'}, {'g'}}}
boustrophedon(input) // ['a', 'c', 'b', 'd', 'e', 'f', 'g']

//         _____ p _____
//        /             \
//     _ o _           _ r _
//    /     \         /     \
//   g       n       o       s
//  / \     / \     / \     / \
// n   o   i   t   a   c   i   t

input = {'p', {'o', {'g', {'n'}, {'o'}}, {'n', {'i'}, {'t'}}}, {'r', {'o', {'a'}, {'c'}}, {'s', {'i'}, {'t'}}}}
boustrophedon(input) // ['p', 'r', 'o', 'g', 'n', 'o', 's', 't', 'i', 'c', 'a', 't', 'i', 'o', 'n']

Participation

All Hacktoberfest solutions should be provably correct. That is, solution submissions should either include the unit tests from the original challenge (implemented in your language of choice) or at least print out the expected answers when run by the maintainers. Solutions that do not meet these criteria may be rejected, or flagged as 'invalid' or 'spam' in egregious cases. This can result in your PR not counting towards your Hacktoberfest participation or becoming ineligible to participate in Hacktoberfest. Violations of our Code of Conduct will be reported, and will also render you ineligible to participate in Hacktoberfest. Please be respectful of the maintainers' and other participants' time by doing your best to submit real solutions to the puzzles. Thanks, and welcome to our learning community!

Challenge

Intervening Verbiage

Language

Complete this challenge using a Bash/Shell script.

Approach

Shell scripts expect to take a string as input and echo to stdout as output. For added credibility, prove your solution with unit tests. One option for unit testing Bash scripts is bats.

Tracing Triangles

You are given an array of arrays of integers, where each array corresponds to a row in a triangle of numbers. For example, [[1], [2, 3], [1, 5, 1]] represents the triangle:

  1
 2 3
1 5 1

We define a path in the triangle to start at the top and go down one row at a time to an adjacent value, eventually ending with an entry on the bottom row. For example, 1 -> 3 -> 5. The weight of the path is the sum of the entries.

Write a program that returns the weight of the maximum weight path.

Business Rules/Errata

• The input will be a nested array of integer arrays.
• Each sub-array should be listed in order and include one more value than the previous sub-array (forming a triangle). If the input does not meet these criteria, return an error.
• If the input array is empty, return 0.
• If the input array contains only a single sub-array, return the value in that sub-array. For example: [[5]] yields 5.
• You do not need to return the path followed, simply the largest path weight.

Examples

//   1
//  2 3
// 1 5 1

input = [[1], [2, 3], [1, 5, 1]]
longest_path(input)  // 9 (1 -> 3 -> 5)

//    6
//   4 4
//  1 2 1
// 5 4 3 2

input = [[6], [4, 4], [1, 2, 1], [5, 4, 3, 2]]
longest_path(input)  // 16, either (6 -> 4 -> 1 -> 5) or (6 -> 4 -> 2 -> 4)

The 24 Game

The 24 game is played as follows. You are given a list of four integers, each between 1 and 9, in a fixed order. By placing the operators +, -, *, and / between the numbers, and grouping them with parentheses, determine whether it is possible to reach the value 24.

For example, given the input [5, 2, 7, 8], you should return True, since (5 * 2 - 7) * 8 = 24.

Write a function that plays the 24 game.

Business Rules/Errata

• Your input will always consist of an array of four integers. These integers do not all need to be positive.
• Your function should return a boolean value indicating whether the input can be combined to produce 24. You do not need to produce the formula that yields 24.
• The results of any division operation should be rounded to the nearest integer. So, 3 / 2 = 2, not 3 / 2 = 1.
• The result of division by zero should be zero, not undefined.

Examples

play([5, 2, 7, 8]);   // True -> (5 * 2 - 7) * 8 = 24
play([2, 4, 8, 10]);  // True -> 2 + 4 + 8 + 10 = 24
play([5, 0, 4, 4]);   // True -> (5 + 0) * 4 + 4 = 24
play([47, 2, 0, 0]);  // True -> (47 / 2) + 0 + 0 = 24
play([1, 5, 7, 19]);  // False, no combinations yield 24

Participation

All Hacktoberfest solutions should be provably correct. That is, solution submissions should either include the unit tests from the original challenge (implemented in your language of choice) or at least print out the expected answers when run by the maintainers. Solutions that do not meet these criteria may be rejected, or flagged as 'invalid' or 'spam' in egregious cases. This can result in your PR not counting towards your Hacktoberfest participation or becoming ineligible to participate in Hacktoberfest. Violations of our Code of Conduct will be reported, and will also render you ineligible to participate in Hacktoberfest. Please be respectful of the maintainers' and other participants' time by doing your best to submit real solutions to the puzzles. Thanks, and welcome to our learning community!

Challenge

Single and Ready to Mingle

Language

Java

Approach

For added credibility, prove your solution with unit tests. Check out any of our Java-based challenges for an IDE-agnostic testing setup. or use the built-in tools from your favorite IDE.

After #135 the only thing missing on our Community tab is having a PR template. I feel like this would help contributors, mainly for solutions.

ZigZag Print

Given a string and a number of lines k, print the string in zigzag form. In zigzag, characters are printed out diagonally from top left to bottom right until reaching the kth line, then back up to top right, and so on.

For example, given the sentence "thisisazigzag" and k = 4, you should print:

t     a     g
 h   s z   a
  i i   i z
   s     g

Business Rules/Errata

• The input will include a string and a positive integer between 2 and 10.
• Your output should be in the form of a string that, when printed to console, will yield the desired pattern. See examples below.
• Your string may contain any valid ASCII letter, number, space, or printable special character ('!', '@', '#', '$', etc.). Importantly, control characters such as '\t', '\n', '\r', '\v', etc. will not be included.
• Spaces should be included in your output pattern.

Examples

printzigzag("bismarcks", 3)  // "b   a   s\n i m r k \n  s   c  "
b   a   s
 i m r k
  s   c


printzigzag("thisisazigzag", 4)  // "t     a     g\n h   s z   a \n  i i   i z  \n   s     g   "
t     a     g
 h   s z   a
  i i   i z
   s     g


printzigzag("ilovechickenandwaffles", 5)  // "i       c       a     \n l     i k     w f    \n  o   h   e   d   f   \n   v c     n n     l s\n    e       a       e "
i       c       a
 l     i k     w f
  o   h   e   d   f
   v c     n n     l s
    e       a       e

We need to decide on a directory structure. There is a proposal by @drkennetz that we separate challenges from solutions

from Slack

Format could be:

./CodingDojo/questions/
    ./03-26-2021/question.MD
    ./04-02-2021/question.MD./CodingDojo/answers/
    ./03-26-2021/answer.py, answer.js, answer.java, answer.rb
./CodingDojo/answers/
    ./03-26-2021/answer.py, answer.js, answer.java, answer.rb

(edited to properly display format)

Find Three Largest Numbers

Write a function that takes in an array of at least three integers and, without sorting the input array, returns a sorted array of the three largest integers in the input array. The function should return duplicate integers if necessary.

Business Rules/Errata

• The input array should have at least three integers. If it does not, you should return a null value.
• You may not sort the input array
• The function should handle duplicate integers; for example [10, 5, 9, 10, 12] should return [10, 10, 12]
• Constant space -> you will return a new array of 3 integers, and this will be the only new data structure you create.
• Linear time -> you should solve this problem by only passing through the array a single time.

Examples

This section should provide examples of expected inputs/outputs like so:

findThreeLargestNumbers([141, 1, 17, -7, -17, -27, 18, 541, 8, 7, 7]) -> [18, 141, 541]
findThreeLargestNumbers([11, -7, 5]) -> [-7, 5, 11]
findThreeLargestNumbers([1]) -> Null

Participation

All Hacktoberfest solutions should be provably correct. That is, solution submissions should either include the unit tests from the original challenge (implemented in your language of choice) or at least print out the expected answers when run by the maintainers. Solutions that do not meet these criteria may be rejected, or flagged as 'invalid' or 'spam' in egregious cases. This can result in your PR not counting towards your Hacktoberfest participation or becoming ineligible to participate in Hacktoberfest. Violations of our Code of Conduct will be reported, and will also render you ineligible to participate in Hacktoberfest. Please be respectful of the maintainers' and other participants' time by doing your best to submit real solutions to the puzzles. Thanks, and welcome to our learning community!

Challenge

Sum Arrays

Language

This challenge was originally set up for Ruby, but it looks like a Ruby solution was never submitted! Yikes! Solve this challenge in Ruby and fix that oversight for us, please.

Approach

Use the original unit tests!

Dictionary Decompression

Given a nested dictionary, flatten the dictionary such that the keys of the final result are namespaced with a period between the original keys leading to the value.

Business Rules/Errata

• Data Structure Required: Dictionary/Map/HashMap This challenge requires a language that supports a version of a Dictionary.
• Your function should be able to flatten dictionaries nested arbitrarily deeply.
• You can assume that none of the dictionary keys contain a period.
• The type of the dictionary values is not important to this exercise. Assume they will always be unsigned integers.

Example

nested_dict = {
  "key": 3,
  "foo": {
    "a": 5,
    "bar": {
      "baz": 8
    }
  }
}

result = flattenDictionary(nested_dict)
print(result)

{
  "key": 3,
  "foo.a": 5,
  "foo.bar.baz": 8
}

Intervening Verbiage

Given two words in a string of words, count the number of other words between the two words you are given.

Business Rules/Errata

• Your solution will take in three pieces of input: a string containing a space-separated list of words, and two other strings representing the first and second words, respectively.
• You may ignore all punctuation and capitalization.
• If your two words are not in the string of words, alert the user to an error.
• You should return a count of the words between your two words as an integer, not the words themselves.
• If your words appear multiple times in the list of words, count words that fall between the first instance of each.

Examples

list_of_words = "There was an old lady who lived in an outhouse";
count_words_between("lady", "outhouse", list_of_words)  // 4 
count_words_between("an", "outhouse", list_of_words)    // 6

• The words 'who', 'lived', 'in', 'an' appear between 'lady' and 'outhouse'.
• The words 'old', 'lady', 'who', 'lived', 'in', 'an' appear between the first instance of 'an' and 'outhouse'.

Sum Arrays

Given an array of values, return the sum of the values.

Business Rules/Errata

• Input must be an array.
• The array may be nested more than one level.
• All values must be integers.
• Solutions shall not use built in methods to flatten the array to one-dimension.

Examples

One dimension:

sum_of_array([1,2,3,4,5]) => 15

Two dimensions:

sum_of_array([1,2,[1,2,3],4,5]) => 18

n dimensions:

sum_of_array([1,[1,2,[3,4],5],[6,7]]) => 29

To help with people learning about our repository through Hacktoberfest, we should include a link to the meetup page for people to join us in the future.

Greedy Goblin

You are writing an AI for a 2D map game. Specifically, you are writing the AI for a Goblin, who only cares about one thing: money! Your goblin is somewhere in a 2D grid, and there are coins strewn about over the map. Because goblins are not very smart, your goblin should seek out the closest coin, go grab it, then move on to the next closest coin.

Given the position of all the coins and your current position, calculate the "optimal" path for your goblin, as described above. The closest coin to your goblin should be evaluated in terms of Manhattan distance. That is, the number of spaces the goblin will need to move up, down, left, or right to reach the coin.

For example, given the following input:

Goblin: (0, 2)
Coins: [(0, 4), (1, 0), (2, 0), (3, 2), (2, 4)]

represented by the below map, where your goblin is "G", coins are "o", and empty spaces are ".":

---------------------
| . | . | G | . | o |
---------------------
| o | . | . | . | . |
---------------------
| o | . | . | . | o |
---------------------
| . | . | o | . | . |
---------------------

you goblin will visit (0, 4) -> (2, 4) -> (3, 2) -> (2, 0) -> (1, 0).

Business Rules/Errata

• The "optimal" path is not really the shortest total travel distance, but the path to the next closest coin at each point.
• Because goblins are particularly dim, if at any point there are two coins equally close to the goblin. he will panic, drop all his coins, and run away in terror. You should return an empty list.
• Goblins cannot move diagonally, only in the four cardinal directions.
• Your input will consist of a (row, column) index pair as the goblin's starting space and a list of (row, column) pairs as the coin locations.
• You should return a list of (row, column) index pairs. These should be tuples if your language supports that, otherwise use an array or list of length 2.
• Indices may be negative.

Examples

goblin = (1, 1)
coins = [(1, 2), (-5, -5), (1, 3)]
goblin_path(goblin, coins) // [(1, 2), (1, 3), (-5, -5)]

goblin = (0, 2)
coins = [(0, 4), (1, 0), (2, 0), (3, 2), (2, 4)]
goblin_path(goblin, coins) // [(0, 4), (2, 4), (3, 2), (2, 0), (1, 0)]

goblin = (100, 100)
coins = [(99, 100), (101, 100), (100, 99), (100, 101)]
goblin_path(goblin, coins) // []  -- he panicked

Discussion has been going around as to how we handle the flow of week to week tasks in preparation for the next mob session.

Challenges

Challenges will be submitted as issues. Voting on these (👍) should be restricted to one vote per person each week.

Challenge will be posted on Friday (Monday may be tried as well) for the following week.

Solutions

• No solutions will be accepted in PR before the mob/meetup.
• The mob solution will be titled mob.[lang] in the solutions directory for that challenge.
• Solutions may be submitted by anyone after that solution is merged. Any and all solutions of this type will be named with the person's github username and the lang. My solutions will be submitted as xanderyzwich.py if they are in Python. These solutions will be submitted through Pull Request (PR) from the persons fork of the repository. Code reviewers can/will assist with forming the solution such that it can be understood by others and be displayed for learning purposes.

Sort Window

Given an array of integers out of order, determine the bounds of the smallest window that must be sorted in order for the entire array to be sorted. For example, given [3, 7, 5, 6, 9], you should return (1, 3).

Business Rules/Errata

• Your input will be an array of unsigned integers.
• An empty array is considered to be sorted.
• You should return an array, with the first element containing the 'start' of the window, and the second element containing the 'end' of the window.
• If your input array is already sorted, return an empty array.
• Note: Some of the elements inside the unsorted window may actually be in the correct order for the final sorted array.

Examples

sort_window([3, 7, 5, 6, 9]) // [2, 4]
sort_window([1, 2, 6, 5, 4]) // [3, 5]
sort_window([3, 2, 1, 4, 5]) // [1, 3]
sort_window([5, 4, 3, 2, 1]) // [1, 5]
sort_window([1, 2, 3, 4, 5]) // []
sort_window([1]) // []
sort_window([]) // []

They are currently multiple .gitignore files scattered throughout the challenges.
These files should be consolidated to one main .gitignore file and then the scattered files should be removed.

Weird Column Naming

Spreadsheets often use an alphabetical encoding for naming columns: "A", "B", "C", ..., "AA", "AB", ..., "ZZ", "AAA", "AAB", ....

Given a column number, return its alphabetical column id. For example, given 1, return "A". Given 27, return "AA".

Business Rules/Errata

• Your function should take an unsigned integer greater than 0. Return an error if a number 0 or less is given.
• Hint: Note that the format "A", "B", "C", ..., "AA", "AB", ..., "ZZ", "AAA", "AAB", .... does not support the concept of "zero".
• This challenge should be attempted with at Test-Driven Development (TDD) methodology. For more information on TDD, see this video.

Examples

to_spreadsheet_colname(1);     // "A"
to_spreadsheet_colname(27);    // "AA"
to_spreadsheet_colname(52);    // "AZ"
to_spreadsheet_colname(287);   // "KA"

Participation

All Hacktoberfest solutions should be provably correct. That is, solution submissions should either include the unit tests from the original challenge (implemented in your language of choice) or at least print out the expected answers when run by the maintainers. Solutions that do not meet these criteria may be rejected, or flagged as 'invalid' or 'spam' in egregious cases. This can result in your PR not counting towards your Hacktoberfest participation or becoming ineligible to participate in Hacktoberfest. Violations of our Code of Conduct will be reported, and will also render you ineligible to participate in Hacktoberfest. Please be respectful of the maintainers' and other participants' time by doing your best to submit real solutions to the puzzles. Thanks, and welcome to our learning community!

Challenge

Potential Palindrome

Language

Complete this challenge using a Bash/Shell script.

Approach

Shell scripts expect to take a string as input and echo to stdout as output. For added credibility, prove your solution with unit tests. One option for unit testing Bash scripts is bats.

PR's should reference the issue number for ease of review and closure.

Runs of Ones

Given a positive integer n, determine the length of the longest run of 1's in the binary representation of that integer.

Business Rules/Errata

• A run of 1's is any series of one or more 1's in a row, with no 0's in between. The first four characters in 11110101 are a run of 1's.
• There's no requirement related to what data type(s) should be used to store the binary representation of n.
• Target time complexity: O(n) (linear)
• Target space complexity: O(1) (constant)

Examples

longest_binary_run(156);   // 3
longest_binary_run(1979);  // 4
longest_binary_run(2731);  // 2
longest_binary_run(2185);  // 1

Monotonic Array

Write a function that takes in an array of integers and returns a Boolean representing whether the array is monotonic. An array is said to be monotonic if its elements, from left to right, are entirely non-increasing or entirely non-decreasing (don't worry, I'll make this very clear with examples!)

Arrays containing only the same element are also said to be monotonic because they are both entirely non-increasing and entirely non-decreasing.

Non-increasing elements aren't necessarily exclusively decreasing; they simply don't increase. Similarly, non-decreasing elements aren't necessarily exclusively increasing; they simply don't decrease.

Note that empty arrays and arrays of one element are monotonic.

Business Rules/Errata

• Your function should accept an input array and return a Boolean if the array is monotonic. The input array can be any length -- including 0!
• An array of length 0 or 1 is said to be monotonic.
• Subsequent numbers that are equal do not change the description of an array. For example, [1, 2, 3, 3] is an increasing monotonic array because the numbers are never decreasing.
• Arrays containing only the exact same element multiple times (IE duplicates) are monotonic.
• If an array is monotonic, the function should return True, otherwise it should return False.
• Bonus: You should be able to determine if an array is monotonic from a single pass through the array, one iteration through the array should be sufficient in the optimal solution.
• Bonus: The optimal solution also uses constant space - no intermediate data structures are required.
• Optimal: O(N) time | O(1) space - where N is the length of the array

Examples

is_monotonic([]) // True
is_monotonic([1]) // True
is_monotonic([1, 2]) // True
is_monotonic([2, 2, 2, 2]) // True
is_monotonic([-5, -4, -3, -2, -1, 0, 1]) // True
is_monotonic([2, 1, 2, 3, 4, 5]) // False
is_monotonic([1, 1, 0, 0, -1, -1, -2, -2]) // True
is_monotonic([5, 4, 3, 3, 3, 2, 1]) // True

Configure to include solutions directories only.

information:

• https://dev.to/katkelly/changing-your-repo-s-language-in-github-5gjo
• https://hackernoon.com/how-to-change-repo-language-in-github-c3e07819c5bb

Simple 2D Iterator

Implement a class (or struct, or object) representing a 2-dimensional iterator. This class should be initialized with a 2-dimensional (nested) array, and should implement two methods:

• next() returns the next element in the array of arrays
• has_next() returns true/false indicating whether the iterator still has elements left

Business Rules/Errata

• Data Structure Required: 2D Array
• Your class will need a constructor method (or other strategy) to accept a 2-dimensional array and produce an instance of your class.
• You should not flatten or otherwise copy data out of the 2D array into another data structure.
• If you call next() on your class, and there are no elements left to return, return null (or some other indicator that the iterator has been exhausted).

Examples

Example 1

instance = new NestedIterator([[1, 2], [3], [], [4, 5, 6]]);
instance.next()  // 1
instance.next()  // 2
instance.next()  // 3
instance.has_next()  // true
instance.next()  // 4
instance.next()  // 5
instance.next()  // 6
instance.has_next()  // false
instance.next()  // NULL

Example 2

instance = new NestedIterator([[9], [1, 7, 5], [2, 9], []]);
instance.next()  // 9
instance.next()  // 1
instance.next()  // 7
instance.has_next()  // true
instance.next()  // 5
instance.next()  // 6
instance.next()  // 9
instance.has_next()  // false
instance.next()  // NULL

Create on boarding document for new leaders to the Coding Dojo

Look and Say Sequence

In mathematics, the look-and-say sequence is the sequence of integers beginning as follows:

1, 11, 21, 1211, 111221, 312211, …

To generate a member of the sequence from the previous member, read off the digits of
the previous member, counting the number of digits in groups of the same digit

For Example:

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
1211 is read off as "one 1, then one 2, then two 1s" or 111221.
111221 is read off as "three 1s, then two 2s, then one 1" or 312211.

Business Rules/Errata

Your mission is to write a function which, given an integer n as parameter, returns a
comma separated list of the first n terms of the sequence. For 0, an empty string
shall be returned.

For 0, negative, or NaN parameters, -1 shall be returned.

Examples

get_lines(2);  //  "1,11"
get_lines(3);  //  "1,11,21"
get_lines(5);  //  "1,11,21,1211,111221"

Friend Finder

A classroom consists of N students, whose friendships can be represented in an adjacency list. For example, the following describes a situation where 0 is friends with 1 and 2, 3 is friends with 6, and so on.

{0: [1, 2],
 1: [0, 5],
 2: [0],
 3: [6],
 4: [],
 5: [1],
 6: [3]} 

Each student can be placed in a friend group, which can be defined as the the smallest set of students such that no student in the group has any friends outside this group. For the example above, the friend groups would be {0, 1, 2, 5}, {3, 6}, {4}.

Given a friendship list such as the one above, determine the number of friend groups in the class.

Business Rules/Errata

• Data Structure Required: Graphs - The input data structure may be described as an undirected graph, where each student (represented by their ID) is connected to each of their friends.
• Your input will be a dictionary (or HashMap, or similar structure) where the keys will be integers representing student ID numbers, and the values will be a list of integers representing the ID numbers of that student's friends.
• Each student will be represented as a key in the input, and all of that student's friends will be included in the associated value. You will not need to account for a partial listing of either.
• This challenge only requires you to calculate the number of friend groups, you do not need to return a list of groups with their members.

Examples

friendList = {
  0: [1, 2], 1: [0, 5], 2: [0],
  3: [6]   , 4: []    , 5: [1],
  6: [3]
} 
friendGroups(friendList) // 3, groups {0, 1, 2, 5}, {3, 6}, {4}

friendList = {
  0: [1, 2], 1: [0, 2], 2: [0, 1, 3],
  3: [2, 4], 4: [3, 5], 5: [3, 4]
}
friendGroups(friendList) // 1, student 3 bridges the two groups

friendList = {
  0: [1], 1: [0], 2: [3], 3: [2],
  4: [5], 5: [4], 6: [7], 7: [6]
}
friendGroups(friendList) // 4, groups {0, 1}, {2, 3}, {4, 5}, {6, 7}

Planet Express

You are managing logistics for an intergalactic delivery service. Your current task is to calculate the amount of time needed to deliver a set of packages. In the best case, the time needed to deliver a package is the difference between the package "pickup" and package "dropoff" events. Unfortunately, it's a dangerous universe out there, and sometimes the courier gets eaten (an "eaten" event). It's really a good news/bad news sort of situation. The good news is that your delivery service has access to a limited form of time travel, so you can send out multiple couriers at the same time (you should see the looks on their faces when two leave at the same time, though). The bad news is that you have to count the time for all the couriers, no matter how many it takes to make a delivery.

Your input data is given in a list of data formatted like the following:

(delivery id, timestamp, event)

The timestamp is a Unix Timestamp. Your function should calculate the total time for all deliveries, including 'mishaps'. For example, if the input is the following:

(1, 1570320047, 'pickup')
(1, 1570320725, 'dropoff')
(2, 1570321092, 'pickup')
(3, 1570321212, 'pickup')
(3, 1570322352, 'dropoff')
(2, 1570323012, 'dropoff')
(2, 1570322092, 'eaten')

The total active time would be 4738 seconds by the following schedule:

(1, 1570320047, 'pickup') -> (1, 1570320725, 'dropoff') => 678 seconds
(2, 1570321092, 'pickup') -> (2, 1570322092, 'eaten')   => 1000 seconds, first attempt
(2, 1570321092, 'pickup') -> (2, 1570323012, 'dropoff') => 1920 seconds, second attempt
(3, 1570321212, 'pickup') -> (3, 1570322352, 'dropoff') => 1140 seconds

Business Rules/Errata

• You may assume that each delivery is being carried by a different courier, time travel aside.
• The result of your calculation should be the total number of seconds of all attempts, added together.
• Every delivery ID will have one 'pickup' and one 'dropoff' event.
• It is possible, though most unfortunate, for more than one courier to be eaten in the course of making a particular delivery.
• If no delivery data is passed to your function, return 0 seconds.

Examples

See above.

Minimum Impossible Sum

Given a sorted array of integers, find the smallest positive integer that is not the sum of a subset of the array.

Business Rules/Errata

• Your input will be an array of integers, sorted in ascending order (smallest to largest).
• Your input will always contain at least one number.
• Your answer should be a positive integer larger than zero.
• You do not need to account for integer overflow (i.e., the answer should always be a 32-bit positive number, in the range from 0 to 4,294,967,295).
• Bonus: Can you solve this challenge in linear (O(n)) time?

Examples

min_impossible_sum([5]) // 1
min_impossible_sum([1]) // 2
min_impossible_sum([1, 2, 3, 10]) // 7
min_impossible_sum([1, 2, 3, 7, 10]) // 24

Limited Levenshtein Leap

Given a start word, and end word, and a "dictionary" of valid words, find the shortest transformation sequence from start to end such that only one letter is changed at each step of the sequence, and each transformed word exists in the dictionary. If there is no possible transformation, return NULL.

Business Rules/Errata

• The "dictionary" is simply an unordered array of strings.
• The start, stop, and "dictionary" words will all be the same length and all lowercase.
• Your function should return the sequence of words that represent the transformations from start to end.

Examples

Example 1

start = "dog"
end = "cat"
dictionary = ["dot", "dop", "dat", "cat"]
findTransformSequence(start, end, dictionary)  // ["dog", "dot", "dat", "cat"]

Example 2

start = "dog"
end = "cat"
dictionary = ["dot", "tod", "dat", "dar"]
findTransformSequence(start, end, dictionary)  // NULL

Use a debugger

the Challenge setup will require some nearly complete broken bits of code

Business Rules/Errata

• Language agnostic (although the setup will require knowledge beforehand)

Examples

Can reuse a previous challenge that is sufficiently complex to have multiple functions that may need troubleshooting.

Zero Point

Given a linked list, remove all consecutive nodes that sum to zero.
For example, suppose you are given the input 3 -> 4 -> -7 -> 5 -> -6 -> 6. In this case, you should first remove 3 -> 4 -> -7, then -6 -> 6, leaving only 5.

Business Rules/Errata

• Data Structure Required: Linked List
• Your input will be a linked list, where each node represents either a positive or negative integer.
• Your return value should be in the form of a linked list containing only nodes that are not part of a consecutive sequence that sums to zero.
• If your input linked list does not contain any nodes that qualify to be returned (such as 1 -> -1), return NULL (or your language's equivalent).
• Your input will contain at least one node with a value.

Examples

input = 1 -> 2 -> 3 -> 4 -> -4 -> -3 -> 5
remove_zero_sequences(input)  // 1 -> 2 -> 5

input = 2 -> -2 -> 3 -> 4 -> 5 -> -9
remove_zero_sequences(input)  // 3

input = 1 -> -10 -> 5 -> 4
remove_zero_sequences(input)  // NULL

Non-Constructible Change

Given an array of sorted positive integers representing the values of coins in your possession, write a function that returns the minimum amount of change (the minimum sum of money) that you cannot create.

Business Rules/Errata

• You can assume that the input will be a list or array of sorted integers.
• The given coins can have any positive integer value, they do not have to correspond to real coin values (for example, we could have a coin worth 3).
• The coins aren't necessarily unique (you could have 7 coins worth 1, 2 coins worth 3, etc.
• Extra challenge: Complete this challenge in linear time and constant space.

Examples

coins = [1]
nonConstructibleChange(coins) // 2

coins = [1, 1, 1, 1, 1]
nonConstructibleChange(coins) // 6 

coins = [1, 1, 2, 3, 5, 7, 22]
nonConstructibleChange(coins) // 20

coins = [1, 1, 4, 5, 6, 8, 9]
nonConstructibleChange(coins) // 3

coins = [1, 1, 1, 1, 5, 10, 15, 20, 100]
nonConstructibleChange(coins) // 55

Data Grouping in a Large Text File

Given a tab delimited text file with two columns with a header: ['HighSchool Year', 'ACT Score'], complete the following tasks:

1. Group the data by HighSchool Year and return the mean and median ACT Score of each year.
2. return the number of scores greater than 25.
3. return the number of sophomore scores greater than 25 and less than 30.
4. return the mean of only the sophomore and junior scores.

As a bonus, plot the mean score as a function high school year and determine if there is a correlation between test scores and high school year.

Business Rules/Errata

• You will be provided a file in the challenge setup with the data.
• Use of external libraries, specifically data analysis libraries is encouraged.
• The data output can be a dictionary or a dataframe (hint hint).
• The data will be much larger than the example.
• Stretch: plot the data in a meaningful way.

Examples

Here is an example of the data file (tab delimited text):

HighSchool Year    ACT Score
Sophomore          22
Junior             28
Freshman           21
Freshman           19
Junior             24
Senior             25
Senior             31
Sophomore          31

Outputs of grouping (dataframe example):

HighSchool Year  Mean     Median
Freshman         20       20
Sophomore        26.5     26.5
Junior           26       26
Senior           28       28

###
# outputs of:

#return the number of scores greater than 25.
3

#return the number of sophomore scores greater than 25 and less than 30.
0

#return the mean of only the sophomore and junior scores.
26.25

Participation

All Hacktoberfest solutions should be provably correct. That is, solution submissions should either include the unit tests from the original challenge (implemented in your language of choice) or at least print out the expected answers when run by the maintainers. Solutions that do not meet these criteria may be rejected, or flagged as 'invalid' or 'spam' in egregious cases. This can result in your PR not counting towards your Hacktoberfest participation or becoming ineligible to participate in Hacktoberfest. Violations of our Code of Conduct will be reported, and will also render you ineligible to participate in Hacktoberfest. Please be respectful of the maintainers' and other participants' time by doing your best to submit real solutions to the puzzles. Thanks, and welcome to our learning community!

Challenge

Sum of Squares

Language

Give Ruby a chance to shine! Solve this challenge in Ruby.

Approach

Make it work?

Participation

All Hacktoberfest solutions should be provably correct. That is, solution submissions should either include the unit tests from the original challenge (implemented in your language of choice) or at least print out the expected answers when run by the maintainers. Solutions that do not meet these criteria may be rejected, or flagged as 'invalid' or 'spam' in egregious cases. This can result in your PR not counting towards your Hacktoberfest participation or becoming ineligible to participate in Hacktoberfest. Violations of our Code of Conduct will be reported, and will also render you ineligible to participate in Hacktoberfest. Please be respectful of the maintainers' and other participants' time by doing your best to submit real solutions to the puzzles. Thanks, and welcome to our learning community!

Challenge

Non-Constructible Change

Language

Can you believe we never got any additional solutions for this one? Solve this challenge in Python, how about?

Approach

Check out some of the other solutions in the repo for ideas about how to use unit tests to prove your solution works.

Participation

All Hacktoberfest solutions should be provably correct. That is, solution submissions should either include the unit tests from the original challenge (implemented in your language of choice) or at least print out the expected answers when run by the maintainers. Solutions that do not meet these criteria may be rejected, or flagged as 'invalid' or 'spam' in egregious cases. This can result in your PR not counting towards your Hacktoberfest participation or becoming ineligible to participate in Hacktoberfest. Violations of our Code of Conduct will be reported, and will also render you ineligible to participate in Hacktoberfest. Please be respectful of the maintainers' and other participants' time by doing your best to submit real solutions to the puzzles. Thanks, and welcome to our learning community!

Challenge

Simple 2D Iterator

Language

Lots of Java in the repo already, add some more! Solve this challenge using Java.

Approach

Check out some of our Java-based challenges for an IDE-agnostic unit-testing setup, or use the tools built in to your favorite IDE.

Move Element to End

You're given an array of integers and an integer. Write a function that moves all instances of that integer in the array to the end of the array and returns the array. The potential difficulty of this challenge lies in achieving the optimal time and space complexity, so they will be a rule requirement.

Business Rules/Errata

• arrays can be empty, which should return an empty array.
• the array is not sorted
• the function will always take a 1 dimensional array of integers and a single integer as input.
• the integers that are not moved do not have to preserve their original order, they can be ordered in any fashion so long as the integers to move all appear at the end
• integers in the array can be duplicated
• This challenge must be solved in O(n) time and O(1) space - n is the length of the array.

Examples

array = [2, 1, 2, 2, 2, 3, 4, 2]
to_move = 2

move_element_to_end(array, to_move) -> [1, 3, 4, 2, 2, 2, 2, 2] # 1, 3, 4 in this do not have to maintain their original order of appearance in the array, although they can

Participation

All Hacktoberfest solutions should be provably correct. That is, solution submissions should either include the unit tests from the original challenge (implemented in your language of choice) or at least print out the expected answers when run by the maintainers. Solutions that do not meet these criteria may be rejected, or flagged as 'invalid' or 'spam' in egregious cases. This can result in your PR not counting towards your Hacktoberfest participation or becoming ineligible to participate in Hacktoberfest. Violations of our Code of Conduct will be reported, and will also render you ineligible to participate in Hacktoberfest. Please be respectful of the maintainers' and other participants' time by doing your best to submit real solutions to the puzzles. Thanks, and welcome to our learning community!

Challenge

A Box in a Box

Language

Solve this challenge in Rust!

Approach

If you've never implemented a Trait before, try creating/implementing an Overlaps trait for boundary checking. If you're new to Rust, then forget about Traits and just make sure you include unit tests.

Fast Peak Picker

Given a array that's sorted but rotated at some unknown pivot, in which all elements are distinct, find the "peak" element. An element is considered a peak if it is greater than both its left and right neighbors. For example, [1, 2, 3, 2, 1] has a peak element of 3.

Business Rules/Errata

• The input will always consist of an array of numbers containing at least one element.
• The first element in the array is always considered to be "larger" than the (non-existent) element to its left.
• The last element in the array is always considered to be "larger" than the (non-existent) element to its right.
• It is possible to solve this problem in less than O(n) time, attempt to find a more efficient solution.

Examples

pick_peak([1, 2, 3, 2, 1]);  // 3
pick_peak([1, 2, 3, 4, 5]);  // 5
pick_peak([5, 4, 3, 2, 1]);  // 5
pick_peak([1]);              // 1

Dominoes Descending

You are given an string representing the initial conditions of some dominoes. Each element can take one of three values:

• "L", meaning the domino has just been pushed to the left,
• "R", meaning the domino has just been pushed to the right, or
• ".", meaning the domino is standing still.

Determine the orientation of each tile when the dominoes stop falling. Note that if a domino receives a force from the left and right side simultaneously, it will remain upright.

For example, given the string .L.R.....L, you should return LL.RRR.LLL.

Business Rules/Errata

• Input will be a valid string containing only the "L", "R", and "." characters.
• Output should be a valid string containing only the "L", "R", and "." characters.
• A domino that is struck from the left will fall left, a domino that is struck from the right will fall right.
• A domino struck from the left and right at the same time will remain standing.

Examples

topple(".L.R....L") // "LL.RRRLLL"
topple("L.......R") // "L.......R"
topple("R........") // "RRRRRRRRR"
topple("........L") // "LLLLLLLLL"
topple("RLRLRLRLR") // "RLRLRLRLR"
topple("R..L.R..L") // "RRLL.RRLL"
topple("...L.R...") // "LLLL.RRRR"
topple("R.......L") // "RRRR.LLLL"