54 lines
1.7 KiB
Java
54 lines
1.7 KiB
Java
import java.util.ArrayDeque;
|
|
import java.util.ArrayList;
|
|
import java.util.Collections;
|
|
import java.util.Comparator;
|
|
import java.util.HashMap;
|
|
import java.util.List;
|
|
import java.util.Map;
|
|
import java.util.Queue;
|
|
import java.util.stream.Collectors;
|
|
import java.util.stream.IntStream;
|
|
|
|
public final class PancakeNumbers {
|
|
|
|
public static void main(String[] args) {
|
|
for ( int n = 1; n <= 9; n++ ) {
|
|
PancakeInfo result = pancake(n);
|
|
System.out.println(String.format("%s%2d%s", "Pancake(", result.index, "). Example " + result.pancake));
|
|
}
|
|
}
|
|
|
|
private static PancakeInfo pancake(int number) {
|
|
List<Integer> initialStack = IntStream.rangeClosed(1, number).boxed().collect(Collectors.toList());
|
|
Map<List<Integer>, Integer> stackFlips = new HashMap<List<Integer>, Integer>();
|
|
stackFlips.put(initialStack, 0);
|
|
Queue<List<Integer>> queue = new ArrayDeque<List<Integer>>();
|
|
queue.add(initialStack);
|
|
|
|
while ( ! queue.isEmpty() ) {
|
|
List<Integer> stack = queue.remove();
|
|
|
|
final int flipCount = stackFlips.get(stack) + 1;
|
|
for ( int i = 2; i <= number; i++ ) {
|
|
List<Integer> flipped = flipStack(stack, i);
|
|
if ( stackFlips.putIfAbsent(flipped, flipCount) == null ) {
|
|
queue.add(flipped);
|
|
}
|
|
}
|
|
}
|
|
|
|
Map.Entry<List<Integer>, Integer> entry =
|
|
stackFlips.entrySet().stream().max(Comparator.comparing( e -> e.getValue() )).get();
|
|
return new PancakeInfo(entry.getKey(), entry.getValue());
|
|
}
|
|
|
|
private static List<Integer> flipStack(List<Integer> stack, int index) {
|
|
List<Integer> copy = new ArrayList<Integer>(stack);
|
|
Collections.reverse(copy.subList(0, index));
|
|
return copy;
|
|
}
|
|
|
|
private static record PancakeInfo(List<Integer> pancake, int index) {}
|
|
|
|
}
|