Skip to content

Instantly share code, notes, and snippets.

@hyuki0000
Last active August 29, 2015 14:01
Show Gist options
  • Save hyuki0000/6273a52b9454ccfca095 to your computer and use it in GitHub Desktop.
Save hyuki0000/6273a52b9454ccfca095 to your computer and use it in GitHub Desktop.
チケットゴブル問題の参照ファイルです。
62 Afghanistan Angola Antarctica Austria Azerbaijan Barbados Belarus Botswana Burundi Canada China Cyprus Denmark Ecuador Eritrea Ethiopia Finland Georgia Germany Ghana Greece Guadeloupe Jordan Kiribati Liberia Libya Liechtenstein Macao Malawi Malaysia Martinique Mongolia Montenegro Montserrat Myanmar Namibia Narnia Niger Nigeria Oman Palau Poland Portugal Romania Rwanda Samoa Senegal Serbia Seychelles Slovakia Slovenia Somalia Sudan Sweden Switzerland Tajikistan Tokelau Turkey Uganda Ukraine Zambia Zimbabwe
Austria 1/1-1/5
Belgium 1/6-1/10
Canada 1/7-1/8
Denmark 1/9-1/10
Egypt 1/18-1/30
#! /usr/bin/ruby
class Ticket
def initialize(country, from_month, from_day, to_month, to_day)
if from_month > to_month
abort("Invalid request: from_month == #{from_month} > to_month == #{to_month}")
elsif from_month == to_month and from_day >= to_day
abort
end
@country, @range = country, Range.new(from_month * 100 + from_day, to_month * 100 + to_day)
end
def first
@range.first
end
def last
@range.last
end
def include?(e)
@range.include?(e)
end
def size
@range.size
end
def conflict?(r)
self.include?(r.first) || self.include?(r.last) || r.include?(self.first) || r.include?(self.last)
end
def to_s
@country + '(' + @range.to_s + ')'
end
attr_reader :country
end
class Solver
def initialize(filename)
@requests = []
File::open(filename) do |f|
while line = f.gets
line.chomp!
if line.match(/^(\S+)\s+(\d+)\/(\d+)-(\d+)\/(\d+)/)
country, from_month, from_day, to_month, to_day = $1, $2.to_i, $3.to_i, $4.to_i, $5.to_i
@requests << Ticket.new(country, from_month, from_day, to_month, to_day)
else
abort("ERROR:#{line}")
end
end
end
end
# 終了日の早いものから順に選ぶ(最善)
def solve1
rs = @requests.sort { |a, b| a.last <=> b.last }
result = []
while !rs.empty?
r = rs.shift
rs.delete_if { |e| e.conflict?(r) }
result << r
end
result.size.to_s + ' ' + result.map {|r| r.country }.sort.join(' ')
end
# 開始日が早いものから順に選ぶ
def solve2
rs = @requests.sort { |a, b| a.first <=> b.first }
result = []
while !rs.empty?
r = rs.shift
rs.delete_if { |e| e.conflict?(r) }
result << r
end
result.size.to_s + ' ' + result.map {|r| r.country }.sort.join(' ')
end
# 期間が短いものから順に選ぶ
def solve3
rs = @requests.sort { |a, b| a.size <=> b.size }
result = []
while !rs.empty?
r = rs.shift
rs.delete_if { |e| e.conflict?(r) }
result << r
end
result.size.to_s + ' ' + result.map {|r| r.country }.sort.join(' ')
end
# できるだけ重なりの少ないものから順に選ぶ
def solve4
conflict_count = Hash.new(0)
@requests.each do |r|
rs = @requests.clone
conflict_count[r.country] = rs.keep_if { |s| r.conflict?(s) }.size
end
rs = @requests.sort { |a, b| conflict_count[a.country] <=> conflict_count[b.country] }
result = []
while !rs.empty?
r = rs.shift
rs.delete_if { |e| e.conflict?(r) }
result << r
end
result.size.to_s + ' ' + result.map {|r| r.country }.sort.join(' ')
end
end
# puts Solver.new("tickets.txt").solve1
# puts Solver.new("tickets.txt").solve2
# puts Solver.new("tickets.txt").solve3
# puts Solver.new("tickets.txt").solve4
puts
puts "answer for five.txt:"
puts Solver.new("five.txt").solve1
puts
puts "answer for tickets.txt"
puts Solver.new("tickets.txt").solve1
Afghanistan 4/17-4/18
Albania 9/25-10/2
Algeria 11/23-11/25
Andorra 8/22-8/27
Angola 5/18-5/19
Anguilla 3/2-3/3
Antarctica 6/3-6/5
Argentina 2/2-2/7
Armenia 5/18-5/21
Aruba 1/1-1/8
Australia 3/25-3/31
Austria 2/7-2/8
Azerbaijan 4/11-4/13
Bahamas 8/20-8/24
Bahrain 7/26-7/31
Bangladesh 6/22-6/26
Barbados 9/5-9/7
Belarus 9/8-9/15
Belgium 6/8-6/10
Belize 7/6-7/10
Benin 8/6-8/10
Bermuda 9/3-9/6
Bhutan 9/14-9/19
Botswana 11/23-11/24
Brazil 7/10-7/13
Bulgaria 2/15-2/22
Burundi 3/6-3/8
Cambodia 3/16-3/22
Cameroon 12/3-12/9
Canada 9/26-9/27
Chad 12/1-12/3
Chile 5/7-5/13
China 1/14-1/18
Colombia 3/2-3/5
Comoros 8/26-8/28
Congo 4/2-4/9
Cuba 1/10-1/17
Cyprus 6/27-6/28
Denmark 2/22-2/24
Djibouti 5/19-5/24
Dominica 12/19-12/24
Ecuador 12/7-12/8
Egypt 12/5-12/6
Eritrea 10/15-10/17
Estonia 11/4-11/11
Ethiopia 8/1-8/6
Fiji 11/19-11/20
Finland 2/18-2/19
France 6/29-7/3
Gabon 3/27-4/3
Gambia 9/25-9/28
Georgia 2/29-3/2
Germany 3/17-3/21
Ghana 11/7-11/9
Gibraltar 7/10-7/15
Greece 11/27-11/28
Greenland 5/3-5/6
Grenada 10/11-10/18
Guadeloupe 12/20-12/24
Guam 4/11-4/16
Guatemala 3/6-3/9
Guernsey 9/13-9/16
Guinea 6/4-6/8
Guyana 10/26-10/30
Haiti 1/20-1/24
Hungary 1/20-1/24
Iceland 7/25-8/1
India 7/21-7/28
Indonesia 8/20-8/27
Iraq 9/12-9/18
Ireland 10/25-10/28
Israel 6/11-6/18
Italy 2/6-2/12
Jamaica 1/23-1/25
Jersey 1/31-2/6
Jordan 12/5-12/6
Kazakhstan 4/2-4/8
Kenya 7/29-8/4
Kiribati 1/3-1/5
Kuwait 7/14-7/18
Kyrgyzstan 6/13-6/14
Latvia 2/6-2/12
Lebanon 1/10-1/14
Lesotho 1/29-2/3
Liberia 7/14-7/18
Libya 4/19-4/21
Liechtenstein 3/30-4/2
Lithuania 5/2-5/8
Luxembourg 8/28-8/31
Macao 4/3-4/10
Madagascar 11/15-11/22
Malawi 9/20-9/21
Malaysia 11/10-11/16
Maldives 10/31-11/5
Mali 9/17-9/24
Malta 8/23-8/25
Martinique 7/28-7/29
Mauritania 10/13-10/20
Mauritius 12/21-12/28
Mayotte 10/24-10/29
Mexico 2/24-3/2
Monaco 12/4-12/7
Mongolia 5/6-5/8
Montenegro 8/9-8/11
Montserrat 12/12-12/16
Morocco 6/26-6/29
Mozambique 2/18-2/21
Myanmar 11/29-12/3
Namibia 10/10-10/12
Narnia 6/8-6/9
Nauru 12/15-12/19
Nepal 5/6-5/8
Netherlands 12/8-12/12
Nicaragua 9/29-10/2
Niger 4/28-5/5
Nigeria 7/23-7/25
Niue 5/14-5/21
Norway 5/8-5/9
Oman 2/13-2/16
Pakistan 6/11-6/16
Palau 6/11-6/14
Panama 7/18-7/20
Paraguay 11/9-11/15
Peru 12/5-12/7
Philippines 4/6-4/11
Pitcairn 6/24-6/29
Poland 8/27-8/28
Portugal 5/27-5/31
Qatar 1/16-1/23
Romania 7/5-7/7
Rwanda 6/6-6/7
Samoa 7/1-7/2
Senegal 11/19-11/20
Serbia 6/20-6/24
Seychelles 8/12-8/17
Singapore 7/23-7/25
Slovakia 6/16-6/17
Slovenia 9/17-9/19
Somalia 10/22-10/27
Spain 9/24-9/29
Sudan 1/8-1/10
Suriname 11/28-11/29
Swaziland 6/10-6/16
Sweden 8/23-8/24
Switzerland 8/31-9/4
Tajikistan 1/20-1/23
Thailand 6/27-6/30
Togo 11/16-11/17
Tokelau 3/28-3/29
Tonga 5/8-5/10
Tunisia 11/16-11/23
Turkey 7/11-7/12
Turkmenistan 11/28-11/30
Tuvalu 3/15-3/22
Uganda 10/6-10/9
Ukraine 9/28-9/29
Uruguay 7/1-7/6
Uzbekistan 2/26-3/4
Vanuatu 8/15-8/21
Yemen 6/24-6/29
Zambia 1/27-2/3
Zimbabwe 10/29-11/5
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment