Post History
The problem Someone has created an encoding format for square bit matrices, however they have found it isn't perfect! One encoding may not decode to exactly one matrix, or it may not even be possi...
#6: Post edited
by
Aftermost2167
·
2023-02-28T20:07:12Z (almost 2 years ago)
Remove time constraint and clarify scoring
- ### The problem
- Someone has created an encoding format for square bit matrices, however they have found it isn't perfect! One encoding may not decode to exactly one matrix, or it may not even be possible to decode.
- Knowing this, you're tasked to write a program to decode a set of encodings and since time is of the essence, it's asked that you make it as fast as possible.
- The encoding is as follows:
- * an integer, **S**, indicating the matrix size (2 for 2×2, 3 for 3×3, etc; always ≥2)
- * **S** integers corresponding to the number of 1s in each line (top-to-bottom)
- * **S** integers corresponding to the number of 1s in each column (left-to-right)
- * 2 integers corresponding to the number of 1s in each diagonal (main, then anti-diagonal)
- * 4 integers corresponding to the number of 1s in each quadrant (top-right, top-right, bottom-left, bottom-right)
- * **S** integers corresponding to the number of transitions in each line (top-to-bottom)
- * **S** integers corresponding to the number of transitions in each column (left-to-right)
- The quadrants are defined by the side length divided by two, floored.
- Here's an example of a 5×5 matrix, with quadrant boundaries highlighted by different digits:
- 11222
- 11222
- 33444
- 33444
- 33444
- The program should output the number of matrices possible to decode, followed by a representation of such matrices.
- That representation should be composed of `0`s and `1`s
- ### Example
- #### Encoding
- 4
- 1 1 1 1
- 1 1 1 1
- 0 4
- 0 2 2 0
- 1 2 2 1
- 1 2 2 1
- #### Decoded matrix
- 1
- 0001
- 0010
- 0100
- 1000
### Time constraintsThe upper bound for evaluation is **20 seconds** to allow everyone to use any language they want.If you manage to get your decoder to run in **under a second** for the bigger cases, you will beat me!### EvaluationAll solutions will be evaluated by me on the same machine, and the time measurements posted as a comment on the corresponding answer.You can expect the latest versions for each language and compiler/interpreter. For Python, PyPy will be used, to make it a more interesting option.- There will be some extra hidden test cases.
- ---
- ### More test cases
- #### Input 1
- 4
- 2 3 4 3
- 2 3 4 3
- 2 4
- 4 3 4 1
- 1 1 0 1
- 1 1 0 1
- #### Output 1
- 0
- #### Input 2
- 3
- 0 2 0
- 1 0 1
- 0 0
- 0 0 1 1
- 0 2 0
- 2 0 2
- #### Output 2
- 1
- 000
- 101
- 000
- ---
- ### Scoreboard
- (no submissions yet)
- ### The problem
- Someone has created an encoding format for square bit matrices, however they have found it isn't perfect! One encoding may not decode to exactly one matrix, or it may not even be possible to decode.
- Knowing this, you're tasked to write a program to decode a set of encodings and since time is of the essence, it's asked that you make it as fast as possible.
- The encoding is as follows:
- * an integer, **S**, indicating the matrix size (2 for 2×2, 3 for 3×3, etc; always ≥2)
- * **S** integers corresponding to the number of 1s in each line (top-to-bottom)
- * **S** integers corresponding to the number of 1s in each column (left-to-right)
- * 2 integers corresponding to the number of 1s in each diagonal (main, then anti-diagonal)
- * 4 integers corresponding to the number of 1s in each quadrant (top-right, top-right, bottom-left, bottom-right)
- * **S** integers corresponding to the number of transitions in each line (top-to-bottom)
- * **S** integers corresponding to the number of transitions in each column (left-to-right)
- The quadrants are defined by the side length divided by two, floored.
- Here's an example of a 5×5 matrix, with quadrant boundaries highlighted by different digits:
- 11222
- 11222
- 33444
- 33444
- 33444
- The program should output the number of matrices possible to decode, followed by a representation of such matrices.
- That representation should be composed of `0`s and `1`s
- ### Example
- #### Encoding
- 4
- 1 1 1 1
- 1 1 1 1
- 0 4
- 0 2 2 0
- 1 2 2 1
- 1 2 2 1
- #### Decoded matrix
- 1
- 0001
- 0010
- 0100
- 1000
- ### Scoring
- The goal for this challenge is the produce the fastest algorithm (i.e, the algorithm with the smallest asymptotic complexity), and as such you should include an short analysis of your algorithm alongside your code.
- Despite that, all solutions will be evaluated by me on the same machine, and the time measurements posted as a comment on the corresponding answer. This is merely for curiosity, not for actual scoring.
- You can expect the latest versions for each language and compiler/interpreter. For languages with [JITs](https://en.wikipedia.org/wiki/Just-in-time_compilation) and similar tools, those will be used (e.g for Python, PyPy will be used).
- If you manage to get your decoder to run in **under a second** for the bigger cases, you will beat me :D
- There will be some extra hidden test cases.
- ---
- ### More test cases
- #### Input 1
- 4
- 2 3 4 3
- 2 3 4 3
- 2 4
- 4 3 4 1
- 1 1 0 1
- 1 1 0 1
- #### Output 1
- 0
- #### Input 2
- 3
- 0 2 0
- 1 0 1
- 0 0
- 0 0 1 1
- 0 2 0
- 2 0 2
- #### Output 2
- 1
- 000
- 101
- 000
- ---
- ### Scoreboard
- (no submissions yet)
#5: Post edited
by
Aftermost2167
·
2023-02-28T18:07:44Z (almost 2 years ago)
Fix statement and example case
- ### The problem
- Someone has created an encoding format for square bit matrices, however they have found it isn't perfect! One encoding may not decode to exactly one matrix, or it may not even be possible to decode.
- Knowing this, you're tasked to write a program to decode a set of encodings and since time is of the essence, it's asked that you make it as fast as possible.
- The encoding is as follows:
- * an integer, **S**, indicating the matrix size (2 for 2×2, 3 for 3×3, etc; always ≥2)
* **S** integers corresponding to the number of 0s in each line (top-to-bottom)* **S** integers corresponding to the number of 0s in each column (left-to-right)* 2 integers corresponding to the number of 0s in each diagonal (main, then anti-diagonal)* 4 integers corresponding to the number of 0s in each quadrant (top-right, top-right, bottom-left, bottom-right)- * **S** integers corresponding to the number of transitions in each line (top-to-bottom)
- * **S** integers corresponding to the number of transitions in each column (left-to-right)
- The quadrants are defined by the side length divided by two, floored.
- Here's an example of a 5×5 matrix, with quadrant boundaries highlighted by different digits:
- 11222
- 11222
- 33444
- 33444
- 33444
- The program should output the number of matrices possible to decode, followed by a representation of such matrices.
- That representation should be composed of `0`s and `1`s
- ### Example
- #### Encoding
- 4
- 1 1 1 1
- 1 1 1 1
0 2- 0 2 2 0
- 1 2 2 1
- 1 2 2 1
- #### Decoded matrix
- 1
- 0001
- 0010
- 0100
- 1000
- ### Time constraints
- The upper bound for evaluation is **20 seconds** to allow everyone to use any language they want.
- If you manage to get your decoder to run in **under a second** for the bigger cases, you will beat me!
- ### Evaluation
- All solutions will be evaluated by me on the same machine, and the time measurements posted as a comment on the corresponding answer.
- You can expect the latest versions for each language and compiler/interpreter. For Python, PyPy will be used, to make it a more interesting option.
- There will be some extra hidden test cases.
- ---
- ### More test cases
- #### Input 1
- 4
- 2 3 4 3
- 2 3 4 3
- 2 4
- 4 3 4 1
- 1 1 0 1
- 1 1 0 1
- #### Output 1
- 0
- #### Input 2
- 3
- 0 2 0
- 1 0 1
- 0 0
- 0 0 1 1
- 0 2 0
- 2 0 2
- #### Output 2
- 1
- 000
- 101
- 000
- ---
- ### Scoreboard
- (no submissions yet)
- ### The problem
- Someone has created an encoding format for square bit matrices, however they have found it isn't perfect! One encoding may not decode to exactly one matrix, or it may not even be possible to decode.
- Knowing this, you're tasked to write a program to decode a set of encodings and since time is of the essence, it's asked that you make it as fast as possible.
- The encoding is as follows:
- * an integer, **S**, indicating the matrix size (2 for 2×2, 3 for 3×3, etc; always ≥2)
- * **S** integers corresponding to the number of 1s in each line (top-to-bottom)
- * **S** integers corresponding to the number of 1s in each column (left-to-right)
- * 2 integers corresponding to the number of 1s in each diagonal (main, then anti-diagonal)
- * 4 integers corresponding to the number of 1s in each quadrant (top-right, top-right, bottom-left, bottom-right)
- * **S** integers corresponding to the number of transitions in each line (top-to-bottom)
- * **S** integers corresponding to the number of transitions in each column (left-to-right)
- The quadrants are defined by the side length divided by two, floored.
- Here's an example of a 5×5 matrix, with quadrant boundaries highlighted by different digits:
- 11222
- 11222
- 33444
- 33444
- 33444
- The program should output the number of matrices possible to decode, followed by a representation of such matrices.
- That representation should be composed of `0`s and `1`s
- ### Example
- #### Encoding
- 4
- 1 1 1 1
- 1 1 1 1
- 0 4
- 0 2 2 0
- 1 2 2 1
- 1 2 2 1
- #### Decoded matrix
- 1
- 0001
- 0010
- 0100
- 1000
- ### Time constraints
- The upper bound for evaluation is **20 seconds** to allow everyone to use any language they want.
- If you manage to get your decoder to run in **under a second** for the bigger cases, you will beat me!
- ### Evaluation
- All solutions will be evaluated by me on the same machine, and the time measurements posted as a comment on the corresponding answer.
- You can expect the latest versions for each language and compiler/interpreter. For Python, PyPy will be used, to make it a more interesting option.
- There will be some extra hidden test cases.
- ---
- ### More test cases
- #### Input 1
- 4
- 2 3 4 3
- 2 3 4 3
- 2 4
- 4 3 4 1
- 1 1 0 1
- 1 1 0 1
- #### Output 1
- 0
- #### Input 2
- 3
- 0 2 0
- 1 0 1
- 0 0
- 0 0 1 1
- 0 2 0
- 2 0 2
- #### Output 2
- 1
- 000
- 101
- 000
- ---
- ### Scoreboard
- (no submissions yet)
#4: Post undeleted
by
Aftermost2167
·
2023-02-27T22:44:05Z (almost 2 years ago)
#3: Post edited
by
Aftermost2167
·
2023-02-27T20:50:36Z (almost 2 years ago)
Apply revisions from sandbox (https://codegolf.codidact.com/posts/287928)
Hello!I have come across this very interesting programming challenge I thought I'd share.### The problemYou're tasked to decode an encoding of a square bit matrix of certain size, which contains the number of 0 cells per line, column, diagonal (main and anti-diagonal) and quadrant, as well as the number of transitions per line and column. This encoding isn't injective, that is, it doesn't perfectly map one encoding to one matrix. Thus, your decoder should output how many matrices can be decoded from the given input encoding, and in case there's only one, display it.- ### Example
- #### Encoding
size: 4line 0s (left to right): 1, 1, 1, 1columns 0s (left to right): 1, 1, 1, 1quadrant 0s: top-right=2 top-left=0, bottom-right=2, bottom-left=0diagonal 0s: main=0, anti=4line transitions (left to right): 1, 2, 2, 1column transitions (left to right): 1, 2, 2, 1- #### Decoded matrix
- 0001
- 0010
- 0100
- 1000
### ConstraintsThe matrices are always square and 2x2 or bigger. The goal is to make a decoder that processes on or more 25x25 encodings under a second (on fairly modern hardware, I suppose). Below that, fastest code wins.
- ### The problem
- Someone has created an encoding format for square bit matrices, however they have found it isn't perfect! One encoding may not decode to exactly one matrix, or it may not even be possible to decode.
- Knowing this, you're tasked to write a program to decode a set of encodings and since time is of the essence, it's asked that you make it as fast as possible.
- The encoding is as follows:
- * an integer, **S**, indicating the matrix size (2 for 2×2, 3 for 3×3, etc; always ≥2)
- * **S** integers corresponding to the number of 0s in each line (top-to-bottom)
- * **S** integers corresponding to the number of 0s in each column (left-to-right)
- * 2 integers corresponding to the number of 0s in each diagonal (main, then anti-diagonal)
- * 4 integers corresponding to the number of 0s in each quadrant (top-right, top-right, bottom-left, bottom-right)
- * **S** integers corresponding to the number of transitions in each line (top-to-bottom)
- * **S** integers corresponding to the number of transitions in each column (left-to-right)
- The quadrants are defined by the side length divided by two, floored.
- Here's an example of a 5×5 matrix, with quadrant boundaries highlighted by different digits:
- 11222
- 11222
- 33444
- 33444
- 33444
- The program should output the number of matrices possible to decode, followed by a representation of such matrices.
- That representation should be composed of `0`s and `1`s
- ### Example
- #### Encoding
- 4
- 1 1 1 1
- 1 1 1 1
- 0 2
- 0 2 2 0
- 1 2 2 1
- 1 2 2 1
- #### Decoded matrix
- 1
- 0001
- 0010
- 0100
- 1000
- ### Time constraints
- The upper bound for evaluation is **20 seconds** to allow everyone to use any language they want.
- If you manage to get your decoder to run in **under a second** for the bigger cases, you will beat me!
- ### Evaluation
- All solutions will be evaluated by me on the same machine, and the time measurements posted as a comment on the corresponding answer.
- You can expect the latest versions for each language and compiler/interpreter. For Python, PyPy will be used, to make it a more interesting option.
- There will be some extra hidden test cases.
- ---
- ### More test cases
- #### Input 1
- 4
- 2 3 4 3
- 2 3 4 3
- 2 4
- 4 3 4 1
- 1 1 0 1
- 1 1 0 1
- #### Output 1
- 0
- #### Input 2
- 3
- 0 2 0
- 1 0 1
- 0 0
- 0 0 1 1
- 0 2 0
- 2 0 2
- #### Output 2
- 1
- 000
- 101
- 000
- ---
- ### Scoreboard
- (no submissions yet)
#2: Post deleted
by
Aftermost2167
·
2023-02-27T01:26:40Z (almost 2 years ago)
#1: Initial revision
by
Aftermost2167
·
2023-02-26T23:22:48Z (almost 2 years ago)
Decoding a non injective bit matrix encoding
Hello!
I have come across this very interesting programming challenge I thought I'd share.
### The problem
You're tasked to decode an encoding of a square bit matrix of certain size, which contains the number of 0 cells per line, column, diagonal (main and anti-diagonal) and quadrant, as well as the number of transitions per line and column. This encoding isn't injective, that is, it doesn't perfectly map one encoding to one matrix. Thus, your decoder should output how many matrices can be decoded from the given input encoding, and in case there's only one, display it.
### Example
#### Encoding
size: 4
line 0s (left to right): 1, 1, 1, 1
columns 0s (left to right): 1, 1, 1, 1
quadrant 0s: top-right=2 top-left=0, bottom-right=2, bottom-left=0
diagonal 0s: main=0, anti=4
line transitions (left to right): 1, 2, 2, 1
column transitions (left to right): 1, 2, 2, 1
#### Decoded matrix
0001
0010
0100
1000
### Constraints
The matrices are always square and 2x2 or bigger. The goal is to make a decoder that processes on or more 25x25 encodings under a second (on fairly modern hardware, I suppose). Below that, fastest code wins.