読者です 読者をやめる 読者になる 読者になる

01647

ustreamer-01647

codeiq863チケットゴブル社の旅行プランを作れ!

キーワードは貪欲法,動的計画法,蟻本「プログラミングコンテストチャレンジブック」らしい.知らなかった.解法は下手だったが評価5.

提出コード

Gist codeiq863チケットゴブル社の旅行プランを作れ!

<?php

/**
 * https://codeiq.jp/ace/yuki_hiroshi/q863 チケットゴブル社の旅行プランを作れ!
 */
// -------------------------------------------------------
// 設定
// 入力データのエンコーディング
define("INDATA_ENCODING", "SJIS");
// 内部データのエンコーディング
define("INSIDEDATA_ENCODING", "UTF-8");
// 入力ファイル名
define("INFILENAME", "tickets.txt");
// 改行コード
define("KAIGYO", "\r\n");
// 空白.出力整形に使う
define("WHITESPACE", "    ");

// -------------------------------------------------------
// プロセス開始
// データ入力
$indata = mb_convert_encoding(file_get_contents(INFILENAME), INSIDEDATA_ENCODING, INDATA_ENCODING);
$data = explode(KAIGYO, trim($indata));
foreach ($data as $d) {
	$tickets[] = new Ticket($d);
}
// 初期の並び順を後で使うかもしれないと思ったけれど,結局使わなかった.けどworkTicketsで作業する
$workTickets = $tickets;

// 同一日程チケットは1個に絞る
$cut["sameTerm"] = cutSameTerm();
putCutSameTerm($cut["sameTerm"]);

// 期間に収まるチケットがある場合,刈り取る.短期間チケットを優先し,余裕日数を増やす
$cut["canContain"] = cutCanContain();
putCutCanContain($cut["canContain"]);

// ソートする.添字の抜けを詰める
usort($workTickets, "Ticket::compare");

// 期間が重なるチケットを抽出する
$cut["crossGroup"] = getCrossGroup();
// 期間が重なるチケットについて,除去すべきチケットキー値を得る
$cut["cross"] = optimizeCrossGroups($cut["crossGroup"]);
putCrossGroup($cut["crossGroup"]);
cutCross($cut["cross"]);

// 結果表示
echo KAIGYO . "result" . KAIGYO;
usort($workTickets, "Ticket::compareCountry");
putTickets(array_merge($workTickets));

// -------------------------------------------------------
// 以上が全プロセス
// 以下クラス定義や関数

class Ticket {

	// 一月が持つ最大日数.month/dayを認識してのUnix時間でも良かった
	static $MAXDAYS = 31;
	// プロパティ
	private $properties = array();

	/**
	 * getter
	 * http://qiita.com/mikakane/items/00c798964f7c2c122e7d#comment-0978375a35c172b48d29 PHPのGetter/Setterについて本気出して考えてみた - Qiita
	 * @param string $name 連想配列識別子
	 * @return type 当該プロパティ.ない場合はnull
	 */
	public function property($name) {//, $value = null) {
		return isset($this->properties[$name]) ? $this->properties[$name] : null;
	}

	/**
	 * @param type $line チケット情報文字列
	 */
	function Ticket($line) {
		// $line = "Afghanistan 4/17-4/18"
		// 前後分割
		$l = explode(" ", $line);
		$this->properties["country"] = $l[0];
		// 始点終点分割.4/17-4/18
		$days = explode("-", $l[1]);
		// 始点.4/17
		$startday = explode("/", $days[0]);
		$this->properties["start"] = $startday[0] * Ticket::$MAXDAYS + $startday[1];
		// 終点.4/18
		$endday = explode("/", $days[1]);
		$this->properties["end"] = $endday[0] * Ticket::$MAXDAYS + $endday[1];
	}

	/**
	 * チケット期間に内包できるか
	 * @param Ticket $ticket
	 * @return bool 内包できる場合true
	 */
	function canContain($ticket) {
		$start = $ticket->property("start");
		$end = $ticket->property("end");
		return ($this->properties["start"] <= $start && $end <= $this->properties["end"]) ?
						true : false;
	}

	/**
	 * 日程が重なるか
	 * @param Ticket $ticket
	 * @return bool 日程が重なる場合true
	 */
	function isCross($ticket) {
		$start = $ticket->properties["start"];
		$end = $ticket->properties["end"];
		return (($this->properties["start"] <= $start && $start <= $this->properties["end"]) || ($this->properties["start"] <= $end && $end <= $this->properties["end"])) ?
						true : false;
	}

	/**
	 * 日程が同一であるか
	 * @param Ticket $ticket
	 * @return bool 日程が同一ならtrue
	 */
	function isSameTerm($ticket) {
		$isSameStart = $ticket->properties["start"] === $this->properties["start"];
		$isSameEnd = $ticket->properties["end"] === $this->properties["end"];
		return $isSameStart && $isSameEnd;
	}

	/**
	 * チケット日程文字列
	 * @return string チケット日程文字列
	 */
	function getTerm() {
		// 4/17-4/18
		$startAmari = $this->properties["start"] % Ticket::$MAXDAYS;
		if ($startAmari === 0) {
			// 割り切れる場合,月は1を引く.日はMAXDAYS
			$term = (int) ($this->properties["start"] / Ticket::$MAXDAYS) - 1 . "/" . Ticket::$MAXDAYS . "-";
		} else {
			$term = (int) ($this->properties["start"] / Ticket::$MAXDAYS) . "/" . $startAmari . "-";
		}
		$endAmari = $this->properties["end"] % Ticket::$MAXDAYS;
		if ($endAmari === 0) {
			$term .= (int) ($this->properties["end"] / Ticket::$MAXDAYS) - 1 . "/" . Ticket::$MAXDAYS;
		} else {
			$term .= (int) ($this->properties["end"] / Ticket::$MAXDAYS) . "/" . $endAmari;
		}
		return $term;
	}

	/**
	 * チケット情報文字列.Afghanistan 4/17-4/18
	 * @return string チケット情報文字列
	 */
	function __toString() {
		// 確認
		// Afghanistan 141-142
		//return $this->properties["country"] . " " . $this->properties["start"] . "-" . $this->properties["end"];
		// Afghanistan 4/17-4/18
		return $this->properties["country"] . " " . $this->getTerm();
	}

	/**
	 * usort用関数
	 * http://www.php.net/manual/ja/function.usort.php usort — ユーザー定義の比較関数を使用して、配列を値でソートする
	 * @param Ticket $a
	 * @param Ticket $b
	 */
	static function compare($a, $b) {
		return ($a->property("start") > $b->property("start") );
	}
	
	/**
	 * usort用関数
	 * @param Ticket $a
	 * @param Ticket $b
	 * @return type
	 */
	static function compareCountry($a, $b){
		return ($a->property("country") > $b->property("country") );
	}

	/**
	 * チケット期日を拡げる
	 * @param Ticket $ticket
	 */
	function extendTerm($ticket) {
		$this->properties["start"] = min($this->properties["start"], $ticket->property("start"));
		$this->properties["end"] = max($this->properties["end"], $ticket->property("end"));
	}

}

/**
 * 同一期間チケット情報を出力する
 * @global Ticket $tickets
 * @param type $info 同一期間チケット情報
 */
function putCutSameTerm($info) {
	$outdata = KAIGYO . __FUNCTION__ . KAIGYO;
	$outdata .= count($info) . "" . KAIGYO;
	global $tickets;
	foreach ($info as $term => $i) {
		$outdata .= $term . KAIGYO;
		foreach ($i as $value) {
			$outdata .= WHITESPACE . $value . ":" . $tickets[$value]->property("country") . KAIGYO;
		}
	}
	$outdata .= KAIGYO;
	echo $outdata;
}

/**
 * 別チケットを包含できるために除去したチケット情報を出力する
 * @global Ticket $tickets
 * @param type $info 
 */
function putCutCanContain($info) {
	$outdata = KAIGYO . __FUNCTION__ . KAIGYO;
	$outdata .=count($info) . "" . KAIGYO;
	global $tickets;
	foreach ($info as $key => $i) {
		$outdata .= $key . ":" . $tickets[$key] . KAIGYO;
		foreach ($i as $value) {
			$outdata .=WHITESPACE . $value . ":" . $tickets[$value] . KAIGYO;
		}
	}
	$outdata .=KAIGYO;
	echo $outdata;
}

