• Logesh Pillay (12/12) Oct 20 2013 I want an associative array in d programming language. The key is
• Andrej Mitrovic (3/15) Oct 20 2013 Try:
• bearophile (11/16) Oct 20 2013 In D structs/classes usually start with an upper case letter:
• Logesh Pillay (4/21) Oct 20 2013 Thanks. Coming to D from python, I have to say D's tuples look
• bearophile (7/10) Oct 20 2013 I think defining the full correct hashing protocol manually for
• Logesh Pillay (7/17) Oct 29 2013 This thread is dead. But I'm just posting to say using struct as
• Daniel Davidson (4/25) Oct 29 2013 What do you mean when you say "using a struct as a key to an
• Logesh Pillay (151/178) Oct 29 2013 Here's the program. Sorry, it's long and I don't see the
• bearophile (5/7) Oct 30 2013 It works as long as you don't put reference types (like dynamic
• Dicebot (6/9) Oct 20 2013 They must be much more complicated because of clear distinction
• Logesh Pillay (2/22) Oct 20 2013 Thanks, that worked.

"Logesh Pillay" <lp webafrica.org.za> writes:

I want an associative array in d programming language. The key is 
a struct with two shorts. Easy so far.

struct kie { short a; short b; }
short[kie] possibles;

Problem is I want to hold more than value per key. Dynamic would 
be useful so it can grow and shrink per key When I try to 
allocate a dynamic array as value to a to key i.e

short[] temp; ... possibles[k] = temp;

I get the understandable error.  Error: cannot append type 
short[] to type short

How do I declare an associative array where the values can be a 
dynamic array of numbers?

"Andrej Mitrovic" <andrej.mitrovich gmail.com> writes:

On Sunday, 20 October 2013 at 13:54:48 UTC, Logesh Pillay wrote:
 I want an associative array in d programming language. The key 
 is a struct with two shorts. Easy so far.

 struct kie { short a; short b; }
 short[kie] possibles;

 Problem is I want to hold more than value per key. Dynamic 
 would be useful so it can grow and shrink per key When I try to 
 allocate a dynamic array as value to a to key i.e

 short[] temp; ... possibles[k] = temp;

 I get the understandable error.  Error: cannot append type 
 short[] to type short

 How do I declare an associative array where the values can be a 
 dynamic array of numbers?

Try:

short[][kie];

"bearophile" <bearophileHUGS lycos.com> writes:

Andrej Mitrovic:

 struct kie { short a; short b; }
 short[kie] possibles;

 ...
 Try:

 short[][kie];

In D structs/classes usually start with an upper case letter:

struct Kie { short a, b; }

But if you want to use Kie as key in an associative array you 
have to add it the full hashing protocol of three functions: 
equality, hash function and comparison.

A simpler solution is to use a Tuple, that already defines those 
three methods:

alias Kie = Tuple!(short,"a", short,"b");

Bye,
bearophile

"Logesh Pillay" <lp webafrica.org.za> writes:

On Sunday, 20 October 2013 at 14:05:53 UTC, bearophile wrote:
 Andrej Mitrovic:

 struct kie { short a; short b; }
 short[kie] possibles;

 ...
 Try:

 short[][kie];

 In D structs/classes usually start with an upper case letter:

 struct Kie { short a, b; }

 But if you want to use Kie as key in an associative array you 
 have to add it the full hashing protocol of three functions: 
 equality, hash function and comparison.

 A simpler solution is to use a Tuple, that already defines 
 those three methods:

 alias Kie = Tuple!(short,"a", short,"b");

 Bye,
 bearophile

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.

"bearophile" <bearophileHUGS lycos.com> writes:

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

"Logesh Pillay" <lp webafrica.org.za> writes:

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

"Daniel Davidson" <nospam spam.com> writes:

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?

"Logesh Pillay" <lp webafrica.org.za> writes:

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);
}

"bearophile" <bearophileHUGS lycos.com> writes:

Logesh Pillay:

 using struct as a key to an associative array worked fine 
 without opHash and other special methods.

It works as long as you don't put reference types (like dynamic 
arrays and strings) as members of that struct.

Bye,
bearophile

"Dicebot" <public dicebot.lv> writes:

On Sunday, 20 October 2013 at 15:13:47 UTC, Logesh Pillay wrote:
 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.

They must be much more complicated because of clear distinction 
between compile-time entities and run-time ones in native 
compiled language, something that Python does not need to care 
about. That said, there unfortunately are also some design quirks 
too, mostly historical mistakes.

"Logesh Pillay" <lp webafrica.org.za> writes:

On Sunday, 20 October 2013 at 13:57:27 UTC, Andrej Mitrovic wrote:
 On Sunday, 20 October 2013 at 13:54:48 UTC, Logesh Pillay wrote:
 I want an associative array in d programming language. The key 
 is a struct with two shorts. Easy so far.

 struct kie { short a; short b; }
 short[kie] possibles;

 Problem is I want to hold more than value per key. Dynamic 
 would be useful so it can grow and shrink per key When I try 
 to allocate a dynamic array as value to a to key i.e

 short[] temp; ... possibles[k] = temp;

 I get the understandable error.  Error: cannot append type 
 short[] to type short

 How do I declare an associative array where the values can be 
 a dynamic array of numbers?

 Try:

 short[][kie];

Thanks, that worked.