Which Are In

• Challenge

Approach 1

Let’s call needle the substrings and haystack the array where to search for the needle.

1. Let needle be the first substring and matches be an initial, empty array.

2. Search for substring in the haystack.

   1. If found, add needle to the list of matches to be returned.

3. If there is no more needle to process, return matches.

4. Let needle be the next substring.

5. Go back and continue from step 2.

JavaScript

The Test Suite

import { inArray } from './which-are-in-v1.js';

describe('inArray()', () => {
  const haystack = ['lively', 'alive', 'harp', 'sharp', 'armstrong'];

  it('should find the correct substrings, if any', () => {
    [
      [['tarp', 'mice', 'bull'], []],
      [['xyz', 'live', 'strong'], ['live', 'strong']],
      [['live', 'strong', 'arp'], ['arp', 'live', 'strong']],
    ].forEach(([input, output]) => {
      expect(inArray(input, haystack)).toEqual(output);
    });
  });
});

Solution 1

/**
 * Retruns a lexicographically sorted list of strings in `xs` which
 * are substrings of the strings in `ys`.
 *
 * ASSUME: parameters are valid lists of strings.
 *
 * @signature
 * [String] [String] -> [String]
 *
 * @param {Array<string>} xs
 * @param {Array<string>} ys
 * @return {Array<string>}
 *
 *  @example
 *  inArray(['hi'], ['good-bye']);
 *  // → []
 *
 *  inArray(['live'], ['Portal' 'Still' 'Alive']);
 *  // → ['live']
 */
function inArray(xs, ys) {
  return xs.filter(function f (x) {
    return ys.find(function g (y) {
      return y.includes(x);
    });
  }).sort();
}

export { inArray };

TypeScript

The Test Suite

import { assertEquals } from '/deps.ts';
import { inArray } from './which-are-in-v1.ts';

Deno.test('inArray()', async (t) => {
  const haystack = ['lively', 'alive', 'harp', 'sharp', 'armstrong'];

  await t.step('should find no substrings', () => {
    assertEquals(inArray(['tarp', 'mice', 'bull'], haystack), []);
  });

  await t.step('should find two substrings', () => {
    assertEquals(
      inArray(['xyz', 'live', 'strong'], haystack),
      ['live', 'strong'],
    );
  });

  await t.step('should find all three substrings', () => {
    assertEquals(
      inArray(['live', 'strong', 'arp'], haystack),
      ['arp', 'live', 'strong'],
    );
  });
});

Solution 1

/**
 * Retruns a lexicographically sorted list of strings in `xs` which
 * are substrings of the strings in `ys`.
 *
 * ASSUME: parameters are valid lists of strings.
 */
function inArray(xs: string[], ys: string[]): string[] {
  return xs.filter(function f (x: string): string | undefined {
    return ys.find(function g (y: string): boolean {
      return y.includes(x);
    });
  }).sort();
}

export { inArray };

Scheme

The Test Suite

(import test)
(load "which-are-in-v1.scm")

(define haystack '("lively" "alive" "harp" "sharp" "armstrong"))

(test-group
 "in-list"
 (test-group
  "when substrings is empty"
  (test "should find nothing"
        '()
        (in-list '() haystack)))

 (test-group
  "when strings is empty"
  (test "should find nothing"
        '()
        (in-list '("tarp" "mice" "bull") '())))

 (test-group
  "when there is one match"
  (test "should return a list with one match"
        '("live")
        (in-list '("xyz" "live" "force") haystack)))

 (test-group
  "when there are multiple matches"
  (test "should return a list with the multiple matches"
        '("strong" "live" "arp")
        (in-list '("live" "strong" "arp") haystack))))

Solution 1

(import (chicken sort))
(import (only srfi-1 find filter))
(import (only srfi-13 string> string-contains))

;;
;; Checks whether `needle` is a substring of `haystack`.
;;
;; @curried
;;
;; @signature
;; String -> [String] -> Int | #f
;;
;; @example
;; ((contains "sh") "lisp")
;; ;; → #f
;;
;; ((contains "sh") "learn scheme!")
;; ;; → 5
;;
(define (contains needle)
  (lambda (haystack)
    (string-contains haystack needle)))

;;
;; Retruns a lexicographically sorted list of strings in `xs` which
;; are substrings of the strings in `ys`.
;;
;; ASSUME: parameters are valid lists of strings.
;;
;; @signature
;; [String] [String] -> [String]
;;
;; @example
;; (in-list '("hi") '("good-bye"))
;; ;; → ()
;;
;; (in-list '("live") '("Portal" "Still" "Alive"))
;; → ("live")
;;
(define (in-list xs ys)
  (sort
   (filter
    (lambda (x)
      (find (contains x) ys)) xs) string>))