Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Building a training set of tags for scala #796

Closed
ErikSchierboom opened this issue Nov 1, 2023 · 21 comments
Closed

Building a training set of tags for scala #796

ErikSchierboom opened this issue Nov 1, 2023 · 21 comments

Comments

@ErikSchierboom
Copy link
Member

Hello lovely maintainers 👋

We've recently added "tags" to student's solutions. These express the constructs, paradigms and techniques that a solution uses. We are going to be using these tags for lots of things including filtering, pointing a student to alternative approaches, and much more.

In order to do this, we've built out a full AST-based tagger in C#, which has allowed us to do things like detect recursion or bit shifting. We've set things up so other tracks can do the same for their languages, but its a lot of work, and we've determined that actually it may be unnecessary. Instead we think that we can use machine learning to achieve tagging with good enough results. We've fine-tuned a model that can determine the correct tags for C# from the examples with a high success rate. It's also doing reasonably well in an untrained state for other languages. We think that with only a few examples per language, we can potentially get some quite good results, and that we can then refine things further as we go.

I released a new video on the Insiders page that talks through this in more detail.

We're going to be adding a fully-fledged UI in the coming weeks that allow maintainers and mentors to tag solutions and create training sets for the neural networks, but to start with, we're hoping you would be willing to manually tag 20 solutions for this track. In this post we'll add 20 comments, each with a student's solution, and the tags our model has generated. Your mission (should you choose to accept it) is to edit the tags on each issue, removing any incorrect ones, and add any that are missing. In order to build one model that performs well across languages, it's best if you stick as closely as possible to the C# tags as you can. Those are listed here. If you want to add extra tags, that's totally fine, but please don't arbitrarily reword existing tags, even if you don't like what Erik's chosen, as it'll just make it less likely that your language gets the correct tags assigned by the neural network.


To summarise - there are two paths forward for this issue:

  1. You're up for helping: Add a comment saying you're up for helping. Update the tags some time in the next few days. Add a comment when you're done. We'll then add them to our training set and move forward.
  2. You not up for helping: No problem! Just please add a comment letting us know :)

If you tell us you're not able/wanting to help or there's no comment added, we'll automatically crowd-source this in a week or so.

Finally, if you have questions or want to discuss things, it would be best done on the forum, so the knowledge can be shared across all maintainers in all tracks.

Thanks for your help! 💙


Note: Meta discussion on the forum

@ErikSchierboom
Copy link
Member Author

Exercise: perfect-numbers

Code

object NumberType extends Enumeration {
  type NumberType = Value
  val Deficient, Perfect, Abundant = Value
}

object PerfectNumbers {
  import NumberType._

  def sumFactorsOf(n: Int) : Int =
    (1 to n/2)
      .filter( n % _ == 0 )
      .sum

  def classify(n: Int) : NumberType =
    sumFactorsOf(n) match {
      case x if x == n => Perfect
      case x if x > n => Abundant
      case x if x < n => Deficient
    }

}

Tags:

construct:class
construct:divide
construct:enum
construct:filter
construct:if
construct:import
construct:int
construct:integral-number
construct:invocation
construct:method
construct:object
construct:parameter
construct:pattern-matching
construct:method-overloading
construct:method
construct:val
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:higher-order-functions
technique:inheritance

@ErikSchierboom
Copy link
Member Author

Exercise: matrix

Code

object Matrix {
  def apply(given: String) = new Matrix(given)
}


class Matrix(val given: String) {
  lazy val rows =
    given.split('\n').toIndexedSeq
      .map(_.split(' ').map(_.toInt).toIndexedSeq)

  lazy val cols = rows.transpose

  override def equals(that: Any): Boolean =
    that.isInstanceOf[Matrix] &&  {
      val thatGiven = that.asInstanceOf[Matrix].given
      given.equals(thatGiven)
    }

  override def hashCode(): Int = given.hashCode()
}

Tags:

construct:boolean
construct:char
construct:class
construct:constructor
construct:def
construct:equals
construct:field
construct:implicit-conversion
construct:invocation
construct:lazy
construct:logical-and
construct:map
construct:method
construct:parameter
construct:string
construct:to
construct:val
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:boolean-logic
technique:higher-order-functions
uses:String::split

