|
import java.util.ArrayDeque; |
|
import java.util.ArrayList; |
|
import java.util.Deque; |
|
import java.util.HashSet; |
|
import java.util.List; |
|
import java.util.Objects; |
|
import java.util.Set; |
|
|
|
import static java.util.Arrays.asList; |
|
|
|
/** |
|
* It's back-to-school time! |
|
* <p> |
|
* In order to buy supplies for your kids, you have to go to 4 different types of shop: |
|
* <ul> |
|
* <li>a bookshop to buy a workbook,</li> |
|
* <li>a school shop to buy some glue,</li> |
|
* <li>a sport store to buy a pair of sneakers,</li> |
|
* <li>a stationery store to buy a pencil.</li> |
|
* </ul> |
|
* Shopping for school isn't a fun hobby for you, so you started to search for the shortest path. |
|
* Then you realized your town has many shops of these types, and it may take too long |
|
* to evaluate all the paths one by one. |
|
* <p> |
|
* So, before searching for the best path, you just want to count them. |
|
* <p> |
|
* The type of shop is encoded in an integer from 0 to 3. |
|
* The 0 is bookshop, type 1 is school shop, type 2 is sport store, type 3 is stationery. |
|
* <p> |
|
* As input, you get a description of your town in the following form : |
|
* <ul> |
|
* <li>{@code shops}: a list of integers, telling the shop types. For example {@code [2, 3, 1, 1, 0]} |
|
* means the shop at index 0 is a sport store, the shop at index 1 is a stationery store, the shops |
|
* at index 2 and 3 are school shops, etc.</li> |
|
* <li>{@code roads}: a list of a couple of 2 integers, showing the roads between shops. For |
|
* example {@code [[0, 1], [0, 3]]} means there is a road between the shop of index 0 and the shop |
|
* of index 1, then another road between the shop of index 0 and the shop index 3.</li> |
|
* </ul> |
|
* |
|
* <b>All roads are bi-directional. There is at most 1 road between 2 shops.</b> So you will never |
|
* have {@code [[2, 5], [5, 2]]}. |
|
* <p> |
|
* You must return the number of valid paths. |
|
* A valid path visits exactly one shop of each type, in any order, by using the available roads. |
|
* <p> |
|
* Visiting the same 4 shops in two different orders counts as two valid paths. |
|
* <p> |
|
* <b>There are a maximum of 50 shops and 250 roads.</b> |
|
* <p> |
|
* <h2>Example</h2> |
|
* With these inputs: |
|
* <br> |
|
* {@code shops = [1, 0, 3, 2, 2]} |
|
* <br> |
|
* {@code roads = [[0, 1], [1, 2], [1, 4], [2, 3], [2, 4]]} |
|
* <br> |
|
* The town looks like this: |
|
* <ul> |
|
* <li>1 -> 0</li> |
|
* <li>0 -> 3</li> |
|
* <li>3 -> 2</li> |
|
* <li>2 -> 0</li> |
|
* </ul> |
|
* The valid paths are below; each list contains the 4 shop indexes to visit:<br> |
|
* {@code [0, 1, 2, 3]}<br> |
|
* {@code [0, 1, 2, 4]}<br> |
|
* {@code [0, 1, 4, 2]}<br> |
|
* {@code [3, 2, 1, 0]}<br> |
|
* {@code [4, 2, 1, 0]}<br> |
|
* {@code [2, 4, 1, 0]} |
|
* <p> |
|
* As there are 6 solutions, your code must output 6. |
|
*/ |
|
public class BackToSchool { |
|
private static final boolean DEBUG = false; |
|
|
|
/** |
|
* @param shops The type of each shop, ordered according to their indexes. |
|
* @param roads The roads between shops. Each element is a couple of two integers. |
|
* @return the number of paths that visits one shop of each type. |
|
*/ |
|
public static int countPaths(List<Integer> shops, List<List<Integer>> roads) { |
|
final List<Path[]> paths = new ArrayList<>(); |
|
|
|
for (int idx = 0; idx < roads.size(); idx++) { |
|
// build a path |
|
traverse(idx, roads, shops, paths); |
|
} |
|
|
|
return paths.size() * 2; // two-ways |
|
} |
|
|
|
/** |
|
* Traverses the graph of roads and shops, and finds all valid routes that visit all the shops. |
|
* |
|
* @param start The starting index of the roads list. |
|
* @param roads A list of lists, where each inner list represents a road with two vertex indices. |
|
* @param shops A list of shop. |
|
* @param routes A list to store the valid routes as arrays of vertex. |
|
*/ |
|
private static void traverse(int start, final List<List<Integer>> roads, final List<Integer> shops, final List<Path[]> routes) { |
|
Deque<Path> stack = new ArrayDeque<>(); |
|
stack.push(Path.of(roads.get(start).get(0), roads.get(start).get(1))); |
|
|
|
while (!stack.isEmpty()) { |
|
Path current = stack.pop(); // a starting point to create a route that allows you to visit all the shops. |
|
|
|
for (int idx = start + 1; idx < roads.size(); idx++) { // try with neighbors |
|
Path fromChain = current; |
|
if (stack.size() == 1) { // peek the path to compare (from, to) |
|
fromChain = stack.peek(); |
|
} |
|
Path toChain = Path.of(roads.get(idx).get(0), roads.get(idx).get(1)); |
|
if (fromChain.value.equals(toChain.key) || (fromChain.value.equals(toChain.value))) { // can build a chain |
|
stack.addLast(toChain); |
|
} |
|
|
|
if (stack.size() == 2 && isValidChain(shops, current, stack.getFirst(), stack.getLast())) { // Can we create a route? |
|
Path[] route = new Path[]{current, stack.getFirst(), stack.getLast()}; |
|
if (DEBUG) { |
|
debugRoute(route); |
|
debugRoute(stack.getLast(), stack.getFirst(), current); |
|
} |
|
routes.add(route); |
|
stack.removeLast(); |
|
} |
|
} |
|
|
|
stack.addFirst(current); // restore starting point |
|
stack.removeLast(); // remove the last point to proceed with the next points. |
|
start++; |
|
} |
|
} |
|
|
|
/** |
|
* Checks if a given chain of paths is a valid route that visits all the shops. |
|
* |
|
* @param shops The list of shop indices. |
|
* @param chain The chain of paths to be validated. |
|
* @return True if the chain is a valid route, false otherwise. |
|
*/ |
|
private static boolean isValidChain(List<Integer> shops, Path... chain) { |
|
if (chain.length == 0) { |
|
return false; |
|
} |
|
|
|
int idx = 1; |
|
Set<Integer> visited = new HashSet<>(); |
|
Path lastPath = chain[0]; |
|
visited.add(shops.get(lastPath.key)); |
|
while (idx < chain.length) { |
|
Path path = chain[idx]; |
|
if (!path.key.equals(lastPath.value) && !path.value.equals(lastPath.value)) { // bi-directional |
|
return false; |
|
} |
|
visited.add(shops.get(path.key)); |
|
visited.add(shops.get(path.value)); |
|
lastPath = path; |
|
|
|
idx++; |
|
} |
|
return visited.size() == 4; |
|
} |
|
|
|
/** |
|
* Prints a debug message for a given route. |
|
* |
|
* @param paths The array of paths that represent the route. |
|
*/ |
|
private static void debugRoute(Path... paths) { |
|
if (paths.length != 3) { |
|
return; |
|
} |
|
|
|
System.out.println("--------------Route--------------"); |
|
|
|
Path lastPath = paths[0]; |
|
System.out.printf("(%d, %d)", lastPath.key, lastPath.value); |
|
for (int idx = 1; idx < paths.length; idx++) { |
|
if (lastPath.value.equals(paths[idx].key)) { |
|
System.out.printf(" (%d, %d)", paths[idx].key, paths[idx].value); |
|
} else { |
|
System.out.printf(" (%d, %d)", paths[idx].value, paths[idx].key); |
|
} |
|
lastPath = paths[idx]; |
|
} |
|
System.out.printf("%n"); |
|
} |
|
|
|
public static void main(String[] args) { |
|
System.out.println("Input = shops: [1, 0, 3, 2, 2], roads : [[0, 1], [1, 2], [1, 4], [2, 3], [2, 4]]"); |
|
System.out.printf("Output = %d%n", countPaths(asList(1, 0, 3, 2, 2), asList(asList(0, 1), asList(1, 2), asList(1, 4), asList(2, 3), asList(2, 4)))); |
|
System.out.println("----------------------"); |
|
} |
|
|
|
|
|
/** |
|
* A generic utility class that represents a key-value pair. |
|
* It provides a way to associate two objects of potentially different types |
|
* and carry them around as a single unit. |
|
* |
|
* @param <T> The type of the key object. |
|
* @param <U> The type of the value object. |
|
*/ |
|
static class Pair<T, U> { |
|
public final T key; |
|
public final U value; |
|
|
|
private Pair(T key, U value) { |
|
this.value = value; |
|
this.key = key; |
|
} |
|
|
|
/** |
|
* Factory method that creates a new {@link Pair} instance with the given key and value. |
|
* |
|
* @param <T> The type of the key object. |
|
* @param <U> The type of the value object. |
|
* @param key The key object to be stored in the instance. |
|
* @param value The value object to be stored in the instance. |
|
* @return A new instance with the specified key and value. |
|
*/ |
|
public static <T, U> Pair<T, U> of(T key, U value) { |
|
return new Pair<>(key, value); |
|
} |
|
|
|
@Override |
|
public boolean equals(Object o) { |
|
if (this == o) return true; |
|
if (!(o instanceof Pair)) return false; |
|
Pair<?, ?> pair = (Pair<?, ?>) o; |
|
return Objects.equals(key, pair.key); |
|
} |
|
|
|
@Override |
|
public int hashCode() { |
|
return Objects.hashCode(key); |
|
} |
|
} |
|
|
|
/** |
|
* Represents a path between two nodes. |
|
* It provides additional methods to access the departure and arrival nodes. |
|
*/ |
|
static class Path extends Pair<Integer, Integer> { |
|
private Path(Integer key, Integer value) { |
|
super(key, value); |
|
} |
|
|
|
/** |
|
* Returns the departure node of the path. |
|
* |
|
* @return The departure node of the path. |
|
*/ |
|
public Integer getDeparture() { |
|
return key; |
|
} |
|
|
|
/** |
|
* Returns the arrival node of the path. |
|
* |
|
* @return The arrival node of the path. |
|
*/ |
|
public Integer getArrival() { |
|
return value; |
|
} |
|
|
|
/** |
|
* Factory method that creates a new {@link Path} instance with the given departure and arrival nodes. |
|
* |
|
* @param from The departure path to be stored in the instance. |
|
* @param to The arrival path to be stored in the instance. |
|
* @return A new instance with the specified departure and arrival. |
|
*/ |
|
public static Path of(Integer from, Integer to) { |
|
return new Path(from, to); |
|
} |
|
} |
|
} |
