Write a program that is valid after circular character shift

Question

Potentially very difficult, but I've seen some amazing things come out of this site.

The goal is to write a program, in any language, that does whatever you want. The catch is that the program must be valid after any circular shift of the characters.

A circular character shift is very similar to a Circular Shift. Some examples my clear things up.

For the program int main() { return 0; }

shifting to the left by 6 characters yields: in() { return 0; }int ma

shifting to the left by 1 character yields: nt main() { return 0; }i

shifting to the right by 10 character yields: eturn 0; }int main() { r

However, this program obviously doesn't comply with the rules.

Rules

• Any language
• Winner is decided by up-vote count
• Solutions which do the same thing, or completely different things for each rotation, will receive 100 virtual up-votes to their score.

UPDATE I think this has gone on long enough. The winner, with the most votes (virtual votes included) is Mark Byers. Well done!

Answer 1

Use the right language for the task. In this case, that's Befunge.

This language naturally allows rotations because:

• All commands are a single character.
• The control wraps around when it reaches the end of the program, starting again from the beginning.

This Befunge program prints the exact same output ("Hello") regardless of how many "circular character shifts" you use:

86*01p75*1-02p447**1-03p439**04p439**05p455**1+06p662**07p75*1-08p645**2-09p69*4+019+p57*029+p59*1-039+p555**1-049+p88*059+p86*01p75*1-02p447**1-03p439**04p439**05p455**1+06p662**07p75*1-08p645**2-09p69*4+019+p57*029+p59*1-039+p555**1-049+p88*059+p645**2-00p645**2-00p

It runs on Befungee. It requires that the board is increased (not the 80 character default). It can be run like this:

python befungee.py -w400 hello.bef

It works by first dynamically generating and storing a program that prints "Hello" and then overwriting the first byte to redirect the control into the newly written program. The program is written twice so that if a byte is not written correctly the first time, it will be corrected the second time.

The idea could be extended to produce any program of arbitrary complexity.

Answer 2

Brainf*ck

Choose the right tool for the job -- an adage that's never been more relevant than this job right here!

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++.+.>++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++.++++++++++++++.>++++++++++.+

The unshifted program you see here simply prints SHIFT (plus a newline). Abitrarily circular shifts will produce various other outputs, though it will always output six ASCII characters.

Answer 3

Commodore 64 BASIC

? is short for PRINT, and : is a statement separator, so:

?1:?2:?3:          // prints 1, 2, and 3
:?1:?2:?3          // prints 1, 2, and 3
3:?1:?2:?          // adds a program line 3 :PRINT1:PRINT2:PRINT
?3:?1:?2:          // prints 3, 1, and 2
:?3:?1:?2          // prints 3, 1, and 2
2:?3:?1:?          // adds a program line 2 :PRINT3:PRINT1:PRINT
?2:?3:?1:          // prints 2, 3, and 1
:?2:?3:?1          // prints 2, 3, and 1
1:?2:?3:?          // adds a program line 1 :PRINT2:PRINT3:PRINT

Longer variations are, of course, possible:

?1:?2:?3:?4:?5:?6:?7:?8:?9:?10:?11:

etc...

Answer 4

Golfscript

This program prints some digits that always sum up to 2, regardless of how the program is shifted:

10 2 base
0 2 base1
 2 base10
2 base10 
 base10 2
base10 2 
ase10 2 b
se10 2 ba
e10 2 bas

The first line prints 1010 (10 in binary), the second line prints 02 and all the other lines print 2.

Update:

The program can be tested here. Please note that I've added ns at the end of each row only for formatting the output; these can be removed and the program still works.

Answer 5

Ruby, probably one of the shortest possible solutions:

p

And another slightly longer and more interesting one:

;;p";p;";p

Answer 6

Unary Answer:

000000 ... 00000

^44391 Zeros

Cat program. No matter how you rotate, it's the same program.

Answer 7

x86 16 bit binary

Manually constructed with the help of these (1 2) tables, nasm and ndisasm. This will always return without a crash or infinite loop, because no bytes are jumps or change the stack and it is filled with NOPs to end with a single byte ret instruction in any case.

In most cases this will output FOO or a substring of that. If AX is broken, this will call a random int 10 (this changed the cursor blinking speed in one of my tests), but it usually does not result in a crash.

To try out, put the hexdump in a file and use xxd -r foo.hex > foo.com, then run in a dos environment (I used dosbox).

Here is a hex dump of this file:

0000000: b846 0d90 90fe c490 9090 bb05 0090 9043  .F.............C
0000010: 43cd 1090 b84f 0d90 90fe c490 9090 bb05  C....O..........
0000020: 0090 9043 43cd 1090 b84f 0d90 90fe c490  ...CC....O......
0000030: 9090 bb05 0090 9043 43cd 1090 9090 c3    .......CC......

And some interesting disassembled offsets:

+0

00000000  B8420D            mov ax,0xd42
00000003  90                nop
00000004  90                nop
00000005  FEC4              inc ah
00000007  90                nop
00000008  90                nop
00000009  90                nop
0000000A  BB0500            mov bx,0x5
0000000D  90                nop
0000000E  90                nop
0000000F  43                inc bx
00000010  43                inc bx
00000011  CD10              int 0x10
00000013  90                nop
00000014  B84F0D            mov ax,0xd4f
00000017  90                nop
00000018  90                nop
00000019  FEC4              inc ah
0000001B  90                nop
0000001C  90                nop
0000001D  90                nop
0000001E  BB0500            mov bx,0x5
00000021  90                nop
00000022  90                nop
00000023  43                inc bx
00000024  43                inc bx
00000025  CD10              int 0x10
00000027  90                nop
00000028  B84F0D            mov ax,0xd4f
0000002B  90                nop
0000002C  90                nop
0000002D  FEC4              inc ah
0000002F  90                nop
00000030  90                nop 
00000031  90                nop
00000032  BB0500            mov bx,0x5
00000035  90                nop
00000036  90                nop
00000037  43                inc bx
00000038  43                inc bx
00000039  CD10              int 0x10
0000003B  90                nop
0000003C  90                nop
0000003D  90                nop
0000003E  C3                ret

(for the examples below, the rest of the binary is still valid)

+1

00000000  42                inc dx
00000001  0D9090            or ax,0x9090
00000004  FEC4              inc ah
00000006  90                nop

+2

00000001  0D9090            or ax,0x9090
00000004  FEC4              inc ah
00000006  90                nop

+6

00000000  C4909090          les dx,[bx+si-0x6f70]
00000004  BB0500            mov bx,0x5
00000007  90                nop
00000008  90                nop
00000009  43                inc bx
0000000A  43                inc bx
0000000B  CD10              int 0x10

+11

00000000  050090            add ax,0x9000
00000003  90                nop
00000004  43                inc bx
00000005  43                inc bx
00000006  CD10              int 0x10

+12

00000000  00909043          add [bx+si+0x4390],dl
00000004  43                inc bx
00000005  CD10              int 0x10

+18

00000000  1090B84F          adc [bx+si+0x4fb8],dl
00000004  0D9090            or ax,0x9090
00000007  FEC4              inc ah
00000009  90                nop

(other offsets are just repetitions of the above)

+58

00000000  10909090          adc [bx+si-0x6f70],dl
00000004  C3                ret

Answer 8

PHP

Here you go, a valid PHP program:

Is this still funny?

Answer 9

Scala

A nested quotes:

""""""""""""""""""""""""""""""""

C++/Java/C#/Scala

Comment:

///////////////////////////////////

Empty command:

;;;;;;;;;;;;;;;

Bash

Comment, Whitespace and Shell builtin combination:

#

:

Sed

Standalone valid commands:

p P n N g G d D h H

A combination of the above:

p;P;n;N;g;G;d;D;h;H;

AWK

To print every line of the file:

1

or

//

Don't print anything:

0

Perl

abcd

Answer 10

J

First, a script to check valid rotations of a program s:

check =: 3 :'((<;(". :: (''Err''"_)))@:(y |.~]))"0 i.#y'

For example, the program +/1 5 (sum of 1 and 5) gives:

 check '+/1 5'
┌───────┬───┐
│┌─────┐│6  │
││+/1 5││   │
│└─────┘│   │
├───────┼───┤
│┌─────┐│Err│
││/1 5+││   │
│└─────┘│   │
├───────┼───┤
│┌─────┐│Err│
││1 5+/││   │
│└─────┘│   │
├───────┼───┤
│┌─────┐│6  │
││ 5+/1││   │
│└─────┘│   │
├───────┼───┤
│┌─────┐│6  │
││5+/1 ││   │
│└─────┘│   │
└───────┴───┘

Then, a boring, valid program:

check '1x1'
┌─────┬───────┐
│┌───┐│2.71828│ NB. e^1
││1x1││       │
│└───┘│       │
├─────┼───────┤
│┌───┐│       │ NB. Value of variable x11
││x11││       │ 
│└───┘│       │
├─────┼───────┤
│┌───┐│11     │ NB. Arbitrary precision integer
││11x││       │
│└───┘│       │
└─────┴───────┘

Answer 11

dc

dc programs are easily valid in any rotation. For example:

4 8 * 2 + p  # 34
8 * 2 + p 4  # stack empty / 10
...

Answer 12

k

.""

Evaluates an empty string

"."

Returns a period character

"".

Returns partial application of '.' (dyanic form) to an empty character list.

Answer 13

Machine Code

How about Z80 / Intel 8051 machine code for NOP.

Sure it does No Operation, but it DOES take up a cycle or two... you can have as many or as few of them as you want.

And I disagree with Ruby answer above - I think a single byte 00h is shorter than a Ruby p.

Answer 14

sh, bash

cc
cc: no input files

cc rotated is cc again, but it is not very friendly if called so naked.

dh 
dh: cannot read debian/control: No such file or directory
hd 

dh debhelper isn't very cooperative too, while hexdump just waits for input.

gs
sg 

Ghostscript starts interactive mode, while switch group shows a usage message - a valid solution here, imho, too.

And here is the script to find candidates for such programs:

#!/bin/bash
for name in /sbin/* /usr/sbin/* /bin/* /usr/bin/*
do 
    len=${#name}
    # len=3 => 1:2 0:1, 2:1 0:2
    # len=4 => 1:3 0:1, 2:2 0:2, 3:1 0:3
    for n in $(seq 1 $((len-1)))
    do
        init=${name:n:len-n}
        rest=${name:0:n}
        # echo $init$rest
        which /usr/bin/$init$rest 2>/dev/null >/dev/null && echo $name $init$rest $n
    done 
done

If finds longer sequences too, like (arj, jar) or (luatex, texlua) which aren't valid after every shift, but only after some certain shifts, which I misread in the beginning, but there are few, so it is easy to filter them out by hand.

Answer 15

Trivial Python example:

"a""b""c""d""e""f""g""h""i""j""k""l""m""n""o""p""q""r""s""t""u""v""w""x""y""z""";print

May be shifted three chars over repeatedly to reveal more and more of the alphabet.

Answer 16

Python

123456789.0

Just evaluate some numbers

Answer 17

dc is already used, but the following program always outputs the same, no matter the rotation :D

d

ouputs

dc: stack empty

Answer 18

APL, 1 byte

⍬

Prints empty array. If the program should print something clearly visible:

⍬⍬

Prints a nested array, consisting of two empty arrays:

┌┬┐
│││
└┴┘

In addition, I tried to come up with a program that does something radically different with each shift.

*1⍝ Prints 2.718281828
1⍝* Prints 1
⍝*1 Prints nothing

However, the question arises whether the last line can be considered a program that does something, because it is just a comment that does nothing.