Commits

Erik van Zijst committed 08c24f3

NONE: Pi's prime-finding puzzle.

Comments (0)

Files changed (3)

+<?xml version="1.0" encoding="UTF-8"?>
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+    <modelVersion>4.0.0</modelVersion>
+
+    <groupId>primes</groupId>
+    <artifactId>primes</artifactId>
+    <version>1.0</version>
+
+    <dependencies>
+        <dependency>
+            <groupId>com.google.collections</groupId>
+            <artifactId>google-collections</artifactId>
+            <version>1.0</version>
+        </dependency>
+    </dependencies>
+</project>

primes/src/main/java/cx/prutser/primes/OptimusPrime.java

+package cx.prutser.primes;
+
+import com.google.common.collect.HashMultimap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Multimap;
+
+import java.math.BigInteger;
+import java.util.Collection;
+import java.util.Set;
+
+public class OptimusPrime
+{
+    // from: http://primes.utm.edu/lists/small/1000.txt
+    private static final Set<Integer> PRIMES = ImmutableSet.copyOf(
+            PrimeUtil.findPrimes(0, 1000)
+//            11, 13, 17, 19, 23, 29,
+//            31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
+//            73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
+//            127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
+//            179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
+//            233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
+//            283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
+//            353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
+//            419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
+//            467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
+//            547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
+//            607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
+//            661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
+//            739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
+//            811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
+//            877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
+//            947, 953, 967, 971, 977, 983, 991, 997
+    );
+    private final int[] board;
+    private final Multimap<Integer, Prime> dict = HashMultimap.create();
+    private long cycles = 0L;
+
+    public static void main(String[] args) {
+        new OptimusPrime().solve();
+    }
+
+    public OptimusPrime() {
+
+        board = new int[PRIMES.size() + 2];
+
+        // create prime index:
+        for (final Integer prime : PRIMES) {
+            final int prefix = (prime / 100) * 10 + (prime % 100) / 10;
+            dict.put(prefix, new Prime(prime));
+        }
+    }
+
+    public BigInteger solve() {
+
+        final long start = System.currentTimeMillis();
+        final MaxCollector collector = new MaxCollector();
+
+        for (final Prime first : dict.values()) {
+            first.available = false;
+            System.arraycopy(first.digits, 0, board, 0, first.digits.length);
+            solve(3, collector);
+            first.available = true;
+        }
+        final BigInteger optimusPrime = collector.getOptimusPrime();
+        System.out.println("Optimus Prime: " + optimusPrime +
+                " found in " + (System.currentTimeMillis() - start) + "ms (" +
+                cycles + " evaluations)");
+        return optimusPrime;
+    }
+
+    private void solve(final int pos, final SolutionCollector collector) {
+
+        cycles++;
+        final int prefix = board[pos - 2] * 10 + board[pos - 1];
+        final Collection<Prime> candidates = dict.get(prefix);
+
+        boolean terminal = true;
+        for (final Prime candidate : candidates) {
+            if (candidate.available) {
+                board[pos] = candidate.digits[2];   // append the third digit
+                candidate.available = false;
+                solve(pos + 1, collector);
+                candidate.available = true;
+                terminal = false;
+            }
+        }
+        if (terminal) {
+            collector.solution(board, pos);
+        }
+    }
+
+    private class Prime {
+
+        boolean available;
+        final int[] digits = new int[3];
+        private final int prime;    // extra copy for fast equals/hashcode
+
+        private Prime(int prime) {
+            digits[0] = prime / 100;
+            digits[1] = (prime % 100) / 10;
+            digits[2] = prime % 10;
+            this.available = true;
+            this.prime = prime;
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+
+            Prime prime1 = (Prime) o;
+
+            if (prime != prime1.prime) return false;
+
+            return true;
+        }
+
+        @Override
+        public int hashCode() {
+            return prime;
+        }
+
+        @Override
+        public String toString() {
+            return String.valueOf(prime);
+        }
+    }
+
+    private interface SolutionCollector {
+        void solution(final int[] board, final int len);
+    }
+
+    private static class MaxCollector implements SolutionCollector {
+
+        private int[] highest = new int[0];
+
+        public void solution(final int[] board, final int len) {
+
+            if (isHigher(board, len)) {
+                highest = new int[len];
+                System.arraycopy(board, 0, highest, 0, len);
+//                System.out.println("New max: " + getOptimusPrime().toString());
+            }
+        }
+
+        private boolean isHigher(final int[] board, final int len) {
+
+            if (len > highest.length) {
+                return true;
+            } else if (len == highest.length) {
+                for (int i = 0; i < len; i++) {
+                    if (board[i] > highest[i]) {
+                        return true;
+                    } else if (board[i] < highest[i]) {
+                        return false;
+                    }
+                }
+            }
+            return false;
+        }
+
+        public BigInteger getOptimusPrime() {
+            final StringBuilder stringBuilder = new StringBuilder();
+            for (final int digit : highest) {
+                stringBuilder.append(String.valueOf(digit));
+            }
+            return new BigInteger(stringBuilder.toString());
+        }
+    }
+}

primes/src/main/java/cx/prutser/primes/PrimeUtil.java

+package cx.prutser.primes;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class PrimeUtil {
+
+    /**
+     *
+     * @param start number to start with (inclusive).
+     * @param end   exclusive.
+     */
+    public static List<Integer> findPrimes(final int start, final int end) {
+
+        final List<Integer> primes = new ArrayList<Integer>();
+
+        for (int i = start; i < end; i++) {
+
+            // To avoid making too many calculations we can first calculate the
+            // square root of each number and then use that for the division.
+            int i1 = (int) Math.ceil(Math.sqrt(i));
+            boolean isPrimeNumber = false;
+
+            while (i1 > 1) {
+
+                if ((i != i1) && (i % i1 == 0)) {
+                    isPrimeNumber = false;
+                    break;
+                } else if (!isPrimeNumber) {
+                    isPrimeNumber = true;
+                }
+                --i1;
+            }
+
+            if (isPrimeNumber) {
+                primes.add(i);
+            }
+        }
+        return primes;
+    }
+}