jvlmdr

module Strain (keep, discard) where

keep :: (a -> Bool) -> [a] -> [a]
keep p = keep' where
  keep' [] = []
  keep' (x:xs) = (if p x then (x :) else id) $ keep' xs

discard :: (a -> Bool) -> [a] -> [a]
discard = keep . (not .)

jvlmdr

module Change (findFewestCoins) where

import Data.Function (on)
import Data.Map (Map, (!?))
import qualified Data.Map as Map
import Safe.Foldable (minimumByMay)

type Change = Maybe [Integer]
type Cache = Map Integer Change

jvlmdr

module Change (findFewestCoins) where

import Data.Array (listArray, (!))
import Data.Function (on)
import Safe.Foldable (minimumByMay)

findFewestCoins :: Integer -> [Integer] -> Maybe [Integer]
findFewestCoins target coins =
  let solutions = listArray (0, target) $ map formSolution [0 .. target]
      lookupSolution x = case compare x 0 of

jvlmdr

module Change (findFewestCoins) where

import Control.Monad.State
import Data.Function (on)
import Data.Map (Map, (!?))
import qualified Data.Map as Map
import Safe.Foldable (minimumByMay)

findFewestCoins :: Integer -> [Integer] -> Maybe [Integer]
findFewestCoins target coins = evalState (memoFind coins target) Map.empty

jvlmdr

:- table fewest_coins/3.

fewest_coins(_, 0, []).
fewest_coins(Coins, Target, Change) :-
    Target > 0,
    convlist(solve_subproblem(Coins, Target), Coins, Solutions),
    min_member(length_leq, Change, Solutions).

length_leq(A, B) :- length(A, LenA), length(B, LenB), LenA =< LenB.

jvlmdr

jvlmdr

jvlmdr

def farey(x, N): 
    a, b = 0, 1
    c, d = 1, 1
    while b + d <= N:
        mediant = (a + c) / (b + d)
        if x == mediant:
            return a + c, b + d 
        elif x > mediant:
            a, b = a + c, b + d 
        else:

jvlmdr

jvlmdr