Diberikan daftar koordinat 2d (x, y), tentukan berapa banyak kuadrat satuan (panjang tepi 1 unit) yang dapat dibentuk menggunakan koordinat.
- Input akan berupa larik 0 atau lebih pasangan koordinat:
misalnya dalam JavaScript:numofsq([[0,0], [1,0], [1,1], [0,1]])
- Tidak ada koordinat duplikat dalam input
- Urutan input akan acak (koordinat 2d acak).
- Bentuk koordinat: [koordinat x, koordinat y] (duh)
- Urutan koordinat: [0,0], [1,0], [1,1], [0,1] dan [0,0], [0,1], [1,1], [1,0 ] menunjukkan satuan satuan yang sama (dihitung sekali saja)
- Koordinat dapat berupa bilangan bulat negatif atau positif (duh)
- Fungsi hanya akan mengembalikan jumlah kuadrat unit yang mungkin, 0 atau lebih.
Kasus uji:
Input Coordinates Pairs Expected Output
[0,0], [0,1], [1,1], [1,0], [0,2], [1,2] 2
[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1] 3
[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1], [2,0] 4
[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1], [2,0], [9,9] 4
Peringatan Spoiler: Hal-hal solusi di sini-seterusnya [JS]
Pendekatan non-Golf, cepat dan kotor, brute-force (termasuk untuk memberikan beberapa arahan).
//cartesian distance function
function dist(a, b) {
if (b === undefined) {
b = [0, 0];
}
return Math.sqrt((b[0] - a[0]) * (b[0] - a[0]) + (b[1] - a[1]) * (b[1] - a[1]));
}
//accepts 4 coordinate pairs and checks if they form a unit square
//this could be optimized by matching x,y coordinates of the 4 coordinates
function isUnitSquare(a) {
var r = a.slice(),
d = [],
c = [],
i,
j = 0,
counter = 0;
for (i = 1; i < 4; i++) {
if (dist(a[0], a[i]) === 1) {
d.push(a[i]);
r[i] = undefined;
counter++;
}
}
r[0] = undefined;
c = d.concat(r.filter(function(a) {return undefined !== a}));
if (dist(c[0], c[1]) === 1) {j++};
if (dist(c[1], c[2]) === 1) {j++};
if (dist(c[2], c[0]) === 1) {j++};
return counter === 2 && j === 2;
}
//a powerset function (from rosetta code)
//however, we will need only "sets of 4 coordinates"
//and not all possible length combinations (sets of 3 coords or
//sets of 5 coords not required). Also, order doesn't matter.
function powerset(ary) {
var ps = [[]];
for (var i=0; i < ary.length; i++) {
for (var j = 0, len = ps.length; j < len; j++) {
ps.push(ps[j].concat(ary[i]));
}
}
return ps;
}
//so to capture only sets of 4 coordinates, we do
var res = powerset([[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1], [2,0]])
.filter(function (a) {return a.length === 8;});
//and a little bit of hoopla to have a nice set of sets of 4 coordinates.
//(Dizzy yet? Wait for the generalized, 3D, cube of any edge length version ;))
var squareQuads = res.map(function(ary) {
return ary.join().match(/\d\,\d/g)
.map(function(e) {
return [+e.split(',')[0], +e.split(',')[1]];
});
});
//Finally, the last bit
var howManyUnitSquares = 0;
squareQuads.map(function(quad) {
if (isUnitSquare(quad)) {
howManyUnitSquares++;
}
});
console.log(howManyUnitSquares);
//Cleaning up and putting those in-line stuff into a function
function howManySquares(r) { //r = [[x,y], [x,y], [x,y], [x,y], ......];
var res = powerset(r)
.filter(function (a) {return a.length === 8;});
var squareQuads = res.map(function(ary) {
return ary.join().match(/\d\,\d/g)
.map(function(e) {
return [+e.split(',')[0], +e.split(',')[1]];
});
});
var answer = 0;
squareQuads.map(function(quad) {
if (isUnitSquare(quad)) {
answer++;
}
});
return answer;
}
[-1,0],[0,-1],[1,0],[0,1]
kotak?[-2,0],[0,-2],[2,0],[0,2]
memiliki panjang tepi2
. Kotak?Jawaban:
APL (Dyalog), 30
Nah, dalam banyak kasus, keterbacaan dan jumlah char proporsional.
Output Sampel
Penjelasan
Jadi, 4 poin membentuk satuan kuadrat jika dan hanya jika posisi relatifnya adalah (1,1), (1,2), (2,1), (2,2)
{(2-/⍵)≡2-/,⍳2 2}
adalah fungsi yang mengembalikan 1 atau 0 (true / false) diberikan satu set 4 poin sebagai input berdasarkan pada apakah mereka berada dalam posisi relatif dan diurutkan dalam urutan (1,1), (1,2), (2,1), (2,2):⍳2 2
Menghasilkan 2 × 2 matriks poin (1,1), (1,2), (2,1), (2,2),
Mengurai matriks ke array poin2-/
Pengurangan pasangan bijaksana mengurangi: (1,1) - ( 1,2); (1,2) - (2,1); (2,1) - (2,2), yang memberikan array [(0, -1), (- 1,1), (0, -1)](2-/⍵)
Pengurangan pair-wise mengurangi input.≡
Periksa apakah keduanya array samaProgram utama
⎕
Mengambil input dan mengevaluasinya. Hal-hal seperti(0 0)(0 1)(1 0)(1 1)
mengevaluasi ke array bersarang (Setara[[0,0],[0,1],[1,0],[1,1]]
dalam JS)⊂¨
Untuk setiap titik (¨
), lampirkan dalam skalar (⊂
) ([[[0,0]],[[0,1]],[[1,0]],[[1,1]]]
)∘.,⍨⍣2
Untuk setiap pasangan elemen array, gabungkan mereka untuk membentuk array baru. ([ [[0,0],[0,0]],[[0,0],[0,1]]...
) Ulangi sekali. Ini memberikan semua set 4 poin yang dapat dibuat menggunakan poin yang diberikan. Dalam beberapa set ini, titik yang sama akan digunakan beberapa kali, tetapi ini tidak akan menjadi satuan kotak sehingga tidak perlu membuang penekanan tombol untuk menghapusnya. (,
menyatukan 2 array,∘.
berarti "melakukan itu untuk setiap pasangan elemen",⍨
berarti "menggunakan operan kanan sebagai operan kiri dan kanan", dan⍣2
berarti "lakukan ini dua kali"),
Karena operasi sebelumnya akan memberikan array 4 dimensi (perhatikan bahwa array bersarang dan array multi dimensi adalah hal yang berbeda dalam APL), kita harus menguraikannya untuk mendapatkan array set (dari 4 poin).¨
Untuk masing-masing set,{...}
jalankan fungsi yang disebutkan di atas. Hasilnya akan menjadi array 0s dan 1s yang menunjukkan apakah set adalah satuan persegi. Perhatikan bahwa karena fungsi ini juga memeriksa pemesanan, duplikat dihilangkan.+/
Akhirnya, jumlah array yang dihasilkan untuk mendapatkan hitungan.sumber
Mathematica 65 karakter
Tes
Penjelasan
Menghasilkan semua himpunan bagian dari 4 poin dan memeriksa semua jarak antar-titik. Jarak antar-titik yang diurutkan untuk unit square adalah: `{1, 1, 1, 1, √2, √2}.
Length
kemudian menghitung jumlah kuadrat unit.sumber
g
?f=Count[#-#[[1]]&/@(Sort/@#~Subsets~{4}.{1,I}),{0,I,1,1+I}]&
Ruby,
164161153147 karakterIni sebenarnya sangat mudah dibaca, kecuali untuk bagian yang menguji apakah itu satuan persegi atau tidak.
Mungkin banyak perbaikan yang mungkin dilakukan, berusaha menemukannya sekarang.
Sampel (semuanya bekerja):
Saya mungkin dapat menemukan trik
transpose
, tetapi saya sudah mencoba untuk sementara waktu dan saya tidak bisa. Inilah fungsinya:sumber
Python, 61 karakter
Sampel:
sumber
Mathematica, 56 karakter
sumber