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!

• Peter Taylor: There are some very boring potential answers in languages in which an int literal is a valid program. Do they receive a virtual -100?
• Griffin: @PeterTaylor I'm assuming that boring answers will receive less votes.
• dmckee --- ex-moderator kitten: "Potentially very difficult" It is always helpful to be familiar with a lot of oddball languages before make this kind of statement in a general way. Hard in c or java, sure, but in languages with 1 character commands and simple syntaxes? Not so much.
• Griffin: @dmckee hence the "Potentially"...
• jk.: @PeterTaylor also in plenty of languages the empty program is a valid program

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.

• ChristopheD: Very nice entry!

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?

• Peter: you should have used a word like "ate" (I'm sure there are longer ones), so that each character shift would still be a real word.
• Lie Ryan: I'm not sure whether to +1 this or -1 this

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

• captncraig: Looks to me like SED would fail on any odd rotation? Is ;P;n;N;g;G;d;D;h;H valid?
• Prince John Wesley: @CMP: yes it is valid.

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.

• Cristian Lupascu: The examples of more than two letters are not valid; the OP said that "the program must be valid after any circular shift". So, arj/jar is not valid, as there is no rja command (although I like this example). +1 for the script - really nice idea :)
• user unknown: Since I was unsure, and not a native English speaker, I consulted a dictionary, where I found it ambiguous, to either mean every, or to mean a random one. The example with shift left by 6, left by 1 and right by 10 assured me in the interpretation, that I just need to find a single shift possibility.
• Griffin: It is not ambiguous. If a program has to be valid after some random shift, then it must also be valid for every possible shift.
• user unknown: @Griffin: Okay - you wrote the question. I removed the longer examples; fortunately there are enough crptc abbrv prgnms in unix like gs and sg. :) Btw.: Are you a native Englisch speaker? In the sentence before, you wrote ... in any language ... - my solution only works in bash (and sh, zsh, ash and a few else), but all those other solutions take program names too.

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.

• Griffin: Sorry, I should have made my question clearer. Any shift must produce a valid program. I've updated the question.

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.