Type Inheritance
Description
You are writing a transcompiler that will be able to translate programs from one programming language to another. Your transcompiler needs to be able to analyze a program to understand what data types it uses and how they should be mapped to the types of the output language.
In order to handle this, you created an inheritance table, which has the following structure:
- derived: a unique data type in the original language;
- base: the base data type from which the
derived
type is inherited.
It’s guaranteed that there are no cyclic dependencies.
For each translated program a variables table is created, which has the following structure:
- var_name: the unique variable name;
- type: the variable type.
Your task is to write a query that will find the variables of types that are inherited from the Number
type. The resulting table should contain var_name
and var_type
columns and be sorted by var_names
.
Example
For the following tables inheritance
derived | base |
---|---|
Double | Number |
Int | Number |
Int64 | Int |
Number | Object |
and variables
var_name | type |
---|---|
A | Int |
B | Object |
C | Double |
D | Int64 |
E | Number |
the output should be
var_name | var_type |
---|---|
A | Int |
C | Double |
D | Int64 |
Type Int64
is inherited from type Int
, which in turn is inherited from Number
type, so both variables A
and D
should be included in the result. Double
type is also inherited from Number
, so C
is also present in the resulting table.
- [execution time limit] 10 seconds (mysql)
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*Please add ; after each select statement*/
CREATE FUNCTION isNumber(class VARCHAR(45))
RETURNS BOOLEAN
BEGIN
DECLARE basec VARCHAR(45) DEFAULT '';
DECLARE next VARCHAR(45) DEFAULT NULL;
DECLARE ret BOOLEAN DEFAULT FALSE;
DECLARE i INT DEFAULT 0;
SET next = class;
SET ret = FALSE;
SET i = 0;
WHILE i < 200 AND (NOT ret) AND (SELECT COUNT(base) FROM inheritance WHERE derived = next LIMIT 1) DO
SELECT base INTO basec FROM inheritance WHERE derived = next LIMIT 1;
SET ret = IF(IFNULL(basec,'') = 'Number', TRUE, FALSE);
SET next = basec;
SET i = i+1;
END WHILE;
RETURN ret OR i > 100;
END;
CREATE PROCEDURE typeInheritance()
BEGIN
SELECT var_name, type as var_type FROM variables WHERE isNumber(type) ORDER BY var_name;
END