Post date: Feb 26, 2017 3:26:59 PM
"Given a text file containing roman numerals, rewrite each number in the most efficient roman numeral form and find how many characters are saved by the conversion."
There are two ways to do this. The simple and boring way and the more fun way.
The simple and boring way is to do straight replacements.
CREATE TABLE #Roman (Roman varchar(50) NOT NULL)
BULK INSERT #Roman FROM 'D:\roman.txt' WITH (ROWTERMINATOR = '0x0a')
-- We have 6 replaces to do, and they need to be in order.
; WITH Conversions (old, new) AS
(
SELECT r.Roman
, REPLACE(
REPLACE(
REPLACE(
REPLACE(
REPLACE(
REPLACE(r.Roman, 'DCCCC', 'CM'),
'CCCC', 'CD'),
'LXXXX', 'XC'),
'XXXX', 'XL'),
'VIIII', 'IX'),
'IIII', 'IV')
FROM #Roman r
)
SELECT SUM(LEN(old) - LEN(new))
FROM Conversions
DROP TABLE #Roman
The more fun way is to decode the roman numerals to get a decimal number and then to encode the integers in the most efficient way.
CREATE TABLE #Decoding (i INT PRIMARY KEY NOT NULL, coded varchar(50) NOT NULL)
INSERT INTO #Decoding VALUES (4, 'IV'), (9, 'IX'), (40, 'XL'), (90, 'XC'), (400, 'CD'), (900, 'CM')
CREATE TABLE #Roman (Roman varchar(50) NOT NULL)
BULK INSERT #Roman FROM 'D:\roman.txt' WITH (ROWTERMINATOR = '0x0a')
ALTER TABLE #Roman ADD Cleaned varchar(50)
ALTER TABLE #Roman ADD Converted int NOT NULL DEFAULT 0
UPDATE #Roman
SET Cleaned = Roman
-- The numbers we get are simple additive numbers except for these special subtractive combinations.
-- We have to clear them out first or we'll have problems
-- We need to be careful to do one update and one sum. There are some in the table that match twice.
WHILE 1 = 1
BEGIN
UPDATE r
SET Converted = Converted + d.i, Cleaned = REPLACE(Cleaned, d.coded, '')
FROM #Roman r
INNER JOIN #Decoding d
ON r.Cleaned LIKE '%' + d.coded + '%'
IF @@ROWCOUNT = 0 BREAK
END
UPDATE #Roman
SET Converted = Converted + (1000 * (LEN(Cleaned) - LEN(REPLACE(Cleaned, 'M', ''))))
WHERE Cleaned LIKE '%M%'
UPDATE #Roman
SET Converted = Converted + 500 -- Only one D is allowed
WHERE Cleaned LIKE '%D%'
UPDATE #Roman
SET Converted = Converted + (100 * (LEN(Cleaned) - LEN(REPLACE(Cleaned, 'C', ''))))
WHERE Cleaned LIKE '%C%'
UPDATE #Roman
SET Converted = Converted + 50 -- Only one L is allowed
WHERE Cleaned LIKE '%L%'
UPDATE #Roman
SET Converted = Converted + (10 * (LEN(Cleaned) - LEN(REPLACE(Cleaned, 'X', ''))))
WHERE Cleaned LIKE '%X%'
UPDATE #Roman
SET Converted = Converted + 5 -- Only one V is allowed
WHERE Cleaned LIKE '%V%'
UPDATE #Roman
SET Converted = Converted + (LEN(Cleaned) - LEN(REPLACE(Cleaned, 'I', '')))
WHERE Cleaned LIKE '%I%'
CREATE TABLE #Encoding (i INT PRIMARY KEY NOT NULL, coded varchar(50) NOT NULL)
INSERT INTO #Encoding VALUES (0, ''),
(1, 'I'), (2, 'II'), (3, 'III'), (4, 'IV'), (5, 'V'),
(6, 'VI'), (7, 'VII'), (8, 'VIII'), (9, 'IX'),
(10, 'X'), (20, 'XX'), (30, 'XXX'), (40, 'XL'),
(50, 'L'), (60, 'LX'), (70, 'LXX'), (80, 'LXXX'), (90, 'XC'),
(100, 'C'), (200, 'CC'), (300, 'CCC'), (400, 'CD'),
(500, 'D'), (600, 'DC'), (700, 'DCC'), (800, 'DCCC'), (900, 'CM')
; WITH RomanesEuntDomus (i, coded) AS
(
SELECT ec.i + ed.i + eo.i, ec.coded + ed.coded + eo.coded
FROM #Encoding eo
CROSS JOIN #Encoding ed
CROSS JOIN #Encoding ec
WHERE eo.i < 10
AND (ed.i BETWEEN 10 AND 90 OR ed.i = 0)
AND (ec.i >= 100 OR ec.i = 0)
)
SELECT SUM(LEN(Roman) - LEN(REPLICATE('M',n.Converted/1000) + red.coded))
FROM #Roman n
INNER JOIN RomanesEuntDomus red
ON red.i = n.Converted % 1000
DROP TABLE #Encoding
DROP TABLE #Decoding
DROP TABLE #Roman