Sample problem

The content of the orange box shows what a typical Phase 1 problem description looks like. It also presents some possible solutions of varying quality, and explains how to provide your own solution.

Each problem starts with a task description; some also include a hint suggesting one or more APL primitives. These may be helpful in solving the problem, but you are under no obligation to use them. Clicking on a primitive in the hint opens the Dyalog documentation page for that primitive.

Each problem ends with some example cases. You can use these as a basis for implementing your solution.

      (your_functionfn) 'COOLAPL'
3
      (your_functionfn) ''   ⍝ empty argument
0
      (your_functionfn) 'NVWLSHR'   ⍝ no vowels here
0

Below are three sample solutions. All three produce the correct answer, but the first two functions would be ranked higher by the competition judging committee as they demonstrate better use of array-oriented programming than the third one.

      ({+/⍵∊'AEIOU'}) 'COOLAPL'   ⍝ good dfn
3
      (+/∊∘'AEIOU') 'COOLAPL'   ⍝ good tacit function
3
      ⍝ suboptimal dfn:
      {(+/⍵='A')+(+/⍵='E')+(+/⍵='I')+(+/⍵='O')+(+/⍵='U')} 'COOLAPL'   ⍝ suboptimal dfn
3

1: Elimination Sort

An "Elimination Sort" is a somewhat farcical sorting algorithm which starts with the leftmost element and keeps subsequent elements that are at least as large as the previous kept element, discarding all other elements. For example:

      EliminationSort 1 3 7 3 5 8 5 8 1 6 1 8 1 10 8 4 3 4 1 4
1 3 7 8 8 8 10 

Write a function that:

• takes a non-empty numeric vector right argument
• returns an "Elimination-sorted" vector of the right argument

Hint: The progressive-maxima idiomatic phrase ⌈\, the greater or equal function ≥, and the replicate function / could be helpful in solving this problem.

Examples

      (your_functionfn) ⍳10
1 2 3 4 5 6 7 8 9 10

      (your_functionfn) 2 1 4 3 6 5 8 7 10 9
2 4 6 8 10

      (your_functionfn) 1000 2500 1333 1969 3141 2345 3141 4291.9 4291.8 4292
1000 2500 3141 3141 4291.9 4292

      EliminationSort 1 3 7 3 5 8 5 8 1 6 1 8 1 10 8 4 3 4 1 4
1 3 7 8 8 8 10 

2: Put It In Reverse

The find function X⍷Y identifies the beginnings of occurrences of array X in array Y.

In this problem, you're asked to return a result that identifies the endings of occurrences of array X in array Y. To keep things simple, X and Y will be at most rank 1, meaning they'll either be vectors or scalars.

Write a function that:

• takes a scalar or vector left argument
• takes a scalar or vector right argument
• returns a Boolean result that is the same shape as the right argument where 1's mark the ends of occurrences of the left argument in the right argument

Hint: The find function ⍷ and reverse function ⌽ could be helpful in solving this problem.

Examples

      'abra' (your_functionfn) 'abracadabra'
0 0 0 1 0 0 0 0 0 0 1

      'issi' (your_functionfn) 'Mississippi'
0 0 0 0 1 0 0 1 0 0 0

      'bb' (your_functionfn) 'bbb bbb'
0 1 1 0 0 1 1

      (,42) (your_functionfn) 42
0

      42 (your_functionfn) 42
1

      (,42) (your_functionfn) ,42
1

      'are' 'aquatic' (your_functionfn) 'ducks' 'are' 'aquatic' 'avians' 
0 0 1 0

3: Caesar Salad

A Caesar cipher, also known as a shift cipher, is one of the simplest encryption techniques. In a Caesar cipher, each letter in the plaintext is replaced by a letter some fixed number of positions away in the alphabet, effectively "shifting" the alphabet.

Write a function that:

• takes a single integer left argument representing the size of the shift
• takes a character vector right argument representing the plaintext message
• returns a result with the same shape as the right argument representing the encrypted message

Notes:

• Use ' ',⎕A as the alphabet
• You can assume that the plaintext message will contain only characters found in the alphabet.

Hint: The rotate function ⌽ could be helpful in solving this problem.

Examples

      4 (your_functionfn) 'HELLO WORLDS'
LIPPSD SVPHW
    
      ¯4 (your_functionfn) 'HELLO WORLDS' ⍝ negative shifts are okay
DAHHKWSKNH O 

      0 (your_functionfn) 'HELLO WORLDS' ⍝ no shift is okay
HELLO WORLDS

      27 (your_functionfn) 'HELLO WORLDS'
HELLO WORLDS

      ¯10 (your_functionfn) '' ⍝ returns an empty vector
    
    

4: Like a Version

One common software version numbering scheme is known as "semantic versioning". Typically, semantic versioning uses three numbers representing a major version number, a minor version number, and a build number.

