problems.cs

using System.Text.RegularExpressions;

/*
For this exercise, a word is any sequence of uppercase or lowercase characters from the Latin alphabet
(A - Z, a - z). A sentence is a sequence of characters that ends with a period (.) or question mark (?).
Write a program that reads a file input.txt and writes out all words that occur in at least two
sentences. Ignore case: "Alice" and "alice" are the same word. Write the words in alphabetical order,
one per line, all in lowercase. For each word, indicate how many sentences it occurs in.
Your program should be reasonably efficient. (Specifically, if the input contains N distinct words, your
program's expected running time should be less than O(N^2).)

For example, suppose that input.txt contains
Alice was beginning to get very tired of sitting by her sister on the
bank, and of having nothing to do. Once or twice she had peeped into
the book her sister was reading, but it had no pictures or conversations
in it. "And what is the use of a book," thought Alice, "without pictures
or conversations?" So she was considering in her own mind whether the
pleasure of making a daisy-chain would be worth the trouble of getting
up and picking the daisies.

The program will print

a (2)
alice (2)
and (3)
book (2)
conversations (2)
her (3)
in (2)
of (3)
or (2)
pictures (2)
she (2)
sister (2)
the (4)
was (3)

Hints:
If you read the input into a single string, you can break it into sentences by calling .Split() with
appropriate argument(s). To find the words in each sentence, you could call the Regex.Matches()
method. That will return an enumeration of Match objects, each with a Value property containing a
matched word. Alternatively, you could extract words by gathering characters in a loop.
*/

HashSet<string> UniqueWords(string sentence)
{
  return [.. new Regex("[a-z]+").Matches(sentence.ToLowerInvariant()).Select(m => m.Value)];
}

void AddWords(Dictionary<string, int> counts, HashSet<string> words)
{
  foreach (var word in words)
  {
    counts.TryGetValue(word, out int count);
    counts[word] = count + 1;
  }
}

void Problem1()
{
  string[] sentences = File.ReadAllText(@"input.txt").Split(['.', '?']);

  Dictionary<string, int> counts = [];
  foreach (var sentence in sentences)
    AddWords(counts, UniqueWords(sentence));

  foreach (var (word, count) in counts.Where(kv => kv.Value >= 2).OrderBy(kv => kv.Key))
    Console.WriteLine($"{word} ({count})");
}

/*
A certain professor can type very quickly, but often makes mistakes. Specifically, whenever he
types a letter from A to Z, he might type the actual letter he intended, or the next letter, or the
previous letter. For example, if he wants to type DOG, he might actually type COH, since C
comes before D, and H comes after G. However, he never makes two mistakes in a row, so he
will not type CPG. Furthermore, his mistakes never wrap around: when he means to type A, he
will never type Z, and vice versa.

Write a program that takes a single command-line argument: a word that the professor typed. The
program should write all the words that he might have intended to type. The given word will
contain only characters in the range from A to Z. You may write the output words in any order.

For example:
$ dotnet run COH
BOG
BOH
BOI
CNH
COG
COH
COI
CPH
DOG
DOH
DOI

Hints:
You don't need to write a Main() method. args[0] will contain the command-line argument.
If c is an ASCII character, then ((char) (c + 1)) is the following character, and ((char) (c - 1)) is
the preceding character.
*/

void Mistakes(string word)
{
  void go(int i, string prefix, bool last_mistake = false)
  {
    if (i == word.Length)
    {
      Console.WriteLine(prefix);
      return;
    }

    char letter = word[i];
    int offset = last_mistake ? 0 : 1;
    for (int c = Math.Max('A', letter - offset); c <= Math.Min('Z', letter + offset); c++)
      go(i + 1, prefix + (char)c, c != letter);
  }

  go(0, "");
}

// Mistakes(args[1]);

/*
A company would like to open a series of restaurants along a road. The possible locations for the
restaurants are d1, d2, ..., dn, which are distances from the start of the road in kilometers. At each
location the company may open either a single restaurant, or none. Every two restaurants must be
separated by at least 50 km.

The numbers p1, p2, ..., pn represent the profit (in millions of Kč) that the company will earn if it opens a
restaurant at each location. The company would like to maximize its profit.

For example, suppose that
• d1 = 0, d2 = 40, d3 = 60, d4 = 100
• p1 = 3, p2 = 4, p3 = 5, p4 = 7

An optimal solution is to open restaurants at distances d2 = 40 and d4 = 100. 100 - 40 ≥ 50, so the
restaurants are far enough apart. The company will earn p2 + p4 = 11 million Kč, the maximum possible.

Write a function void plan(int[] distances, int[] profits) that takes arrays with the values di
and pi. The function should write out the maximum total profit that can be achieved, along with the
distances at which restaurants should be opened. (If more than one solution can achieve the maximum
possible profit, you may print any.)

For example,
plan([0, 40, 60, 100], [3, 4, 5, 7]);

will write

total profit = 11
40 100

Use bottom-up dynamic programming for an efficient (polynomial-time) solution.

Hints:
Here is one possible approach. Let total[i] be the maximum profit that the company can earn if it
opens a restaurant at location i, and also possibly at locations after i. If you know the value of total[j]
for all j > i, you can calculate total[i]. To do this, consider all possible locations j (if any) where you
might open the next restaurant after i. Be sure only to consider locations that are at least 50 km from
distances[i].

When you have finished filling in the total array, you will need to scan it to find its largest value, which
is the location where the company should open its first restaurant. (This might not be location 0.)

You may also want to fill in a second array where for each i you record the index next[i] of the next
restaurant to open in order to achieve the profit total[i].

Another example:
plan([0, 40, 70, 110, 140, 150, 180], [3, 2, 3, 7, 3, 5, 2]);

will write

total profit = 12
0 110 180
*/

void Plan(int[] distances, int[] profits)
{
  if (distances.Length != profits.Length)
    throw new ArgumentException();

  const int MIN_SPAN = 50;

  int[] total = new int[profits.Length];
  int[] next = new int[profits.Length];
  int bestIx = profits.Length - 1; // Position of the best result

  for (int i = total.Length - 1; i >= 0; i--)
  {
    int distance = distances[i];
    int bestTotal = 0;
    next[i] = -1;
    for (int j = i + 1; j < total.Length; j++)
    {
      if (distances[j] >= distance + MIN_SPAN && total[j] > bestTotal)
      {
        bestTotal = total[j];
        next[i] = j;
      }
    }
    total[i] = bestTotal + profits[i];
    if (total[i] > total[bestIx])
      bestIx = i;
  }

  // Reconstructing the output
  Console.WriteLine($"total profit = {total[bestIx]}");
  int ix = bestIx;
  while (bestIx != -1)
  {
    Console.Write($"{distances[bestIx]} ");
    bestIx = next[bestIx];
  }
  Console.WriteLine();
}

// Plan([0, 40, 70, 110, 140, 150, 180], [3, 2, 3, 7, 3, 5, 2]);