DAMN COVID-19
| Paradigm(s) | Imperative |
|---|---|
| Designed by | Hakerh400 |
| Appeared in | 2020 |
| Computational class | Unknown |
| Major implementations | Interpreter |
| File extension(s) | .txt |
DAMN COVID-19 is a 2D programming language in which the computation is performed by infecting adjacent cells in a 2D square grid.
Overview
Memory consists of unbounded 2D square grid (called map) and a bounded tape of bits. Some cells on the map (tiles) contain cities (at most one city per tile), while other tiles are empty.
Input
Input represents a map of cities (arbitrary large, but finite in size). Input itself is finite in size, but the actual grid is infinite.
All cities must be connected (there cannot be a group of isolated cities - any city can be reached from any other city by moving along adjacent cities). Cities are represented as # characters, while empty tiles are spaces. There must be exactly one * character and it represents the city that is currently infected by the virus. Example of initial grid (input grid):
##### ##### ## ########*##### ##### # #### ##### ##
All connected cities represent an island. If the initial map consists of more than one island, then it is an error. It is also an error if there are no cities at all.
Before the program starts, arbitrary random number of new cities appear at random positions (that number can also be 0) but all cities will remain connected. New random cities cannot appear inside the holes (the above example contains a hole (empty tile surrounded by 4 cities) and new cities cannot appear there).
After new random cities are generated, program starts (and during program execution no new cities can randomly appear).
Source code
Virus can move only along cities (it cannot cross empty tiles). This constraint no longer applies once all cities are infected (a city is infected when a virus visits it; once infected, it remains infected). How the virus moves is defined by the source code.
Virus is always in a single city. Cities that were visited by the virus are inficted, but they cannot spread the virus to adjacent cities.
Source code consists of commands, if/else statements and loops.
If statement is represented as
?condition(
// If the condition is true do this
)
and if-else is represented as
?condition(
// If the condition is true do this
):(
// If the condition is false do this
)
While loop is represented as (note the curly braces)
?condition{
// While the condition is true do this
}
Inverted condition can be achieved by prepending ! before the actual condition.
Here condition is one of
#- Is there a city inside the current tile^- Is there a city above the current tilev- Is there a city below the current tile<- Is there a city on the left>- Is there a city on the right.- Is the value in the current memory cell 1@- Are all cities infected
Except the 2D map of cities, there is also a 1D tape of bits (cells can be either 0 or 1). The tape is finite in size and all cells are initially zeros. The size of the tape is determined by the non-negative integer that must appear on the beginning of the source code.
When all cities are infected, virus can also spread over empty tiles. There is no way for the virus to check whether the current cell is infected or not.
Commands:
^- Go one city upwardsv- Go one city downwards<- Go one city to the left>- Go one city to the right~<- Go one cell to the left (on the tape)~>- Go one cell to the right (on the tape)!- Flip the bit in the current cell (on the tape)@- If there is a city in the current cell, remove it, otherwise add it (works only when all cities are previously infected)%- Teleport to the starting cell (works only when all cities are previously infected)
Commands ^, v, < and > have no effects if both there is no city there and some cities are not infected.
Output
Output is the map of cities that remain when the program halts.
Basic examples of the syntax
Example 1
Source code:
1 // The tape has 1 cell (single bit)
?!@{ // Repeat until all cities are infected
?.( // If the current bit on the tape is 1
// If can go to the right, go right, otherwise flip the bit on the tape
?>(>):(!)
):(
// If can go to the left, go left, otherwise flip the bit on the tape
?<(<):(!)
)
}
// Now all cities are infected (since we are outside of the loop)
?<{<} // Go to the leftmost city
?#{@>} // Delete all cities
Suppose this is the input map:
#### #### # ###*########## # #### ####
Now, before the program starts, new random cities will appear, but they cannot fill the two holes there. So, after random cities appear, the map may look like this:
##
#### ## ####
## ###*########## #####
#### # #####
### # ##
#
Now, the program starts. The tape contains exactly one bit and it is 0. The virus will move to the left until it reaches the empty tile and then it will invert the bit on the tape. We mark infected cities using % character:
##
#### ## ####
## *%%%########## #####
#### # #####
### # ##
#
Since the bit on the tape is now 1, according to the source code, virus will now spread to the right:
##
#### ## ####
## %%%%%%%%%%%%%* #####
#### # #####
### # ##
#
It will again flip the tape bit and come back to the left and so on. It will never halt, because it is not able to infect all cities and the loop will never end.
Suppose that the input was:
###*####
and that no new random cities are created (which has low probability), then the computation will go as follows. First, the virus will go to the left (according to the source code and the tape bit being 0):
*%%%####
Then it will go to the right:
%%%%%%%*
Now, all cities are infected and the main loop ends. Now, we execute ?<{<} and the virus again goes to the left:
*%%%%%%
And at the end, we execute ?#{@>} and no cities remain on the map when the program halts.
Example 2
Source code:
3?!@{?!.{~>?!.(~>?!.(?^(^!~>!):(!~<!~<)):(?>(>!~<!~<!):(!~>))):(~>?!.(?v(v!~>!):(!~<!~<)):(?<(<!~<!~<!):(!~>)))}!}
This program is able to infect any island of cities which does not contain loops.
For example, given the input map:
### # # ####### # * ########
Possible look of the map after adding random cities (interpreter does this):
######
#
#######
##### #
### # #######
# *
#########
And here is the computation step-by-step:
######
#
#######
##### #
### # #######
# *
#########
######
#
#######
##### #
### # *######
# %
#########
######
#
#######
##### #
### # %*#####
# %
#########
######
#
#######
##### #
### # %%*####
# %
#########
######
#
#######
##### #
### # %%%*###
# %
#########
######
#
#######
##### #
### # %%%%*##
# %
#########
######
#
#######
##### #
### # %%%%%*#
# %
#########
######
#
#######
##### #
### # %%%%%%*
# %
#########
######
#
#######
##### #
### # %%%%%*%
# %
#########
######
#
#######
##### *
### # %%%%%%%
# %
#########
######
#
#######
##### %
### # %%%%%*%
# %
#########
######
#
#######
##### %
### # %%%%*%%
# %
#########
######
#
#######
##### %
### # %%%*%%%
# %
#########
######
#
#######
##### %
### # %%*%%%%
# %
#########
######
#
#######
##### %
### # %*%%%%%
# %
#########
######
#
#######
##### %
### # *%%%%%%
# %
#########
######
#
#######
##### %
### # %%%%%%%
# *
#########
######
#
#######
##### %
### # %%%%%%%
# %
#####*###
######
#
#######
##### %
### # %%%%%%%
# %
####*%###
######
#
#######
##### %
### # %%%%%%%
# %
###*%%###
######
#
#######
##### %
### # %%%%%%%
# %
##*%%%###
######
#
#######
##### %
### # %%%%%%%
# %
#*%%%%###
######
#
#######
##### %
### # %%%%%%%
* %
#%%%%%###
######
#
#######
##### %
### * %%%%%%%
% %
#%%%%%###
######
#
#######
##*## %
### % %%%%%%%
% %
#%%%%%###
######
#
#######
##%*# %
### % %%%%%%%
% %
#%%%%%###
######
#
#######
##%%* %
### % %%%%%%%
% %
#%%%%%###
######
#
*######
##%%% %
### % %%%%%%%
% %
#%%%%%###
######
#
%*#####
##%%% %
### % %%%%%%%
% %
#%%%%%###
######
#
%%*####
##%%% %
### % %%%%%%%
% %
#%%%%%###
######
#
%%%*###
##%%% %
### % %%%%%%%
% %
#%%%%%###
######
#
%%%%*##
##%%% %
### % %%%%%%%
% %
#%%%%%###
######
#
%%%%%*#
##%%% %
### % %%%%%%%
% %
#%%%%%###
######
#
%%%%%%*
##%%% %
### % %%%%%%%
% %
#%%%%%###
######
#
%%%%%*%
##%%% %
### % %%%%%%%
% %
#%%%%%###
######
#
%%%%*%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
######
#
%%%*%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
######
#
%%*%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
######
*
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
#*####
%
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
#%*###
%
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
#%%*##
%
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
#%%%*#
%
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
#%%%%*
%
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
#%%%*%
%
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
#%%*%%
%
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
#%*%%%
%
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
#*%%%%
%
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
*%%%%%
%
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
%*%%%%
%
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
%%%%%%
*
%%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%*%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%*%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
%%%%%%
%
*%%%%%%
##%%% %
### % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
##%%* %
### % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
##%*% %
### % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
##*%% %
### % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
#*%%% %
### % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
*%%%% %
### % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
%%%%% %
##* % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
%%%%% %
#*% % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
%%%%% %
*%% % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
%%%%% %
%*% % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
%%%%% %
%%* % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
*%%%% %
%%% % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
%*%%% %
%%% % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
%%*%% %
%%% % %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
%%%%% %
%%% * %%%%%%%
% %
#%%%%%###
%%%%%%
%
%%%%%%%
%%%%% %
%%% % %%%%%%%
* %
#%%%%%###
%%%%%%
%
%%%%%%%
%%%%% %
%%% % %%%%%%%
% %
#*%%%%###
%%%%%%
%
%%%%%%%
%%%%% %
%%% % %%%%%%%
% %
*%%%%%###
%%%%%%
%
%%%%%%%
%%%%% %
%%% % %%%%%%%
% %
%*%%%%###
%%%%%%
%
%%%%%%%
%%%%% %
%%% % %%%%%%%
% %
%%*%%%###
%%%%%%
%
%%%%%%%
%%%%% %
%%% % %%%%%%%
% %
%%%*%%###
%%%%%%
%
%%%%%%%
%%%%% %
%%% % %%%%%%%
% %
%%%%*%###
%%%%%%
%
%%%%%%%
%%%%% %
%%% % %%%%%%%
% %
%%%%%*###
%%%%%%
%
%%%%%%%
%%%%% %
%%% % %%%%%%%
% %
%%%%%%*##
%%%%%%
%
%%%%%%%
%%%%% %
%%% % %%%%%%%
% %
%%%%%%%*#
%%%%%%
%
%%%%%%%
%%%%% %
%%% % %%%%%%%
% %
%%%%%%%%*
Computational class
This programming language is Turing-complete if and only if there is an FSM that can traverse arbitrary large (but finite) island of connected tiles on a square grid.
If the language is Turing-complete, programming can be done like this:
- First, encode the input as a single non-negative integer (call it
N) - Then, create a map consisting of a single row of
N + 1consecutive tiles and two extra holes on both ends (see example below) - Use an algorithm to visit all cities (storing only finite amount of information on the tape)
- When all cities are visited (infected), teleport to the starting tile
- Now, we obtain unlimited amount of memory, because we can now modify the map (add and remove cities), so we can store unlimited information
- Given unlimited memory and while loops, we can implement any algorithm
For example, if N is 3, we create the following initial map:
### ### # *### # ### ###
Random cities can appear at random positions, but not inside the two holes before the program starts. For example, the map may look like this (after random cities appear):
############### ############### ############### #### *### ##### ############### ############### ###############
Then the virus somehow would visit (infect) all cities and teleport to the starting position:
%%%%%%%%%%%%%%% %%%%%%%%%%%%%%% %%%%%%%%%%%%%%% %%%% *%%% %%%%% %%%%%%%%%%%%%%% %%%%%%%%%%%%%%% %%%%%%%%%%%%%%%
After all cities are infected, the virus gains the ability to add and remove cities, so now we can still access the integer N (two holes are preserved and we can count the number of tiles between them), but now the map access is unlimited (the tape is still finite though).