Skip to content

Instantly share code, notes, and snippets.

@tom-galvin
Last active August 29, 2015 14:17
Show Gist options
  • Save tom-galvin/796387d5acef8bf5394c to your computer and use it in GitHub Desktop.
Save tom-galvin/796387d5acef8bf5394c to your computer and use it in GitHub Desktop.
DailyProgrammer Challenge #206e Solution (Recurrence Relations, part 1)
open Util // fs-util available at https://gist.github.com/Quackmatic/2309d4f7b93631c99f22
/// Relation tree structure.
type Relation =
| Add of left: Relation * right: Relation
| Subtract of left: Relation * right: Relation
| Multiply of left: Relation * right: Relation
| Divide of left: Relation * right: Relation
| Constant of value: float
| Relative of offset: int
/// Defined terms needed to begin the series.
type Term = { index : int; value: float }
type Series = { terms: Term list; relation: Relation}
/// Evaluates relation with the given function to get a relative value
let rec evaluateRelation getRelative relation =
match relation with
| Add(l, r) -> (evaluateRelation getRelative l) + (evaluateRelation getRelative r)
| Subtract(l, r) -> (evaluateRelation getRelative l) - (evaluateRelation getRelative r)
| Multiply(l, r) -> (evaluateRelation getRelative l) * (evaluateRelation getRelative r)
| Divide(l, r) -> (evaluateRelation getRelative l) / (evaluateRelation getRelative r)
| Constant(x) -> x
| Relative(o) -> getRelative o
/// Gets the relative requirements of the given relation, e. if the relation is
/// first-order, return [-1]; ie. needs the value offset -1 from current index.
/// Fibonacci sequence relation would return [-1, -2].
let getRequirements relation =
let rec getRequirementsR relation =
match relation with
| Constant(x) -> []
| Relative(o) -> [o]
| Add(l, r) | Subtract(l, r) | Multiply(l, r) | Divide(l, r) -> (getRequirementsR l, getRequirementsR r) ||> List.append
getRequirementsR relation
|> List.distinct
|> List.sort
/// Determines whether the i-th term is defined with the given pre-existing term
let isDefinedAt terms i =
List.exists (fun x -> terms |> List.exists (fun def -> i + x = def.index) |> not) >> not
/// Evaluates the i-th term of the series
let evaluateAt terms relation i =
let getPrev i' =
(terms |> List.filter (fun def -> def.index = i + i') |> List.head).value
evaluateRelation getPrev relation
/// Converts the given series information to a generator sequence
let toGenerator series limit =
let reqs = getRequirements series.relation
let ord = -(reqs |> List.min)
let terms =
series.terms
|> List.sortBy (fun def -> def.index)
if List.isEmpty terms then
failwith "No initial condition."
else
let nextTerm terms =
let startDef, endDef = terms |> List.head, terms |> List.rev |> List.head
let rec nextTermR i =
if i < startDef.index + ord then
failwith <| sprintf "%d-th term undefined." i
elif isDefinedAt terms i reqs then
let newDef = { index = i; value = evaluateAt terms series.relation i }
if newDef.index > limit && limit > 0 then // Give limit 0 or below to go on forever
None
else
Some(newDef, (terms @ [newDef]))
else
nextTermR (i - 1)
nextTermR (endDef.index + ord)
terms |> Seq.unfold nextTerm |> (terms |> Seq.ofList |> Seq.append)
/// Parses challenge input for the Easy challenge
let readEasy =
let relation =
System.Console.ReadLine()
|> String.split [" "]
|> List.fold (fun relation s ->
let c, x = s.[0], s.Substring(1) |> float
match c with
| '+' -> Relation.Add(relation, Relation.Constant(x))
| '-' -> Relation.Subtract(relation, Relation.Constant(x))
| '*' -> Relation.Multiply(relation, Relation.Constant(x))
| '/' -> Relation.Divide(relation, Relation.Constant(x))
| _ -> failwith <| sprintf "Unknown operator %c." c) (Relation.Relative(-1))
let startVal = System.Console.ReadLine() |> float
{ terms = [ { index = 0; value = startVal } ]; relation = relation }
[<EntryPoint>]
let main argv =
let gen = toGenerator readEasy
let max = System.Console.ReadLine() |> int
Seq.iter (fun x ->
printfn "Term %d: %A" x.index x.value) (gen max)
System.Console.ReadKey() |> ignore
0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment