Golf: Berapa banyak kotak panjang unit dalam daftar koordinat 2d?

8

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;
}

sumber
1
itu [-1,0],[0,-1],[1,0],[0,1]kotak?
Johannes Kuhn
@JohannesKuhn Tidak, panjang tepi mereka bukan kesatuan, tetapi sqrt (2), jadi mereka bukan kotak satuan.
Tetapi [-2,0],[0,-2],[2,0],[0,2]memiliki panjang tepi 2. Kotak?
Johannes Kuhn
2
@JohannesKuhn Square? Iya. Alun-Alun UNIT ? Tidak.

Jawaban:

5

APL (Dyalog), 30

+/{(2-/⍵)≡2-/,⍳2 2}¨,∘.,⍨⍣2⊂¨⎕

Nah, dalam banyak kasus, keterbacaan dan jumlah char proporsional.


Output Sampel

⎕:
      (0 0)(0 1)(1 0)(1 1)(0 2)(1 2)(2 2)(2 1)(2 0)
4

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 2Menghasilkan 2 × 2 matriks poin (1,1), (1,2), (2,1), (2,2)
,Mengurai matriks ke array poin
2-/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 sama

Program 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]]])
∘.,⍨⍣2Untuk 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 ⍣2berarti "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.

TwiNight
sumber
3

Mathematica 65 karakter

f@d_ := Length@Select[Subsets[d, {4}], Sort[g@#] == {1, 1, 1, 1, √2, √2} &]

Tes

f[{{0, 0}, {0, 1}, {1, 1}, {1, 0}, {0, 2}, {1, 2}}]

2

f[{{0, 0}, {0, 1}, {1, 1}, {1, 0}, {0, 2}, {1, 2}, {2, 2}, {2, 1}}]

3

f[{{0, 0}, {0, 1}, {1, 1}, {1, 0}, {0, 2}, {1, 2}, {2, 2}, {2, 1}, {2,0}}]

4

f[{{0, 0}, {0, 1}, {1, 1}, {1, 0}, {0, 2}, {1, 2}, {2, 2}, {2, 1}, {2,0}, {9, 9}}]

4

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.

DavidC
sumber
Apa definisi dari g?
alephalpha
1
Ini solusi saya yang lebih singkat:f=Count[#-#[[1]]&/@(Sort/@#~Subsets~{4}.{1,I}),{0,I,1,1+I}]&
alephalpha
1

Ruby, 164 161 153 147 karakter

f=->a{a.combination(4).map(&:sort).uniq.count{|x|[x[1][0]==l=x[0][0],x[3][0]==m=x[2][0],x[2][1]==n=x[0][1],x[3][1]==o=x[1][1],m-l==1,o-n==1].all?}}

Ini 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):

puts f[[[0,0], [0,1], [1,1], [1,0], [0,2], [1,2]]]                             #--> 2
puts f[[[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1]]]               #--> 3
puts f[[[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1], [2,0]]]        #--> 4
puts f[[[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1], [2,0], [9,9]]] #--> 4

Saya mungkin dapat menemukan trik transpose, tetapi saya sudah mencoba untuk sementara waktu dan saya tidak bisa. Inilah fungsinya:

irb(main):001:0> a = [[5, 10], [5, 11], [6, 10], [6, 11]]
=> [[5, 10], [5, 11], [6, 10], [6, 11]]
irb(main):002:0> a.transpose
=> [[5, 5, 6, 6], [10, 11, 10, 11]]
Gagang pintu
sumber
Setuju dengan bagian yang dapat dibaca - Sebagai seseorang yang belum pernah memprogram di Ruby, saya masih dapat memahami langkah-langkahnya. Sayang sekali JS tidak memiliki beberapa kombinatorik.
0

Python, 61 karakter

f=lambda l:sum(1for x,y in l if{(x+1,y),(x,y+1),(x+1,y+1)}<l)

Sampel:

>>> f({(0,0), (0,1), (1,1), (1,0), (0,2), (1,2)})
2
>>> f({(0,0), (0,1), (1,1), (1,0), (0,2), (1,2), (2,2), (2,1)})
3
>>> f({(0,0), (0,1), (1,1), (1,0), (0,2), (1,2), (2,2), (2,1), (2,0)})
4
>>> f({(0,0), (0,1), (1,1), (1,0), (0,2), (1,2), (2,2), (2,1), (2,0), (9,9)})
4
Daniel Lubarov
sumber
0

Mathematica, 56 karakter

f=Count[#-#[[1]]&/@Subsets[{}⋃#.{1,I},{4}],{0,I,1,1+I}]&
alephalpha
sumber