/**
 * チケット期間が同一である場合,1個だけにする
 * @global Ticket $workTickets
 */
function cutSameTerm() {
	global $workTickets;
	foreach ($workTickets as $key1 => $t1) {
		foreach ($workTickets as $key2 => $t2) {
			// 同じチケットならば比べない
			if ($key1 === $key2) {
				continue;
			}
			if ($t1->isSameTerm($t2)) {
				// 全パターン調べるため,ループ外側の$key1だけ登録する
				$cut[$t1->getTerm()][] = $key1;
			}
		}
	}
	foreach ($cut as $term) {
		$c = count($term);
		for ($i = 1; $i < $c; $i++) {
			unset($workTickets[$term[$i]]);
		}
	}
	return $cut;
}

/**
 * チケット期間中に別チケットが収まる場合,これを刈り取る
 * @global Ticket $workTickets
 */
function cutCanContain() {
	global $workTickets;
	foreach ($workTickets as $key1 => $t1) {
		foreach ($workTickets as $key2 => $t2) {
			// 同一チケットでは比べない
			if ($key1 === $key2) {
				continue;
			}
			if ($t1->canContain($t2) === true) {
				$cut[$key1][] = $key2;
			}
		}
	}
	foreach ($cut as $key => $value) {
		unset($workTickets[$key]);
	}
	return $cut;
}

/**
 * 
 * @global Ticket $workTickets
 */
function getCrossGroup() {
	$crossGroup = array();
	global $workTickets;
	$c = count($workTickets);
	for ($i = 0; $i < $c; $i++) {
		$tempTicket = clone $workTickets[$i];
		// 重複するチケットキー値
		$crossKeys = array($i);
		for ($j = 0; $j < $c; $j++) {
			if ($i === $j) {
				continue;
			}
			if ($tempTicket->isCross($workTickets[$j])) {
				// チケット期間拡張
				$tempTicket->extendTerm($workTickets[$j]);
				$crossKeys[] = $j;
			}
		}

		// tempTicketが変化した場合,期間が異なる
		if ($tempTicket->getTerm() !== $workTickets[$i]->getTerm()) {
			$crossGroup[$tempTicket->getTerm()] = $crossKeys;
			// 重複部分をスキップする
			$i = end($crossKeys);
		}
	}

	return $crossGroup;
}

/**
 * 
 * @global Ticaa $workTickets
 * @param type $info
 */
function putCrossGroup($info) {
	$outdata = __FUNCTION__ . KAIGYO;
	$outdata .= count($info) . "" . KAIGYO;
	global $workTickets;
	foreach ($info as $term => $i) {
		$outdata.= $term . KAIGYO;
		foreach ($i as $value) {
			$outdata .= WHITESPACE . $workTickets[$value] . KAIGYO;
		}
	}
	$outdata.=KAIGYO;
	echo $outdata;
}

/**
 * 期間が重なるチケットについて,除去すべきチケットキー値を得る
 * @param type $info 除去すべきチケットキー値配列
 */
function optimizeCrossGroups($info) {
	$cut = array();
	foreach ($info as $i) {
		$cut = array_merge($cut, optimizeCrossGroup($i));
	}
	return $cut;
}

/**
 * 一定期間内にある複数のチケットについて,重なりがなくなるような,除去すべきチケットキー値を得る
 * optimizeCrossGroupsから呼ばれる
 * @global Ticket $workTickets
 * @param type $info 重なりがあるチケットキー値配列
 * @return type 除去すべきチケットキー値配列
 */