• The major version is incremented when a new version of the software introduces changes that would make existing applications using the software fail or behave differently.
• The minor version is incremented when new features are added that didn't previously exist — no pre-existing use of the software will fail in this case.
• The build number is incremented for bug fixes and similar changes.

Write a function that:

• takes 3-element integer vector left and right arguments each representing a major version, minor version, and build number.
• returns
  • ¯1 if the left argument represents a version number older than the right argument
  •  0 if the left argument represents a version number equal to the right argument
  •  1 if the left argument represents a version number newer than the right argument

Hint: The less function < could be helpful in solving this problem.

Examples

      
      1 2 3 (your_functionfn) 1 2 3
0 

      1 2 3 (your_functionfn) 1 0 9
1

      14 2 11 (your_functionfn) 14 2 12
¯1

5: Risky Business

The board game Risk is a game of world domination where opposing players roll dice to determine the outcome of one player's armies attacking another's. The attacker can roll up to three 6-sided dice and the defender can roll up to two 6-sided dice. The resulting rolls are then individually compared from highest to lowest. If the attacker's die value is greater than the defender's, the defender loses one army. If the defender's die value is greater than or equal to the attacker's, the attacker loses one army. If one player rolls more dice than the other other player, the additional dice are not considered in the evaluation. For this problem, we'll generalize the task by allowing any number of dice for either the attacker or defender, and any integer values in the arguments.

Write a function that:

• takes a non-empty, descending integer vector left argument representing the attacker's dice rolls
• takes a non-empty, descending integer vector right argument representing the defender's dice rolls
• returns a 2-element vector where the first element represents the number of armies the attacker lost and the second element represents the number of armies the defender lost.

Note: The left and right arguments do not need to be the same length.

Hint: The less function < could be helpful in solving this problem.

Examples

      
      6 6 4 2 1 (your_functionfn) 6 5 5 ⍝ attacker loses 2 armies, defender loses 1 army
2 1 

      6 (your_functionfn)⍥, 5 ⍝ ⍥, ravels both arguments (making them vectors) before passing them to your function
0 1

      4 0 ¯1  (your_functionfn) 3 1 ¯2
1 2

6: Key/Value Pairs

Representing data as key/value pairs (also known as name/value pairs) is a very common technique. For example, it can be found in query strings in HTTP URIs, attribute settings in HTML elements, and in JSON objects. One common representation for a key/value pair is to have a character key (name) followed by an equals sign (=) followed by the value. Multiple key/value pairs can be separated by a delimiter character or characters. For example:

      key1=value1;key2=value2

Write a function that:

• takes a 2-element character vector left argument where the first element represents the separator character between multiple key/value pairs and the second element represents the separator between the key and the value for each pair.
• takes a character vector right argument representing a valid set of key/value pairs (delimited as specified by the left argument).
• returns a 2-column matrix where the first column contains the character vector keys of the key/value pairs and the second column contains the character vector values.

Note: You may assume that there will be no empty names or values in the right argument.

Hint: The partition function ⊆ could be helpful in solving this problem.

Examples

      
      ⍴ ⎕← ' ='(your_functionfn)'language=APL dialect=Dyalog' 
┌────────┬──────┐
│language│APL   │
├────────┼──────┤
│dialect │Dyalog│
└────────┴──────┘
2 2      

      ⍴ ⎕← ';:'(your_functionfn)'duck:donald' 
┌────┬──────┐
│duck│donald│
└────┴──────┘
1 2      
 
      ⍴ ⎕← '/:'(your_functionfn)'name:Morten/name:Brian/name:Adám'
┌────┬──────┐
│name│Morten│
├────┼──────┤
│name│Brian │
├────┼──────┤
│name│Adám  │
└────┴──────┘
3 2      
      

8: Critical Thinking

      23 23 28∧⍥(÷∘2)28 33 33
322 379.5 462
            

Write a function that:

• takes a 3-element integer left argument representing a valid birthdate
• takes a 3-element integer right argument representing a valid date occurring on or after the left argument
• returns a 3-element integer array representing the date of the next double or triple critical day occurring on or after the date represented by the right argument.

Note: All the dates in this specification are to be in the form year month day

Hint: The date time system function ⎕DT and residue function | could be helpful in solving this problem.

Examples

      1962 10 31 (your_functionfn) 2023 1 1
2023 2 4 

      1961 2 23 (your_functionfn) 1961 2 23 ⍝ one's birthdate is a triple critical day
1961 2 23

21 April 2023 Note:

We messed up... Even though we said a critical day occurs when a cycle crosses the x-axis in either direction, we didn't account for that in the subsequent description. (Unfortunately, neither did the reference we used when researching this problem.) We've amended the description above and copied the original text below.

To be fair to people who have already submitted "correct" solutions, we will accept solutions that conform to either the original or current descriptions.

We also express our thanks to the participants in The APL Orchard for bringing this to our attention.

Original text:

"Critical days" are days when a cycle crosses the x-axis in either direction and are purported to be accompanied by unstable conditions in the corresponding area. A "double critical day" occurs when two of the three cycles cross the x-axis on the same day. The periodicity of double critical days is the least common multiple of periodicities of the two involved cycles. So, the periodicities of the Physical-Emotional, Physical-Intellectual and Emotional-Intellectual double critical days can be calculated respectively as:

      23 23 28∧28 33 33
644 759 924
            

Fortunately, the dreaded "triple critical day", when all three cycles cross the x-axis on the same day, only occurs every (∧/23 28 33) or 21,252 days (a bit more than 58 years).

9: Flipping Pairs

This problem has no practical use in the real world (that the author can think of) other than to give your array manipulation muscles some exercise.

Write a function that:

• takes a non-empty non-scalar array right argument
• returns an array of the same shape as the argument, but with pairs of elements along the last axis "flipped". If the array has an odd number of elements in the last axis, leave the last element unchanged.

Hint: Either the reverse function ⌽ used with the partitioned enclose function ⊂, or the grade up function ⍋ used with the index function ⌷, could be helpful in solving this problem.

Examples

      (your_functionfn) ⍳10
2 1 4 3 6 5 8 7 10 9

      (your_functionfn) ⍳9
2 1 4 3 6 5 8 7 9

      (your_functionfn) 4 2⍴⍳8
2 1
4 3
6 5
8 7

(your_functionfn) 4 3⍴⍳12
 2  1  3
 5  4  6
 8  7  9
11 10 12

      (your_functionfn) 3 3 3⍴⍳27
2  1  3
5  4  6
8  7  9
     
11 10 12
14 13 15
17 16 18
     
20 19 21
23 22 24
26 25 27

      (your_functionfn) 2 3⍴'donald' 'duck' 'wrote' 'some' 'good' 'APL'
┌────┬──────┬─────┐
│duck│donald│wrote│
├────┼──────┼─────┤
│good│some  │APL  │
└────┴──────┴─────┘

10: Partition with a Twist

Splitting delimited data into sub-arrays using partitioning on a delimiter character (or characters) is a fairly common operation in APL. For instance, if you partition the character vector 'this is an example' on each occurrence of the space character, there would be 4 sub-arrays: 'this' 'is' 'an' 'example'. This problem adds a slight twist to the operation in that the left argument indicates how many sub-arrays to return.

Write a function that:

• takes a non-negative integer left argument, N
• takes a space-delimited character vector right argument, string
• returns an array of length N where:
  • if N is less than or equal to the number of sub-arrays in string, the first N-1 elements of the result are the first N-1 space-delimited partitions in string.
    The N^th element of the result is the remaining portion of string.
  • if N is greater than the number of sub-arrays, pad the result with as many empty arrays as necessary to achieve length N.

  Note: Each space in string be considered as a delimiter. This means that leading, trailing, or contiguous spaces are potentially significant.

  Hint: The partitioned enclose function ⊂ could be helpful in solving this problem.

  ---

  Examples

        1 (your_functionfn) 'this is a sample'
  ┌────────────────┐
  │this is a sample│
  └────────────────┘
  
        2 (your_functionfn) 'this is a sample'
  ┌────┬───────────┐
  │this│is a sample│
  └────┴───────────┘
  
        4 (your_functionfn) 'this is a sample'
  ┌────┬──┬─┬──────┐
  │this│is│a│sample│
  └────┴──┴─┴──────┘
  
        ⍴¨4 (your_functionfn) 'this is a sample' ⍝ each sub-array is a vector
  ┌─┬─┬─┬─┐
  │4│2│1│6│
  └─┴─┴─┴─┘
  
        13 (your_functionfn) '  this  is  a sample  ' ⍝ note the leading, trailing, and multiple interior spaces 
  ┌┬┬────┬┬──┬┬─┬──────┬┬┬┬┬┐
  │││this││is││a│sample││││││
  └┴┴────┴┴──┴┴─┴──────┴┴┴┴┴┘
  
        0 (your_functionfn) 'this is a sample' ⍝ returns an empty vector
  
  
        4 (your_functionfn) ''
  ┌┬┬┬┐
  │││││
  └┴┴┴┘
  

APL Problem Solving Competition
Phase 2

Introduction

Phase 2 is similar to Phase 1 in that you submit solutions for each problem separately. In contrast to Phase 1, Phase 2 solutions are larger and more complex, and they should be adequately commented. You need to have submitted at least one correct Phase 1 solution before you can submit anything for Phase 2.

Each Phase 2 problem comprises one or more tasks. You must complete all of the tasks for both Phase 2 problems to qualify for consideration for one of the top three student prizes or the non-student prize. You can write additional subfunctions in support of your solutions if necessary.

Each task description contains one or more examples. The judging committee can submit your solutions to additional testing beyond the specific example solutions.

Your solutions will be tested in the default Dyalog environment using (⎕IO ⎕ML)←1. Your code can employ a different, localised, setting for either of these if necessary.

