kAshinho

The task is to process matrix, which consist of decimal numbers, to create the maximum number which is divisible by 3 created from matrix numbers. Every matrix is squared and consist 25 numbers (5 rows and 5 columns). Results are constructed like this:
- You have to start in upper-left corner , number in this corner is most significant of our constructed number
- You have to finish in bottom-right corner, number in this corner is less significant of out constructed number
- Number which is our result is constructed from left to right (e.x. if U find 1,2,3,4 from left to right our number is 1234)
- You can only move : up,down,left,right
- You can't overstep the matrix
For example:
Input :
1 2 3 4 5
6 7 8 9 0
1 2 3 4 5
6 7 8 9 0
1 2 3 4 5
Output :
1672389450543872161234905

I'd be happy if anyone could help me

Mjordan2nd

What do you have so far?

__________________
"Every gun that is made, every warship launched, every rocket signifies, in the final sense, a theft from those who hunger and are not fed, from those who are cold and are not clothed. The world in arms is not spending money alone. It is spending the sweat of its laborers, the genius of its scientists, the hopes of its children." - Dwight D. Eisenhower

nnxion

I don't see the pattern in the output. Care to tell me what I'm missing.

__________________
"Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for."
-- Socrates

Arevos

The output is a number made from neighbouring digits in the matrix, starting from the top left. Using a coordinate system starting in the top left, the number represents the digits found at: (0, 0) (0, 1) (1, 1) (1, 0) (2, 0) (2, 1) (3, 1)... etc.

The goal is to find the maximum number that is divisible by three. This appears to be a problem to be solved through a brute-force approach.

DaWei

Reminds me of the recent "Eternity Loop" post, it does.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

The Dark

Sounds like fun!

You could do a recursive search. At each point in the matrix, recurse through each direction that hasn't been used yet (taking the highest number first). The first time you manage to recurse to the end with a 25 digit number divisible by 3 then that is the number you want.
So you need to keep track of which entries you have already been to, to check for which direction you can go in next and to check if you have visited all 25 when you reach the end.
To check for the 25 digit number being divisible by three, add up the digits and see if that is divisible by three.

There are probably some speedups you could do to detect when you have "orphaned" some area of the matrix, e.g. if you went 1678 in the example, there is no way you could get to the 2 in the top row and still reach the end.

The Dark

After thinking about it a bit more, my end conditions were a bit off.
If all 25 entries in the matrix add up to a number divisible by three, then you are just trying to find the biggest number on the way through. If they don't add up to three, then you won't end up with a 25 digit number at all.
So it might be a bit more brute force than I thought.

The Dark

On my machine, a fairly simple recursive version took 7.5ms to complete, so it is probably not worth doing much in the way of optmising the strategies unless you are doing millions of them, or are doing bigger matrices, or want to get extra marks.