0
\$\begingroup\$

Write a program that takes a string as input and modifies it by reversing the string in its place by mirroring the position. The first position goes to last, second to second last and so it goes on. In simple words, the string would be mirrored.

"In Place" means the program should use \$O(1)\$ additional memory regardless of the length of the string

Test Cases

Input: "Hello, World!" Output: "!dlroW ,olleH"

Input: "Hello" Output: "olleH"

Input: "A man a plan a canal Panama" Output: "amanaP lanac a nalp a nam A"

Input: "123456789" Output: "987654321"

Input: "" Output: ""

\$\endgroup\$
21
  • 9
    \$\begingroup\$ I’m voting to close this question because because the requirement to not allocate memory for additional copies of the input string is objectively unobservable - does creating memory for every character of the input but the last count as making memory for the input string? Does making memory for individual characters count as making memory for the input string? And what about languages where you can't directly inspect memory (like interpreted languages)? \$\endgroup\$
    – lyxal
    Mar 3, 2023 at 7:02
  • 5
    \$\begingroup\$ I suggest using the sandbox next time to get challenge feedback before posting. It's a good way of making sure there's no problems with questions :) \$\endgroup\$
    – lyxal
    Mar 3, 2023 at 7:07
  • 2
    \$\begingroup\$ It's still unclear what it means to reverse the string "in place" - saying that all operations should be applied to the same variable isn't objective because then that definition falls apart for languages that don't have variables or operate on stacks/tapes/other data structures. And even when there are variables, it's still an unobservable requirement, which is disallowed in questions. \$\endgroup\$
    – lyxal
    Mar 3, 2023 at 7:13
  • 2
    \$\begingroup\$ Did you mean to say the program should use O(1) memory regardless of the length of the string? That would be observable and force "in-place" allocation while still allowing temporary variables \$\endgroup\$
    – mousetail
    Mar 3, 2023 at 7:14
  • 4
    \$\begingroup\$ I don't think this is substantially different from Reverse stdin and place on stdout, the requirement to reverse inplace being unobservable. \$\endgroup\$
    – ATaco
    Mar 3, 2023 at 7:19

5 Answers 5

2
\$\begingroup\$

x86 assembly (Linux) - 42 26 bytes

F6 D6 29 D4 B0 03 89 E1 CD 80 01 C1 43 89 DA 49 39 E1 7C 06 B0 04 CD 80 EB F5

This is my first Assembly program. Reads from stdin, then outputs to stdout in reverse order. Try it online.

not dh       ; sys_read count = edx = 65280
sub esp,edx  ; allocate 65280 bytes on stack

mov al,3     ; 0x03 = "read" syscall
mov ecx,esp  ; sys_read buf = ecx = stack pointer
int 0x80     ; eax = sys_read(stdin, esp, 65280)

add ecx,eax  ; add read bytes to stack pointer

inc ebx      ; sys_write fd = 1 = stdout
mov edx,ebx  ; sys_write count = 1

reverse:
dec ecx      ;
cmp ecx,esp  ; check if we've gone too far
jl done      ;

mov al,4     ; 0x04 = "write" syscall
int 0x80     ; eax = sys_write(stdout, ecx, 1)

jmp reverse

done:

Disassembly

0:  f6 d6                   not    dh
2:  29 d4                   sub    esp,edx
4:  b0 03                   mov    al,0x3
6:  89 e1                   mov    ecx,esp
8:  cd 80                   int    0x80
a:  01 c1                   add    ecx,eax
c:  43                      inc    ebx
d:  89 da                   mov    edx,ebx
0000000f <reverse>:
f:  49                      dec    ecx
10: 39 e1                   cmp    ecx,esp
12: 7c 06                   jl     1a <done>
14: b0 04                   mov    al,0x4
16: cd 80                   int    0x80
18: eb f5                   jmp    f <reverse>
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Mar 6, 2023 at 19:48
1
\$\begingroup\$

C (gcc), 139 134 132 bytes

#define C strlen(a[1])
main(int n,char**a){for(n=0;n<C/2;){*(a[1]+n)^=**a=*(a[1]+n)^*(a[1]+C-n-1);*(a[1]+C-n++-1)^=**a;}puts(a[1]);}

Try it online!

Thanks for the "you can use puts suggestion from Neil that saved 2 bytes...

OK, assuming I understand the goal (which is big assumption), I think this one does the right thing... It reverses the string passed as the first commandline argument, then prints it. No additional storage is allocated to effect the reversal.

It works by XOR'ing each character of the string with the one it should be swapped with, then XOR'ing that composite value with each of the original characters. The temporary storage needed to complete the work are a char for holding the XOR composite, and an int string offset. The code overloads variables the compiler created for other purposes to avoid allocating additional memory for those temporary variables.

#define C strlen(a[1])       - just a shortcut to save space
main(int n,char**a){ ... }   - standard "this is a C program" stuff
for(n=0;n<C/2;){ ... }       - loop C/2 times (half the length of the string)
**a=*(a[1]+n)^*(a[1]+C-n-1); - set "*a[0]" to a composite of current swap chars
*(a[1]+n)^=**a...            - use composite to swap first char (w/ XOR)
*(a[1]+C-n++-1)^=**a;        - and repeat with the second char, increment "n"
puts(a[1]);                  - output the reversed string

If the rules allow for temporary variables, this could be shorter.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 86 bytes \$\endgroup\$
    – ceilingcat
    Mar 4, 2023 at 18:49
  • 1
    \$\begingroup\$ Always use hard-coded strings as the first parameter to printf e.g. printf("%s",a[1]);, otherwise the user could insert format specifiers and cause undefined behaviour. In this case you could probably use puts instead. \$\endgroup\$
    – Neil
    Mar 4, 2023 at 22:05
  • \$\begingroup\$ re: ceilingcat's MUCH shorter version... I think that's different enough that it warrants being posted as a separate answer. Also, it's sort of what I was thinking when I wrote "If the rules allow for temporary variables", so I think it's a different idea entirely. \$\endgroup\$
    – cnamejj
    Mar 6, 2023 at 3:15
  • \$\begingroup\$ Re:unsafe printf() use, I agree but for golf contests I think that's OK? But the puts() call is shorter too, so I switch it. Thanks! \$\endgroup\$
    – cnamejj
    Mar 6, 2023 at 3:19
0
\$\begingroup\$

Factor, 8 bytes

reverse!

Try it online!

Builtin. The documentation (and source code) for reverse! corroborates its O(1) additional memory usage beyond the string itself.

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 57 bytes

for$l(0...5*length){s/.{$l}\K(.)(.*)(.)(.{$l})/$3$2$1$4/}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

JavaScript, 14 bytes

s=>s.reverse()

Try it:

f=s=>s.reverse()

;[
  'Hello, World!',
  'Hello',
  'A man a plan a canal Panama',
  '123456789',
  ''
].forEach(s=>console.log(f([...s]).join``))

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.