8
\$\begingroup\$

Given a list of 2d (x, y) coordinates, determine how many unit squares (edge length 1 unit) can be formed using the coordinates.

  • Input will be an array of 0 or more pairs of coordinates:
    e.g. in JavaScript: numofsq([[0,0], [1,0], [1,1], [0,1]])
  • No duplicate coordinates in input
  • Input order will be random (random 2d coordinates).
  • Coordinate form: [x-coordinate, y-coordinate] (duh)
  • Order of coordinates: [0,0], [1,0], [1,1], [0,1] and [0,0], [0,1], [1,1], [1,0] denote the same unit square (to be counted just once)
  • Coordinates can be negative or positive integers (duh)
  • Function will return just the number of unit squares possible, 0 or more.

Test cases:

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

Spoiler Alert: Solution stuff here-onwards [JS]

Non-Golfed, quick and dirty, brute-force approach (included to provide some directions).

//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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ is [-1,0],[0,-1],[1,0],[0,1] a square? \$\endgroup\$ – Johannes Kuhn Oct 18 '13 at 20:05
  • \$\begingroup\$ @JohannesKuhn No, their edge lengths are not unity, but sqrt(2), so they are not unit squares. \$\endgroup\$ – user9323 Oct 18 '13 at 20:13
  • \$\begingroup\$ But [-2,0],[0,-2],[2,0],[0,2] has a edge length of 2. Square? \$\endgroup\$ – Johannes Kuhn Oct 22 '13 at 9:24
  • 2
    \$\begingroup\$ @JohannesKuhn Square? Yes. UNIT Square? No. \$\endgroup\$ – user9323 Oct 23 '13 at 8:12
5
\$\begingroup\$

APL(Dyalog), 30

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

Well, in most cases, readability and char count is proportional.


Sample Output

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

Explaination

So, 4 points forms a unit square if and only if their relative positions are (1,1),(1,2),(2,1),(2,2)
{(2-/⍵)≡2-/,⍳2 2} is a function that return 1 or 0 (true/false) given a set of 4 points as input based on whether they are in relative positions and sorted in the order (1,1),(1,2),(2,1),(2,2):
⍳2 2 Generate a 2×2 matrix of the points (1,1),(1,2),(2,1),(2,2)
, Unravel that matrix to an array of points
2-/ Pair-wise subtraction reduce: (1,1) - (1,2) ; (1,2) - (2,1) ; (2,1) - (2,2), which gives the array [(0,-1),(-1,1),(0,-1)]
(2-/⍵) Pair-wise subtraction reduce on the input
Check if the two arrays equal

The main program
Takes input and evals it. Things like (0 0)(0 1)(1 0)(1 1) evaluates to a nested array (Equivalent of [[0,0],[0,1],[1,0],[1,1]] in JS)
⊂¨ For every point (¨), enclose it in a scalar () ([[[0,0]],[[0,1]],[[1,0]],[[1,1]]])
∘.,⍨⍣2 For every pair of elements of the array, concatenate them to form a new array. ([ [[0,0],[0,0]],[[0,0],[0,1]]...) Repeat once. This gives all sets of 4 points that can be made using the given points. In some of these sets, the same point would be used multiple times, but these would not be unit squares so no need to waste keystrokes to remove them. (, concatenates 2 arrays, ∘. means "do that for every pair of elements", means "use right operand as both left and right operands", and ⍣2 means "do this twice")
, As the previous operation would give a 4-dimensional array (note that nested arrays and multi-dimensional arrays are different things in APL), we have to unravel it to get an array of sets (of 4 points).
¨ For each of the sets,
{...} execute the aforementioned function. The result would be an array of 0s and 1s indicating whether the set is a unit square. Note that because the function also check ordering, duplicates are eliminated.
+/ Finally, sum resulting array to get the count.

\$\endgroup\$
3
\$\begingroup\$

Mathematica 65 chars

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

Tests

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

Explanation

Generates all subsets of 4 points and checks all the inter-point distances. The sorted inter-point distances for a unit square are: `{1, 1, 1, 1, √2, √2}.

Length then counts the number of unit squares.

\$\endgroup\$
  • \$\begingroup\$ What is the definition of g? \$\endgroup\$ – alephalpha Oct 19 '13 at 4:23
  • 1
    \$\begingroup\$ Here is my shorter solution: f=Count[#-#[[1]]&/@(Sort/@#~Subsets~{4}.{1,I}),{0,I,1,1+I}]& \$\endgroup\$ – alephalpha Oct 19 '13 at 4:54
1
\$\begingroup\$

Ruby, 164 161 153 147 characters

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

It's actually very readable, except for the part that tests whether it's a unit square or not.

Probably many improvements possible, attempting to find them now.

Samples (all of them work):

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

I may be able to find a trick with transpose, but I've been trying for a while and I can't. Here's what it does:

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]]
\$\endgroup\$
  • \$\begingroup\$ Agree with the readable part - As someone who has never programmed in Ruby, I can still clearly understand the steps. Too bad JS doesn't have some combinatorics built in. \$\endgroup\$ – user9323 Oct 18 '13 at 21:21
0
\$\begingroup\$

Python, 61 chars

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

Sample:

>>> 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
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 56 characters

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy