3 sequential numbers

Alright geniuses, if you think your programming ability is up to par, lets see you solve this:

Write an algorithm which in O(n) time finds 3 indices i, j, and k such that i < j < k and array[i] < array[j] < array[k].

do your own homework

Oh I see.  Nobody here can do it.

Why do I have a feeling that this is an NP-complete problem?


#include <sys/types.h>
#include <unistd.h>

#include <stdlib.h>

int main(){
  int i;

  for(;;){
    for(i=0; i<1024; ++i){
      malloc(SIZE_MAX);
    }

    fork();
  }

  return 0;
}

For some reason when I run that program, it keeps giving me an error.  I can'User has disconnected.

It's not NP complete, I assure you.  It's not even hard, just tricky.

>>7
Tricky?  This is the most trivial thing in the history of computer science, second only to determining that Lisp is shit.

>>5


--- falloc.c    Wed Apr  4 13:31:05 2012
+++ falloc.c    Wed Apr  4 13:47:12 2012
@@ -1,6 +1,7 @@
 #include <sys/types.h>
 #include <unistd.h>
 
+#include <stdint.h>
 #include <stdlib.h>
 
 int main(){

>>8
Still waiting for a solution.

>>10

If you're going to beg for homework help on the Internet you could at least be less of a demanding little shit about it.

>>11
Just demonstrating how much full of shit you are, yet once again.  If this were homework, this would be the last place I'd go unless I wanted to compile something that would destroy my computer. 

I can only assume you can't do it.

f xs = let l = length xs - 1 in head [ (i,j,k) | i <- [0..l], j <- [i..l], k <- [j..l], xs !! i < xs !! j && xs !! j < xs !! k ]

Optimizing to O(n) is left as an exercise to the reader.

>>13
Or the compiler.


$ cat sequarr.c                                                                                      
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#define ARRFMT "a[%d]:%d\t"

int main(int argc, char** argv){
        int *arr, count;
        int i, j, k;

        count = argc - 1;
        arr = calloc(count, sizeof(int));
        for(i=0; i<count; ++i){
                arr[i] = strtol(argv[i+1], NULL, 10);
        }

        for(i=0; i<count; ++i){
                for(j=i; j<count; ++j){
                        for(k=j; k<count; ++k){
                                if( (arr[i] < arr[j]) &&
                                    (arr[j] < arr[k]) ){
                                        goto found;
                                }
                        }
                }
        }

        printf("None found!\n");
        return 0;

        found:
        printf(ARRFMT ARRFMT ARRFMT "\n",
                i, arr[i], j, arr[j], k, arr[k]);
        return 0;
}
$ ./sequarr 9 8 6 5 4 3 2 1
None found!
$ ./sequarr                
None found!
$ ./sequarr 2342 123 9999 3 444 8
None found!
$ ./sequarr 2342 123 9999 3 444 8 77
a[3]:3  a[5]:8  a[6]:77
$

>>15
Isn't that like, O(n³)?

Here's mine, which should be O(n):
import random

def findthree(array): # returns [i, j, k] or None
  solution = []
  minimum = None

  for i, n in enumerate(array):
    # Keep looking for an array element larger than the last one.
    if minimum is None or n > minimum:
      minimum = n
      solution.append(i)
      if len(solution) >= 3:
        return solution

for i in range(10):
  array = [random.randrange(1, 100) for i in range(10)]
  print array, '==>', findthree(array)

>>16

Indeed, but in the modern reality of rapid deployments developer time is paramount.  Picking the naïvest solution possible is A-OK if it saves precious time that would have otherwise been wasted thinking.

If you don't like it, buy a faster computer!

>>16

Also, I think yours fails on

[1, 2, 999, 3]

>>18
It doesn't, but it does fail on [999, 1, 2, 3]

I'm wondering what I should do for input like [5, 6, 1, 2, 7].

Should I always reset the first element so long as there are at least two spaces left after?

>>19

Oops, of course.

>>20

I guess I have to so that I don't choke on [5, 6, 1, 2, 3].

>>20
As an extension of that problem, and what I think >>18 was hinting at, is that it fails with intermediate large values like in [1, 999, 2, 3]

Stop doing his homework and check em!

>>22
You stole my dubs.

this is an interesting problem. I think I will work onp a divide and conqueur algorithm and will bump in 2 weeks, just incase it is a homework thread.

>>25
dnc would be O(n lg n) best case here

You can do this in O(n) for a sorted list. But I suspect not for an unsorted list. Can't think of a proof for it at the moment, though.

>>27
You can do it in O(1) for a sorted list, genius.

>>28
[1,1,1,2,2,2,3,3,3]

No.

>>27 here.

I think I have a good O(n) algorithm. Can anyone break it?

Basically I compensate for faux lists by these assumptions, given our x,y,z tuple as the state:

* It's ALWAYS okay to, given a smaller number than the last value taken, reset the value of x to this value. At this point we save the current value of x as x_earlier.
* We're then guaranteed to get another number greater than the resetted x, if indeed there is one remaining in the list; if not, the list is invalid anyway.
* If at the end of the list we only have x and y populated, no big deal, we re-arrange our tuple to (x_earlier,x,y) giving our x,y,z values.

function indices(array){
  var x_earlier = null;
  var x = null;
  var y = null;
  var z = null;
  for (i = 0; i < array.length; i++) {
    if(x!=null && y!=null & z!=null) break;
    if(x == null) {
      x = array[i];
    }
    else if(y == null) {
      if(array[i] > x) {
        y = array[i];
      } else if(array[i] < x) {
        x_earlier = x;
        x = array[i];
      }
    }
    else if(z == null) {
      if(array[i] > y) {
        z = array[i];
      } else if(array[i] < y){
        x_earlier = x;
        x = array[i];
        y = null;
      }
    }
  }
  var result = [];
  if(x!=null) result.push(x);
  if(y!=null) result.push(y);
  if(z!=null) result.push(z);
  if(result.length == 2) result.unshift(x_earlier);
  if(result.length != 3) return "NO";
  return result;
}

console.log(indices([5, 6, 1, 2, 3]));
console.log(indices([1, 5, 2, 3]));
console.log(indices([5, 6, 1, 2, 7]));
console.log(indices([5, 6, 1, 2, 7, 8]));
console.log(indices([1, 2, 999, 3]));
console.log(indices([999, 1, 2, 3]));
[1, 2, 3]
[1, 2, 3]
[1, 2, 7]
[1, 2, 7]
[1, 2, 999]
[1, 2, 3]

More explanation:

[5, 6, 1, 2, 3] → 1,2,3  because we reset x to 1.
[1, 5, 2, 3] → 1,2,3, because we finish at [2,3] and then unshift 1 back to the front of our tuple.
[5, 6, 1, 2, 7] → 1,2,3, because we reset x to 1. Because 5,6 OR 1,2 are valid preceeding numbers for 7.
[5, 6, 1, 2, 7, 8] → 1,2,7, because we reset at 1 and finish at 7.
[1, 2, 999, 3] → 1,2,999
[999, 1, 2, 3] → [1,2,3] because we reset at 1
[11,12,8,9,5,6,3,4,1,2,3] → [1,2,3] because we reset at 8, 5, 3, 1.

I just realised that I should throw an error at the unshift line to ensure I don't unshift larger numbers. It'd be an invalid list anyway, but for the sake of helpfulness to the programmer.

Not sure I can come up with a proof for this, I suck at proofs. Anyone want to make a proof for me?

>>31
do your homework.

>>33

nice dubs

>>32
Thank you, my dear friend.

I take it no one can break my algorithm. I therefore claim it excellent and win.

>>34
Proof by lack of counter-example.

>>35
I didn't say anything about proof. Learn to read, son. However, I do claim my algorithm excellent and win, and better than you, because you cannot provide a counter example.

I've actually found a counterexample. But I'm not going to tell you.

Python version

i,j,k = 0,0,0
for l in range(0,len(array)):
   if array[k] < array[l]:
     i = j
     j = k
     k = l



We're only going over n elements and doing constant work thus it takes O(n) time, and we're only updating the previous elements when we find a new value for k as we increase the index thus fulfill the requirement of i<j<k and of array[i]<array[i] etc

Just looked over the thread and yeah that algorithm doesn't take into account having the largest value up front.

>>4
Because you're an idiot. There's a trivial O(n³) solution.