10
\$\begingroup\$

related


What's assignable to what?

In this challenge you will be given two types, A and B and determine if A is assignable to B, B is assignable to A, or neither.

The Type System

(I will use t to represent any type)

Basic Types

Basic types are represented by a single capital letter, such as X. They are basically classes.

  • X is assignable to Y if Y is either the same as, or a parent class of X.

Intersection Types

Intersection types are represented by intersect<X, Y>, and can have any number of types between the <'s (e.g. intersect<X, Y, Z, D, E>).

  • t is assignable to intersect<X1, X2... Xn> if t is assignable to all X.
  • intersect<X1, X2... Xn> is assignable to t if any X is assignable to t.

Union Types

Union types are represented by union<X, Y> and can have any number of types between the <'s (e.g. union<X, Y, Z, D, E>).

  • t is assignable to union<X1, X2... Xn> if t is assignable to any X.
  • union<X1, X2... Xn> is assignable to t if all X are assignable to t.

Input

You will receive as input:

  • The class hierarchy. You may choose the method of input for the class hierarchy. You can input a representation of a tree, or each type with a list of its parents, or anything else that accurately represents the class hierarchy.
  • Two types (input is flexible, as long as the notation is consistent you may receive these types however you like).

Output

You will output one of three consistent and distinct values, call them X, Y, and Z. Given two types A and B, output X if A is assignable to B, output Y if B is assignable to A and output Z otherwise (If A is assignable to B and B is assignable to A, you may output X, Y, both, or a fourth value).


Test Cases

Format:

# of types
[type, parents...]
[type, parents...]
Type a
Type b

2
[A,B]
[B]
A
B
--
A is assignable to B


3
[A,B,C]
[B,C]
[C]
intersect<A,C>
A
--
A is assignable to intersect<A,C>


3
[A,B,C]
[B,C]
[C]
union<A,C>
A
--
A is assignable to union<A,C>


3
[A,B,C]
[B,C]
[C]
intersect<B,C>
A
--
A is assignable to intersect<B,C>


3
[A,B,C]
[X,Y,Z]
[T,U,V]
intersect<union<A,T,X>,intersect<A,B>,Y>
intersect<T,C,X>
--
intersect<T,C,X> and intersect<union<A,T,X>,intersect<A,B>,Y> are not assignable to each other    

1
[A]
A
A
--
A is assignable to A


3
[A,B,C]
[X,Y,Z]
[T,U,V]
intersect<A,intersect<A,B>,Y>
intersect<T,C,X>
--
intersect<T,C,X> and intersect<A,intersect<A,B>,Y> are not assignable to each other


2
[A]
[B]
A
B
--
B and A are not assignable to each other

3
[A,B,C]
[X,Y,Z]
[T,U,V]
intersect<union<A,X>,intersect<A,B>,Y>
intersect<T,C,X>
--
intersect<T,C,X> and intersect<union<A,X>,intersect<A,B>,Y> are not assignable to each other

Here is a link to a working ungolfed Java solution you can use for testing (it takes input in the same way as the test cases)


This is code-golf, so least bytes in each language wins for that language!

\$\endgroup\$
  • \$\begingroup\$ Sandbox (deleted) \$\endgroup\$ – Socratic Phoenix Oct 24 '17 at 16:18
  • \$\begingroup\$ @ovs no, A has parents B and C. \$\endgroup\$ – Socratic Phoenix Oct 24 '17 at 20:52
  • \$\begingroup\$ @HalvardHummel apologies; I've edited the post \$\endgroup\$ – Socratic Phoenix Oct 24 '17 at 21:07
  • \$\begingroup\$ Will inherit form a circle? \$\endgroup\$ – tsh Oct 25 '17 at 9:13
  • \$\begingroup\$ What should output if both A is assignable to B and B is assignable to A? \$\endgroup\$ – tsh Oct 25 '17 at 9:13
3
\$\begingroup\$

Python 3, 177 bytes

c is a dictionary of the parents of each type, a and b are the two expression to check. Types are represented by strings, while intersects and unions are represented by lists with of expressions, with the first element set to 0for intersect and 1 for union

Returns 0 if they are not assignable to each other, 1 if a is assignable to b, 2 if b is assignable to a and 3 if both are assignable to each other

