hickford

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Linq;

/// <summary>
/// A dictionary that remembers the order that keys were first inserted. If a new entry overwrites an existing entry, the original insertion position is left unchanged. Deleting an entry and reinserting it will move it to the end.
/// </summary>
/// <typeparam name="TKey">The type of keys</typeparam>

hickford

let protoFib f x = if x > 1 then f(x-1) + f(x-2) else x
let rec Y f x = f (Y f) x
let fib = Y protoFib
[1..10] |> List.map fib |> printfn "%A" 

hickford

/// Assuming f is a continuous function with a single minimum and no maximums in (lower,upper), find the minimum point.
let rec minimise f lower upper =
    let lmid = (2.0*lower+upper)/3.0
    let umid = (lower+2.0*upper)/3.0
    if lmid = lower && umid = upper then
        Seq.minBy f [lower; upper]
    else if f lmid < f umid then      
        minimise f lower umid
    else
        minimise f lmid upper

hickford

let solveByBacktracking moves solved initialState = 
    let rec inner state = 
        // to do: backtrack immediately if arrive at state we've seen before. (This can't happen for knight's tour or n queens as below.)
        match state with
            | Some progress when (progress |> solved |> not) ->
                progress |> moves |> Seq.map (Some >> inner) |> Seq.tryFind Option.isSome |> Option.flatten
            | _ -> state
    initialState |> Some |> inner

let describe row = 

hickford

// https://techdevguide.withgoogle.com/resources/volume-of-water/
// Imagine an island that is in the shape of a bar graph. When it rains, certain areas of the island fill up with rainwater to form lakes. Any excess rainwater the island cannot hold in lakes will run off the island to the west or east and drain into the ocean.
// Given an array of positive integers representing 2-D bar heights, design an algorithm (or write a function) that can compute the total volume (capacity) of water that could be held in all lakes on such an island given an array of the heights of the bars. Assume an elevation map where the width of each bar is 1.

// Calculate rainwater capacity of bar graph island.
let capacity heights =
    // height to which water rises is bounded above by greatest height to the left and greatest height to the right, and equal to the minimum of these. This is the 'rectilinear convex hull' of the original shape.

    // greatest height strictly to the left of ith bar
    let leftLimits = List.scan max

hickford

// solve a problem by backtracking
let solveByBacktracking solved moves initialState = 
    let rec inner state = 
        // to do: backtrack immediately if arrive at state we've seen before. (This can't happen for knight's tour or n queens as below.)
        match state with
            | Some progress when (progress |> solved |> not) ->
                progress |> moves |> Seq.map (Some >> inner) |> Seq.tryFind Option.isSome |> Option.flatten
            | _ -> state
    initialState |> Some |> inner

hickford

type Token = Text of string | Number of int | LeftBracket | RightBracket

let tokenize (compressed:string) : Token list =
    let folder tokens c =
        match c with
        | '[' -> LeftBracket :: tokens
        | ']' -> RightBracket :: tokens
        | _ when System.Char.IsDigit c -> 
            let digit = c |> string |> int
            match tokens with

hickford

// Cartesian product of lists
let product lists = 
    let folder list state =
         state |> Seq.allPairs list |> Seq.map List.Cons 
    Seq.singleton List.empty |> List.foldBack folder lists

let cycle seq =
    Seq.initInfinite (fun _ -> seq) |> Seq.concat

let T = System.Console.ReadLine() |> int

hickford

let check rows =
    // test if any queens are threatening each other
    let n = rows |> Seq.length
    let areDistinct = Seq.distinct >> Seq.length >> (=) n
    let forwardDiagonals = rows |> Seq.mapi (+)
    let backDiagonals = rows |> Seq.mapi (-)
    rows |> areDistinct && forwardDiagonals |> areDistinct && backDiagonals |> areDistinct

let solve n =
    // solve n-queens problem by generating random solutions

hickford

let solve words = 
    let words = words |> List.sort
    let r = words.[0] |> String.length

    let iths i = words |> List.map (fun s -> s.[i]) |> List.sort |> List.distinct 

    let letters = [0..r-1] |> List.map iths

    let bases = letters |> List.map List.length