digitalmars.D.learn - Dynamic associative array, to hold many values per key
- 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.
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?
Oct 20 2013
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];
Oct 20 2013
Andrej Mitrovic: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, bearophilestruct kie { short a; short b; } short[kie] possibles;... Try: short[][kie];
Oct 20 2013
On Sunday, 20 October 2013 at 14:05:53 UTC, bearophile wrote:Andrej Mitrovic: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.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, bearophilestruct kie { short a; short b; } short[kie] possibles;... Try: short[][kie];
Oct 20 2013
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
Oct 20 2013
On Sunday, 20 October 2013 at 16:08:50 UTC, bearophile wrote:Logesh Pillay: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 + yThanks. 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
Oct 29 2013
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: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: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 + yThanks. 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
Oct 29 2013
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: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); }On Sunday, 20 October 2013 at 16:08:50 UTC, bearophile wrote: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: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 + yThanks. 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
Oct 29 2013
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
Oct 30 2013
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.
Oct 20 2013
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:Thanks, that worked.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];
Oct 20 2013