Category: algorithm

Mr. White is a very versatile person – absolutely everything is interesting to him. Perhaps this is why he has many friends. Quite unfortunately, however, none of his friends are versatile at all. Each of them is interested only in two topics and refuses to talk about anything else. Therefore, each time Mr. White organizes a party, it’s a big problem for him to decide whom to invite so that the party is interesting to everybody. Now that Mr. White has a lot of experience in organizing parties, he knows for sure that a party will be interesting if and only if there’s a topic interesting to each of the invited friends.

#include <vector>
#include <string>
using namespacee std;

class InterestingParty {
    public:
        int bestInvitation(vector <string> first, vector <string> second) {
            int i, j;
            int ans = 0;

            for(i=0; i<first.size(); i++){
                int f=0;
                int s=0;
                for(j=0; j<first.size(); j++){
                    if(first[i] == first[j]) f++;
                    if(first[i] == second[j]) f++;
                    if(second[i] == first[j]) s++;
                    if(second[i] == second[j]) s++;
                }
                ans = max(f, ans);
                ans = max(s, ans);
            }
            return ans;
        }
}

連想配列を使う場合

#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespacee std;

class InterestingParty {
    public:
        int bestInvitation(vector <string> first, vector <string> second) {
            map <string, int> dic;

            for(int i=0; i<first.size(); i++){
                dic[first[i]] = 0;
                dic[second[i]] = 0;
            }

            for(int i=0; i<first.size; i++){
                dic[first[i]]++;
                dic[second[i]]++;
            }
            int ans = 0;
            map <string, int>::iterator it;
            for(it=dic.begin(); it!=dic.end(); it++){
                ans = max(ans, it->second);
            }
            return ans;
        }
}

Amazon, 楽天, Yahooのショッピングカートの送料のアルゴリズムを確認したい。

### Amazon
商品ごとに送料が計算され、合計金額で合計の送料が計算される

### 楽天
商品ごとに送料計算

### Yahoo Shopping
商品ごとに送料があり、注文手続きの際に、合計金額と合計送料を計算

なるほど、送料は基本商品ごとに持っていて、単純に合計するのね。
同じ会社の商品の場合の計算方法がよくわからん。例えば、A社から送料300円の商品Bと商品Cを購入した時って、送料600円にならないよね。。

うーむ。つまり、商品ごとに送料を持っていて、同じ会社から複数商品を買った場合は、計算処理してるってことね。

出力する

$orders = [
	'yamada' => ['a','b','c'],
	'tanaka' => ['b','f'],
	'sato' => ['a','g','b','f','h','i'],
	'goto' => ['e','f'],
	'kudo' => ['e','g'],
	'oba' => ['b','f','e'],
	'toda' => ['c'],
];

// 省略

foreach($data as $k => $v){
	arsort($v);
	$v = array_slice($v, 0, 5);
	echo $k ." を買った人はこんな商品も買っています=> ";
	foreach($v as $name => $num){
		echo $name . " ";
	}
	echo "<br>";
}

なんか大丈夫っぽいな。ksort($data);で、abcdef順にソートする。
Excelで出力したい。

$orders = [
	'yamada' => ['a','b','c'],
	'tanaka' => ['b','f'],
	'sato' => ['a','g','b','f'],
	'goto' => ['e','f'],
];

foreach($orders as $order => $products){
	foreach($products as $product){
		$togethers = (array_diff($products, array($product)));
		foreach($togethers as $together){
			// 一緒に買った商品の配列が既にある
			if($data[$product] != null){
				if(in_array($together, array_keys($data[$product]) )){
					echo "yes";
					foreach($data[$product] as $key => $value){
						if($key == $together){
							$data[$product][$key] += 1;
						}
					}
				} else {
					$data[$product] = array_merge($data[$product], array($together => 1));
				}
			// 一緒に買った商品の配列がない
			} else {
				$data[$product] = array($together => 1);
			}
		}
	}
}

echo "<pre>";
var_dump($data);
echo "</pre>";

aを買ってる人でbを買ってる人は2人いる。
bを買ってる人で、aを買ってる人は2人、fを買ってる人は2人

