Post History
A finite binary string is "Sturmian" if for every two contiguous substrings $x$ and $y$ of the same length, the number of $0$s in $x$ and $y$ differs by at most 1. Your program should take a finit...
#2: Post edited
by
WheatWizard
·
2026-04-09T16:03:28Z (5 months ago)
- A finite binary string is "Sturmian" if for every two contiguous substrings \$x\$ and \$y\$ of the same length, the number of \$0\$s in \$x\$ and \$y\$ differs by at most 1.
- Your program should take a finite binary string and output one of two distinct values. The first if the input is Sturmian the other if the input is not Sturmian.
- This is code-golf so the goal is to minimize the size of your source code as measured in bytes.
- ## Bonus
This problem is solvable in worst-case linear time complexity. I encourage people to submit linear time solutions. Although it is not necessary, I give my official blessing for linear time solutions to be scored separately from slower solutions. Just as different programming languages are not competing against each other.- In fact I consider this in some sense the real challenge. There seems to me more dimension for golfing strategy in the linear time case.
- ## Test cases
- Please do not try to guess the property based on the test-cases. Please read the description, and if something is unclear ask about it.
- I have included the falsifying substrings in the Non-Sturmian cases. Your solution is not required to, or even permitted to, output these extra strings.
- ```txt
- 0110 -> Sturmian
- 0011 -> Non-Sturmian (00, 11)
- 100001000100001 -> Sturmian
- 1000001000010001 -> Non-Sturmian (00000, 10001)
- 10010100100101001001010010 -> Sturmian
- 10010100100100101001010010 -> Non-Sturmian (00100100, 10100101)
- ```
- A finite binary string is "Sturmian" if for every two contiguous substrings \$x\$ and \$y\$ of the same length, the number of \$0\$s in \$x\$ and \$y\$ differs by at most 1.
- Your program should take a finite binary string and output one of two distinct values. The first if the input is Sturmian the other if the input is not Sturmian.
- This is code-golf so the goal is to minimize the size of your source code as measured in bytes.
- ## Bonus
- This problem is solvable in worst-case linear time complexity. I encourage people to submit linear time solutions. Although it is not necessary, I give my official blessing for linear time solutions to be scored separately from slower solutions. Just as different programming languages are not competing against each other
- In fact I consider this in some sense the real challenge. There seems to me more dimension for golfing strategy in the linear time case.
- In order for this to work on the leader board I suggest that submissions append "linear" to the language name. e.g. `Elm linear, 240 bytes`
- ## Test cases
- Please do not try to guess the property based on the test-cases. Please read the description, and if something is unclear ask about it.
- I have included the falsifying substrings in the Non-Sturmian cases. Your solution is not required to, or even permitted to, output these extra strings.
- ```txt
- 0110 -> Sturmian
- 0011 -> Non-Sturmian (00, 11)
- 100001000100001 -> Sturmian
- 1000001000010001 -> Non-Sturmian (00000, 10001)
- 10010100100101001001010010 -> Sturmian
- 10010100100100101001010010 -> Non-Sturmian (00100100, 10100101)
- ```
#1: Initial revision
by
WheatWizard
·
2026-04-09T14:48:52Z (5 months ago)
Determine if a string is Sturmian
A finite binary string is "Sturmian" if for every two contiguous substrings \$x\$ and \$y\$ of the same length, the number of \$0\$s in \$x\$ and \$y\$ differs by at most 1. Your program should take a finite binary string and output one of two distinct values. The first if the input is Sturmian the other if the input is not Sturmian. This is code-golf so the goal is to minimize the size of your source code as measured in bytes. ## Bonus This problem is solvable in worst-case linear time complexity. I encourage people to submit linear time solutions. Although it is not necessary, I give my official blessing for linear time solutions to be scored separately from slower solutions. Just as different programming languages are not competing against each other. In fact I consider this in some sense the real challenge. There seems to me more dimension for golfing strategy in the linear time case. ## Test cases Please do not try to guess the property based on the test-cases. Please read the description, and if something is unclear ask about it. I have included the falsifying substrings in the Non-Sturmian cases. Your solution is not required to, or even permitted to, output these extra strings. ```txt 0110 -> Sturmian 0011 -> Non-Sturmian (00, 11) 100001000100001 -> Sturmian 1000001000010001 -> Non-Sturmian (00000, 10001) 10010100100101001001010010 -> Sturmian 10010100100100101001010010 -> Non-Sturmian (00100100, 10100101) ```