Submission format

You can write your solutions using any combination of tradfns or dfns. The only requirement is that the function name and syntax must match the task description. For example, if the task description is:

Write a function named Plus which:

• takes a numeric array right argument.
• takes a numeric singleton left argument.
• returns a result that is the same shape as the right argument and whose values are the sums of the left argument added to each element of the right argument.

then either of the following would be valid solutions:

∇ r←a Plus b
  r←a+b
∇

Plus←{⍺+⍵}

Judging Guidelines

Phase 2 will mainly be judged based on:

• Did you solve the problem?
• Does your solution demonstrate appropriate use of array-oriented techniques? For example, solutions that use looping where an obvious array-based solution exists will be judged lower.
• Did you comment your solution? It's not necessary to write a novel, or add a comment to every line, but comments describing non-trivial lines of code are advised. These help the judging committee determine your level of understanding of the problem and its solution.
• Is your solution original? Your solution should be your own work and not a copy or near-copy of an already-published solution.

Tips

• Read the descriptions carefully.
• Don't make any assumptions about shape, rank, datatype, or values that are not explicitly stated in the description. For example, if an argument is stated to be a numeric array then it can be any numeric type (Boolean, integer, floating point, complex) and of any shape or depth.
• Make sure that your functions return a result rather than just display output to the session.
• Pay attention to any additional judging criteria that are stated in an individual problem's description.
• Be aware that the examples serve to provide basic guidance and validation for your solutions and are not intended to be a complete exposition of all possible edge cases; the judging committee will submit your solutions to additional test cases.

1: Bioinformatics (5 tasks)

All of the tasks in this problem set are derived from the excellent Rosalind.info bioinformatics website.

For most tasks, we provide at least one sample dataset consisting of an input file and a corresponding result file that has been verified on Rosalind.info. You can download these for your own testing purposes; the examples in this problem description assume the files have been downloaded into a folder named /tmp/ (if you download them to a different location, substitute the location you used). In addition to the sample datasets we provide in this problem description, you can also use the Rosalind website to validate your solutions.

The first four tasks in this problem will help you to build utilities to solve the last task.

Task 1: The origin for this task can be found at Transcribing DNA into RNA

DNA strings are formed from an alphabet containing 'A', 'C', 'G', and 'T'. RNA strings are formed from an alphabet containing 'A', 'C', 'G', and 'U'. The transcribed RNA string for a given DNA string is formed by replacing all occurrences of 'T' in the DNA string by 'U'.

Write a function named rna that:

• takes a character vector or scalar right argument representing a DNA string
• returns a character array of the same shape as the right argument representing the transcribed RNA string for the right argument

Sample dataset:

• Input: rosalind_rna_1_dataset.txt. Result: rosalind_rna_1_output.txt

Examples

      rna 'GATGGAACTTGACTACGTAAATT'
GAUGGAACUUGACUACGUAAAUU

      rna '' ⍝ returns an empty vector


      rna 'T' ⍝ returns a scalar
U

     ⍝ using the sample dataset - substitute your appropriate folder name for /tmp/ 
     '/tmp/rosalind_rna_1_output.txt' ≡∘rna⍥{⊃⊃⎕NGET ⍵ 1} '/tmp/rosalind_rna_1_dataset.txt'
1     

Task 2: The origin for this task can be found at Complementing a Strand of DNA

In DNA strings, the symbols 'A' and 'T' are complements of each other, as are 'C' and 'G'. The reverse complement of a DNA string is formed by reversing the symbols and then taking the complement of each symbol.

Write a function named revc that:

• takes a character vector or scalar right argument representing a DNA string
• returns a character array of the same shape as the right argument representing the reverse complement of the right argument

Sample dataset:

• Input: rosalind_revc_1_dataset.txt. Result: rosalind_revc_1_output.txt

Examples

      revc 'AAAACCCGGT'
      ACCGGGTTTT
      
      revc '' ⍝ returns an empty vector
      
      
      revc 'T' ⍝ returns a scalar
A
      
      ⍝ using the sample dataset - substitute for /tmp/ as appropriate
      '/tmp/rosalind_revc_1_output.txt' ≡∘revc⍥{⊃⊃⎕NGET ⍵ 1} '/tmp/rosalind_revc_1_dataset.txt'
1     

Task 3: The origin for this task can be found at Translating RNA into Protein

The 20 commonly occurring amino acids are abbreviated by using 20 letters from the English alphabet. Protein strings are constructed from these 20 symbols. A codon is an RNA sequence of 3 nucleotides. There are 4 symbols used in RNA ('ACGU'), so there are 64 (4*3) possible codons. 61 codons specify amino acids and 3 are used as stop signals. The RNA codon table shows the mapping between the 64 codons and amino acids or stop signals:

UUU F      CUU L      AUU I      GUU V
UUC F      CUC L      AUC I      GUC V
UUA L      CUA L      AUA I      GUA V
UUG L      CUG L      AUG M      GUG V
UCU S      CCU P      ACU T      GCU A
UCC S      CCC P      ACC T      GCC A
UCA S      CCA P      ACA T      GCA A
UCG S      CCG P      ACG T      GCG A
UAU Y      CAU H      AAU N      GAU D
UAC Y      CAC H      AAC N      GAC D
UAA Stop   CAA Q      AAA K      GAA E
UAG Stop   CAG Q      AAG K      GAG E
UGU C      CGU R      AGU S      GGU G
UGC C      CGC R      AGC S      GGC G
UGA Stop   CGA R      AGA R      GGA G
UGG W      CGG R      AGG R      GGG G 

Write a function named prot that:

• takes a non-empty character vector right argument representing an RNA string. If the length of the vector is not a multiple of 3, truncate the last 1 or 2 characters to make its length a multiple of 3.
• returns a character vector representing the protein string made by translating the codons into their corresponding amino acids.

Note: You can assume that the RNA string will contain at most one stop signal which, if present, will be at the end of the RNA string.

Sample dataset:

• Input: rosalind_prot_1_dataset.txt. Result: rosalind_prot_1_output.txt

Examples

      prot 'AUGGCCAUGGCGCCCAGAACUGAGAUCAAUAGUACCCGUAUUAACGGGUGA'
MAMAPRTEINSTRING

      prot 'UUUAAAGG' ⍝ argument is length 8, use the first 6 elements
FK
      
      ⍝ using the sample dataset - substitute your appropriate folder name for /tmp/ 
      '/tmp/rosalind_prot_1_output.txt' (≡∘prot⍥{⊃⊃⎕NGET ⍵ 1}) '/tmp/rosalind_prot_1_dataset.txt'
1     

Task 4: The origin for this task can be found at FASTA format

In bioinformatics, the FASTA format is a text-based format for representing genetic (RNA, DNA and protein) strings.

A FASTA file can contain one or more genetic string definitions, each of which is composed of some identifying information and the character representation of the genetic string itself. Specifically, each string comprises:

• an identifier line, which begins with the '>' character followed by an identifier for the string (and then, optionally, a space and additional descriptive text)
• additional lines containing the genetic string itself, up until either the end of the file or another line beginning with the '>' character (which marks the beginning of another genetic string definition).
  Note: The genetic string can be split across multiple contiguous lines in the file. This is typically done to maintain a line length of 80 or fewer characters.

Write a function named readFASTA that:

