Skip to content

Instantly share code, notes, and snippets.

View SethTisue's full-sized avatar

Seth Tisue SethTisue

View GitHub Profile
@SethTisue
SethTisue / solve.scala
Created May 6, 2011 23:31
Google Code Jam: solves goo.gl/NyPoz in O(n log n)
// solves goo.gl/NyPoz in O(n log n)
def solveAll(credit: Int, items: Seq[Int]): (Int, Int) = {
// build a map from items to their indices in the input (lists of length 1 or 2)
val indices: Map[Int, Seq[Int]] =
items.zipWithIndex
.groupBy(_._1)
.mapValues(_.map(_._2 + 1))
def solve(item: Int): Option[(Int, Int)] =
if(item * 2 == credit)
@SethTisue
SethTisue / StateMachine.scala
Created May 6, 2011 23:32
sample DFA (deterministic finite automaton) implementation in Scala
// implements this DFA:
// en.wikipedia.org/wiki/File:DFAexample.svg
// as described here:
// en.wikipedia.org/wiki/Finite-state_machine#Acceptors_and_recognizers
// We have a few representational choices here:
// - We can have an explicit EOF, or not.
// (I chose yes.)
// - We can represent success and failure as states, or not.
@SethTisue
SethTisue / 99problems.scala
Created May 6, 2011 23:34
99 Scala problems — a few solutions
// 1
def last[A](xs: List[A]): A =
if(xs.tail.isEmpty) xs.head
else last(xs.tail)
// 2
def penultimate[A](xs: List[A]): A =
xs match {
@SethTisue
SethTisue / ch19.scala
Created May 6, 2011 23:39
The Seasoned Schemer, chapter 19, page 176
// page 176
// recursive non-consing solution with var
def hasTwoInARow[T](lists: List[Any]) = {
var previous: Option[Any] = None
def recurse(rest: Any): Boolean =
rest match {
case xs: List[_] =>
xs.exists(recurse)
@SethTisue
SethTisue / ch13.scala
Created May 6, 2011 23:41
Seasoned Schemer, chapter 13
// page 37
/*
def intersect[T](set1: List[T], set2: List[T]): List[T] =
set1 match {
case Nil => Nil
case car :: cdr =>
if (set2.contains(car))
car :: intersect(cdr, set2)
else
@SethTisue
SethTisue / .gitignore
Last active December 7, 2016 01:42
parse iTunes library XML, compile stats. shows how to use Scala's XML pull API, by putting some DSL-y goodness on top of it
/tunes.txt
@SethTisue
SethTisue / io.scala
Created May 6, 2011 23:46
abandoned attempt at a Haskell-style IO monad in Scala
// I started with code from:
// http://apocalisp.wordpress.com/2011/01/10/functional-programming-for-beginners/
// the filter stuff doesn't really make sense, since IO has no zero, but I was
// interested in fooling with it anyway and seeing what worked and what didn't.
// since I did this Apocalisp has done an official version and added it to Scalaz
object io {
@SethTisue
SethTisue / koch.hs
Created May 6, 2011 23:48
Koch snowflake code in Haskell. an exercise from Hudak's book The Haskell School of Expression
-- how to run: ghci -i Koch.hs Picture Region Draw Shape Animation SOE EnableGUI
module Koch where
-- infrastructure
import SOE hiding (Region)
import Picture
import Animation (turn)
import EnableGUI
@SethTisue
SethTisue / buffer.scala
Created May 24, 2011 17:58
eliminating a mutable buffer
import java.io._
def userStream =
new BufferedReader(
new InputStreamReader(
new FileInputStream("/etc/passwd")))
// imperative style
def linesI(s: BufferedReader): List[String] = {
val buf = new collection.mutable.ListBuffer[String]
@SethTisue
SethTisue / Dynamic.scala
Created May 24, 2011 21:41
for BASE talk
import scala.util.DynamicVariable
class Workspace {
def run(s: String) { println(s) }
def report(s: String) = 10
def dispose() { println("disposed") }
}
def expect[T](expected: T)(actual: T) {
assert(expected == actual, actual.toString)