From c512cd80ab18d18bd5ab8ec136af2c46772cbd73 Mon Sep 17 00:00:00 2001
From: john <john@eeepc>
Date: Sun, 4 Mar 2012 12:10:51 +0300
Subject: [PATCH] imped brute search (too slow)

---
 1.4/ariprog.in   |   4 +-
 1.4/ariprog.java | 111 ++++++++++++++-----------------------------------------
 2 files changed, 29 insertions(+), 86 deletions(-)

diff --git a/1.4/ariprog.in b/1.4/ariprog.in
index 64fbf37..33cd01f 100644
--- a/1.4/ariprog.in
+++ b/1.4/ariprog.in
@@ -1,2 +1,2 @@
-18
-100
+22
+250
diff --git a/1.4/ariprog.java b/1.4/ariprog.java
index bb5b7a7..e01b582 100644
--- a/1.4/ariprog.java
+++ b/1.4/ariprog.java
@@ -55,61 +55,10 @@ class ariprog {
 
     //////////////////////////////////////////
 
-    static class DiffRecord {
-        int          value;
-        int          count;
-        DiffRecord   next;
-
-        private static DiffRecord           pool = null;
-
-        public static int      total_alloced = 0;
-
-        public static final DiffRecord      max = new DiffRecord(Integer.MAX_VALUE, 0, null);
-
-        DiffRecord (int value, int count, DiffRecord next) {
-            this.value = value;
-            this.count = count;
-            this.next  = next;
-        }
-
-        static DiffRecord alloc(int value, int count, DiffRecord next) {
-            if(pool == null) {
-                total_alloced++;
-                return new DiffRecord(value, count, next);
-            }
-
-            DiffRecord r = pool;
-            pool = pool.next;
-
-            r.value = value;
-            r.count = count;
-            r.next  = next;
-
-            return r;
-        }
-
-        static DiffRecord release(DiffRecord d) {
-            DiffRecord r = d.next;
-
-            d.next = pool;
-            pool = d;
-
-            return r;
-        }
-    }
-
-    static class Bisquare {
-        public final int    value;
-        public DiffRecord   diffs;
-
-        public Bisquare(int value, DiffRecord diffs) {
-            this.value = value;
-            this.diffs = diffs;
-        }
-    }
-
     static int                  progression_limit = 0;
-    static Vector<Bisquare>     bisquares = null;
+
+    static Vector<Integer>      bisqs = null;
+    static BitSet               bisq_set = null;
 
     static final TreeMap<Integer, Vector<Integer>>    result = new TreeMap<Integer, Vector<Integer>> ();
 
@@ -126,37 +75,30 @@ class ariprog {
         result.put(delta, item);
     }
 
-    static void bisquare_process (final int value) {
-
-        DiffRecord      diff = DiffRecord.max;
-
-        for(Bisquare bi : bisquares){
-            final int delta = value - bi.value;
-
-            while (bi.diffs.value < delta) {
-                bi.diffs = DiffRecord.release(bi.diffs);
-            }
-            
-            int     count = 2;
+    static boolean bisquare_process_inner (int prev, final int delta) {
+        for(int j = 2; j < progression_limit; j++){
+            final int pp = prev - delta;
+            if(pp < 0 || !bisq_set.get(pp)) return false;
+            prev = pp;
+        }
 
-            if(bi.diffs.value == delta){
-                count = bi.diffs.count + 1;
+        return true;
+    }
 
-                if(count == progression_limit){
-                    register_new_progression(value, delta); // <--
-                    count--;
-                }
+    static void bisquare_process (final int value) {
+        for(int i = bisqs.size() - 1; i >= progression_limit - 2; i--) {
+            final int   prev = bisqs.get(i);
+            final int   delta = value - prev;
 
-                bi.diffs = DiffRecord.release(bi.diffs);
+            if(bisquare_process_inner(prev, delta)) {
+                register_new_progression(value, delta);
             }
-
-            diff = DiffRecord.alloc(delta, count, diff);
         }
 
-        bisquares.add(new Bisquare(value, diff));
+        bisqs.add(value);
+        bisq_set.set(value);
     }
 
-
     static int bisquare_search(final int limit) {
         class Cell implements Comparable<Cell> {
             public int      x, y;
@@ -253,15 +195,16 @@ class ariprog {
         final int slimit = io.nextIntLine();
         // final int slimit = 5;
 
-        bisquares = new Vector<Bisquare> (80 * slimit * slimit / 100, 1024);
+        bisqs = new Vector<Integer> (80 * slimit * slimit / 100, 1024);
+        bisq_set = new BitSet (2 * slimit * slimit);
 
-        try {
+        // try {
             bisquare_search(slimit);
-        } catch (OutOfMemoryError e) {
-            System.err.println("OutOfMemoryError exception");
-            System.err.printf("DiffRecord allocated: %d\n", DiffRecord.total_alloced);
-            System.exit(1);
-        }
+        // } catch (OutOfMemoryError e) {
+        //     System.err.println("OutOfMemoryError exception");
+        //     // System.err.printf("DiffRecord allocated: %d\n", DiffRecord.total_alloced);
+        //     System.exit(1);
+        // }
 
         if(result.size() > 0){
             Map.Entry<Integer, Vector<Integer>>     entry;
-- 
2.11.4.GIT