module Algorithmable::Cups::Primitives
Public Instance Methods
anagrams?(string, other_string)
click to toggle source
# File lib/algorithmable/cups/primitives.rb, line 113 def anagrams?(string, other_string) return false unless string.size == other_string.size registry = Hash.new 0 string.each_char do |char| registry[char] += 1 end other_string.chars.none? do |char| (registry[char] -= 1) < 0 end end
chars_is_uniq?(string)
click to toggle source
# File lib/algorithmable/cups/primitives.rb, line 33 def chars_is_uniq?(string) return unless string map = Array.new 127, false string.chars.each do |char| return false if map[char.ord] map[char.ord] = true end end
find_common_chars_in_words(collection)
click to toggle source
Write a program that gives count of common characters presented in an array of strings..(or array of character arrays)
For eg.. for the following input strings..
aghkafgklt dfghako qwemnaarkf
The output should be 3. because the characters a, f and k are present in all 3 strings.
Note: The input strings contains only lower case alphabets
# File lib/algorithmable/cups/primitives.rb, line 254 def find_common_chars_in_words(collection) map = Hash.new 0 collection.each_with_index do |word, index| word.chars.each do |char| map[char] += 1 if map[char] == index end end map.select do |key, value| { key => value } if value == collection.size end end
find_cycled_node(root)
click to toggle source
# File lib/algorithmable/cups/primitives.rb, line 73 def find_cycled_node(root) return unless root.next || root.next.next slow = root fast = root until fast.next.nil? slow = slow.next fast = fast.next.next break if slow == fast end # return, no cycle return if fast.next.nil? slow = root until slow == fast slow = slow.next fast = fast.next end # at this point return value is a node which is tail pointing to. fast end
find_distance_between_words(dictionary, from, to)
click to toggle source
/* This class will be given a list of words (such as might be tokenized
* from a paragraph of text), and will provide a method that takes two * words and returns the shortest distance (in words) between those two * words in the provided text. * Example: * WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick")); * assert(finder.distance("fox","the") == 3); * assert(finder.distance("quick", "fox") == 1); * /
# File lib/algorithmable/cups/primitives.rb, line 278 def find_distance_between_words(dictionary, from, to) return 0 if from == to dict_size = dictionary.size distance = -1 dictionary.each_with_index do |word, index| next unless [from, to].include? word temp = word == from to = temp ? to : from distance += 1 i = index while i < dict_size - 1 && dictionary[i] != to i += 1 distance += 1 return distance if dictionary[i] == to end end distance end
nth_to_last_in_list(list, nth = 1)
click to toggle source
# File lib/algorithmable/cups/primitives.rb, line 171 def nth_to_last_in_list(list, nth = 1) return if list.nil? || list.empty? node1 = list.front node2 = list.front nth.downto(nth).each do |_i| if node1 end end end
parse_char(char, state)
click to toggle source
# File lib/algorithmable/cups/primitives.rb, line 139 def parse_char(char, state) chunk_id = state[:chunk_id] case char when /[\(\{\[\)\}\]]/ state[:escaping] = char != state[:prev_char] state[:chunks][chunk_id] << char unless state[:escaping] else if state[:escaping] chunk_id = state[:chunk_id] += 1 state[:escaping] = false end state[:chunks][chunk_id] << char end state[:prev_char] = char end
parse_string_with_escapes(string)
click to toggle source
# File lib/algorithmable/cups/primitives.rb, line 124 def parse_string_with_escapes(string) app_state = { chunk_id: 0, escaping: false, prev_char: nil, chunks: Hash.new { |h, k| h[k] = [] } } string.each_char do |char| parse_char char, app_state end app_state[:chunks].values end
ransom_note(note, magazine)
click to toggle source
# File lib/algorithmable/cups/primitives.rb, line 97 def ransom_note(note, magazine) ascii_table = Hash.new 0 source = magazine.chars source.each do |char| ascii_table[char] += 1 end note.chars.each do |char| return false unless ascii_table[char].nonzero? ascii_table[char] -= 1 end true end
remove_duplicated_chars(chars = [])
click to toggle source
# File lib/algorithmable/cups/primitives.rb, line 50 def remove_duplicated_chars(chars = []) return if chars.empty? || chars.size < 2 array_tail = 1 chars.size.times do |cur_char_index| next unless cur_char_index.nonzero? prev_char_index = 0 while prev_char_index < array_tail break if chars[cur_char_index] == chars[prev_char_index] prev_char_index += 1 end if prev_char_index == array_tail chars[array_tail] = chars[cur_char_index] array_tail += 1 end end # trim all after new tail chars[0...array_tail] end
remove_duplicates_from_list(list)
click to toggle source
# File lib/algorithmable/cups/primitives.rb, line 155 def remove_duplicates_from_list(list) map = {} prev = nil node = list.front while node if map[node.item] prev.next = node.next else map[node.item] = true prev = node end node = node.next end end
replace_space_chars(string, expression = '%20')
click to toggle source
this module contains a lot of C style code. It is done intentionally. All the methods avoiding using already existent algorithms in Ruby. Algorithms/solutions should be implemented in place
# File lib/algorithmable/cups/primitives.rb, line 8 def replace_space_chars(string, expression = '%20') return unless string space_count = 0 length = string.length replacement = expression.chars.reverse.freeze length.times { |i| space_count += 1 if string[i] == ' ' } new_length = length + space_count * 2 chars = Array.new(new_length, ?\x00) (0..length.pred).to_a.reverse_each do |i| if string[i] == ' ' replacement.each_with_index do |char, index| j = index + 1 chars[new_length - j] = char end new_length -= replacement.length else new_length -= 1 chars[new_length] = string[i] end end chars.join end
reverse_string(string)
click to toggle source
# File lib/algorithmable/cups/primitives.rb, line 42 def reverse_string(string) return unless string chars = string.chars reversed = '' string.size.times { reversed << chars.pop } reversed end
sort_linked_list(node)
click to toggle source
int maxDiff(int arr[], int arr_size) {
int max_diff = arr[1] - arr[0]; int i, j; for(i = 0; i < arr_size; i++) { for(j = i+1; j < arr_size; j++) { if(arr[j] - arr[i] > max_diff) max_diff = arr[j] - arr[i]; } } return max_diff;
}
getBestTime(int stocks[], int sz, int &buy, int &sell) {
int min = 0; int maxDiff = 0; buy = sell = 0; for (int i = 0; i < sz; i++) { if (stocks[i] < stocks[min]) min = i; int diff = stocks[i] - stocks[min]; if (diff > maxDiff) { buy = min; sell = i; maxDiff = diff; } }
}
# File lib/algorithmable/cups/primitives.rb, line 216 def sort_linked_list(node) return unless node || node.empty? swapped = false prev = nil begin swapped = false current = node until current.next == prev if current.item > current.next.item swap_nodes current, current.next swapped = true end current = current.next end prev = current end while swapped end
swap_nodes(node1, node2)
click to toggle source
# File lib/algorithmable/cups/primitives.rb, line 237 def swap_nodes(node1, node2) tmp = node1.item node1.item = node2.item node2.item = tmp end