1
1
Problem: We have a two dimensional matrix of positive integer cells. On each turn any non-zero cell with a neighbor (top/bottom/left/right) of zero decreases by 1. We want count to the number of non-zero cells present and add them up across all turns.
Is there a faster solution than to use a priority queue?
Is there a name for this problem or a similar problem? I don’t know what to search for.
Example
Here is an input where the result is 7:
00000
00100
01210
00100
00000
Initially there are 5 non-zero cells.
00000
00000
00200
00000
00000
After the first turn, there is 1 non-zero cell.
00000
00000
00100
00000
00000
After the second turn, there is still 1 non-zero cell.
00000
00000
00000
00000
00000
After the third turn, there are 0 non-zero cells.
If we total these up:
\$5 + 1 + 1 = 7\$
Our result is \$7\$
LFA
Posted 2019-07-07T19:54:31.280
Reputation: 11
2Welcome to CGCC! "Is there a faster solution than to use a priority queue?", "Is there a name for this problem or a similar problem?" - this is not the right stack for these questions as we host competitive programming problems. This might fit here as a challenge, although I'm not 100% sure, but if you're after answers to those questions you might not find them here. As far as I can tell though it seems to be a cellular automaton related to an Abelian sandpile. – Jonathan Allan – 2019-07-07T20:06:54.680
1Also wouldn't the example answer be
3since the four1s all decrease to0at the same time-step? – Jonathan Allan – 2019-07-07T20:11:09.397The problem is totaling the time each cell takes to reach zero. Each of the ones were 1, so 4 x 1. – LFA – 2019-07-07T20:39:55.963
Welcome to the site! Like Johathan Allen I am not sure on what the desired task is, or where the number 7 comes from in your example. If you could explain the task without using examples first and then add one or two examples. Then we could move forward to seeing if there is an on topic challenge that can be made from this. In the meanwhile you should checkout the help center. Ideally you should also move this to the sandbox where it can get the help it needs to be on topic.
– Post Rock Garf Hunter – 2019-07-07T21:01:49.5607 is 5 + 1 + 1. – LFA – 2019-07-07T21:15:01.177
The number 7 doesn't seem to match up with the description at the top of the puzzle. The description say number of turns given which is 3 but, based on the example, it seems your 7 comes from counting the number of non-zero cells every turn and adding them up. – Post Rock Garf Hunter – 2019-07-07T21:26:19.127
I meant the sum of the time for each cell to reach zero. Please, let me know how to word it better and I’ll edit it. – LFA – 2019-07-07T21:32:02.897
1This can make a good challenge, but you need a winning criterion. [tag:code-golf] could work, or once you find out the fastest algorithm by asking on CS.SE or Stack Overflow, [tag:code-golf] [tag:restricted-complexity] restricting answers to use an algorithm of that time complexity. – lirtosiast – 2019-07-07T22:23:09.947
Ok so I have gone ahead and made the challenge description clear as per our discussion, feel free to make changes if you think I have gone against your intentions. If lirtosiast's issue of winning criterion is adressed I think this will be ready to be opened and I expect a speedy reopening. Also if you want a user to see a comment it is best if you "ping" them by starting your message with
@and then their name. The only reason I have seen your comments is that I have been periodically checking this question. – Post Rock Garf Hunter – 2019-07-08T14:41:11.887