lambda c,a,b:y(a,b,c)+2*y(b,a,c)
y=lambda a,b,c:(b in c[a]or a==b if b[0]in c else[all,any][b[0]](y(a,x,c)for x in b[1:]))if a[0]in c else[any,all][a[0]](y(x,b,c)for x in a[1:])

Try it online!

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 138 bytes

(p,a,b,g=(a,b)=>a==b||(p[a]||a.i||a.u||[])[a.u?'every':'some'](t=>g(t,b))||(b.i||b.u||[])[b.i?'every':'some'](t=>g(a,t)))=>g(a,b)||+g(b,a)

p is the parent map, which is a JavaScript object whose keys are the types with parents and whose values are arrays of parent(s). For example, if there are two types A and B and B is the parent of A then p would be {A:['B']}.

Intersection types are represented in a and b as a JavaScript object with a key of i whose value is an array of types, while union types have a key of u. For example, the intersection of two types A and B would be {i:['A','B']}.

The return value is true if a is assignable to b, 1 if a is not assignable to b but b is assignable to a, or 0 if neither is assignable to each other.

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

C++17, 595 bytes

#include<type_traits>
#define p(x)template<class...T>class x;
#define d(a,b)disjunction<s<a,b>...>{};
#define c(a,b)conjunction<s<a,b>...>{};
#define u(x)u<x...>
#define i(x)i<x...>
#define k struct s
#define e ...A
#define t(a,b)template<class a,class b>
using namespace std;p(i)p(u)t(B,D)k:disjunction<is_base_of<B,D>,is_same<B,D>>{};t(a,e)k<a,u(A)>:d(a,A)t(a,e)k<a,i(A)>:c(a,A)t(a,e)k<u(A),a>:c(A,a)t(a,e)k<i(A),a>:d(A,a)t(e,...B)k<i(A),i(B)>:d(A,i(B))t(e,...B)k<u(A),u(B)>:c(A,u(B))t(e,...B)k<i(A),u(B)>:d(A,u(B))t(e,...B)k<u(A),i(B)>:c(A,u(B))t(A,B)int f=s<A,B>::value?-1:s<B,A>::value?1:0;

Try it online!

A variable template f that accepts as input some types and intersection i<...> or union u<...> of them and returns -1 if A is assignable to B and 1 if B is assignable to A and 0 otherwise.

Ungolfed:

#include <type_traits>
using namespace std;

template<class...T>class Intersect;
template<class...T>class Union;

template<class A,class B>
struct is_assignable_to:
    disjunction<is_base_of<A,B>,is_same<A,B>>{};

template<class a,class...A>
struct is_assignable_to<a,Union<A...>>:
    disjunction<is_assignable_to<a,A>...>{};

template<class a,class...A>
struct is_assignable_to<a,Intersect<A...>>:
    conjunction<is_assignable_to<a,A>...>{};

template<class a,class...A>
struct is_assignable_to<Union<A...>,a>:
    conjunction<is_assignable_to<A,a>...>{};

template<class a,class...A>
struct is_assignable_to<Intersect<A...>,a>:
    disjunction<is_assignable_to<A,a>...>{};

template<class...A,class...B>
struct is_assignable_to<Intersect<A...>,Intersect<B...>>:
    disjunction<is_assignable_to<A,Intersect<B...>>...>{};

template<class...A,class...B>
struct is_assignable_to<Union<A...>,Union<B...>>:
    conjunction<is_assignable_to<A,Union<B...>>...>{};

template<class...A,class...B>
struct is_assignable_to<Intersect<A...>,Union<B...>>:
    disjunction<is_assignable_to<A,Union<B...>>...>{};

template<class...A,class...B>
struct is_assignable_to<Union<A...>,Intersect<B...>>:
    conjunction<is_assignable_to<A,Intersect<B...>>...>{};

template <class A,class B>
int f = is_assignable_to<A,B>::value?-1:is_assignable_to<B,A>::value?1:0;

Usage:

#include <iostream>
int main(){
    struct B{};
    struct C{};
    struct Y{};
    struct Z{};
    struct U{};
    struct V{};
    struct A:B,C{};
    struct X:Y,Z{};
    struct T:U,V{};
    std::cout << f<Intersect<A,Intersect<A,B>,Y>,Union<T,C,X>>; 
}
\$\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.