Skip to content

Instantly share code, notes, and snippets.

@zer0tonin
Last active August 19, 2019 14:26
Show Gist options
  • Save zer0tonin/11aefefa88ed2b443259a6c3d4ead000 to your computer and use it in GitHub Desktop.
Save zer0tonin/11aefefa88ed2b443259a6c3d4ead000 to your computer and use it in GitHub Desktop.
Pancake Sorting algorithm
public class Pancake {
private int size;
public Pancake(int size) {
this.size = size;
}
public int size() {
return size;
}
public String toString() {
return String.valueOf(size);
}
}
import java.util.List;
import java.util.ArrayList;
public class PancakeStack {
List<Pancake> pancakes;
public PancakeStack(List<Pancake> pancakes) {
this.pancakes = pancakes;
}
public void sort() {
display();
sort(pancakes.size());
}
public void sort(int size) {
if (size != 0) {
var max = findMaxIndex(size);
if (max != size) {
putMaxAtTheEnd(size, max);
}
sort(size-1);
}
}
private int findMaxIndex(int size) {
var max = 0;
for (int i = 1; i < size; i++) {
if (pancakes.get(max).size() < pancakes.get(i).size()) {
max = i;
}
}
return max;
}
private void putMaxAtTheEnd(int size, int maxIndex) {
if (maxIndex != 0) {
flip(maxIndex);
}
flip(size-1);
}
private void flip(int position) {
var above = getPancakesAboveSpatula(position);
var under = getPancakesUnderSpatula(position);
var flipped = flipPancakesAboveSpatula(above);
pancakes = assembleStack(flipped, under);
display();
}
private List<Pancake> getPancakesAboveSpatula(int position) {
var above = new ArrayList<Pancake>();
for (int i = 0; i < pancakes.size(); i++) {
if (i <= position) {
above.add(pancakes.get(i));
}
}
return above;
}
private List<Pancake> getPancakesUnderSpatula(int position) {
var above = new ArrayList<Pancake>();
for (int i = 0; i < pancakes.size(); i++) {
if (i > position) {
above.add(pancakes.get(i));
}
}
return above;
}
private List<Pancake> flipPancakesAboveSpatula(List<Pancake> above) {
var flipped = new ArrayList<Pancake>();
var iterator = above.listIterator(above.size());
while (iterator.hasPrevious()) {
flipped.add(iterator.previous());
}
return flipped;
}
private List<Pancake> assembleStack(List<Pancake> flipped, List<Pancake> under) {
var result = new ArrayList<Pancake>();
for (var pancake : flipped) {
result.add(pancake);
}
for (var pancake : under) {
result.add(pancake);
}
return result;
}
public int[] getPancakeSizes() {
var sizes = new int[pancakes.size()];
for (int i = 0; i < pancakes.size(); i++) {
sizes[i] = pancakes.get(i).size();
}
return sizes;
}
public static PancakeStack of(int... pancakeSizes) {
var pancakes = new ArrayList<Pancake>();
for (int pancakeSize : pancakeSizes) {
pancakes.add(new Pancake(pancakeSize));
}
return new PancakeStack(pancakes);
}
private void display() {
var result = new StringBuilder();
for (var pancake : pancakes) {
result.append(pancake.toString());
result.append(" ");
}
System.out.println(result.toString());
}
}
import org.junit.Assert;
import org.junit.Test;
public class PancakeStackTest {
@Test
public void testSort1() {
var pancakeStack = PancakeStack.of(3, 1, 2);
pancakeStack.sort();
Assert.assertArrayEquals(new int[]{1, 2, 3}, pancakeStack.getPancakeSizes());
}
@Test
public void testSort2() {
var pancakeStack = PancakeStack.of(7, 6, 4, 2, 6, 7, 8, 7);
pancakeStack.sort();
Assert.assertArrayEquals(new int[]{2, 4, 6, 6, 7, 7, 7, 8}, pancakeStack.getPancakeSizes());
}
@Test
public void testSort3() {
var pancakeStack = PancakeStack.of(11, 5, 12, 3, 10, 3, 2, 5);
pancakeStack.sort();
Assert.assertArrayEquals(new int[]{2, 3, 3, 5, 5, 10, 11, 12}, pancakeStack.getPancakeSizes());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment