Avatar of paulfioravanti

paulfioravanti's solution

to Grep in the Elixir Track

Published at Aug 29 2019 · 0 comments
Instructions
Test suite
Solution

Search a file for lines matching a regular expression pattern. Return the line number and contents of each matching line.

The Unix grep command can be used to search for lines in one or more files that match a user-provided search query (known as the pattern).

The grep command takes three arguments:

  1. The pattern used to match lines in a file.
  2. Zero or more flags to customize the matching behavior.
  3. One or more files in which to search for matching lines.

Your task is to implement the grep function, which should read the contents of the specified files, find the lines that match the specified pattern and then output those lines as a single string. Note that the lines should be output in the order in which they were found, with the first matching line in the first file being output first.

As an example, suppose there is a file named "input.txt" with the following contents:

hello
world
hello again

If we were to call grep "hello" input.txt, the returned string should be:

hello
hello again

Flags

As said earlier, the grep command should also support the following flags:

  • -n Print the line numbers of each matching line.
  • -l Print only the names of files that contain at least one matching line.
  • -i Match line using a case-insensitive comparison.
  • -v Invert the program -- collect all lines that fail to match the pattern.
  • -x Only match entire lines, instead of lines that contain a match.

If we run grep -n "hello" input.txt, the -n flag will require the matching lines to be prefixed with its line number:

1:hello
3:hello again

And if we run grep -i "HELLO" input.txt, we'll do a case-insensitive match, and the output will be:

hello
hello again

The grep command should support multiple flags at once.

For example, running grep -l -v "hello" file1.txt file2.txt should print the names of files that do not contain the string "hello".

Running tests

Execute the tests with:

$ mix test

Pending tests

In the test suites, all but the first test have been skipped.

Once you get a test passing, you can unskip the next one by commenting out the relevant @tag :pending with a # symbol.

For example:

# @tag :pending
test "shouting" do
  assert Bob.hey("WATCH OUT!") == "Whoa, chill out!"
end

Or, you can enable all the tests by commenting out the ExUnit.configure line in the test suite.

# ExUnit.configure exclude: :pending, trace: true

If you're stuck on something, it may help to look at some of the available resources out there where answers might be found.

Source

Conversation with Nate Foster. http://www.cs.cornell.edu/Courses/cs3110/2014sp/hw/0/ps0.pdf

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

grep_test.exs

defmodule GrepTest do
  use ExUnit.Case

  setup context do
    if context[:files] do
      File.write!("iliad.txt", """
      Achilles sing, O Goddess! Peleus' son;
      His wrath pernicious, who ten thousand woes
      Caused to Achaia's host, sent many a soul
      Illustrious into Ades premature,
      And Heroes gave (so stood the will of Jove)
      To dogs and to all ravening fowls a prey,
      When fierce dispute had separated once
      The noble Chief Achilles from the son
      Of Atreus, Agamemnon, King of men.
      """)

      File.write!("midsummer-night.txt", """
      I do entreat your grace to pardon me.
      I know not by what power I am made bold,
      Nor how it may concern my modesty,
      In such a presence here to plead my thoughts;
      But I beseech your grace that I may know
      The worst that may befall me in this case,
      If I refuse to wed Demetrius.
      """)

      File.write!("paradise-lost.txt", """
      Of Mans First Disobedience, and the Fruit
      Of that Forbidden Tree, whose mortal tast
      Brought Death into the World, and all our woe,
      With loss of Eden, till one greater Man
      Restore us, and regain the blissful Seat,
      Sing Heav'nly Muse, that on the secret top
      Of Oreb, or of Sinai, didst inspire
      That Shepherd, who first taught the chosen Seed
      """)

      on_exit(fn ->
        File.rm!("iliad.txt")
        File.rm!("midsummer-night.txt")
        File.rm!("paradise-lost.txt")
      end)
    end
  end

  @moduletag :files

  describe "grepping a single file" do
    test "one match, no flags" do
      assert Grep.grep("Agamemnon", [], ["iliad.txt"]) ==
               """
               Of Atreus, Agamemnon, King of men.
               """
    end

    @tag :pending
    test "one match, print line numbers flag" do
      assert Grep.grep("Forbidden", ["-n"], ["paradise-lost.txt"]) ==
               """
               2:Of that Forbidden Tree, whose mortal tast
               """
    end

    @tag :pending
    test "one match, case-insensitive flag" do
      assert Grep.grep("FORBIDDEN", ["-i"], ["paradise-lost.txt"]) ==
               """
               Of that Forbidden Tree, whose mortal tast
               """
    end

    @tag :pending
    test "one match, print file names flag" do
      assert Grep.grep("Forbidden", ["-l"], ["paradise-lost.txt"]) ==
               """
               paradise-lost.txt
               """
    end

    @tag :pending
    test "one match, match entire lines flag" do
      assert Grep.grep("With loss of Eden, till one greater Man", ["-x"], ["paradise-lost.txt"]) ==
               """
               With loss of Eden, till one greater Man
               """
    end

    @tag :pending
    test "one match, multiple flags" do
      assert Grep.grep("OF ATREUS, Agamemnon, KIng of MEN.", ["-n", "-i", "-x"], ["iliad.txt"]) ==
               """
               9:Of Atreus, Agamemnon, King of men.
               """
    end

    @tag :pending
    test "several matches, no flags" do
      assert Grep.grep("may", [], ["midsummer-night.txt"]) ==
               """
               Nor how it may concern my modesty,
               But I beseech your grace that I may know
               The worst that may befall me in this case,
               """
    end

    @tag :pending
    test "several matches, print line numbers flag" do
      assert Grep.grep("may", ["-n"], ["midsummer-night.txt"]) ==
               """
               3:Nor how it may concern my modesty,
               5:But I beseech your grace that I may know
               6:The worst that may befall me in this case,
               """
    end

    @tag :pending
    test "several matches, match entire lines flag" do
      assert Grep.grep("may", ["-x"], ["midsummer-night.txt"]) == ""
    end

    @tag :pending
    test "several matches, case-insensitive flag" do
      assert Grep.grep("ACHILLES", ["-i"], ["iliad.txt"]) ==
               """
               Achilles sing, O Goddess! Peleus' son;
               The noble Chief Achilles from the son
               """
    end

    @tag :pending
    test "several matches, inverted flag" do
      assert Grep.grep("Of", ["-v"], ["paradise-lost.txt"]) ==
               """
               Brought Death into the World, and all our woe,
               With loss of Eden, till one greater Man
               Restore us, and regain the blissful Seat,
               Sing Heav'nly Muse, that on the secret top
               That Shepherd, who first taught the chosen Seed
               """
    end

    @tag :pending
    test "no matches, various flags" do
      assert Grep.grep("Gandalf", ["-n", "-l", "-x", "-i"], ["iliad.txt"]) == ""
    end
  end

  describe "grepping multiples files at once" do
    @tag :pending
    test "one match, no flags" do
      assert Grep.grep("Agamemnon", [], ["iliad.txt", "midsummer-night.txt", "paradise-lost.txt"]) ==
               """
               iliad.txt:Of Atreus, Agamemnon, King of men.
               """
    end

    @tag :pending
    test "several matches, no flags" do
      assert Grep.grep("may", [], ["iliad.txt", "midsummer-night.txt", "paradise-lost.txt"]) ==
               """
               midsummer-night.txt:Nor how it may concern my modesty,
               midsummer-night.txt:But I beseech your grace that I may know
               midsummer-night.txt:The worst that may befall me in this case,
               """
    end

    @tag :pending
    test "several matches, print line numbers flag" do
      assert Grep.grep("that", ["-n"], ["iliad.txt", "midsummer-night.txt", "paradise-lost.txt"]) ==
               """
               midsummer-night.txt:5:But I beseech your grace that I may know
               midsummer-night.txt:6:The worst that may befall me in this case,
               paradise-lost.txt:2:Of that Forbidden Tree, whose mortal tast
               paradise-lost.txt:6:Sing Heav'nly Muse, that on the secret top
               """
    end

    @tag :pending
    test "one match, print file names flag" do
      assert Grep.grep("who", ["-l"], ["iliad.txt", "midsummer-night.txt", "paradise-lost.txt"]) ==
               """
               iliad.txt
               paradise-lost.txt
               """
    end

    @tag :pending
    test "several matches, case-insensitive flag" do
      assert Grep.grep("TO", ["-i"], ["iliad.txt", "midsummer-night.txt", "paradise-lost.txt"]) ==
               """
               iliad.txt:Caused to Achaia's host, sent many a soul
               iliad.txt:Illustrious into Ades premature,
               iliad.txt:And Heroes gave (so stood the will of Jove)
               iliad.txt:To dogs and to all ravening fowls a prey,
               midsummer-night.txt:I do entreat your grace to pardon me.
               midsummer-night.txt:In such a presence here to plead my thoughts;
               midsummer-night.txt:If I refuse to wed Demetrius.
               paradise-lost.txt:Brought Death into the World, and all our woe,
               paradise-lost.txt:Restore us, and regain the blissful Seat,
               paradise-lost.txt:Sing Heav'nly Muse, that on the secret top
               """
    end

    @tag :pending
    test "several matches, inverted flag" do
      assert Grep.grep("a", ["-v"], ["iliad.txt", "midsummer-night.txt", "paradise-lost.txt"]) ==
               """
               iliad.txt:Achilles sing, O Goddess! Peleus' son;
               iliad.txt:The noble Chief Achilles from the son
               midsummer-night.txt:If I refuse to wed Demetrius.
               """
    end

    @tag :pending
    test "one match, match entire lines flag" do
      assert Grep.grep("But I beseech your grace that I may know", ["-x"], [
               "iliad.txt",
               "midsummer-night.txt",
               "paradise-lost.txt"
             ]) ==
               """
               midsummer-night.txt:But I beseech your grace that I may know
               """
    end

    @tag :pending
    test "one match, multiple flags" do
      assert Grep.grep("WITH LOSS OF EDEN, TILL ONE GREATER MAN", ["-n", "-x", "-i"], [
               "iliad.txt",
               "midsummer-night.txt",
               "paradise-lost.txt"
             ]) ==
               """
               paradise-lost.txt:4:With loss of Eden, till one greater Man
               """
    end

    @tag :pending
    test "no matches, various flags" do
      assert Grep.grep("Frodo", ["-n", "-l", "-x", "-i"], [
               "iliad.txt",
               "midsummer-night.txt",
               "paradise-lost.txt"
             ]) == ""
    end
  end
