AoC 2015 Puzzle 9

Info

I solved this puzzle. You can find the code here, but I have yet to write a good explanation of the solution here. I will do this shortly, thank you for your patience.

Day 9: All in a Single Night

Every year, Santa manages to deliver all of his presents in a single night.

This year, however, he has some new locations to visit; his elves have provided him the distances between every pair of locations. He can start and end at any two (different) locations he wants, but he must visit each location exactly once. What is the shortest distance he can travel to achieve this?

For example, given the following distances:

  • London to Dublin = 464
  • London to Belfast = 518
  • Dublin to Belfast = 141

The possible routes are therefore:

  • Dublin -> London -> Belfast = 982
  • London -> Dublin -> Belfast = 605
  • London -> Belfast -> Dublin = 659
  • Dublin -> Belfast -> London = 659
  • Belfast -> Dublin -> London = 605
  • Belfast -> London -> Dublin = 982

The shortest of these is London -> Dublin -> Belfast = 605, and so the answer is 605 in this example.

What is the distance of the shortest route?

Part 2

The next year, just to show off, Santa decides to take the route with the longest distance instead.

He can still start and end at any two (different) locations he wants, and he still must visit each location exactly once.

For example, given the distances above, the longest route would be 982 via (for example) Dublin -> London -> Belfast.

What is the distance of the longest route?

Complete Solution

    private <T> void swap(T[] input, int a, int b) {
        T tmp = input[a];
        input[a] = input[b];
        input[b] = tmp;
    }

    public <T> List<T[]> permuteAllIterative(int n, T[] elements) {
        List<T[]> permutations = new ArrayList<>();
        int[] indexes = new int[n];
        for (int i = 0; i < n; i++) {
            indexes[i] = 0;
        }

        permutations.add(elements.clone());

        int i = 0;
        while (i < n) {
            if (indexes[i] < i) {
                swap(elements, i % 2 == 0 ? 0 : indexes[i], i);
                permutations.add(elements.clone());
                indexes[i]++;
                i = 0;
            } else {
                indexes[i] = 0;
                i++;
            }
        }

        return permutations;
    }

    // City City Distance
    Map<String, Map<String, Integer>> _paths = new HashMap<>();
    List<String> _cities = new ArrayList<>();

    private void storeCities(String... cities) {
        Arrays.stream(cities).forEach(s -> {
            if (!_cities.contains(s))
                _cities.add(s);
        });
    }

    private void addConnection(String from, String to, int distance) {
        Map<String, Integer> connections = _paths.getOrDefault(from, new HashMap<String, Integer>());
        connections.put(to, distance);

        _paths.put(from, connections);
    }

    public List<String[]> getPermutations(List<String> input) {
        for (String s : input) {
            String[] parts = s.split(" ");

            storeCities(parts[0], parts[2]);

            addConnection(parts[0], parts[2], Integer.parseInt(parts[4]));
            addConnection(parts[2], parts[0], Integer.parseInt(parts[4]));
        }

        // All permuatations of cities
        return permuteAllIterative(_cities.size(), _cities.toArray(new String[0]));
    }

    @Override
    public String part1(List<String> input) {
        _cities.clear();
        _paths.clear();

        List<String[]> permutations = getPermutations(input);

        int shortest = Integer.MAX_VALUE;
        for (String[] permutation : permutations) {
            int current = 0;
            for (int i = 0; i < permutation.length - 1; ++i) { // last index not necessary
                String from = permutation[i];
                String to = permutation[i + 1];

                int distance = _paths.get(from).get(to);
                current += distance;
            }
            if (current < shortest) {
                shortest = current;
            }
        }

        return String.valueOf(shortest);
    }

    @Override
    public String part2(List<String> input) {
        _cities.clear();
        _paths.clear();

        List<String[]> permutations = getPermutations(input);

        permutations.stream()
                .mapToInt(p -> IntStream.range(0, p.length - 1)
                        .mapToObj(idxFrom -> _paths.get(p[idxFrom]).get(p[idxFrom + 1])).mapToInt(Integer::intValue)
                        .sum())
                .max().getAsInt();

        return String.valueOf(longest);
    }

}