Last active
November 4, 2019 16:33
-
-
Save isaksky/8f9dd4189d1563b49c038bff73ead181 to your computer and use it in GitHub Desktop.
Solution to Robot Journey in TSQL https://github.com/mikehadlow/Journeys
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
declare @input nvarchar(max) = | |
N'1 1 E | |
RFRFRFRF | |
1 1 E | |
3 2 N | |
FRRFLLFFRRFLL | |
3 3 N | |
0 3 W | |
LLFFFLFLFL | |
2 4 S'; | |
declare @journeys as table (id int, startpos nvarchar(max), endpos nvarchar(max), instructions nvarchar(max)); | |
-- Phase 1: Parsing the string | |
with tmp as ( | |
select j as txt, ROW_NUMBER() OVER(order by (select 1)) as [rn] | |
from STRING_SPLIT(@input, CHAR(13)) cross apply (SELECT REPLACE(REPLACE(value, CHAR(13), ''), CHAR(10), '') as j) b | |
where j <> '' | |
) | |
insert into @journeys(id, startpos, endpos, instructions) | |
select ROW_NUMBER() OVER(order by start_pos.rn) as id, trim(start_pos.txt), trim(end_pos.txt), trim(instrs.txt) | |
from (select * from tmp where rn % 3 = 1) as start_pos | |
outer apply (select * from tmp tmp2 where rn % 3 = 2 and tmp2.rn = start_pos.rn + 1) instrs | |
outer apply (select * from tmp tmp2 where rn % 3 = 0 and tmp2.rn = start_pos.rn + 2) end_pos | |
declare @journey_steps as table (journey_id int, n int, x int, y int, dir char(1)); | |
insert into @journey_steps(journey_id, n, x, y, dir) | |
select id, 0 as n, | |
CAST(SUBSTRING (j, 1, 1) as int), | |
CAST(SUBSTRING (j, 2, 1) as int), | |
SUBSTRING (j, 3, 1) | |
from @journeys a cross apply (select trim(replace(startpos, ' ', '')) as j) b | |
-- Phase 2: Lookup tables used in solution | |
declare @directions as table (n int identity(0,1), dir char(1)); | |
insert into @directions(dir) values ('N'), ('E'), ('S'), ('W'); | |
declare @forward_offsets as table (dir char(1), x int , y int); | |
insert into @forward_offsets values ('N', 0, 1), ('E', 1, 0), ('S', 0, -1), ('W', -1, 0); | |
-- Phase 3: Solution via recursive CTE | |
with steps as ( | |
select journey_id, n, x, y, dir, CAST('' as nvarchar(max)) as instr_applied | |
from @journey_steps b | |
union all | |
select prev.journey_id, prev.n + 1, isnull(new_x, prev.x), isnull(new_y, prev.y), isnull(new_dir, prev.dir), cur_instr | |
from steps prev | |
join @journeys j on j.id = prev.journey_id | |
join @directions prev_dir on prev.dir = prev_dir.dir | |
cross apply ( | |
select SUBSTRING(j.instructions, prev.n + 1, 1) as cur_instr | |
) instr | |
outer apply ( | |
select new_x, new_y | |
from (select x, y from @forward_offsets o where cur_instr = 'F' and o.dir = prev.dir) o | |
cross apply (select prev.x + o.x as new_x, prev.y + o.y as new_y) n | |
) new_pos | |
outer apply ( | |
select d.dir as new_dir | |
from (select case cur_instr when 'R' then 1 when 'L' then -1 end as dir_incr) a | |
join @directions d on d.n % 4 = (prev_dir.n + dir_incr + 4) % 4 -- Note: the +4 is to ensure it wraps properly with negative increments | |
) new_dir | |
where prev.n <= len(instructions) | |
) | |
select journey_id, n as step_number, x, y, dir, instr_applied, j.startpos, j.endpos as expected_end | |
from steps s | |
join @journeys j on j.id = s.journey_id | |
order by journey_id, n |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
startpos | step_number | x | y | dir | instr_applied | expected_end | |
---|---|---|---|---|---|---|---|
1 1 E | 0 | 1 | 1 | E | 1 1 E | ||
1 1 E | 1 | 1 | 1 | S | R | 1 1 E | |
1 1 E | 2 | 1 | 0 | S | F | 1 1 E | |
1 1 E | 3 | 1 | 0 | W | R | 1 1 E | |
1 1 E | 4 | 0 | 0 | W | F | 1 1 E | |
1 1 E | 5 | 0 | 0 | N | R | 1 1 E | |
1 1 E | 6 | 0 | 1 | N | F | 1 1 E | |
1 1 E | 7 | 0 | 1 | E | R | 1 1 E | |
1 1 E | 8 | 1 | 1 | E | F | 1 1 E | |
1 1 E | 9 | 1 | 1 | E | 1 1 E | ||
3 2 N | 0 | 3 | 2 | N | 3 3 N | ||
3 2 N | 1 | 3 | 3 | N | F | 3 3 N | |
3 2 N | 2 | 3 | 3 | E | R | 3 3 N | |
3 2 N | 3 | 3 | 3 | S | R | 3 3 N | |
3 2 N | 4 | 3 | 2 | S | F | 3 3 N | |
3 2 N | 5 | 3 | 2 | E | L | 3 3 N | |
3 2 N | 6 | 3 | 2 | N | L | 3 3 N | |
3 2 N | 7 | 3 | 3 | N | F | 3 3 N | |
3 2 N | 8 | 3 | 4 | N | F | 3 3 N | |
3 2 N | 9 | 3 | 4 | E | R | 3 3 N | |
3 2 N | 10 | 3 | 4 | S | R | 3 3 N | |
3 2 N | 11 | 3 | 3 | S | F | 3 3 N | |
3 2 N | 12 | 3 | 3 | E | L | 3 3 N | |
3 2 N | 13 | 3 | 3 | N | L | 3 3 N | |
3 2 N | 14 | 3 | 3 | N | 3 3 N | ||
0 3 W | 0 | 0 | 3 | W | 2 4 S | ||
0 3 W | 1 | 0 | 3 | S | L | 2 4 S | |
0 3 W | 2 | 0 | 3 | E | L | 2 4 S | |
0 3 W | 3 | 1 | 3 | E | F | 2 4 S | |
0 3 W | 4 | 2 | 3 | E | F | 2 4 S | |
0 3 W | 5 | 3 | 3 | E | F | 2 4 S | |
0 3 W | 6 | 3 | 3 | N | L | 2 4 S | |
0 3 W | 7 | 3 | 4 | N | F | 2 4 S | |
0 3 W | 8 | 3 | 4 | W | L | 2 4 S | |
0 3 W | 9 | 2 | 4 | W | F | 2 4 S | |
0 3 W | 10 | 2 | 4 | S | L | 2 4 S | |
0 3 W | 11 | 2 | 4 | S | 2 4 S |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment