<commit_before>package ru._99_problems

import org.scalatest.matchers.ShouldMatchers
import org.junit.Test


class Misc extends ShouldMatchers {
	@Test def `P90 (**) Eight queens problem`() {
		solveEightQueen(2) should equal(Seq())
		solveEightQueen(3) should equal(Seq())
		solveEightQueen(4).size should equal(2)
		solveEightQueen(5).size should equal(10)
		solveEightQueen(8).size should equal(92)
	}


	private case class Queen(col: Int, row: Int) {
		def attacks(that: Queen): Boolean = {
			col == that.col || row == that.row || (col - that.col).abs == (row - that.row).abs
		}
	}
	private type Solution = Seq[Queen]

	private def solveEightQueen(boardSize: Int, startCol: Int = 0): Seq[Solution] = {
		if (boardSize < 3) return Seq()
		if (startCol >= boardSize) return Seq(Seq())

		val solutions = solveEightQueen(boardSize, startCol + 1)
		Range(0, boardSize).flatMap{ row =>
			val queen = Queen(startCol, row)<commit_msg>P91 draft<commit_after>package ru._99_problems

import org.scalatest.matchers.ShouldMatchers
import org.junit.Test


class Misc extends ShouldMatchers {
	private case class Point(x: Int, y: Int) {
		def knightMoves: Seq[Point] = {
			Seq()
		}

		def isOnBoard(boardSize: Int): Boolean = {
			x < boardSize && x >= 0 && y < boardSize && y >= 0
		}
	}

	@Test def `P91 (**) Knight's tour.`() {
		findKnightMoves(boardSize = 5, Point(0, 0), Seq(Point(0, 0))) should equal(Seq(Point(0, 0)))
	}

	private def findKnightMoves(boardSize: Int, startPoint: Point, moves: Seq[Point]): Seq[Point] = {
		if (moves.size == boardSize * boardSize) return moves

		val nextMoves = startPoint.knightMoves.filter(_.isOnBoard(boardSize)).filter(!moves.contains(_))
		if (nextMoves.isEmpty) return Seq()

		nextMoves.foldLeft[Option[Seq[Point]]](None) { (result, nextMove) =>
			if (result != None) result
			else {
				val subMoves = findKnightMoves(boardSize, nextMove, nextMove +: moves)
				if (subMoves.nonEmpty) Some(subMoves) else None
			}
		}.getOrElse(Seq())
	}


	@Test def `P90 (**) Eight queens problem`() {
		solveEightQueen(2) should equal(Seq())
		solveEightQueen(3) should equal(Seq())
		solveEightQueen(4).size should equal(2)
		solveEightQueen(5).size should equal(10)
		solveEightQueen(8).size should equal(92)
	}


	private case class Queen(col: Int, row: Int) {
		def attacks(that: Queen): Boolean = {
			col == that.col || row == that.row || (col - that.col).abs == (row - that.row).abs
		}
	}
	private type Solution = Seq[Queen]

	private def solveEightQueen(boardSize: Int, startCol: Int = 0): Seq[Solution] = {
		if (boardSize < 3) return Seq()
		if (startCol >= boardSize) return Seq(Seq())

		val solutions = solveEightQueen(boardSize, startCol + 1)
		Range(0, boardSize).flatMap{ row =>
			val queen = Queen(startCol, row)
{'fraction_non_alphanumeric': 0.14497469269703542, 'fraction_numerical': 0.017715112075198842, 'mean_word_length': 4.362403100775194, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3618795', 'n_tokens_mistral': 1098, 'n_tokens_neox': 963, 'n_words': 247}