Same algorithm; 2 boxes per case, servers in first box, queries in second.
swtch=: 4 : 0
c=. >./ y i. x
(}:c}.y), ({:y)+c<#y
)
([EMAIL PROTECTED] [ swtch^:_ ],[EMAIL PROTECTED])&>/"1
Most of my time I spent in formatting the output.
R.E. Boss
> -----Oorspronkelijk bericht-----
> Van: [EMAIL PROTECTED] [mailto:programming-
> [EMAIL PROTECTED] Namens Henry Rich
> Verzonden: maandag 28 juli 2008 1:47
> Aan: 'Programming forum'
> Onderwerp: RE: [Jprogramming] Saving the Universe
>
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
