DataFilter
TCCC '04 Finals · 2004-02-23 · by dgoodman
Problem Statement
Each worker has his own unique id that is a string of digits, the first of which is always zero ('0'). Each worker has a name consisting of uppercase letters 'A'-'Z', and has an age that is an integer with no leading zeros. Neither name nor age can be relied upon to be unique. Each data record contains information for a single worker, and is formatted to contain no leading or trailing spaces. It may contain 1, 2, or all 3 of the fields (name, age, id) in any order. The fields within a record will be separated by one or more spaces.
Create a class DataFilter that contains a method untangle that is
given a
Each element of data consists of one or more records, separated from each other by a single semicolon (';'). If there is more than one way to untangle the data, return the smallest possible number of workers. If there is no consistent interpretation of the data, return -1.
Notes
- Ids should be treated as strings, not numbers.
Constraints
- data will contain between 1 and 50 elements inclusive.
- Each element of data will contain between 1 and 50 characters inclusive.
- Each element of data will consist of 1 or more records, separated from each other by a single ';'
- Each record in each element of data will contain no leading or trailing spaces.
- Each record will contain exactly 1, 2, or 3 fields separated by (possibly multiple) spaces.
- No record will contain more than one age, name, or id.
- Each age will be between 1 and 150 inclusive, and will not have a leading '0'
- Each id will contain between 1 and 10 characters inclusive, all digits and having a leading '0'
- Each name will contain between 1 and 10 characters inclusive, all uppercase letters 'A'-'Z'
{"BOB 22 013","17 BOB;22","0234","16"}
Returns: 3
data consists of 5 records (one of the elements of data contains 2 records, separated by a ';'). One of the records has all 3 fields, one of the records has 2 fields, and the other records each have just a single field. There are at least 3 different workers since there are 3 different ages. [BOB 22 013],[BOB 17 0234],[TOM 16 099] is one possibility that is consistent with these 5 data records.
{"2 01;02 B;B;B 02;2 02;C 02"}
Returns: -1
One record has the employee with id 02 being named B, while another record claims that 02 is named C. So these records are inconsistent.
{"A 21","B 21","B 23","A 23","01 A","02 21","B 03","04 B"}
Returns: 4
One way to untangle these 8 records into just 4 employees is [A 23 01], [B 21 03], [B 23 04], [A 21 02].
{"A 23","B 21","B 23","A 21","01 A","02 21","B 03","04 B"}
Returns: 4
{"001 AA","002 51","003 BB","004 52","005 CC","006 53",
"007 DD","008 54","009 EE","010 55","011 FF","012 56",
"013 GG","014 57","015 HH","016 58","017 II","018 59",
"019 JJ","020 60","021 KK","022 61","023 LL","024 62","025 MM",
"AA 51","BB 51","BB 52","CC 52","CC 53","DD 53","DD 54","EE 54",
"EE 55","FF 55","FF 56","GG 56","GG 57","HH 57","HH 58","II 58",
"II 59","JJ 59","JJ 60","KK 60","KK 61","LL 61","LL 62","MM 53",
"CC 60"};
Returns: 25
{"JHA 01",
"06 86",
"GEJ 07",
"18",
"02 60",
"FCD 42",
"CDJ"}
Returns: 5
01 JHA ?? 02 ??? 60 06 ??? 86 07 GEJ ?? ?? ??? 18 ?? FCD 42 ?? CDJ ??
{"00 BOB 22","0 BOB 22"}
Returns: 2
Id's 0 and 00 are different, so these two cannot be combined.
{"C 11;01 11;02 D;E 12","C 18;00 C;A 18;03 18"}
Returns: 5
00 C 18 01 C 11 02 D ?? 03 A 18 04 E 12
Submissions are judged against all 67 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DataFilter with a public method int untangle(vector<string> data) · 67 test cases · 2 s / 256 MB per case