Skip to content

Instantly share code, notes, and snippets.

@isaksky
Last active November 4, 2019 16:33
Show Gist options
  • Save isaksky/8f9dd4189d1563b49c038bff73ead181 to your computer and use it in GitHub Desktop.
Save isaksky/8f9dd4189d1563b49c038bff73ead181 to your computer and use it in GitHub Desktop.
Solution to Robot Journey in TSQL https://github.com/mikehadlow/Journeys
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
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