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
|
Task 1: "Pack a Spiral
Submitted by: Stuart Little
You are given an array @A of items (integers say, but they can be anything).
Your task is to pack that array into an MxN matrix spirally
counterclockwise, as tightly as possible.
'Tightly' means the absolute value |M-N| of the difference has to be as
small as possible.
Example 1:
Input: @A = (1,2,3,4)
Output:
4 3
1 2
Since the given array is already a 1x4 matrix on its own, but that's
not as tight as possible. Instead, you'd spiral it counterclockwise into
4 3
1 2
Example 2:
Input: @A = (1..6)
Output:
6 5 4
1 2 3
or
5 4
6 3
1 2
Either will do as an answer, because they're equally tight.
Example 3:
Input: @A = (1..12)
Output:
9 8 7 6
10 11 12 5
1 2 3 4
or
8 7 6
9 12 5
10 11 4
1 2 3
"
My notes: ok, interesting question. First, need to find "tightest" MxN
where abs(M-N) is minimum, easy. Second, need to build MxN array via
a "counterclockwise spiral starting at bottom corner". Not trivial, but
should be relatively easy. Hmmm.. actually, I can't see a particularly
quick and easy way, I'm sure I'm missing something.
Task 2: "Origin-containing Triangle
Submitted by: Stuart Little
You are given three points in the plane, as a list of six co-ordinates:
A=(x1,y1), B=(x2,y2) and C=(x3,y3).
Write a script to find out if the triangle formed by the given three
co-ordinates contain origin (0,0).
Print 1 if found otherwise 0.
Example 1:
Input: A=(0,1), B=(1,0) and C=(2,2)
Output: 0 because that triangle does not contain (0,0).
Example 2:
Input: A=(1,1), B=(-1,1) and C=(0,-3)
Output: 1 because that triangle contains (0,0) in its interior.
Example 3:
Input: A=(0,1), B=(2,0) and C=(-6,0)
Output: 1 because (0,0) is on the edge connecting B and C.
"
My notes: oh, God. Geometry. I hate geometry. Intuitively I've no
idea how to do this, so need to Google for solutions. Many different
ways, vectors, cross products, etc. Easiest to understand is from
www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/
and it seems to work (even it compares areas with "=="). Hmm, this seems
easier than Task 1!
|
