2
\$\begingroup\$

Bessie the cow is in Farmer John's field. The field is of size 0..1,000,000,000 for x and y. Farmer John knows that there are N/2 wormholes at certain coordinates, but he does not know which wormholes are paired. When Bessie enters into a wormhole, she is transported to the wormhole that is paired with it. How many pairings of these wormholes make it so that it is possible for Bessie to get stuck in an infinite cycle?

I have constraints so that this program needs to run in under 1 second. However, it currently runs in about 1.094 seconds.

import java.util.List;
import java.util.Comparator;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.HashSet;

public class wormhole {
public ArrayList<Integer> cycle_count=new ArrayList<Integer>();
public ArrayList<Integer> pair_sequence=new ArrayList<Integer>();
public int iterator=0;
public static int count=0;
Point nextLoc;
Point constant=new Point((int)Math.pow(10, 10),(int)Math.pow(10, 10));
Point nextpoint=new Point(0,0);
public static ArrayList<Integer>original_wormhole_list=new ArrayList<Integer>();
public static void main(String []args) throws IOException
{
    wormhole test=new wormhole();
    BufferedReader f= new BufferedReader(new FileReader("wormhole.in"));
    PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("wormhole.out")));

    int N=Integer.parseInt(f.readLine());

    ArrayList<Integer> wormholes_by_number=new ArrayList<Integer>();
    for(int i=0;i<N;i++)
    {
        wormholes_by_number.add(i);
    }

    ArrayList<Point> wormholes=new ArrayList<Point>();
    for(int i=0;i<N;i++)
    {
        String [] twocoords=f.readLine().split(" ");
        int x=Integer.parseInt(twocoords[0]);
        int y=Integer.parseInt(twocoords[1]);
        wormholes.add(new Point(x,y));
    }
    Point_Compare comparer=test.new Point_Compare();
    Collections.sort(wormholes, comparer);
    original_wormhole_list.addAll(wormholes_by_number);
    ArrayList<Integer> onepairing=new ArrayList<Integer>();
    test.num_infinite_cycles(wormholes_by_number, onepairing, wormholes);
    out.println(count);
    out.close();
}
public void num_infinite_cycles(ArrayList<Integer> list_of_wormholes, ArrayList<Integer> pairing, ArrayList<Point> wormholes) //k starts as 1
{
if(pairing.size()==wormholes.size()) {
    ArrayList<Integer> pair_seq=new ArrayList<Integer>();
    int j=0;
    Point current_coords=new Point(-5,5);
    boolean infinite_cycle_exists=false;
    if(cycle_exists(pairing,wormholes,pair_seq, j, current_coords, infinite_cycle_exists))
    {
        count++;
    }
}

else  {
    for(int k=1;k<list_of_wormholes.size();k++)
    {
        ArrayList<Integer> list_of_wormholes_copy=new ArrayList<Integer>(list_of_wormholes);
        ArrayList<Integer>a=new ArrayList<Integer>(pairing);
        a.add(list_of_wormholes_copy.get(0)); list_of_wormholes_copy.remove(0);
        a.add(list_of_wormholes_copy.get(k-1)); list_of_wormholes_copy.remove(k-1); 

        num_infinite_cycles(list_of_wormholes_copy, a,wormholes);
    }
}
}
//there might be something wrong with infinite_cycle_exists
public boolean cycle_exists(ArrayList<Integer> pairing, ArrayList<Point> wormholes, ArrayList<Integer> pair_seq, int j, Point current_coords, boolean infinite_cycle_exists)
{
    nextpoint.setLocation(move_on(current_coords, wormholes,pairing,j));
    outercircle:
    if(nextpoint.equals(constant) && j%2==0 && infinite_cycle_exists==false) 
    {
        break outercircle;
    }
    else if(pair_seq.size()>=4 && pair_seq.size()%2==0)
    {
        if(contains_repeat(pair_seq))
        {
            infinite_cycle_exists=true;
            break outercircle;
        }
        else 
        {
            ArrayList<Integer> copy_pair_seq=new ArrayList<Integer>(pair_seq);
            copy_pair_seq.add(wormholes.indexOf(nextpoint));
            Point copy_current_coords=new Point(nextpoint);
            int a=j+1;
            return cycle_exists(pairing,wormholes,copy_pair_seq,a,copy_current_coords,infinite_cycle_exists);
        }
    }
    else
    {
        if(j==0)
        {
            j++;
            for(int i=0;i<wormholes.size();i++)
            {
                ArrayList<Integer> copy_pair_seq=new ArrayList<Integer>(pair_seq);
                copy_pair_seq.add(i);
                Point copy_current_coords=new Point(wormholes.get(i));
                boolean exists=cycle_exists(pairing,wormholes,copy_pair_seq,j,copy_current_coords,infinite_cycle_exists);
                if(exists==true || i==wormholes.size()-1)
                {
                    if(exists==true)
                        infinite_cycle_exists=true;
                    break outercircle;
                }
            }
        }
        else
        {
            ArrayList<Integer> copy_pair_seq=new ArrayList<Integer>(pair_seq);
            copy_pair_seq.add(wormholes.indexOf(nextpoint));
            Point copy_current_coords=new Point(nextpoint);
            int a=j+1;
            return cycle_exists(pairing,wormholes,copy_pair_seq,a,copy_current_coords,infinite_cycle_exists);
        }
    }
    return infinite_cycle_exists;
}
public Point move_on(Point current_wormhole, ArrayList<Point> wormholes, ArrayList<Integer> pairing, int j)
{
    if(current_wormhole.equals(new Point(-5,5)))
    {
        return new Point(-5,-5);
    }
    if(j%2==1)
    {
        return paired_wormhole(current_wormhole, wormholes, pairing);
    }
    else
    {
        return next_wormhole_in_row(wormholes, pairing,current_wormhole);
    }
}
public Point paired_wormhole(Point current_wormhole, ArrayList<Point> wormholes, ArrayList<Integer> pairing)
{
    int k=wormholes.indexOf(current_wormhole);
    k=pairing.indexOf(k);
    if(k%2==0)
        return wormholes.get(pairing.get(k+1));
    else
        return wormholes.get(pairing.get(k-1));
}

