VM7WC '15 #6 Silver - Whipping Out the Old Dictionary

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

A common method of data compression, "dictionary coding", is to replace words in a text by numbers indicating their positions in a dictionary. Dynamic dictionary coding derives the dictionary from the text to be compressed. The text is processed from beginning to end, starting with an empty dictionary. Whenever a word is encountered that is in the dictionary, it is replaced by a number indicating its position in the dictionary. Whenever a word is encountered that is not in the dictionary, it appears as-is in the compressed text and is added to the end of the dictionary.

Input Specification

The first line of the input file contains a positive integer which is the number of cases to be compressed. Each case will consist of several lines containing text made of lower case letters and spaces only and will be separated from next case by a single blank line.

Output Specification

The output file should contain the cases compressed using dynamic dictionary coding as described above. Keep a single blank line between data sets as shown in input and keep all spacing and lines the same as input..

Sample Input

1
the cat chased the rat while
the dog chased the cat into the rat house

Sample Output

the cat chased 1 rat while
1 dog 3 1 2 into 1 4 house

Comments


  • 1
    PaulOlteanu  commented on Feb. 12, 2015, 11:29 p.m.

    Is it a problem with the way I read the input, or the way I'm printing?

    Input method: while True: temp = input() if len(temp) < 1: break; else: lines.append(temp)


    • 3
      moladan123  commented on April 21, 2016, 9:06 p.m.

      EOFError happens in python whenever you try to read a line when there isn't one. Try and read up on the try statement. Something like this:

      try:
          some code
      except EOFError:
          pass

      • 7
        bobhob314  commented on April 21, 2016, 10:04 p.m.

        ... and a year later, our savior moladan123 appears


  • 1
    MathBunny  commented on Feb. 12, 2015, 7:03 p.m.

    How do you know when the program ends execution???


    • 1
      MathBunny  commented on Feb. 12, 2015, 7:03 p.m.

      In the sample input there is no blank space or anything !!


      • 1
        kobortor  commented on Feb. 12, 2015, 7:13 p.m.

        Each case will consist of several lines containing text made of lower case letters and spaces only and will be separated from next case by a single blank line.

        Just keep looping until you hit a blank line.