Scala/Scala Ninety-Nine Problems 11

P98. Scala로 풀어본 Nonogram(노노그램, 네모네모로직) - 2

이전 글에서 살펴본 특징을 바탕으로 스칼라 코드로 구현해 보자. 0. 유틸리티성 정의Int로 표기하면 굉장히 복잡해진다. 좀 더 이해하기 쉽게 Enumeration을 정의한다./** * Nonogram 문제에서 사용할 Enumeration. * 칠한 부분은 O, 칠할 수 없는 부분은 X, 알 수 없는 부분은 U로 표기한다. */ object NonogramEnum extends Enumeration { val O, X, U = Value } 이전 문제들과 달리 스택에 쌓아가며 재귀호출하는 문제는 아니기 때문에 mutable 콜렉션을 사용할 수도 있다.하지만 함수형답게 immutable 콜렉션으로 푼다면 아래 메소드들이 필요하다. /** * 행이 칠해진 보드를 리턴하는 함수 * * @param board ..

P98. Scala로 풀어본 Nonogram(노노그램, 네모네모로직) - 1

P98 (***) Nonograms.Around 1994, a certain kind of puzzles was very popular in England. The "Sunday Telegraph" newspaper wrote: "Nonograms are puzzles from Japan and are currently published each week only in The Sunday Telegraph. Simply use your logic and skill to complete the grid and reveal a picture or diagram." As a programmer, you are in a better situation: you can have your computer do the..

P97. Scala로 풀어본 Sudoku(스도쿠)

P97 (**) Sudoku. (alternate solution)Sudoku puzzles go like this: 주어진 스도쿠 퍼즐을 푸는 알고리즘을 작성하는 문제다.스도쿠의 룰은 모두가 아는 것처럼 간단하다. 9 x 9의 스도쿠 퍼즐 판이 있을 때 가로 방향으로 1에서 9까지의 숫자, 세로 방향으로도 1에서 9까지의 숫자만을 포함하고 작은 섹션에서도 1에서 9까지의 숫자만을 가지면 된다. N-Queens 알고리즘과 마찬가지로 스도쿠를 풀기 위한 알고리즘도 여러가지가 있다. 가장 유명하고 단순한 방법인 백트래킹부터 제시된 풀이인 Dancing Links(알고리즘 X)와 같은 방법까지 있다. 나는 N-Queens와 마찬가지로 재귀를 이용한 백트래킹으로 문제를 풀어 보려 한다. 이전 문제들과 마찬가지의..

P94. Scala로 만들어본 K-regular simple graph(정규 그래프)

P94 (***) Generate K-regular simple graphs with N nodes. In a K-regular graph all nodes have a degree of K; i.e. the number of edges incident in each node is K. How many (non-isomorphic!) 3-regular graphs with 6 nodes are there? 노드의 갯수 N, 각 노드의 엣지 갯수 K를 입력받아 정규 그래프를 만드는 문제다. 정규 그래프(Regular graph)란 각 노드가 동일한 갯수의 엣지를 가지는 그래프로 각 엣지는 다른 노드와 연결된다. 노드와 엣지 갯수에 따른 정규 그래프들 정규 그래프를 그려보면 몇 가지 간단한 규칙을 찾을 수 ..

P93. Scala로 풀어본 Arithmetic Puzzle

P93 (***) An arithmetic puzzle.Given a list of integer numbers, find a correct way of inserting arithmetic signs (operators) such that the result is a correct equation. Example: With the list of numbers List(2,3,5,7,11) we can form the equations 2-3+5+7 = 11 or 2 = (3*5+7)/11 (and ten others!). 리스트로 주어진 수의 사이에 '=' 를 넣어 양 쪽 식의 값이 같게 되는 경우를 찾는 문제다.List(2, 3, 5, 7, 11)을 입력했을 때 답의 일부는 아래와 같다.2 = (3 ..

P91. Scala로 풀어본 Knight's Tour(기사의 여행)

P91 (**) Knight's tour.Another famous problem is this one: How can a knight jump on an N×N chessboard in such a way that it visits every square exactly once?Hints: Represent the squares by pairs of their coordinates of the form (X, Y), where both X and Y are integers between 1 and N. (Alternately, define a Point class for the same purpose.) Write a function jumps(N, (X, Y)) to list the squares t..