Source code in the jq programming language

### Generic helper functions

# bag-of-words
def bow(stream): 
  reduce stream as $word ({}; .[($word|tostring)] += 1);

def permutations:
  if length == 0 then []
  else
    range(0;length) as $i
    | [.[$i]] + (del(.[$i])|permutations)
  end ;

# Give a synoptic view of the input string,
# highlighting the occurrence of ACGTU letters
def synopsis:
  ["A", "C", "G", "T", "U"] as $standard
  | . as $seq
  | bow(explode | map([.]|implode)[]) as $bases
  | ("Nucleotide counts for \($seq):\n"),
    (($standard + ($bases|keys - $standard))[] | "\(.): \($bases[.]//0)"),
    "__",
    "Σ: \($seq|length)" ;

# If the strings, $s1 and $s2, overlap by at least $minimumoverlap characters,
# return { i1: <index in $s1 where overlap starts>,  overlap: <overlapping string>},
# otherwise, return null
def overlap_info($s1; $s2; $minimumoverlap):
  first( range(0; $s1|length + 1 - $minimumoverlap) as $i1
         | $s1[$i1:] as $overlap
         | select($s2 | startswith($overlap))
	 | {$i1, $overlap} ) // null ;

# Input: an array of strings
# Remove duplicates and strings contained within a larger string
def deduplicate:
  unique
  | . as $arr
  | reduce range(0;length) as $i ([];
      $arr[$i] as $s1
      | if any( $arr[] | select(. != $s1); index($s1))
        then .
	else . + [$s1]
	end);

# Given an array of deduplicated strings, attempt to find a superstring
# composed of these strings in the same order;
# return it if found, else null.
def relevant($min):
  . as $in
  | length as $length
  | {s: .[0], i:0}
  | until (.s == null or .i >= $length - 1;
       .i as $i
       # Since the strings have been deduplicated we can use $in[$i]:
       | overlap_info($in[$i]; $in[$i+1]; $min) as $overlap
       | if $overlap then .s += $in[$i+1][$overlap.overlap|length:]
         else .s = null
	 end
       | .i += 1 )
   | .s ;
     
# Input: an array of strings
# Return shortest common superstring
def shortest_common_superstring:
  deduplicate as $ss
  | reduce ($ss | permutations) as $perm ({shortestsuper: ($ss | add) };
      ($perm | relevant(1)) as $candidate
      | if $candidate and ($candidate|length) < (.shortestsuper|length)
        then .shortestsuper = $candidate
        else . end)
  | .shortestsuper;

def examples:
 [
  ["TA", "AAG", "TA", "GAA", "TA"],

  ["CATTAGGG", "ATTAG", "GGG", "TA"],

  ["AAGAUGGA", "GGAGCGCAUC", "AUCGCAAUAAGGA"],

  ["ATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTAT",
   "GGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGT",
   "CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA",
   "TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC",
   "AACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTT",
   "GCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTC",
   "CGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCT",
   "TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC",
   "CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGC",
   "GATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATT",
   "TTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC",
   "CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA",
   "TCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGA"]
  ];

def tasks:
  def t: shortest_common_superstring | synopsis;

  examples
  | . as $examples
  | range(0;length) as $i
  |  "Task \($i+1):", ($examples[$i]|t), "";

tasks