Constraint issue: pick number within array with specific number match

Viewed 765

This is the problem from my last interview as following:

Q. (Constrained randomization) Consider the lottery rules on this page

  • Given the set of six numbers that will win the jackpot as input, try and implement the constraint to generate a set of numbers that wins the second-highest award, matching exactly 5 numbers out of the six jackpot numbers.

The Following are my code link to EDA playground:

Test Bench:

module tb;
    initial begin
      Pick    p = new();
      p.randomize();

      $display("\nPicked result:");
      for (int i=0; i<`NUM_JACKPOT; i++)
        $write("%0d ", p.jackpot_result[i]);
      $write("\n");
      
    end
endmodule

Design Code:

`define NUM_JACKPOT  6

class Lottery;
  randc int six_jackpot_nums[`NUM_JACKPOT];
  
  constraint rand_jackpot {
    foreach (six_jackpot_nums[i])
      six_jackpot_nums[i] inside {[1:49]};
  }
endclass

class Pick;

  randc int six_jackpot_nums[`NUM_JACKPOT];
  randc int jackpot_result  [`NUM_JACKPOT];
        int award_2nd_hi = `NUM_JACKPOT -1;
 
  function pre_randomize();
    Lottery l = new();
    l.randomize();
    $display("Jackpot bingo:");
    for (int i=0; i<`NUM_JACKPOT; i++) begin
      six_jackpot_nums[i] = l.six_jackpot_nums[i];
      $write("%0d ", l.six_jackpot_nums[i]);
    end
  endfunction 
  
  constraint pick_jackpot{
    foreach (jackpot_result[i])
      jackpot_result[i] inside {[1:49]};      
    award_2nd_hi == (match(jackpot_result[0])+match(jackpot_result[1])+match(jackpot_result[2])+match(jackpot_result[3])+match(jackpot_result[4])+match(jackpot_result[5]));
  }
  
  function int match(int v);
    int tmp[$];
    tmp = six_jackpot_nums.find(x) with (x == v);
    if(tmp.size != 0) return 1;
    return 0;
  endfunction
  
  
endclass

For the current status, I can successfully create the Six Number Jackpot. Yet, as I creating the 2nd highest pair of numbers, I got the conflict. Please advice.

Result:

xmsim: *W,RNDOCS: These constraints contribute to the set of conflicting constraints:

    award_2nd_hi == (match(jackpot_result[0])+match(jackpot_result[1])+match(jackpot_result[2])+match(jackpot_result[3])+match(jackpot_result[4])+match(jackpot_result[5])); (./design.sv,31)

xmsim: *W,RNDOCS: These variables contribute to the set of conflicting constraints:


Var_Name                          Type   Status        Current_Value          Source                 
-----------------------------------------------------------------------------------------------------
award_2nd_hi                      (S32)  STATE VAR     5 (0x5)                ./design.sv ; line 16
jackpot_result[0]                 (S32)  SOLVED EARLY  32 (0x20)              ./design.sv ; line 15
jackpot_result[1]                 (S32)  SOLVED EARLY  47 (0x2f)              ./design.sv ; line 15
jackpot_result[2]                 (S32)  SOLVED EARLY  21 (0x15)              ./design.sv ; line 15
jackpot_result[3]                 (S32)  SOLVED EARLY  40 (0x28)              ./design.sv ; line 15
jackpot_result[4]                 (S32)  SOLVED EARLY  1 (0x1)                ./design.sv ; line 15
jackpot_result[5]                 (S32)  SOLVED EARLY  27 (0x1b)              ./design.sv ; line 15
match( .v( jackpot_result[0] ) )  (S32)  SOLVED EARLY  0 (0x0)                ./design.sv ; line 31
match( .v( jackpot_result[1] ) )  (S32)  SOLVED EARLY  1 (0x1)                ./design.sv ; line 31
match( .v( jackpot_result[2] ) )  (S32)  SOLVED EARLY  0 (0x0)                ./design.sv ; line 31
match( .v( jackpot_result[3] ) )  (S32)  SOLVED EARLY  0 (0x0)                ./design.sv ; line 31
match( .v( jackpot_result[4] ) )  (S32)  SOLVED EARLY  0 (0x0)                ./design.sv ; line 31
match( .v( jackpot_result[5] ) )  (S32)  SOLVED EARLY  0 (0x0)                ./design.sv ; line 31


Jackpot bingo:
31 49 43 24 47 8
Picked result:
0 0 0 0 0 0 
3 Answers

Here is a simpler approach which avoids all the warnings (and errors on other simulators). Randomly generate the set of 6 winners. Also, randomly pick one of the winners to be replaced with a losing number. Using post_randomize, create the set of losers, then randomly pick one of them and replace one of the winners.

`define NUM_JACKPOT  6

class Lottery;
    rand  int six_jackpot_nums[`NUM_JACKPOT];
          int jackpot_result  [`NUM_JACKPOT];
          int losers          [$];
    rand int unsigned idx;

    function void post_randomize;
        for (int i=1; i<50; i++) begin
            if (!(i inside {six_jackpot_nums})) losers.push_back(i);
        end
        losers.shuffle();
        for (int i=0; i<`NUM_JACKPOT; i++) begin
            jackpot_result[i] = (i == idx) ? losers[0] : six_jackpot_nums[i];
        end
    endfunction 

    constraint rand_jackpot {
        unique {six_jackpot_nums};
        foreach (six_jackpot_nums[i]) six_jackpot_nums[i] inside {[1:49]};
        idx inside {[1:`NUM_JACKPOT]};
    }
endclass

module tb;
    Lottery lot;
    initial begin
        lot = new();
        void'(lot.randomize());
        $display("\nPicked result:");
        for (int i=0; i<`NUM_JACKPOT; i++) $write("%0d ", lot.six_jackpot_nums[i]);
        $display("\nJackpot bingo:");
        for (int i=0; i<`NUM_JACKPOT; i++) $write("%0d ", lot.jackpot_result  [i]);
        $display;
    end
endmodule

Example output:

Picked result:
48 4 46 3 17 16 
Jackpot bingo:
48 4 21 3 17 16 

Here, 46 is replaced by 21.


To address the randc issue noted in another answer, use the unique constraint keyword.

The declaration randc won't guarantee the array elements are unique in single randomization. So I add a constraint unique_cons to address this issue.

`define NUM_JACKPOT  6

class Lottery;
  rand int six_jackpot_nums[`NUM_JACKPOT];
  rand int jackpot_result  [`NUM_JACKPOT];
  rand int missed;
  
  constraint unique_cons {
    foreach (six_jackpot_nums[i])
      foreach(six_jackpot_nums[j])  
        if(i!=j) six_jackpot_nums[i]!=six_jackpot_nums[j];      
  }
  
  constraint valid_cons {
    foreach (six_jackpot_nums[i]){
      six_jackpot_nums[i] inside {[1:49]};
      jackpot_result[i] inside {[1:49]};
    }
  }
  constraint missed_cons {
    missed inside {[0:`NUM_JACKPOT-1]} ;    
       
  }
  constraint rand_jackpot {
    foreach (six_jackpot_nums[i])
      if(i==missed) 
        ~(jackpot_result[i] inside {six_jackpot_nums});
      else 
        jackpot_result[i] == six_jackpot_nums[i];
  } 
  