• takes a character vector right argument representing the name of a file containing data in FASTA format.
• returns a vector of 2-element vectors for each genetic string contained in the file in the order in which they appear in the file. Each sub-vector will contain:
  • the identifier for the genetic string
  • the genetic string itself

  Sample dataset:

  • Input: sampleFASTA.txt (contents appear below)

  >Taxon1 Some description here
  CCTGCGGAAGATCGGCACTAGAATAGCCAGAACCGTTTCTCTGAGGCTTCCGGCCTTCCC
  TCCCACTAATAATTCTGAGG
  >Taxon2
  CCATCGGTAGCGCATCCTTAGTCCAATTAAGTCCCTATCCAGGCGCTCCGCCGAAGGTCT
  ATATCCATTTGTCAGCAGACACGC
  >Taxon3
  CCACCCTCGTGGTATGGCTAGGCATTCAGGAACCGGAGAACGCTTCAGACCAGCCCGGAC
  TGGGAACCTGCGGGCAGTAGGTGGAAT
  

  Examples

        ⍝ using the sample dataset - substitute your appropriate folder name for /tmp/ 
        ⍪ readFASTA '/tmp/sampleFASTA.txt'
  ┌────────────────────────────────────────────────────────────────────────────────────────────────┐
  │┌──────┬────────────────────────────────────────────────────────────────────────────────┐       │
  ││Taxon1│CCTGCGGAAGATCGGCACTAGAATAGCCAGAACCGTTTCTCTGAGGCTTCCGGCCTTCCCTCCCACTAATAATTCTGAGG│       │
  │└──────┴────────────────────────────────────────────────────────────────────────────────┘       │
  ├────────────────────────────────────────────────────────────────────────────────────────────────┤
  │┌──────┬────────────────────────────────────────────────────────────────────────────────────┐   │
  ││Taxon2│CCATCGGTAGCGCATCCTTAGTCCAATTAAGTCCCTATCCAGGCGCTCCGCCGAAGGTCTATATCCATTTGTCAGCAGACACGC│   │
  │└──────┴────────────────────────────────────────────────────────────────────────────────────┘   │
  ├────────────────────────────────────────────────────────────────────────────────────────────────┤      
  │┌──────┬───────────────────────────────────────────────────────────────────────────────────────┐│
  ││Taxon3│CCACCCTCGTGGTATGGCTAGGCATTCAGGAACCGGAGAACGCTTCAGACCAGCCCGGACTGGGAACCTGCGGGCAGTAGGTGGAAT││
  │└──────┴───────────────────────────────────────────────────────────────────────────────────────┘│
  └────────────────────────────────────────────────────────────────────────────────────────────────┘
           
  

  Task 5: The origin for this task can be found at Open Reading Frames

  A reading frame is one of three possible ways to translate a given strand of DNA into amino acids depending on its starting position. For example, the DNA string ACGTACGT could be read as ACGTAC, CGTACG, and GTACGT ...

  ACGTACGT
  └────┘
   └────┘
    └────┘
  

  ...which can be translated to RNA strings ACGUAC, CGUACG, and GUACGU – these can then be mapped to amino acids TY, RT, and VR respectively.

  A DNA string has 6 possible ways to be translated into amino acids - 3 reading frames for the DNA string itself, and 3 reading frames for the DNA string's reverse complement.

  An open reading frame (ORF) is a sequence of DNA or RNA that is potentially able to encode a protein. An open reading frame starts with the start codon and ends with the stop codon without any other stop codons in between.

  The start codon is the RNA string AUG, which is transcribed from the DNA string ATG. In the genetic code, the start codon corresponds to the amino acid methionine (M) and triggers the beginning of translation of a molecule of RNA into protein.

  There are three possible stop codons; RNA strings UAG, UGA, and UAA, which are transcribed from DNA codons TAG, TGA, and TAA.

  Write a function named orf that:

  • takes a right argument that is the name of a file containing a single DNA string in FASTA format
  • returns a vector of the distinct protein strings (character vectors) that can be translated from the ORFs of the DNA string. The strings can be in any order.

  Sample datasets:

  • Input: sampleORF.txt
  • Input: rosalind_orf_1.txt Result: rosalind_orf_1_output.txt

  Examples

        sort←(⊂⍋)⌷⊢
  
        ⍝ using the sample datasets - substitute your appropriate folder name for /tmp/ 
  
        solution←'MLLGSFRLIPKETLIQVAGSSPCNLS' (,'M') 'MGMTPRLGLESLLE' 'MTPRLGLESLLE'
        solution ≡⍥sort orf '/tmp/sampleORF.txt'
  1     
        solution←' '~¨⍨⊃⎕NGET '/tmp/rosalind_orf_1_output.txt' 1 ⍝ read solution as vector of vectors (removing blanks)
        solution ≡⍥sort orf '/tmp/rosalind_orf_1_dataset.txt'
  1
  

2: Potpourri (4 tasks)

The tasks in this problem set come from a variety of domains and sources.

Task 1: Identification Please

The origin for this task may be found at Check-digit calculation.

In the United States and Canada, a vehicle identification number (VIN) is a 17-character alphanumeric identifier used to uniquely identify a vehicle. VINs have a built-in check digit in the 9^th position. The check digit is the result of a modulus 11 calculation computed from the other digits in the VIN.

The check-digit is calculated by:

1. Replacing any letters in the VIN with appropriate numerical counterparts as follows:
   

   A: 1	B: 2	C: 3	D: 4	E: 5	F: 6	G: 7	H: 8	—
   J: 1	K: 2	L: 3	M: 4	N: 5	—	P: 7	—	R: 9
   —	S: 2	T: 3	U: 4	V: 5	W: 6	X: 7	Y: 8	Z: 9

   Note: the letters I, O, and Q are not allowed in a VIN.


2. Multiplying each number by a weight factor based on the position within the VIN:
   Note:

   Position	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
   Weight	8	7	6	5	4	3	2	10	0	9	8	7	6	5	4	3	2



3. Sum the products


4. Take the 11 modulo of the sum. The result, if not 10, is the check-digit. If the result is 10, use the letter X as the check-digit.

Write a function named vin that:

• takes a character vector right argument:
• returns a value that is dependent on the character vector right argument:
• if the length of the argument is 16:
  takes the first 8 characters as the first 8 characters of a VIN and the last 8 characters as the last 8 characters of a VIN, computes the check-digit, and returns the complete VIN with the check-digit in the 9^th position.
• if the length of the argument is 17:
  computes the check-digit, compares it to the character in the 9^th position, and returns 1 if the computed check-digit matches the supplied one or 0 if it does not match.
• if the length of the argument is not 16 or 17:
  returns ¯1.
• if the argument contains any characters that are not allowed in a VIN:
  returns ¯1.

Examples

      vin '1M8GDM9AKP042788' ⍝ 16-character argument
1M8GDM9AXKP042788

      vin vin '1M8GDM9AKP042788'
1

      vin¨ '5GZCZ43D13S812715' 'SGZCZ43D13S812715'
1 0

      vin 'happy birthday'
¯1

Task 2: Get Your Versions in Order

Tatin is an APL package manager developed by the APL Team. Anyone can contribute packages to the public Tatin repository for use by those developing an APL application. A Tatin package is identified in the following format:

      groupName-packageName-major.minor.patch{-patchInfo}