@ErikSchierboom
Copy link
Member Author

Exercise: pangram

Code

object Pangrams {
  def isPangram(s: String) =
    s.toLowerCase().split("[^a-z]|").toSet.size == 27
}

Tags:

construct:method
construct:object
construct:parameter
construct:regex
construct:set
construct:string
construct:toMethod
construct:toInt
construct:toSet
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:regular-expression
uses:Regex
uses:Set

@ErikSchierboom
Copy link
Member Author

Exercise: rna-transcription

Code

import scala.io.Source

object Dna {

  val Ns = Map('G' -> 'C', 'C' -> 'G', 'T' -> 'A', 'A' -> 'U')

  def isValid(s: String) = s.foldLeft(true) { (valid, char) => valid && Ns.contains(char) }

  def toRna(dna: String) =
    if (isValid(dna)) Some(dna.map(Ns))
    else None

}

Tags:

construct:boolean
construct:char
construct:class
construct:curried-invocation
construct:def
construct:if
construct:import
construct:invocation
construct:map
construct:method
construct:object
construct:parameter
construct:tuple
construct:val
construct:boolean
construct:method
construct:val
construct:boolean
construct:if-expression
construct:implicit-conversion
construct:import
construct:map
construct:method
construct:parameter
construct:set
construct:tuple
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
uses:Map
uses:Set
uses:Tuple

@ErikSchierboom
Copy link
Member Author

Exercise: beer-song

Code

/**
  * Created by johncowie on 26/06/2017.
  */
object BeerSong {

  def bottleString(n: Int) = {
    n match {
      case 0 => "no more bottles"
      case 1 => "1 bottle"
      case x => s"$x bottles"
    }
  }

  def thirdLine(n: Int) = {
    n match {
      case 0 => "Go to the store and buy some more, "
      case 1 => "Take it down and pass it around, "
      case x => "Take one down and pass it around, "
    }
  }

  def verses(end: Int, start: Int): String = (start to end).reverse.map(verse).mkString("\n")

  def verse(i: Int): String = {
    val bottleA = bottleString(i)
    val bottleB = if(i==0) bottleString(99) else bottleString(i-1)

    s"$bottleA of beer on the wall, $bottleA of beer.\n".capitalize +
      thirdLine(i) + s"$bottleB of beer on the wall.\n"
  }

}

Tags:

construct:string-interpolation
construct:add
construct:assignment
construct:case-class
construct:if-else
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:map
construct:match
construct:method
construct:number
construct:object
construct:parameter
construct:string
construct:subtract
construct:to-method
construct:val
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:higher-order-functions

@ErikSchierboom
Copy link
Member Author

Exercise: beer-song

Code

object BeerSong {
  val verseN: Int => String = idx =>
    s"$idx ${bottlesStr(idx)} of beer on the wall, $idx ${bottlesStr(idx)} of beer.\nTake ${itStr(
      idx)} down and pass it around, ${remaining(idx)} of beer on the wall.\n"
  val verseOne = Int
  val verseZero =
    "No more bottles of beer on the wall, no more bottles of beer.\nGo to the store and buy some more, 99 bottles of beer on the wall.\n"

  val bottlesStr: Int => String = i => if (i == 1) "bottle" else "bottles"
  val itStr: Int => String = i => if (i == 1) "it" else "one"
  val remaining: Int => String = i =>
    if (i > 1) s"${(i - 1).toString} ${bottlesStr(i - 1)}"
    else "no more bottles"

  def verse(idx: Int): String = if (idx > 0) verseN(idx) else verseZero
  def verses(hi: Int, lo: Int): String =
    (Range.inclusive(hi, lo, -1)
      .foldLeft(new StringBuilder)((sb, i) => sb ++=  verse(i) ++= "\n"))
      .toString.stripLineEnd

}

Tags:

construct:string-interpolation
construct:assignment
construct:boolean
construct:class
construct:constructor
construct:def
construct:else
construct:if
construct:implicit-conversion
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:method
construct:number
construct:parameter
construct:return
construct:string
construct:subtract
construct:throw
construct:val
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:exceptions
technique:higher-order-functions
uses:StringBuilder

@ErikSchierboom
Copy link
Member Author

Exercise: series

Code

object Series {
  def slices(len: Int, series: String): Stream[Seq[Int]] =
    series
      .map(_ asDigit)
      .sliding(len)
      .toStream
}

Tags:

construct:asDigit
construct:method
construct:parameter
construct:stream
construct:string
construct:underscore
construct:implicit-conversion
construct:invocation
construct:method-overloading
construct:object
construct:stream
construct:to
construct:undescore-method
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:laziness
uses:String#map
uses:String#sliding
uses:Stream

@ErikSchierboom
Copy link
Member Author

Exercise: meetup

Code

import java.util.Calendar
import java.util.GregorianCalendar

case class Meetup(month: Int, year: Int) {
  val start = new GregorianCalendar(year, month - 1, 1)
  val teenthStart = new GregorianCalendar(year, month - 1, 13)
  val nextMonth = new GregorianCalendar(year, month, 1)

  def teenth(meetupDay: Int) = teenthStart.addDays(teenthStart.calculateDaysUntil(meetupDay))

  def last(meetupDay: Int) = nextMonth.addDays(-7).addDays(nextMonth.calculateDaysUntil(meetupDay))

  def first(meetupDay: Int) = start.addDays(start.calculateDaysUntil(meetupDay))
  def second(meetupDay: Int) = start.addDays(7 + start.calculateDaysUntil(meetupDay))
  def third(meetupDay: Int) = start.addDays(7 * 2 + start.calculateDaysUntil(meetupDay))
  def fourth(meetupDay: Int) = start.addDays(7 * 3 + start.calculateDaysUntil(meetupDay))

  implicit class ImmutableCalendar(calendar: Calendar) {
    def dayOfWeek(): Int = calendar.get(Calendar.DAY_OF_WEEK)
    def calculateDaysUntil(weekday: Int) = (Meetup.Sat - dayOfWeek + weekday) % 7
    def addDays(numDays: Int) = updateWith(_.add(Calendar.DAY_OF_YEAR, numDays))
    def copy: Calendar = calendar.clone.asInstanceOf[Calendar]
    def updateWith(func: Calendar => Unit) = {
      val _c = calendar.copy
      func(_c)
      _c
    }
  }

}

object Meetup {
  val Mon = Calendar.MONDAY
  val Tue = Calendar.TUESDAY
  val Wed = Calendar.WEDNESDAY
  val Thu = Calendar.THURSDAY
  val Fri = Calendar.FRIDAY
  val Sat = Calendar.SATURDAY
  val Sun = Calendar.SUNDAY
}

Tags:

construct:add
construct:asInstanceOf
construct:bigInteger
construct:class
construct:constructor
construct:date
construct:dayOfWeek
construct:def
construct:divide
construct:field
construct:int
construct:integralNumber
construct:implicitClass
construct:import
construct:invocation
construct:lambda
construct:method
construct:multiply
construct:namedArgument
construct:number
construct:object
construct:parameter
construct:patternMatching
construct:subtract
construct:throw
construct:val
construct:variable
construct:visibilityModifier
paradigm:functional
paradigm:object-oriented
technique:exceptions
technique:higher-order-functions
uses:Calendar
uses:GregorianCalendar

@ErikSchierboom
Copy link
Member Author

Exercise: kindergarten-garden

Code

object Plant extends Enumeration {
  type Plant = Value
  val Radishes, Clover, Grass, Violets = Value
}

class Garden(val students: Seq[String], val sillString:String) {
  import Plant._
  import Garden._

  lazy val indexByStudent =
    students.sorted
      .zipWithIndex
      .groupBy(_._1)
        .mapValues(_.head._2 + 1)

  lazy val sills = sillString.split("\n").toList

  def plantsByIndex(i: Int, width: Int): Seq[Plant] =
    sills
      .map(_.slice(i-width, i))
      .flatten
      .map(Plants)

