스터디파이 코틀린 입문 스터디 (https://studypie.co/ko/course/kotlin_beginner) 관련 자료입니다.
코틀린 입문반은 Kotlin을 직접 개발한 개발자가 진행하는 Coursera 강좌인 “Kotlin for Java Developers” (https://www.coursera.org/learn/kotlin-for-java-developers) 를 기반으로 진행되며 아래는 본 강좌 요약 및 관련 추가 자료 정리입니다.
목차
(9) 실습 : Mastermind in a functional style, Nice String, Taxi Park
- game2048 (관련 링크 : 2048(게임) — 나무위키)과 game of Fifteen (관련 링크 : 15퍼즐의 해법에 관하여)를 구현하는 과제입니다.
- 이전 Board 실습에서 구현한 GameBoard 인터페이스 구현체를 재사용합니다.
- 구현을 모두 마친 후에는 ui >PlayGame2048.kt 와 ui > playGameOfFifteen.kt 에서 main 함수를 실행시켜 직접 게임 동작을 확인해볼 수 있습니다.
1. Game 2048
문제 설명
- 다음 링크를 통해 Game 2048이 어떤 게임인지 직접 경험해볼 수 있습니다. (관련 링크 : 2048 Game)
- 사용자는 매 턴마다 키보드 up, down, right, left 중에서 선택할 수 있습니다.
- 선택할 경우 값들이 선택한 키보드 방향 쪽으로 쏠리는데 동일한 숫자 2개가 인접할 경우 두 숫자는 합쳐지며 그 동일한 두 숫자를 더한 (= 곱하기 2) 값을 가지는 숫자가 생성됩니다. 즉, 보드에 생성될 수 있는 숫자는 2의 거듭제곱 수 뿐입니다. (ex: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 등..)
- 키보드를 한번 선택할 때마다 비어있는 칸 중 랜덤한 위치에 새로운 숫자 (2 또는 4 중 하나)가 1개 생성됩니다.
- 보드가 모든 숫자로 꽉 차서 더이상 빈 공간이 없을 때 게임이 종료됩니다.
- 게임의 목표는 게임이 종료되기 전까지 2048을 만들어내는 것입니다.
구현 세부 과제 설명
moveAndMergeEqual()구현
- 게임 보드가 오직 1개의 row이고, 빈 공간은 제거한다고 가정할 때 (즉, 키보드로 방향을 선택한다는 개념이 존재하지 않음) 빈 공간을 제거하고 인접한 동일 숫자들을 합치는 기능을 수행하는
moveAndMergeEqual()메소드를 구현하세요.
fun <T : Any> List<T?>.moveAndMergeEqual(merge: (T) -> T): List<T> - 위 코드와 같이 메소드는 1개 row에 대응되는 값을 저장한 List의 확장 함수이며, 동작을 수행한 결과를 List 타입으로 반환합니다.
- 인자로 병합을 어떤식으로 수행할지를 정의하는 lambda를 받습니다. 예를 들어 본 문제 테스트 코드가 있는 TestGame2048Helper.kt 파일에는 인자로
{ it -> it.repeat(2) }를 받는데, 이는 “a”와 “a”가 병합될 경우 “aa” (="a".repeat(2))가 됨을 의미합니다. - 한편 병합은 무조건 왼쪽 -> 오른쪽 순서로 진행됩니다. 즉
["a", "a", null, "a"]와["a", null, "a", "a"]둘다 메소드를 수행하면["aa", "a"]가 됩니다.
2. nextValue() 구현
- 빈 셀이 존재하는지 찾아 1개 이상 존재할 경우 그 중 랜덤하게 선택하여 추가하는 값과 함께 반환 (
Pair<Cell, Int>)하고, 존재하지 않을 경우null을 반환하는nextValue()메소드를 구현하세요. - 새로운 값의 생성 규칙은 90%의 확률로 2, 10%의 확률로 4를 생성시키는 것입니다. (이건 이미
generateRandomStartValue()로 구현되어 있습니다.)
3. addNewValue() 구현
- 앞서
nextValue()구현을 통해 얻은 랜덤한 값을 랜덤한 빈 셀에 넣는 정보를 이용하여 실제로GameBoard를 갱신하는addNewValue()메소드를 구현하세요.
4. moveValuesInRowOrColumn() 구현
- 키보드로 방향을 선택할 때마다 이에 대응 되어 값들이 이동되고 인접한 동일한 값이 합쳐지는 기능을 수행하는
moveValuesInRowOrColumn()메소드를 구현하세요. - 앞서 구현한
moveAndMergeEqual()메소드를 사용합니다. - 이동이 발생한 경우
true를 반환하고, 이동이 발생하지 않은 경우false를 반환합니다.
5. moreValues() 구현
- 앞서 구현한 메소드를 이용하여 direction이 인자로 주어지면 Game2048의 턴별 이동 동작을 수행하는 메소드를 구현하세요.
예시 답안
moveAndMergeEqual()구현
fun <T : Any> List<T?>.moveAndMergeEqual(merge: (T) -> T): List<T> {
return this.asSequence() // call chain에 대한 최적화
.filterNotNull() // null 제거
.fold(mutableListOf()){ result, curr ->
// 빈 mutableList에 왼쪽부터 값을 하나씩 넣으며 인접한 두 값를 비교
// 두 값이 동일할 경우 merge한 값으로 교체
// 두 값이 다른 경우 값 삽입
when(curr){
result.lastOrNull() -> {
result[result.lastIndex] = merge(curr)
result
}
else -> {
result.add(curr)
result
}
}
}
}2. nextValue() 구현
override fun nextValue(board: GameBoard<Int?>): Pair<Cell, Int>? {
board.filter {
// 빈칸(null)인 cell만 찾는다.
it == null
}.takeIf{
// 빈칸이 1개 이상 존재하는 경우에만 추후 로직이 수행되도록 한다.
it.isNotEmpty()
}?.let{
// 빈칸이 1개 이상 존재하는 경우 그 중 랜덤으로 하나를 선택해 2 or 4 와 함께 반환한다.
return it.random() to RandomGame2048Initializer.generateRandomStartValue()
}
// 빈칸이 0개인 경우 null을 반환한다.
return null
}3. addNewValue() 구현
fun GameBoard<Int?>.addNewValue(initializer: Game2048Initializer<Int>) {
//nextValue 메소드가 null이 아닌 경우에만 수행
RandomGame2048Initializer.nextValue(this)?.let{ (cell, value) ->
// destructuring declaration을 통한 가독성 개선
// 앞서 Board 과제에서 구현한 set 함수에 대한 연산자 오버로딩 ([]) 사용
this[cell] = value
}
}4. moveValuesInRowOrColumn() 구현
fun GameBoard<Int?>.moveValuesInRowOrColumn(rowOrColumn: List<Cell>): Boolean {
val valuesRowOrColumn= rowOrColumn.map{ this[it] }
valuesRowOrColumn.moveAndMergeEqual {
it * 2
}.let{
// 빈공간을 null로 채움
val movedRowOrColumn:MutableList<Int?> = it.toMutableList()
repeat(rowOrColumn.size - it.size){
movedRowOrColumn.add(null)
}
movedRowOrColumn
}.takeIf { movedRowOrColumn ->
// move가 발생한 경우에만 추후 로직 진행 및 true 반환
movedRowOrColumn != valuesRowOrColumn
}?.let{movedRowOrColumn ->
rowOrColumn.forEachIndexed { index, cell ->
// 이전 Board 과제에서 구현한 set 함수에 대한 연산자 오버로딩 ([]) 사용
this[cell] = movedRowOrColumn[index]
}
return true
}
// move가 발생하지 않은 경우 false 반환
return false
}5. moreValues() 구현
fun GameBoard<Int?>.moveValues(direction: Direction): Boolean {
fun getRowOrColumn(direction: Direction, index:Int):List<Cell>{
return when(direction){
Direction.UP -> this.getColumn(1.. this.width, index)
Direction.DOWN -> this.getColumn(this.width downTo 1, index)
Direction.RIGHT -> this.getRow(index, this.width downTo 1)
Direction.LEFT -> this.getRow(index, 1..this.width)
}
}
return (1 .. this.width).fold(false){ isMoved, idx ->
this.moveValuesInRowOrColumn(getRowOrColumn(direction, idx))||isMoved
}
}2. Game of Fifteen
문제 설명
- 다음 링크를 통해 Game of Fifteen이 어떤 게임인지 직접 경험해볼 수 있습니다. (관련 링크 : Play the Fifteen puzzle online)
- 1부터 15까지의 숫자가 4 x 4 보드에 랜덤하게 채워져 있습니다. 위 예제에서는 빈칸에 인접한 숫자를 클릭하면 해당 숫자를 빈칸으로 이동시킬 수 있습니다. 한편 본 과제에서는 사용자가 키보드 up, down, right, left 중에서 선택을 하면 해당 방향으로 숫자들을 밀어내는 방식으로 이동시킵니다.
- 게임의 목표는 이러한 이동을 통해 1부터 15까지를 정렬하는 것입니다.
구현 세부 과제 설명
isEven()구현
- Game of Fifteen은 초기에 1부터 15까지의 숫자를 섞을 때 두 개의 숫자끼리 짝지어 교환하는 방식으로 (permutation) 섞은 경우, 이러한 permutation을 짝수번 한 경우에만 문제가 solvable 하고, 홀수번한 경우에는 solvable 하지 않다는 것이 증명되어 있습니다. (관련 링크 : 15퍼즐의 해법에 관하여)
- 이와 관련하여 숫자 교환이 짝수번인지 홀수번인지를 체크하는
isEven()메소드를 구현하세요. - 아래 설명은 다음 링크에 보다 자세히 설명되어 있습니다. (관련 링크 : 순열의 홀짝성)
- P를 (1..n) 숫자 배열에 대한 permutation 함수로 정의합니다. 예를 들어 1..5 라고 한다면, 아래와 같이 permutation 결과를 반환하는 함수입니다.
permutation = [4, 2, 5, 3, 1] 인 경우P(1) = 4
P(2) = 2
P(3) = 5
P(4) = 3
P(5) = 1
- 이 때 이 배열 중 임의의 두 원소 쌍 (i, j) (단, i < j) 에 대해, 만약 P(i) > P (j)인 경우를 생각해봅시다. 즉 위 예시에서는 P(1) = 4, P(4) = 3과 같이 인자는 1 < 4 이지만, 반환값은 P(1) > P(3) 인 경우입니다. 이러한 경우를 invert the order of (i, j) 또는 inverted pairs 라 부릅니다.
- 그리고 해당 Permutation 함수에 대해 이러한 inverted pairs가 짝수개로 존재하는 경우 even permutation (짝순열)이라 하고 짝수 번의 숫자 교환으로 원위치로 복구 시킬 수 있습니다. inverted pairs가 홀수개로 존재하는 경우 odd permutation (홀순열)이라 하고 홀수 번의 숫자 교환으로 원위치로 복구시킬 수 있습니다. (이에 대한 자세한 설명은 순열의 홀짝성을 참고 부탁드립니다.)
- 예를 들어 위 예시의 경우 inverted paris는 (1, 2), (1, 4), (1, 5), (2, 5), (3, 4), (3, 5), (4, 5)로 7개이므로 위 예시는 홀순열이라 할 수 있고,
isEven()메소드는 false를 반환합니다.
2. initialPermutation 구현
- 앞서 구현한
isEven()을 활용해 solvable한 문제 리스트를 만드는 연산을 하여 저장하는 lazy propertyinitialPermutation를 구현하세요. (1..15)를 랜덤하게 섞은 후 (shuffled()함수 사용 가능)isEven()을 통해 짝순열 여부를 판단하여 짝순열일 경우 그대로 반환하고, 홀순열일 경우 한번 더 두개의 숫자를 교환하여 짝순열로 만들어 반환합니다.
3. newGameOfFifteen() 구현
- 앞서 구현한 메소드를 활용하여 Game of Fifteen 게임을 위한 Game 인터페이스 구현체를 개발하여
newGameOfFifteen()를 구현하세요. - 즉 Game 인터페이스에 선언된 아래 함수들을 오버라이드 하여 구현해야 합니다.
interface Game {
fun initialize()
fun canMove(): Boolean
fun hasWon(): Boolean
fun processMove(direction: Direction)
operator fun get(i: Int, j: Int): Int?
}- 앞서 푼 Game2048 게임을 위한 Game 인터페이스 구현체 (Game2048.kt 파일 참고)를 참고하여 구현할 수 있습니다.
예시 답안
isEven()구현
fun isEven(permutation: List<Int>): Boolean {
// pair of original : (i, j) (i < j)
// permutation of i : Pi
val listOfOriginToPermutation = permutation.map { Pi ->
permutation.indexOf(Pi) + 1 to Pi
}
with(listOfOriginToPermutation) {
val test = flatMap { (i, Pi) ->
filter { (j, _) ->
i < j
}.map { (_, Pj) ->
Pi to Pj
}
}.count { (Pi, Pj) ->
Pi > Pj
}.takeIf { numOfInverted ->
numOfInverted % 2 == 0
}?.let {
return true
}
return false
}
}2. initialPermutation 구현
override val initialPermutation by lazy {
val shuffledList = (1..15).toList().shuffled()
when(isEven(shuffledList)){
true -> shuffledList
false -> shuffledList.apply {
Collections.swap(this, 0, 1)
}
}
}3. newGameOfFifteen() 구현
fun newGameOfFifteen(initializer: GameOfFifteenInitializer = RandomGameInitializer()): Game =
GameImpl(initializer)
class GameImpl(private val initializer: GameOfFifteenInitializer) : Game{
private val board = createGameBoard<Int?>(4)
private val solutionBoard = createGameBoard<Int?>(4)
override fun initialize() {
board.filter {
it == null
}.forEachIndexed { index, cell ->
board[cell] = initializer.initialPermutation.getOrNull(index)
solutionBoard[cell] = (1..15).toList().getOrNull(index)
}
}
override fun canMove(): Boolean = board.any { it == null }
override fun hasWon(): Boolean {
return board.getAllCells().all{cell ->
board[cell] == solutionBoard[cell]
}
}
override fun processMove(direction: Direction) {
val toMoveCell = board.find { it == null }
val fromMoveCell = with(board){
// with을 통해 SquareBoardImpl 내부에 구현된 확장함수 접근
toMoveCell?.getNeighbour(direction.reversed())
}
// move 불가능 케이스 : 옮길 수 있는 곳은 언제나 존재하나,
// 옮길 수 있는 곳에 대한 해당 direction에 대응되는 인접셀이 null 인 경우
fromMoveCell?.let{
board[toMoveCell!!] = board[fromMoveCell]
board[fromMoveCell] = null
}
}
override fun get(i: Int, j: Int): Int? = board.run { get(getCell(i,j)) }
}