array(6) {
[“a”]=>
array(4) {
[“b”]=>
int(2)
[“c”]=>
int(1)
[“g”]=>
int(1)
[“f”]=>
int(1)
}
[“b”]=>
array(4) {
[“a”]=>
int(2)
[“c”]=>
int(1)
[“f”]=>
int(2)
[“g”]=>
int(1)
}
[“c”]=>
array(2) {
[“a”]=>
int(1)
[“b”]=>
int(1)
}
[“f”]=>
array(4) {
[“b”]=>
int(2)
[“a”]=>
int(1)
[“g”]=>
int(1)
[“e”]=>
int(1)
}
[“g”]=>
array(3) {
[“a”]=>
int(1)
[“b”]=>
int(1)
[“f”]=>
int(1)
}
[“e”]=>
array(1) {
[“f”]=>
int(1)
}

きゃあああああああああああああああ、ほぼほぼ出来たくさい。
こっからさらにソートして出力したい。　OK、カモン

各人の注文データがある

$orders = [
	'yamada' => ['a','b','c'],
	'tanaka' => ['b','f'],
	'sato' => ['a','g'],
	'goto' => ['e','f'],
];

foreach($orders as $order => $products){
	foreach($products as $product){
		echo $product;
	}
	echo "<br>";
}

abc
bf
ag
ef

こうすると、一緒に買われている商品が配列で入る。

$orders = [
	'yamada' => ['a','b','c'],
	'tanaka' => ['b','f'],
	'sato' => ['a','g','b'],
	'goto' => ['e','f'],
];

foreach($orders as $order => $products){
	foreach($products as $product){
		$togethers = (array_diff($products, array($product)));
		foreach($togethers as $together){
			if($data[$product] != null){
				$data[$product] = array_merge($data[$product], array($together => 1));
			} else {
				$data[$product] = array($together => 1);
			}
			
		}
	}
}

array(6) {
[“a”]=>
array(3) {
[“b”]=>
int(1)
[“c”]=>
int(1)
[“g”]=>
int(1)
}
[“b”]=>
array(4) {
[“a”]=>
int(1)
[“c”]=>
int(1)
[“f”]=>
int(1)
[“g”]=>
int(1)
}
[“c”]=>
array(2) {
[“a”]=>
int(1)
[“b”]=>
int(1)
}
[“f”]=>
array(2) {
[“b”]=>
int(1)
[“e”]=>
int(1)
}
[“g”]=>
array(2) {
[“a”]=>
int(1)
[“b”]=>
int(1)
}
[“e”]=>
array(1) {
[“f”]=>
int(1)
}
}

keyの値を足して、一緒に買われている回数まで出したい。
おうおう、もうちょいだ

mysql内に、 ‘2019-10-05′,’2020-01-05’,’2020-02-13’などのレコードがあった場合に、その範囲内の連続したYYYYMMの配列(2019-10, 2019-11, 2019-12, 2020-01)を作りたい時
-> 最初と最後のUnixTime範囲内で、1ヵ月づつ増えるFor文を作る。

        $last = Hoge::where('user_id', $id)->orderBy('time','ASC')->first();
        $last_month = substr($last['time'], 0, 7);
        $last_unix = strtotime('first day of ' . $last_month);
        $latest = Hoge::where('user_id', $id)->orderBy('time','DESC')->first();
        $latest_month = substr($latest['time'], 0, 7);
        $latest_unix = strtotime('last day of ' . $latest_month);

        for($time = $last_unix; $time <= $latest_unix; $time = strtotime('+1 month', $time)){
            $Ym[] = date('Ym', $time);
        }

取得したデータをそのままUnixTimeにして 1ヵ月づつ増やすと、　$last_month　+ 1 month > $latest_month となる場合があるので、$last_monthを月初の日付、$latest_monthを月末の日付に変換してからFor文を回す必要がある。

う〜ん、最初にDBのデータ型考える際に、ロジックの計算処理を考えてデータ型を決めれるようになるな。

Exclusive control is the exclusive control of a resource when a conflict arises due to simultaneous access from multiple processes to shared resources that can be used by multiple processes in the execution of a computer program. While it is used as it is, it means the things of processing that maintains consistency by making other processes unavailable. Also called mutual exclusion or mutual exclusion. The case where up to k processes may access shared resources is called k-mutual exclusion.

def ensure_float(v):
	if is_number(v):
		return float(v)

def audit_population_density(input_file):
	for row in input_file:
		population = ensure_float(row['populationTotal'])
		area = ensure_float(row['areaLand'])
		population_density = ensure_float(row['populationDensity'])
		if population and area and population_density:
			calculated_density = population / area
			if math.fabs(calculated_density - population_density) > 10:
				print "Possibly bad population density for ", row['name']

if __name__ == '__main__':
	input_file = csv.DictReader(open("cities.csv"))
	skip_lines(input_file, 3)
	audit_population_density(input_file)