public Point next_wormhole_in_row(ArrayList<Point> wormholes, ArrayList<Integer> pairing, Point current_coords)
{
    Point closest=new Point((int)Math.pow(10, 10),(int)Math.pow(10, 10)); //if point is this then there is no cycle
    for(int i=0;i<wormholes.size();i++)
    {
        if(current_coords.getY()==wormholes.get(i).getY() && current_coords.getX()<wormholes.get(i).getX()  && closest.getX()>wormholes.get(i).getX())
        {
            closest.setLocation(wormholes.get(i));
        }
    }
    return closest;
}

public boolean contains_repeat(ArrayList<Integer> sequence)
{
    String seq="";
    String regex="(\\d{2,})\\1";
    Pattern p=Pattern.compile(regex);
    for(int i=0;i<sequence.size();i++)
    {
        String a=sequence.get(i).toString();
        seq+=a;
    }
    Matcher matcher = p.matcher(seq);
    boolean repeat=false;
    if(matcher.find())
    {
        repeat=true;
    }
    return repeat;
}
public class Point_Compare implements Comparator<Point>
{
    public int compare(final Point a, final Point b) {
        if (a.x < b.x) {
            return -1;
        }
        else if (a.x > b.x) {
            return 1;
        }
        else {
            return 0;
        }
}
}
public int all_possible_pairings(int a)
{
    int total_pairings=1;
    for(int i=1;i<a;i+=2)
    {
        total_pairings*=i;
    }
    return total_pairings;
}
}

To test the code, just make a text file called "wormhole.in" The text file should contain the following with no spaces after the last number on each line, and one space between numbers on the same line. For example, "12" should have no space. 636437309 and 704270751 should only have a space between them.

12
636437309 704270751
695056713 700147825
636437309 356396548
921201220 589666013
430411607 671693685
324259336 671693685
723442153 589666013
528904109 419799944
921201220 356396548
723442153 856537355
691516566 726853849
941903572 634527403

\$\endgroup\$
  • \$\begingroup\$ This looks like USACO 2013 Problem 3. \$\endgroup\$ – 200_success Jun 21 '16 at 22:00
  • 1
    \$\begingroup\$ Java does not do tail call optimization. \$\endgroup\$ – 200_success Jun 21 '16 at 22:00
  • \$\begingroup\$ It is part of the USACO training page \$\endgroup\$ – HSCoder Jun 21 '16 at 23:52
  • 1
    \$\begingroup\$ What method should I call to test the code? You might want to look into unit testing so its easier for reviewers to see the code works correctly before and after their suggestions \$\endgroup\$ – Ferrybig Jun 23 '16 at 15:26
  • \$\begingroup\$ @Ferrybig you can test the code now. After running the program, a file called wormhole.out will be created which will contain the answer. The right answer in this case is 2835 \$\endgroup\$ – HSCoder Jun 23 '16 at 18:16
3
\$\begingroup\$

Let's just start at the top. I'll do some basic things that you should have done before posting here. Because they are basic courtesy to the reader. After that, when I still have some energy left I actually may review your code.

Basic Conventions & Cleanliness:

  • Classnames should be PascalCase. wormhole should be Wormhole
  • Unused fields and Variables as well as Imports and Methods should be removed. That already nukes the imports for List, Set and HashSet. It also nukes cycle_count, pair_sequence as well as iterator. Also all_possible_pairings is never used, that also eliminates nextLoc
  • Methods, Variables, Fields and basically everything in Java is conventionally named in camelCase. This is not python, all these underscores are unexpected and "surprising" to read in java code and thus lead to mental strain. Respect the conventions of the language you write in. (It also looks significantly better to combine that with library methods)
  • Respect standard formatting conventions. Indent class bodies by one level. Add a space around binary operators. Cramming everything into the least space possible is straining the mind unnecessarily.
  • Reduce visibility where possible. All those public fields can be private, the same goes for all the methods you got there (unless you're unit-testing them, which I doubt, judging by the comment //there might be something wrong with infinite_cycle_exists...)

Language opportunities:

Java has Generics inference on the right side of the assignment. Also you should program against interfaces. All your collection instantiations should look similar to: Interface<Type> name = new Implementation<>();.

Additional notes:

  • My IDE flags original_wormhole_list because it's only written to, but never queried.
  • It also flags the parameter pairing in next_wormhole_in_row as unused.
  • Boolean comparisons like exists == true can be simplified to exists because that's already a boolean. infinite_cycle_exists == false becomes !infinite_cycle_exists.
  • While we're at infinite_cycle_exists. The invocation of cycle_exists in num_infinite_cycles is flagged, because infinite_cycle_exists is always false there. You can inline that invocation

Simplification Refactorings:

Avoid global state. static int counter is a code-smell, because you're making your program extremely brittle. Declare variables as close as possible to their usage and pull global state into scopes so it's more manageable. So is a static original_wormhole_list.

Make Point_Comparator static to avoid having to instantiate it on your test instance. Also you should inline the usage in your Collections.sort call. It's bad practice to leave variables lieing about, because it increases contextual load when reading code.

After those basic refactorings your code looks like the following:

import java.awt.*;
import java.io.*;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Wormhole {
    private Point constant = new Point((int) Math.pow(10, 10), (int) Math.pow(10, 10));
    private Point nextpoint = new Point(0, 0);

    public static void main(String[] args) throws IOException {
        Wormhole test = new Wormhole();
        BufferedReader f = new BufferedReader(new FileReader("wormhole.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("wormhole.out")));

        int N = Integer.parseInt(f.readLine());

        List<Integer> wormholes_by_number = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            wormholes_by_number.add(i);
        }

        List<Point> wormholes = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String[] twocoords = f.readLine().split(" ");
            int x = Integer.parseInt(twocoords[0]);
            int y = Integer.parseInt(twocoords[1]);
            wormholes.add(new Point(x, y));
        }
        Collections.sort(wormholes, new PointComparator());
        List<Integer> onepairing = new ArrayList<>();
        int count = test.numInfiniteCycles(wormholes_by_number, onepairing, wormholes);
        out.println(count);
        out.close();
    }

    public int numInfiniteCycles(List<Integer> list_of_wormholes, List<Integer> pairing, List<Point> wormholes) //k starts as 1
    {
        int count = 0;
        if (pairing.size() == wormholes.size()) {
            List<Integer> pair_seq = new ArrayList<>();
            int j = 0;
            Point current_coords = new Point(-5, 5);
            if (cycleExists(pairing, wormholes, pair_seq, j, current_coords, false)) {
                count++;
            }
        } else {
            for (int k = 1; k < list_of_wormholes.size(); k++) {
                List<Integer> list_of_wormholes_copy = new ArrayList<>(list_of_wormholes);
                List<Integer> a = new ArrayList<>(pairing);
                a.add(list_of_wormholes_copy.get(0));
                list_of_wormholes_copy.remove(0);
                a.add(list_of_wormholes_copy.get(k - 1));
                list_of_wormholes_copy.remove(k - 1);

                count += numInfiniteCycles(list_of_wormholes_copy, a, wormholes);
            }
        }
        return count;
    }

    //there might be something wrong with infinite_cycle_exists
    public boolean cycleExists(List<Integer> pairing, List<Point> wormholes, List<Integer> pair_seq, int j, Point current_coords, boolean infinite_cycle_exists) {
        nextpoint.setLocation(moveOn(current_coords, wormholes, pairing, j));
        outercircle:
        if (nextpoint.equals(constant) && j % 2 == 0 && !infinite_cycle_exists) {
            break outercircle;
        } else if (pair_seq.size() >= 4 && pair_seq.size() % 2 == 0) {
            if (containsRepeat(pair_seq)) {
                infinite_cycle_exists = true;
                break outercircle;
            } else {
                List<Integer> copy_pair_seq = new ArrayList<>(pair_seq);
                copy_pair_seq.add(wormholes.indexOf(nextpoint));
                Point copy_current_coords = new Point(nextpoint);
                int a = j + 1;
                return cycleExists(pairing, wormholes, copy_pair_seq, a, copy_current_coords, infinite_cycle_exists);
            }
        } else {
            if (j == 0) {
                j++;
                for (int i = 0; i < wormholes.size(); i++) {
                    List<Integer> copy_pair_seq = new ArrayList<>(pair_seq);
                    copy_pair_seq.add(i);
                    Point copy_current_coords = new Point(wormholes.get(i));
                    boolean exists = cycleExists(pairing, wormholes, copy_pair_seq, j, copy_current_coords, infinite_cycle_exists);
                    if (exists || i == wormholes.size() - 1) {
                        if (exists)
                            infinite_cycle_exists = true;
                        break outercircle;
                    }
                }
            } else {
                List<Integer> copy_pair_seq = new ArrayList<>(pair_seq);
                copy_pair_seq.add(wormholes.indexOf(nextpoint));
                Point copy_current_coords = new Point(nextpoint);
                int a = j + 1;
                return cycleExists(pairing, wormholes, copy_pair_seq, a, copy_current_coords, infinite_cycle_exists);
            }
        }
        return infinite_cycle_exists;
    }

    public Point moveOn(Point current_wormhole, List<Point> wormholes, List<Integer> pairing, int j) {
        if (current_wormhole.equals(new Point(-5, 5))) {
            return new Point(-5, -5);
        }
        if (j % 2 == 1) {
            return pairedWormhole(current_wormhole, wormholes, pairing);
        } else {
            return nextWormholeInRow(wormholes, current_wormhole);
        }
    }

    public Point pairedWormhole(Point current_wormhole, List<Point> wormholes, List<Integer> pairing) {
        int k = wormholes.indexOf(current_wormhole);
        k = pairing.indexOf(k);
        if (k % 2 == 0)
            return wormholes.get(pairing.get(k + 1));
        else
            return wormholes.get(pairing.get(k - 1));
    }

    public Point nextWormholeInRow(List<Point> wormholes, Point current_coords) {
        Point closest = new Point((int) Math.pow(10, 10), (int) Math.pow(10, 10)); //if point is this then there is no cycle
        for (int i = 0; i < wormholes.size(); i++) {
            if (current_coords.getY() == wormholes.get(i).getY() && current_coords.getX() < wormholes.get(i).getX() && closest.getX() > wormholes.get(i).getX()) {
                closest.setLocation(wormholes.get(i));
            }
        }
        return closest;
    }

    public boolean containsRepeat(List<Integer> sequence) {
        String seq = "";
        String regex = "(\\d{2,})\\1";
        Pattern p = Pattern.compile(regex);
        for (int i = 0; i < sequence.size(); i++) {
            String a = sequence.get(i).toString();
            seq += a;
        }
        Matcher matcher = p.matcher(seq);
        boolean repeat = false;
        if (matcher.find()) {
            repeat = true;
        }
        return repeat;
    }

    private static class PointComparator implements Comparator<Point> {
        public int compare(final Point a, final Point b) {
            if (a.x < b.x) {
                return -1;
            } else if (a.x > b.x) {
                return 1;
            } else {
                return 0;
            }
        }
    }
}

And I haven't even started looking at how the code works...

\$\endgroup\$
  • \$\begingroup\$ I changed my cycle_exists method so that it is now iterative. The program now runs in .866 seconds for the input I specified but for another input that I also need to pass, it takes 1.6 seconds. Do you have any idea how I can make my num_infinite_cycles method iterative without making it complicated? Or should I do something else? \$\endgroup\$ – HSCoder Jun 24 '16 at 12:49

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.