  def getPlants(student: String): Seq[Plant] =
    indexByStudent.get(student)
      .map(_*2)
      .map(plantsByIndex(_:Int, 2))
      .getOrElse(Nil)
}

object Garden {
  val DefaultStudents =
    Seq("Alice", "Bob", "Charlie", "David", "Eve", "Fred", "Ginny", "Harriet", "Ileana", "Joseph", "Kincaid", "Larry")

  val Plants =
    Plant.values
      .groupBy(_.toString.charAt(0))
      .mapValues(_.head)

  def defaultGarden(sill: String) = Garden(DefaultStudents, sill)

  def apply(students: Seq[String], sill: String) = new Garden(students, sill)

}

Tags:

construct:add
construct:char
construct:class
construct:constructor
construct:def
construct:divide
construct:field
construct:implicit-conversion
construct:import
construct:int
construct:integral-number
construct:invocation
construct:lazy
construct:list
construct:method
construct:multiply
construct:nested-class
construct:number
construct:object
construct:parameter
construct:sort
construct:string
construct:subtract
construct:throw
construct:tuple
construct:type-alias
construct:val
construct:value-class
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:exceptions
technique:higher-order-functions
uses:List
uses:SortedSet
uses:Tuple2

@ErikSchierboom
Copy link
Member Author

Exercise: pascals-triangle

Code

object PascalsTriangle {
  def elemAt( col: Int, row: Int): Int = {
    if (row == 0 || col == 0 || (col == row)) 1
    else {
      elemAt(col - 1, row - 1) + elemAt(col, row - 1)
    }
  }

  def triangle(n: Int): List[List[Int]] =
    (for {
      r <- 0 to n - 1
      l = ((0 to r) map (elemAt(_, r))).toList
    } yield l).toList
}

Tags:

construct:add
construct:boolean
construct:for-comprehension
construct:if
construct:implicit-conversion
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:list
construct:logical-or
construct:method
construct:number
construct:object
construct:parameter
construct:recursive-call
construct:subtract
construct:to
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:boolean-logic
technique:higher-order-functions
technique:recursion
uses:List

@ErikSchierboom
Copy link
Member Author

Exercise: saddle-points

Code

case class Matrix(matrix: List[List[Int]]) {

  val rows = matrix.length
  val cols = matrix.headOption.map(_.length).getOrElse(0)

  val rowsMax = matrix.map(_.max)
  val colsMin = matrix.transpose.map(_.min)

  def rowMax(x: Int) = rowsMax(x)
  def colMin(y: Int) = colsMin(y)

  def element(x: Int, y: Int) = matrix(x)(y)
  def isSaddlePoint(x: Int, y: Int) = element(x, y) == rowMax(x) && element(x, y) == colMin(y)

  val points = for {
    x <- 0 until rows
    y <- 0 until cols
    if isSaddlePoint(x, y)
  } yield (x, y)

  val saddlePoints = points.toSet
}

Tags:

construct:boolean
construct:class
construct:constructor
construct:definition
construct:field
construct:for-comprehension
construct:if
construct:implicit-conversion
construct:indexed-access
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:list
construct:logical-and
construct:map
construct:method
construct:number
construct:parameter
construct:set
construct:tuple
construct:val
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:boolean-logic
technique:higher-order-functions
uses:Set
uses:Tuple

@ErikSchierboom
Copy link
Member Author

Exercise: roman-numerals

Code

case class RomanNumeral(n: Int) {

  private def divMod(x: Int, y: Int) = (x / y, x % y)

  private val s = Map(3 -> ("M", ""), 2 -> ("C", "D"), 1 -> ("X", "L"), 0 -> ("I", "V"))

  private def romanMagic(unit: Int, quint: Int, p: Int) = {
    if (unit == 4) s(p)._1 + s(p + 1)._1 * quint + s(p)._2 * (1 - quint) // e.g. IV, IX, XC, XL, CM, CD
    else s(p)._2 * quint + s(p)._1 * unit                                // VII, XI, CX, etc.
  }

  private def pow10(p: Int) = Math.pow(10, p).toInt

  val value =
    (3 to (0, -1)).foldLeft(("", n)) {
      case ((s, n), k) => {
        val (q, n1) = divMod(n, 5 * pow10(k))
        val (u, n2) = divMod(n1, pow10(k) )
        (s + romanMagic(u, q, k), n2)
      }
    }._1
}

Tags:

construct:add
construct:class
construct:comment
construct:divide
construct:if
construct:implicit-conversion
construct:int
construct:integral-number
construct:invocation
construct:method
construct:multiply
construct:named-argument
construct:number
construct:parameter
construct:tuple
construct:val
construct:variable
construct:visibility-modifiers
paradigm:object-oriented
technique:bit-manipulation
uses:Tuple2

@ErikSchierboom
Copy link
Member Author

Exercise: atbash-cipher

Code

case class Atbash() {
  def encode(plaintext: String): String = {
    plaintext
      .toLowerCase
      .replaceAll("[^a-z0-9]", "")
      .map(encodeLetterOrNumber)
      .grouped(5)
      .mkString(" ")
  }

  private def encodeLetterOrNumber(char: Char): Char = char match {
    case char if ('a' to 'z') contains char => ('z' - (char - 'a')).toChar
    case _ => char
  }
}

Tags:

construct:class
construct:method
construct:parameter
construct:method-overloading
construct:visibility-modifiers
paradigm:object-oriented

@ErikSchierboom
Copy link
Member Author

Exercise: pig-latin

Code

object PigLatin {
  def translate(phrase: String): String = {
    phrase.split(" ").map(PigLatinWord(_)).mkString(" ")
  }
}

object PigLatinWord {
  val vowelRegx = """([aeiou]{1,}[a-z]{1,})""".r
  val consRegx = """([^aeiou]{1,})([aeiou]{1,}[a-z]{1,})""".r
  val quRegx = """([^aeiou]{0,}qu)([a-z]{1,})""".r

  def apply(word: String): String = {
    def addSuffix(chars: String) = {
      chars + "ay"
    }
    word match {
      case vowelRegx(chars) => addSuffix(chars)
      case quRegx(first, next) => addSuffix(next + first)
      case consRegx(first, next) => addSuffix(next + first)
    }
  }
}

Tags:

construct:big-integer
construct:class
construct:constructor
construct:method
construct:parameter
construct:throw
construct:try
construct:val
construct:variable
construct:visibility-modifiers
paradigm:object-oriented
technique:exceptions

@ErikSchierboom
Copy link
Member Author

Exercise: binary-search-tree

Code

case class Bst[+T](value: T, left: Option[Bst[T]], right: Option[Bst[T]]) {
  def insert[U >: T <% Ordered[U]](x: U): Bst[U] = {
    def insert(x: U, node: Option[Bst[U]]): Option[Bst[U]] =
      node match {
        case Some(n) => Option(n.insert(x))
        case _ => Option(new Bst(x, None, None))
      }

    if (x <= value) new Bst(value, insert(x, left), right)
    else Bst(value, left, insert(x, right))
  }
}

object Bst {
  def fromList[T <% Ordered[T]](l: List[T]): Bst[T] = l match {
    case x::xs => xs.foldLeft(Bst(x, None, None))((r, e) => r.insert(e))
    case Nil => throw new IllegalArgumentException("Tree must not be empty")
  }

  def toList[T](tree: Bst[T]): List[T] = toList(Some(tree))

  private def toList[T](tree: Option[Bst[T]]): List[T] = tree match {
    case Some(b) => toList(b.left) ++ List(b.value) ++ toList(b.right)
    case None => List.empty
  }

  def apply[T](x: T): Bst[T] = Bst(x, None, None)
}

Tags:

construct:case-class
construct:class
construct:constructor
construct:def
construct:if
construct:implicit-conversion
construct:invocation
construct:method
construct:object
construct:parameter
construct:pattern-matching
construct:private
construct:throw
construct:throw-expression
construct:underscore
construct:val
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:exceptions

@ErikSchierboom
Copy link
Member Author

Exercise: zebra-puzzle

Code

import scala.collection.mutable.ListBuffer

object ZebraPuzzle {

