We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
For something different, here's a manythread solution for Java 15. This aims to perform a simultaneous N-way search for the portkey, given N processors. Note it may have some latent nondeterminism.
classResult{/* * Find path to a portkey square, while counting the number of * decision points (we'll call them "junctions") * * Note: Take care to define "junction" appropriately for the * terminal points. Internally, uses Cartesian coordinates (x, y) * to represent the matrix. * * As a learning experiment, implemented as a 'parallelized' * search, so each ⨁-way DFS may occur at once. * * 𝚯(log N) in theory, given unlimited processors and span efficiency. * Otherwise, 𝚯(|V| + |E|) runtime, that is 𝚯(N + 4N) or 𝚯(N), * where N = number of matrix cells (N = length * width). * * 𝚯(N) space complexity for the overall search. */publicstaticStringcountLuck(List<String>matrix,intk){longjunctions=findPath(graphOf(matrix)).parallelStream().filter(Cell::isJunction).count();if(k==junctions){return"Impressed";}return"Oops!";}/* Create an undirected graph of the matrix, with open cells only. * Note final cells are unblocked (open), but not necessarily reachable.*/privatestaticMap<Point,Cell>graphOf(List<String>matrix){finalintx=matrix.get(0).length();finalinty=matrix.size();returnCell.matrixOf(x,y).parallel().filter(p->Cell.isOpen(p,matrix)).collect(toConcurrentMap(p->p,p->newCell(p,matrix)));}/* Initial recursive depth-first search (DFS) for the "port key" * Thread-safe only as used here. */privatestaticList<Cell>findPath(Map<Point,Cell>graph){returnfindPath(Cell.start,graph,newHashSet<>());}/* Search for goal in graph, then return the successful path */privatestaticList<Cell>findPath(Pointcurrent,Map<Point,Cell>graph,Set<Point>visited){if(current.equals(Cell.goal)){returnnewArrayList<>(List.of(graph.get(current)));}visited.add(current);Optional<List<Cell>>path=graph.get(current).neighbors.stream().parallel().filter(not(visited::contains)).map(p->findPath(p,graph,visited)).filter(not(List::isEmpty)).findFirst();path.ifPresent(p->p.add(0,graph.get(current)));returnpath.orElse(List.of());}}/* Cell of a matrix, with neighbors in cardinal aspect (N, S, E, W).*/classCell{finalSet<Point>neighbors;privatefinalPointposition;privatefinalintwidth,height;staticPointgoal,start;Cell(Pointp,List<String>matrix){this.position=p;this.width=matrix.get(0).length();this.height=matrix.size();neighbors=neighborsOf().filter(n->isOpen(n,matrix)).collect(toSet());}/* A "junction" is any cell with more than one option, in a viable * path to the goal. The goal itself is never a junction. */publicbooleanisJunction(){if(position.equals(goal)){returnfalse;}elseif(position.equals(start)){returnneighbors.size()>1;}returnneighbors.size()>2;}/* Translate a matrix into Cartesian points for consistency */publicstaticStream<Point>matrixOf(intwidth,intheight){returnIntStream.range(0,height).mapToObj(y->IntStream.range(0,width).mapToObj(x->newPoint(x,y))).flatMap(p->p);}/* Check if a given point of the matrix is unblocked, aka open. */staticpublicbooleanisOpen(Pointp,finalList<String>matrix){finalcharblocked='X';finalchargoal='*';finalcharstart='M';charterrain=matrix.get(p.y).charAt(p.x);if(terrain==goal){Cell.goal=p;}elseif(terrain==start){Cell.start=p;}return(terrain!=blocked);}/* Show all valid positions reachable from this Cell */privateStream<Point>neighborsOf(){returnDirection.all().parallel().map(this::pointOf).filter(this::isValid);}
Count Luck
You are viewing a single comment's thread. Return to all comments →
For something different, here's a manythread solution for Java 15. This aims to perform a simultaneous N-way search for the portkey, given N processors. Note it may have some latent nondeterminism.
Complete file: https://github.com/profinite/HackerRank/blob/main/Algorithms/Search/CountLuck/Solution.java