Problem 86

Problem 86 - Project Euler
クモとアリ,最短経路などでググると有名らしい問題がでてくるけど,それよりは単純.頂点から頂点への移動,その最短距離が整数になる場合を数えるだけ.なんとなく三角形作ればいいんだなってのはすぐ分かる.
しかしかなり手間取った.三角形を作れば必ず最短経路になるってわけじゃないし,天井とか壁とか床とか区別しないってことに気付くのも遅れた.

is.int.side <- function(n,m){
  floor(sqrt(n^2+m^2))^2==n^2+m^2
}
paths <- function(n){
  x <- (2:(2*n))[is.int.side(n,2:(2*n))]
  if(length(x)==0) return(0)
  ans <- 0
  for(i in x){
    if(n > i){
      ans <- ans + floor(i/2)
    }else{
      ans <- ans + ceiling(n-(i-1)/2)
    }
  }
  ans
}

sum.path <- 0
i <- 1
while(sum.path < 1e6){
  i <- i+1
  sum.path <- sum.path + paths(i)
}
i