PE1 (AY23/24)

Problems

1. Mirror

My solution is to use char** cs1010_read_word_array(size_t k).

#include "cs1010.h"

int main()
{
  size_t n = cs1010_read_size_t();
  char **left_half = cs1010_read_word_array(n);
  if (left_half == NULL)
  {
    return 1;
  }
  for (size_t i = 0; i < n; i += 1)
  {
    char *temp = left_half[i];
    long length = 0;
    while (*temp != '\0')
    {
      putchar(*temp);
      length += 1;
      temp += 1;
    }
    for (long j = length - 1; j >= 0; j -= 1)
    {
      putchar(left_half[i][j]);
    }
    cs1010_println_string("");
  }
  for (size_t i = 0; i < n; i += 1)
  {
    free(left_half[i]);
  }
  free(left_half);
}

2. Nigh

This question reminds us the importance of counting the frequency of each digit in a number, which appears in Ex3 Q4 before.

3. Alternate

This question teaches us an important point: when traversing from end to the start of a string, it is always recommended to cast the loop index to be long! Since size_t will always be 0 and we still need to zero index element, so it will be hard for us to define when to stop!

After reading the comments, I feel like my solution is a bit more elegant.

char *alternate(const char *w1, const char *w2)
{
  size_t len1 = length_of(w1);
  size_t len2 = length_of(w2);
  char *new_word = calloc(len1 + len2 + 1, sizeof(char));
  long temp1 = (long)len1 - 1;
  long temp2 = (long)len2 - 1;
  bool at_w2 = true;
  bool change_di = true;
  for (long i = (long)len1 + (long)len2 - 1; i >= 0; i -= 1)
  {
    if (temp1 == -1 || temp2 == -1)
    {
      change_di = false;
    }
    if (at_w2)
    {
      new_word[i] = w2[temp2];
      if (temp2 >= 0)
      {
        temp2 -= 1;
      }
    }
    else
    {
      new_word[i] = w1[temp1];
      if (temp1 > 0)
      {
        temp1 -= 1;
      }
    }
    if (change_di)
    {
      at_w2 = !at_w2;
    }
  }
  new_word[len1 + len2 - 1] = '\0';
  return new_word;
}    

4. Grammar

This is actually a Sliding Window problem.

But I use a recursive method when doing this question at the first time

bool grammar_check(size_t start, size_t end, char *word)
{
  if (start == end)
  {
    return step_3(word[start]);
  }
  if (word[start] == '%' && word[end] == '#')
  {
    return grammar_check(start + 1, end - 1, word);
  }
  if (word[start] == '@' && word[start + 1] == '@')
  {
    return grammar_check(start + 2, end, word);
  }
  return false;
}

5. Pirate

This problem is similar to Ex5 Q6

1. For Captains, we notice that the captains are all in the diagonal of the 2-D matrix whose value is not -1 (Suppose I initialise all the elements to -1)

2. For counting crew numbers, we use the recursive thinking, start from the captain, once we find a crew, treat the crew as a new "captain" and find its crew. Until we have iterated every row in each function call. We are done

After reading the comments, I feel the method using a 2-D array is more elegant.

#include "cs1010.h"

void free_mem(size_t start, size_t end, long **tar)
{
  for (size_t i = start; i < end; i += 1)
  {
    free(tar[i]);
  }
  free(tar);
}

long **init_canva(size_t num)
{
  long **canva = calloc(num, sizeof(long *));
  if (canva == NULL)
  {
    return NULL;
  }
  for (size_t i = 0; i < num; i += 1)
  {
    canva[i] = calloc(num, sizeof(long));
    if (canva[i] == NULL)
    {
      free_mem(0, i, canva);
      return NULL;
    }
  }
  for (size_t i = 0; i < num; i += 1)
  {
    for (size_t j = 0; j < num; j += 1)
    {
      canva[i][j] = -1;
    }
  }
  return canva;
}

void update_super(long *super, long **canva, size_t num)
{
  for (size_t i = 0; i < num; i += 1)
  {
    canva[i][super[i]] = super[i];
  }
}

void count_crew(long captain, size_t num, long **canva, long *count, long *super)
{
  for (size_t i = 0; i < num; i += 1)
  {
    if ((long)i != captain && canva[i][super[i]] == captain)
    {
      *count += 1;
      count_crew((long)i, num, canva, count, super);
    }
  }
}

long count_captains(long **canva, size_t num)
{
  long count = 0;
  for (size_t i = 0; i < num; i += 1)
  {
    if (canva[i][i] != -1)
    {
      count += 1;
    }
  }
  return count;
}

int main()
{
  size_t num = cs1010_read_size_t();
  long *super = cs1010_read_long_array(num);
  long **canva = init_canva(num);
  if (canva == NULL)
  {
    return 1;
  }
  update_super(super, canva, num);
  cs1010_println_long(count_captains(canva, num));
  for (size_t i = 0; i < num; i += 1)
  {
    long count = 0;
    if (canva[i][i] != -1)
    {
      cs1010_print_size_t(i);
      cs1010_print_string(" ");
      count_crew((long)i, num, canva, &count, super);
      cs1010_println_long(count + 1);
    }
  }
  for (size_t i = 0; i < num; i += 1)
  {
    free(canva[i]);
  }
  free(canva);
}