Welcome, Guest. Please login or register.

October 22, 2019, 09:46:02 am

Author Topic: SDD Algorithm Contest (ALCON) | Problem 5: Supermarket Subterfuge  (Read 1319 times)  Share 

0 Members and 1 Guest are viewing this topic.

Opengangs

  • MOTM: AUG 17
  • New South Welsh
  • Forum Leader
  • ****
  • Posts: 683
  • Respect: +436
<< Prev

ALCON PROBLEM 5:
SUPERMARKET SUBTERFUGE

Week 4 asked you to write a program that allows Toby Strak to keep track of all the Nickel Man suits in the facility by introducing the data into an array. IIf you missed this problem, you can always do them in your spare time and get feedback in your code.

You can find the sample answer to Week 4's problem, as well as everything Week 4 related here.

Please make sure you've read the rules here.

Week 5 question:

The two supermarket giants, Kohls and Fleecies, are in kahoots with each other. With new competitors, BELDI and YGA entering the market, they’re determined to keep their current power. To prevent the government from getting suspicious, Kohls and Fleecies send each other coded messages every day.

The real message is deciphered by taking the first two characters of each word in the coded message and putting them together. E.g. ‘Blizzard ueda Location tuesday sTorm entraps Top nine ghurkas t.’ → ‘BlueLotusTenTonight.’

Write a program that can decode the messages. It should accept the encrypted string as an input parameter, and return a decrypted string in the output.

Notes: In pseudocode (which is a little outdated at times), strings are arrays of characters. A “word” is separated by a space on both sides (unless it’s the first or last word, in which case there’s only one space on the right or left or it).

Optional challenge add-on (+2 marks)
You’ve figured out how to intercept the messages before they reach the other party. Sabotage them by deleting every other word in the string.

You’ll be marked on correctness, efficiency, and defensive programming.

Learning objectives for the week:

-> String manipulation.

Marking guidelines

Don't forget to login or register an account to submit your answer!

Good luck, and as always, happy algorithming!
« Last Edit: June 25, 2018, 01:27:58 am by Opengangs »
2017: English (Advanced): 86 | Mathematics: 94 | Mathematics (Extension 1): 45 | Biology: 84 | Business Studies: 87 | Software Design and Development: 88

2018: Computer Science @ UNSW

RuiAce

  • ATAR Notes Lecturer
  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 8532
  • "All models are wrong, but some are useful."
  • Respect: +2382
Re: SDD Algorithm Contest (ALCON) | Problem 5: Supermarket Subterfuge
« Reply #1 on: June 11, 2018, 11:11:41 am »
+6
Code: (rui_is_bored.c) [Select]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INITIAL_SIZE 32

static int riskOverFlow(char* msg) {
   return (sizeof(char)*(strlen(msg)+strlen("'\0'")+2) > sizeof(msg)) ? 1 : 0;
}

int main (int argc, char **argv) {
   char *msg = malloc(INITIAL_SIZE*sizeof(char));
   if (msg == NULL) {
      fprintf(stderr, "ERROR: Failed to create dynamic string.\n");
      exit(EXIT_FAILURE);
   }
   msg[0] = '\0';

   for (int i = 1; i < argc; i++) {
      if (riskOverFlow(msg)) {
         char* tmp = realloc(msg, sizeof(msg)*2);
         if (tmp == NULL) {
            fprintf(stderr,"ERROR: Failed to increase length of dynamic string.\n");
            exit(EXIT_FAILURE);
         }
         msg = tmp;
      }
      strncat(msg, argv[i], 2);
   }
   printf("The decoded message is %s\n", msg);
   free(msg);
   return EXIT_SUCCESS;
}

// Yeah, I'm too lazy to do things the file-handling way because I don't learn that until next sem.


Code: (rui_should_go_study_but_is_feeling_evil_rn.c) [Select]
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char **argv) {
   for (int i = 1; i < argc; i += 2)
      printf("%s ", argv[i]);
   return EXIT_SUCCESS;
}
« Last Edit: June 11, 2018, 07:54:03 pm by RuiAce »

JTrudeau

  • MOTM: APR 18
  • Trendsetter
  • **
  • Posts: 109
  • Master of the Meeses
  • Respect: +89
Re: SDD Algorithm Contest (ALCON) | Problem 5: Supermarket Subterfuge
« Reply #2 on: June 11, 2018, 04:56:13 pm »
+5
... I guess we didn't technically specify that algorithms must be written in pseudocode.
Well played, Sir, well played :D

Now how am I gonna mark this one
Data Science, Finance || University of Sydney
== First in State for Software Design and Development 2017 ==
Advanced English | Maths Extension 1 | Maths Extension 2 | Economics | Software Design & Development | Chemistry

cthulu

  • Trailblazer
  • *
  • Posts: 35
  • Respect: +1
Re: SDD Algorithm Contest (ALCON) | Problem 5: Supermarket Subterfuge
« Reply #3 on: June 17, 2018, 06:37:33 pm »
+2
Code: [Select]
BEGIN [u]OperationDecodeMessage(string input) [/u]

SET count to 0
SET tally to 0
SET decodedString to “”

WHILE (count < length of input) DO
IF (input[count] == “ “) THEN
SET secondaryCount to count + 1

WHILE (secondaryCount < length of input) DO
SET newString to newString + input[secondaryCount]
INCREMENT secondaryCount by 1
END WHILE
OperationDecodeMessage(newString)
ELSE
IF (tally != 2) THEN
SET decodedString to decodedString + input[count]
INCREMENT tally by 1
END IF
END IF

INCREMENT count by 1
END WHILE

[u]END OperationDecodeMessage[/u]

anomalous

  • Adventurer
  • *
  • Posts: 7
  • Respect: 0
Re: SDD Algorithm Contest (ALCON) | Problem 5: Supermarket Subterfuge
« Reply #4 on: June 23, 2018, 09:37:22 pm »
0
65 lines and much time later... Hopefully NESA doesn't ask anything like this in the actual exam.

Code: [Select]
BEGIN [u]Decoder[/u](encoded_string)
encoded_array = []
array_index = 0
FOR i = 0 TO i = length of encoded_string - 1
IF encoded_string(i) != " " THEN
encoded_array(array_index) = encoded_array(array_index) + encoded_string(i)
ELSE THEN
array_index = array_index + 1
ENDIF
NEXT i

decoded_string = ""
FOR i = 0 TO i = length of encoded_array - 1
IF length of encoded_array(i) <= 2 THEN
decoded_string = decoded_string + encoded_array(i)
ELSE IF length of encoded_array(i) > 2 THEN
decoded_string = decoded_string + Extract(encoded_array(i), 0, 1)
ENDIF
NEXT i

RETURN decoded_string
END [u]Decoder[/u]

BEGIN [u]Extract[/u](string, start, end)
extracted = ""
i = start

WHILE i <= end
extracted = extracted + string(i)
i = i + 1
ENDWHILE

RETURN extracted
END [u]Extract[/u]

BEGIN [u]Sabotage[/u](message)
message_array = []
array_index = 0
FOR i = 0 TO i = length of message - 1
IF encoded_string(i) != " " THEN
message_array(array_index) = message_array(array_index) + message(i)
ELSE THEN
array_index = array_index + 1
ENDIF
NEXT i

sabotaged_message_array = []
array_index = 0
FOR i = 0 TO i = length of message_array - 1 STEP 2
sabotaged_message_array = message_array(i)
NEXT i

sabotaged_message = ""
FOR i = 0 to i = length of sabotaged_message_array - 1
IF i = length of sabotaged_message_array - 1 THEN
sabotaged_message = sabotaged_message + sabotaged_message_array(i)
ELSE THEN
sabotaged_message = sabotaged_message + sabotaged_message_array(i) + " "
ENDIF
NEXT i

RETURN sabotaged_message
END [u]Sabotage[/u]
« Last Edit: June 24, 2018, 07:14:24 pm by anomalous »
2018 ATAR: 98.10

HSC 2018:
> English (Advanced) - 93
> Mathematics - 97
> Mathematics Extension 1 - 49
> Software Design and Development - 95
> Ancient History - 91
> Japanese Continuers - 83

Opengangs

  • MOTM: AUG 17
  • New South Welsh
  • Forum Leader
  • ****
  • Posts: 683
  • Respect: +436
Re: SDD Algorithm Contest (ALCON) | Problem 5: Supermarket Subterfuge
« Reply #5 on: June 25, 2018, 01:43:58 am »
0
ALCON WEEK 5 FEEDBACK

Week 5 was definitely one of the more challenging questions to write in pseudocode with the average mark being 4/7. Both submissions did quite well, but could have provided a more thoughtful layout and considered a 2 dimensional array. Other methods were fine - but it may have been less efficient.

Everything you need for Week 5's problem can be found here. You can find your own entry and read the comments and feedback.

In the meantime, don't forget to check out Week 6's question.

Sample answer:
(note [u ][/u] tags mean that the code was underlined.)
Sample answer
Code: [Select]
BEGIN [u]Alcon5[/u]()

    // Main question

    SET max TO 256 // buffer to avoid overflow
    GET string FROM user input
    DECLARE Integer Index, Index2, Counter
    SET Index, Index2, Counter TO 0

    DECLARE char words[max][max]
    SET words[max][max] TO NULL

    // Iterate through entire string until null terminator
    WHILE Index < length of string DO
        IF string[Index] == ‘ ‘ THEN
            Increment Counter
            SET Index2 TO 0
        END IF

        ELSE
            SET words[Index2][Counter] TO string[Index]
            Increment Index2
        END ELSE

        Increment Index
    END WHILE

    SET Index, Index2 TO 0
    WHILE Index < Counter DO

    // while we still have more characters
    WHILE words[Index2][Index] NOT NULL DO
        IF Index2 NOT 0 OR Index2 NOT 1 THEN

            // Challenge
            words[Index2][Index] = NULL
        END IF

        ELSE
            DISPLAY words[Index2][Index]
        END ELSE

        Increment Index2
    END WHILE
     
    Increment Index
    Index2 = 0
    END WHILE       
END [u]Alcon5[/u]

Good luck everyone!
2017: English (Advanced): 86 | Mathematics: 94 | Mathematics (Extension 1): 45 | Biology: 84 | Business Studies: 87 | Software Design and Development: 88

2018: Computer Science @ UNSW