VanDerWaerden.scala

package music

import org.junit.Assert._
import org.junit.Test
import util.ControlStructures._
import util.ImplicitConversions._

object Candle {
  def maxGap(len: Int) = len / 2

  def isSame(x: Int, xs: Seq[Int], offset: Int): Boolean = {
    val index = xs.length - 1 - offset
    index >= 0 && xs(index) === x
  }

  def isLegalAppend(xs: Seq[Int]): Boolean = {
    xs.lastOption match {
      case Some(last) => (1 to maxGap(xs.length)).forall(gap => !(isSame(last, xs, gap) && isSame(last, xs, gap * 2)))
      case None => true
    }
  }

  def isLegal(xs: Seq[Int]): Boolean = {
    def isSame2(head: Int, all: Seq[Int], index: Int): Boolean = {
      index >= 0 && index < xs.length && xs(index) === head
    }
    def checkGaps(head: Int, all: Seq[Int]): Boolean = {
      (1 to maxGap(all.length)).forall(gap => !(isSame2(head, all, gap) && isSame2(head, all, gap * 2)))
    }

    xs.toList match {
      case x :: rest if rest.length >= 2 => checkGaps(x, xs) && isLegal(rest)
      case _ => true
    }
  }

  def createSequences(len: Int, colors: Seq[Int]): Option[Iterator[Seq[Int]]] = {
    def createSequence0(soFar: Seq[Int]): Option[Iterator[Seq[Int]]] = {
      if (soFar.length === len)
        Some(Seq(soFar).toIterator)
      else {
        val legalColors = colors.shuffle.filter(color => isLegalAppend(soFar :+ color)).toIterator
        if (legalColors.nonEmpty)
          Some(legalColors.flatMap(legalColor => createSequence0(soFar :+ legalColor)).flatten)
        else
          None
      }
    }
    createSequence0(Seq.empty)
  }

  def createSequence(len: Int, colors: Seq[Int]): Option[Seq[Int]] = createSequences(len, colors).headOption.flatMap(_.headOption)
}

class CandleTests {
  import Candle._
  @Test def testMaxGap: Unit = {
    (1 to 20).map(len => (len, maxGap(len)))
  }

  @Test def testLegal: Unit = {
    def good(xs: Int*) = assertTrue(Candle.isLegal(xs))
    def bad(xs: Int*) = assertFalse(Candle.isLegal(xs))
    val indexForColor = "rbgy".zipWithIndex.toMap
    def colors(s: String): Seq[Int] = s.map(indexForColor)
    bad(1, 1, 1)
    good(1, 1)
    bad(1, 2, 1, 2, 1)
    good(1, 1, 2, 2, 1)
    good(colors("rrbbggyyrbgrbgy"): _*)
    bad(colors("rrbbggyyrbgrbgyg"): _*)
    bad(1, 3, 1, 2, 4, 3, 4, 3, 1, 2, 3, 3, 4, 4, 3, 1, 1, 2, 1, 1, 3, 2, 2, 4, 4, 3, 4, 4, 2, 1, 2, 3, 4, 1, 3, 1, 2, 3, 3, 1, 2, 4, 3, 4, 3, 1, 2, 3, 3, 4, 4, 3, 1, 1, 2, 1, 1, 3, 2, 2, 4, 4, 3, 4, 4, 2, 1, 2, 3, 4, 1, 3, 1, 2, 2)
    good(3, 4, 3, 1, 4, 2, 1, 3, 2, 2, 3, 1, 2, 1, 2, 4, 4, 1, 2, 4, 4, 2, 1, 3, 1, 1, 2, 4, 3, 3, 1, 3, 2, 4, 1, 2)
  }

  @Test def testSequence: Unit = {
    val legalColors = 1 to 4
    createSequences(len = 36, colors = legalColors).map { sequences =>
      sequences.toStream.filter { bigChunk =>
        val Seq(x1, x2, x3) = legalColors.shuffle.take(3)
        val all = Seq(x1) ++ bigChunk ++ Seq(x2) ++ bigChunk ++ Seq(x3)
        isLegal(all)
      }
    }.headOption.tap(x => println(s"AbcTests.scala:85: $x"))
  }
}