  sealed trait Resident {
    var housePos: Option[Int] = None
    var animal: Option[String] = None
    var houseColor: Option[String] = None
    var cigarettes: Option[String] = None
    var beverage: Option[String] = None

    override def toString: String = {
      getClass.getSimpleName + "[" + housePos.getOrElse("?") + ", " + animal.getOrElse("?") + ", " +
        houseColor.getOrElse("?") + ", " + cigarettes.getOrElse("?") + ", " + beverage.getOrElse("?") + "]"
    }
  }
  case object Englishman extends Resident
  case object Spaniard extends Resident
  case object Ukrainian extends Resident
  case object Norwegian extends Resident
  case object Japanese extends Resident

  case class Solution(waterDrinker: Resident, zebraOwner: Resident)

  lazy val solve: Solution = solvePuzzle()

  val Residents = List(Englishman, Spaniard, Ukrainian, Norwegian, Japanese)
  private var conditions = ListBuffer[PartialFunction[Resident, Boolean]]()
  private var nearbyConditions = ListBuffer[PartialFunction[(Resident, Resident), Boolean]]()

  private var unassignedResidents: List[Resident] = _
  private var houseColors: List[String] = _
  private var animals: List[String] = _
  private var cigaretteBrands: List[String] = _
  private var beverages: List[String] = _

  private var solution: List[Resident] = _

  def createConditions(): Unit = {
    conditions += { case r => r.houseColor.contains("green") && r.beverage.contains("coffee") }

    nearbyConditions += { case (r1: Resident, r2: Resident) =>
      r1.houseColor.contains("ivory") && r2.houseColor.contains("green")
    }

    conditions += { case r => r.cigarettes.contains("Old Gold") && r.animal.contains("snails") }

    conditions += { case r => r.houseColor.contains("yellow") && r.cigarettes.contains("Kools") }

    conditions += { case r => r.beverage.contains("milk") && r.housePos.contains(3) }

    nearbyConditions += { case (r1: Resident, r2: Resident) =>
      r1.cigarettes.contains("Chesterfields") && r2.animal.contains("fox") ||
        r2.cigarettes.contains("Chesterfields") && r1.animal.contains("fox")
    }

    nearbyConditions += { case (r1: Resident, r2: Resident) =>
      r1.cigarettes.contains("Kools") && r2.animal.contains("horse") ||
        r2.cigarettes.contains("Kools") && r1.animal.contains("horse")
    }

    conditions += { case r => r.cigarettes.contains("Lucky Strike") && r.beverage.contains("orange juice") }

    nearbyConditions += { case (r1: Resident, r2: Resident) =>
      r1 == Norwegian && r2.houseColor.contains("blue") || r2 == Norwegian && r1.houseColor.contains("blue")
    }
  }

  def initialize(): Unit = {
    Englishman.houseColor = Some("red")
    Spaniard.animal = Some("dog")
    Ukrainian.beverage = Some("tea")
    Japanese.cigarettes = Some("Parliaments")
    Norwegian.housePos = Some(1)

    unassignedResidents = List(Englishman, Spaniard, Ukrainian, Japanese)
    houseColors = List("green", "ivory", "yellow", "orange", "blue")
    animals = List("snails", "fox", "horse", "zebra")
    cigaretteBrands = List("Old Gold", "Kools", "Chesterfields", "Lucky Strike")
    beverages = List("coffee", "milk", "orange juice", "water")
  }

  def logState(permutation: List[Resident]): Unit = {
    for (r <- permutation) print(r + " ")
    println()
  }

  def generatePositions(nextPos: Int, unassignedResidents: List[Resident], result: List[Resident]): Boolean = {
    if (nextPos > 4) {
      return generateHouseColors(0, houseColors, result)
    } else {
      for (r <- unassignedResidents) {
        r.housePos = Some(nextPos + 1)
        if (generatePositions(nextPos + 1, unassignedResidents.filterNot(_ == r), result :+ r)) {
          return true
        }
        r.housePos = None
      }
    }
    false
  }

