英語うんちく ― 米国はイラクに正義をお届け?!
正解は一つとは限らない―だから面白い

ミネラルウォーターの謎、謎解き編

Tsu  昨日のエントリー「ミネラルウォーターの謎」、答えは「すぐに私が飲んでいる水だと分かるように色をつけた」である。

 ヒントは問題の「私の家では、『ミネラルウォーターをたくさん飲む』という健康法が流行っている」という部分にある。つまり、私以外にも同じようにミネラルウォーターを飲んでいる人たち(妻と子供)がいるのである。

 『ミネラルウォーターをたくさん飲む』とはいっても、一度にはたくさん飲めないので、家族全員がそれぞれペットボトルを抱えてそこから直接ちびちびと飲むことになる。するとだらしない私とか息子とかは飲みかけのペットボトルをパソコンの横だとか、テレビの前だとかに置いたままどこかへ行ってしまうことがしょっちゅうあるのだ。そんなことをしていると、置いてあるペットボトルを見ても自分のものかどうかすぐに分からなくなってしまい、誰かのを飲んでしまったり、すでに飲みかけのボトルがあるのにもう一本空けてしまったりするのだ。

 ペットボトルのラベルに名前を書いておくという方法もあるが、書きにくいし、分かりにくい。それならいっそのこと「色のつく何か」を混ぜておけばよかろうと白羽の矢を立てたのが、一度だけゼリーを作る時に使ったまま何年間も放置されていたペパーミント(リキュール酒)である。

 ペパーミントの色はとても強いので、数滴まぜただけで十分に色がつく。こうすることにより、「緑色の水の入ったペットボトルは私の」ということが私自身にも家族にも一目で分かるようになったのである。「ミネラルウォーターに混ぜて飲むのなら摂取するのが目的であるはず」という常識に囚われている限りこの答えにはたどりつけない。

そこで、またまたもう一問、今度はプログラマーになりたい人向きの頭の柔軟体操。

【問題】ある直線上に線分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部作もこちらに移した。一気に読む場合は、下から上に読まないと、先に解答を見ることになってしまうので注意。

Comments

e-donkey

2線分の中点間の距離が、線分の長さの和の半分より短い。ながいっすか?

前屈の達人

B0がA0以上A1以下
または
B1がA0以上A1以下

zorio

B0<=A1 && A0<=B1

重ならない条件
A1 < B0 || B1 < A0

その反対なので、
!(A1 < B0 || B1 < A0)
⇒ !(A1 < B0) && !(B1 < A0)
⇒ B0<=A1 && A0<=B1

びしばし

ベクトル(B0→A1)と(B1→A0)の向きが同じかどうかで判別します。
同じ方向なら、A、Bは重なっていません。

びしばし

あ、式になってなかったですね。

if (B0-A1)*(B1-A0) > 0 then 重なっていない
else 重なっている

akausagi

線分Bを固定して考えると
重なってるのは
B0-(A1-A0) つまり
A0+B0-A1 から
B0-A1<0 で
(B0-A1)*(B1-A0)<0
↑と同じですねー

akausagi

エンティティが…
線分Bを固定して考えると
重なってるのは
B0-(A1-A0)<A0<B1
つまり
A0+B0-A1<A0<B1
から
B0-A1<0<B1-A0

(B0-A1)*(B1-A0)<0
↑と同じですねー

holic

これって、
http://satoshi.blogs.com/life/2005/06/post_2.html
の1次元版ですよね。

satoshi

>これって、http://satoshi.blogs.com/life/2005/06/post_2.html
の1次元版ですよね。

 その通りです。色々とうんちくを傾けるのにちょうど良いので、1次元版に簡略化して出題しました。

タカハシ

一次元なので

AO≦B0≦A1
または
A0≦B1≦A1
または
B0≦A0≦B1
または
B0≦A1≦B1


でよいかと思います

すら

2つの線分が重ならない条件はすごく簡単で
(A1<B0)||(B1<A0)
線分は重なるか重ならないかのどちらかなので
重なる条件は実は重ならない条件の否定になる。
よって答えは
!((A1<B0)||(B1<A0))
もうちょっと展開すると
(A1>=B0)&&(B1>=A0)

って、とっくに同じ答え出てますね…orz

ると

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]

演算回数の少なさだけが簡潔さではないということと、用意されたもの(例題の答え)は有効利用するということで。


#<を半角にすると上手く投稿できない……。

ると

しまった。これだとAがBに含まれる場合が抜けてますね。

Verify your Comment

Previewing your Comment

This is only a preview. Your comment has not yet been posted.

Working...
Your comment could not be posted. Error type:
Your comment has been posted. Post another comment

The letters and numbers you entered did not match the image. Please try again.

As a final step before posting your comment, enter the letters and numbers you see in the image below. This prevents automated programs from posting comments.

Having trouble reading this image? View an alternate.

Working...

Post a comment

Your Information

(Name is required. Email address will not be displayed with the comment.)