Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Users Search
Help Dashboard Sign In Sign Up
Challenges Q&A Sandbox Meta
Sandbox
Posts Tags Edits
Create Draft

Post History

66%
+2 −0
Sandbox Decoding a non injective bit matrix encoding [FINALIZED]

posted 2y ago by Aftermost2167‭  ·  edited 2y ago by trichoplax‭

Article finalized optimization fastest-code encoding binary
#7: Post edited by user avatar trichoplax‭ · 2023-02-28T08:14:06Z (almost 2 years ago)
Mark as finalized
  • Decoding a non injective bit matrix encoding
  • Decoding a non injective bit matrix encoding [FINALIZED]
  • ### 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)
  • ## Now posted: [Decoding a non injective bit matrix encoding](https://codegolf.codidact.com/posts/287925 "View the finished challenge")
  • ---
  • ### 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)
finalized optimization fastest-code encoding binary
#6: Post edited by user avatar Aftermost2167‭ · 2023-02-27T14:47:48Z (almost 2 years ago)
Make 20s the limit for everybody
  • ### 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
  • For "regular" languages (like C, C++, Java, Python, Go, Rust, etc) the upper bound is **1 second**. Any submissions taking longer than that won't be taken into account.
  • For anyone looking for an even spicier challenge, submissions written in any [esolang](https://esolangs.org) will be allowed up to **20 seconds**, and be arranged in a separate scoreboard.
  • ### 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
  • #### "Regular languages"
  • (no submissions yet)
  • #### Esolangs
  • (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 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)
#5: Post edited by user avatar Aftermost2167‭ · 2023-02-27T13:19:18Z (almost 2 years ago)
Clarify odd-sided quandrants
  • ### 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 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
  • For "regular" languages (like C, C++, Java, Python, Go, Rust, etc) the upper bound is **1 second**. Any submissions taking longer than that won't be taken into account.
  • For anyone looking for an even spicier challenge, submissions written in any [esolang](https://esolangs.org) will be allowed up to **20 seconds**, and be arranged in a separate scoreboard.
  • ### 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
  • #### "Regular languages"
  • (no submissions yet)
  • #### Esolangs
  • (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 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
  • For "regular" languages (like C, C++, Java, Python, Go, Rust, etc) the upper bound is **1 second**. Any submissions taking longer than that won't be taken into account.
  • For anyone looking for an even spicier challenge, submissions written in any [esolang](https://esolangs.org) will be allowed up to **20 seconds**, and be arranged in a separate scoreboard.
  • ### 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
  • #### "Regular languages"
  • (no submissions yet)
  • #### Esolangs
  • (no submissions yet)
#4: Post edited by user avatar Aftermost2167‭ · 2023-02-27T13:12:41Z (almost 2 years ago)
Forgot to remove previous summary, and add more test cases
  • ### The problem
  • You're tasked to decode an encoding of a square bit matrix of a 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.
  • 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 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 2 0
  • 1 2 2 1
  • 1 2 2 1
  • #### Decoded matrix
  • 1
  • 0001
  • 0010
  • 0100
  • 1000
  • ### Time constraints
  • For "regular" languages (like C, C++, Java, Python, Go, Rust, etc) the upper bound is **1 second**. Any submissions taking longer than that won't be taken into account.
  • For anyone looking for an even spicier challenge, submissions written in any [esolang](https://esolangs.org) will be allowed up to **20 seconds**, and be arranged in a separate scoreboard.
  • ### 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.
  • ---
  • ### Scoreboard
  • #### "Regular languages"
  • (no submissions yet)
  • #### Esolangs
  • (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 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 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
  • For "regular" languages (like C, C++, Java, Python, Go, Rust, etc) the upper bound is **1 second**. Any submissions taking longer than that won't be taken into account.
  • For anyone looking for an even spicier challenge, submissions written in any [esolang](https://esolangs.org) will be allowed up to **20 seconds**, and be arranged in a separate scoreboard.
  • ### 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
  • #### "Regular languages"
  • (no submissions yet)
  • #### Esolangs
  • (no submissions yet)
#3: Post edited by user avatar Aftermost2167‭ · 2023-02-27T12:39:10Z (almost 2 years ago)
Improve problem statement according to feedback
  • 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 a 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 one or more 25x25 encodings in under a second (on fairly modern hardware, I suppose). Below that, fastest code wins.
  • ### Evaluation
  • All solutions will be evaluated by me on the same machine, and the time measurements posted as a comment on the corresponding answer.
  • ### The problem
  • You're tasked to decode an encoding of a square bit matrix of a 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.
  • 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 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 2 0
  • 1 2 2 1
  • 1 2 2 1
  • #### Decoded matrix
  • 1
  • 0001
  • 0010
  • 0100
  • 1000
  • ### Time constraints
  • For "regular" languages (like C, C++, Java, Python, Go, Rust, etc) the upper bound is **1 second**. Any submissions taking longer than that won't be taken into account.
  • For anyone looking for an even spicier challenge, submissions written in any [esolang](https://esolangs.org) will be allowed up to **20 seconds**, and be arranged in a separate scoreboard.
  • ### 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.
  • ---
  • ### Scoreboard
  • #### "Regular languages"
  • (no submissions yet)
  • #### Esolangs
  • (no submissions yet)
#2: Post edited by user avatar trichoplax‭ · 2023-02-27T10:56:43Z (almost 2 years ago)
Typos 
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.
  • ### Evaluation
  • All solutions will be evaluated by me on the same machine, and the time measurements posted as comment on the corresponding answer.
  • 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 a 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 one or more 25x25 encodings in under a second (on fairly modern hardware, I suppose). Below that, fastest code wins.
  • ### Evaluation
  • All solutions will be evaluated by me on the same machine, and the time measurements posted as a comment on the corresponding answer.
optimization fastest-code encoding code-challenge binary
#1: Initial revision by user avatar Aftermost2167‭ · 2023-02-27T01:30:57Z (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.

### Evaluation

All solutions will be evaluated by me on the same machine, and the time measurements posted as comment on the corresponding answer.
optimization fastest-code encoding code-challenge binary