okbulb2

1 files changed, 138 insertions, 6 deletions

diff --git a/src/main.c b/src/main.c
index c4e74e4..94bc3d0 100644
--- a/src/main.c
+++ b/src/main.c
@@ -3,10 +3,57 @@
 #include <stdint.h>
 #include <okelib2/okelib2.h>
 
+int64_t piss516(int16_t *i,int32_t w);
 int64_t piss5(int32_t *i,int32_t w);
 int64_t piss4(int32_t *i,int32_t w);
+unsigned long long rfp416(unsigned short *bars, unsigned int n);
+unsigned long long rfp4(unsigned int *bars, unsigned int n);
 unsigned long long rfp3(int *bars, int n);
 
+int64_t piss516(int16_t *i,int32_t w){
+  int64_t   v;
+  int64_t   q;
+  int16_t   l;
+  int16_t   m;
+  int32_t   y;
+
+  v = 0;
+  l = 0;
+  q = 0;
+  y = 0;
+  int n = 0;
+
+  for(int32_t x = 0;x < w;x++){
+    int16_t c = i[x];    
+
+    if(c >= l){
+      v  += (int64_t)l*(int64_t)(x-y-1);
+      v  -= q;
+      q   = 0;
+      y   = x;
+      l   = c;
+      n++;
+    }else{
+      q  += c;
+    }
+  }
+
+  m = l; 
+  l = 0;
+
+  for(int32_t x = w-1;i[x] < m;x--){
+    int16_t c = i[x];    
+
+    if(c >= l){
+      l   = c;
+    }else{
+      v  += l-c;
+    }
+  }
+
+  return v;
+}
+
 int64_t piss5(int32_t *i,int32_t w){
   int64_t   v;
   int64_t   q;
@@ -18,6 +65,7 @@ int64_t piss5(int32_t *i,int32_t w){
   l = 0;
   q = 0;
   y = 0;
+  int n = 0;
 
   for(int32_t x = 0;x < w;x++){
     int32_t c = i[x];    
@@ -28,6 +76,7 @@ int64_t piss5(int32_t *i,int32_t w){
       q   = 0;
       y   = x;
       l   = c;
+      n++;
     }else{
       q  += c;
     }
@@ -88,6 +137,68 @@ int64_t piss4(int32_t *i,int32_t w){
   return v;
 }
 
+unsigned long long rfp416(unsigned short *bars, unsigned int n) {
+    unsigned long long bedrock_volume = bars[0];
+    unsigned long long volume = 0;
+    unsigned short highest = bars[0];
+    unsigned int start_i = 0;
+    unsigned int watershed_i = 0;
+
+    for (unsigned int i = 1; i < n; i++) {
+        bedrock_volume += bars[i];
+        if (bars[i] >= highest) {
+            volume += (i - start_i) * (unsigned long long)highest;
+            highest = bars[i];
+            start_i = i;
+            watershed_i = i;
+        }
+    }
+
+    volume += highest;
+
+    highest = bars[n-1];
+    start_i = n-1;
+    for (unsigned int i = n-2; i > watershed_i; i--) {
+        if (bars[i] > highest) {
+            volume += (start_i - i) * (unsigned long long)highest;
+            highest = bars[i];
+            start_i = i;
+        }
+    }
+    return volume + (start_i - watershed_i) * (unsigned long long)highest - bedrock_volume;
+}
+
+unsigned long long rfp4(unsigned int *bars, unsigned int n) {
+    unsigned long long bedrock_volume = bars[0];
+    unsigned long long volume = 0;
+    unsigned long long highest = bars[0];
+    unsigned int start_i = 0;
+    unsigned int watershed_i = 0;
+
+    for (unsigned int i = 1; i < n; i++) {
+        bedrock_volume += bars[i];
+        if (bars[i] >= highest) {
+            volume += (i - start_i) * highest;
+            highest = bars[i];
+            start_i = i;
+            watershed_i = i;
+        }
+    }
+
+    volume += highest;
+
+    highest = bars[n-1];
+    start_i = n-1;
+    for (unsigned int i = n-2; i > watershed_i; i--) {
+        if (bars[i] > highest) {
+            volume += (start_i - i) * highest;
+            highest = bars[i];
+            start_i = i;
+        }
+    }
+    return volume + (start_i - watershed_i) * highest - bedrock_volume;
+}
+
 unsigned long long rfp3(int *bars, int n) {
   unsigned long long volume = 0;
   unsigned long long prev_volume = 0;
@@ -119,16 +230,21 @@ unsigned long long rfp3(int *bars, int n) {
 }
 
 int main(int argc,char **argv){
-  int32_t  *i;
+  uint32_t *i;
+  uint16_t *i16;
   int32_t   w;
   ftimer_t  t;
 
   srand(20);
   w = 100000000;
-  i = malloc(sizeof(int32_t)*w);
+  i   = malloc(sizeof(uint32_t)*w);
+  i16 = malloc(sizeof(uint16_t)*w);
   if(!i) return 1;
+  if(!i16) return 1;
   for(int32_t x = 0;x < w;x++){
-    i[x] = (int32_t)rand() & 0xFFFF;
+    i16[x]  = (uint16_t)rand() & 0xFFFF;
+    if(x > w/2 && i16[x]>0) i16[x] -= 1;
+    i[x]    = i16[x];
   }
 
 /*
@@ -139,16 +255,32 @@ int main(int argc,char **argv){
 
   ftimer_init(&t);
   
+  /*
+  ftimer_zero(&t);  
+  printf("rfp3    %14lld    ",rfp3(i,w));
+  print_ftimer(&t);
+  */
+
   ftimer_zero(&t);  
-  printf("rfp3    %lld    ",rfp3(i,w));
+  printf("rfp4    %14lld    ",rfp4(i,w));
   print_ftimer(&t);
 
   ftimer_zero(&t);  
-  printf("piss4   %lld    ",piss4(i,w));
+  printf("rfp416  %14lld    ",rfp416(i16,w));
+  print_ftimer(&t);
+
+  /*
+  ftimer_zero(&t);  
+  printf("piss4   %14lld    ",piss4(i,w));
+  print_ftimer(&t);
+  */
+
+  ftimer_zero(&t);  
+  printf("piss5   %14lld    ",piss5(i,w));
   print_ftimer(&t);
 
   ftimer_zero(&t);  
-  printf("piss5   %lld    ",piss5(i,w));
+  printf("piss516 %14lld    ",piss516(i16,w));
   print_ftimer(&t);
 
   return 0;