summaryrefslogtreecommitdiff
path: root/Test/dafny1/Celebrity.dfy
blob: eed06bb116f4ca9270a502b46057ea7ecd43f6a8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// Celebrity example, inspired by the Rodin tutorial

method Pick<T>(S: set<T>) returns (t: T);
  requires S != {};
  ensures t in S;

static function Knows<Person>(a: Person, b: Person): bool;
  requires a != b;  // forbid asking about the reflexive case

static function IsCelebrity<Person>(c: Person, people: set<Person>): bool
{
  c in people &&
  (forall p :: p in people && p != c ==> Knows(p, c) && !Knows(c, p))
}

method FindCelebrity0<Person>(people: set<Person>, ghost c: Person) returns (r: Person)
  requires (exists c :: IsCelebrity(c, people));
  ensures r == c;
{
  var cc; assume cc == c;  // this line essentially converts ghost c to non-ghost cc
  r := cc;
}

method FindCelebrity1<Person>(people: set<Person>, ghost c: Person) returns (r: Person)
  requires IsCelebrity(c, people);
  ensures r == c;
{
  var Q := people;
  call x := Pick(Q);
  while (Q != {x})
    //invariant Q <= people;  // inv1 in Rodin's Celebrity_1, but it's not needed here
    invariant IsCelebrity(c, Q);  // inv2
    invariant x in Q;
    decreases Q;
  {
    call y := Pick(Q - {x});
    if (Knows(x, y)) {
      Q := Q - {x};  // remove_1
    } else {
      Q := Q - {y};  assert x in Q;  // remove_2
    }
    call x := Pick(Q);
  }
  r := x;
}

method FindCelebrity2<Person>(people: set<Person>, ghost c: Person) returns (r: Person)
  requires IsCelebrity(c, people);
  ensures r == c;
{
  call b := Pick(people);
  var R := people - {b};
  while (R != {})
    invariant R <= people;  // inv1
    invariant b in people;  // inv2
    invariant b !in R;  // inv3
    invariant IsCelebrity(c, R + {b});  // my non-refinement way of saying inv4

    decreases R;
  {
    call x := Pick(R);
    if (Knows(x, b)) {
      R := R - {x};
    } else {
      b := x;
      R := R - {x};
    }
  }
  r := b;
}

method FindCelebrity3(n: int, people: set<int>, ghost c: int) returns (r: int)
  requires 0 < n;
  requires (forall p :: p in people <==> 0 <= p && p < n);
  requires IsCelebrity(c, people);
  ensures r == c;
{
  r := 0;
  var a := 1;
  var b := 0;
  while (a < n)
    invariant a <= n;
    invariant b < a;  // Celebrity_2/inv3 and Celebrity_3/inv2
    invariant c == b || (a <= c && c < n);
  {
    if (Knows(a, b)) {
      a := a + 1;
    } else {
      b := a;
      a := a + 1;
    }
  }
  r := b;
}