This was my solution (after reading in the testcases):
NB. Run one case. servers in first box, queries in second
docase =: 3 : 0
NB. Convert queries to machine #s. For each machine, find the
NB. first match; pick machine with the last first-match. Discard
NB. as many as the last first-match.
q =. i.&>/ y
switches =. 0
while. 1 do.
if. 0 = #q =. (i.#>{.y) (>./@(i.~) }. ]) q do. break. end.
switches =. >: switches
end.
switches
)
If it weren't a timed event, for fun I would have tried something like
0 >. <: 0: ` (>:@$:@(>./@(i.&(i.#>{.y)) }. ])) @.([EMAIL PROTECTED]) i.&>/ y
Henry Rich
> -----Original Message-----
> From: [EMAIL PROTECTED]
> [mailto:[EMAIL PROTECTED] On Behalf Of June Kim
> Sent: Sunday, July 27, 2008 6:54 PM
> To: Programming forum
> Subject: [Jprogramming] Saving the Universe
>
> Following is a problem from google code jam 2008, which is an
> interesting contest in the regard that the contest allows any
> programming languages.
>
> http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamF
> tcg8LEghjb250ZXN0cxjqOQw
>
> I have a J solution for the problem but am eager to learn from your
> solutions. I will post my solution here in a couple of days.
>
> ----
> Problem
>
> The urban legend goes that if you go to the Google homepage and search
> for "Google", the universe will implode. We have a secret to share...
> It is true! Please don't try it, or tell anyone. All right, maybe not.
> We are just kidding.
>
> The same is not true for a universe far far away. In that universe, if
> you search on any search engine for that search engine's name, the
> universe does implode!
>
> To combat this, people came up with an interesting solution. All
> queries are pooled together. They are passed to a central system that
> decides which query goes to which search engine. The central system
> sends a series of queries to one search engine, and can switch to
> another at any time. Queries must be processed in the order they're
> received. The central system must never send a query to a search
> engine whose name matches the query. In order to reduce costs, the
> number of switches should be minimized.
>
> Your task is to tell us how many times the central system will have to
> switch between search engines, assuming that we program it optimally.
>
> Input
>
> The first line of the input file contains the number of cases, N. N
> test cases follow.
>
> Each case starts with the number S -- the number of search engines.
> The next S lines each contain the name of a search engine. Each search
> engine name is no more than one hundred characters long and contains
> only uppercase letters, lowercase letters, spaces, and numbers. There
> will not be two search engines with the same name.
>
> The following line contains a number Q -- the number of incoming
> queries. The next Q lines will each contain a query. Each query will
> be the name of a search engine in the case.
>
> Output
>
> For each input case, you should output:
>
> Case #X: Ywhere X is the number of the test case and Y is the number
> of search engine switches. Do not count the initial choice of a search
> engine as a switch.
>
> Limits
>
> 0 < N ? 20
>
> Small dataset
>
> 2 ? S ? 10
>
> 0 ? Q ? 100
>
> Large dataset
>
> 2 ? S ? 100
>
> 0 ? Q ? 1000
>
>
>
> Sample
>
>
> Input
>
> 2
> 5
> Yeehaw
> NSM
> Dont Ask
> B9
> Googol
> 10
> Yeehaw
> Yeehaw
> Googol
> B9
> Googol
> NSM
> B9
> NSM
> Dont Ask
> Googol
> 5
> Yeehaw
> NSM
> Dont Ask
> B9
> Googol
> 7
> Googol
> Dont Ask
> NSM
> NSM
> Yeehaw
> Yeehaw
> Googol
>
>
> Output
>
> Case #1: 1
> Case #2: 0
>
>
>
> In the first case, one possible solution is to start by using Dont
> Ask, and switch to NSM after query number 8.
> For the second case, you can use B9, and not need to make any
> switches.
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
