Background and Motivation:
IOC Country Codes are three letter abbreviations that are commonly used when broadcasting the Olympic Games. The last two letters of some codes overlap with the first two letters of other codes (RUS -> USA, JPN -> PNG), etc. Clearly, you can transform the first country code into the second by removing the first letter, and adding a new letter at the end. Sometimes, you can chain these transformations into a longer path (RUS -> USA -> SAM).
I want to find determine whether a path exists between 2 given country codes (using a provided list like the IOC list or the FIFA list) in order to impress party guests, and in the event that multiple paths exist, I'd like to output the longest one. To keep the output small enough to sneak into a commercial break, paths are compressed by not repeating common substrings between adjacent country codes: RUS -> USA -> SAM would be written as RUSAMfor example.
If multiple equal length paths are possible, you can select any result (previously asked for a deterministic tiebreaking rule that "I could explain to a partygoer." I would still appreciate answers that include this, but it's probably not a good objective rule that constrains whether an answer is correct.)
The Technical Challenge
Inputs:
- initial 3 letter country code
- terminal 3 letter country code
- set of valid 3 letter country codes
Outputs:
Determine whether a string exists such that:
- the first three letters are identical to the initial 3 letter country code
- The last three letters are identical to the terminal 3 letter country code
- each 3-letter substring corresponds to a valid country code from the input set
- the same country code cannot appear twice in the string (with the exception that the first 3 characters and the last 3 characters can be the same)
If one such string exists, print that string as the output. If multiple such strings exist, print the longest such string. If no such string exists, any of the following are acceptable:
- no output
- falsey output
- error
Other ways of indicating that no such path exists are also allowed as long as they can't be confused for a valid path.
Valid Assumptions:
*The initial 3 letter country code and the terminal 3 letter country code are both contained in the provided set of valid 3 letter country codes.
Invalid Assumptions:
*The input set cannot be assumed to be ordered for purposes of producing a deterministic output.
*The initial 3 letter country code cannot be assumed to be different from the terminal country code (cyclic requests are allowed)
Extra Style Points (Not Necessary for Submission to be Valid):
If your answer includes a description of a deterministic tie-breaking rule you are using to determine which string to output when multiple identical length strings exist that meet all the above criteria, then you'll make this internet stranger very happy. Preferably something easy enough to explain to a random Olympics viewer, which is too fuzzy to be a good requirement for a valid submission.
Scoring:
This is code golf, so the shortest answer (in bytes) wins. Standard Loopholes apply.
Test Cases
Input 1: "AAA", "ZZZ", ["AAA", "AAZ", "AZZ", "ZZZ"]
Output 1: "AAAZZZ" (Find valid path if it exists)
Input 2: "AAA", "ZZZ", ["AAA", "AAZ", "AZZ", "ZZZ", "AAB", "ABB", "BBB", "BBZ", "BZZ", "ZZZ"]
Output 2: "AAABBBZZZ" (Find longest path if short and long paths both exist)
Input 3: "AAA", "ZZZ", ["AAA", "ZZZ"]
Output 3: Crash, falsey message, or no output (just don't output "AAAZZZ" or something that could be confused for a path)
Input 4: "AAA", "ZZZ", ["AAA", "AAB", "ABZ", "BZZ", "AAY", "AYZ", "YZZ", "ZZZ"],
Output 4: "AAABZZZ" OR "AAAYZZZ", but you must explain what rule decided which one to output (consistent behavior that follows your chosen rule)
Input 5: "AAA", "AAA", ["AAA", "ABA", "AAB", "BAA"],
Output 5: "AAABAAA" (Test case where initial code == terminal code, but other codes should be included in result)
Input 6: "AAA", "AAA", ["AAA", "ABA"],
Output 6: "AAA" ("AAABAAA" is not valid because "AAB" and "BAA" are 3 letter substrings contained in the answer which are not part of the valid set of country codes)
Input 7: "ISL", "ERI",
["AFG", "AHO", "AIA", "ALB", "ALG", "AND", "ANG", "ANT", "ARG", "ARM", "ARU", "ASA", "AUS", "AUT", "AZE", "BAH", "BAN", "BAR", "BDI", "BEL", "BEN", "BER", "BHU", "BIH", "BIZ", "BLR", "BOL", "BOT", "BRA", "BRN", "BRU", "BUL", "BUR", "CAF", "CAM", "CAN", "CAY", "CGO", "CHA", "CHI", "CHN", "CIV", "CMR", "COD", "COK", "COL", "COM", "CPV", "CRC", "CRO", "CUB", "CYP", "CZE", "DEN", "DJI", "DMA", "DOM", "ECU", "EGY", "ERI", "ESA", "ESP", "EST", "ETH", "FAR", "FGU", "FIJ", "FIN", "FLK", "FPO", "FRA", "FSM", "GAB", "GAM", "GBR", "GBS", "GEO", "GEQ", "GER", "GHA", "GIB", "GRE", "GRL", "GRN", "GUA", "GUD", "GUI", "GUM", "GUY", "HAI", "HEL", "HKG", "HON", "HUN", "INA", "IND", "IRI", "IRL", "IRQ", "ISL", "ISR", "ISV", "ITA", "IVB", "JAM", "JOR", "JPN", "KAZ", "KEN", "KGZ", "KIR", "KOR", "KSA", "KUW", "LAO", "LAT", "LBA", "LBR", "LCA", "LES", "LIB", "LIE", "LTU", "LUX", "MAC", "MAD", "MAR", "MAS", "MAW", "MAY", "MDA", "MDV", "MEX", "MGL", "MGO", "MKD", "MLI", "MLT", "MNT", "MON", "MOZ", "MRI", "MRT", "MSH", "MTN", "MYA", "NAM", "NCA", "NCD", "NED", "NEP", "NFI", "NGR", "NIG", "NIU", "NMA", "NOR", "NRU", "NZL", "OMA", "PAK", "PAN", "PAR", "PER", "PHI", "PLE", "PLW", "PNG", "POL", "POR", "PRK", "PUR", "QAT", "REU", "ROU", "RSA", "RUS", "RWA", "SAM", "SEN", "SEY", "SIN", "SKN", "SLE", "SLO", "SMR", "SOL", "SOM", "SPM", "SRB", "SRI", "STP", "SUD", "SUI", "SUR", "SVK", "SWE", "SWZ", "SYR", "TAN", "TGA", "THA", "TJK", "TKM", "TKS", "TLS", "TOG", "TPE", "TTO", "TUN", "TUR", "TUV", "UAE", "UGA", "UKR", "URU", "USA", "UZB", "VAN", "VEN", "VIE", "VIN", "WAF", "YEM", "ZAM", "ZIM"]
Output 7: ISLESTPERI (real world test case: IOC codes ISL -> SLE -> LES -> EST -> STP -> TPE -> PER -> ERI corresponding to Iceland -> Sierra Leone -> Lesotho -> Estonia -> Sao Tome and Principe -> Republic of China -> Peru -> Eritrea)
Input 8: USA, USA,
["ABW", "AFG", "AGO", "AIA", "ALA", "ALB", "AND", "ARE", "ARG", "ARM", "ASM", "ATA", "ATF", "ATG", "AUS", "AUT", "AZE", "BDI", "BEL", "BEN", "BES", "BFA", "BGD", "BGR", "BHR", "BHS", "BIH", "BLM", "BLR", "BLZ", "BMU", "BOL", "BRA", "BRB", "BRN", "BTN", "BVT", "BWA", "CAF", "CAN", "CCK", "CHE", "CHL", "CHN", "CIV", "CMR", "COD", "COG", "COK", "COL", "COM", "CPV", "CRI", "CUB", "CUW", "CXR", "CYM", "CYP", "CZE", "DEU", "DJI", "DMA", "DNK", "DOM", "DZA", "ECU", "EGY", "ERI", "ESH", "ESP", "EST", "ETH", "FIN", "FJI", "FLK", "FRA", "FRO", "FSM", "GAB", "GBR", "GEO", "GGY", "GHA", "GIB", "GIN", "GLP", "GMB", "GNB", "GNQ", "GRC", "GRD", "GRL", "GTM", "GUF", "GUM", "GUY", "HKG", "HMD", "HND", "HRV", "HTI", "HUN", "IDN", "IMN", "IND", "IOT", "IRL", "IRN", "IRQ", "ISL", "ISR", "ITA", "JAM", "JEY", "JOR", "JPN", "KAZ", "KEN", "KGZ", "KHM", "KIR", "KNA", "KOR", "KWT", "LAO", "LBN", "LBR", "LBY", "LCA", "LIE", "LKA", "LSO", "LTU", "LUX", "LVA", "MAC", "MAF", "MAR", "MCO", "MDA", "MDG", "MDV", "MEX", "MHL", "MKD", "MLI", "MLT", "MMR", "MNE", "MNG", "MNP", "MOZ", "MRT", "MSR", "MTQ", "MUS", "MWI", "MYS", "MYT", "NAM", "NCL", "NER", "NFK", "NGA", "NIC", "NIU", "NLD", "NOR", "NPL", "NRU", "NZL", "OMN", "PAK", "PAN", "PCN", "PER", "PHL", "PLW", "PNG", "POL", "PRI", "PRK", "PRT", "PRY", "PSE", "PYF", "QAT", "REU", "ROU", "RUS", "RWA", "SAU", "SDN", "SEN", "SGP", "SGS", "SHN", "SJM", "SLB", "SLE", "SLV", "SMR", "SOM", "SPM", "SRB", "SSD", "STP", "SUR", "SVK", "SVN", "SWE", "SWZ", "SXM", "SYC", "SYR", "TCA", "TCD", "TGO", "THA", "TJK", "TKL", "TKM", "TLS", "TON", "TTO", "TUN", "TUR", "TUV", "TWN", "TZA", "UGA", "UKR", "UMI", "URY", "USA", "UZB", "VAT", "VCT", "VEN", "VGB", "VIR", "VNM", "VUT", "WLF", "WSM", "YEM", "ZAF", "ZMB", "ZWE"]
Output 8: "USAUSA" (real world test case: ISO3166-Alpha-3 codes representing the path USA -> SAU -> AUS -> USA corresponding to United States -> Saudi Arabia -> Australia -> United States)
Data:
All country codes for the real world examples was taken from https://datahub.io/core/country-codes#data if you want to play with it more. The paths were a lot shorter and less interesting than I thought they'd be when I started this question (I guess the country codes don't populate the space of 3 letter strings densely enough), but someone else may find something interesting to do with them.
Reference Code: In case you prefer code you can play with over written test cases (or simply want to play with various paths but don't want to solve the challenge), here's some reference (ungolfed) code that solves all test cases quickly.
def pathfinder_helper(initial_code, terminal_code, valid_codes):
if initial_code != terminal_code:
if initial_code[1:] == terminal_code[:-1]:
return [initial_code, terminal_code]
if not valid_codes:
if initial_code == terminal_code:
return [initial_code]
return None
best_path = None
for intermediate_code in valid_codes:
# Pure speed optimization, can be left out and be "correct" but will be super slow on cases 7 and 8
if initial_code[1:] != intermediate_code[:-1]:
continue
initial_intermediate_path = pathfinder_helper(initial_code, intermediate_code, valid_codes - {intermediate_code})
intermediate_terminal_path = pathfinder_helper(intermediate_code, terminal_code, valid_codes - {intermediate_code})
if initial_intermediate_path and intermediate_terminal_path:
# Longer paths preferred
if (best_path is None) or len(initial_intermediate_path + intermediate_terminal_path[1:]) >= len(best_path):
if best_path and len(initial_intermediate_path + intermediate_terminal_path[1:]) == len(best_path):
# If lengths equal, use sort order (lexicographic)
if initial_intermediate_path + intermediate_terminal_path[1:] < best_path:
best_path = initial_intermediate_path + intermediate_terminal_path[1:]
else:
best_path = initial_intermediate_path + intermediate_terminal_path[1:]
return best_path
def pathfinder(initial_code, terminal_code, valid_codes):
path = pathfinder_helper(initial_code, terminal_code, valid_codes - {initial_code, terminal_code})
if path:
return ''.join([path[0]] + [code[-1] for code in path[1:]])
print("Case 0:", pathfinder("AAA", "AAA", {"AAA"}))
print("Case 1:", pathfinder("AAA", "ZZZ", {"AAA", "AAZ", "AZZ", "ZZZ"}))
print("Case 2:", pathfinder("AAA", "ZZZ", {"AAA", "AAZ", "AZZ", "ZZZ", "AAB", "ABB", "BBB", "BBZ", "BZZ", "ZZZ"}))
print("Case 3:", pathfinder("AAA", "ZZZ", {"AAA", "ZZZ"}))
print("Case 4:", pathfinder("AAA", "ZZZ", {"AAA", "AAB", "ABZ", "BZZ", "AAY", "AYZ", "YZZ", "ZZZ"}))
print("Case 5:", pathfinder("AAA", "AAA", {"AAA", "ABA", "AAB", "BAA"}))
print("Case 6:", pathfinder("AAA", "AAA", {"AAA", "ABA"}))
print("Case 7:", pathfinder("ISL", "ERI", {"AFG", "AHO", "AIA", "ALB", "ALG", "AND", "ANG", "ANT", "ARG", "ARM", "ARU", "ASA", "AUS", "AUT", "AZE", "BAH", "BAN", "BAR", "BDI", "BEL", "BEN", "BER", "BHU", "BIH", "BIZ", "BLR", "BOL", "BOT", "BRA", "BRN", "BRU", "BUL", "BUR", "CAF", "CAM", "CAN", "CAY", "CGO", "CHA", "CHI", "CHN", "CIV", "CMR", "COD", "COK", "COL", "COM", "CPV", "CRC", "CRO", "CUB", "CYP", "CZE", "DEN", "DJI", "DMA", "DOM", "ECU", "EGY", "ERI", "ESA", "ESP", "EST", "ETH", "FAR", "FGU", "FIJ", "FIN", "FLK", "FPO", "FRA", "FSM", "GAB", "GAM", "GBR", "GBS", "GEO", "GEQ", "GER", "GHA", "GIB", "GRE", "GRL", "GRN", "GUA", "GUD", "GUI", "GUM", "GUY", "HAI", "HEL", "HKG", "HON", "HUN", "INA", "IND", "IRI", "IRL", "IRQ", "ISL", "ISR", "ISV", "ITA", "IVB", "JAM", "JOR", "JPN", "KAZ", "KEN", "KGZ", "KIR", "KOR", "KSA", "KUW", "LAO", "LAT", "LBA", "LBR", "LCA", "LES", "LIB", "LIE", "LTU", "LUX", "MAC", "MAD", "MAR", "MAS", "MAW", "MAY", "MDA", "MDV", "MEX", "MGL", "MGO", "MKD", "MLI", "MLT", "MNT", "MON", "MOZ", "MRI", "MRT", "MSH", "MTN", "MYA", "NAM", "NCA", "NCD", "NED", "NEP", "NFI", "NGR", "NIG", "NIU", "NMA", "NOR", "NRU", "NZL", "OMA", "PAK", "PAN", "PAR", "PER", "PHI", "PLE", "PLW", "PNG", "POL", "POR", "PRK", "PUR", "QAT", "REU", "ROU", "RSA", "RUS", "RWA", "SAM", "SEN", "SEY", "SIN", "SKN", "SLE", "SLO", "SMR", "SOL", "SOM", "SPM", "SRB", "SRI", "STP", "SUD", "SUI", "SUR", "SVK", "SWE", "SWZ", "SYR", "TAN", "TGA", "THA", "TJK", "TKM", "TKS", "TLS", "TOG", "TPE", "TTO", "TUN", "TUR", "TUV", "UAE", "UGA", "UKR", "URU", "USA", "UZB", "VAN", "VEN", "VIE", "VIN", "WAF", "YEM", "ZAM", "ZIM"}))
print("Case 8:", pathfinder("USA", "USA", {"ABW", "AFG", "AGO", "AIA", "ALA", "ALB", "AND", "ARE", "ARG", "ARM", "ASM", "ATA", "ATF", "ATG", "AUS", "AUT", "AZE", "BDI", "BEL", "BEN", "BES", "BFA", "BGD", "BGR", "BHR", "BHS", "BIH", "BLM", "BLR", "BLZ", "BMU", "BOL", "BRA", "BRB", "BRN", "BTN", "BVT", "BWA", "CAF", "CAN", "CCK", "CHE", "CHL", "CHN", "CIV", "CMR", "COD", "COG", "COK", "COL", "COM", "CPV", "CRI", "CUB", "CUW", "CXR", "CYM", "CYP", "CZE", "DEU", "DJI", "DMA", "DNK", "DOM", "DZA", "ECU", "EGY", "ERI", "ESH", "ESP", "EST", "ETH", "FIN", "FJI", "FLK", "FRA", "FRO", "FSM", "GAB", "GBR", "GEO", "GGY", "GHA", "GIB", "GIN", "GLP", "GMB", "GNB", "GNQ", "GRC", "GRD", "GRL", "GTM", "GUF", "GUM", "GUY", "HKG", "HMD", "HND", "HRV", "HTI", "HUN", "IDN", "IMN", "IND", "IOT", "IRL", "IRN", "IRQ", "ISL", "ISR", "ITA", "JAM", "JEY", "JOR", "JPN", "KAZ", "KEN", "KGZ", "KHM", "KIR", "KNA", "KOR", "KWT", "LAO", "LBN", "LBR", "LBY", "LCA", "LIE", "LKA", "LSO", "LTU", "LUX", "LVA", "MAC", "MAF", "MAR", "MCO", "MDA", "MDG", "MDV", "MEX", "MHL", "MKD", "MLI", "MLT", "MMR", "MNE", "MNG", "MNP", "MOZ", "MRT", "MSR", "MTQ", "MUS", "MWI", "MYS", "MYT", "NAM", "NCL", "NER", "NFK", "NGA", "NIC", "NIU", "NLD", "NOR", "NPL", "NRU", "NZL", "OMN", "PAK", "PAN", "PCN", "PER", "PHL", "PLW", "PNG", "POL", "PRI", "PRK", "PRT", "PRY", "PSE", "PYF", "QAT", "REU", "ROU", "RUS", "RWA", "SAU", "SDN", "SEN", "SGP", "SGS", "SHN", "SJM", "SLB", "SLE", "SLV", "SMR", "SOM", "SPM", "SRB", "SSD", "STP", "SUR", "SVK", "SVN", "SWE", "SWZ", "SXM", "SYC", "SYR", "TCA", "TCD", "TGO", "THA", "TJK", "TKL", "TKM", "TLS", "TON", "TTO", "TUN", "TUR", "TUV", "TWN", "TZA", "UGA", "UKR", "UMI", "URY", "USA", "UZB", "VAT", "VCT", "VEN", "VGB", "VIR", "VNM", "VUT", "WLF", "WSM", "YEM", "ZAF", "ZMB", "ZWE"}))
