17
\$\begingroup\$

Background

The number of values for a given type is called the cardinality of that type, and that of type T is written as |T|.

Haskell and a few other languages have a certain set of enum types, each of which has a small finite number of values (the exact names vary, so this challenge uses some arbitrarily chosen names).

Name  | Cardinality
------+-------------
Never | 0
Unit  | 1
Bool  | 2 (true or false)
Order | 3 (LT, EQ, or GT)

And they also have some derived types which have one or more type parameters. Their cardinality depends on which types they get as parameters (written as T and U in the table below). Func(T,U) represents the function commonly written as T -> U, i.e. a function that takes a parameter of type T and returns a value of type U.

Name(Params) | Cardinality
-------------+-------------
Option(T)    | |T| + 1     (some value from T, or absence)
Either(T,U)  | |T| + |U|   (some value from T or some value from U)
Pair(T,U)    | |T| * |U|   (any combination of values from T and U)
Func(T,U)    | |U| ** |T|  (any combination of U for every value of T)

Note: A "function" here is to be understood as a mathematical concept rather than a programming one. A mathematical function Func(T,U) maps every possible value of T to some value of U, disregarding the "how". For programmers, it is OK to think of it as functions of the form of (in Haskell-like pseudocode):

\(x :: T) -> case x of
  value1OfT -> someValue1OfU
  value2OfT -> someValue2OfU
  ...
  valueXOfT -> someValueXOfU

with all cases provided.

For example, Option(Never) has cardinality 1, and Func(Bool,Order) has cardinality 3**2 = 9. Func(Never,Never) has cardinality 1; 0**0 is defined to be 1 in this system.

A type parameter can itself be a derived type, so Pair(Func(Never,Never),Pair(Either(Bool,Bool),Option(Order))) is also a valid type, which has cardinality of (0**0) * ((2+2) * (3+1)) = 16.

For this challenge, assume that no types other than the 8 presented above are available.

Challenge

Given a string that represents a valid type in this system, output its cardinality. You can assume the input does not contain spaces.

Standard rules apply. The shortest code in bytes wins.

Test cases

Never -> 0
Unit -> 1
Bool -> 2
Order -> 3
Func(Never,Never) -> 1
Func(Unit,Never) -> 0
Option(Unit) -> 2
Option(Order) -> 4
Either(Bool,Bool) -> 4
Either(Bool,Order) -> 5
Pair(Bool,Order) -> 6
Pair(Func(Never,Never),Pair(Either(Bool,Bool),Option(Order))) -> 16
Func(Func(Order,Order),Order) -> 7625597484987
\$\endgroup\$
3
  • \$\begingroup\$ I cannot understand why Either(Bool, Bool) should be 4. Won't it noly support true and false anyway? \$\endgroup\$
    – tsh
    Oct 14 at 2:13
  • 1
    \$\begingroup\$ @tsh Using Haskell terms, Either(T,U) has two constructors Left(T) and Right(U), and Left(True) != Right(True). So you get four values in total: Left(True), Left(False), Right(True), Right(False). \$\endgroup\$
    – Bubbler
    Oct 14 at 2:15
  • 2
    \$\begingroup\$ @tsh It's not a simple union type, but a labeled union type. \$\endgroup\$ Oct 16 at 0:11

11 Answers 11

17
\$\begingroup\$

Proton, 80 bytes

Never,Unit,Bool,Order=0..4
Option=(1+)
Either=(+)
Pair=(*)
Func=(x,y)=>y**x
eval

Try it online!

This solution is a whole lot shorter in Proton. Original Python solution included below.

Python 3, 106 bytes

Never=0
Unit=1
Bool=2
Order=3
Option=1 .__add__
Either=int.__add__
Pair=int.__mul__
Func=int.__rpow__
eval

Try it online!

-3 bytes thanks to dingledooper

__rpow__ exists so I don't even have to do lambda x,y:y**x so this is even more boring :D

trivial solution and I'm sure there's something both better and smarter

