Shuffle

Shuffle

Paradigm(s)	Imperative
Designed by	User:Enoua5
Appeared in	2016
Memory system	Cell based
Computational class	Unknown
Major implementations	Version 2.0
File extension(s)	.deck

Introduction

Shuffle was created by User:Enoua5 in November of 2016. It reads instructions from a "deck of cards" by playing the card game War. An updated 2.0 version adding a couple new features was created in June of 2021.

Note that .deck files must be encoded as UTF-8

Documentation

Syntax

Valid characters

The Unicode playing cards (U+1F0A1 to U+1F0DF), with the exception of the knight cards encode Shuffle's commands. Cards in this range that are "reserved" are interpreted as jokers. All other characters are comments.

In version 2.0, a few more characters can have syntactic meaning, as explained later.

File Format

The file is split into either two or four sections, the four section variant being exclusive to version 2.0. Each section is separated from the others by two line breaks. Section 1 is Player One's deck, Section 2 Player Two's, Section 3 is the initial data pointer position, and Section 4 is the initial memory state.

Decks

Each player's deck is defined as a sequence of cards. By default, these are the Unicode playing cards mentioned previously. The first card in the definition will appear at the top of that player's hand, and each in sequence until the last defined is at the bottom.

These decks don't need to be of equal size, don't need to contain all cards, and can have duplicate cards.

An optional convention in version 2.0 is for bracket-notation cards. To use these, a flag must be set in the interpreter, otherwise they will be ignored just like any other comment character. Cards defined this way begin with an open square bracket '[', followed immediately by a single lowercase letter describing the suit: 'h' for heart, 'd' for diamond, 'c' for club, 's' for spade, or 'j' for joker. Immediately following that, any positive integer to for the card's value. The definition closes off with a close square bracket ']', and no other characters beyond what was described here are allowed between them.

The main reason the bracket version exists, is that it allows cards to have values greater than 13. This is also why it's disabled by default, as using it with a "skip n" command allows the program to skip all of the shuffled commands, defeating the point of the language, really.

Initial Pointer

Section 3, if included, contains the starting data pointer. This is written as two decimal numbers, separated by one or more white-space characters. Negative values are allowed. The first is the x value, and the second is the y value.

Initial Memory State

Section 4, if included, contains the starting memory state. This is written as a series of decimal numbers. The first number listed is placed at (0,0), and the following numbers — separated by one or more non-linefeed white-space characters — are put to the right cell by cell. A newline character causes the data copying to continue on the next line down, back at the left. These lines don't have to be even, unspecified values will be filled in with zeros.

Running

Memory Layout

The program manipulates unsigned 8-bit numbers on an infinite grid of cells. There is a pointer that points to the number currently being manipulated. This pointer can be moved around in 4 directions, one cell at a time. If the number under the pointer goes above 255 or below 0, it wraps around. All cells start with a value of 0, unless specified otherwise in Section 4.

Card meaning

Shuffle takes the suits of the two cards which are played as a command. The commands are as defined in the table bellow.

Player One Suit	Player Two Suit	Effect
Spade (move pointer)	Spade	Move pointer to the right.
	Heart	Move pointer down.
	Diamond	Move pointer up.
	Club	Move pointer to the left.
Heart (skip)	Spade	If the current cell has a value of zero, interpret the next command as NOP.
	Heart	Interpret the next n commands as NOP, where n is the value of Player One's card.
	Diamond	Interpret the next command as NOP.
	Club	If the current cell has a value of zero, interpret the next n commands as NOP, were n is the value of Player One's card.
Diamond (math)	Spade	Subtract the value of Player One's card from the current cell.
	Heart	Add one onto the current cell.
	Diamond	Subtract one from the current cell.
	Club	Add the value of Player One's card to the current cell.
Club (IO)	Spade	Get user input in the form of an 8-bit character and save the value to the current cell.
	Heart	Output the value of the current cell as an int.
	Diamond	Output the value of the current cell as an 8-bit character.
	Club	Get user input in the form of an 8-bit unsigned int and save the value to the current cell.

If a joker is played (and is not interpreted as NOP), the program terminates.

Card values

Card	Value
Joker	0
Ace	1
2	2
3	3
4	4
5	5
6	6
7	7
8	8
9	9
10	10
Jack	11
Queen	12
King	13

"Game play"

