問題の趣旨

問題文は上のリンク先で確認してもらうとして、趣旨としては、要素の並べ替え問題なのだが、要素同士の順位はネットワーク越しにAPI経由しか取れないし、一度にわかるのは2つの要素の順位の大小だけ。

こういったときに効率よく並べ替えをどうするか、要はAPIを叩く回数を減らすにはどうするかというのが中心の問題。

あとはエラー時のハンドリングなどを見るものと思われる。

ソースコード

toybox/solve.rb at 263acef1105f5e0461a59b2940ed75351aa905c5 · nanjakkun/toybox · GitHub

require "net/http"
require "json"

class Monster
  include Comparable 

  URI_ROOT = "https://ob6la3c120.execute-api.ap-northeast-1.amazonaws.com/Prod/battle/"

  def initialize(name:)
    @name = name
  end

  def to_s
    @name
  end

  def <=>(that)
    uri = URI.parse("#{URI_ROOT}#{self}+#{that}")

    # response example: {"winner":"dragon","loser":"griffin"}
    response = Net::HTTP.get_response(uri)

    if response.code.to_i != 200
      raise "status code is #{response.code}"
    end

    res = JSON.parse(response.body)

    # puts res
    
    res['winner'] == @name ? 1 : -1
  end
end

arr = ARGV.map{|arg| Monster.new(name: arg)}

puts arr.sort.reverse.map(&:to_s).join(' ')

ちょっとだけ自分で解説

最適解ではない、です。

この手の問題だと、自分で最も効率の良い（と思った）ソートアルゴリズムを実装したくなるかもしれないが、

標準ライブラリのArray#sortを使いました。

Comparableをincludeして<=>メソッドを実装すればsortできます。

<=>の中でAPIコールしてどちらが大きいか返せばOK。

module Comparable (Ruby 2.7.0 リファレンスマニュアル)

sortの中身が分からずに使うの気持ち悪いとか思うかもしれないですが

（大体の言語の実装系ではソートアルゴリズム指定しない場合はクイックソートで、要素数少ないときだけ別のを入れてるパターンが多い気がする）

任せてしまってもそんなに悪くないんじゃないかと。

実際いくつかのパターンで、自分で書いたクイックソートに置き換えて試してみましたがAPIコール数は同じでした（全部試したわけではないので違うケースもあるかもしれない）。

コード量多くなる割に効果がないのでその部分は消しましたが。

他、APIの結果キャッシュが要ると思うかもしれないですが、試した限りでは同じものが2度以上呼ばれていなかったので実装しませんでした。

所感

問題中に示されているURI、実際に叩けるんですね。 AWS LambdaとAmazon API Gatewayで出来ているんでしょうか。

なんじゃくにっき

プログラミングの話題中心。

クックパッドマートのエンジニア採用試験の問題を解く

問題の趣旨

ソースコード

ちょっとだけ自分で解説

所感