I tried to solve the paiza campaign problem "Challenge from Kaito 813"

After solving the problem, I heard that I could get an Amazon gift certificate or meat by lottery, so I tried it. https://paiza.jp/poh/phantom_thief

problem

The treasure location information is written with the x, y coordinates of N treasures in meters, with the location of the phantom thief as 0, 0. It moves in a straight line between each coordinate. Start from the 0,0 position and output the route that steals all the treasure with the shortest possible route.

Way of thinking

If you output the coordinates closest to the origin, output the coordinates closest to that coordinate again, and so on, you can proceed with a short route. I thought, I tried to solve it.

It was written that the answer could be written on a blog, so I posted it below.

Submission code


import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String firstLine = sc.nextLine().replaceAll(" ","");
        int itemCount = Integer.parseInt(firstLine);
        
        ArrayList<Point> pointList = new ArrayList<Point>();
        
        //Create a coordinate list from standard input
        for(int i = 0; i < itemCount ; i++){
            String[] line = sc.nextLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            pointList.add(new Point(x,y));
        }
        
        Point originPoint = new Point(0,0);
        while(pointList.size() > 0){
            int minDistance = Integer.MAX_VALUE;
            Point minDistancePoint = new Point();

            //Get the coordinates closest to the reference point from the coordinate list
            for(Point getPoint : pointList){
                int tmpDistance = getDistance(originPoint,getPoint);
                if(minDistance > tmpDistance){
                    minDistance = tmpDistance;
                    minDistancePoint = getPoint;
                }
            }
            //Display coordinate position
            minDistancePoint.output();
            //Change the reference point
            originPoint = minDistancePoint;
            //Remove coordinates from the coordinate list
            int index = pointList.indexOf(minDistancePoint);
            pointList.remove(index);
        }
    }

    //Find the distance between the coordinates of two points
    public static int getDistance(Point p1, Point p2) {
            double x1 = p1.x;
            double y1 = p1.y;
            double x2 = p2.x;
            double y2 = p2.y;

        double distance = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
        return (int) distance;
    }

}

//Coordinate class
class Point{
    int x;
    int y;
    
    public Point(){
        this.x = 0;
        this.y = 0;
    }
    
    public Point(int x , int y){
        this.x = x;
        this.y = y;
    }
        
    public void output(){
        System.out.println(x + " " + y);
    }
}

result

Here. It seems that it was not the optimal solution. https://paiza.jp/poh/phantom_thief/result/a8a222d8

How to find the optimal solution?

After a little research, [Traveling Salesman Problem](https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E3%82%BB%E3%83%BC%E3 It seems to be a problem called% 83% AB% E3% 82% B9% E3% 83% 9E% E3% 83% B3% E5% 95% 8F% E9% A1% 8C). (Is it a little different because you don't have to go back to the first coordinates?)

The method I solved this time seems to be an algorithm called "greedy method".

Algorithms for solving the traveling salesman problem include the "2-opt method", "hill climbing method", and "simulated annealing method". Using these methods seems to be closer to the optimal solution, but I gave up because it seems difficult.

Recommended Posts

I tried to solve the paiza campaign problem "Challenge from Kaito 813"
I tried to solve the problem of "multi-stage selection" with Ruby
I tried to solve the problem of Google Tech Dev Guide
[Rails] I tried to raise the Rails version from 5.0 to 5.2
I tried to solve the tribonacci sequence problem in Ruby, with recursion.
[Java] I tried to solve Paiza's B rank problem
I tried to solve the tribonatch sequence problem in Ruby (time limit 10 minutes)
I tried the FizzBuzz problem
[Beginner's point of view] I tried to solve the FizzBuzz problem "easily" with Ruby!
I tried upgrading from CentOS 6.5 to CentOS 7 with the upgrade tool
I tried to explain the method
I tried to solve the Ruby karaoke machine problem (there is an example of the answer)
I tried to solve the Ruby bonus drink problem (there is an example of the answer)
I tried to summarize the methods used
I tried to solve AOJ's Binary Search
I tried to solve the Ruby bingo card creation problem (there is an example of the answer)
I tried to implement the Iterator pattern
I tried to summarize the Stream API
I tried to build Ruby 3.0.0 from source
[Ruby] I tried to summarize the methods that frequently appear in paiza
[Ruby] I tried to summarize the methods that frequently appear in paiza ②
I tried to organize the session in Rails
I tried to set tomcat to run the Servlet.
[Java] Try to solve the Fizz Buzz problem
I tried to get the distance from the address string to the nearest station with ruby
[JDBC ③] I tried to input from the main method using placeholders and arguments.
I tried to organize the cases used in programming
[Java] I want to calculate the difference from the date
Tokoro I rewrote in the migration from Wicket 7 to 8
I tried to summarize the state transition of docker
I tried to decorate the simple calendar a little
05. I tried to stub the source of Spring Boot
I tried to reduce the capacity of Spring Boot
I tried to solve AOJ's Small, Large, or Equal
I tried to implement the Euclidean algorithm in Java
I didn't understand the topological sort, so I looked it up and implemented it in BFS, and then tried to solve the AtCoder problem.
I tried to make an application in 3 months from inexperienced
I tried to implement the like function by asynchronous communication
I tried to introduce Bootstrap 4 to the Rails 6 app [for beginners]
I tried to increase the processing speed with spiritual engineering
I tried to collect and solve Ruby's "class" related problems.
I tried to summarize the basics of kotlin and java
[Swift] I tried to implement the function of the vending machine
You can solve the problem by referring to the two articles !!!
I tried to summarize the basic grammar of Ruby briefly
I tried to build the environment little by little using docker
I tried to build the environment of WSL2 + Docker + VSCode
I tried validation to unify the way hashtags are written
I tried the Docker tutorial!
I tried the VueJS tutorial!
Let's solve the FizzBuzz problem!
I tried to verify yum-cron
How to solve the problem that you can not pull image from docker hub with Minikube
I want to solve the N + 1 problem where the data is collated excessively and the operation becomes heavy.
I tried to summarize the words that I often see in docker-compose.yml
[Metal] I tried to figure out the flow until rendering using Metal
[Java] Try to solve the Fizz Buzz problem using recursive processing
I tried to summarize what was asked at the site-java edition-
I tried to illuminate the Christmas tree in a life game
I tried to sort the data in descending order, ascending order / Rails
[Ruby] Tonight, I tried to summarize the loop processing [times, break ...]