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 »
Challenges

Post History

75%
+4 −0
Challenges Decoding a non injective bit matrix encoding

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...

0 answers  ·  posted 1y ago by Aftermost2167‭  ·  edited 1y ago by Aftermost2167‭

#6: Post edited by user avatar Aftermost2167‭ · 2023-02-28T20:07:12Z (about 1 year 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 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
  • ### 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 user avatar Aftermost2167‭ · 2023-02-28T18:07:44Z (about 1 year 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 user avatar Aftermost2167‭ · 2023-02-27T22:44:05Z (about 1 year ago)
#3: Post edited by user avatar Aftermost2167‭ · 2023-02-27T20:50:36Z (about 1 year 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 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.
  • ### 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 user avatar Aftermost2167‭ · 2023-02-27T01:26:40Z (about 1 year ago)
#1: Initial revision by user avatar Aftermost2167‭ · 2023-02-26T23:22:48Z (about 1 year 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.