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?

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];

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

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.

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.

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

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.

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

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?

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