fork download
copy 
  1. #!/usr/bin/env stack
  2. -- stack --resolver=lts-8.2 --install-ghc runghc
  3.  
  4. {-
  5. Ricochet
  6. ========
  7.  
  8. - https://r...content-available-to-author-only...d.it/5vb1wf
  9.  
  10. My journey to finding the formulas is commented beneath the code.
  11. -}
  12.  
  13. module Main
  14.     ( Corner(..)
  15.     , ricochet
  16.     , main
  17.     ) where
  18.  
  19. data Corner = UL | UR | LR | LL deriving (Show, Eq)
  20.  
  21. ricochet :: (Integral a, Fractional b) => a -> a -> a -> a -> b -> (Corner, a, b)
  22. ricochet h w m n v
  23.     = (c,b,fromIntegral d / v)
  24.  
  25.     where
  26.     h' = h - m
  27.     w' = w - n
  28.     d  = lcm w' h'
  29.  
  30.     b  = d `div` h' + d `div` w' - 2
  31.     c  =
  32.         case (
  33.             ((d `div` h' - 1) `mod` 2),
  34.             ((d `div` w' - 1) `mod` 2)
  35.         ) of
  36.             (0,0) -> LR
  37.             (0,1) -> LL
  38.             (1,0) -> UR
  39.             (1,1) -> UL
  40.  
  41. main :: IO ()
  42. main = interact ( unlines
  43.                 . map (output . input . words)
  44.                 . lines
  45.                 )
  46.  
  47.     where
  48.     -- How to make these less fragile and more idiomatic?
  49.     input (h:w:m:n:v:[]) = ricochet (read h) (read w) (read m) (read n) (read v)
  50.     output (c,b,t) = show c ++ " " ++ show b ++ " " ++ show t
  51.  
  52. {-
  53. ## Finding the Formulas
  54.  
  55. __Simplifying the bonus__
  56.  
  57. I quickly nailed the bonus "for free" thanks to a neat observation:
  58.  
  59. > If checking the top-right corner of the grid for a match,
  60. > you only need to check the top-right corner of the moving rectangle,
  61. > and so forth with the other corners:
  62. >
  63. >     UL of both      UR of both
  64. >     @--+--------+---@
  65. >     |oo|        |ooo|
  66. >     |oo|        +---+
  67. >     +--+            |
  68. >     |               |
  69. >     +---+          ++
  70. >     @---+----------+@
  71. >     LL of both      LR of both
  72.  
  73. Somehow (perhaps ironically) this helped me soon realise that:
  74.  
  75. > The two questions `10 7 3 2 1` and `7 5 0 0 1` are identical.
  76. >
  77. >     10 7 3 2 1    7 5 0 0 1
  78. >     @-+-----@-+   @-------@
  79. >     |o|     |o|   |       |
  80. >     |o|     |o|   |       |
  81. >     +-+     +-|   |       |
  82. >     |       . |   |       |
  83. >     |       . |   |       |
  84. >     |       . |   |       |
  85. >     @-+ . . @-+   @-------@
  86. >     |o|     |o|   
  87. >     |o|     |o|   
  88. >     +-+-----+-+   
  89.  
  90. That's why the variables `h' = h - m` and `w' = w - n` are used.
  91. They're the solution to the bonus.
  92.  
  93. __The answer__
  94.  
  95. Whilst searching for relationships between the example inputs and outputs,
  96. I quickly discovered that the time taken (`t` for demonstration) was simply:
  97.  
  98. > `d = h' * w'`
  99. > `t = d \ v`
  100.  
  101. I also reduced the number of bounces to:
  102.  
  103. > `d / h' + d / w' - 2`
  104.  
  105. However, these formulas failed tests on other examples, like `1 2 0 0 1`.
  106.  
  107. Unfortunately, I happened to see the term "LCM" while skimming the problem page,
  108. and thus led my train of thought went in that direction.
  109. I'm not sure if I'd have made the connection without seeing those three letters.
  110.  
  111. It turned out my initial attempt was only correct when `h * w == lcm h w`,
  112. which coincidentally covered each sample on the problem page.
  113. Using `d = lcm h w` instead yielded correct results.
  114. -}
Success #stdin #stdout 0s 8388607KB
comments ()
stdin
copy 
8 3 0 0 1
15 4 0 0 2
10 7 3 2 1
stdout
copy 
LL 9 24.0
UR 17 30.0
LR 10 35.0
https://ideone.com/5Jm85Z
language:
Haskell (ghc 8.4.4)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!