\$\endgroup\$
7
  • \$\begingroup\$ Perhaps I'm missing something but the bare eval at the end seems not to do anything? \$\endgroup\$
    – Dingus
    Oct 14 at 3:54
  • \$\begingroup\$ @Dingus It's the actual function that produces the output. \$\endgroup\$ Oct 14 at 3:56
  • 3
    \$\begingroup\$ Funny solution! I think you can replace lambda x,y:y**x with int.__rpow__? \$\endgroup\$ Oct 14 at 4:07
  • 2
    \$\begingroup\$ Is there a special rule that allows this format for function answers? It looks to me half way between full program and function: you cannot assign this code to a variable and call it like a function, or use it in a place where a lambda function would be accepted, like in another function's parameter.. \$\endgroup\$
    – Kaddath
    Oct 14 at 7:50
  • 4
    \$\begingroup\$ @Kaddath Functions are allowed to depend on previous code (such as other function declarations), if that's what you mean? \$\endgroup\$
    – Neil
    Oct 14 at 8:30
6
\$\begingroup\$

05AB1E, 77 31 28 bytes

Rv"0123>+*m ""NUBdpEPF"ykè.V

Byte-count more than halved and sped up a lot by porting @Neil's Charcoal answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

R                            # Reverse the (implicit) input-string
 v                           # Loop over each of its characters `y`:
             "NUBdpEPF"yk    #  Get the index of `y` in "NUBdpEPF"
                             #  (which will result in -1 if it isn't present)
  "0123>+*m "            è   #  Use it to (0-base modulair) index into "0123>+*m "
                          .V #  Execute it as 05AB1E code:
                             #   `>`: Increment the top value by 1
                             #   `+`: Add the top two values together
                             #   `*`: Multiply the top two values
                             #   `m`: Take the exponent of the top two values
                             #   The digits 0-3 remain the same
                             #   ` `: No-op for not found characters / index -1
                             # (after which the result is output implicitly)

Original (77 bytes) answer:

”†™‰¿ëÄ‚Ñ”#ā<:Δ”íŽ‰‡¥Öˆ¦c”#vD.γd}þàÝ©NĀiã©',ý}€…(ÿ)yì®N_i>ëíðý…m+*Nè«}øvy`.V:

Because 05AB1E lacks both regexes and functions, this uses a brute-force replacement method wrapped in a loop. It's therefore also extremely slow the larger the integer becomes, and will fail to complete the final test cases as is.

Try it online or verify all test cases (the Δ is replaced with [Dd# in the test suite to speed it up slightly, so we can also verify the last test case).

Explanation:

”†™‰¿ëÄ‚Ñ”       # Push dictionary string "Never Unit Bool Order"
          #      # Split it on spaces: ["Never","Unit","Bool","Order"]
           ā     # Push a list in the range [1,length] (without popping): [1,2,3,4]
            <    # Decrease each to the range [0,length): [0,1,2,3]
             :   # Replace all "Never" with 0; "Unit" with 1; etc. in the (implicit)
                 # input-string
Δ                # Loop until the result no longer changes:
[Dd#             # (slightly faster alternative, so we'll have one iteration less:)
[                #  Start an infinite loop
 D               #   Duplicate the current string
  d              #   If it's a non-negative (>=0) integer:
   #             #    Stop the infinite loop
 ”펉‡¥Öˆ¦c”     #  Push dictionary string "Option Either Pair Func"
            #    #  Split it on spaces: ["Option","Either","Pair","Func"]
 v               #  Loop over each string `y` in this list:
  D.γd}þà        #   Get the current maximum integer in the string:
  D              #    Duplicate the string
   .γ            #    Group this string into substrings by:
     d           #     If it's a non-negative (>=0) integer
      }þ         #    After the group-by, only leave these integers
        à        #    And pop and push the maximum
         Ý       #   Pop and push a list in the range [0,max]
          ©      #   Store it in variable `®`
  NĀi            #   If the index is NOT 0 (thus not "Option"):
     ã           #    Take the cartesian product of this list
      ©          #    Store that in variable `®` instead
       ',ý      '#    And join each inner pair with "," delimiter
    }€…(ÿ)       #   After the if-statement: wrap each integer/string into parenthesis
          yì     #   And prepend the current string `y`
  ®              #   Push list `®` again
   N_i           #   If the index is 0 (thus "Option"):
      >          #    Simply increase the value by 1
     ë           #   Else:
      í          #    Reverse each pair in the list
       ðý        #    Join each pair with space delimiter
         …m+*    #    Push string "m+*"
             Nè  #    Index the loop-index into it (0-based modulair)
               « #    Append it to each string
     }ø          #   After the if-else statement: zip to create pairs of the two lists
       v         #   Loop over each pair `y` in this list:
        y        #    Push the pair `y`
         `       #    Pop and push both values separated to the stack
          .V     #    Execute the second string as 05AB1E code, resulting in an integer
            :    #    Replace the first string to this integer
                 # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to use the dictionary?) to understand why ”†™‰¿ëÄ‚Ñ” is "Never Unit Bool Order" and ”펉‡¥Öˆ¦c” is "Option Either Pair Func".

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Ugh, another boring eval-based answer ;-) \$\endgroup\$
    – Neil
    Oct 15 at 8:34
  • \$\begingroup\$ @Neil Haha, I guess yeah. Seems to be the shortest approach, based on my two programs. ;p \$\endgroup\$ Oct 15 at 8:45
5
\$\begingroup\$

JavaScript (V8), 98 bytes

Never=0
Unit=1
Bool=2
Order=3
Option=x=>1+x
Either=(x,y)=>x+y
Pair=Math.imul
Func=(x,y)=>y**x
eval

Try it online!

Same idea as @hyper-neutrino, though its shorter in js

-1 byte thanks to @Arnauld

\$\endgroup\$
2
  • 2
    \$\begingroup\$ You can save a byte by using Math.imul instead of (x,y)=>x*y (32-bit only, though). \$\endgroup\$
    – Arnauld
    Oct 14 at 9:10
  • \$\begingroup\$ @Arnuald nice, thanks! \$\endgroup\$
    – wasif
    Oct 14 at 10:15
4
\$\begingroup\$

Retina, 129 bytes

Or
Q
{T`NUBQ)(l`0-3;_
O(\d+);
$.(_$1*
E(\d+),(\d+);
$.($1*_$2*
P(\d+),(\d+);
$.($1*$2*
F(\d+)
F$1*
(F_*)_(,\d+;)
P$1$2$2
F,\d+;
1

Try it online! Link includes test cases. Explanation:

Or
Q

Change Order to Qder to avoid confusion with Option, and also because O has special meaning for Transliterate.

{

Repeat the remaining transformations until the desired result is obtained. (The transliteration does not need to be repeated but it's golfer to share the `.)

T`NUBQ)(l`0-3;_