Information about versions of packages that Dyalog has published can be retrieved by using the Tatin ListPackages user command:

      ]Tatin.ListPackages [tatin] -group=dyalog -noaggr
 Registry: [tatin]         
 Group & Name              
 ------------              
 dyalog-HttpCommand-5.1.10 
 dyalog-HttpCommand-5.1.11 
 dyalog-HttpCommand-5.1.12 
 dyalog-HttpCommand-5.1.13 
 dyalog-HttpCommand-5.1.14 
 dyalog-HttpCommand-5.1.5  
 dyalog-HttpCommand-5.1.6  
 dyalog-HttpCommand-5.1.7  
 dyalog-HttpCommand-5.1.8  
 dyalog-HttpCommand-5.1.9  
 dyalog-Jarvis-1.11.10     
 dyalog-Jarvis-1.11.5      
 dyalog-Jarvis-1.11.6      
 dyalog-Jarvis-1.11.7      
 dyalog-Jarvis-1.11.8      
 dyalog-Jarvis-1.11.9      

The versions are sorted alphanumerically and not by major.minor.patch, meaning that HttpCommand 5.1.10 is listed before rather than after 5.1.9.

Write a function named sortVersions that:

• takes a character vector representing a single package identifier, or a vector of character vectors each representing a package identifier.
• returns a vector of character vectors of the package identifiers sorted by version number. If the right argument is a simple character vector representing a single package identifier, the result should be a 1-element vector of the enclosed right argument. If there is more than one unique groupName-packageName in the right argument, the entries should be grouped by groupName-packageName, but the order of groups is not significant.

Notes:

• While it might be useful, it is not necessary to have Tatin installed or available on your platform to solve this problem.
• The Tatin ListVersions function properly sorts by version number but cannot be used in this problem!
• The data for the example above can be downloaded from here and then brought into the workspace using:

        pkgs←⎕JSON ⊃⎕NGET '/downloads/pkgs.json'

  you will need to change "downloads" to the location where you downloaded pkgs.json

Examples

      ]Box on
Was OFF     

      sortVersions 'a-b-1.2.1' 'a-b-1.2.10' 'a-b-1.2.2'
┌─────────┬─────────┬──────────┐
│a-b-1.2.1│a-b-1.2.2│a-b-1.2.10│
└─────────┴─────────┴──────────┘
            
      sortVersions 'a-b-1.2.10'
┌──────────┐
│a-b-1.2.10│
└──────────┘

      ]Box off
Was ON

      sortVersions 'a-b-1.2.3-test' 'a-b-1.2.3-prod' 'a-b-1.2.3-dev' 
 a-b-1.2.3-dev  a-b-1.2.3-prod  a-b-1.2.3-test 

      ⍪sortVersions ,pkgs  ⍝ pkgs is from the note above
 dyalog-HttpCommand-5.1.5  
 dyalog-HttpCommand-5.1.6  
 dyalog-HttpCommand-5.1.7  
 dyalog-HttpCommand-5.1.8  
 dyalog-HttpCommand-5.1.9  
 dyalog-HttpCommand-5.1.10 
 dyalog-HttpCommand-5.1.11 
 dyalog-HttpCommand-5.1.12 
 dyalog-HttpCommand-5.1.13
 dyalog-HttpCommand-5.1.14 
 dyalog-Jarvis-1.11.5      
 dyalog-Jarvis-1.11.6      
 dyalog-Jarvis-1.11.7      
 dyalog-Jarvis-1.11.8      
 dyalog-Jarvis-1.11.9      
 dyalog-Jarvis-1.11.10     

Task 3: Time for a Change

I happened to make a purchase the other day and the change came to $1.32. The cashier gave me a one-dollar bill worth (1.00), three dimes (worth 0.30), and two pennies (worth 0.02) totaling $1.32. It struck me that this was a sub-optimal solution - because a one-dollar bill and 4 coins – a quarter (worth 0.25), a nickel (worth 0.05) and two pennies (worth 0.02) would total the same but with fewer coins.

It occurred to me that there are lots of combinations of denominations that can sum to $1.32 – after writing a solution to this task, I found there are 646 combinations.

Write a function named makeChange that:

