algorithm - OCaml 中的倒计时游戏

Question

这是一个非常典型的游戏。

您将获得一个整数列表以及一个值。

您使用括号、+、-、*、/ 来得到最接近给定值。

不必使用列表中的所有整数。如果无法计算出相同的值，则您正在寻找最接近的值。

---

例如，您给 [1;3;7;10;25;50] 和 831。你能做的最接近的是

7 + (1 + 10) * (25 + 50) = 832

---

如何用 FP 或 ocaml 编写程序来解决这个问题？

1. 如何应用括号？
2. 如何生成所有可能的表达式？

Answer 1

let (|->) l f = List.concat (List.map f l)

type op = Add | Sub | Mul | Div

let apply op x y =
  match op with
  | Add -> x + y
  | Sub -> x - y
  | Mul -> x * y
  | Div -> x / y

let valid op x y =
  match op with
  | Add -> true
  | Sub -> x > y
  | Mul -> true
  | Div -> x mod y = 0

type expr = Val of int | App of op * expr * expr

let rec eval = function
  | Val n -> if n > 0 then Some n else None
  | App (o,l,r) ->
    eval l |> map_option (fun x ->
      eval r |> map_option (fun y ->
      if valid o x y then Some (apply o x y)
      else None))

let list_diff a b = List.filter (fun e -> not (List.mem e b)) a
let is_unique xs =
  let rec aux = function
    | [] -> true
    | x :: xs when List.mem x xs -> false
    | x :: xs -> aux xs in
  aux xs

let rec values = function
  | Val n -> [n]
  | App (_,l,r) -> values l @ values r

let solution e ns n =
  list_diff (values e) ns = [] && is_unique (values e) &&
  eval e = Some n

(* Brute force solution. *)

let split l =
  let rec aux lhs acc = function
    | [] | [_] -> []
    | [y; z] -> (List.rev (y::lhs), [z])::acc
    | hd::rhs ->
      let lhs = hd::lhs in
      aux lhs ((List.rev lhs, rhs)::acc) rhs in
  aux [] [] l

let combine l r =
  List.map (fun o->App (o,l,r)) [Add; Sub; Mul; Div]
let rec exprs = function
  | [] -> []
  | [n] -> [Val n]
  | ns ->
    split ns |-> (fun (ls,rs) ->
      exprs ls |-> (fun l ->
        exprs rs |-> (fun r ->
          combine l r)))

let rec choices = function _ -> failwith "choices: implement as homework"

let guard n =
  List.filter (fun e -> eval e = Some n)
let solutions ns n =
  choices ns |-> (fun ns' ->
    exprs ns' |> guard n)

(* Alternative implementation *)

let guard p e =
  if p e then [e] else []
let solutions ns n =
  choices ns |-> (fun ns' ->
    exprs ns' |->
      guard (fun e -> eval e = Some n))

有关说明，请参阅 Functional Programming in OCaml .