Prove commutativity on this monoid presentation.
Given two binary strings $A$ and $B$ such that $A$ is an anagram of $B$, output a third binary string $S$ such that both $A$ and $B$ can be created by iterated removals of the substring $10101$ from $S$.
For example for $A=100$ and $B = 010$, one solution is $S = 10101010$ since
$$ (10101)010 \rightarrow 010 $$$$ 10(10101)0 \rightarrow 100 $$For a more complex example if $A = 1100$ and $B = 0101$, then one solution is $S = 11010101010101$ since
$$ 110(10101)010101 \rightarrow 1100(10101) \rightarrow 1100 $$$$ 1(10101)01010101 \rightarrow (10101)0101 \rightarrow 0101 $$There are multiple solutions to every possible input, but there is no requirement that the output be any particular one, only that it satisfy the requirements.
This is code-golf, the goal is to minimize the size of your source code as measured in bytes.
2 answers
x86-64 machine code, 37 bytes
31 C0 50 50 FF 04 C4 AC 2C 30 79 F8 5A 48 B8 31 30 31 30 AE 51 F3 AB 59 51 F3 AA 88 27 59 FF CA 75 F1 88 17 C3
Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as a null-terminated byte string, and in RSI and RDX, addresses of the inputs, as null-terminated byte strings (the second is ignored).
This uses the same method as my last answer: output (1n0(1010)n)m1n, where m and n are the numbers of 0s and 1s respectively (and exponentiation is repetition).
In assembly:
f: xor eax, eax # Set EAX to 0.
push rax # Push RAX onto the stack twice. (The E?? registers are the
push rax # low 32 bits of the corresponding 64-bit R?? registers,
# and when they are modified the high bits become 0,
# so RAX is 0 here.)
li: inc DWORD PTR [rax * 8 + rsp] # Add 1 to the low 32 bits of
# the RAXth 64-bit value from the top of the stack.
# The first time, RAX is 0; later, the input string's digits.
lodsb # Load a byte from the input string into AL
# (low byte of RAX), advancing the pointer.
sub al, 0x30 # Subtract 0x30 from that byte: '0'→0, '1'→1.
jns li # Jump back, to repeat if the result is nonnegative.
# (The loop ends at the null terminator.)
pop rdx # Pop into RDX the count of 0s plus 1.
.ascii "\x48\xB8" "1010"
# Put eight bytes into RAX: the first (low) four are "1010",
# and the rest absorb the next three instructions,
# skipping those instructions for the first iteration.
lo: scasb # Advance RDI past the "0" while comparing it to AL.
push rcx # Push the count of 1s back onto the stack.
rep stosd # Write EAX ("1010") to the output string RCX times,
# advancing RDI and counting down RCX.
pop rcx; push rcx # Pop the count of 1s into RCX and repush it.
rep stosb # Write AL ("1") to the output string that many times,
# advancing RDI and counting down RCX.
mov [rdi], ah# Put AH ("0") in the next place in the output string.
pop rcx # Pop the count of 1s into RCX.
dec edx # Subtract 1 from EDX.
jnz lo # Jump back, to repeat, if the result is nonzero.
mov [rdi], dl# Add a 0 byte to the output string from RDX's low byte.
ret # Return.
0 comment threads
Python 3.8, 64 bytes
lambda s,_:((n:=s.count("1"))*"1"+"0"+n*"1010")*(len(s)-n)+n*"1"
Let Tn consist of (2n+1) 0s and 2n 1s alternating. Tn can consume a 1 on either side and become Tn-1:
[1 0101]01010
01010[1010 1]
Repeating this, Tn can consume n 1s in total from both sides and become T0 = 0.
The output alternates m+1 runs of n 1s with m copies of Tn.
This can be reduced to any string of m 0s and n 1s.
0 comment threads
0 comment threads