Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- In order to fulfill the requirement of no duplicates you need to check whether the modulo of both dimensions of your 2d vector with the smallest value down to 2 is 0.
- Example:
- (3,2) is the first vector on the straight line with slope 2/3.
- For example for the vector (6,4) you pick the dimension with the smallest value (4).
- You can simply calculate min x y.
- This yields ```((6 % 4) == 0) && ((4 % 4) == 0) = False```
- Repeat down to 2
- ```((6 % 3) == 0) && ((4 % 3) == 0) = False
- ((6 % 2) == 0) && ((4 % 2) == 0) = True```
- Lets call the value which we modulo'd with and got a `True`
- **d = 2**
- Ok we found **something**. But what does it mean?
- If we divide both dimensions by **d** which we just determined we get (6/2, 4/2) = (3,2)
- and
- *OH LAWD* this is the smallest vector you can have with whole numbers that lies on the line with slope 2/3.
- So the conclusion is: If you find a number d from (min x y) downto 2 where (x % d == 0) && (y % d == 0) then you've seen the vector already.
- There are a few exceptions for example logically modulo 1 needs to be caught since it's always 0.
- The other exception is that you don't count vectors where (x=y). It's trivial to see that (x,y) is a duplicate of (nx, ny) where n is a whole number <0.
- So you can just add 1 at the end.
- This *should* work, I hope I didn't miss anything.
- I'm sure there's some mathematical formula that does that without iteration/recursion, I'm just not good enough at determining which formula that might be.
- I've implemented this in haskell to test it and it seems to work.
- ```Haskell
- uniqueVec :: Integer -> [(Integer, Integer, Bool)]
- uniqueVec limit = map (isUnique 0) candidates
- where
- candidates = [(x,y) | x <- [1..limit], y <- [1..limit], x /= y, y <= x]
- isUnique :: Integer -> (Integer, Integer) -> (Integer, Integer, Bool)
- isUnique 0 (x,y) = isUnique (min x y) (x,y)
- isUnique 1 (x,y) = (x,y,True)
- isUnique current (x,y) = if (x > 1 && y > 1) && (mod x current == 0 && mod y current == 0)
- then (x,y,False)
- else isUnique (current - 1) (x,y)
- countVec :: Integer -> Int
- countVec limit = (+ 1) $ length $ foldr (\(x,y,z) xs -> if z then ((x,y):xs) else xs) [] $ uniqueVec limit
- ```
- GHCI output:
- ```*Main> uniqueVec 6
- [(2,1,True),(3,1,True),(3,2,True),(4,1,True),(4,2,False),(4,3,True),(5,1,True),(5,2,True),(5,3,True),(5,4,True),(6,1,True),(6,2,False),(6,3,False),(6,4,False),(6,5,True)]```
- And now we count the vectors that are marked as unique with `True` and add 1:
- ```*Main> countVec 6
- 12```
- which is the same as in the image
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement