"be consistent" PerlMonks

### perl array matrix

by perlhelp (Initiate)
 on Apr 12, 2015 at 07:51 UTC Need Help??

perlhelp has asked for the wisdom of the Perl Monks concerning the following question:

can somebody show me the example perl code for array matrix related question .

1.Hash of Number to Array of Position.

2.Hash of Position to (Hash of Number to Array of Position). Thanks

here is the example from the blog.

I have a matrix

note: the matrix can be number or string.

and a search string. The task is to find out whether the numbers in the search

string are values in the matrix that are near-by each other along the x and y

coordinates.

"2,7,12,16" should return true

"2,4,7,12" should return true

"1,6,8,12" should return false

"1,5,14,15" should return false

Replies are listed 'Best First'.
Re: perl array matrix
by AnomalousMonk (Bishop) on Apr 12, 2015 at 08:07 UTC

I don't understand what you mean by your questions, but perhaps Perl Data Structures Cookbook (see also  perldocperldsc   from the command line) might help.

Give a man a fish:  <%-(-(-(-<

Re: perl array matrix
by Laurent_R (Canon) on Apr 12, 2015 at 11:11 UTC
It is not very clear to me. My guess is that you are trying to use an array of arrays, probably something like this:
```( [1, 2, 3, 4,],
[5, 6, 7, 8,],
[9, 10, 11, 12,],
[13, 14, 3, 16,],
[2, 18, 19, 20,] )
but you'll have to explain why "2,7,12,16" and "2,4,7,12" should return true and why "1,6,8,12" and "1,5,14,15" should return false. Well, "1,5,14,15" being false, I can understand a plausible reason, because 15 is nowhere in the data structure, but why "1,6,8,12" should be false?

Je suis Charlie.
Hi ; Je suis Charlie. : This is due to the "2,7,12,16" and "2,4,7,12" numbers are nearby each others . and the others are not. in term of matrix x and y position.

Maybe it would help if you define the distance function for your matrix and tell us that function?

Re: perl array matrix
by AnomalousMonk (Bishop) on Apr 12, 2015 at 16:33 UTC

Please feel free to update your posts as you have done with your OP, but it is considered polite to include a note to the effect that an update has been made.

Also: Please use  <c> ... </c> or  <code> ... </code> tags around code, data and input/output. (Please see Markup in the Monastery and Writeup Formatting Tips.) Otherwise, something like 1, 2, 3, 4 looks like a hyperlink to... somewhere... maybe the Delta Quadrant?

Give a man a fish:  <%-(-(-(-<

Re: perl array matrix
by choroba (Archbishop) on Apr 13, 2015 at 12:56 UTC
One possible solution:
1. Start at the first number from the input list.
2. Create two lists: list of visited numbers, and list of the matrix positions to visit.
3. Mark the current number as visited at the current position. If you visited all the input numbers, return true.
4. Check all the neighbouring positions, non-visited ones present in the input list should go to the list of positions to visit.
5. Visit the first position from the list, go to #3.
6. If the list is empty, try starting with the next input number (this is needed, as numbers could be repeated, e.g. 2 in your sample). Go to #2.
7. You tried all the input numbers, but you can't reach all the rest from any of them. Return false.

Which translates easily to Perl:

```#! /usr/bin/perl
use warnings;
use strict;

my @matrix = ( [ 1,  2,  3,  4],
[ 5,  6,  7,  8],
[ 9, 10, 11, 12],
[13, 14,  3, 16],
[ 2, 18, 19, 20],
);

sub nearby {
my @input = @_;
my %numbers;
undef @numbers{@input};

for my \$y (0 .. \$#matrix) {
for my \$x (0 .. \$#{ \$matrix[\$y] }) {
next unless exists \$numbers{ \$matrix[\$y][\$x] };

my @next = ([\$x, \$y]);
my %visited;
while (@next) {
my (\$r, \$s) = @{ shift @next };
undef \$visited{ \$matrix[\$s][\$r] }{"\$r \$s"};
return 1 if keys %visited == keys %numbers;

push @next, grep \$_->[0] >= 0 && \$_->[1] >= 0
&& \$_->[0] <= \$#{ \$matrix[\$s] } && \$_->[1]
+ <= \$#matrix
&& exists \$numbers{ \$matrix[ \$_->[1] ][ \$_
+->[0] ] }
&& ! exists \$visited{ \$matrix[ \$_->[1] ][
+\$_->[0] ] }{"@\$_"},
[\$r - 1, \$s - 1],
[\$r,     \$s - 1],
[\$r + 1, \$s - 1],
[\$r + 1, \$s    ],
[\$r + 1, \$s + 1],
[\$r,     \$s + 1],
[\$r - 1, \$s + 1],
[\$r - 1, \$s    ];
# warn map "<@\$_>", @next;
}
}
}
return
}

use Test::More;

ok(nearby(2, 7, 12, 16));
ok(nearby(2, 4, 7, 12));
ok(! nearby(1, 6, 8, 12));
ok(! nearby(1, 5, 14, 15));

# Unspecified?
ok(nearby(2, 13, 9, 5, 7));
ok(! nearby(2, 13, 7));
ok(nearby(6, 3, 8, 12, 18));

@matrix = ( [ 1,  1,  1,  1, 2],
[ 1,  0,  0,  0, 0],
[ 1,  0,  1,  1, 3],
[ 1,  0,  1,  0, 0],
[ 1,  0,  1,  1, 1],
[ 1,  0,  0,  0, 1],
[ 1,  1,  1,  1, 1],
);
ok(nearby(1, 2, 3));

done_testing();

Update: It's unclear how to handle duplicate numbers. The code returns true for the last case, but did you really want to use 1 several times? Please, clarify your specification.

Update 2: added positions to visited numbers.

لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
How to avoid the duplicated numbers. I run into trouble if so many position x,y return from the sub. it there any way to check the closerx,y. in order to filter out ? Thanks
How to convert the following concept into the code:

1. Create a mapping from numbers to start positions: Hash of Number to Array of Position.

2. Create a neighbor mapping for all positions: Hash of Position to (Hash of Number to Array of Position) -- or just Hash of Number to Position if you can only have one neighbor with that number.

3. For each search string: initialize position possibilities to the array returned by the start mapping.

Iterate through remaining numbers, getting next position set from the neighbor mapping for the possibilities.

If you have no position possibilities left, it's not a match.

I'm sorry I don't understand. Could you please reword, give some examples, draw pictures?
لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
Wow wow wow, Nice code + explanation. Thanks choroba THE PERL EXPERT.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://1123184]
Approved by Happy-the-monk
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (7)
As of 2021-04-23 14:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?