At the beginning of each round, both players will play the card on the top of their deck. These two cards are then run as instruction. Whichever player has the higher value card gets both of the played cards added to the bottom of their deck with the higher valued card on the bottom. The next round is then played.

Tie breaking

In the event that both players play cards of the same value, each player forms a "stakes" pile. The two players then will add cards from the top of their deck to the bottom of their stakes pile until they have placed three cards each. A player will not add a card to their stakes if it is their last card. The six (three from each player) cards added to the stakes do not have their commands run.
Each then adds one more card to the bottom of their stakes. These last two cards are run. The values of the two most recently placed cards are then compared. Whoever has the higher value card gets the stakes piles added onto the bottom of their own; with the winning stake pile under the losing pile. The next round is then played.

If the cards once again have the same value, then the players repeat the tie-breaking process without clearing the stakes piles. This continues until a winner is decided, or until a player runs out of cards.

End of program

When one of the two players run out of cards, the program terminates. Alternatively, if a joker is ran as a command, the program terminates.

Example programs

Quit

Exits the program on startup

🃏

🃟

Since the first command in this program contains a joker, the program immediately terminates. This is considered the "nice" method of terminating a program, though simply having one player run out of cards also works.

1 byte cat

Gets a char input, then outputs it

🃒🃓

🂡🃁

This program consists of two commands. The 2 of clubs combines with the ace of spaces to get an ascii value from the user. Next the 3 of clubs and ace of diamonds combine to output that character. The program terminates as Player Two runs out of cards

Hello

Prints "Hello" with a trailing new-line

🃎🃎🃎🃎🃎🃇🃞🃎🃎🃃🃞🃇🃞🃞🃃🃞🂮🃊🃞

🃑🃑🃑🃑🃑🃑🃁🃑🃑🃑🃁🃑🃁🃁🃑🃁🂡🃑🃁

This program uses addition and subtraction to put the ascii values for "Hello" into the starting memory cell one by one, using club-diamond to output them.

Loop

Loops forever.

Found by reading this paper: https://math.pugetsound.edu/~mspivey/War.pdf

🂾

🂱🂾

Since there are no commands to loop, or even jump backward in Shuffle, looping must be done by constructing a deck that will periodically return to its starting state. One way of accomplishing this is by having splitting the cards into two categories, A and B, where the value of all A cards is greater than the value of all B cards. If both players' decks end with an A card, and one player has one more card than the other, then the program will loop forever (until a joker is ran).

Truth-machine

🃑🃞🂲🂾🃏🂷

🃞🂱🂮🃁🂾🂱🂾

This program shows the main obstacle in creating programs in Shuffle. After just six commands, the program needs to return to the start state in order to run the next loop and continue outputting 1s. However, after running the first six commands, the cards are all moved around between the two decks. For example, in the execution of the second command, the Player Two's Ace of Diamonds is placed at the end of Player One's deck, pairing it with Player Two's King of Hearts. This diamond-heart would be interpreted to mean "Add 1 onto the current cell", a command that is run despite never being explicitly written! To combat this, the program ends in a "Skip 7" command, causing the next seven commands to be ignored, and allowing the program to return to the start state. Interestingly, the start state it returns to *doesn't* have all the cards in their original positions, but it does just so happen to have all cards swapped in matching pairs where needed.

Hello, world!

Hello world program using version 2.0 features!
Also shown off in this program: comments!
We can include pretty arbitrary text here, we just need to avoid
using any \n\n combos, and avoiding open square brackets is also good.
Anyway, here's the instuctions that will be being ran:
if 0, skip (since there's no if 1, we have to do this double skip thing)
skip
halt
output char
right
jump to next iteration of the program
Card parings: HS HD J* CD SS HH
🂱🂾🃟🃞🂡🂶

🂮🃁🂮🃁🂮🂱🂮 <- this last card is an arbitrary high card
No comments allowed after this section :(
So, to explain the below parts here, the "0 0" isjust saying to start the data pointer at (0,0) which is default, but we have to specify 
to be allowed to use the extra sections.
The numbers after that are the string "Hello, world!\n" in ascii. This gets loaded into the memory space before starting.

0 0

72 101 108 108 111 44 32 119 111 114 108 100 33 10

Similar to the Truth Machine example, the cards aren't returning to their original positions after the 6 ignored commands, but the ones that out of place are all swapped with matching cards:

If the original cards were numbered

 1  2  3  4  5  6
 7  8  9 10 11 12 13

then after the running the six commands, and ignoring the next six, we have:

 1  2  3  4  5  6
11  8 12 10  7 12  9

which has 9/13 cards in the right spot, where all the cards in incorrect spots just so happen to be the King of Spades, filling each other's spots.

If the program didn't have this symmetry, we would need to skip 18 instructions rather than 6, which is higher than we can accomplish with a single skip. We would either have to use bracket cards (cheating!), hope that one of the shuffled commands is a skip of the right size, or hope that the shuffled commands don't mess up the state of the program.

Rule 110

Rule 110
111 110 101 100 011 010 001 000
 0   1   1   0   1   1   1   0
-
This program does not have interactive IO. To set the starting
state of the Rule 110 simulation, edit the last line of this program; use '1' to represent 1 and '255' to represent zero.
To see the output of the program, use the --pgm or --csv opts
in the default interpreter. Note, again, the program uses 255
to represent 0.  
-
Rule 110 implementation using a bracket card to return to top, so program must be ran with -b flag.
Bracket cards were avoided all other places. Because of this,
There are relays throughout the program to extend jump ranges.
-
Explanation for below:
Each row will contain the actual card that is ran,
followed by a text representation of that card and
the card it's paired with
(the actual pair card is later)
followed by a mnemonic that to explain what the program is doing.
comments will be denoted with a #, sections with === text ===
and labels with :text. This is just for human readability,
Shuffle has no comment character.
High cards are >= 9 for this program
-
=== determine which loop is being performed ===
🂾 Hk Sa skip if zero
🂸 H8 Hk jump :update
=== seek to beginning of line ===
  🂮 Sk Da up
  # if there is a zero, then we've found uninitialized memory
  🂳 H3 Ck jump if zero :mark_end
    🂮 Sk Ca left
    🂡 Sa Hk down
    🂹 H9 Ha jump :end
  :mark_end
    🂡 Sa Hk down
    🃎 Dk Ha inc
    🂶 H6 Hk jump :end
=== update the current cell ===
:update
  🂮 Sk Da up
  🂡 Sa Sk right
  🂾 Hk Ca jump if zero :right_is_uninit
  # check if it's -1, which we're using as 0
  🃁 Da Hk inc
  🂾 Hk Ca jump if zero :right_is_zero
  === relay ===
    🂱 Ha Dk skip
    🂾 Hk Ha jump :end
  ===       ===
  🃁 Da Dk dec
    # right is one possible states from here:
    # 111 101 011 001
    #  0   1   1   1 
    # the only case for a 0 is if all else are 1
    🂮 Sk Ca left
    🃁 Da Dk dec
    🂺 Hx Ca jump if zero :+continue
      🃁 Da Hk inc
      🂾 Hk Ha jump :write_one
      🂱 Ha Hk (unconditionally skipped, used for spacing)
      🂾 Hk Ha (unconditionally skipped, used for spacing)
      === relay ===
        🂱 Ha Dk skip
        🂾 Hk Ha jump :right_is_uninit
      ===       ===
      === relay ===
        🂱 Ha Dk skip
        🂾 Hk Ha jump :right_is_zero
      ===       ===
      === relay ===
        🂱 Ha Dk skip
        🂾 Hk Ha jump :end
      ===       ===
    :+continue
    🃁 Da Hk inc
-
    🂮 Sk Ca left
    🃁 Da Dk dec
    🂻 Hj Ca jump if zero :+continue
      === relay ===
        🂱 Ha Dk skip
        🂾 Hk Ha jump :write_one
      ===       ===
      🃁 Da Hk inc
      🂮 Sk Sa right
      === relay ===
        🂱 Ha Dk skip
        🂺 Hx Ha jump :right_is_uninit
      ===       ===
      === relay ===
        🂱 Ha Dk skip
        🂻 Hj Ha jump :right_is_zero
      ===       ===
      === relay ===
        🂱 Ha Dk skip
        🂾 Hk Ha jump :end
      ===       ===
      🂴 H4 Hk jump :write_one
    :+continue
    🃎 Dk Ha inc
    🂡 Sa Sk right
    # if we've made it this far, they were all ones
    🂻 Hj Ha jump :write_zero
    === relay ===
      🂱 Ha Dk skip
      🂻 Hj Ha jump :write_one
    ===       ===
-
  :right_is_uninit
    🂡 Sa Ck left
    🂮 Sk Ha down
    === relay ===
      🂱 Ha Dk skip
      🂺 Hx Ha jump :right_is_zero
    ===       ===
    🃁 Da Dk dec
    🂮 Sk Sa right
    === relay ===
      🂱 Ha Dk skip
      🂹 H9 Ha jump :end
    ===       ===
    === relay ===
      🂱 Ha Dk skip
      🂹 H9 Ha jump :write_zero
    ===       ===
    === relay ===
      🂱 Ha Dk skip
      🂺 Hx Ha jump :write_one
    ===       ===
    🂡 Sa Dk up
    🂾 Hk Da skip
  :right_is_zero
    # we reach here if right was -1, so we have to put it back as we found it
    🃁 Da Dk dec
  :+
    # since right is zero, the possible states are:
    # 110 100 010 000
    #  1   0   1   0
    # so the value to write is the center value
    🂮 Sk Ca left
    === relay ===
      🂱 Ha Dk skip
      🂾 Hk Ha jump :end
    ===       ===
    === relay ===
      🂱 Ha Dk skip
      🂽 Hq Ha jump :write_zero
    ===       ===
    🂶 H6 Ck jump if zero :write_zero_default
    === relay ===
      🂾 Hk Da skip
      # actually hits a different jump command
      🂳 H3 Hk jump :write_one
    ===       ===
    🃎 Dk Ha inc
    🂸 H8 Ck jump if zero :write_zero_with_fix
    🃎 Dk Da dec
    # center was one
    🂷 H7 Hk jump :write_one 
-
  :write_zero_default
    🂮 Sk Ha down
    🃁 Da Dk dec
    🂮 Sk Da up
    === relay ===
      🂱 Ha Dk skip
      🂾 Hk Ha jump :end
    ===       ===
    🂳 H3 Hk jump :write_zero
  :write_zero_with_fix
    === relay ===
      🂾 Hk Da skip
      🂸 H8 Hk jump :write_one
    ===       ===
    🃎 Dk Da dec
  :write_zero
    🂡 Sa Hk down
    🂮 Sk Ha down
    # padding to get the right high-low order for the jump
    🂲 H2 Hk jump 2
    🂾 Hk Ha (unconditionally ignored)
    🂱 Ha Hk (unconditionally ignored)
    🃎 Dk Da dec
    🂵 H5 Hk jump :end_update
-
  :write_one
  🂮 Sk Ha down
  === relay ===
    🂱 Ha Dk skip
    🂺 Hx Ha jump :end
  ===       ===
  🂡 Sa Hk down
  🃎 Dk Ha inc
:end_update
  🂡 Sa Dk up
  🃎 Dk Ha inc
  🂶 H6 Ck jump if zero :flag_seek
    🂮 Sk Sa right
    # padding to get the right high-low order for the jump
    🂲 H2 Hk jump 2
    🂾 Hk Ha (unconditionally ignored)
    🂱 Ha Hk (unconditionally ignored)
    🃎 Dk Ha inc
    🂲 H2 Hk jump :end
  :flag_seek
    🂮 Sk Ha down
    🂡 Sa Hk down
:end
Evil bracket card that jumps so far that I have no confidence I could make this program using regular cards
[H12321] H(lots) Ha jump to beginning of program

🂡🂾🃁🃞🃑🂾🂱🂾🂱🂾🃁🂮🃑🂾🃑🃎🂱🃎🃑🃎🃑🂾🂱🂾🂱🃎🂱🃎🂱🃎🂱🂾🃑🃎🃑🃎🂱🂾🂡🃎🂱🃎🂱🃎🂱🂾🂱🂮🂱🃎🂱🃞🂱🃎🂱🃎🂡🃎🂱🃎🂱🃎🂱🃎🃁🃎🃑🃎🂱🃎🂱🃞🃁🂾🂱🃞🃁🂾🂱🃎🃁🃎🂱🂾🃁🂾🃁🂾🂱🂾🂱🂾🃁🂾🂱🃎🂱🂾🂱🃎🂱🃞🂡🂾🂱🂾🂱🂾🂱🂾🂱🂾

0 1

1

Note: while this proves the language is Turing Complete when using bracket cards, bracket cards allow the program to skip the parts of Shuffle that make it hard to work with. As such, this is a "cheating" version of the rule 110 program. A proper implementation using no bracket cards would require the program to go through all the shuffled commands and return to the beginning with the program state unaltered (or altered in a way that continues the computation).