Dynamic associative array, to hold many values per key

[Logesh Pillay]

On Wednesday, 30 October 2013 at 01:14:53 UTC, Daniel Davidson 
wrote:
> On Tuesday, 29 October 2013 at 18:02:46 UTC, Logesh Pillay 
> wrote:
>> On Sunday, 20 October 2013 at 16:08:50 UTC, bearophile wrote:
>>> Logesh Pillay:
>>>
>>>> Thanks.  Coming to D from python, I have to say D's tuples 
>>>> look difficult.  I'm going to see how far I can get with 
>>>> structs writing my sudoku solver.
>>>
>>> I think defining the full correct hashing protocol manually 
>>> for structs is harder than using tuples.
>>>
>>> There were many discussions to improve and simplify D tuples, 
>>> but nothing has come out of them yet.
>>>
>>> Bye,
>>> bearophile
>>
>> This thread is dead.  But I'm just posting to say using struct 
>> as a key to an associative array worked fine without opHash 
>> and other special methods.  Does that mean (Alexandrescu, ch 
>> 4.4.7) that the array retrieves slower (The sudoku solver 
>> seems fast enough though) If so, there is an obvious way to 
>> write (x, y) as an int: 10x + y
>
> What do you mean when you say "using a struct as a key to an 
> associative array worked fine without opHash and other special 
> methods? Do you have sample code showing it work?

Here's the program. Sorry, it's long and I don't see the 
enclosing code labels.

import std.stdio;

struct Kie {int a, b;}

int[][Kie] possibles;
int[2][][Kie] associates;

void print_grid(ref int[][] ar) {
   foreach (y; 0 .. 9) {
     foreach (x; 0 .. 9)
       if (ar[y][x])
         writef("%s ", ar[y][x]);
       else writef(". ");
     writeln;
   }
   writeln;
}

void removeElem (int n, ref int[] lst) {
   foreach (i, v; lst)
     if (v == n) {
       lst = lst[0 .. i] ~ lst[i+1 .. $];
       break;
     }
}

void setup (ref int[][] ar) {
   foreach (y; 0 .. 9)
     foreach (x; 0 .. 9)
       if (!ar[y][x]) {
         Kie k = {y, x};
         foreach (i; 0 .. 9) {
           if (i <> x)
             associates[k] ~= [y, i];   //ass's in column
           if (i <> y)
             associates[k] ~= [i, x];   //ass's in row
         }
         foreach(c; 3 * (y/3) .. 3 + (3 * (y/3)))
           foreach(r; 3 * (x/3) .. 3 + (3 * (x/3)))
             if ((c <> y) && (r <> x))
               associates[k] ~= [c, r]; //ass's in 9-block
         int[10] used;                  // setup possible values
         foreach (i; associates[k])
           if (ar[i[0]][i[1]])
             used [ar[i[0]][i[1]]] = 1;
         foreach (i; 1 .. 10)
           if (!used[i])
             possibles[k] ~= i;
     }
}

void eliminate (ref int[][] ar) {
   bool ansFound = true;
   while (ansFound) {
     ansFound = false;
     foreach (y; 0 .. 9)
       foreach (x; 0 .. 9)
         if (!ar[y][x]) {
           Kie k = {y, x};
           if (possibles[k].length == 1) {
             int ans = ar[y][x] = possibles[k][0];
             ansFound = true;
             foreach (i; associates [k])
               if (!ar[i[0]][i[1]]) {
                 Kie m = {i[0], i[1]};
                 removeElem (ans, possibles[m]);
               }
           }
         }
   }
}

void backtrack (ref int[][] ar) {
   uint count;
   bool ansFound = false;
   foreach (y; 0 .. 9)
     foreach (x; 0 .. 9)
       if (!ar[y][x])
         ++count;
   if (count) {
     int[2][] lst;
     foreach (y; 0 .. 9)
       foreach (x; 0 .. 9)
         if (!ar[y][x])
           lst ~= [y, x];

   void b2 (int i) {
     if (i == count) {
       ansFound = true;
       return;
     }
     if (!ansFound) {
       int c = lst[i][0],
           r = lst[i][1];
       Kie k = {c, r};
       foreach (v; possibles[k]) {
         if (ansFound)
           break;
         bool valid = true;
         foreach (s; associates[k])
           if (ar[s[0]] [s[1]] == v) {
             valid = false;
             break;
           }
         if (valid) {
           ar[c][r] = v;
           b2(i+1);
           if (!ansFound)
             ar[c][r] = 0;
         }
       }
     }
   }

   b2(0);
   }
}

void main() {
   /*
  int[][] arr = [
  [0, 0, 3, 0, 2, 0, 6, 0, 0], //easy
  [9, 0, 0, 3, 0, 5, 0, 0, 1],
  [0, 0, 1, 8, 0, 6, 4, 0, 0],
  [0, 0, 8, 1, 0, 2, 9, 0, 0],
  [7, 0, 0, 0, 0, 0, 0, 0, 8],
  [0, 0, 6, 7, 0, 8, 2, 0, 0],
  [0, 0, 2, 6, 0, 9, 5, 0, 0],
  [8, 0, 0, 2, 0, 3, 0, 0, 9],
  [0, 0, 5, 0, 1, 0, 3, 0, 0]];

   int [][] arr = [
   [7, 3, 0, 9, 0, 0, 5, 0, 0],          //hard
   [0, 0, 5, 0, 8, 0, 0, 3, 0],
   [0, 0, 6, 5, 0, 4, 0, 9, 0],
   [0, 0, 0, 0, 0, 0, 3, 5, 6],
   [3, 0, 0, 0, 0, 0, 0, 0, 1],
   [1, 5, 8, 0, 0, 0, 0, 0, 0],
   [0, 7, 0, 3, 0, 5, 6, 0, 0],
   [0, 4, 0, 0, 9, 0, 2, 0, 0],
   [0, 0, 2, 0, 0, 6, 0, 1, 3]];
  */
   int [][] arr = [                    // harder
   [8, 0, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 3, 6, 0, 0, 0, 0, 0],
   [0, 7, 0, 0, 9, 0, 2, 0, 0],
   [0, 5, 0, 0, 0, 7, 0, 0, 0],
   [0, 0, 0, 0, 4, 5, 7, 0, 0],
   [0, 0, 0, 1, 0, 0, 0, 3, 0],
   [0, 0, 1, 0, 0, 0, 0, 6, 8],
   [0, 0, 8, 5, 0, 0, 0, 1, 0],
   [0, 9, 0, 0, 0, 0, 4, 0, 0]];

   print_grid(arr);
   setup(arr);
   eliminate (arr);
   backtrack(arr);
   print_grid(arr);
}