endclass

The results:

Jackpot bingo:
30 44 12 37 1 22 
Picked result:
30 44 12 37 1 9 
Jackpot bingo:
40 12 20 46 8 2 
Picked result:
40 12 20 5 8 2 
Jackpot bingo:
29 23 13 41 48 28 
Picked result:
29 39 13 41 48 28 
Jackpot bingo:
8 14 35 19 28 39 
Picked result:
8 20 35 19 28 39 

Good call from the 1st answer, unique constraint keyword was enabled in systemverilog-2012.

You should look for a solution avoiding pre/post_randomize() if at all possible. This makes it much easier to override or add more constraints when all constraints and random variables are solved at once.

parameter int JACKPOT_NUM = 6;

class Lottery;
  rand int six_jackpot_nums[JACKPOT_NUM];
  rand int pick_result_nums[JACKPOT_NUM];
  
  constraint jack_rand {
    unique {six_jackpot_nums};
    foreach(six_jackpot_nums[i]) six_jackpot_nums[i] inside {[1:49]};
    unique {pick_result_nums};
    foreach(pick_result_nums[i]) pick_result_nums[i] inside {[1:49]};
  }
  constraint pick5 {
    pick_result_nums.sum() with (int'(item == six_jackpot_nums[item.index])) == 5;
  }
 
endclass

module tb;
    initial begin
      static Lottery l = new();
      repeat(3) begin
        assert(l.randomize());
        $display("\nBingo result:");
        foreach(l.six_jackpot_nums[i])
          $write("%0d ", l.six_jackpot_nums[i]);
        $display("\nPicked result:");
        foreach(l.six_jackpot_nums[i])
          $write("%0d ", l.pick_result_nums[i]);
        $write("\n");
      end
      
    end
endmodule

Doing it this way lets you add more constraints, like "the picked number that does not match must be one greater than the jackpot number". That of course leaves 49 from being chosen as the missed jackpot number, but it also leaves out missing any the first of any two sequential jackpot numbers.

Related