commit 2b8d338b5fa85447e118d2806326215c090b8d03
parent 3019fd50df4da5ab744bdab58d70f5e6d72ea448
Author: dwrz <dwrz@dwrz.net>
Date: Sun, 6 Jan 2019 21:58:48 +0000
Add elisp/hamming
Diffstat:
3 files changed, 125 insertions(+), 0 deletions(-)
diff --git a/elisp/hamming/README.md b/elisp/hamming/README.md
@@ -0,0 +1,44 @@
+# Hamming
+
+Calculate the Hamming difference between two DNA strands.
+
+A mutation is simply a mistake that occurs during the creation or
+copying of a nucleic acid, in particular DNA. Because nucleic acids are
+vital to cellular functions, mutations tend to cause a ripple effect
+throughout the cell. Although mutations are technically mistakes, a very
+rare mutation may equip the cell with a beneficial attribute. In fact,
+the macro effects of evolution are attributable by the accumulated
+result of beneficial microscopic mutations over many generations.
+
+The simplest and most common type of nucleic acid mutation is a point
+mutation, which replaces one base with another at a single nucleotide.
+
+By counting the number of differences between two homologous DNA strands
+taken from different genomes with a common ancestor, we get a measure of
+the minimum number of point mutations that could have occurred on the
+evolutionary path between the two strands.
+
+This is called the 'Hamming distance'.
+
+It is found by comparing two DNA strands and counting how many of the
+nucleotides are different from their equivalent in the other string.
+
+ GAGCCTACTAACGGGAT
+ CATCGTAATGACGGCCT
+ ^ ^ ^ ^ ^ ^^
+
+The Hamming distance between these two DNA strands is 7.
+
+# Implementation notes
+
+The Hamming distance is only defined for sequences of equal length. This means
+that based on the definition, each language could deal with getting sequences
+of equal length differently.
+
+## Source
+
+The Calculating Point Mutations problem at Rosalind [http://rosalind.info/problems/hamm/](http://rosalind.info/problems/hamm/)
+
+## Submitting Incomplete Solutions
+
+It's possible to submit an incomplete solution so you can see how others have completed the exercise.
diff --git a/elisp/hamming/hamming-test.el b/elisp/hamming/hamming-test.el
@@ -0,0 +1,55 @@
+;;; hamming-test.el --- Tests for hamming (exercism)
+
+;;; Commentary:
+;; Common test data version: 2.0.1 f79dfd7
+
+;;; Code:
+
+(load-file "hamming.el")
+
+(declare-function hamming-distance "hamming.el")
+
+(ert-deftest empty-strands ()
+ (should (= 0 (hamming-distance "" ""))))
+
+(ert-deftest identical-strands ()
+ (should (= 0 (hamming-distance "A" "A"))))
+
+(ert-deftest long-identical-strands ()
+ (should (= 0 (hamming-distance "GGACTGA" "GGACTGA"))))
+
+(ert-deftest complete-distance-in-single-nucleotide-strands ()
+ (should (= 1 (hamming-distance "A" "G"))))
+
+(ert-deftest complete-distance-in-small-strands ()
+ (should (= 2 (hamming-distance "AG" "CT"))))
+
+(ert-deftest small-distance-in-small-strands ()
+ (should (= 1 (hamming-distance "AT" "CT"))))
+
+(ert-deftest small-distance ()
+ (should (= 1 (hamming-distance "GGACG" "GGTCG"))))
+
+(ert-deftest small-distance-in-long-strands ()
+ (should (= 2 (hamming-distance "ACCAGGG" "ACTATGG"))))
+
+(ert-deftest non-unique-character-in-first-strand ()
+ (should (= 1 (hamming-distance "AAA" "AAG"))))
+
+(ert-deftest same-nucleotides-in-different-positions ()
+ (should (= 2 (hamming-distance "TAG" "GAT"))))
+
+(ert-deftest large-distance ()
+ (should (= 4 (hamming-distance "GATACA" "GCATAA"))))
+
+(ert-deftest large-distance-in-off-by-one-strand ()
+ (should (= 9 (hamming-distance "GGACGGATTCTG" "AGGACGGATTCT"))))
+
+(ert-deftest disallow-first-strand-longer ()
+ (should-error (hamming-distance "AATG" "AAA")))
+
+(ert-deftest disallow-second-strand-longer ()
+ (should-error (hamming-distance "ATA" "AGTG")))
+
+(provide 'hamming-test)
+;;; hamming-test.el ends here
diff --git a/elisp/hamming/hamming.el b/elisp/hamming/hamming.el
@@ -0,0 +1,26 @@
+;;; hamming.el --- Hamming (exercism)
+
+;;; Commentary:
+
+;;; Code:
+
+(provide 'hamming)
+
+(defun count-different-chars(s1 s2)
+ "Count the number of different characters between two strings, S1 and S2, which must be of equal length."
+ (let ((count 0) (i 0))
+ (while (< i (length s1))
+ (if (not (char-equal (aref s1 i) (aref s2 i)))
+ (setq count (+ count 1)))
+ (setq i (+ i 1)))
+ count))
+
+(defun hamming-distance(s1 s2)
+ "Determine the Hamming distance of two strands of DNA.
+Expects the strands as two strings, S1 and S2,
+which must be of equal length."
+ (cond ((string= s1 s2) 0)
+ ((eq (length s1) (length s2)) (count-different-chars s1 s2))
+ (error "Strands must be of equal length")))
+
+;;; hamming.el ends here
