LoginSignup
0

More than 5 years have passed since last update.

オフラインリアルタイムどう書くE11 Ruby で解く

Posted at

問題はこちら:
http://qiita.com/Nabetani/items/10b2ccc28301e44e09e6
http://nabetani.sakura.ne.jp/hena/orde11tredis/

parents を覚えさせておいて Array#& で共通の親を取得する。
近い順に並んでいるのであとは index とるだけ。

require 'bundler/inline'

gemfile do
  source 'https://rubygems.org'

  gem 'minitest', require: 'minitest/autorun'
  gem 'minitest-reporters'

  gem 'awesome_print'
  gem 'tapp'

  gem 'pry'
  gem 'pry-rescue', require: 'pry-rescue/minitest'
  gem 'pry-stack_explorer'
end

class Tree
  attr_reader :base, :leaves, :parents

  include Enumerable

  def initialize(base, parents=[])
    @base = base
    @parents = parents
    @leaves = dividers_for(base).map do |n|
      Tree.new(n, [self] + parents)
    end
  end

  def each(&block)
    block.call(self)

    leaves.each do |leaf|
      leaf.each(&block)
    end
  end

  def distance(a, b)
    as = select {|tree| tree.base == a }
    bs = select {|tree| tree.base == b }

    as.product(bs).map {|_a, _b|
      next _a.parents.index(_b) + 1 if _a.parents.include?(_b)
      next _b.parents.index(_a) + 1 if _b.parents.include?(_a)

      common_parent = (_a.parents & _b.parents).first
      _a.parents.index(common_parent) + _b.parents.index(common_parent) + 2
    }.min
  end

  private

  def dividers_for(base)
    return [] if base <= 3

    (2...base).select {|n| base % n == 0 }.map {|n| n + 1 }
  end
end

def solve(input)
  base, a, b = input.scan(/\d+/).map(&:to_i)
  Tree.new(base).distance(a, b).to_s
end

TEST_DATA = <<~EOS
/*0*/ test( "50:6,3", "1" );
/*1*/ test( "98:5,11", "4" );
/*2*/ test( "1000:33,20", "7" );
/*3*/ test( "514:9,18", "8" );
/*4*/ test( "961:5,4", "3" );
/*5*/ test( "1369:1369,3", "2" );
/*6*/ test( "258:16,12", "5" );
/*7*/ test( "235:13,3", "2" );
/*8*/ test( "1096:19,17", "8" );
/*9*/ test( "847:7,17", "6" );
/*10*/ test( "1932:3,5", "2" );
/*11*/ test( "2491:4,8", "3" );
/*12*/ test( "840:421,36", "2" );
/*13*/ test( "1430:37,111", "3" );
/*14*/ test( "496:17,9", "2" );
/*15*/ test( "891:6,10", "1" );
/*16*/ test( "1560:196,21", "2" );
/*17*/ test( "516:20,12", "5" );
/*18*/ test( "696:30,59", "2" );
/*19*/ test( "1760:5,441", "2" );
/*20*/ test( "1736:11,26", "5" );
/*21*/ test( "1518:17,34", "4" );
/*22*/ test( "806:63,16", "5" );
/*23*/ test( "1920:3,97", "2" );
/*24*/ test( "1150:13,22", "4" );
/*25*/ test( "920:116,5", "1" );
/*26*/ test( "2016:7,337", "2" );
/*27*/ test( "408:9,25", "2" );
/*28*/ test( "735:36,8", "2" );
/*29*/ test( "470:5,31", "2" );
/*30*/ test( "2100:12,351", "3" );
/*31*/ test( "870:36,10", "1" );
/*32*/ test( "1512:253,13", "2" );
/*33*/ test( "697:12,15", "3" );
/*34*/ test( "1224:5,14", "2" );
/*35*/ test( "986:125,17", "3" );
/*36*/ test( "864:12,13", "3" );
/*37*/ test( "500:21,51", "2" );
/*38*/ test( "819:33,21", "4" );
/*39*/ test( "594:55,3", "2" );
/*40*/ test( "638:17,24", "3" );
EOS

Minitest::Reporters.use!(Minitest::Reporters::ProgressReporter.new)

describe 'Doukaku' do
  TEST_DATA.each_line do |test|
    number, input, expected = test.scan(/(\d+).*"(.*)", "(.*)"/)[0]

    it "##{number}" do
      assert_equal expected, solve(input)
    end
  end
end

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0