題目：Advent of Code 2019 Day 3
使用語言：C#
第三天的題目稍微複雜一些，要將字串轉為行進方向，在座標上形成線，input為兩條線，Part1目標是得出這兩條線的曼哈頓距離。
首先光是為了理解曼哈頓距離就花了不少時間。這時候就覺得自己的英文閱讀能力有夠差……
這邊本來是想要利用斜率求交點，但因為斜率太久沒用早已忘光，再加上得到交點後還必須要確認點是不是有在指定的線段上，雖說Google研究後覺得理論上看起來應該是不難寫，但我實在是已經拖太久了，最後還是尋求了簡單暴力。
然後程式似乎沒有保留到Part2的部分……這段程式看起來只有算曼哈頓距離，然後Part2寫一半的感覺。
但總之還是先記錄著。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static void Main()
{
var firstWire = new string[] {"R990","U944","L921","U993","L64","U29","R899","D406","R841","U716","L32","U658","L830","D481","L441","U491", "L687","D847","L459","U920","R165","U224","L896","D868","L191","U877","L909","U467","R798","U132","R234","U49","R484","U911","R108","D308", "R867","U350","L404","U107","L84","U668","R850","U470","L182","U93","R284","U999","L664","U110","R650","D189","R540","D112","R794","U999", "R871","D829","L549","U988","R654","D411","R323","D774","R529","U275","L909","U936","R122","D922","L331","U813","L748","U770","R511","D892", "L770","U318","R661","U823","R210","D393","L694","U929","L76","D619","R395","U651","R526","U145","R851","U112","R73","D89","R17","U929","R807", "U87","R764","D158","L820","U803","L785","D205","L828","D271","L839","D482","L797","U338","R322","D633","L292","U16","R627","U19","R548","U516", "L384","U83","R256","U937","R404","U322","R671","D543","L412","U446","R238","U246","L794","D750","L34","U317","L994","U874","L247","D20","R491", "U834","L498","D987","R2","U175","R452","U168","R495","D183","R201","U532","L192","U984","L566","D471","L704","D2","L776","U5","R911","U308", "R763","D555","R458","D439","L968","D78","R549","D583","R289","D355","L503","D871","L881","U516","L507","D551","R711","U702","L308","D905", "L408","U932","L884","U218","L158","D562","L200","D114","R673","U448","R887","U181","R247","U329","L965","U495","L329","D162","L265","D389", "R419","U435","R258","U146","R208","D184","R730","D19","L78","D886","R472","D350","R484","U392","L542","U601","L202","U974","L310","U52","L537", "U597","L163","D655","R928","U269","L926","D790","L513","U441","L90","U581","L211","U871","R603","D130","L220","U459","L933","U648","R721", "U642","R301","U537","L858","D777","R823","U14","R820","D218","L96","D318","L206","U280","R887","D241","L752","U828","R354","U864","R844", "D872","L728","D298","L234","U695","R434","D94","R905","D592","L32","D860","R680","D197","R886","U760","L232","U916","L452","U248","R715", "D773","R867","U77","R751","D36","R565","U897","R782","U931","R546","U261","R920","D296","R451","U258","L394","U965","R912","D593","L990"};
var secondWire = new string[] {"L994","U515","R163","U863","L343","U162","L875","D92","L483","D601","R79","D761","L389","U167","L145","U145", "L247","U886","R61","U820","L584","D239","R402","U805","R956","U126","R615","D322","R431","D460","R397","D511","R805","D177","L778","U296", "R599","U759","R40","U1","L422","U751","R94","U401","R504","U940","L564","U24","R595","U944","R815","U672","R787","D854","R579","D604","L62", "U670","L516","U199","L639","D919","L485","U655","R391","U669","R772","D34","R868","D12","L108","U295","R701","D603","R493","U927","R29","D34", "R499","U111","L87","U190","R884","D658","R474","D166","R921","U698","R592","U25","R710","D398","L26","U696","L432","D887","R469","U656","L428", "D188","L543","D150","R160","U543","R743","U692","R618","D148","R956","U753","L175","D789","R897","U305","L137","D914","R330","D780","R744", "D473","L754","U482","L975","D413","L698","U656","L177","U419","R13","D827","L67","D800","R369","U97","L34","D588","L41","D760","L164","U224", "L921","D311","R489","U956","R277","U180","R724","U748","R785","U826","L426","D957","R303","U16","L729","U224","L712","U43","L280","D648", "R987","D941","R154","D581","R876","U615","L480","D103","R636","D276","R948","U89","R434","D212","R837","D295","R532","D390","R374","D926", "R911","D110","R258","U83","L955","U747","L925","D366","R571","U241","R628","D344","R919","U117","R337","D683","L720","U261","L124","D545", "R979","D601","L906","D324","R441","U678","L978","U744","L472","D217","R799","U740","L77","U964","L278","U497","R441","U21","L37","U319","L24", "D211","L44","U459","R35","D609","R900","D538","R397","D776","R629","D860","R519","D340","R168","U603","R46","U889","R897","D442","R997","U705", "L82","D963","R941","U701","L347","D824","R269","U891","L569","D558","L867","U145","R121","D369","R542","U227","L198","U863","L755","U273", "L734","D233","R578","U67","L821","U600","L203","D234","R695","U819","L639","D700","R295","D129","L612","U157","R212","U536","L968","U562", "L999","D391","L231","U262","R334","D967","R463","U748","R842","D500","R860","U856","R263","D633","R460","D337","L880","U146","R910"};
// Example
//var firstWire = new string[] {"R75","D30","R83","U83","L12","D49","R71","U7","L72"};
//var secondWire = new string[] {"U62","R66","U55","R34","D71","R55","D58","R83"};
var firstRoute = GetRoute(firstWire);
var secondRoute = GetRoute(secondWire);
var result = 0;
var targetPoint = new Coordinate();
var crossPoint = firstRoute.Join(secondRoute, f => new {f.x, f.y}, s => new {s.x, s.y}, (f, s) => f)
.Where(r=>!r.x.Equals(0) && !r.y.Equals(0)).ToList();
foreach(var point in crossPoint)
{
var Manhattandistance = Math.Abs(point.x) + Math.Abs(point.y);
if(result.Equals(0) || result > Manhattandistance)
{
targetPoint = point;
result = Manhattandistance;
}
}
firstRoute = firstRoute.Where(x=>x.step<targetPoint.step).ToList();
firstRoute.Add(targetPoint);
secondRoute = secondRoute.Where(x=>x.step<targetPoint.step).ToList();
secondRoute.Add(targetPoint);
var firstRouteDistance = GetTargetDistance(firstRoute, targetPoint.step);
var secondRouteDistance = GetTargetDistance(secondRoute, targetPoint.step);
Console.WriteLine(result);
Console.WriteLine(firstRouteDistance+secondRouteDistance);
}
public class Coordinate
{
public int x {get;set;}
public int y {get;set;}
public int step {get;set;}
public bool isDest {get;set;}
}
public static List<Coordinate> GetRoute(string[] routeMap)
{
var result = new List<Coordinate>();
var position = new Coordinate() {x=0, y=0, step=0, isDest=true};
for(int i = 0; i< routeMap.Length;i++)
{
var data = CalculateCoordinate(position, routeMap[i]);
position = data.position;
result.AddRange(data.route);
}
return result;
}
public static int GetTargetDistance(List<Coordinate> source, int step)
{
var distance = 0;
for(int i = 0;i < step;i++)
{
//Console.WriteLine(GetDistance(source[i], source[i+1]));
distance += GetDistance(source[i], source[i+1]);
}
return distance;
}
public static int GetDistance(Coordinate startPoint, Coordinate endPoint)
{
return Math.Abs(startPoint.x - endPoint.x) + Math.Abs(startPoint.y - endPoint.y);
}
public static (Coordinate position, List<Coordinate> route) CalculateCoordinate(Coordinate position, string move)
{
var result = position;
var vector = move.Substring(0, 1);
var distance = Convert.ToInt32(move.Substring(1));
var route = new List<Coordinate>();
result.step += 1;
result.isDest = true;
switch(vector)
{
case "R":
route.AddRange(GetRoutePoints(result.x, result.x + distance, result.y, vector, result.step));
result.x += distance;
break;
case "L":
route.AddRange(GetRoutePoints(result.x - distance, result.x, result.y, vector, result.step));
result.x -= distance;
break;
case "U":
route.AddRange(GetRoutePoints(result.y, result.y + distance, result.x, vector, result.step));
result.y += distance;
break;
case "D":
route.AddRange(GetRoutePoints(result.y - distance, result.y, result.x, vector, result.step));
result.y -= distance;
break;
}
route.Add(result);
return (result, route);
}
public static List<Coordinate> GetRoutePoints(int start, int end, int fixPoint, string direction, int step)
{
var result = new List<Coordinate>();
for(int i = start;i<end;i++)
{
if(direction.Equals("R") ||direction.Equals("L"))
result.Add(new Coordinate() {x=i, y=fixPoint, step = step, isDest=false});
if(direction.Equals("U") ||direction.Equals("D"))
result.Add(new Coordinate() {x=fixPoint, y=i, step = step, isDest=false});
}
return result;
}
}
Comments