7
\$\begingroup\$

I need to create a circle with numbers from 1 to n , however it is necessary to respect some rules:

  1. All numbers from 1 to n are used in the circle only once.
  2. The sum of two consecutive numbers is a prime number
  3. The sum of a number with what is diametrically opposite it is also a prime number

So I need to create an algorithm that receives an integer n and determines whether there is a circle of size n, if it exists.

For example:

enter image description here

Program response: 1 6 7 16 15 8 5 12 11 18 13 10 3 4 9 14 17 2

I managed to get the expected result, but I do not know if I made the faster way, or if there is something badly written.

import java.sql.Date;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Vector;

import javax.swing.JOptionPane;

public class QuintoDesafio {

    private static int j;
    private static int k;

    private static Vector primes  = new Vector();

    public static void main(String[] args) 
    { 

        long start = System.currentTimeMillis();  

        ArrayList list = new ArrayList();

        primes.add( new Integer( 2 ) );
        primes.add( new Integer( 3 ) );
        primes.add( new Integer( 5 ) );
        primes.add( new Integer( 7 ) );
        primes.add( new Integer( 11 ) );
        primes.add( new Integer( 13 ) );
        primes.add( new Integer( 17 ) );
        primes.add( new Integer( 19 ) );
        primes.add( new Integer( 23 ) );
        primes.add( new Integer( 31 ) );
        primes.add( new Integer( 37 ) );
        primes.add( new Integer( 41 ) );

        String n = JOptionPane.showInputDialog( "Input n (even) ");
        int ene = Integer.parseInt( n );

        for ( int i=1; i <= ene; i++ ) {
            list.add( new Integer(i) );
        }
        exchange(list, 0);

        long end  = System.currentTimeMillis();   
        System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(end - start)));  
    }

    static void exchange(ArrayList arr, int k){
        boolean passed = true; 

        for(int i = k; i < arr.size(); i++){
            java.util.Collections.swap(arr, i, k);
            exchange(arr, k+1);
            java.util.Collections.swap(arr, k, i);
        }
        if (k == arr.size() -1){
            int half = arr.size()/2;

            for ( int j=0; j<arr.size(); j++ ) {
                int one = (int) arr.get(j);
                int two;
                if ( j+1 == arr.size() ) {
                    two = (int) arr.get(0);
                } else {
                    two = (int) arr.get(j+1);
                }
                Integer number_test = new Integer( one+two );
                if ( !primes.contains( number_test )) {
                    passed = false;
                }
            }

            for ( int j=0; j<half; j++ ) {
                int one = (int) arr.get(j);
                int two = (int) arr.get(j+half);
                Integer number_test = new Integer( one+two );
                if ( !primes.contains( number_test )) {
                    passed = false;
                }
            }
            if ( passed ) {
                System.out.println(java.util.Arrays.toString(arr.toArray()));
            }
        }
    }
}
```
\$\endgroup\$
  • \$\begingroup\$ What geito means? \$\endgroup\$ – user255572 Jun 10 at 22:31
  • \$\begingroup\$ For me it looks like you are brute forcing meaning iterating all possible lists and checking whether they fit your conditions. It is slowest way to solve any problem. I don't know solution, but you could be looking in dynamic programming where you create sets of pairs and then try to combine them or graph search algorithms, where you find a path of numbers with fit conditions. \$\endgroup\$ – user255572 Jun 10 at 22:39
  • 2
    \$\begingroup\$ By the way I get a lexicographically earlier result [1, 2, 5, 8, 9, 10, 7, 6, 11, 12, 17, 14, 15, 4, 3, 16, 13, 18], perhaps because you are missing the prime 29 \$\endgroup\$ – harold Jun 10 at 23:36
  • 1
    \$\begingroup\$ An observation about the problem rather than your solution. There can be no such circle if n is a multiple of 4. This is because opposite numbers would be both even or both odd. Such quick tests are often worth putting in before trying to exhaust possibilities expensively. \$\endgroup\$ – Josiah Jun 11 at 8:40
8
\$\begingroup\$

First, Vector shouldn't be used here. It's essentially a synchronized ArrayList, and you don't need any synchronization in this case. Just change it to an ArrayList.

This has the potential to be a little faster.


Second, you're using a raw ArrayList which isn't typesafe:

list.add("Some nonsense"); // Doesn't cause an error

and is necessitating your (int) type-casts later on. Specify that the list is holding integers using generics, and it will be typesafe. Read the < > as "of" here:

// Note how we specify what the list can hold
// An ArrayList of Integers
ArrayList<Integer> list = new ArrayList<>();

list.add("Some nonsense") // This causes an error now at compile time

You're also doing odd stuff with the Integer constructor. You don't need to manually cast unboxed integers like Integer(2). 2 will be "auto-boxed" into its object wrapper as necessary implicitly.


You're calling Integer/parseInt outside of a try; which is risky. If the user enters bad input, your whole program with crash. Wrap it up and handle failure (yes, users will enter bad input):

try {
    int ene = Integer.parseInt(n);
    // Code using "ene"

} catch (NumberFormatException e) {
    // Just an example. You'll need to do something more involved, like re-asking for input
    System.out.println("Parse failed");
}

Just as an example of what I mentioned earlier:

static void exchange(ArrayList arr, int k){
    ...
    int one = (int) arr.get(j);
    int two = (int) arr.get(j + half);
    Integer number_test = new Integer(one + two);

Make the parameter generic, and do away with the casts and boxing. Just write:

static void exchange(ArrayList<Integer> arr, int k){
    ...
    int one = arr.get(j);
    int two = arr.get(j + half);
    int number_test = one + two;

And then similarly below that.


Also, Java prefers camelCase, not snake_case. It's best to stick to the conventions of the language you're using.


import java.sql.Date;

is a little worrying. You shouldn't really be raiding a SQL library just to make use of some date object. Java has a java.time package for this purpose.


Just as a tip,

int two;
if (j + 1 == arr.size()) {
    two = arr.get(0);

} else {
    two = arr.get(j + 1);
}

Can also be written as:

int two = j + 1 == arr.size() ? arr.get(0) : arr.get(j + 1);

or, alternatively:

int two = arr.get(j + 1 == arr.size() ? 0 : j + 1);

Depending on how much duplication you can tolerate. The ? : part is known as the "ternary operator"/a "conditional expression".


if (!primes.contains(number_test)) {

This is quite expensive when done on a List like an ArrayList. If you need to use contains, you should probably be using a Set like a HashSet. Membership lookups are much faster using sets. The time difference will become increasingly noticeable as primes grows.

\$\endgroup\$
  • \$\begingroup\$ int two = arr.get(j + 1 == arr.size() ? 0 : j + 1); is complex enough that I'd probably break that up into int wrapped_idx = (j + 1 == arr.size()) ? 0 : j + 1; and int two = arr.get(wrapped_idx);. Or peel that last iteration so I don't need a hand-rolled modulo inside the loop. Or walk 2 pointers / indices, like j2 = j1; j1++; So you can start with j2=arr.size()-1; and j1=0; and don't need to do any wrap-checking inside the loop but also don't need to manually peel an iteration of the loop body. \$\endgroup\$ – Peter Cordes Jun 11 at 16:01
6
\$\begingroup\$

Your algorithm, if I understand it correctly, is to recursively enumerate all permutations and then check every one of them until a solution is found. There is a very simple improvement to that which can skip huge chunks of the search space: try to detect violations of the constraints as early as possible.

For example, if the current permutation starts with "1, 3, .." and we are in the process of calling exchange recursively to create the "tails" of these permutations, then all work done by these recursive calls will ultimately be useless. At this point it is unavoidable that the "1, 3" pair will violate the second constraint no matter what the rest of the permutation will be. If this situation was detected, we could return straight away and continue with "1, 4, ..". It should be possible to adapt your current check to work on a partial configuration, and use it to prune in this way.

To give a sense of the impact, with this pruning and nothing especially clever, my code takes 0.06s on ideone for that circle of 18 elements.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.