From 55748d704df7242b1acedae79c2eea7616eac2a9 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Thu, 10 Dec 2015 08:42:56 +0000
Subject: Faster implementation, test enhancement Practical2

Tester strings are padded nicely.
Implementation uses less memory and is faster with -Ofast.
---
 Practical2/Makefile       |  2 +-
 Practical2/checkout.c     | 31 +++++++++++++++----------------
 Practical2/tester/test.sh |  2 +-
 3 files changed, 17 insertions(+), 18 deletions(-)

(limited to 'Practical2')

diff --git a/Practical2/Makefile b/Practical2/Makefile
index e64a1f7..0b147dd 100644
--- a/Practical2/Makefile
+++ b/Practical2/Makefile
@@ -6,7 +6,7 @@ OBJS=checkout
 all: $(OBJS)
 
 $(OBJS): % : %.c
-	$(CC) -o $@ $<
+	$(CC) -o $@ $< -Ofast 
 
 clean:
 	rm $(OBJS)
diff --git a/Practical2/checkout.c b/Practical2/checkout.c
index 82eda3a..738aa61 100644
--- a/Practical2/checkout.c
+++ b/Practical2/checkout.c
@@ -12,33 +12,32 @@ uint32_t round_ct(uint32_t cents) {
 }
 
 int32_t maximum_profit(uint16_t products[], uint16_t n_products, uint8_t dividers) {
-    uint32_t sums[n_products+1][n_products+1];
-    uint16_t i, j;
-    for (i = 0; i <= n_products; i++) {
-        for (j = 0; j <= n_products; j++) {
-            if (j <= i) {
-                sums[i][j] = 0;
-            } else if (j == 1) {
-                sums[i][j] = products[0];
-            } else {
-                sums[i][j] = sums[i][j-1] + products[j-1];
-            }
-        }
-    }
-
     int32_t profit[n_products+1][dividers+1];
     uint16_t p, d;
     for (p = 0; p <= n_products; p++) {
+        uint32_t sums[p];
+        if (p == 0) {
+            sums[0] = 0;
+        } else {
+            int16_t i;
+            for (i = p-1; i >= 0; i--) {
+                if (i == p-1)
+                    sums[i] = products[i];
+                else
+                    sums[i] = products[i] + sums[i+1];
+            }
+        }
+
         for (d = 0; d <= dividers; d++) {
             if (p == 0) {
                 profit[p][d] = 0;
             } else if (d == 0) {
-                profit[p][d] = sums[0][p] - round_ct(sums[0][p]);
+                profit[p][d] = sums[0] - round_ct(sums[0]);
             } else {
                 int32_t max = profit[p][d-1];
                 uint16_t i;
                 for (i = 0; i < p; i++) {
-                    int32_t try = profit[i][d-1] + sums[i][p] - round_ct(sums[i][p]);
+                    int32_t try = profit[i][d-1] + sums[i] - round_ct(sums[i]);
                     if (try > max)
                         max = try;
                 }
diff --git a/Practical2/tester/test.sh b/Practical2/tester/test.sh
index 9051e97..8f42b77 100755
--- a/Practical2/tester/test.sh
+++ b/Practical2/tester/test.sh
@@ -9,7 +9,7 @@ cd "$dir"
 for tc in "$samples/"*.in; do
     answer=$(cat ${tc/in/out})
     header=$(head -n1 "$tc" | tr -d '\n')
-    echo -n "Running $(basename $tc) $(printf '%-12s' "($answer ")$(printf '%-12s' "/ $header)") ... "
+    echo -n "Running $(printf '%-15s' "$(basename $tc)") $(printf '%-10s' "($answer ")$(printf '%-10s' "/ $header)") ... "
     time_start=$(($(date +%s%N)/1000000))
     result=$(eval "cat '$tc' | $cmd")
     time_end=$(($(date +%s%N)/1000000))
-- 
cgit v1.2.3