ソニーからの挑戦状をPythonで解いてみた

Sony Japan | 採用情報｜新卒採用｜GO FOR IT～情熱と技術が世界を変える～

の真似をして、Pythonで書こうと思います。

以下で作るCubeクラスの仕様はPyQt4/PySideのQtCore.QRectと同様にしたかったのですが、QtCore.QRectは

>>> QtCore.QPoint(0, 0) in QtCore.QRect(0, 0, 5, 5)
True
>>> QtCore.QPoint(5, 5) in QtCore.QRect(0, 0, 5, 5)
False

というように、数学の言葉で言えば、ではなく、になっています。

しかし、Sonyの問題の場合はとするべきだと思うので、そういう仕様に変更しています。

また、２つの立方体が頂点や辺のみで接している場合は「重なっている」と判定することとしています。

#!python3
#encoding:mbcs
from itertools import product
from collections import namedtuple

Point3d = namedtuple("Point3", "x y z")
Size3d = namedtuple("Size3d", "x y z")

class Cube:
    __slots__ = "_point _size _normalized".split()
    def __init__(self, point, size):
        self._point = point
        self._size = size
        self._normalized = None
    
    @property
    def point(self):
        return self._point
    
    @property
    def size(self):
        return self._size
    
    def all_vertexes(self):
        axises = []
        for x, s in zip(self._point, self._size):
            axises.append([x, x + s])
        
        for x, y, z in product(*axises):
            yield Point3d(x, y, z)
    
    def is_normal(self):
        return all(s >= 0 for s in self._size)
    
    def normalized(self):
        if self._normalized is not None:
            return self._normalized
        if self.is_normal():
            self._normalized = self
            return self
        
        point = []
        size = []
        for x, length in zip(self._point, self._size):
            if length < 0:
                x += length + 1
                length = -length
            point.append(x)
            size.append(length)
        self._normalized = Cube(Point3d(*point), Size3d(*size))
        return self._normalized
    
    def __contains__(self, p):
        #辺の長さがマイナスだと扱いづらいので、正規化
        n = self.normalized()
        return all(x <= px <= x + length
            for px, x, length in zip(p, n._point, n._size))
    
    def overwraps(self, cube):
        return any(p in self for p in cube.all_vertexes())
    
    def __repr__(self):
        return "{}({}, {})".format(
            self.__class__.__name__, self._point, self._size)
    
    def __eq__(self, cube):
        n0 = self.normalized()
        n1 = cube.normalized()
        return n0._point == n1._point and n0._size == n1._size


import unittest
class TestCube(unittest.TestCase):
    def test_normalized(self):
        cube = Cube(Point3d(1, 1, 1), Size3d(4, 5, 6))
        self.assertTrue(cube.is_normal())
        self.assertEqual(cube.point, Point3d(1, 1, 1))
        self.assertEqual(cube.size, Size3d(4, 5, 6))
        
        #辺の長さがマイナスの場合
        cube = Cube(Point3d(4, 5, 6), Size3d(-4, -5, -6))
        self.assertFalse(cube.is_normal())
        #normalize(辺の長さをプラスになるように修正)が正しく行えているか？
        cube = cube.normalized()
        self.assertTrue(cube.is_normal())
        self.assertEqual(cube.point, Point3d(1, 1, 1))
        self.assertEqual(cube.size, Size3d(4, 5, 6))
        
        self.assertEqual(Cube(Point3d(1, 1, 1), Size3d(4, 5, 6)),
                         Cube(Point3d(4, 5, 6), Size3d(-4, -5, -6)))
        
        cube = Cube(Point3d(1, 1, 1), Size3d(0, 0, 0))
        self.assertTrue(cube.is_normal())
    
    def test_contains(self):
        #辺の長さがプラスの場合
        cube = Cube(Point3d(1, 1, 1), Size3d(4, 5, 6))
        self.assertIn(Point3d(1, 1, 1), cube)
        self.assertIn(Point3d(4, 1, 1), cube)
        self.assertNotIn(Point3d(0, 1, 1), cube)
        self.assertNotIn(Point3d(6, 1, 1), cube)
        
        #辺の長さがマイナスの場合
        cube = Cube(Point3d(4, 5, 6), Size3d(-4, -5, -6))
        self.assertIn(Point3d(1, 1, 1), cube)
        self.assertIn(Point3d(4, 1, 1), cube)
        self.assertNotIn(Point3d(0, 1, 1), cube)
        self.assertNotIn(Point3d(6, 1, 1), cube)
        
        cube = Cube(Point3d(1, 1, 1), Size3d(0, 0, 0))
        self.assertIn(Point3d(1, 1, 1), cube)
    
    def test_overwraps(self):
        cube1 = Cube(Point3d(0, 0, 0), Size3d(10, 10, 10))
        cube2 = Cube(Point3d(5, 5, 5), Size3d(10, 10, 10))
        cube3 = Cube(Point3d(15, 15, 15), Size3d(10, 10, 10))
        cube4 = Cube(Point3d(1, 1, 1), Size3d(0, 0, 0))
        self.assertTrue(cube1.overwraps(cube2))  #接している
        self.assertFalse(cube1.overwraps(cube3)) #接していない
        self.assertTrue(cube3.overwraps(cube2))  #頂点のみで接している
        self.assertTrue(cube1.overwraps(cube4))  #内部にある
        
        
def main():
    unittest.main()
    

if __name__ == "__main__":
    main()