Εργαστήριο Τεχνολογίας Λογισμικού
0 votes
171 views

Ο αλγόριθμος μας για την ασκηση 1 λειτουργεί για τα πρώτα test cases αλλα στα μεγαλα test cases στο τέλος βγάζει λάθος αποτέλεσμα. Θα μπορούσατε να μας στείλετε extra test cases μικρού μεγεθους για να μπορέσουμε να καταλάβουμε τι κάνουμε λάθος;

in pl1 by (190 points) | 171 views

1 Answer

+1 vote
Best answer

Από το username σου βρήκα την υποβολή σου, όπως και μία επόμενη υποβολή που δε βγάζει λάθος αποτέλεσμα, άρα υποψιάζομαι ότι το πρόβλημα λύθηκε.

Παρόλα αυτά, θα περιγράψω μία γενική μέθοδο για να κάνεις αυτό που θέλεις στην περίπτωσή μας.

  1. Έστω ότι το αρχείο in7.txt περιέχει το test case για το οποίο το πρόγραμμά μας βγάζει λάθος αποτέλεσμα. Το εν λόγω αρχείο είναι το:

    1000 3
    32 50 92 76 66 27 -67 -82 98 -93 21 -71 35 14 -60 69 -12 54 -27 44 23 87 10 56 -95 69 1 -7 -5 76 35 84 -65 91 59 95 62 36 -14 32 -54 21 57 -93 98 -70 89 -55 100 -49 -81 -39 -69 -32 71 -7 -43 -86 -100 -100 -10 -87 -11 -12 45 10 99 -38 89 73 -5 58 27 -8 -35 -90 86 85 50 45 -89 83 -69 50 50 11 -34 8 -33 -27 48 21 53 73 -99 13 -26 22 55 -18 0 53 42 15 -3 -21 38 -63 34 86 -99 -12 86 50 13 -24 -9 53 57 -58 87 61 -45 -87 -76 71 64 -20 -61 73 46 79 19 -28 17 -60 -44 -34 50 71 -8 21 -97 -25 75 -20 -68 69 -79 -79 26 42 -68 -86 -40 50 21 -79 92 -27 80 33 -15 -18 -52 25 81 27 -39 -22 24 -29 -66 -76 -64 -34 -99 -100 -78 -64 -54 -90 30 93 9 -73 55 -9 29 79 -82 -3 39 -17 -43 59 -31 -76 51 73 -36 -37 58 10 -46 -46 -100 97 -74 -57 11 14 26 -93 -63 -93 9 -62 20 -39 -43 -29 37 38 -19 -29 87 67 -85 88 -63 70 64 28 -95 22 -39 38 77 -4 14 -10 95 -88 39 -94 19 -87 1 0 82 -39 100 -64 40 64 44 56 -82 28 23 -2 88 -79 -45 -98 -80 38 45 85 -63 -20 100 24 27 -73 47 77 -29 -66 -40 -97 28 33 -97 93 -36 91 70 -89 -51 -4 51 52 -1 58 -23 7 83 22 -88 44 -74 -11 61 -46 99 37 41 -15 18 89 30 -56 -51 -78 -93 75 45 58 92 66 -36 -92 -67 26 61 26 96 -67 93 -74 34 19 -29 32 39 -90 -80 53 -9 -65 98 3 26 -26 79 7 -72 -85 -98 -99 19 68 53 33 -47 -12 63 -30 -22 -3 21 28 99 98 67 85 58 66 -62 78 18 -9 25 84 -88 64 -43 -97 -19 50 80 81 -25 65 -99 1 -7 -53 68 85 -64 57 -27 -71 39 -64 -44 0 87 -42 -66 67 -5 71 34 19 57 58 -65 38 14 99 -88 -72 -31 64 -25 34 67 92 -71 70 -91 -63 55 -56 63 -88 -55 30 85 -74 23 46 -85 23 -40 -25 86 -9 86 -91 -92 -98 13 -53 14 -33 -36 -79 -83 -4 78 35 16 97 54 27 43 -26 -73 -46 -13 16 96 6 -65 -60 23 71 82 -8 24 21 46 62 10 88 -58 -24 70 -22 -57 -17 14 -99 -23 -89 -22 -45 52 -26 -61 32 -64 90 -42 -35 -71 92 3 -63 -37 9 -56 -64 36 12 86 26 -77 31 -55 -20 38 50 88 -20 14 32 1 -56 54 68 -24 39 0 61 22 -32 -21 77 -97 95 -25 -39 33 -25 -11 92 -52 -6 -50 -10 57 32 49 66 82 -10 -97 66 92 31 75 61 -32 81 24 -82 -98 -15 1 87 -12 -54 -97 -56 -2 -66 27 65 86 -57 48 -44 55 -93 -63 -32 73 -84 67 12 56 -34 -55 -20 -90 -33 7 -77 91 -28 31 -62 -12 -3 -77 66 -67 -24 -85 -11 17 78 3 17 -98 -58 52 52 37 -40 25 25 84 63 43 -7 55 69 -33 -9 -40 -54 29 -73 46 -28 -48 -84 -22 -52 54 90 -16 -100 71 44 81 -21 7 17 -20 93 37 26 62 55 28 96 -85 -26 -37 93 -88 -19 -8 19 -72 -47 19 -90 -51 91 45 -87 -32 82 71 -65 27 39 79 -47 -93 11 -10 66 86 38 -96 -12 -90 66 -22 -42 6 92 -86 -45 -40 -55 -96 78 87 35 16 -87 16 -13 -92 23 -61 7 21 -30 39 -82 -17 35 -57 76 96 -64 -86 -73 76 68 49 -52 -36 61 55 -65 -56 -62 -57 -23 76 35 71 77 46 20 -54 0 35 83 -71 -89 9 96 3 11 -72 43 -67 74 51 -31 44 -77 -79 -35 43 -46 25 93 -47 -17 -59 50 71 13 29 -21 -78 -6 87 -38 67 10 79 -29 24 24 97 -86 13 -86 -21 74 74 87 -15 -59 -22 -93 38 83 -42 55 33 30 -23 73 12 -83 62 18 99 92 -92 -46 46 36 -13 46 -94 56 26 12 39 11 -100 -11 63 -46 -78 88 24 0 58 -79 44 -80 8 90 14 -48 11 38 13 -27 -92 56 -54 74 -87 4 77 -33 -8 93 -13 -11 -13 -100 42 0 -58 92 70 47 -49 9 3 37 -41 -68 79 -17 -95 10 -86 -76 68 56 -10 83 -42 31 -90 61 -52 75 -9 15 -64 3 85 -22 89 6 73 -47 -90 80 -27 63 -29 38 44 84 -58 -80 -4 -64 73 100 25 -79 -48 -6 -85 99 -74 44 62 -98 -36 97 -11 -55 38 -94 -13 -66 77 78 -76 -30 -89 96 69 -4 -18 37 53 -73 -77 58 38 -93 -12 97 -83 -17 9 99 7 60 62 -23 70 -9 -42 -58 -82 37 15 -90 -36 42 -50 25 86 -63 46 53 -79 39 76 95 33 65 -12 83 -46 -36 -73 -35 -67 40 84 -88 -48 22 -57 -72 -77 -78 -21 28 49 50 -61 -86 -35 94 50 -99 39 1 66 -13
    
  2. Έστω ότι ./wrong είναι το εκτελέσιμό μας, που βγάζει λάθος αποτελέσματα στο παραπάνω.

  3. Έστω ./correct ένα εκτελέσιμο που θεωρούμε σωστό. Αυτό μπορούμε να το φτιάξουμε εύκολα (με κακή πολυπλοκότητα, brute force) για αυτή την άσκηση. (Αν το "δανειστείτε" από κάποια άλλη ομάδα, φροντίστε να δανειστείτε το εκτελέσιμο και όχι το source code, γιατί φοβάμαι ότι τότε θα μπλέξετε...)

  4. Με το παρακάτω Python script (μόλις τη μάθαμε, να μην τη χρησιμοποιήσουμε;) έχετε καλές πιθανότητες να μειώσετε αυτόματα το input έτσι ώστε οι απαντήσεις του ./correct και του ./wrong να εξακολουθούν να διαφέρουν. Δείτε τι κάνει και πώς το κάνει.

    #!/usr/bin/env python3
    
    import random
    import subprocess
    
    def shrink(source, target):
      with open(source, "rt") as f:
        M, N = map(int, f.readline().split())
        A = list(map(int, f.readline().split()))
      def save(B):
        with open(target, "wt") as f:
          print(len(B), N, file=f)
          print(*B, file=f)
      def correct(B):
        save(B)
        expected = int(subprocess.check_output(["./correct", "in.txt"]))
        given = int(subprocess.check_output(["./wrong", "in.txt"]))
        return expected == given
      print("Starting from M =", M)
      more = True
      def test(B):
        nonlocal A, more
        if correct(B): return False
        print("... down to M =", len(B))
        A = B
        more = True
        return True
      while more:
        more = False
        for k in range(1, len(A)):
          B = random.sample(A, k)
          if test(B): break
      save(A)
    
    if __name__ == "__main__":
      import sys
      shrink(sys.argv[1], sys.argv[2])
    
  5. Τρέχοντας το script (προσέξτε ότι η συμπεριφορά του είναι τυχαία, αφού χρησιμοποιεί το random.sample) προκύπτει εύκολα το εξής:

    $ ./shrink.py in7.txt in.txt
    Starting from M = 1000
    ... down to M = 10
    ... down to M = 9
    ... down to M = 6
    $ cat in.txt
    6 3
    -8 34 18 87 -46 -8
    

    Πήρα σαν ./wrong τη δική σου υποβολή και σαν ./correct τη δική μου λύση.

by (9.4k points)
selected by

297 questions

287 answers

287 comments

3.1k users