ミネラルウォーターの謎、謎解き編
2006.06.08
昨日のエントリー「ミネラルウォーターの謎」、答えは「すぐに私が飲んでいる水だと分かるように色をつけた」である。
ヒントは問題の「私の家では、『ミネラルウォーターをたくさん飲む』という健康法が流行っている」という部分にある。つまり、私以外にも同じようにミネラルウォーターを飲んでいる人たち(妻と子供)がいるのである。
『ミネラルウォーターをたくさん飲む』とはいっても、一度にはたくさん飲めないので、家族全員がそれぞれペットボトルを抱えてそこから直接ちびちびと飲むことになる。するとだらしない私とか息子とかは飲みかけのペットボトルをパソコンの横だとか、テレビの前だとかに置いたままどこかへ行ってしまうことがしょっちゅうあるのだ。そんなことをしていると、置いてあるペットボトルを見ても自分のものかどうかすぐに分からなくなってしまい、誰かのを飲んでしまったり、すでに飲みかけのボトルがあるのにもう一本空けてしまったりするのだ。
ペットボトルのラベルに名前を書いておくという方法もあるが、書きにくいし、分かりにくい。それならいっそのこと「色のつく何か」を混ぜておけばよかろうと白羽の矢を立てたのが、一度だけゼリーを作る時に使ったまま何年間も放置されていたペパーミント(リキュール酒)である。
ペパーミントの色はとても強いので、数滴まぜただけで十分に色がつく。こうすることにより、「緑色の水の入ったペットボトルは私の」ということが私自身にも家族にも一目で分かるようになったのである。「ミネラルウォーターに混ぜて飲むのなら摂取するのが目的であるはず」という常識に囚われている限りこの答えにはたどりつけない。
そこで、またまたもう一問、今度はプログラマーになりたい人向きの頭の柔軟体操。
【問題】ある直線上に線分AとBがあります。線分Aの両端の座標はそれぞれA0とA1(ただしA0<A1)、線分Bの端の座標はそれぞれB0とB1(ただしB0<B1)とします。そのとき、線分Aと線分Bが一部でも重なる(一点だけで接している場合も重なっているとみなす)ための条件を出来るだけ簡単な式で書いてください。式は純粋な数式でも良いし、プログラム言語の一つを使ってもOK。
「式を書け」と言われてもとまどってしまう人もいるだろうから、簡単な例題とその解答例を書いておく。
【簡単な例題】ある直線上に線分Aと点Pがあります。線分Aの両端の座標はそれぞれA0とA1(ただしA0<A1)、点Pの座標はP0とします。そのとき、点Pが線分Aの上にある(PがAのどちらかの端点にある場合も含む)ための条件を出来るだけ簡単な式で書いてください。
【解答例】
例1.(A0<=P0 && P0<=A1)
例2.(A0<=P0 and P0<=A1)
例3.P0はA0以上でA1以下
大切なことは「出来るだけ簡単な式で書く」という部分。妙に複雑になり始めたら「何かおかしい」と思った方が良いかも知れない。
【追記】 この手のエントリーが増えてきたので、「頭の柔軟体操」として独立したカテゴリーに。「ビルゲイツの面接試験シリーズ」4部作もこちらに移した。一気に読む場合は、下から上に読まないと、先に解答を見ることになってしまうので注意。
2線分の中点間の距離が、線分の長さの和の半分より短い。ながいっすか?
Posted by: e-donkey | 2006.06.08 at 15:05
B0がA0以上A1以下
または
B1がA0以上A1以下
Posted by: 前屈の達人 | 2006.06.08 at 17:46
B0<=A1 && A0<=B1
重ならない条件
A1 < B0 || B1 < A0
その反対なので、
!(A1 < B0 || B1 < A0)
⇒ !(A1 < B0) && !(B1 < A0)
⇒ B0<=A1 && A0<=B1
Posted by: zorio | 2006.06.08 at 18:40
ベクトル(B0→A1)と(B1→A0)の向きが同じかどうかで判別します。
同じ方向なら、A、Bは重なっていません。
Posted by: びしばし | 2006.06.08 at 18:41
あ、式になってなかったですね。
if (B0-A1)*(B1-A0) > 0 then 重なっていない
else 重なっている
Posted by: びしばし | 2006.06.08 at 19:19
線分Bを固定して考えると
重なってるのは
B0-(A1-A0) つまり
A0+B0-A1 から
B0-A1<0 で
(B0-A1)*(B1-A0)<0
↑と同じですねー
Posted by: akausagi | 2006.06.08 at 21:03
エンティティが…
線分Bを固定して考えると
重なってるのは
B0-(A1-A0)<A0<B1
つまり
A0+B0-A1<A0<B1
から
B0-A1<0<B1-A0
で
(B0-A1)*(B1-A0)<0
↑と同じですねー
Posted by: akausagi | 2006.06.08 at 22:05
これって、
http://satoshi.blogs.com/life/2005/06/post_2.html
の1次元版ですよね。
Posted by: holic | 2006.06.09 at 05:30
>これって、http://satoshi.blogs.com/life/2005/06/post_2.html
の1次元版ですよね。
その通りです。色々とうんちくを傾けるのにちょうど良いので、1次元版に簡略化して出題しました。
Posted by: satoshi | 2006.06.09 at 08:05
一次元なので
AO≦B0≦A1
または
A0≦B1≦A1
または
B0≦A0≦B1
または
B0≦A1≦B1
でよいかと思います
Posted by: タカハシ | 2006.06.09 at 08:22
2つの線分が重ならない条件はすごく簡単で
(A1<B0)||(B1<A0)
線分は重なるか重ならないかのどちらかなので
重なる条件は実は重ならない条件の否定になる。
よって答えは
!((A1<B0)||(B1<A0))
もうちょっと展開すると
(A1>=B0)&&(B1>=A0)
って、とっくに同じ答え出てますね…orz
Posted by: すら | 2006.06.09 at 10:26
Rubyにて
def in_range(p0, a0, a1)
a0 <= p0 && p0 <= a1
end
[b0, b1].any? do |p| in_range(p, a0, a1) end
Haskellにて
any (\p0 -> a0 <= p0 && p0 <= a1) [b0, b1]
演算回数の少なさだけが簡潔さではないということと、用意されたもの(例題の答え)は有効利用するということで。
#<を半角にすると上手く投稿できない……。
Posted by: ると | 2006.06.10 at 03:45
しまった。これだとAがBに含まれる場合が抜けてますね。
Posted by: ると | 2006.06.10 at 07:25