Advertisement
Spiritreader

Untitled

Dec 11th, 2019
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.61 KB | None | 0 0
  1. 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.
  2.  
  3. Example:
  4. (3,2) is the first vector on the straight line with slope 2/3.
  5.  
  6. For example for the vector (6,4) you pick the dimension with the smallest value (4).
  7. You can simply calculate min x y.
  8.  
  9. This yields ```((6 % 4) == 0) && ((4 % 4) == 0) = False```
  10. Repeat down to 2
  11. ```((6 % 3) == 0) && ((4 % 3) == 0) = False
  12. ((6 % 2) == 0) && ((4 % 2) == 0) = True```
  13. Lets call the value which we modulo'd with and got a `True`
  14. **d = 2**
  15.  
  16. Ok we found **something**. But what does it mean?
  17. If we divide both dimensions by **d** which we just determined we get (6/2, 4/2) = (3,2)
  18. and
  19. *OH LAWD* this is the smallest vector you can have with whole numbers that lies on the line with slope 2/3.
  20.  
  21. 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.
  22.  
  23. There are a few exceptions for example logically modulo 1 needs to be caught since it's always 0.
  24. 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.
  25. So you can just add 1 at the end.
  26.  
  27. This *should* work, I hope I didn't miss anything.
  28. 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.
  29.  
  30. I've implemented this in haskell to test it and it seems to work.
  31. ```Haskell
  32. uniqueVec :: Integer -> [(Integer, Integer, Bool)]
  33. uniqueVec limit = map (isUnique 0) candidates
  34. where
  35. candidates = [(x,y) | x <- [1..limit], y <- [1..limit], x /= y, y <= x]
  36. isUnique :: Integer -> (Integer, Integer) -> (Integer, Integer, Bool)
  37. isUnique 0 (x,y) = isUnique (min x y) (x,y)
  38. isUnique 1 (x,y) = (x,y,True)
  39. isUnique current (x,y) = if (x > 1 && y > 1) && (mod x current == 0 && mod y current == 0)
  40. then (x,y,False)
  41. else isUnique (current - 1) (x,y)
  42.  
  43. countVec :: Integer -> Int
  44. countVec limit = (+ 1) $ length $ foldr (\(x,y,z) xs -> if z then ((x,y):xs) else xs) [] $ uniqueVec limit
  45. ```
  46. GHCI output:
  47. ```*Main> uniqueVec 6
  48. [(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)]```
  49. And now we count the vectors that are marked as unique with `True` and add 1:
  50. ```*Main> countVec 6
  51. 12```
  52. which is the same as in the image
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement