Claude.ai kan parallellisere algoritmer, spesielt kan den parallellisere algoritmer i Java

[lania]

Ba claude.ai løse 'S No Problem – Kattis, Kattis problemet, selv om det finnes løsninger - der ute - på de fleste kattis oppgaver.

Det en kan regne med, på tross, er at det er få som har giddet å parallellisere alle sammen; ba derfor claude.ai å CLAUDE  parallelliseringen til denne løsningen claude.ai kom opp med.

Det ser ut som at det er vel R.I.P at en manuelt parallelliserer noe? Blir det bare clauding fra nå av?

Uansett, fikk følgende resultat fra claude:

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

public class SnowClearingOptimization {
    
    static class Edge {
        int to;
        int length;
        
        Edge(int to, int length) {
            this.to = to;
            this.length = length;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt(); // Number of buildings
        
        // Create adjacency list for the tree
        List<List<Edge>> graph = Collections.synchronizedList(new ArrayList<>(n + 1));
        for (int i = 0; i <= n; i++) {
            graph.add(Collections.synchronizedList(new ArrayList<>()));
        }
        
        // Read edges (sidewalks) and build graph
        // Use parallel streams for larger inputs
        AtomicInteger totalLength = new AtomicInteger(0);
        
        // Read input sequentially since Scanner is not thread-safe
        int[][] edges = new int[n-1][3];
        for (int i = 0; i < n - 1; i++) {
            edges[i][0] = scanner.nextInt(); // a
            edges[i][1] = scanner.nextInt(); // b
            edges[i][2] = scanner.nextInt(); // d
        }
        
        // Parallelize graph construction
        ForkJoinPool customThreadPool = new ForkJoinPool(
            Runtime.getRuntime().availableProcessors()
        );
        
        try {
            customThreadPool.submit(() -> 
                Arrays.stream(edges).parallel().forEach(edge -> {
                    int a = edge[0];
                    int b = edge[1];
                    int d = edge[2];
                    
                    graph.get(a).add(new Edge(b, d));
                    graph.get(b).add(new Edge(a, d));
                    totalLength.addAndGet(d);
                })
            ).get(); // Wait for completion
        } catch (Exception e) {
            e.printStackTrace();
        }
        
        // Find the diameter of the tree (longest path)
        // Step 1: Find the farthest node from any arbitrary node (e.g., node 1)
        ConcurrentHashMap<Integer, Integer> distances1 = new ConcurrentHashMap<>();
        for (int i = 1; i <= n; i++) {
            distances1.put(i, -1);
        }
        distances1.put(1, 0);
        int farthestNode = parallelBfs(graph, 1, distances1, n);
        
        // Step 2: Find the farthest node from the previously found farthest node
        ConcurrentHashMap<Integer, Integer> distances2 = new ConcurrentHashMap<>();
        for (int i = 1; i <= n; i++) {
            distances2.put(i, -1);
        }
        distances2.put(farthestNode, 0);
        int otherEnd = parallelBfs(graph, farthestNode, distances2, n);
        
        // The diameter is the distance between these two nodes
        int diameter = distances2.get(otherEnd);
        
        // For two snow blowers, the optimal solution is to clear all edges
        // The minimum total distance is 2 * (total length of all sidewalks) - (diameter)
        int minTotalDistance = 2 * totalLength.get() - diameter;
        
        System.out.println(minTotalDistance);
    }
    
    // Parallel BFS to find the farthest node and compute distances
    private static int parallelBfs(List<List<Edge>> graph, int start, ConcurrentHashMap<Integer, Integer> distance, int n) {
        ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();
        queue.add(start);
        
        AtomicInteger farthestNode = new AtomicInteger(start);
        AtomicInteger maxDistance = new AtomicInteger(0);
        
        // Process BFS levels in parallel when possible
        while (!queue.isEmpty()) {
            // Process current level
            List<Integer> currentLevel = new ArrayList<>();
            Integer node;
            while ((node = queue.poll()) != null) {
                currentLevel.add(node);
            }
            
            if (currentLevel.isEmpty()) {
                break;
            }
            
            // Process nodes in current level in parallel
            CountDownLatch latch = new CountDownLatch(currentLevel.size());
            
            for (Integer current : currentLevel) {
                CompletableFuture.runAsync(() -> {
                    try {
                        int currentDistance = distance.get(current);
                        
                        for (Edge edge : graph.get(current)) {
                            if (distance.getOrDefault(edge.to, -1) == -1) {
                                int newDistance = currentDistance + edge.length;
                                distance.put(edge.to, newDistance);
                                queue.add(edge.to);
                                
                                // Update farthest node if needed
                                updateFarthestNode(farthestNode, maxDistance, edge.to, newDistance);
                            }
                        }
                    } finally {
                        latch.countDown();
                    }
                });
            }
            
            try {
                latch.await(); // Wait for all nodes at this level to be processed
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
        
        return farthestNode.get();
    }
    
    private static void updateFarthestNode(AtomicInteger farthestNode, AtomicInteger maxDistance, 
                                          int nodeId, int distance) {
        boolean updated = false;
        while (!updated) {
            int currentMax = maxDistance.get();
            if (distance > currentMax) {
                updated = maxDistance.compareAndSet(currentMax, distance);
                if (updated) {
                    farthestNode.set(nodeId);
                }
            } else {
                updated = true; // No update needed
            }
        }
    }
}