1
votes

LeetCode 1: Comment traduire la somme de la question deux de ReasonML à Clojure?

J'ai répondu à la question " TwoSum " dans ReasonML / Ocaml mais je n'ai aucune idée de comment coder cela dans Clojure avec un pseudo algorithme similaire. Veuillez commenter comment traduire cette solution en Clojure

Clojure

  module TwoSum: {
    let twoSum: (int, Belt.List.t(int)) => list(list(int));
    let run: unit => unit;
  } = {

    let logl = l => l |> Array.of_list |> Js.log;

    let concatmap = (xs: list('a), f) => {
      List.concat(List.map(x => f(x), xs));
    };

    let twoSum = (n, xs) => {
      let ixs = Belt.List.zip([0, ...range(1, List.length(xs))], xs);
      concatmap(ixs, ((i, x)) =>
        concatmap(drop(i, ixs), ((j, y)) => x + y == n ? [[i, j]] : [])
      );
    };

    let run = () => {
      Printf.printf("1. Two Sum :\n");
      let res = twoSum(21, [0, 2, 11, 19, 90, 10]);
      res |> logl;

    };
  };

ReasonML

(def nums [2 7 11 15])
(def target 9)

(defn two-sum [n xs]
  (let [ixs (map vector xs (range (count xs)))]))

algorithm functional-programming clojure reason

2 commentaires

Pouvez-vous s'il vous plaît fournir un lien vers la "question TwoSum" que vous faites référence aussi

@cfrick Veuillez vous référer à ce lien " leetcode.com/problems/two-sum "

3 Réponses :

3
votes

Vous pouvez utiliser pour pour lister toutes les paires d'index possibles et le : quand option pour filtrer les paires qui remplissent les conditions à deux sommes. Cela renverra une séquence de solutions possibles. Ensuite, vous choisissez la première solution.

(defn two-sum [numbers target]
  (let [inds (range (count numbers))]
    (first (for [i inds
                 j inds
                 :when (and (not= i j)
                            (= target (+ (nth numbers i)
                                         (nth numbers j)))) ]
             [i j]))))

(two-sum [2 7 11 15] 9)
;; => [0 1]

0 commentaires

1
votes

J'irais avec un style plus fonctionnel:

à partir de la création de paires fonction:

(defn sum2 [target data]
  (for [[[i x] & xs] (->> data
                          (map-indexed vector)
                          (iterate rest)
                          (take-while seq))
        [j y] xs
        :when (== target (+ x y))]
    [i j]))

user> (sum2 9 [2 7 11 15])
;;=> ([0 1])

alors vous pouvez générer ces paires d'index -to-item tuples:

(defn sum2 [target data]
  (->> data
       (map-indexed vector)
       pairs
       (keep (fn [[[i x] [j y]]]
               (when (== target (+ x y))
                 [i j])))))

user> (sum2 9 [2 7 11 15])
;;=> ([0 1])

pour que vous ayez juste besoin de garder les paires dont vous avez besoin:

user> (pairs (map-indexed vector [:a :b :c]))
;;=> ([[0 :a] [1 :b]] 
;;    [[0 :a] [2 :c]] 
;;    [[1 :b] [2 :c]])

une autre option consiste à utiliser des listes de compréhension pour cela:

(defn pairs [data]
  (->> data
       (iterate rest)
       (take-while seq)
       (mapcat (fn [[x & xs]] (map (partial vector x) xs)))))

user> (pairs [:a :b :c :d])
;;=> ([:a :b] [:a :c] [:a :d] [:b :c] [:b :d] [:c :d])

0 commentaires

3
votes

En guise de légère variation, j'utiliserais une fonction d'assistance indexé pour convertir [: a: b: c] en:

(two-sum [2 7 11 15] 666)     => nil
(two-sum [2 7 11 15] 9)       => [0 1]
(two-sum [0 1 2 7 11 15] 9)   => [2 3]

puis nous obtenons:

(defn indexed
  [vals]
  (mapv vector (range) vals))

(defn two-sum
  [vals tgt]
  (let [idx-vals (indexed vals)]
    (first
      (for [[i x] idx-vals  ; destructure each pair => local vars i & x
            [j y] idx-vals
            :when (and (< i j)
                    (= tgt (+ x y)))]
        [i j]))))

0 commentaires