The aim of this challenge is to write a program that satisfies the following conditions:

  • The program is not palindromic, or essentially palindromic (meaning that it is possible to remove characters to make it a palindrome without changing the effects of the program).

  • The program is not an involution (meaning that it does not produce its original input when run on its output)

  • The reversed-polarity program is the inverse of the normal program; so when the reversed program is run on the output of the normal program, it returns the original input.

What does reversed-polarity mean? Well, it differs between languages.

  • For most non-esolangs, this means reversing the order of sub-operations in a single operation, reversing the order of arguments, and reversing the contents of hard-coded lists/arrays/tuples/dictionaries/stacks/queues/etc, as well as reversing the order of code-blocks and stand-alone lines (but not lines within blocks)

Examples:

Haskell: x`mod`y -> y`mod`x;zipWith ((*3).(+)) [1,2,3] [4,5,6] -> zipWith ((+).(*3)) [6,5,4] [3,2,1]

Python: 2**3 -> 3**2; for x,y in [(1,2),(3,4),(5,6)] -> for y,x in [(6,5),(4,3),(2,1)]

  • For languages that have 1-character functions (like Pyth, APL), simply reverse the string of instructions

  • For 1-dimensional esolangs like BF, reverse the instructions or swap the polarity; polarity swaps are [] -> {}, + -> -, - -> +, > -> <, < -> >, . -> , and , -> . (but not both)

  • For 2-dimensional esolangs like Befunge, you may either perform a reflection across the x- or y- axes or a diagonal, rotate 180 degrees, or do a combination of a reflection and a rotation

Commutative operations are allowed, but palindromic ones are not: 2*x is fine, but x+x is bad. The definition of a polarity-reversal is pretty loose, but use your judgment as to what makes sense; the object isn't to find the most clever loophole, but to find the most clever solution.

This is a popularity contest, so a very clever loophole may be popular, but try to keep within the spirit of this challenge. The winner will be announced once there are at least 10 solutions with at least 1 upvote, and there is at least one solution with more upvotes than there are submissions with at least 1 upvote; or in 1 month, whichever comes first. This is my first challenge, so try to be fair and give me constructive feedback, but also let me know if this is an unreasonable challenge or it is in any way miscategorized or ambiguous. If you have questions about a language that don't fit into any of the pigeonholes I have set out here, comment, and I will bend to the will of the community if there is a strong outcry for a particular clarification or rule-change.

UPDATE

It has been exactly 1 month since this contest was started (I just happened to check on it by chance, not knowing that I was actually on time). As this is a popularity contest, the winner (by a landslide) is Pietu1998-Befunge. Even though the bottom components (the text reverser and the backwards-alphabet) are both involutions, the encoder/decoder are not, so there is no problem there. Bonus points (in my mind) for managing to write "BEFUNGE" down the middle. I personally liked the novelty of Zgarb's Theseus solution, because the language looks cool (if restricted). Thanks to everyone for participating, and while the winner has been chosen, I am leaving this contest completely open, and welcome future submissions.

  • 1
    What do you mean by the reversed-polarity program is the inverse of the normal program? Does output differ in some way? – Sp3000 Nov 18 '14 at 23:58
  • It performs the inverse operation; when the reversed program is run on the output of the normal program, it returns the original input. – archaephyrryx Nov 18 '14 at 23:59
  • Sorry for the error; I hadn't heard of it before, and it seemed a bit grotesque to me, so I must have assumed it was an Esolang; I will change that. – archaephyrryx Nov 19 '14 at 0:02
  • 1
    Just something that should probably be specified - is () palindromic? Technically, the reverse is )(. – Sp3000 Nov 19 '14 at 0:07
  • 1
    In the Haskell example why is the function argument not shuffled to the end? Are the reverses chosen in such a way that preserves type safety? Are we allowed to choose some details of the polarity reversal operation? – John Dvorak Nov 19 '14 at 8:23
up vote 41 down vote accepted

Befunge

Whoa, that was a job, even with the editor I made for this challenge. Here's what I got, a nice 11x12 block:

v$,g6<6g,$v
v,$ _^_ $,v
1W>v\B\v>L1
~T+:1E1:-O~
+F00-F-02L+
>:|6gUg6|:>
{a@>^N^>@z`
>1+|@G$| +>
:^9< E<  ^1
~>7^@_,#:>:
 xD>65 ^=P~
v,-\+**<  v

It does a couple of things, sadly only for lowercase letters.

What it does

When run normally, it performs a Caesar cipher on the input.

abcxyz      -> bcdyza
exampletext -> fybnqmfufyu

When flipped horizontally, it reverses said cipher. This is the requirement for the challenge, but it doesn't end here.

bcdyza      -> abcxyz
fybnqmfufyu -> exampletext

When flipped vertically, it ciphers input with a reverse alphabet. This can be considered the opposite approach to the Caesar cipher.

abcxyz      -> zyxcba
exampletext -> vcznkovgvcg

Finally, when rotated 180 degrees, it reverses input. I have a feeling it has to be a reverse of something (hint: the input).

abcxyz      -> zyxcba
exampletext -> txetelpmaxe

How it works

The block basically consists of four semi-overlapping algorithms.

Caesar cipher encoder

v$,g6<
v,$ _^
1 >v\
~ +:1
+ 00-
>:|6g
{a@>^

Caesar cipher decoder (flipped horizontally)

v$,g6<
v,$ _^
1 >v\
~ -:1
+ 20-
>:|6g
`z@>^

Reverse alphabet cipher (flipped vertically)

v,-\+**<
   >65 ^
~>7^
:^9<
>1+|@
   >^

Text reverser (rotated 180 degrees)

v  <
~      
:>:#,_@
1^  <
>+ |$
   >^
  • 2
    I suppose Befunge is at a slight advantage here, because you can always just use the upper left quadrant and completely ignore what's in the rest of the code. Nice work though! – Martin Ender Nov 19 '14 at 17:28
  • 1
    Wow! I HAVE to upvote this, even though that means I drop down to third place. – Level River St Nov 19 '14 at 19:35

Brainfuck, 5

,+.-,

Possibly for the first time ever, Brainfuck produces an answer that is competitive on code length. Shame it's not a code-golf question.

Inputs a byte (character) , increments it, and outputs the result. The comma at the end is waiting for another input, which if given will be ignored. There is nothing in the spec about proper termination :-)*

*(or about doing something useful with all the code in both directions)

Typical results (second character if given is ignored).

Forward: B --> C

Reverse: B --> A or C --> B

Marbelous

Here is a simple one to start us off. It reads one character from STDIN, increments and prints it.

--
]]
00
]]
++

If we rotate this by 180° (without swapping brackets), or mirror it in the x-axis, we get

++
]]
00
]]
--

which reads a byte from STDIN and decrements it.

You can test it here.

I might look into some more complicated Marbelous programs, but I'm sure es1024 will beat me to it. ;)

Explanation

The 00 is a marble with value 0 (which is arbitrary). The ]] devices read a byte from STDIN - that is, if a marble falls through them, the marble's value is changed into the read byte. The ++ and -- devices simply increment or decrement a marble's value (mod 256) and let it fall through. When a marble falls off the board, the byte is written to STDOUT.

Therefore, the two devices at the top are simply ignore because control flow never reaches them.

  • Alternately, you could replace your three middle rows by a single input device. – overactor Nov 19 '14 at 11:38
  • @overactor Or do you mean }0 and use it as a subboard? – Martin Ender Nov 19 '14 at 11:57
  • }0 as a command line input to be precise. – overactor Nov 19 '14 at 12:04

Marbelous

This board takes one argument (x) and returns (101 * x) mod 256.

.. @5 .. }0 }0 @1 .. @0 .. @2 .. 
.. /\ Dp << \\ .. &0 >0 &1 .. .. 
!! @3 .. << }0 .. \/ -- \/ .. }0 
@4 .. .. &0 @1 /\ &0 65 &1 /\ @2 
/\ Dp .. @4 .. .. @3 @0 @5 !! \\

Mirroring the cells along the y-axis will result in a board that takes one argument (y) and returns (101 * y + 8 * y) mod 256, which is the inverse of the first board.

.. @2 .. @0 .. @1 }0 }0 .. @5 ..
.. .. &1 >0 &0 .. \\ << Dp /\ ..
}0 .. \/ -- \/ .. }0 << .. @3 !!
@2 /\ &1 65 &0 /\ @1 &0 .. .. @4
\\ !! @5 @0 @3 .. .. @4 .. Dp /\

Test this here. Cylindrical boards and Include libraries should both be checked.

Example input/output:

Original Board:      Mirrored Board:
Input   Output       Input    Output
025     221          221      025
042     146          146      042
226     042          042      226

Please note that Marbelous only allows for passing of positive integers as arguments, and these integers are passed into the program modulo 256 by the interpreter.

101 was chosen for two reasons: it is a prime (and every possible input to this program results in a unique output), and the inverse operation involved 109, which is a convenient distance of 8 away from 101.

Brief Explanation

The column containing the cells (from top to bottom) @0 >0 -- 65 @0 runs the same in both boards, and loops 101 times before heading to the right. On either side of the >0 branch is a different synchroniser; which one is chosen depends on whether the board is mirrored or not.

On each side, in sync with the center loop, the input is repeatedly summed, thus obtaining 101*x mod 256. On the reversed board, two copies of the input are also bit shifted twice to the left (input * 4), then summed and left in a synchroniser.

Once the center loop finishes, the summed up marbles are sent for printing, which is on the side of the board (left for original board, right for mirrored). After printing, a !! cell is reached, terminating the board. Note that the loop that gave 101 * x continues to run by itself until the board is terminated.

Dp simply prints out the result as a decimal number.

Theseus

This may be considered as a loophole, but I like the language, so here goes. This program defines a function f on natural numbers that maps 3n to 3n+1, 3n+1 to 3n+2, and 3n+2 to 3n, for every n.

data Num = Zero | Succ Num

iso f :: Num <-> Num
  | n                          <-> iter $ Zero, n
  | iter $ m, Succ Succ Succ n <-> iter $ Succ m, n
  | iter $ m, Succ Succ Zero   <-> back $ m, Zero
  | iter $ m, Succ Zero        <-> back $ m, Succ Succ Zero
  | iter $ m, Zero             <-> back $ m, Succ Zero
  | back $ Succ m, n           <-> back $ m, Succ Succ Succ n
  | back $ Zero, n             <-> n
  where iter :: Num * Num
        back :: Num * Num

Theseus is a reversible language with a Haskell-like syntax, where every function is invertible (discounting issues with non-termination). It is highly experimental, and designed for research purposes. The above code defines a datatype for natural numbers, and the function f. Given an input number, you pattern-match to it on the left-hand side (it always matches n). Then you look at the pattern on the right. If that pattern has a label (here iter), you proceed to pattern-match it on the left-hand side, and again take the corresponding value on the right-hand side. This repeats until you have an unlabeled value on the right, and that is your output. The patterns on the left, and on the right, must be exhaustive and non-overlapping (separately for each label). Now, to "reverse the polarity" of f, I do the following.

  • Swap the two values of every label. This does not change the semantics of f.
  • Swap the right- and left-hand-sides in the function body. This defines the inverse function of f by design.

The result:

iso f :: Num <-> Num
  | iter $ n, Zero             <-> n
  | iter $ n, Succ m           <-> iter $ Succ Succ Succ n, m
  | back $ Zero, m             <-> iter $ Succ Succ Zero, m
  | back $ Succ Succ Zero, m   <-> iter $ Succ Zero, m
  | back $ Succ Zero, m        <-> iter $ Zero, m
  | back $ Succ Succ Succ n, m <-> back $ n, Succ m
  | n                          <-> back $ n, Zero
  where iter :: Num * Num
        back :: Num * Num

tr

a b

Example:

$ echo "apple" | tr a b
bpple
$ echo "bpple" | tr b a
apple

Only a true inverse on the domain of strings that don't include both 'a' and 'b'.

  • You actually need to restrict the domain a bit more than that. For example, if you start with "bog", your program and its reverse give "bog" -> "bog" -> "aog". So any string containing 'b' is a problem (or containing 'a', if you apply the reverse program first). – user19057 Nov 19 '14 at 22:57
  • You can use tr abc bca with the reversed polarity version tr acb cba. – Christian Sievers Oct 12 '16 at 1:18

Another Marbelous answer

The original right shifts the command line input (an 8 bit value), adding a leading one if a 1 gets lost by shifting. (0000 0001 -> 1000 0000)

{0 ..
~~ ..
>> {0
-2 =0
.. ^0
\/ }0
}0 Sb
<< ..
\\ ..
:Sb
// ..
Sb >>
}0 ..
^7 }0
{0 \/

Rotating this board by 180° (but leaving the content of each cell the same) Changes the program so that it left shifts (1000 0000 -> 0000 0001)

\/ {0
}0 ^7
.. }0
>> Sb
.. //
:Sb
.. \\
.. <<
Sb }0
}0 \/
^0 ..
=0 -2
{0 >>
.. ~~
.. {0

You can test it here. (you'll need to turn on 'Display output as decimal numbers')

Explanation

Both program consist of two boards, the main board (which gets the command line input) and Sb. Lets have a look at both versions of the main board, only looking at cells that can be reached in their respective orientation (since marbles typically can't go upwards and the input devices are not at the top):

original:      flipped:
   }0          }0
}0 Sb          .. }0
<< ..          >> Sb
\\ ..          .. //

Those are pretty straightforward boards, both take two copies of the input (which take the place of the }0cells. The original feeds one version into a left shift device << the flipped version puts it in a right shift device >> These perform a bitshift but unfortunately discard any lost bits. Which is where the Sb boards come in, they check if bitshifting the value they're fed will result in a bit being lost and return a value to be added to the result to counteract the lost bit.

Here's the relevant part of the original Sbboard for the original program:

}0
^7
{0

This one is incredibly easy, `^7' checks the value of the most significant bit. If this one is 1, performing a left shift would cause this bit to be lost. So this board outputs the value of this bit as an 8 bit value to be added to the result of the bitshift.

For the flipped version, Sbhas to look at the least significant bit and return 128 or 0, this is a little bit more complicated:

}0
^0 ..
=0 -2
{0 >>
.. ~~
.. {0

If the least significant bit (as tested by ^0) is 0, it just returns 0. If it is one, ^0 will output 1. This will fail the equality test with 0 =0 and thus be push to the right. We then subtract 2 -2to get 255, left shift >> to get 127 and perform a binary not ~~ to get 128 (we could also simply have added one ++ to get 128, but where's the fun in that?)

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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