• takes an ascendingly-sorted integer vector left argument (named denom) representing a set of denominations.
• takes a single integer right argument (named amount) representing an amount.
• returns an integer matrix (that we'll call result) with (≢denom) columns where each row represents a unique combination of elements of denom that total amount. There will be as many rows as unique combinations of denom that total amount. The order of the rows is not significant. The following will be true:
  • amount ∧.= result +.× denom ⍝ all rows total amount
  • (≢result)=≢∪result ⍝ all rows are unique

Some sample denominations (banknotes and coins):

• Euro: euro←1 2 5 10 20 50 100 200 500 1000 5000 10000 20000
  representing: 1c 2c 5c 10c 20c 50c €1 €2 €5 €10 €20 €50 €100 €200 (€1 = 100c)
• UK: uk←1 2 5 10 20 50 100 200 500 1000 2000 5000
  representing: 1p 2p 5p 10p 20p 50p £1 £2 £5 £10 £20 £50 (£1 = 100p)
• USA: usa←1 5 10 25 50 100 500 1000 2000 5000 10000
  representing: 1¢ 5¢ 10¢ 25¢ 50¢ $1 $5 $10 $20 $50 $100 ($1 = 100¢)

Notes:

• The number of combinations grows exponentially based on the number of elements in denom and the value of amount. You can, therefore, assume that all test cases that will be used to validate your solution will return fewer than 100,000 combinations.
• Although speed is not a primary criteria for judging this task, if two solutions are roughly equivalent in their correctness and use of array-oriented techniques, the faster solution will be judged more favourably.

Examples

      1 2 5 makeChange 5
0 0 1
1 2 0
3 1 0
5 0 0

      ⍴2 5 10 makeChange 3
0 3

      ≢usa makeChange 132
646

      ≢usa makeChange 200
2728

      ≢euro makeChange 200
73682

Task 4: Array Partitioning

In this task you will write a function to partition an array into a vector of sub-arrays. The stencil operator ⌺ can be used to perform operations on sub-arrays of an APL array. While you are under no obligation to use stencil in your solution, it may be a good place to start.

Write a function named partition that:

• takes a rank-1 or greater APL array right argument (named array)
• takes a left argument (named spec) that contains the specifications for extracting the sub-arrays:
• the first element is a non-empty positive integer vector that has up to ≢⍴array elements and specifies the shape of the sub-arrays
• the second element is optional and, if it exists, it has the same shape as the first element and specifies the movement size for the partitioning. If not supplied or empty, the movement is assumed to be (≢1⊃spec)⍴1
• the third element is also optional, has ≢⍴array elements, and specifies the co-ordinates for the first partition. If not supplied or empty, the co-ordinates are assumed to be (≢⍴array)⍴1
Note: If spec is a simple depth 0 or 1 array, you should enclose it and use it as the sub-array shape specification (the movement and co-ordinate elements should be defaulted).
• returns a vector of sub-arrays of array, each of the shape described in spec[1;]. If no sub-arrays matching spec exist, return an empty vector.

Examples

      3 partition ⍳10 ⍝ start with a simple case
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬──────┐
│1 2 3│2 3 4│3 4 5│4 5 6│5 6 7│6 7 8│7 8 9│8 9 10│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴──────┘

      (,3)(,2) partition ⍳10 ⍝ movement is 2
┌─────┬─────┬─────┬─────┐
│1 2 3│3 4 5│5 6 7│7 8 9│
└─────┴─────┴─────┴─────┘

      (,3)(,2) 4 partition ⍳10 ⍝ start from the 4th position
┌─────┬─────┬──────┐
│4 5 6│6 7 8│8 9 10│
└─────┴─────┴──────┘

      5 5⍴⎕A
ABCDE
FGHIJ
KLMNO
PQRST
UVWXY

      3 partition 5 5⍴⎕A
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ABC│BCD│CDE│FGH│GHI│HIJ│KLM│LMN│MNO│PQR│QRS│RST│UVW│VWX│WXY│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

      (2 2)(2 3) partition 5 5⍴⎕A
┌──┬──┬──┬──┐
│AB│DE│KL│NO│
│FG│IJ│PQ│ST│
└──┴──┴──┴──┘

      (2 2)(2 3)(2 1) partition 5 5⍴⎕A ⍝ 2×2 sub-arrays; movement 2 rows, 3 columns; starting at [2;1]
┌──┬──┬──┬──┐
│FG│IJ│PQ│ST│
│KL│NO│UV│XY│
└──┴──┴──┴──┘

      (3 2)(2 1)(2 2 2) partition 4 5 6⍴⍳120
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬───────┬───────┬───────┬───────┐
│38 39│39 40│40 41│41 42│68 69│69 70│70 71│71 72│ 98  99│ 99 100│100 101│101 102│
│44 45│45 46│46 47│47 48│74 75│75 76│76 77│77 78│104 105│105 106│106 107│107 108│
│50 51│51 52│52 53│53 54│80 81│81 82│82 83│83 84│110 111│111 112│112 113│113 114│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴───────┴───────┴───────┴───────┘

      ⍴7 partition ⍳6 ⍝ can't get a 7-element sub-array from a 6-element array
0

      ⍴⊃7 partition ⍳6 ⍝ but the shape of the prototype matches the shape in spec
7

      1 partition ⍳5
┌─┬─┬─┬─┬─┐
│1│2│3│4│5│
└─┴─┴─┴─┴─┘

      ⍴¨1 partition ⍳5
┌─┬─┬─┬─┬─┐
│1│1│1│1│1│
└─┴─┴─┴─┴─┘