10
\$\begingroup\$

Background

Ada is a programming language that is not exactly known for its terseness.

However, its array literal syntax can in theory allow for fairly terse array specifications. Here is a simple EBNF description of the array literal syntax (passable to bottlecaps.de:

array ::= positional_array | named_array
positional_array ::= expression ',' expression (',' expression)*
                   | expression (',' expression)* ',' 'others' '=>' expression
named_array ::= component_association (',' component_association)*
component_association ::= discrete_choice_list '=>' expression
discrete_choice_list ::= discrete_choice ('|' discrete_choice)*
discrete_choice ::= expression ('..' expression)? | 'others'

We will limit ourselves to 1-dimensional arrays of integers for simplicity. This means that we will use only integers for the expression values. Perhaps in a future challenge we could try something more advanced (like declaring variables and multidimensional arrays). You do not have to golf the integer literals.

Here are some examples of Ada array literals and a python-esque equivalent representation for clarity:

(1, 2, 3) = [1, 2, 3]
(1, others => 2) = [1, 2, 2, ..., 2]
(others => 1) = [1, 1, ..., 1]
(1 => 1, 2 => 3) = [1, 3]
(1|2 => 1, 3 => 2) = [1, 1, 2]
(1 => 1, 3 => 2, others => 3) = [1, 3, 2, 3, 3, ..., 3]

Challenge

The goal of this challenge is to output the shortest byte-count Ada array literal for a given input array. Note that Ada arrays can start from whatever index is desired, so you can pick what you wish the starting index to be as long as each value is sequential. In this example I choose to start at 1, which is idiomatic for Ada, however you can choose to start at any other integer.

Input

Your input will consist of a list of integers, in whatever form is convenient.

Output

Your output will be a string of text representing the shortest valid Ada array literal that represents the list of input integers. You may use any starting index you wish on this array, but your choice (whatever it is) must be specified in your answer (the starting index may also be dynamic).

The integers are to represented as signed decimal numbers, as in the examples. This challenge does not cover golfing of integer values.

Examples

Here are some examples:

Simple: [1, 2, 3] -> (1,2,3)
Range: [1, 1, 1, 1, 1, 1, 1,] -> (1..7=>1)
Others: [1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1] -> (6=>2,others=>1)
Multiple Ranges: [1,1,1,1,1,2,2,2,2,2,1,1,1,1,1,2,2,2,2,2,1,1,1,1,1] -> (6..10|16..20=>2,others=>1)
Tiny Ranges: [1,1,2,2,1,1,1,1,1] -> (3|4=>2,others=>1)
Far Range: [[1]*5, [2]*100, [3]*5] -> (1..5=>1,6..105=>2,others=>3)
Alternation: [1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2] -> (1|3|5|7|9|11|13|15|17=>1,others=>2)
Big Number: [1234567890,1,1234567890] -> (2=>1,1|3=>1234567890)
Big-ish Number: [1234567,1,1234567] -> (1234567,1,1234567)
Solo: [-1] -> (1=>-1)
Huge Input: [[0],[1]*1000000000] -> (0,others=>1)
Positional Others: [1, 2, 3, 3, 3, 3, 3, 3] -> (1,2,others=>3)
Range and Choice, no Others: [1,1,1,12,12,3,3,3,3,3,3,3,3,3,3,4] -> (1..3=>1,4|5=>12,6..15=>3,16=>4)

Minimum Requirements

  • Support at least 100 numbers and inputs of at least 256 numbers in length.

  • Produce the correct result for all such inputs

    • Includes putting 'others' at the end
    • Includes putting an index for single item arrays
  • Terminate (preferably on TIO) for each of the above inputs in under a minute.

Shortest solution in bytes wins!

Reference Implementation

Try it online!

This implementation uses the input as its array, with each character being a number. Capital letters are special constants for large values. The program argument is the 'start index' to use.

The "code" section in the TIO link is a correct solution to the problem, while the "header" and "footer" implement the test structure.

\$\endgroup\$
  • 3
    \$\begingroup\$ Does the "Far Range" case exist simply to indicate that we may take input in that format if we choose or to highlight that we have to be able to handle that input format as well as normal arrays? Also, shouldn't the last test case just output (-1)? \$\endgroup\$ – Shaggy May 13 at 17:43
  • 3
    \$\begingroup\$ The "Far Range" case is merely written that way to save space, the actual input would be a flat array consisting of 110 integers, but the output is correct. Its purpose is to demonstrate cases where the 'others' keyword should go on a shorter range that has a longer representation. (106..110=>3,others=>2 would be longer) The last case needs to have an index, as the grammar doesn't allow single element positional arrays (positional_array ::= expression ',' expression (',' expression)*) \$\endgroup\$ – LambdaBeta May 13 at 17:52
  • 1
    \$\begingroup\$ In theory, could (and should) a list of 100,000,000 \$1\$'s be encoded as (1=>1,others=>1) since it's shorter than (1..100000000=>1)? \$\endgroup\$ – Arnauld May 13 at 18:12
  • 2
    \$\begingroup\$ Could you please confirm that (1|3=>1234567,2=>1) is another valid output for [1234567,1,1234567]? \$\endgroup\$ – Arnauld May 13 at 22:52
  • 1
    \$\begingroup\$ Are we allowed to use Ada as our language of choice? \$\endgroup\$ – Benjamin Urquhart May 13 at 23:01
5
\$\begingroup\$

JavaScript (ES6),  307  304 bytes

Saved 2 bytes thanks to @KevinCruijssen

This is embarrassingly long ...

a=>[b=([...a,m=''].map(o=(v,i)=>(i?p==v?!++n:m=o[(o[p]=[o[p]&&o[p]+'|']+(n?i-n+(n>1?'..':'|')+i:i))[m.length]?(x=i-n,j=p):j]:1)&&(p=v,M=n=0)),Object.keys(o).map(k=>j-k|!m[6]?o[k]+'=>'+k:O,O='others=>'+j).sort()),1/a[1]?[...a]:b,j-a.pop()?b:a.slice(0,x-1)+[,O]].map(a=>M=M[(s=`(${a})`).length]||!M?s:M)&&M

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 305 bytes (-2) by creating a variable for the duplicated 'others=>'. \$\endgroup\$ – Kevin Cruijssen May 15 at 11:07
  • \$\begingroup\$ @KevinCruijssen Thanks! (NB: In your version, t is used before it's defined; the reason why it doesn't crash is that the first 2 test cases don't use it at all; that can be easily fixed at no cost, though.) \$\endgroup\$ – Arnauld May 15 at 11:25
  • \$\begingroup\$ Ah ok. I didn't really ungolf your answer to see what was used where. I simply noticed you had 'others' two times and tried to create a variable for it without changing the output. ;) Thanks for explaining it though, and nice golf of the comma by using [,O]. :) \$\endgroup\$ – Kevin Cruijssen May 15 at 11:36
2
\$\begingroup\$

05AB1E, 136 134 132 bytes

"',ý'(ì')«ˆ"©.V"θ…ˆ†=>쪮.V"Uγ¨D€gPi˜IX.V}\ÙεQƶ0KDāαγ€g£}D2Fε¾iεнyg≠iyθyg<i'|ë„..}ý}}ë˜}'|ý„=>«Iyнн<è«}Ю.VgFDN._ć'>¡X.V}\¼}¯éIgi¦}н

EDIT: Fixed for all test cases now.

Try it online or verify all test cases (except for the 'Huge Input' one, since it's too big).

Explanation:

"',ý'(ì')«ˆ"       # Push this string (function 1), which does:
 ',ý              '#  Join a list by ","
    '(ì           '#  Prepend a "("
       ')«        '#  Append a ")"
          ˆ        #  Pop and add it to the global array
            ©      # Store this string in the register (without popping)
             .V    # And execute it as 05AB1E code on the (implicit) input-list
"θ…ˆ†=>쪮.V"      # Push this string (function 2), which does:
 θ                 #  Pop and push the last element of the list
  …ˆ†=>ì           #  Prepend dictionary string "others=>"
        ª          #  Append that to the list which is at the top of the stack
         ®.V       #  And execute function 1 from the register     
             U     # Pop and store this string in variable `X`
γ                  # Get the chunks of equal elements in the (implicit) input-list
 ¨                 # Remove the last chunk
  D                # Duplicate the list of remaining chunks
   €g              # Get the length of each
     Pi     }      # If all chunk-lengths are 1:
       ˜           #  Flatten the list of remaining chunks
        I          #  Push the input-list
         X.V       #  Execute function 2 from variable `X`
             \     # Discard the top of the stack (in case we didn't enter the if-statement)
Ù                  # Uniquify the (implicit) input-list
 ε                 # Map each unique value `y` to:
  Q                #  Check for each value in the (implicit) input-list if it's equal to `y`
                   #  (1 if truthy; 0 if falsey)
   ƶ               #  Multiply each by its 1-based index
    0K             #  Remove all 0s
      D            #  Duplicate it
       ā           #  Push a list [1, length] without popping the list itself
        α          #  Get the absolute difference at the same indices
         γ         #  Split it into chunks of the same values
          €g       #  Get the length of each
            £      #  And split the duplicated indices-list into those parts
                   # (this map basically groups 1-based indices per value.
                   #  i.e. input [1,1,2,1,1,2,2,1,1] becomes [[[1,2],[4,5],[8,9]],[[3],[6,7]]])
 }D                # After the map: duplicate the mapped 3D list
   2F              # Loop 2 times:
     ε             #  Map the 3D list of indices to:
      ¾i           #   If the counter_variable is 1:
        ε          #    Map each list `y` in the 2D inner list to:
         н         #     Leave the first value
         yg≠i      #     And if there is more than one index:
             yθ    #      Push the last value as well
             yg<i  #      If there are exactly two indices:
              '|  '#       Push string "|"
             ë     #      Else (there are more than two indices)
              „..  #       Push string ".."
             }ý    #      And join the first and last value by this string
        }}         #    Close the if-statement and map
      ë            #   Else:
       ˜           #    Flatten the 2D list
      }'|ý        '#   After the if-else: join by "|"
          „=>«     #   Append "=>"
       yнн         #   Get the very first index of this 2D list
          <        #   Decrease it by 1 to make it 0-based
      I    è       #   And index it into the input-list to get its value again
            «      #   Which is also appended after the "=>"
     }Ð            #  After the map: triplicate the result
       ®.V         #  Execute function 1 from the register
       g           #  Get the amount of items in the triplicated list
        F          #  Loop that many times:
         D         #   Duplicate the list
          N._      #   Rotate it the index amount of times
          ć        #   Extract the head; pop and push remainder and head
           '>¡    '#   Split this head by ">"
              X.V  #   And then function 2 is executed again from variable `X`
        }\         #  After the loop: discard the list that is still on the stack
          ¼        #  And increase the counter_variable by 1
   }¯              # After looping twice: push the global array
     é             # Sort it by length
      Igi }        # If the input only contained a single item:
         ¦         #  Remove the very first item
           н       # And then only leave the first item
                   # (which is output implicitly as result)

See this 05AB1E tip of mine (section How to compress strings not part of the dictionary?) to understand why …ˆ†=> is "others=>".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.