RubyでTopCoderの問題を解いてみる(深さ優先探索)

TopCoder SRM425 Div2 Level1を解いてみました。

※旧ブログからの転載記事です。

[問題要約]
東西南北自由に動き回るロボットが指定回数動いたときに、同じ地点に戻ってこない確率を求めよ。

ここでは深さ優先探索を用いてロボットの歩行パターンを列挙し、最後に結果をまとめています。
深さ優先探索を、はじめて実装しました。

class CrazyBot

    # class variable

    @@grid = Array.new(100).map{Array.new(100, false)}

    @@vx = [1,-1,0,0]

    @@vy = [0,0,1,-1]

    @@prob = Array.new(4).map{0}


    #

    #= 成功する確率を求める

    # 

    def get_probability(n, east, west, south, north)
      @@prob[0] = east / 100.0

      @@prob[1] = west / 100.0

      @@prob[2] = south / 100.0

      @@prob[3] = north / 100.0
      pp @@prob
      return dfs(50,50,n)
    end
    #

    #= 深さ優先探索

    #

    def dfs(x, y, n)

      return 0 if @@grid[x][y] # 既に通過している

      return 1 if n == 0 # 探索しつくした
      #pp "dfs x=#{x}, y=#{y}, n=#{n}"
      @@grid[x][y] = true # 通過したら印をつける

      ret = 0
      for i in 0..3 do

        ret += dfs(x+@@vx[i], y+@@vy[i], (n-1)) * @@prob[i]

      end
      @@grid[x][y] = false # 探索が終わって、上に戻ったら印を消す

      return  ret
    end
  end
crazy_bot = CrazyBot.new

# example1

pp "correct" if 1.0 == crazy_bot.get_probability(1,25,25,25,25)
# example2

pp "correct" if 0.75 == crazy_bot.get_probability(2,25,25,25,25)
# example3

pp "correct" if 1.0 == crazy_bot.get_probability(7,50,0,0,50)

初心者がiOSアプリと連携する自社サービスを"浅く"チューニングしてみた話

※旧ブログからの転載記事です。

最近、お仕事ではiPhoneアプリとそのAPIをRailsで作っておりました。

それなりに多数のアクセスが見込まれるフェーズになってきたため、サーバサイドでの高速化に着手し、その中で得られた知見を社内で共有しました。

cocoa podsとparse sdkを使用した時のUndefined symbols for architecture ...を解消した話

※旧ブログからの転載記事です。

parseのQuickstart tutorialに従って、CocoaPodsを使用した既存のプロジェクトに Parse ios SDKを組み込んでいたところ、Linker errorが多数発生しました。

Undefined symbols for architecture i386:

  "_FBTokenInformationExpirationDateKey", referenced from:

      -[PFFacebookTokenCachingStrategy cacheTokenInformation:] in ParseFacebookUtils(PFFacebookTokenCachingStrategy.o)

      -[PFFacebookTokenCachingStrategy expirationDate] in ParseFacebookUtils(PFFacebookTokenCachingStrategy.o)

      -[PFFacebookTokenCachingStrategy setExpirationDate:] in ParseFacebookUtils(PFFacebookTokenCachingStrategy.o)

  "_FBTokenInformationTokenKey", referenced from:

      -[PFFacebookTokenCachingStrategy accessToken] in ParseFacebookUtils(PFFacebookTokenCachingStrategy.o)

      -[PFFacebookTokenCachingStrategy setAccessToken:] in ParseFacebookUtils(PFFacebookTokenCachingStrategy.o)

  "_FBTokenInformationUserFBIDKey", referenced from:

      -[PFFacebookTokenCachingStrategy facebookId] in ParseFacebookUtils(PFFacebookTokenCachingStrategy.o)

      -[PFFacebookTokenCachingStrategy setFacebookId:] in ParseFacebookUtils(PFFacebookTokenCachingStrategy.o)

  "_OBJC_CLASS_$_FBAppCall", referenced from:

      objc-class-ref in ParseFacebookUtils(PFFacebookAuthenticationProvider.o)

  "_OBJC_CLASS_$_FBRequest", referenced from:

      objc-class-ref in ParseFacebookUtils(PFFacebookAuthenticationProvider.o)

  "_OBJC_CLASS_$_FBSession", referenced from:

      objc-class-ref in ParseFacebookUtils(PFFacebookAuthenticationProvider.o)

  "_OBJC_CLASS_$_FBSessionTokenCachingStrategy", referenced from:

      _OBJC_CLASS_$_PFFacebookTokenCachingStrategy in ParseFacebookUtils(PFFacebookTokenCachingStrategy.o)

  "_OBJC_METACLASS_$_FBSessionTokenCachingStrategy", referenced from:

      _OBJC_METACLASS_$_PFFacebookTokenCachingStrategy in ParseFacebookUtils(PFFacebookTokenCachingStrategy.o)

ld: symbol(s) not found for architecture i386

clang: error: linker command failed with exit code 1 (use -v to see invocation)

現時点での最善の選択肢は、Facebook SDKをCocoaPodsに追加するか、Objc linker　flagを削除するか、どちらかになるそうです。僕は前者を選択してPodfileに下記を追記して、pod installしました。
pod 'Facebook-iOS-SDK'

ありがとう、stackoverflow!

[参考]
How to use cocoa pods and the parse sdk without getting linker errors