Solution to Daily Programmer Challenge #353 [Easy] Closest String

ClosestString.rb

# Challenge #353 [Easy] Closest String
# Objective: Given n number of strings, find the string that is the 'Geometric Center' by Hamming Distance
# Approach: Iterate through strings in order and compare, adding the differences between string a and b to their respective totals
# Note: Storing the differences for both at the same time reduces the number of comparisons performed.

def find_hamming_center(input)
    input_array = input.split("\n")
    num_str = input_array.slice!(0).to_i
    diff_arr = Array.new(num_str, 0)# <- array to store sum of differences for each string

    # Loop through all the strings except the last one (all the comparisons for it will have been done by the end)
    input_array[0..-2].each_with_index do | string_a, i |

        # Loop through all strings ahead of current string
        start = i + 1
        input_array[start..-1].each_with_index do |string_b, ii|

            # Compare both strings and store the result in diff_arr
            diff = compare_strings(string_a, string_b)
            diff_arr[i] += diff
            diff_arr[start + ii] += diff
        end
    end

    return input_array[get_min_num_arr(diff_arr)]
end

# Takes to strings and returns the number of differences between them
def compare_strings(a, b)
    differences = 0
    a.split('').each_with_index { |c, i| differences += 1 unless c == b[i] }
    return differences
end

# Takes an array of number and returns the minimum value index (first)
def get_min_num_arr(arr)
    smallest, ret_i = arr[0], 0
    arr.each_with_index { |n, i| smallest, ret_i = n, i if n < smallest }
    return ret_i
end

ClosestStringTest.rb

require 'test/unit'
require_relative 'ClosestString.rb'

class CS_Test < Test::Unit::TestCase

  def test_compare_strings
    assert_equal(0, compare_strings("aa", "aa"), "Matching strings did not return 0")
    assert_equal(3, compare_strings("abc", "efg"), "Unique strings length:3 did not return 3")
    assert_equal(1, compare_strings("abc", "acc"), "Strings with one difference did not return 1")
  end

  def test_find_hamming_center
    basic_input = "3
abcd
zyxd
afgh"
    test_input = "4
CTCCATCACAC
AATATCTACAT
ACATTCTCCAT
CTCCCCACTC"

    challenge_input_1 = "11
AACACCCTATA
CTTCATCCACA
TTTCAATTTTC
ACAATCAAACC
ATTCTACAACT
ATTCCTTATTC
ACTTCTCTATT
TAAAACTCACC
CTTTTCCCACC
ACCTTTTCTCA
TACCACTACTT"

    challenge_input_2 = "21
ACAAAATCCTATCAAAAACTACCATACCAAT
ACTATACTTCTAATATCATTCATTACACTTT
TTAACTCCCATTATATATTATTAATTTACCC
CCAACATACTAAACTTATTTTTTAACTACCA
TTCTAAACATTACTCCTACACCTACATACCT
ATCATCAATTACCTAATAATTCCCAATTTAT
TCCCTAATCATACCATTTTACACTCAAAAAC
AATTCAAACTTTACACACCCCTCTCATCATC
CTCCATCTTATCATATAATAAACCAAATTTA
AAAAATCCATCATTTTTTAATTCCATTCCTT
CCACTCCAAACACAAAATTATTACAATAACA
ATATTTACTCACACAAACAATTACCATCACA
TTCAAATACAAATCTCAAAATCACCTTATTT
TCCTTTAACAACTTCCCTTATCTATCTATTC
CATCCATCCCAAAACTCTCACACATAACAAC
ATTACTTATACAAAATAACTACTCCCCAATA
TATATTTTAACCACTTACCAAAATCTCTACT
TCTTTTATATCCATAAATCCAACAACTCCTA
CTCTCAAACATATATTTCTATAACTCTTATC
ACAAATAATAAAACATCCATTTCATTCATAA
CACCACCAAACCTTATAATCCCCAACCACAC"

    assert_equal(
        "abcd",
        find_hamming_center(basic_input),
        "Basic input did not produce expected results")

    assert_equal(
        "AATATCTACAT",
        find_hamming_center(test_input),
        "Test input did not produce AATATCTACAT")

    assert_equal(
        "ATTCTACAACT", 
        find_hamming_center(challenge_input_1),
        "Challenge input did not produce ATTCTACAACT")

    assert_equal(
        "TTAACTCCCATTATATATTATTAATTTACCC",
        find_hamming_center(challenge_input_2),
        "Challenge did not produce expected results")
  end
end