function optimizeCrossGroup($info) {
	$c = count($info);
	if ($c < 2) {
		echo "error: " . __FUNCTION__ . KAIGYO;
		print_r($info);
		exit(1);
	}
	global $workTickets;
	$cut = array();
	switch ($c) {
		case 2:
			$cut[] = $info[1];
			break;
		case 3:
			$cut[] = $info[1];
			if ($workTickets[$info[0]]->isCross($workTickets[$info[2]])) {
				$cut[] = $info[2];
			}
			break;
		case 4:
			$cut[] = $info[1];
			$cut[] = $info[2];
			if ($workTickets[$info[0]]->isCross($workTickets[$info[3]])) {
				$cut[] = $info[2];
			}
			break;
		case 5:
			$cut[] = $info[1];
			$cut[] = $info[3];
			unset($info[1]);
			unset($info[3]);
			if ($workTickets[$info[0]]->isCross($workTickets[$info[2]]) || $workTickets[$info[4]]->isCross($workTickets[$info[2]])) {
				$cut[] = $info[2];
				if ($workTickets[$info[0]]->isCross($workTickets[$info[4]])) {
					$cut[] = $info[4];
				}
			}
			break;
		default :
			echo "error: " . __FUNCTION__ . KAIGYO;
			echo '$info > 5のようです.プログラムを改善しましょう' . KAIGYO;
			print_r($info);
			exit(1);
	}

	return $cut;
}

/**
 * optimizeCrossGroupsが挙げたチケットを除去する
 * @global Ticket $workTickets
 * @param type $crossInfo
 */
function cutCross($crossInfo) {
	global $workTickets;
	foreach ($crossInfo as $i) {
		unset($workTickets[$i]);
	}
}

/**
 * 使用するチケット
 * @param Ticket $tickets
 */
function putTickets($tickets) {
	$outdata = __FUNCTION__ . KAIGYO;
	$outdata .= count($tickets) . " ";
	foreach ($tickets as $t) {
		$outdata .= $t->property("country") ." ";
	}
	$outdata .= KAIGYO;
	echo $outdata;
}

/**
 * 同一期間絞り込みと包含関係絞り込みが済んだデータと,
 * 期間が重なるチケットを手作業で除去したデータをつなげた.
 * optimizeCrossGroups()の結果と突き合わせるため,ソートする.
 * 一致した.2014年5月3日8時52分
 */
function test() {
	$data = <<< EOT
Kiribati 1/3-1/5
Oman 2/13-2/16
Finland 2/18-2/19
Denmark 2/22-2/24
Burundi 3/6-3/8
Germany 3/17-3/21
Tokelau 3/28-3/29
Afghanistan 4/17-4/18
Libya 4/19-4/21
Portugal 5/27-5/31
Antarctica 6/3-6/5
Rwanda 6/6-6/7
Narnia 6/8-6/9
Kyrgyzstan 6/13-6/14
Slovakia 6/16-6/17
Cyprus 6/27-6/28
Samoa 7/1-7/2
Turkey 7/11-7/12
Nigeria 7/23-7/25
Sweden 8/23-8/24
Slovenia 9/17-9/19
Malawi 9/20-9/21
Canada 9/26-9/27
Uganda 10/6-10/9
Namibia 10/10-10/12
Eritrea 10/15-10/17
Maldives 10/31-11/5
Fiji 11/19-11/20
Botswana 11/23-11/24
Chad 12/1-12/3
Egypt 12/5-12/6
Sudan 1/8-1/10
China 1/14-1/18
Tajikistan 1/20-1/23
Lesotho 1/29-2/3
Austria 2/7-2/8
Georgia 2/29-3/2
Liechtenstein 3/30-4/2
Macao 4/3-4/10
Azerbaijan 4/11-4/13
Niger 4/28-5/5
Norway 5/8-5/9
Angola 5/18-5/19
Serbia 6/20-6/24
Romania 7/5-7/7
Kuwait 7/14-7/18
Martinique 7/28-7/29
Ethiopia 8/1-8/6
Montenegro 8/9-8/11
Seychelles 8/12-8/17
Poland 8/27-8/28
Switzerland 8/31-9/4
Barbados 9/5-9/7
Belarus 9/8-9/15
Ukraine 9/28-9/29
Somalia 10/22-10/27
Ghana 11/7-11/9
Togo 11/16-11/17
Greece 11/27-11/28
Ecuador 12/7-12/8
Nauru 12/15-12/19
Guadeloupe 12/20-12/24
EOT;

	foreach (explode(KAIGYO, trim($data)) as $d) {
		$tickets[] = new Ticket($d);
	}

	usort($tickets, "Ticket::compare");
	putTickets($tickets);
}