중요 편집 : 이전에는 예 1에서 잘못된 값이있었습니다. 수정되었습니다.
각 셀에 4 개의 값 중 하나가 포함 된 2 차원 배열이 제공됩니다.
예 :
1 2 2 2 2 1 @ . . X X V
1 3 1 4 1 4 e . @ I C V
2 3 1 3 4 2 H H @ X I V
1 4 4 2 1 3 V C C
2 2 2 3 2 3 X X X
4 개의 값은 방향 화살표 (위, 아래, 왼쪽 및 오른쪽)를 나타내지 만 어떤 값이 어떤 방향을 나타내는 지 모릅니다.
방향 화살표는 배열의 모든 셀을 포함하는 끊어지지 않은 경로를 형성하지만 시작점 또는 끝 점이 어디에 있는지는 모릅니다.
네 가지 값 각각이 나타내는 방향과 시작 및 끝 지점의 위치를 결정하는 코드를 작성하십시오.
값 A, B, C 및 D를 포함하는 배열에 허용되는 반환 값은 다음과 같습니다.
{ up: A, down: C, left: D, right: B, start: [2, 0], end: [4, 2] }
처음부터 끝까지 그리고 끝에서 끝까지 양방향으로 경로를 탐색 할 수 있기 때문에 항상 올바른 솔루션이 둘 이상 있으며 둘 이상이있을 수 있습니다. 위의 예에서와 같이 수신 한 입력에 항상 하나 이상의 올바른 솔루션이 있다고 가정하십시오. 올바른 솔루션이 두 개 이상인 경우 올바른 솔루션 중 하나만 반환하면 충분합니다.
가장 짧은 코드가 승리합니다. 새로 제출하지 않고 7 일 또는 24 시간 후에 우승자를 선택합니다.
위의 예제에 대한 솔루션을 포함하고 있지만 코드를 작성한 후에 만 확인하는 것이 좋습니다.
하나:
{위 : 3, 아래 : 1, 왼쪽 : 4, 오른쪽 : 2, 시작 : [0,0], 끝 : [2,5]}
두:
{위 : ‘@’, 아래 : ‘e’, 왼쪽 : ‘.’, 오른쪽 : ‘H’, 시작 : [1,1], 끝 : [0,0]}
세:
{위 : ‘I’, 아래 : ‘V’, 왼쪽 : ‘C’, 오른쪽 : ‘X’, 시작 : [0,2], 끝 : [4,2]}
답변
씨#
편집 : 나누기와 서식을 수정했습니다. 그리고 도우미 클래스를 추가했습니다.
골프 코드 807 자
class M{public int c,x,y,u;}
void G(string[] z){
M K;int[]x={0,0,-1,1},y={-1,1,0,0},I={0,0,0,0};
string[]T={"Up","Down","Left","Right"};
int X,Y,R,n=0,H=z.Length,W=z[0].Length;W-=W/2;var D= string.Join(" ", z).Where(c=>c!=' ').Select(c=>new M(){c=c,x=n%W,y=n++/W}).ToList();n=0;var S=D.GroupBy(k=>k.c).ToDictionary(k=>k.Key,k =>n++);
for(;I[0]<4;I[0]++)for(I[1]=0;I[1]<4;I[1]++)for(I[2]=0;I[2]<4;I[2]++)for(I[3]=0;I[3]<4;I[3]++){
if ((1<<I[0]|1<<I[1]|1<<I[2]|1<<I[3])!=15)continue;
foreach (var Q in D){D.ForEach(p=>p.u=-1);R=1;K=Q;j:if((X=K.x+x[n=I[S[K.c]]])>=0&&X<W&&(Y=K.y+y[n])>=0&&Y<H&&(K=D[X+Y*W]).u<0){
K.u=1;if(++R==D.Count){Console.WriteLine("{4} Start({0}:{1}) End({2}:{3})",Q.x,Q.y,K.x,K.y,string.Join(", ",S.Select(k=>string.Format("{1}: '{0}'",(char)k.Key,T[I[k.Value]])).ToArray()));return;}goto j;}}}
}
세 가지 테스트 사례에 대한 결과 :
아래 : ‘1’, 오른쪽 : ‘2’, 위 : ‘3’, 왼쪽 : ‘4’시작 (0 : 0) 끝 (5 : 2)
위 : ‘@’, 왼쪽 : ‘.’, 아래 :: e ‘, 오른쪽 :’H ‘시작 (1 : 1) 끝 (0 : 0)
오른쪽 :’X ‘, 아래쪽 :’V ‘, 위쪽 :’I ‘, 왼쪽 :’C ‘시작 (0 : 2) 끝 (2 : 4)
이것은 “golf”가없는 원시 코드이며 거의 4,000 자입니다.
class Program
{
static string[] input1 = { "1 2 2 2 2 1",
"1 3 4 4 1 4",
"2 3 1 3 4 2",
"1 4 4 2 1 3",
"2 2 2 3 2 3"};
static string[] input2 = { "@ . .",
"e . @",
"H H @",
};
static string[] input3 = { "0 0 1",
"0 0 1",
"3 2 2",
};
static void Main(string[] args)
{
Resolve(input1);
Resolve(input2);
Resolve(input3);
Console.ReadLine();
}
class N { public int c; public int x, y, i, u; }
static void Resolve(string[] input)
{
int[] ox = { -1, 1, 0, 0 }, oy = { 0, 0, -1, 1 }, I = { 0, 0, 0, 0 };
string[] TXT = { "Left", "Right", "Up", "Down" };
int X, Y, R, n = 0, H = input.Length, W = input[0].Length;
W -= W / 2;
N K = null;
var data = string.Join(" ", input).Where(c => c != ' ').Select(c => new N() { c = c, x = (n % W), y = (n / W), i = n++, u = -1 }).ToList();
n = 0;
var S = data.GroupBy(k => k.c).ToDictionary(k => k.Key, k => n++);
for (; I[0] < 4; I[0]++)
for (I[1] = 0; I[1] < 4; I[1]++)
for (I[2] = 0; I[2] < 4; I[2]++)
for (I[3] = 0; I[3] < 4; I[3]++)
{
if (((1 << I[0]) | (1 << I[1]) | (1 << I[2]) | (1 << I[3])) != 15) continue;
foreach(var Q in data)
{
data.ForEach(p => p.u = -1);
R = 0;
K = Q;
while (K != null)
{
n = I[S[K.c]];
X = K.x + ox[n];
Y = K.y + oy[n];
if (X >= 0 && X < W && Y >= 0 && Y < H)
{
n = X + Y * W;
if (data[n].u < 0)
{
data[n].u = K.i;
K = data[n];
R++;
if (R == data.Count - 1)
{
Console.WriteLine();
Console.WriteLine("Start({0}:{1}) End({2}:{3})", Q.x, Q.y, K.x, K.y);
Console.WriteLine(string.Join(", ", S.Select(k => string.Format("'{0}': {1}", (char)k.Key, TXT[I[k.Value]])).ToArray()));
Action<N> Write = null;
Write = (k) =>
{
if (k.u != -1)
{
Write(data[k.u]);
}
Console.Write(string.Format("({0}:{1}){2}", k.x, k.y, k == K ? "\n" : " => "));
};
Write(K);
return;
}
continue;
}
}
K = null;
}
}
}
Console.WriteLine("Solution not found");
}
}
}
다음은 세 가지 예에 대한 결과입니다.
해결책을 찾을 수 없습니다
시작 (1 : 1) 끝 (0 : 0) ‘@’: 위, ‘.’: 왼쪽, ‘e’: 아래, ‘H’: 오른쪽
(1 : 1) => (0 : 1) => (0 : 2) => (1 : 2) => (2 : 2) => (2 : 1) => (2 : 0) => ( 1 : 0) => (0 : 0)
시작 (0 : 0) 끝 (1 : 1) ‘0’: 오른쪽, ‘1’: 아래로, ‘3’: 위로, ‘2’: 왼쪽
(0 : 0) => (1 : 0) => (2 : 0) => (2 : 1) => (2 : 2) => (1 : 2) => (0 : 2) => ( 0 : 1) => (1 : 1)
답변
매스 매 티카 278
“명확성”을 위해 추가 된 공간
k@l_ := (s = #~Join~-# &@{{1, 0}, {0, 1}};
f@r_ := Flatten[MapIndexed[#2 -> #2 + (#1 /. r) &, l, {2}], 1];
g = Subgraph[#, t = Tuples@Range@Dimensions@l] & /@
Graph /@ f /@ (r = Thread[# -> s] & /@ Permutations[Union @@ l]);
{t[[#]] & /@ Ordering[Tr /@ IncidenceMatrix@g[[#]]][[{1, -1}]], r[[#]]} & @@@
Position[PathGraphQ /@ g, True])
세션 및 출력 :
l = l1 = {{1, 2, 2, 2, 2, 1}, {1, 3, 1, 4, 1, 4}, {2, 3, 1, 3, 4, 2},
{1, 4, 4, 2, 1, 3}, {2, 2, 2, 3, 2, 3}}; ;
k@l1
{{{{1, 1}, {3, 6}},
{1 -> {1, 0}, 2 -> {0, 1}, 3 -> {-1, 0}, 4 -> {0, -1}}}}
시작 정점, 끝 정점 및 각 심볼과 관련된 전환 규칙입니다.
다음은 방향 그래프를 표시하는 보완 코드입니다.
sol = sg[[Position[PathGraphQ /@ sg, True][[1, 1]]]];
Framed@Graph[
VertexList@sol,
EdgeList@sol,
VertexCoordinates -> VertexList@sol /. {x_, y_} :> {y, -x},
VertexLabels -> MapThread[Rule, {VertexList@sol, Flatten@l}],
EdgeShapeFunction -> GraphElementData["FilledArcArrow", "ArrowSize" -> 0.03],
ImagePadding -> 20]
답변
매스 매 티카 (151)
L = {{1, 2, 2, 2, 2, 1}, {1, 3, 1, 4, 1, 4}, {2, 3, 1, 3, 4, 2},
{1, 4, 4, 2, 1, 3}, {2, 2, 2, 3, 2, 3}};
PathGraphQ@#~If~Print@{TopologicalSort[#]〚{1,-2}〛,r}&@
Graph@Flatten@MapIndexed[#2->#2+(#/.r)&,L,{2}]~Do~{r,
Thread[Union@@L->#]&/@{-1,0,1}~Tuples~{4,2}}
시작점, 끝점 및 전환 규칙을 반환합니다. 첫 번째 인덱스는 행이고 두 번째 인덱스는 열입니다
{{{1,1},{3,6}},{1->{1,0},2->{0,1},3->{-1,0},4->{0,-1}}}
내 코드는 와도 작동합니다 {-1,0,1}~Tuples~{4,2}. 속도를 높이기 위해 Permutations@{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}대신 사용할 수 있습니다 .
답변
APL (207)
나는 TopologicalSort와 같은 측면에서 추론 할 수 없기 때문에 Mathematica보다 짧게 만들 수 없었습니다. 더 똑똑한 사람들은 그것을 더 짜낼 수 있습니다.
골프 :
{u←∪,t←⍵⋄q r←↑(0≠+/¨r)/⊂[2]p,⍪r←{m←,⍵[u⍳t]⋄v r←⊂[1]⊃{{(↑⍴∪⍵),⊂(↑⍵)(↑⌽⍵)}n↑{3::⍬⋄i←↑⌽⍵⋄⍵,i+i⌷m}⍣n,⍵}¨⍳n←↑⍴,t⋄↑(v=n)/r}¨p←⊂[2]{1≥⍴⍵:⊃,↓⍵⋄⊃⍪/⍵,∘∇¨⍵∘~¨⍵}d←¯1 1,¯1 1×c←¯1↑⍴t⋄⊃('←→↑↓',¨u[q⍳d]),{1+(⌊⍵÷c)(c|⍵)}¨r-1}
언 골프 드 :
D←{⎕ML ⎕IO←3 1
pmat←{1≥⍴⍵:⊃,↓⍵⋄⊃⍪/⍵,∘∇¨⍵∘~¨⍵} ⍝ utility: permutations of the given vector
u←∪,t←⍵ ⍝ the 4 unique symbols in t←⍵
n←↑⍴,t ⍝ number of elements in t
d←¯1 1,¯1 1×c←¯1↑⍴t ⍝ the four ∆i (+1, -1, +cols, -cols)
p←⊂[2]pmat d ⍝ list of permutations of the four ∆i
r←{ ⍝ for each permutation ⍵∊p (=interpretation of the 4 symbols)
m←,⍵[u⍳t] ⍝ (ravelled) t-shaped matrix of ∆i, using interpretation ⍵
v r←⊂[1]⊃{ ⍝ for each starting index ⍵∊⍳n
v←n↑{ ⍝ trail of visited cells after n steps
3::⍬ ⍝ if index out of bounds return empty list
i←↑⌽⍵ ⍝ take last visited index
⍵,i+i⌷m ⍝ follow the directions and add it to the list
}⍣n,⍵
(↑⍴∪v),⊂(↑v),↑⌽v ⍝ number of unique cells, plus start/end indices
}¨⍳n
↑(v=n)/r ⍝ 1st couple of start/end indices to visit all cells (if any)
}¨p
q r←↑(0≠+/¨r)/⊂[2]p,⍪r ⍝ select first perm. and start/end indices to visit all cells
⊃('←→↑↓',¨u[q⍳d]),{1+(⌊⍵÷c)(c|⍵)}¨r-1 ⍝ return char mapping and start/end indices
}
예 :
(지수는 1에서 시작)
D⊃'122221' '131414' '231342' '144213' '222323'
← 4
→ 2
↑ 3
↓ 1
1 1
3 6
D⊃'@..' 'e.@' 'HH@'
← .
→ H
↑ @
↓ e
2 2
1 1
D⊃'XXV' 'ICV' 'XIV' 'VCC' 'XXX'
← C
→ X
↑ I
↓ V
3 1
5 3