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
            }
        }
    }
}

 

[Gammel Gubbe]

Spennende, men fungerer det?

Jeg kjørte det på en online java-greie, og fikk feil svar, 18 i stedet for 15.

Nå er vel mye av problemet her å skjønne logikken i algoritmen. Implementasjonen når logikken er forstått er sekundært.

[quantum]

Blir det bare clauding fra nå av?

Vibe-koding er det nye, store sier de ... 

Det som er bra med AI+koding er jo at man lett ser om man har fått et svar som funker. Med AI'enes hang til å hallusinere fram allverdens svar er det ikke så lett å skille det ene fra det andre i andre disipliner. 

Som man spør får man svar heter det seg. Og så må man ofte gjennom en del "runder" før resultatet er bra. Man vi ha kode som er forståelig, vedlikeholdbar og godt strukturert. Alt dette kan jo AI-kode være, men det er ikke gitt at man får det uten å be om det.