  def generateHouseColors(nextPos: Int, unassignedColors: List[String], residents: List[Resident]): Boolean = {
    if (nextPos > 4) {
      return generateAnimals(0, animals, residents)
    } else if (residents(nextPos).houseColor.isDefined) {
      return generateHouseColors(nextPos + 1, unassignedColors, residents)
    } else {
      for (c <- unassignedColors) {
        residents(nextPos).houseColor = Some(c)
        if (generateHouseColors(nextPos + 1, unassignedColors.filterNot(_ == c), residents)) {
          return true
        }
        residents(nextPos).houseColor = None
      }
    }
    false
  }

  def generateAnimals(nextPos: Int, unassignedAnimals: List[String], residents: List[Resident]): Boolean = {
    if (nextPos > 4) {
      return generateCigaretteBrands(0, cigaretteBrands, residents)
    } else if (residents(nextPos).animal.isDefined) {
      return generateAnimals(nextPos + 1, unassignedAnimals, residents)
    } else {
      for (a <- unassignedAnimals) {
        residents(nextPos).animal = Some(a)
        if (generateAnimals(nextPos + 1, unassignedAnimals.filterNot(_ == a), residents)) {
          return true
        }
        residents(nextPos).animal = None
      }
    }
    false
  }

  def generateCigaretteBrands(nextPos: Int, unassignedBrands: List[String], residents: List[Resident]): Boolean = {
    if (nextPos > 4) {
      return generateBeverages(0, beverages, residents)
    } else if (residents(nextPos).cigarettes.isDefined) {
      return generateCigaretteBrands(nextPos + 1, unassignedBrands, residents)
    } else {
      for (c <- unassignedBrands) {
        residents(nextPos).cigarettes = Some(c)
        if (generateCigaretteBrands(nextPos + 1, unassignedBrands.filterNot(_ == c), residents)) {
          return true
        }
        residents(nextPos).cigarettes = None
      }
    }
    false
  }

  def generateBeverages(nextPos: Int, unassignedBeverages: List[String], residents: List[Resident]): Boolean = {
    if (nextPos > 4) {
      if (checkConditions(residents)) {
        solution = residents
        return true
      }
    } else if (residents(nextPos).beverage.isDefined) {
      return generateBeverages(nextPos + 1, unassignedBeverages, residents)
    } else {
      for (b <- unassignedBeverages) {
        residents(nextPos).beverage = Some(b)
        if (generateBeverages(nextPos + 1, unassignedBeverages.filterNot(_ == b), residents)) {
          return true
        }
        residents(nextPos).beverage = None
      }
    }
    false
  }

  def checkConditions(residents: List[Resident]): Boolean = {
    for (c <- conditions) {
      if (!residents.exists(c(_))) {
        return false
      }
    }
    for (c <- nearbyConditions) {
      var conditionFulfilled = false
      for (i <- 0 until residents.size - 1) {
        if (c(residents(i), residents(i + 1))) {
          conditionFulfilled = true
        }
      }
      if (!conditionFulfilled) {
        return false
      }
    }
    true
  }


  def solvePuzzle(): Solution = {
    createConditions()

    initialize()

    generatePositions(1, unassignedResidents, List(Norwegian))

    Solution(solution.filter(_.beverage.contains("water")).head, solution.filter(_.animal.contains("zebra")).head)
  }

  def main(args: Array[String]): Unit = {
    println(solve)
  }
}

Tags:

construct:add
construct:assignment
construct:boolean
construct:class
construct:collection
construct:constructor
construct:field
construct:for-comprehension
construct:if
construct:implicit-conversion
construct:indexed-access
construct:import
construct:int
construct:integral-number
construct:invocation
construct:lazy-evaluation
construct:list
construct:logical-and
construct:logical-or
construct:method
construct:nested-method
construct:object
construct:overloading
construct:parameter
construct:pattern-matching
construct:return
construct:sealed-trait
construct:string
construct:subtract
construct:trait
construct:underscore
construct:val
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:higher-order-functions
technique:inheritance
technique:looping
technique:recursion
uses:List
uses:ListBuffer

@ErikSchierboom
Copy link
Member Author

Exercise: variable-length-quantity

Code

package exercism

object VariableLengthQuantity {

  val MAX_DIGIT = 0x7F
  val MASK = 0x80