Transliterate the Never, Unit, Bool and Qder to 0 to 3 respectively, transliterate the ) to ; for ease of matching, and delete the lower case letters and (.

O(\d+);
$.(_$1*

Handle Option by incrementing the value.

E(\d+),(\d+);
$.($1*_$2*

Handle Either by taking the sum of the values.

P(\d+),(\d+);
$.($1*$2*

Handle Pair by taking the product of the values.

F(\d+)
F$1*

Convert the first parameter of Func to unary.

(F_*)_(,\d+;)
P$1$2$2

Compute Func(n+1,m) as Func(n,m)*m using P to do the multiplication.

F,\d+;
1

Func(0,m) is just 1.

Retina 0.8.2, 111 bytes

Op.{5}
EU,
T`NUB\O)(l`0-3;_
\d
$*
E(1*),(1*);
$1$2
(P1*)1(,1*;)
E$1$2$2
P,1*;

(F1*)1(,1*;)
P$1$2$2
}`F,1*;
1
1

Try it online! Link includes reduced test cases, as Retina 0.8.2 has to calculate in unary, which limits the magnitude of the result. Explanation:

Op.{5}
EU,

Change Option( to Either(Unit, (except preabbreviated).

T`NUB\O)(l`0-3;_

Transliterate the Never, Unit, Bool and Order to 0 to 3 respectively, transliterate the ) to ; for ease of matching, and delete the lower case letters and (.

\d
$*

Convert to unary.

E(1*),(1*);
$1$2

Handle Either by taking the sum of the values.

(P1*)1(,1*;)
E$1$2$2

Compute Pair(n+1,m) as Pair(n,m)+m using E to do the addition.

P,1*;

Pair(0,m) is just 0.

(F1*)1(,1*;)
P$1$2$2

Compute Func(n+1,m) as Func(n,m)*m using P to do the multiplication.

F,1*;
1

Func(0,m) is just 1.

}`

Repeat the above transformations until the desired result is obtained.

1

Convert to decimal.

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES7), 103 bytes

A regex-based solution. This is longer than using @hyper-neutrino's method, but not as much longer as I was expecting.

s=>eval(s.replace(/\w+/g,s=>(i="enorpiau".search(s[1]))<4?i:`((x,y)=>y${['|1+','+','*','**'][i&3]}x)`))

Try it online!

How?

All keywords can be unambiguously identified by looking at the second character. Hence the lookup string "enorpiau" and an index i into this string. We use the pattern ((x,y)=>y…x) for all operations.

 i | keyword  | translation
---+----------+----------------
 0 | N[e]ver  | 0
 1 | U[n]it   | 1
 2 | B[o]ol   | 2
 3 | O[r]der  | 3
 4 | O[p]tion | ((x,y)=>y|1+x)
 5 | E[i]ther | ((x,y)=>y+x)
 6 | P[a]ir   | ((x,y)=>y*x)
 7 | F[u]nc   | ((x,y)=>y**x)
\$\endgroup\$
3
\$\begingroup\$

Julia 1.0, 87 bytes

eval∘Meta.parse
Never,Unit,Bool,Order=0:3
Option,Pair,Either=x->x+1,*,+
Func(x,y)=y^x

Try it online!

Same idea as the other answers

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 66 61 60 bytes

F⮌S«≡ιd⊞υ³B⊞υ²U⊞υ¹N⊞υ⁰p⊞υ⊕⊟υE⊞υ⁺⊟υ⊟υP⊞υ×⊟υ⊟υF«≔⊟υθ⊞υX⊟υθ»»Iυ

Try it online! Link is to verbose version of code. Edit: Saved 5 bytes thanks to @KevinCruijssen pointing out that d and p uniquely identify Order and Option. Saved 1 byte by finding a slightly shorter way to exponentiate. Explanation:

F⮌S«

Loop over the characters of the input string in reverse order.

≡ι

Switch on the current character.

d⊞υ³

For (Or)d(er) push 3 to the predefined empty list.

B⊞υ²

For B(ool) push 2 to the predefined empty list.

U⊞υ¹

For U(nit) push 1 to the predefined empty list.

N⊞υ⁰

For N(ull) push 0 to the predefined empty list.

O⊞υ⊕⊟υ

For (O)p(tion) increment the top of the list.

E⊞υ⁺⊟υ⊟υ

For E(ither) sum the top two elements of the list.

P⊞υ×⊟υ⊟υ

For P(air) multiply the top two elements of the list.

F«≔⊟υθ⊞υX⊟υθ»

For F(unc) exponentiate the top two elements of the list. (Unfortunately the elements are in the wrong order, complicating the code. I tried processing the string from left to right which avoids that issue but that then requires an operator stack which ends up making the code much longer.)

»

Ignore any other characters.

Iυ

Output the final result.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ -5 bytes by removing the split on "Or" and join on null-bytes, by simply using "d" and "p" as switch options, instead of null and "O": try it online. \$\endgroup\$ Oct 15 at 7:53
1
\$\begingroup\$

Ruby, 120 95 bytes

p=i=->x,y=1{x+y}
a=->x,y{x*y}
u=->x,y{y**x}
f=->s{eval s.gsub(/\w+/){$&[1]}.tr'enor()','0-3[]'}

Try it online!

  • Thanks to @Dingus for the 25 Bytes saved!
\$\endgroup\$
0
1
\$\begingroup\$

R, 121 bytes

Or R>=4.1, 100 bytes by replacing the three function appearances with \s.

function(s,Never=0,Unit=1,Bool=2,Order=3,Option=function(x)x+1,Either=`+`,Pair=`*`,Func=function(a,b)b^a)eval(parse(t=s))

Try it online!

R doesn't have a simple eval, you need to parse the string first.

\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 92 bytes

Never=0
Unit=1
Bool=2
Order=3
Option(x)=1+x
Either(x,y)=x+y
Pair(x,y)=x*y
Func(x,y)=y^x
eval

Try it online!

The same as @hyper-neutrino's and @wasif's answers.

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 105 bytes

s/\w(.)\w+/$1/g;y/enor/0123/;1while s|([piau]).(\d+)(,(\d+))?\)|($4//1).({a,'*',u,'**'}->{$1}//'+').$2|ee

Try it online!

\$\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.