end

test_helper.exs

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)
defmodule Grep do
  @entire_lines_only "-x"
  @caseless "i"
  @ignore_case "-" <> @caseless
  @invert_pattern "-v"
  @starting_index 1
  @filenames_only "-l"
  @line_numbers "-n"

  @spec grep(String.t(), [String.t()], [String.t()]) :: String.t()
  def grep(pattern, flags, files) do
    regex = generate_regex(pattern, flags)
    multiple_files = length(files) > 1
    line_guard = generate_line_guard(flags)
    params = {flags, regex, multiple_files, line_guard}

    files
    |> Enum.reduce([], &grep_file(params, &1, &2))
    |> Enum.reverse()
    |> Enum.join()
  end

  defp generate_regex(pattern, flags) do
    source =
      if Enum.member?(flags, @entire_lines_only) do
        "\\A#{pattern}\n\\z"
      else
        pattern
      end

    options = if Enum.member?(flags, @ignore_case), do: @caseless, else: ""
    Regex.compile!(source, options)
  end

  defp generate_line_guard(flags) do
    if Enum.member?(flags, @invert_pattern) do
      fn line, regex, acc ->
        if String.match?(line, regex), do: throw({:next, acc})
      end
    else
      fn line, regex, acc ->
        unless String.match?(line, regex), do: throw({:next, acc})
      end
    end
  end

  defp grep_file(params, filename, acc) do
    params = Tuple.append(params, filename)

    filename
    |> File.stream!()
    |> Stream.with_index(@starting_index)
    |> Enum.reduce(acc, &grep_line(params, &1, &2))
  end

  defp grep_line(params, {line, index}, acc) do
    {flags, regex, multiple_files, line_guard, filename} = params
    line_guard.(line, regex, acc)

    if Enum.member?(flags, @filenames_only) do
      add_filename_only(filename, acc)
    else
      header = generate_header(flags, multiple_files, filename, index)
      [header <> line | acc]
    end
  catch
    {:next, acc} ->
      acc
  end

  defp add_filename_only(filename, acc) do
    filename = filename <> "\n"
    if Enum.member?(acc, filename), do: acc, else: [filename | acc]
  end

  defp generate_header(flags, multiple_files, filename, index) do
    ""
    |> maybe_add_filename(filename, multiple_files)
    |> maybe_add_line_number(flags, index)
  end

  defp maybe_add_filename(string, filename, true), do: string <> filename <> ":"
  defp maybe_add_filename(string, _filename, false), do: string

  defp maybe_add_line_number(string, flags, index) do
    if Enum.member?(flags, @line_numbers) do
      string <> to_string(index) <> ":"
    else
      string
    end
  end
end

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?