  def decode1(digits: List[Int]) = digits.foldLeft(0) { (acc, digit) =>
    (acc << 7) | (digit & MAX_DIGIT)
  }

  def encode1(num: Int, acc: List[Int] = Nil): List[Int] =
    if(num == 0) (if(acc.isEmpty) List(0) else acc)
    else encode1(num >>> 7, ((num & MAX_DIGIT) | (if(acc.isEmpty) 0 else MASK)) :: acc)

  def encode(nums: List[Int]): List[Int] = nums.flatMap(encode1(_))

  def decode(nums: List[Int]): Either[Unit, List[Int]] = decode(nums, Nil)
  def decode(nums: List[Int], acc: List[Int]):
      Either[Unit, List[Int]] = {
    if(nums.isEmpty) Right(acc.reverse)
    else {
      val (nextNum, rest) = nums.span(digit => (digit & MASK) != 0)
      if(rest.isEmpty) Left(())
      else decode(rest.tail, decode1(nextNum :+ rest.head) :: acc)
    }
  }
}

Tags:

construct:bitwise-and
construct:bitwise-or
construct:class
construct:constructor
construct:def
construct:default-parameters
construct:if
construct:implicit-conversion
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:left-shift
construct:list
construct:method
construct:nested-method
construct:number
construct:package
construct:parameter
construct:pattern-matching
construct:recursion
construct:scala:BigInt
construct:scala:List
construct:scala:Right
construct:scala:Tuple
construct:scala:ValDef
construct:val
construct:variable-length-quantity
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:bit-manipulation
technique:bit-shifting
technique:higher-order-functions
technique:looping
uses:List

@ErikSchierboom
Copy link
Member Author

Exercise: binary

Code

case class Binary(binary: String) {
  val toDecimal =
    if (binary forall {"01" contains _})
      binary.foldRight((0,0)) { case (c, (s, k)) => (s + (1 << k) * c.toString.toInt, k + 1) }._1
    else 0
}

Tags:

construct:bitwise-left-shift
construct:case-class
construct:if
construct:implicit-conversion
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:left-shift
construct:method
construct:multiply
construct:number
construct:parameter
construct:pattern-matching
construct:string
construct:tuple
construct:val
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:bit-manipulation
technique:bit-shifting
technique:higher-order-functions

@ErikSchierboom
Copy link
Member Author

Exercise: darts

Code

object Darts {

  private val scores = Seq(
    (1, 10),
    (5, 5),
    (10, 1)
  )

  def score(x: Double, y: Double) = {
    val hitRadius =
    scores.collectFirst {
      case (r, s) if r >= hitRadius => s
    }.getOrElse(0)
  }
}

Tags:

construct:assignment
construct:case-class
construct:collect
construct:double
construct:floating-point-number
construct:function
construct:if
construct:implicit-conversion
construct:invocation
construct:method
construct:number
construct:object
construct:parameter
construct:pattern-matching
construct:private
construct:tuple
construct:val
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:higher-order-functions

@ErikSchierboom
Copy link
Member Author

Exercise: high-scores

Code

object HighScores {
    def latest(a: List[Int]): Int = a.last

    def personalTop(a: List[Int]): List[Int] = {
        val b = a.sorted(Ordering.Int.reverse).take(3)
    }
    def personalBest(a: List[Int]): Int = a.max

    def report(a: List[Int]): String = {
        if(a.last == a.max)
        s"Your latest score was ${a.max}. That's your personal best!"
        else
        s"Your latest score was ${a.last}. That's ${Math.abs(a.max - a.last)} short of your personal best!"
    }
}

Tags:

construct:string-interpolation
construct:if
construct:implicit-conversion
construct:int
construct:integral-number
construct:invocation
construct:method
construct:number
construct:parameter
construct:subtract
construct:val
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented

@ErikSchierboom
Copy link
Member Author

This is an automated comment

Hello 👋 Next week we're going to start using the tagging work people are doing on these. If you've already completed the work, thank you! If you've not, but intend to this week, that's great! If you're not going to get round to doing it, and you've not yet posted a comment letting us know, could you please do so, so that we can find other people to do it. Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant