posted 9 months ago

I cooked up an algorithm that seems to work initially but fails a hidden test on Code Fights. Can you give me a hint as to what's wrong?

Here is the complete (this time) problem statement.

Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees.

Example

For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be

sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].

Input/Output

[time limit] 3000ms (java)

[input] array.integer a

If a[i] = -1, then the ith position is occupied by a tree. Otherwise a[i] is the height of a person standing in the ith position.

Constraints:

5 ≤ a.length ≤ 15,

-1 ≤ a[i] ≤ 200.

[output] array.integer

Sorted array a with all the trees untouched.

My implementation:

Here is the complete (this time) problem statement.

Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees.

Example

For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be

sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].

Input/Output

[time limit] 3000ms (java)

[input] array.integer a

If a[i] = -1, then the ith position is occupied by a tree. Otherwise a[i] is the height of a person standing in the ith position.

Constraints:

5 ≤ a.length ≤ 15,

-1 ≤ a[i] ≤ 200.

[output] array.integer

Sorted array a with all the trees untouched.

My implementation:

posted 9 months ago

Let's understand what is being asked first. How do you know this output you showed is correct?

For me looks, that 170, -1, ... is descending, while you are asked to sort in non-descending.

Sergiu Dobozi wrote:Your task is to rearrange the people by their heights in a non-descending order

...

For a = [-1, 150, 190, 170, -1, -1, 160, 180],

the output should be

sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].

Let's understand what is being asked first. How do you know this output you showed is correct?

For me looks, that 170, -1, ... is descending, while you are asked to sort in non-descending.

posted 9 months ago

Because -1 should not be moved. It's like a tree. Every other number is like a person, they can be moved around the trees.

Liutauras Vilda wrote:Sergiu Dobozi wrote:Your task is to rearrange the people by their heights in a non-descending order

...

For a = [-1, 150, 190, 170, -1, -1, 160, 180],

the output should be

sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].

Let's understand what is being asked first. How do you know this output you showed is correct?

For me looks, that 170, -1, ... is descending, while you are asked to sort in non-descending.

Because -1 should not be moved. It's like a tree. Every other number is like a person, they can be moved around the trees.

posted 9 months ago

Thanks a lot! I wrote a new code and it worked on all test cases.

Liutauras Vilda wrote:Ah, yes, didn't see that, sorry.

Fails on this case: A= {-1, 150, -1, -1, 190, 170, -1, -1, 160, 180, -1}

Output after sorting: [-1, 150, -1, -1, 160, 170, -1, -1, 190, 180, -1]

Write down your internal test cases first to see if you can pass all locally.

Thanks a lot! I wrote a new code and it worked on all test cases.

posted 9 months ago

I just created two new arrays: one as a copy of the original, which I then sorted using Arrays.sort, and another one to hold the results. Then I iterated over the original, moving trees to the results and putting in the next sorted person otherwise. This gave a functional solution that did not mutate the original input array. I think it was about 8 or 9 lines of code.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 9 months ago

Your post led me to think in a different way for sure!

Here is my implementation, mine is a little more than 9 lines, hope I got it right.

Junilu Lacar wrote:I just created two new arrays: one as a copy of the original, which I then sorted using Arrays.sort, and another one to hold the results. Then I iterated over the original, moving trees to the results and putting in the next sorted person otherwise. This gave a functional solution that did not mutate the original input array. I think it was about 8 or 9 lines of code.

Your post led me to think in a different way for sure!

Here is my implementation, mine is a little more than 9 lines, hope I got it right.

posted 9 months ago

That's almost exactly what I have. Looks like my primary method was about 9 lines; I extracted some of that to another method so I actually had 19 lines in all, including blank lines and method headers and closing braces.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Don't get me started about those stupid light bulbs. |