Last active
August 19, 2019 14:26
-
-
Save zer0tonin/11aefefa88ed2b443259a6c3d4ead000 to your computer and use it in GitHub Desktop.
Pancake Sorting algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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()); | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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