Coding Dojo solution

[Bartosz Blimke]

Hi.

Here is my solution for the problem we tried to solve at Coding Dojo.
http://gist.github.com/216759

It works in O(nlogn) time.

Bartosz

[Kerry Buckley]

On 23 Oct 2009, at 10:03, Bartosz Blimke <bartosz...@gmail.com>
wrote:

> Here is my solution for the problem we tried to solve at Coding Dojo.

Speaking of which, does anyone have a link to the Gattaca problem spec
and sample data?

Kerry

[Mr Jaba]

Here you go:

http://www.facebook.com/careers/puzzles.php?puzzle_id=15

2009/10/23 Kerry Buckley <kerryj...@googlemail.com>

[Kerry Buckley]

On 23 Oct 2009, at 10:25, Mr Jaba <the....@gmail.com> wrote:

Here you go:

http://www.facebook.com/careers/puzzles.php?puzzle_id=15

Thanks Tom!

Kerry

[Piers Cawley]

I'm afraid it doesn't work because it doesn't check whether
predictions point to the same DNA string. Consider:

4
GAGA
2
0 1 2
2 3 1

Your algorithm would give that a score of 3, by the spec, the maximum
possible score is 2.

[Bartosz Blimke]

Hi Piers.

I was also very confused about the last part of the spec where they say:

"When constructing your output, you may only consider genes exactly as they are described in the input. If you find the contents of a gene replicated elsewhere in the DNA string, you are not allowed to treat the second copy as a viable gene. "

Then I understood what they actually meant. They basically say that you are only allowed to use genes exactly as they are

described by the gene predictions and exactly as they are positioned in the DNA string.

In case you find the contents of some prediction anywhere else in the DNA sequence you are not allowed to treat it as a prediction, unless it's defined in the input. You can only treat predictions defined in the input (by the start and en position) as valid. If the spec defines another prediction with the same content, you are allowed to use it though.

The result of the example you provided will be actually 3.

If the spec would say that you are not allowed to have two predictions with the same content in the solution, it would be much harder to solve. I'm not sure if there is a non-NP solution to this problem but for sure it's much more expensive than loglinear.

I posted my solution to FB to verify this and it passed all the tests.

Bartosz

2009/10/24 Piers Cawley <pdca...@gmail.com>

[Piers Cawley]

On Sat, Oct 24, 2009 at 1:47 PM, Bartosz Blimke
<bartosz...@gmail.com> wrote:
> Hi Piers.
> I was also very confused about the last part of the spec where they say:
>
> "When constructing your output, you may only consider genes exactly as they
> are described in the input. If you find the contents of a gene replicated
> elsewhere in the DNA string, you are not allowed to treat the second copy as
> a viable gene. "
> Then I understood what they actually meant. They basically say that you are
> only allowed to use genes exactly as they are
> described by the gene predictions and exactly as they are positioned in the
> DNA string.
> In case you find the contents of some prediction anywhere else in the DNA
> sequence you are not allowed to treat it as a prediction, unless it's
> defined in the input. You can only treat predictions defined in the input
> (by the start and en position) as valid. If the spec defines another
> prediction with the same content, you are allowed to use it though.
> The result of the example you provided will be actually 3.
> If the spec would say that you are not allowed to have two predictions with
> the same content in the solution, it would be much harder to solve. I'm not
> sure if there is a non-NP solution to this problem but for sure it's much
> more expensive than loglinear.
> I posted my solution to FB to verify this and it passed all the tests.

I stand corrected then.