title: Langton's ant ASCII art.

text:
# Question
Title: Langton's ant ASCII art.
Draw the path of Langton's ant.

### Description

> Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel in any of the four cardinal directions at each step it takes. The ant moves according to the rules below:
>
> * At a white square, turn 90° right, flip the color of the square, move forward one unit
> * At a black square, turn 90° left, flip the color of the square, move forward one unit

### Specifications

* Input: an integer N between 0 and 725 (inclusive).
* Output: a 17 by 17 grid representing the "path" of the ant as of step N.

### Rules

* The ant starts facing right (3 o' clock).
* The ant starts at the center of the grid.
* Use `_#@` for white squares, black squares and the ant respectively.
* The grid is initially completely white.
* You may make either a complete program or a function on an interpreted language.
* Input by stdin or argument.

### Examples

**Update:** case's N = 450 output was wrong.

N = 0

```
_________________
_________________
_________________
_________________
_________________
_________________
_________________
_________________
________@________
_________________
_________________
_________________
_________________
_________________
_________________
_________________
_________________

```

N = 1

```
_________________
_________________
_________________
_________________
_________________
_________________
_________________
_________________
________#________
________@________
_________________
_________________
_________________
_________________
_________________
_________________
_________________

```

N = 450

```
_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________

```

# Answer
## GolfScript - 67 chars

```
~17.'_'*n+*\153:|;{|/()[124^.2/6+:6.1&17*)\2&(*|+:|;]@++}*|/();'@'@

```

hallvabo's Python solution is the most similar to this, so I'll only describe the main differences.

The board is stored as a string instead of an array. This is so we can update a value on the board with less characters (as strings are always flat), and so getting it to the desired output format is easy.

The ant position is incremented by the formula `((d&1)*17+1)*((d&2)-1)` (i.e. `.1&17*)\2&(*`), where d is the direction. We use the variable `6` so we can skip initialization.
> 11 votes

# Answer
## Ruby 1.9, 104 characters

```
f=->z{l=[*[r=1]*17,2]*17;c=152;z.times{c+=r=(r*r>1?r/18:-r*18)*l[c]*=-1};l[c]=0;l.map{|a|putc"@_
#"[a]}}

```

Input via function argument.

* (146 -\> 142) Inlined `m`
* (142 -\> 140) Check for `r*r>1` instead of `r.abs>1`
* (142 -\> 128) Use `String#scan` to generate the output. Changed a `==` to `>`
* (128 -\> 125) Removed obsolete variable
* (125 -\> 122) Replace `String#tr` with a conditional
* (122 -\> 122) Now generates the same output as the updated examples
* (122 -\> 111) Use ints instead of chars when generating the ant's path.
* (111 -\> 109) Reorder some expressions to save parentheses
* (109 -\> 108) Code is now a function
* (108 -\> 104) Print every character individually
> 10 votes

# Answer
## Python, 123

```
n=input()
d=x=152
g=(17*[95]+[10])*17
while n:d+=g[x]/2;g[x]^=124;x+=(1,-18,-1,18)[d%4];n-=1
g[x]=64
print"%c"*306%tuple(g)

```

Just a slight reworking of my Python solution from http://golf.shinh.org/p.rb?Langtons+Ant.
> 6 votes

# Answer
## Windows PowerShell, ~~119~~ 118

```
for($p,$n,$g=144,+"$args"+,1*289;$n--){$d+=$g[$p]*=-1
$p+='B0@R'[$d%4]-65}$g[$p]=0
-join'@_#'[$g]-replace'.{17}',"$&
"

```
> 5 votes

# Answer
# GolfScript 96 94 89

My favourite hate language is back with another bunch of of semi-readable sorta-bytecode.

89 version, I finally managed to integrate @ into the output loop.

```
~289[0:c]*145:b;{.b>\b<)!..c++(4%:c[1 17-1-17]=b+:b;@++}@*{{(b(:b!.++'_#@@'1/=\}17*n\}17*

```

94 version:

```
~306[0:c]*152:b;{.b<\b>(!..c++(4%:c[1 18-1-18]=b+:b;\++}@*{{('_#'1/=\}17*(;n\}17*].b<\b>(;'@'\

```

Commented:

```
               #Initialization.
~                  #Parse input.
306[0:c]*          #Make array of 306 0s, set c to 0 in the middle of that operation.
152:b;             #Set b to 152, remove 152 from the stack.
                   #b is a value for the ant's position, c for its rotation.

               #Run the algorithm.
{                  #Start of block.
    .b<\b>(        #Split the array at index b into before, after and value at b.
    !..            #Not the value and make 2 copies of it.
    c++            #Add the 2 copies to c.
    (4%:c          #Subtract 1, modulus by 4 and save the result to c.
    [1 18-1-18]=   #Define an array and take element number c.
    b+:b;          #Add b to the value, save result to b, remove result from stack.
    \++            #Reform the array.
}@*                #Switch the input to the top of the stack and run the block input times.

               #Convert array of 1s and 0s to the correct characters.
{                  #Start of block.
    {              #Start of block.
        ('_#'1/=   #Take the first array element, convert it to either '_' or '#'.
        \          #Switch the array to the top of the stack.
    }17*           #Execute block 17 times.
    (;n\           #Discard the 18th element of the line, write a lineshift.
}17*               #Execute block 17 times.

               #Insert the @.
]                  #Put everything in an array.
.b<\b>(            #Split the array at index b into before, after and value at b.
;'@'\              #Ditch the value at b, write a @ and shift it into place.

```

Edit, I might as well make a big version, here goes 59\*59 and 10500 iterations:

```
~59:a.*[0:c]*1741:b;{.b>\b<)!..c++(4%:c[1 a-1-59]=b+:b;@++}@*{{(b(:b!.++'_#@@'1/=\}a*n\}a*

```

.

```
___________________________________________________________
___________________________________________________________
_________________________##__##____________________________
________________________#__@_###___________________________
_______________________###__#_#_#__________________________
_______________________#####_#__##_________________________
________________________#___##_##_#________________________
_________________________###___#__##_______________________
__________________________#___##_##_#______________________
___________________________###___#__##_____________________
____________________________#___##_##_#__##________________
_____________________________###___#__##__##_______________
______________________________#___##_##__##___#____________
________________________####___###___#___#__###____________
_______________________#____#___#___##_####___#____________
______________________###____#___#_#______#_##_#___________
______________________###____#_##_____#_##__#_##___________
_______________________#____#___##_#_#_____##______________
_______________________#_#______#_#####__#___#_____________
______________________#___#####__________##_######_________
______________________###__##__#_##_#_#_#___##_#_##________
____________________##__#_#######_#___#__###____##_#_______
___________________#__#__######_##___#__#_##___#___#_______
__________________#____#_#_##_#__######_#######___#________
__________________#_####_##_#_####____##__##_#_##_#________
___________________#____####___#__#_######_##____###_______
______________________#___#_##_#_###_#__##__##___###_______
_________________________#######____#__##_##_#_____#_______
_________________####__##_##__####_##_##_##__#_____#_______
________________#____#_#___###_##_###____#_####____#_______
_______________###_______###_#_#_#####____#_#______#_______
_______________#_#___###_####_##_#___##_###_##_____#_______
_____________________##_##__####____####_#_#_#_____#_______
________________#____#__##___###__###_____###______#_______
________________##___##_###_####__#______###___##__#_______
________________##_#_####_____#___#__#_##_###_##___#_______
_______________####_##___##_####__#_#__#__#__###___#_______
_______________#_##_###__#_#_##_#_#_____#_#_____#_#________
___________________#_#__#____##_##__#_#__###_##____________
___________________##_#____#__#####_#____#____#__#_#_______
__________________#_##_#__#____##_##_#__###______###_______
________________#_#___#__#__#__#__###___##__##____#________
_______________###_#_#####_######_###_#######_#_##_________
_______________#_#_#____#####___##__#####_#####____________
_________________#__##___#______#__#_##__###_###___________
______________####___#####_#########___#_#_________________
_________##____#__#_____###_#_#___#_###__###_______________
________#__#__####_##___###_##___###_##_____##_____________
_______###____#_##_#_#####___#____#__#__##_###_____________
_______#_#####_#_#___##__##_____#____#___#__#______________
___________######_####__##_#___#__##__#_#_##_______________
_________##______#_###_##__####___#___###__________________
__________#__#_#####__#___#_##___#__#__#___________________
__________##_###_#######_____#_____#_##____________________
_________#_#__##_##______#___##____#_______________________
________#__#_####________###__##__#________________________
________#_##_###____________##__##_________________________
_________##________________________________________________
__________##_______________________________________________

```
> 5 votes

# Answer
## PHP, ~~350~~ ~~309~~ ~~307~~ ~~312~~ ~~174~~ ~~161~~ ~~166~~ ~~159~~ ~~151~~ ~~149~~ ~~147~~ ~~144~~ 143

```
<?$p=144;while($i=$argv[1]--){$g[$p]=$a=2-$g[$p];$d+=--$a;$p+=(1-($d&2))*(1+16*($d&1));}while($i++<288)echo$i%17?$i!=$p?$g[$i]?"#": _:"@":"\n";

```

**Ungolfed**

```
$p = 144; // Set initial pointer

while($i = $argv[1]--){ // Ends at -1
    $g[$p] = $a = 2 - $g[$p]; // Either returns true (2) or false(0)

    $d += --$a; // Adds 1 (2-1) or removes 1 (0-1) from the direction

    $p += (1 - ($d & 2)) * (1 + 16 * ($d & 1));
}

while($i++ < 288)
    echo $i % 17? $i != $p? $g[$i]? "#" : @_ : "@" : "\n"; // Prints the correct character

```

**350 -\> 309:** Various compression techniques with the for() loops, also updated to show correct output.
**309 -\> 307:** Converted main for() loop to a while() loop.
**307 -\> 312:** Forgot to change it to use argv.
**312 -\> 174:** Recoded based on another answer.
**174 -\> 161:** No longer defaults entire array.
**161 -\> 166:** Argv wins again.
**166 -\> 159:** No need to redefine argv\[1\].
**159 -\> 151:** No longer defaults anything, PHP does it automatically.
**151 -\> 149:** Removed a set of parenthesis, order of operations removes the need.
**149 -\> 147:** Shortened the last for() loop, braces not needed.
**147 -\> 144:** Last for() loop is now a while() loop.
**144 -\> 143:** Used a temporary variable to save a character.
> 4 votes

# Answer
# Delphi, 217

```
var g,a:PByte;i,d,Word;begin g:=AllocMem(306);a:=g+153;Read(i);for n:=1to i do begin a^:=2-a^;d:=d-1+a^;a:=a+(1-2and d)*(1+17*(1and d))end;a^:=1;for n:=1to 306do if n mod 18=0then WriteLn else Write('_@#'[1+g[n]])end.

```

The indented & commented code reads like this:

```
var
  g,a:PByte;
  i,d,n:Int32;
begin
  g:=AllocMem(306); // g: The grid is initially completely white. (size=18*17=306)
  // Assume 0=d: Ant start 'd'irection faces right (=0, see below)
  a:=g+153; // a: Ant position starts at the center of the grid (=8*18+9=153)
  Read(i);
  for n:=1to i do
  begin
    // Flip the color of the square;
    a^:=2-a^;
    // Turn 90° right if at an '_' space, 90° left otherwise;
    d:=d-1+a^;
    // Move one unit forward;
    //   For this, determine the step size, using the two least significant bits of d.
    //   This gives the following relation :
    //     00 = 0 =  90° = right =   1
    //     01 = 1 = 180° = down  =  18
    //     10 = 2 = 270° = left  = - 1
    //     11 = 3 =   0° = up    = -18
    //   (d and 2) gives 0 or 2, translate that to 1 or -1
    //   (d and 1) gives 0 or 1, translate that to 1 or 18
    //   Multiply the two to get an offset 1, 18, -1 or -18 :
    a:=a+(1-2and d)*(1+17*(1and d))
  end;
  // Place the ant and print the grid :
  a^:=1; // 0 > '_', 1='@', 2 > '#'
  for i:=1to 306do
    if i mod 18=0then // we insert & abuse column 0 for newlines only (saves a begin+end pair)
      WriteLn
    else
      Write('_@#'[1+g[i]])
end.

```

Input:

```
450

```

Output :

```
_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________

```
> 4 votes

# Answer
## C, 166 162

Here a translation of my Delphi-approach to C, showing off how compact C can be. I borrowed the conditional newline trick from fR0DDY (thanks mate!) :

```
g[289]={0},a=144,d,i,N;main(){scanf("%d",&N);while(N--)g[a]=2-g[a],d+=g[a]-1,a+=(1-(d&2))*(1+d%2*16);for(g[a]=1;i<289;)printf("%s%c",i++%17?"":"\n","_@#"[g[i]]);}

```

The indented, commented version looks like this :

```
g[289]={0}, // g: The grid is initially completely white. (size=17*17=289)
a=144, // a: Ant position starts at the center of the grid (=8*17+8=144)
d, // Assume 0=d: Ant start 'd'irection faces right (=0, see below)
i,
N;
main(){
  scanf("%d",&N);
  while(N--)
    // Flip the color of the square:
    g[a]=2-g[a],
    // Turn 90° right if at an '_' space, 90° left otherwise :
    d+=g[a]-1,
    // Move one unit forward;
    //   For this, determine the step size, using the two least significant bits of d.
    //   This gives the following relation :
    //     00 = 0 =  90° = right =   1
    //     01 = 1 = 180° = down  =  17
    //     10 = 2 = 270° = left  = - 1
    //     11 = 3 =   0° = up    = -17
    //   (d and 2) gives 0 or 2, translate that to 1 or -1
    //   (d and 1) gives 0 or 1, translate that to 1 or 17
    //   Multiply the two to get an offset 1, 17, -1 or -17 :
    a+=(1-(d&2))*(1+d%2*16);
  // Place the ant and print the grid :
  for(g[a]=1;i<289;)
    printf("%s%c",i++%17?"":"\n","_@#"[g[i]]); // 0 > '_', 1='@', 2 > '#'
}

```
> 4 votes

# Answer
**C 195 Characters**

```
x=144,T,p=1,i,N[289]={0},a[]={-17,1,17,-1};c(t){p=(p+t+4)%4;x+=a[p];}main(){scanf("%d",&T);while(T--)N[x]=(N[x]+1)%2,c(N[x]?1:-1);for(;i<289;i++)printf("%s%c",i%17?"":"\n",i-x?N[i]?'#':'_':'@');}

```

http://www.ideone.com/Dw3xW

I get this for 725.

```
_________________
_________________
___________##____
____##______##___
___#___##__##_#__
__###____#_#__#__
__#_#_#__#_#_#___
______###____#__@
_______###__#__#_
_____#_#____#___#
___#_#_#_##____#_
__#__#_#_#_#_###_
__#_##_#_____####
___##_#____#_####
____###___####_#_
_______#__#__##__
________####_____

```
> 3 votes

# Answer
## sed, 481 chars

```
#n
1{s/.*/_________________/;h;H;H;H;G;G;G;G;s/^\(.\{152\}\)_/\1@/;s/$/;r/;ta;};x;:a;/;r/br;/;d/bd;/;l/bl;/;u/bu;:w;y/rdlu/dlur/;bz;:b;y/rdlu/urdl/;bz;:r;s/@\(.\{17\}\)_/#\1@/;tw;s/@\(.\{17\}\)#/#\1!/;tw;s/_\(.\{17\}\)!/@\1_/;tb;s/#\(.\{17\}\)!/!\1_/;tb;:d;s/_@/@#/;tw;s/#@/!#/;tw;s/!_/_@/;tb;s/!#/_!/;tb;:l;s/_\(.\{17\}\)@/@\1#/;tw;s/#\(.\{17\}\)@/!\1#/;tw;s/!\(.\{17\}\)_/_\1@/;tb;s/!\(.\{17\}\)#/_\1!/;tb;:u;s/@_/#@/;tw;s/@#/#!/;tw;s/_!/@_/;tb;s/#!/!_/;tb;:z;h;${s/!/@/;s/;.//p}

```

May be reduced to 478 chars by removing first line and running with `-n`

Requires N lines for input, eg. when run as

```
seq 450 | sed -f ant.sed

```

outputs:

```
_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________

```
> 3 votes

# Answer
# Perl, 110 characters

```
$p=144;$p+=(1,-17,-1,17)[($d+=($f[$p]^=2)+1)%4]for 1..<>;$f[$p]=1;print$_%17?'':$/,qw(_ @ #)[$f[$_]]for 0..288

```

Number is read from the first line of STDIN. Rest of input is ignored.

### Slightly more readable:

```
$p=144;
$p += (1,-17,-1,17)[($d+=($f[$p]^=2)+1) % 4] for 1..<>;
$f[$p]=1;
print $_%17 ? '' : $/, qw(_ @ #)[$f[$_]] for 0..288

```

### Edits

* **(112 → 111)** No need to update `$d` with the modulo-4 value.
* **(111 → 110)** Can now inline the `$d` increment

### Addendum (109 characters)

We can have it one character shorter if you’re happy to have the special case of `N=0` fail (it doesn’t output the `@` character for the ant). All other inputs work correctly:

```
$p+=(1,-17,-1,17)[($d+=($f{$p+0}^=2)+1)%4]for 1..<>;$f{$p}=1;print$_%17-9?'':$/,qw(_ @ #)[$f{$_}]for-144..144

```

The differences are that we now use `%f` instead of `@f` so we can use negative indices, and we iterate from `-144..144` instead of `0..288`. It saves having to initialise `$p`.
> 3 votes

# Answer
# \>\<\>, 122 bytes

At the risk of a little thread necromancy, I thought writing an answer in \>\<\> would be an interesting challenge...

```
1&f8r\
1-:?!\r:@@:@$:@@:@g:2*1+&+4%:&}1$-@p{:3$-5gaa*-$@+@5gaa*-+r
2}p70\~
a7+=?\:@@:@g4+5go$1+:
o053.>~1+:64*=?;a
dedc_#@

```

This program expects the number of steps to compute to be present on the stack before execution.
> 2 votes

# Answer
# Mathematica, 94 chars

```
a@_=d=1;a@Nest[#+(d*=(a@#*=-1)I)&,9-9I,Input[]]=0;Grid@Array["@"[_,"#"][[a[#2-# I]]]&,17{1,1}]

```
> 1 votes

# Answer
# APL(Dyalog Unicode), 108 bytes SBCS

```
{'@'@(⊂9 11○⊃⍵)⊢3⊃⍵}{p s g←⍵⋄(p+s)(s←s×0j1×¯1 1['#_'⍳g[x]])(('_#'~g[x])@(x←⊂9 11○p)⊢g)}⍣⎕⊢9J9 0J1(17 17⍴'_')

```

Try it on APLgolf!, Alternate version

A tradfn submission which takes a single number as input.
> 1 votes

# Answer
# brainfuck, ~~5040~~ ~~4562~~ 4390 bytes

```
,>,>,>++++++[->++++++++<]>[<<-<-<->>>>-]>++++++++>++++++++<<<<[>+>+<<-]>[<+>-]<<[>>+>+<<<-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>[<<<+>>>-]>[<+>[-]]<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[-<<<<<[>>>>>+>-<<<<<<-]>>>>>-[<<<<<+>>>>>-]+>[<->[-]]<[-<<<<<[-]+++++++++<[>>>>>>+>-<<<<<<<-]>>>>>>-[<<<<<<+>>>>>>-]+>[<->[-]]<[<<<<<<++++++++++<->>>>>>>-]]<<<<[>>>>+<<<<-]<[>+>>>>>-<<<<<<-]>[<+>-]<<[>>+>>>>>-<<<<<<<-]>>[<<+>>-]<<<[>>>+>>>>>-<<<<<<<<-]>>>[<<<+>>>-]>>>>[<<<<+>>>>-]+>[<->[-]]<[<<<<->>>>-]<[>+++++++++++++++++>+<<-]>>[<<+>>-]<<<[>>+>+<<<-]>>>[<<<+>>>-]<[>>[-]+<[>+<-]<-[>+<-]>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>[<<+>>-]<[<[<+>-]>-[<+>-]<]+<[>-<<<<->>>-]>[<<<<+>[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<<<<[>>>+++++++++++++++++>+<<<<-]>>>>[<<<<+>>>>-]<[>>>[-]<[>+<-]<+[>+<-]<-[>+<-]>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>[-[<+>-]<]<<-]<+<<<[>>>>+<<<<-]>>>>>++++<[->-[>+>>]>[+[<+>-]>+>>]<<<<<]>>[<<+<<<<+>>>>>>-]<<[-[-[<<->->-]<[<<->>-]>]<[<+>-]>]<[<<+>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<]>+[[-]>+[[-]<<[>>+>-<<<-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>[<<<+>>>-]+>[<->[-]]<<[>>+>-<<<-]>>[<<+>>-]<<<<<[>>>>>+>+<<<<<<-]>>>>>[<<<<<+>>>>>-]+>[<->[-]]<<[->[>+<-]<]>>[<<+>>-]<[-]+<[->+++++++[->++++++++<]>.<<]>[-<<<[>>>+>+++++++++++++++++<<<<-]>>>[<<<+>>>-]<<[>>+>+<<<-]>>[<<+>>-]>[>+[>+<-]<-[>+<-]>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>[<<+>>-]<[<[<+>-]>-[<+>-]<]+<[---[>--<+++++++]>--.[-]<]>[--[>++<-----]>-------.[-]<]<<]<<[>+>+<<-]>>+[<<+>>-]<----------------]++++++++++.[-]<[-]<[>+>+<<-]>>+[<<+>>-]<----------------]

```

Try it online!

Input is zero padded. So for 5 iterations you type `005`.
> 0 votes

---
Tags: code-golf, ascii-art
---


title: Filetype Color Codes

text:
# Question
Title: Filetype Color Codes
On Unix-like systems, the `ls` command lists files. GNU's version of `ls` also colors them according to their properties and the environment variable `LS_COLORS`. The main file property that `ls` bases its colors on is the file's **mode**. In this challenge, you will determine what keys from LS\_COLORS `ls` should look for a given mode.

## File modes

A file's mode determines what type of a file it is (is it a normal file? a socket? a pipe? a directory?) and what permissions it has (can the owner execute it? can everyone write to it?).

The mode is given by a 16-bit unsigned integer. The highest 4 bits determine the file's type, the next 3 bits determine certain special attributes, and the remaining 9 bits determine user, group, and world permissions (3 bits each).

The grouping-up by 3s makes it very common write these permissions in octal:

```
      type  special  permissions  |      type  sp  perms
      ----  -------  -----------  |       --   --  -----
(bin) 1111    111    111 111 111  | (oct) 17    7  7 7 7

```

The top 4 bits will take on one of these values. Any other values can produce undefined behavior:

```
Binary       Octal    File type
---------    -----    ----------------
0b1100...    014...   socket
0b1010...    012...   symbolic link
0b1000...    010...   regular file
0b0110...    006...   block device
0b0100...    004...   directory
0b0010...    002...   character device
0b0001...    001...   FIFO (named pipe)

```

The remaining 4 octets can have any value. each bit is a flag which can be set independently from the others:

```
????-------------  Filetype, see above
----1------------  SUID: Execute this file with the UID set to its owner
-----1-----------  SGID: Execute this file with the GID set to its group
------1----------  Sticky: Users with write permissions to this dir cannot move or delete files within owned by others
-------1---------  User read:  The owner of the file can read this
--------1--------  User write: The owner of the file can write to this
---------1-------  User exec:  The owner of the file can execute this
-----------111---  Group r/w/x: The group of this file can read/write/execute
--------------111  Other r/w/x: All users can read/write/execute

```

## LS\_COLORS

GNU's `ls` uses the environment variable LS\_COLORS to add color to the files it lists. The variable LS\_COLORS is a colon-delimited list of `key=value` rules. Some of those keys are for file names (e.g.: `*.tar=01;31`), but we care about the file type keys.

```
ln      Symbolic link.
pi      Named pipe
bd      Block device
cd      Character device
or      Symbolic link pointing to a non-existent file
so      Socket
tw      Directory that is sticky and other-writable (+t,o+w)
ow      Directory that is other-writable (o+w) and not sticky
st      Directory with the sticky bit set (+t) and not other-writable
di      Directory
su      Normal file that is setuid (u+s)
sg      Normal file that is setgid (g+s)
ex      Executable normal file (i.e. has any 'x' bit set in permissions)
fi      Normal file

```

Now when `ls` finds a match in the above list, it only applies that color *if that key exists* in LS\_COLORS. If a directory is sticky and other-writeable, but no `tw` key is in LS\_COLORS, it will fall back to `ow`, then fall back to `st`, then fall back to `di`. The list above is ordered to give the same result as `ls`.

## Challenge

Take as an integer input any valid file mode, and output the fallback list of two-character codes.

**Input:** A file mode with a valid file type, in any convenient integer format that is at least 16 bits.

**Output:** The corresponding **ordered** list of two-character keys for a file with that mode, in fallback order. Since all codes are two characters, the concatenated string (e.g.: `"twowstdi"`) is also acceptable, as it is still unambiguous. Additionally, printing the codes in reverse order (`di st ow tw`) is also fine, as long as it is consistent for all inputs.

Example:

* Input: `17389` (in octal: `0041755`)
* Output: `["st", "di"]` (the sticky bit `0001000` is set, and it is an directory `0040000`.)

Test cases (these are in octal, and a symbolic equivalent for your convenience):

```
 Input    Symbolic      Output     | Note:
-------  ----------  ------------- | -----
0140000  s---------   so           | socket
0147777  srwsrwsrwt   so           | suid/sgid/sticky/other-writeable does not apply
0120000  l---------   ln           | symbolic link (you MAY choose to output "or" instead)
0127777  lrwsrwsrwt   ln           |
0060000  b---------   bd           | block device
0067777  brwsrwsrwt   bd           |
0020000  c---------   cd           | character device
0027777  crwsrwsrwt   cd           |
0010000  p---------   pi           | pipe
0017777  prwsrwsrwt   pi           |

0040755  drwxr-xr-x   di           | directory
0041755  drwxrwxr-t   st di        | sticky bit set
0040002  d-------w-   ow di        | other-writable
0041777  drwxrwxrwt   tw ow st di  | sticky + other-writeable
0046000  d--S--S---   di           | suid/sgid only apply to normal files

0100000  ----------   fi           | normal file
0100000  ---------T   fi           | sticky bit only applies to directories
0100100  ---x------   ex fi        | executable file
0100010  ------x---   ex fi        |
0100001  ---------x   ex fi        |
0104000  ---S------   su fi        | suid
0106777  -rwsrwsrwx   su sg ex fi  | suid has priority over sgid and executable
0102000  ------S---   sg fi        | sgid
0102777  -rwxrwsrwx   sg ex fi     | sgid has priority over executable

0110000  ?---------  <undefined>   | Unknown filetype, any output is valid

```

Standard loopholes are forbidden. This is , so shorter answers are best.

---

Similar Challenges: File Permissions, Do I have permission?

# Answer
> 3 votes
# JavaScript (Node.js), 141 bytes

```
c=>(E='',x=c>>8,y=c>>13,y-2?y-4?E:(x&8?'su':E)+(x&4?'sg':E)+(c&73?'ex':E):(x&c&2?'tw':E)+(c&2?'ow':E)+(x&2?'st':E))+'pcdbfls'[y]+'ididino'[y]

```

Try it online!

*-7 bytes thanks to @Arnauld!*

Takes the file mode as an integer and returns the colour string without spaces.

## Commented

```
// Saving these values to single char variables allows the logic below to be shorter
c=>(E='',x=c>>8,y=c>>13,
  y-2?
    y-4?
      // Other type colors (none)
      E
    // File colors
    :(x&8?'su':E)+(x&4?'sg':E)+(c&73?'ex':E)
  // Directory colors
  :(x&c&2?'tw':E)+(c&2?'ow':E)+(x&2?'st':E)
// The top three bits uniquely identify the mode
)+'pcdbfls'[y]+'ididino'[y]

```

# Answer
> 3 votes
# Charcoal, 87 bytes

```
≔◧⍘Ｎ²¦¹⁷θ≡﹪Σ…θ⁴¦⁸¦⁶so⁵ln⁴ΦfiexsgsuＩ§⟦1⌈✂θχφ³§θ⁶§θ⁵⟧⊘κ³bd²Φdistowtw⁼κ＆κＩ⁺⁺§θ¹⁵§θ⁷1¹cd¦pi

```

Try it online! Link is to verbose version of code. Takes input in decimal and outputs without separators and in reverse order. Explanation:

```
≔◧⍘Ｎ²¦¹⁷θ

```

Convert the input to base 2 and left-pad it to 17 bits with spaces. This ensures that it starts with a space, guaranteeing consistent behaviour of the `Sum` operator; other choices would have required extra bytes to arrange zero padding.

```
≡﹪Σ…θ⁴¦⁸

```

Take the first four bits, convert to decimal, and reduce modulo 8. (The alternatives was either to spend more bytes padding with zeros to allow me to convert from base 2 or to spend more bytes taking a copy of the input and integer dividing it by 4096.)

```
⁶so

```

It's a socket.

```
⁵ln

```

It's a symbolic link.

```
⁴ΦfiexsgsuＩ§⟦1⌈✂θχφ³§θ⁶§θ⁵⟧⊘κ

```

It's a file. Filter on the file subtypes according to whether (one of) the relevant bits are set.

```
³bd

```

It's a block device.

```
²Φdistowtw⁼κ＆κＩ⁺⁺§θ¹⁵§θ⁷1

```

It's a directory. Filter on the subtypes according to the combination of set bits. The base 10 conversion is safe here as the numbers 10, 11, 100, 101, 110 and 111 all end in the same three digits in both decimal and binary.

```
¹cd

```

It's a character device.

```
pi

```

It had better be a named pipe.

---
Tags: code-golf, binary, file-system
---


# Question
Title: Tips for restricted source in Powershell
Adapted from Tips for restricted source in Python

---

Just like , pushes one to exploit quirks and hidden features of the Powershell language. Now, We already have a place to collect all these for , those for remain transmitted by word of mouth or hidden deep within the Powershell documentation.

Let's collaborate on this thread to gather the tips for in Powershell!

Please only include 1 tip per answer.

---

## What makes a good tip here?

There are a couple of criteria I think a good tip should have:

1. It should be (somewhat) non obvious.

Similar to the tips it should be something that someone who has golfed in python a bit and read the tips page would not immediately think of. For example "Replace `a + b` with `a+b` to avoid using spaces", is obvious to any golfer since it is already a way to make your code shorter and thus not a good tip.
2. It should not be too specific.

Since there are many different types of source restrictions, answers here should be at least somewhat applicable to multiple source restrictions, or one common source restriction. For example tips of the form **How to X without using character(s) Y** are generally useful since banned characters is a common source restriction. The thing your tip helps to do should also be somewhat general. For example tips of the form **How to create numbers with X restriction** are useful since many programs utilize numbers regardless of the challenge. Tips of the form **How to implement Shor's algorithm with X restriction** are basically just answers to a challenge you just invented and not very helpful to people solving other challenges.

# Answer
# Alternatives To Single And Double Quotes

```
{A}  #Normal Curly Braces; This makes a scriptblock, but the ToString prints the contents
‘B‘  # Left Single Quotation Mark              0x2018
’C’  # Right Single Quotation Mark             0x2019
‚D‚  # Single Low-9 Quotation Mark             0x201a
‛E‛  # Single High-Reversed-9 Quotation Mark   0x201b
“F“  # Left Double Quotation Mark              0x201c
”G”  # Right Double Quotation Mark             0x201d
„H„  # Double Low Quotation Mark               0x201E

```

```
PS C:\> {A}
A
PS C:\> ‘B‘
B
PS C:\> ’C’
C
PS C:\> ‚D‚
D
PS C:\> ‛E‛
E
PS C:\> “F“
F
PS C:\> ”G”
G
PS C:\> „H„
H

```

Yes, these work! But What's better? The quotes single quotes and double quotes act as their respective normal quotes, (') and ("), and {} behave like single quotes ('). Thus:

```
$x="A Variable"
‘$x‘
’$x’
‚$x‚
‛$x‛
“$x“
”$x”
„$x„
{$x}

```

outputs:

```
$x           # ‘$x‘
$x           # ’$x’
$x           # ‚$x‚
$x           # ‛$x‛
A Variable   # “$x“
A Variable   # ”$x”
A Variable   # „$x„
$x           # {$x}

```

As a final useful bit; you don't even have to match the starting and ending quotes, so long as they are of the same type (single/double). Meaning these:

```
‘$x‛
‚$x'
”$x“
„$x"

```

Are all perfectly valid, and output like so:

```
$x           # ‘$x‛
$x           # ‚$x'
A Variable   # ”$x“
A Variable   # „$x"

```

# Alternative Dashes and Uncommon Whitespace

In addition to the additional quotes characters above, PowerShell recognizes some special dashes as equivalent to the hyphen (-):

```
5–4  # EN DASH          0x2013   [–]
3—2  # EM DASH          0x2014   [—]
1―1  # HORIZONTAL BAR   0x2015   [―]

```

Powershell also recognizes two other uncommon whitespace characters:

```
NoBreakSpace   0x00A0
NextLine       0x0085

```

These were found by @ZaelinGoodman's experiment here

If anything changes, or if you want to see the specifics of how these work, you can find the source code for this handling in the PowerShell Github

I made this community wiki, so this list can be freely updated.
> 8 votes

# Answer
# Using variables if $ is forbidden

Use the Get/Set-Variable:

```
Set-Variable myVar 5
Get-Variable myVar

```

And shorter with their aliases:

```
sv myVar 6
gv myVar

```

as `Get-Variable` returns a `PSVariable` object, use the `-v` for `ValueOnly` to get only the value

```
gv myVar -v

```

Note that it works for already defined variables such as `$args` in functions.
> 3 votes

# Answer
# Printing numbers in Restricted source

You can use Boolean or hexadecimal numbers or print numbers in other way, in restricted source.

---

When performing arithmetic operations on Booleans, Powershell treats them as if they are the numbers 1 and 0. Basically, if you cast any undefended variable to `[int]`, it will be considered as `0`.

An example is:

```
PS C:\Users\Administrator> [int]$true
1
PS C:\Users\Administrator> [int]$false
0
PS C:\Users\Administrator> [int]$x #This variable is not defined
0

```

A shorter way is to add/subtract digits to the boolean/non-existent variable:

```
PS C:\Users\Administrator> $true+0
1
PS C:\Users\Administrator> $false+1
1
PS C:\Users\Administrator> $true+$true
2
PS C:\Users\Administrator> ($true+$true)*($true+$true)
4

```

Or just `+$true`, thanks to @mazzy

This especially comes useful if (most) digits are not allowed.

---

Hexadecimal numbers come up useful too, like if you aren't allowed to use `1-9` but have to print `100`, then use `0xa*0xa` (because `0xa=10`)

```
PS C:\Users\Administrator> 0xa
10
PS C:\Users\Administrator> 0xa*0xa
100

```

---

Another tip is you can calculate a string's length (length of `18` `x`s):

```
PS C:\Users\Administrator> 'xxxxxxxxxxxxxxxxxx'.length
18
PS C:\Users\Administrator> 'xxxxxxxxxxxxxxxxxx'|% le*
18

```

use "$args" to cast the arguments to one value. use +"$args" if you need only one value, thanks to @mazzy
> 1 votes

---
Tags: restricted-source, tips, powershell
---


# Question
Title: First sequence with no square differences
Consider the sequence \\$(a\_n)\\$ defined in the following way.

* \\$a\_0=0\\$
* For all \\$n=1, 2, 3, \dots\\$, define \\$a\_n\\$ to be the smallest positive integer such that \\$a\_n-a\_i\\$ is not a square number, for any \\$0\leq i\<n\\$

In other words, this is the lexicographically first sequence where no two terms differ by a square. It is proven that this sequence is infinite, and it is A030193 in the OEIS. The sequence begins

`0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, 52, 57, 62, 65, 67, 72, 85, 95, 109, 119, 124, 127, 130, 132, 137, 142, 147, 150, 170, 177, 180, 182, 187, 192, 197, 204, 210, 215, 238, 243, 249, 255, 257, 260, 262, 267,...`

## Challenge

The challenge is to write a program or function which does one of these:

* Takes a nonnegative integer `n` and returns or prints the n-th term of this sequence. Either 1-indexed or 0-indexed is acceptable.
* Takes a positive integer `n` and returns or prints the first n terms of this sequence
* Takes no input and returns or prints all terms of the sequence with an infinite loop or infinite list

Any reasonable form of input and output is allowed.

## Example (0-indexed)

```
Input -> Output
0     -> 0
10    -> 34
40    -> 215

```

## Rules

* Standard loopholes forbidden.
* Code golf: shortest program in bytes for each language wins.

# Answer
# Ruby, ~~72~~ ~~62~~ ~~57~~ ~~50~~ 47 bytes

```
0.step{|x|$*<<p(x)if$*.all?{|i|(x-i)**0.5%1>0}}

```

Try it online!

Prints all terms of the sequence indefinitely.

7 bytes saved by Dingus and further 3 by Sisyphus.

## Ruby 2.7+, 45 bytes

```
0.step{|x|$*<<p(x)if$*.all?{(x-_1)**0.5%1>0}}

```
> 9 votes

# Answer
# Python 3, 67 bytes

Takes no input and prints all terms of the sequence with an infinite loop.

```
n,*a=0,
while 1:a+=n*(all((n-i)**.5%1for i in a)>0!=print(n)),;n+=1

```

Try it online!
> 9 votes

# Answer
# Python 3, ~~101~~ 93 bytes

```
f=lambda n,l=[],a=0:n and(any((a-b)**.5%1==0for b in l)and f(n,l,a+1)or f(n-1,l+[a],a+1))or l

```

Try it online!

Inputs a positive integer \\$n\\$ and returns the first \\$n\\$ terms of \\$A030193\\$.
> 8 votes

# Answer
# Python 3, ~~102~~ ~~92~~ ~~88~~ 84 bytes

```
f=lambda n,a=[],x=0:n and f(*[n,n-1,a,a+[x]][all((x-k)**.5%1for k in a)::2],x+1)or a

```

Try it online!

*-4 bytes thanks to movatica*
> 8 votes

# Answer
# Husk, 17 bytes

```
¡λVoΛoS≠⌊√M≠⁰N);0

```

Try it online!

Returns an infinite list. The header is used to take 10 elements from it so the result can be displayed.

## Explanation

```
¡λVoΛoS≠⌊√M≠⁰N);0
               ;0 start with [0]
¡                 iterate on this array, appending results:
 λ            )   lambda function (argument → ⁰)
  Vo         N    first natural number where
          M≠⁰     differences with elements so far
    Λo            are all
      S≠⌊√        not square?

```
> 7 votes

# Answer
# Retina 0.8.2, 46 bytes

```
.+
$*¶
+1m`^(_*)¶(_+¶)*((\3__|^_))*\1$
$&_
%`_

```

Try it online! Outputs the 0ᵗʰ to nᵗʰ terms. Explanation: The program first matches the 0ᵗʰ and nᵗʰ terms, which initially differ by zero, and increments the nᵗʰ term. On the next pass through the loop, it discovers that the nᵗʰ term differs from the first entry by one, and so increments it again. The difference is now two, so this pair of terms no longer matches. Instead, further passes start incrementing previous terms, until finally the 1ˢᵗ term has been incremented to two. At this point, the 0ᵗʰ term cannot be paired with any other term, so now the 1ˢᵗ term is paired with the nᵗʰ term, as they are both two. The nᵗʰ term thus gets incremented twice to four. At this point however the 0ᵗʰ and nᵗʰ terms can be matched again, so the nᵗʰ term gets incremented to five. Now further passes can start incrementing previous terms, until finally the 2ⁿᵈ term has been incremented to five. Having for now exhausted all matches of the 0ᵗʰ and 1ˢᵗ terms, the 2ⁿᵈ term is now paired with the nᵗʰ term. As before, it gets incremented twice, then further passes increment previous terms, until finally the 3ʳᵈ term has been incremented to seven. Eventually all of the terms get incremented until no two terms differ by a square. (It is however important that only one term gets incremented on each pass, otherwise some terms may get incremented prematurely, being the sum of a square of a term whose value is itself still the sum of a square of a term.)

```
.+
$*¶

```

Generate an array of n+1 terms, all of which start off at zero.

```
+`

```

Repeat while two terms have a square difference...

```
1`

```

... update one pair of terms...

```
m`^(_*)¶(_+¶)*((\3__|^_))*\1$

```

... match a term, any number of terms, then an term which is a square number plus the initially matched term...

```
$&_

```

... and add one to that term.

```
%`_

```

Convert each term to decimal.

At a cost of 2 bytes, using a lookbehind allows all of the terms to be incremented simultaneously, dramatically improving performance:

```
.+
$*¶
+m`$(?<=^\2(¶_+)*¶(_*)((\3__|_$))*)
_
%`_

```

Try it online!
> 5 votes

# Answer
# JavaScript (ES7), 66 bytes

Returns the **n**-th term, 0-indexed.

```
n=>n&&(k=0,g=a=>a[n]||g(++k*a.every(v=>(k-v)**.5%1)?[...a,k]:a))``

```

Try it online!
> 5 votes

# Answer
# , ~~85~~ ~~76~~ ~~67~~ 63 bytes

*Edit: -9 bytes thanks to Giuseppe, and then -4 bytes thanks to Kirill L.*

```
s=0;repeat{s=c(F,s);show(+F);while(any((0:F)^2%in%(F-s)))F=F+1}

```

Try it online!

Outputs the infinite sequence.
> 4 votes

# Answer
# Jelly, 14 bytes

```
ŻJ²p⁸§Ṭ¬TŻḣðƬṪ

```

A monadic Link accepting a positive integer \\$N\\$ that yields a list of the first \\$N\\$ terms.

**Try it online!**

### How?

Iterates towards the greedy solution. It would be easier to follow as `0ð...` but we can start the `Ƭ`-loop with \\$N\\$ rather than \\$0\\$ saving those two bytes.

```
ŻJ²p⁸§Ṭ¬TŻḣðƬṪ - Link: N
            Ƭ  - start with a left argument of N, apply repeatedly until no change, collecting
                 the left arguments in a list:
           ð   -   dyadic chain - f(L=current left argument, N)
Ż              -     when L is an integer [0..L]  (first pass only)
                     when L is a list [0]+L       (all other passes)
 J             -     range of length -> [1..n+1]  (all passes due to ḣ, below)
  ²            -     square these -> [1,4,9,...,(n+1)²]
    ⁸          -     L (on the first pass L is N and this is implicitly cast to [1..N])
   p           -     (squares) Cartesian product (L)
     §         -     sums -> numbers which are any of L plus any of these squares
      Ṭ        -     untruth -> a binary list with ones at those indices
       ¬       -     logical NOT
        T      -     truth -> a list of the indices of the truthy entries
                              i.e. a bunch of numbers that aren't in the result of the sums, §
         Ż     -     prepend a zero
          ḣ    -     head to length (N)
             Ṫ - tail

```

As an example of the `Ƭ`-loop consider \\$N=3\\$:

```
>>> L = 3
ŻJ²           -> [1, 4, 9, 16]
ŻJ²p⁸         -> [[1, 1], [1, 2], [1, 3], [4, 1], [4, 2], [4, 3], [9, 1], [9, 2], [9, 3], [16, 1], [16, 2], [16, 3]]
ŻJ²p⁸§        -> [2, 3, 4, 5, 6, 7, 10, 11, 12, 17, 18, 19]
ŻJ²p⁸§Ṭ¬TŻ    -> [0, 1, 8, 9, 13, 14, 15, 16]
ŻJ²p⁸§Ṭ¬TŻḣ   -> [0, 1, 8]
>>> L = [0, 1, 8]
ŻJ²           -> [1, 4, 9, 16]
ŻJ²p⁸         -> [[1, 0], [1, 1], [1, 8], [4, 0], [4, 1], [4, 8], [9, 0], [9, 1], [9, 8], [16, 0], [16, 1], [16, 8]]
ŻJ²p⁸§        -> [1, 2, 9, 4, 5, 12, 9, 10, 17, 16, 17, 24]
ŻJ²p⁸§Ṭ¬TŻ    -> [0, 3, 6, 7, 8, 11, 13, 14, 15, 18, 19, 20, 21, 22, 23]
ŻJ²p⁸§Ṭ¬TŻḣ   -> [0, 3, 6]
>>> L = [0, 3, 6]
ŻJ²           -> [1, 4, 9, 16]
ŻJ²p⁸         -> [[1, 0], [1, 3], [1, 6], [4, 0], [4, 3], [4, 6], [9, 0], [9, 3], [9, 6], [16, 0], [16, 3], [16, 6]]
ŻJ²p⁸§        -> [1, 4, 7, 4, 7, 10, 9, 12, 15, 16, 19, 22]
ŻJ²p⁸§Ṭ¬TŻ    -> [0, 2, 3, 5, 6, 8, 11, 13, 14, 17, 18, 20, 21]
ŻJ²p⁸§Ṭ¬TŻḣ   -> [0, 2, 3]
>>> L = [0, 2, 3]
ŻJ²           -> [1, 4, 9, 16]
ŻJ²p⁸         -> [[1, 0], [1, 2], [1, 3], [4, 0], [4, 2], [4, 3], [9, 0], [9, 2], [9, 3], [16, 0], [16, 2], [16, 3]]
ŻJ²p⁸§        -> [1, 3, 4, 4, 6, 7, 9, 11, 12, 16, 18, 19]
ŻJ²p⁸§Ṭ¬TŻ    -> [0, 2, 5, 8, 10, 13, 14, 15, 17]
ŻJ²p⁸§Ṭ¬TŻḣ   -> [0, 2, 5]
>>> L = [0, 2, 5]
ŻJ²           -> [1, 4, 9, 16]
ŻJ²p⁸         -> [[1, 0], [1, 2], [1, 5], [4, 0], [4, 2], [4, 5], [9, 0], [9, 2], [9, 5], [16, 0], [16, 2], [16, 5]]
ŻJ²p⁸§        -> [1, 3, 6, 4, 6, 9, 9, 11, 14, 16, 18, 21]
ŻJ²p⁸§Ṭ¬TŻ    -> [0, 2, 5, 7, 8, 10, 12, 13, 15, 17, 19, 20]
ŻJ²p⁸§Ṭ¬TŻḣ   -> [0, 2, 5]
>>> [0, 2, 5]
>>> seen previously, so stop the Ƭ-loop and yield:
    [3, [0, 1, 8], [0, 3, 6], [0, 2, 3], [0, 2, 5]]
Ṫ             -> [0, 2, 5]

```
> 4 votes

# Answer
# Haskell, 56 bytes

```
n!l|or[elem(n-y*y)l|y<-[0..n]]=(n+1)!l|m<-n:l=n:n!m
0![]

```

Try it online!

`0![]` is an infinite list of the results.

This draws some inspiration from AZTECCO's answer.
> 4 votes

# Answer
# K (ngn/k), ~~31~~ 29 bytes

```
{*|x{x,{y+|/~1!%y-x}[x]/0}/0}

```

Try it online!

Returns the n-th item of the series (0-indexed). If it's acceptable to return the first `n+1` terms of the sequence, the leading `*|` can be dropped to save two bytes.

* `{*|...}` return only the last item of the generated sequence
    + `x{...}/0` run a fold-do loop, for `x` iterations seeded with `0`
        - `{...}[x]/0` run a fold-converge loop, fixing `x` (the generated sequence so far), seeded with `0`. this will stop when the next value in the sequence has been identified
            * `%y-x` take the square root of the differences between the current loop value and each value in the generated sequence so far
            * `~1!` check if any difference is a square number (i.e. if it has a remainder of zero after being mod'd by 1)
            * `y+|/` increment the current loop value if it is not the next term in the sequence
    + `{x,...}` append the next value in the sequence
> 4 votes

# Answer
# Wolfram Language (Mathematica), 55 bytes

returns the first n terms

```
Nest[#~Join~{While[Or@@AtomQ/@√(++k-#)];k}&,{k=0},#]&

```

Try it online!

-11 bytes thanks to @att
> 3 votes

# Answer
# PowerShell, 76 75 69 64 bytes

Takes no input, outputs the infinite series (up to the maximum for a 64-bit signed integer)

```
for(){($a+=,+$n*!($a|?{!([Math]::Sqrt($n-$_)%1)}).Count)-eq$n++}

```

Try it online!
> 3 votes

# Answer
# Japt, ~~27 23~~ 22 bytes

```
@A{ZmaA fAõ² l}fXÄ}h0ô

```

Try it online!

Returns the first `n` numbers in the sequence. If you replace `h` with `g` it instead returns the `n`th number in the sequence (0-indexed).

Improvements:

* Used "difference is in list of squares" instead of "square root of difference is an integer" to save 4 bytes, inspired by Jonathan Allan's Jelly answer
* Used  to initialize the array as suggested by AZTECCO

Explanation:

```
@A{ZmaA fAõ² l}fXÄ}h0ô
                    0ô    # Starting with [0]
@                 }h      # Add elements to the array until the length is n:
 A{           }fXÄ        #  Find the next integer A that returns 0:
   Zm                     #   For each element already in the array:
     aA                   #    Get the absolute difference between it and A
        f                 #   Remove any elements that are also in:
         Aõ²              #    All squares up to A^2
             l            #   Count how many elements are left

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 51 bytes

```
g@n_:=g@m_/;AtomQ@√(m-n)=Print@n
i=0
g@i++~Do~∞

```

Try it online!

Outputs the list indefinitely.
> 3 votes

# Answer
# JavaScript, 66 bytes

```
_=>{a=[];for(i=0;;i++)a.every(x=>(i-x)**.5%1)&&a.push(i);return a}

```

Adds the terms of the sequence to an array with an infinite loop.

Try it online!

# JavaScript (V8), ~~77~~ 76 bytes

```
n=>{a=[];for(i=0;a.length<n;i++)a.every(x=>(i-x)**.5%1)&&a.push(i);print(a)}

```

Prints the first `n` terms of the sequence.

Try it online!

## Explanation

```
n=>{
   a=[];//array of terms in the sequence
   for(i=0;a.length<n;i++) //loop until array length is n
     a.every(x=>(i-x)**.5%1)
      //check if square root of delta with each previous number in sequence is not an integer
       &&a.push(i);//then add to array
   print(a)//output array (return works too)
}

```
> 2 votes

# Answer
# Haskell, ~~95~~ 89 bytes

```
n!l|and[y*y/=n-x|x<-l,y<-[0..n-x]]=n:l|m<-n+1=m!l
f n=iterate(\l@(h:t)->(h+1)!l)[0]!!n!!0

```

Try it online!

* saved 6 thanks to @Wheat Wizard !
* uses this tip Don't waste the "otherwise" guard
* returns nth term 0-indexed
* f(n) - iterates (!) n times, starting with \[0\] and prepends next term. then takes the element in front because list is reversed.
* (!) tries next number at beginning of list: if it satisfy condition returns it prepended to list else try the next
> 2 votes

# Answer
# , 35 bytes

```
0&(],]>:@]^:(1 e.(=<.)@%:@-)^:_[)0:

```

Try it online!

Given `n`, returns the first `n+1` terms.
> 2 votes

# Answer
# Jelly, ~~15~~ 14 bytes

```
;0_Æ²Ẹ¬ʋ1#$$¡Ṗ

```

Try it online!

Prints the first n terms.

If we allow outputting the first n+1 items (as some answers are doing), then it's 13 bytes (without the last character).

*-1 byte thanks to Jonathan Allan*
> 2 votes

# Answer
# Scala, 109 bytes

```
Stream.iterate(0::Nil)(s=>Stream.from(s(0)).find(x=> !s.exists(Set(0 to x:_*)map(a=>x-a*a))).get::s)map(_(0))

```

Try it in Scastie!

An infinite Stream.

## First n elements, 100 bytes

```
Stream.iterate(0::Nil)(s=>Stream.from(s(0)).find(x=> !s.exists(Set(0 to x:_*)map(a=>x-a*a))).get::s)

```

This is the exact same code, just without the `map(_(0))` part at the end. Given an n, it gives the first n elements of the sequence, but in reverse.

### Another 100 byte solution

```
1.to(_)./:(0::Nil)((s,_)=>Stream.from(s(0)).find(x=> !s.exists(Set(0 to x:_*)map(a=>x-a*a))).get::s)

```

Try it in Scastie

Explanation:

```
Stream.iterate            //Build an infinite Stream by repeatedly applying a function to
  (0::Nil)                //A List containing only a 0
  (s=>                    //The previous elements (in reverse)
    Stream.from(s(0))      //Make a Stream starting from the last element
      .find(x=>            //Find a number with no square difference
        !s.exists(          //Make sure none of the previous elements are in this Set:
          Set(0 to x:_*)     //Start with a set of integers from 0 to x
            map(a=>x-a*a)    //Subtract square from x (to get all elements with squared differences)
         )
      ).get                //Unwrap the Option (as the sequence is infinite)
    ::s                    //Prepend to s, the sequence
  )map(_(0))               //Get the first (or rather, last) element of each partial sequence

```
> 2 votes

# Answer
# APL (Dyalog Unicode), 34 bytes

```
{∇⍵,⎕←⊃(g~⊢)∊⍵∘.+2*⍨(g←⍳2+⌈/)⍵}⎕←0

```

Try it online!

### With a train (and a small dfn), 41 bytes

```
(⊢,(({⎕←⊃⍵}g∘∊~⊢)∘.+∘(2*⍨g←⍳2+⌈/)⍨))⍣≡⎕←0

```

Try it online!
> 1 votes

# Answer
# C (gcc), 99 bytes

```
m,i,k;f(n,l){l*=!!m++;for(i=1;i<m;k%=m,i+=!k)k+=(&l)[i*8]+k*k-l||(l+=i=k=1);!n?m=0,n=l:f(n-1,l+1);}

```

Try it online!

Takes n as input and returns the n-th number in the sequence (0-indexed)

# C (gcc), 78 bytes

shorter solution, extremely slow for n \> 8

Edit: -2 Bytes thanks to ceilingcat

```
f(n,i,k,r){r=n?f(n-1):0;for(i=k=0;k<n;i>n?i=!++k:++i)k=f(k)+i*i-r?k:!++r;n=r;}

```

Try it online!
> 1 votes

# Answer
# Raku, 36 bytes

```
0,{first (*-@_.all).sqrt%1,^∞}...*

```

Try it online!

This is an expression for a lazy, infinite sequence of the required values.
> 1 votes

# Answer
# 05AB1E, 13 bytes

```
0λλU∞.ΔXαÅ²≠P

```

Outputs the infinite sequence.

Try it online.

Should have been 11 bytes by removing `λU` and changing `X` to `λ` (`0λ∞.ΔλαÅ²≠P`), but unfortunately the recursive environment builtin still has some issues here and there, and apparently trying to retrieve the recursive-list `λ` inside a nested loop ( in this case) doesn't work.

Outputting the first \\$n\\$ or \\$n^{th}\\$ value would be 1 byte longer than the infinite list:
try the first \\$n\\$ online or try the 0-based \\$n^{th}\\$ online.

**Explanation:**

```
 λ              # Start a recursive environment,
                # to output the infinite sequence implicitly as result afterwards,
0               # starting a(0)=0,
                # and where every following a(n) is calculated as follows:
   λ            #  Push a list of the previous results of a(0)..a(n-1)
    U           #  Pop and store this list in variable `X`
     ∞.Δ        #  Find the first positive integer [1,2,3,...] which is truthy for:
        X       #   Push list `X`
         α      #   Get for each the absolute difference with the current integer
          Å²    #   Check for each whether it's a square number
            ≠   #   Invert each boolean, so we check they're NOT a square number
             P  #   And check if this is truthy for all of them

```
> 1 votes

---
Tags: code-golf, math, number, sequence, number-theory
---


title: Let's rise higher

text:
# Question
Title: Let's rise higher
# Challenge

The main objective of the challenge is pretty simple, this is an answer chaining contest, where you have to serially print numbers from 1. That means User 1's answer will print `1`, then User 2's answer will print `2` and so on. But there are some rules to make the contest tougher.

# Rules

* **You can't use the characters of the source code used in the previous answer.**
* Use of comments in your code is disallowed.
* You cannot post 2 answers in a row, let me explain, suppose you have written answer no. 5, now you cannot write answer no. 6, you have to wait someone to post a valid answer no. 6 (That prints `6` without using characters in answer no. 5), and after that you can write a valid answer no. 7 following the rules.
* Program cannot take input or access internet.
* Standard loopholes apply.
* You can have leading/trailing newlines but not whitespaces (except newline) in the output.

# Scoring criterion

**This is not challenge, so there is a custom objective scoring criteria. Try to make your score higher.**

* Each answer's initial score is 1. (Only chain beginning answer has score 0).
* For each distinct byte you use, your score is increased by the number of distinct bytes. That means if your number of distinct bytes is `6`, then your score increases by `1+2+3+4+5+6`, and if your number of distinct bytes is `7`, then your score increases by `1+2+3+4+5+6+7` and so on.
* You have to calculate distinct byte difference with the previous answer, and add/subtract score using the 2nd rule. So if byte difference is `3` then you will get a `+1+2+3` score, or if `-3` (Previous answer has 3 more distinct bytes than yours), then `-1-2-3`.
* For each 1 to 9th byte `-1`, from 10th to 19th byte `-2` for each byte, from 20th to 29th byte `-3` for each byte and so on.

A total example:

# Answer format

```
# Answer Number. Language Name, x Bytes, y Distinct bytes, Score: Z

    source code

(TIO/Any other interpreter link) -> Not required, but preferred

```

**example**

```
1. Powershell, x Bytes, y Distinct Bytes, Score: Z

......

```

# Winning criterion

**Winner will be determined after 30 days, winner is determined by total score. But users are welcome to continue the chain after that!**

Suppose you have three answers with score `33,16,78` then your total score will be `33+16+78=127`.

And there is two special prizes from me after 30 days:

* +150 bounty for the winner.
* +50 bounty for the single answer with highest score! (Such as man of the match in Cricket)

# Answer
# 2. Python 3, 102 bytes, 66 distinct bytes, Score: 3710, My Total Score: 3710

```
print(int(str(2+3+4+5+6+7+8+90-25*5+2)+"abcdefghijklmnopqrstuvwxyz`-=:{}][;'_+()*&^%$#@!~`/.,?>< "*0))

```

Try it online!
> 6 votes

# Answer
# 3. Vyxal, 162 bytes, 162 distinct bytes, Score: 16467, My total score: 16467

```
γ₥⌊₴λƛ¬∧⟑∨⟇÷«»°•․⍎Ṛ½∆øÏÔÇæʀʁɾɽÞƈ∞⫙ß⎝⎠⎡⎣⨥⨪∺❝ð→←ÐřŠč√⳹ẊȦȮḊĖẸṙ∑Ĥ⟨⟩ı⁌\tΤĴ²‿⁂ĸ¶⁋⁑Ńń‼⨊≈µʗ◁⊐∫⍋⍒∈ₛ£Œœ≕≠¥ⁱ‹›⍲⍱‸¡⊑≀℅≤≥↜≗⋯⧢ũ⁰¹ªₑϊ≎⇿⊛×¯±⊂⍞፣⍉ΐ₁⊘ᶢ₌↭ſƀƁ⁚⌈⊓⊣Ḟḟ∪∩⊍⁜⌑Ḇ₂⁾₦¼ƒɖꝒ′α″βΠ"

```

Try it Online! The power of Unicode. I'm not sure about the score, but this takes the average of \[1, 2, 8\] (`3.66666...`) and takes the floor of that number.

Feel free to correct my score if needed. I calculated it as \\$(1+2+3+...+162)\\$ \[part 1 of scoring\]

\\$+ (1+2+3+...+96)\\$ \[part 2 of scoring: 162 my answer - 66 previous answer = 96 difference distinct bytes)

* (`sum(map(lambda x: x*10, range(1, 17)))`)\\$ - 16\*2\\$ \[part 3\]

~~My scoring utility. Takes number of distinct bytes in your answer, the number of distinct bytes in the previous answer and the length of your answer~~

Try this one instead. It should work a bit more accurately and work for higher byte counts. Inputs are: a) your distinct bytes, b) last answers distinct bytes, c) program length
> 6 votes

# Answer
# 1. PowerShell, 1 byte, 1 distinct byte, Score: 0, My Total score: 0

```
1

```

Try it online!
> 5 votes

# Answer
# 6. Mornington Crescent, ~~425~~ ~~423~~ 396 bytes, ~~30~~ 32 distinct bytes, score ~~-8475~~ ~~-8391~~ -7155

To break the monotony of using all of the ASCII characters, let's rule out only *some* ASCII characters for the next answer. This is the shortest program in this language that outputs 6. I'm pretty sure making it any longer to include more distinct bytes would make the score even lower, as adding any more extraneous instructions would necessarily reuse some bytes.

```
Take Northern Line to Euston
Take Victoria Line to Seven Sisters
Take Victoria Line to Victoria
Take Circle Line to Victoria
Take District Line to Upminster
Take District Line to Parsons Green
Take District Line to Notting Hill Gate
Take Circle Line to Notting Hill Gate
Take District Line to Upminster
Take District Line to Bank
Take Circle Line to Bank
Take Northern Line to Mornington Crescent

```

Try it online!

Distinct bytes used:  `BCDEGHLMNPSTUVaceghiklmnoprstuv`
> 5 votes

# Answer
# 4. C (gcc), 106 bytes, 91 distinct bytes, Score: 6132, My Total score: 6132

```
main(){printf("%d",strlen(" !#$&'*+./0123\4789:<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`bcghjkoquvwxyz~")-65);}

```

Try it online!
> 4 votes

# Answer
# 7. Keg, 4,376,598 bytes, 2,157,610 distinct bytes, Score: 3697321176253, My total score: 3697321192720

You can find the source code here

Don't even bother trying it online. This uses everything in unicode except the bytes `\n BCDEGHLMNPSTUVaceghiklmnoprstuv`, so the next person to answer is going to have an extremely low score.

Here's how I generated it:

```
file = open("seven.keg", mode="w", encoding="utf-8")
file.write(chr(127240))
file.write("¶")
bad = " BCDEGHLMNPSTUVaceghiklmnoprstuv"
bad += "\n¶" + chr(127240)
for i in range(4294967294):
    letter = chr(i)
    if letter in bad:
        continue
    try:
        file.write(letter)
    except:
        continue
file.close()

```

Which turns into:

```
\";_`<massive string of unicode>`_

```

Which prints `7` and then pushes (`"` \- 1), discards that, pushes a massive string and then discards it.

Don't bother putting the score into my utility. It's calculated via:

$$ \frac{2,157,610 \times 2,157,611}{2} + \frac{(2,157,577 \times 2,157,578}{2} - rule3 $$

* it uses the triangle number formula to speed up computing. `2,157,577 = 2,157,610 - 33`. The total score is calculated by:

```
score = 4655211869108
for i in range(437696):
    score -= 10 * i
score -= 9 * 437695
print(score)
print(score + 16467)

```
> 3 votes

# Answer
# \[5. Vyxal, 12 bytes, 9 distinct bytes, score 3436\]

```
⨥⨥²⨥⨥⨪½Ç◁ṙȦ₴

```

Try it online

Well I really just wanted to get this challenge moving again, after @Noodle9 basically ruled out the entire ASCII character set! So I learnt a little Vyxal just for this... after writing a Deadfish interpreter here Vyxal actually made some sense...

I'm sure I could do more useless operations to the register, but basically its just increment twice, square it, increment twice then decrement for 5, half it for 2.5, subtract from 1 for 1.5, reverse for 5.1, round it for 5, take the absolute value, and output it.

(As far as the scoring, I'm totally confused, I just put what Lyxal's utility gave me. From the text, it sounds like my small answer should have a negative score for being smaller than #4...)
> 2 votes

# Answer
# Deadfish~, 8 bytes, 3 distinct bytes, Score:2,327,635,062,034 according to Lyxal's utility?

```
iisiiiio

```

Try it online!

Well with not many options left from Lyxal's answer for #7, I had to resort to Deadfish...
> 2 votes

---
Tags: number, kolmogorov-complexity, restricted-source, answer-chaining
---


title: Solve a 2x2 Eigensystem

text:
# Question
Title: Solve a 2x2 Eigensystem
For those with a little linear algebra background, the challenge is as simple as this: determine the eigenvalues and eigenvectors of a given complex 2x2 matrix. You may skip ahead to The Challenge for I/O details, etc. For those who need a little refresher on eigensystems, read on.

## Background

The characteristic equation of a matrix \\$A\\$ is defined by

$$\det| A - λI | = 0$$

where \\$λ\\$ is a complex (scalar) parameter, \\$I\\$ is the identity matrix and \\$\det|...|\\$ is the determinant. The left-hand side evaluates to a polynomial in \\$λ\\$, the *characteristic polynomial*, which is quadratic in the case of 2x2 matrices. The solutions of this characteristic equation are the *eigenvalues* of \\$A\\$, which we will denote as \\$λ\_1\\$ and \\$λ\_2\\$.

Now the *eigenvectors* \\$v\_i\\$ of \\$A\\$ satisfy

$$Av\_i = λ\_iv\_i$$

For each \\$λ\_i\\$, this gives you a system of two equations in two unknowns (the components of \\$v\_i\\$), which can be solved quite easily. You will notice that the system is actually underspecified, and the magnitude of the eigenvectors are not determined by the equations. We will usually want the eigenvectors to be normalised, that is \\$\sqrt{|x|^2 + |y|^2} = 1\\$, where \\$x\\$ and \\$y\\$ are the vector components, \\$|x|^2\\$ is \\$x\\$ multiplied by its complex conjugate.

Note that the eigenvalues may be degenerate, i.e. \\$λ\_1 = λ\_2\\$. In this case, you may or may not be able to satisfy the single system of equations with two linearly independent eigenvectors.

## The Challenge

Given a 2x2 matrix with complex elements, determine its two (possibly identical) eigenvalues and a normalised eigenvector for each eigenvalue. The resulting numbers must be accurate to at least 3 (decimal) significant digits. You may assume that the real and imaginary parts of any matrix element is in the range \\$\[-1,1\]\\$.

You may write a function or a program, taking input via STDIN, command-line argument, prompt or function argument. You may output the result to STDOUT, a dialog box or as the function return value.

You may use any convenient (but unambiguous) string or list format for input and output. You can also choose between pairs of floats or complex types to represent the individual numbers.

You must not use built-in functions for solving eigensystems (like Mathematica's `Eigenvectors` or `Eigensystem`) or equation solvers.

This is code golf, so the shortest answer (in bytes) wins.

## Examples

Each example is three lines: the input, the eigenvalues and the corresponding eigenvectors in the same order. Note that the eigenvectors are only determined up to their phase, and that in the case of degenerate eigenvalues, the eigenvectors may actually be arbitrary (as in the first example).

```
[[1.0, 0.0], [0.0, 1.0]]
[1.0, 1.0]
[[1.0, 0.0], [0.0, 1.0]]

[[0.0, 0.4], [-0.1, -0.4]]
[-0.2, -0.2]
[[0.894427, -0.447214], [0.894427, -0.447214]]

[[0.3, 0.1], [0.4, -0.9]]
[-0.932456, 0.332456]
[[-0.0808731, 0.996724], [0.951158, 0.308703]]

[[0.5, -1.0], [0.8, -0.5]]
[0.74162i, - 0.74162i]
[[0.745356, 0.372678 - 0.552771i], [0.745356, 0.372678 + 0.552771i]]

[[-0.0539222 + 0.654836i, -0.016102 + 0.221334i], [0.739514 - 0.17735i, -0.0849216 + 0.77977i]]
[0.238781 + 0.984333i, -0.377625 + 0.450273i]
[[0.313668 + 0.322289i, 0.893164], [-0.236405 - 0.442194i, 0.865204]]

[[-0.703107 - 0.331792i, 0.286719 - 0.587305i], [-0.418476 + 0.396347i, -0.885934 + 0.50534i]]
[-1.13654 - 0.32678i, -0.4525 + 0.500329i]
[[0.833367, -0.248208 - 0.493855i], [-0.441133 - 0.408236i, 0.799215]]

[[-0.156312 + 0.788441i, 0.045056 - 0.579167i], [0.130741 - 0.97017i, 0.049183 - 0.590768i]]
[-0.181759 + 1.11738i, 0.0746298 - 0.919707i]
[[0.86955, -0.493846 + 0.000213145i], [0.318856 - 0.0181135i, 0.94763]]

```

# Answer
# MATLAB, 91

A standard technique to obtain a normalized vector and remove the useless degree of freedom is representing the elements of the vector as the cosine and sine of some angle.

I originally tried to code in Python, but its math handling proved to be too brain-damaged. Its math functions refused to accept complex values, and it does not understand that floating-point division by zero is OK.

```
function[]=f(a,b,c,d)
L=(a+d+[1,-1]*((a-d)^2+4*b*c)^.5)/2
t=atan((L-a)/b);v=[cos(t);sin(t)]

```

First the two eigenvalues are printed under the heading `L =`. Then two column vectors are printed under the corresponding values of L, under `v =`. The code may fail to give linearly independent vectors in cases where it is possible to do so (such a program normally would be considered broken), but Martin said it is not required.
> 7 votes

# Answer
# Python 2, 198 bytes

```
a,b,c,d=input()
H=(a+d)/2
D=(H*H-a*d+b*c)**.5
X,Y=H+D,H-D
p,q,r,s=[[1,0,0,1],[b,X-a,b,Y-a],[X-d,c,Y-d,c]][2*(c!=0)or(b!=0)]
A=abs
V=A(A(p)+A(q)*1j)
W=A(A(r)+A(s)*1j)
print[X,Y],[[p/V,q/V],[r/W,s/W]]

```

Input is a flat list of 4 complex numbers via STDIN, e.g.

```
[0.0+0j, 0.4+0j, -0.1+0j, -0.4+0j]

```

Note that Python uses `j` instead of `i` for complex numbers.

Output is two lists, the first containing the eigenvalues and the second containing the eigenvectors, e.g.

```
[(-0.2+0j), (-0.2+0j)]
[[(0.8944271909999159+0j), (-0.4472135954999579+0j)], [(0.8944271909999159+0j), (-0.4472135954999579+0j)]]

```

*(newline inserted for clarity)*
> 8 votes

# Answer
# APL (Dyalog Classic), 59 bytes

```
{a b c d←⍵⋄l,2 1∘.○¯3○b÷⍨a-⍨l←2÷⍨a+d(+,-).5*⍨(4×b×c)+×⍨a-d}

```

**Derivation of formula for eigenvalues:** $$ det|A-\lambda I|=0 \\ det\left|\begin{pmatrix} a & b \\ c & d \end{pmatrix}- \begin{pmatrix} \lambda & 0 \\ 0 & \lambda \end{pmatrix}\right|=0 \\ det\left|\begin{pmatrix} a-\lambda & b \\ c & d-\lambda \end{pmatrix}\right|=0 \\ (a-\lambda)(d-\lambda)-bc=0 \\ \lambda^{2}-(a+d)\lambda+ad-bc=0 \\ \lambda=\frac{a+d\pm \sqrt{(a+d)^{2}-4(ad-bc)}}{2} \\ \lambda=\frac{a+d\pm \sqrt{a^{2}+2ad+d^{2}-4ad+4bc}}{2} \\ \lambda=\frac{a+d\pm \sqrt{a^{2}-2ad+d^{2}+4bc}}{2} \\ \lambda=\frac{a+d\pm \sqrt{(a-d)^{2}+4bc}}{2} $$ As for the eigenvectors... everything I tried myself was longer than the MATLAB answer that I don't really understand yet. May add another explanation here at some point.

The code is then a simple implementation of these formulae.

```
{a b c d←⍵⋄l,2 1∘.○¯3○b÷⍨a-⍨l←2÷⍨a+d(+,-).5*⍨(4×b×c)+×⍨a-d}
 a b c d←⍵                                                    ⍝ assign variable names
                            l←2÷⍨a+d(+,-).5*⍨(4×b×c)+×⍨a-d    ⍝ formula for the eigenvalues
             2 1∘.○¯3○b÷⍨a-⍨l                                 ⍝ formula for the eigenvectors
           l,                                                 ⍝ append eigenvalues

```

Try it online!
> 5 votes

# Answer
# Lua, ~~462~~ ~~455~~ ~~431~~ 427 bytes

There is no built-in complex math in Lua. No vector operations either. All had to be rolled by hand.

```
a,b,c,d,e,f,g,h=...x=math.sqrt z=print i=a-g j=b-h
k=(i^2-j^2)/2+2*(c*e-d*f)m=x(k^2+(i*j+2*(c*f+d*e))^2)n=x(m+k)o=x(m-k)i=(a+g+n)/2
j=(b+h+o)/2 k=(a+g-n)/2 l=(b+h-o)/2 z(i,j,k,l)q=c^2+d^2 r=e^2+f^2 s=q+r if s==0
then z(1,0,0,0,0,0,1,0)else if r==0 then m,n,o,p=c,d,c,d c,d=i-a,j-b e,f=k-a,l-b
u=x(q+c^2+d^2)v=x(q+e^2+f^2)else m,n=i-g,j-h o,p=k-g,l-h c,d=e,f
u=x(r+m^2+n^2)v=x(r+o^2+p^2)end z(m/u,n/u,o/v,p/v,c/u,d/u,e/v,f/v)end

```

Run from the command-line with the following arguments:

```
lua eigen.lua Re(a) Im(a) Re(b) Im(b) Re(c) Im(c) Re(d) Im(d)

```

Produces the following output:

```
Re(lambda1) Im(lambda1) Re(lambda2) Im(lambda2)
Re(v11) Im(v11) Re(v12) Im(v12) Re(v21) Im(v21) Re(v22) Im(v22)

```

...for a,b,c,d the 4 components of the input matrix, lambda1 and lambda2 the two eigenvalues, v11,v21 the first unit eigenvector, and v12,v22 the second unit eigenvector. For example,

```
lua eigen.lua 1 0  1 0  1 0  0 0

```

...produces...

```
1.6180339887499 0   -0.61803398874989   0
0.85065080835204    0   -0.52573111211913   0   0.52573111211913    0   0.85065080835204    0

```
> 4 votes

---
Tags: code-golf, math, matrix, linear-algebra, complex-numbers
---


title: Interpret Befunge-93

text:
# Question
Title: Interpret Befunge-93
The program will be provided as the first argument, stdin should be used for all read requests by the program and stdout for all write requests. It can be assumed that the program is less than 80 characters wide and less than 25 lines high.

* `~` should push -1 if there is nothing to read.
* Any pop off the bottom of the list should simply return 0, including for any calculations.
* For `p` and `g`, `x` and `y` are 0 based indices.
* Input should be fully buffered, i.e. `&` and `~` block the program until `EOF` is encountered on stdin then any remaining input is kept to serve future requests.

The following commands must be available:

> `0-9`  Push this number on the stack `+`  Addition: Pop `a` then `b`, push `a+b` `-`  Subtraction: Pop `a` then `b`, push `b-a` `*`  Multiplication: Pop `a` then `b`, push `a*b` `/`  Integer division: Pop `a` then `b`, push `b/a`, rounded down. If `a` is 0, result is undefined `%`  Modulo: Pop `a` then `b`, push the remainder of the integer division of `b/a`. If `a` is 0, result is undefined `!`  Logical NOT: Pop a value. If the value is 0, push 1; otherwise, push 0. ```  Greater than: Pop `a` then `b`, push 1 if `b>a`, otherwise 0. `>`  Start moving right `<`  Start moving left `^`  Start moving up `v`  Start moving down `?`  Start moving in a random cardinal direction `_`  Pop a value; move right if value=0, left otherwise `|`  Pop a value; move down if value=0, up otherwise `"`  Start string mode: push each character's ASCII value all the way up to the next `"` `:`  Duplicate value on top of the stack `\`  Swap two values on top of the stack `$`  Pop value from the stack `.`  Pop value and output as an integer `,`  Pop value and output as ASCII character `#`  Trampoline: Skip next cell `p`  A "put" call (a way to store a value for later use). Pop `y` then `x` then `v`, change the character at the position `(x,y)` in the program to the character with ASCII value `v` `g`  A "get" call (a way to retrieve data in storage). Pop `y` then `x`, push ASCII value of the character at that position in the program `&`  Input an integer (may be multiple characters and may be negative) and push it `~`  Input a single character from stdin and push its ASCII value `@`  End program

This is a code golf, shortest answer wins. If there is a tie then the first answer wins.

You may use any language feature not specifically designed for Befunge to implement this, if you want to try and translate Befunge to native code and eval it good luck.

For test cases look at my recent answers. The reference interpreter I have been using is http://www.quirkster.com/js/befunge.html.

One quick test case of some features from `"egnufeB">:#,_@`

```
1-0g:"Z"-#v_$91+"sparw tup/teG">:#,_$               v                          Z
          >:" "-#v_$91+"ecaps snruter teg BOO">:#,_$v
v                >0" snruter teg BOO">:#,_$.91+,    >
>8:+:*11p11g#v_91+"tib 8 dengis"01-11p11g!#v_"nu">" era slleC">:#,_v
vv           >91+"tib 8>"                  >     ^                 >91+"krow " #
 >        >"spmuj egdE">:#,_   91+"krow "04-3%1+#v_        >"sredniamer evitag"v
>"ton od "^                                      >"ton od "^
"eN">:#,_  91+"skrow edomgnirts ni @">:#,_@                                    >

```

# Answer
> 25 votes
# Befunge-93 - ~~404~~ ~~371~~ ~~361~~ ~~352~~ ~~339~~ ~~337~~ 323 bytes

```
<xyXYvp01<>110vv5_v#`0+1:_v#+!-"g"\<v"<":::<>1v#p03-1_>! g20gp00g1+0v25p
v2g02 < p0 20p<+vp020p01-10$_:"p"-!^>>-!\ v^ <>0p20pv|!*-";"\+1::~p0<
v2-10<^v# ^#<  <<$<       < ^+!-"_"\+!-"?"<>#^_10v4p<:^00 _$20g1+20p^
v21p010>#<40g20v>\%:40p5+g:92p:75*1--00g!\#^_\$0 v   >91+-^
<3+g01g 03p04+g<^++g04g02:*54p03:%\++g03g01:"P"p0<

```

Try It Online!

Input program must have at most 20 lines. Input can be provided in same file as Befunge program by placing it after a `;` character. Yes, it can interpret itself, but the `*54` in the bottom line should be replaced by `*53` if you do that. And if you ask that interpreted interpreter to interpret itself, change it to `*52` etc. If run in a Befunge-97 interpreter, it will also support the `a-f` commands (but not `'` or any new command that affects control flow or wrapping behavior).

Note that it basically asks the interpreter it runs in to handle all the stuff relating to I/O and stack, so its specific behavior is largely dependent on that of the interpreter running it. In other words, it is perfectly compliant if run in a compliant interpreter.

It works by reading in the program from input (until EOF or semicolon) directly into the playfield below it, then simulating the movement of a virtual instruction pointer through that program. It copies each command from the program into its own execution area (at position (9,2) on the grid) and runs its own instruction pointer through it after ensuring all of its own data has been removed from the stack (as all of the interpreted program's stack data is maintained at the bottom of the stack). This is the standard methodology for Befunge self-interpretation since the early 00s, but I don't think it has ever been done in such a small program.

A fuller explanation is in the annotations you can see by clicking the link above.

# Answer
> 11 votes
## Perl, 515 ~~525~~ ~~532~~

Ok, so this might not be the most readable code I've ever written, but it does run all the examples in the reference implementation page properly, and use -1 as a `~`-didn't-have-a-reply value. (the programs in the page exercise the empty stack behavior extensively)

As usual, Perl 5.10 or later. In this instance, `-M5.010` is your best bet. Newlines for presentation on CG.SE, you should remove them before trying. (in this "edit 1.5" ragged-right version, it might actually work out of the box)

```
@p=map[/./g],<>;$h=1;$_="for(;;){for(D_=P[Y][X]){
when('\"BS=!S}when(!!S){IordW0'||/\\d/){ID_W+BIO+
OW-BEO;IO-MW*BIO*OW/BEO;Iint(O/M)W%BEO;IO% MW!BI!
OW`BEO;I(M<O)W?BD_=qw(< > ^ v)[rand 4]R_BD_=O?'<'
:'>'R|BD_=O?'^':'v'R>BH=1;V=0W<BH=-1;V=0W^BH=0;V
=-1WvBH=0;V=1W:BI0+S[-1]W\\\\BIO,OWDBOW.BsayOW,B
print chrOW#BFWpBEO;N=O;P[M][N]=chrOWgBEO;IordP[
M][O]W&BIE<>W~BIord<>||-1WABexit}}F}";s/B/'){/g;
s/I/pushAs,/g;s/E/M=/g;s/F/X=(X+H)%A{P[0]};Y=(Y+
V)%Ap/g;s/O/(popAs)/g;s/R/;redoW/g;s/W/}when('/g
;y/DA/$@/;s/[A-Z]/\$\l$&/g;eval

```

Improvements welcome :-D

*Edit 1:* fix integer division (+2), reorganize (-9)

*Edit ~~2~~ 1.5:* ~~read char by char (+4);~~ halt on division by zero (-10)

Still missing char by char input, I'm not clear yet how it parses numbers and I'm too tired to be able to do it now.

Not motivated enough to make the cell size unsigned 8-bit as suggested by the compatibility test, and not sure how negative remainders are expected in an unsigned environment.

# Answer
> 8 votes
## 16bit MSDOS .COM File - 1104 bytes

This is Base64 encoded (decoder here), save decoded file as a .com and execute from command line with name of program file to run as the only argument. Tested in WinXP command prompt.

```
yEAAADP/jNiAxBCJRv6JRvKAxBCJfuqJRuyJfvqJfviJfvSAxBCJRvbHRuiMAo7AM8C5AIDzq7Qs
zSGJVvC6RgWKHoAAMv+A6wF9Cei3ALQJzSHJw8aHggAAuAA9uoIAzSG6SAVy5YvYjkb+uQCAM8Dz
q7kBALpQBbQ/zSG6SgVyygvAdCWgUAU8CnQHPCBy4qrr34vHOkb5cgOIRvn+RviB5wD/gccAAevI
tD7NIQv/ukwFdJa4AwDNEDPb6FQAtAfNITxxdDk8cnQhPDF0DTwydBE8c3Xo6I8A6+CLRvaJRvLr
2ItG/olG8uvQi0b2iUby6B4A6HEAgH76AHTu67zoAgDJw7gAuI7AuCAHuQCA86vDYB6OXvK4ALiO
wLUZM/8z9rQHsVCsq/7JdfqBxrAA/s118FOLRvI7Rv6yz3QFi170svCA+1BzG4D/GXMWise0oPbk
ANiA1AAA2IDUAIv4R4rCqlsfYcOORv4migc8MHJVPDl3UbQALDDoKwD/ZugK23UDil75/svD/sM6
Xvl1+DLbwwr/dQOKfvj+z8P+xzp++HX4Mv/DBsR+6quJfuoHwwbEfuozwAv/dAmD7wImiwWJfuoH
w77uBIPGA4A8/3QOOAR19ItEAQvAdAP/4MO6TgXpZP7olP8migc8InSNtADos//r7+i4/4nB67To
9v8Dwel0/+ju/yvB6Wz/6Ob/9+npZP/o3v+Z9/npW//o1f+Z9/mLwulQ/+iF/wvAuAEAdAFI6UL/
6Lz/O8G4AQB/AUjpNP/HRuiMAukv/+hh/wvAdPHHRuiCAukg/+hS/wvAdAjHRuiWAukR/8dG6KAC
6Qn/i0bwuk189+IFGTaJRvAkBgWSA4vwrYlG6Ont/pYCoAKCAowC6Bf/6Ar/6dn+6FP/kegA/4nI
6c3+6AL/6cr+6Pz+C8B5CffYULAt6CYAWFO7UAUz0rkKAPfxgMIwiBdDC8B170uKB+gKAIH7UAV1
9Fvplf48CnQUBsR+9KqLxzxQdQSBx7AAiX70B8PGRvQA/kb1w+in/uja/+ls/uhp/ulm/ugOAOiV
/gaORv4miAQH6VX+6If+ik74C8B5BwLBgNQA6/X28YjhtQDocP5Rik75C8B5BwLBgNQA6/X28Yjg
WYjMi/DD6Mr/Bo5G/iaKBAe0AOkP/v928otG9olG8jP2Msnol/20B80hPC11CwrJdfH+wehc/+vq
PA11Do9G8ovGCsl0AvfY6dr9iMUsMDwJd9C0AFCwCvfmC9JadcT2xIB1vwHC9saAdbiJ1ojo6CH/
66//dvKLRvaJRvLoPf20B80hPCBy+FDoB/9YtACPRvLpkP3GRvoBwysAAy0IAyoQAy8YAyUhAyEs
A2A6Az5IAzxXA15mA3ZuAz92A19QA3xfAyLoAjqaA1yjAySvAy61AywKBCMTBHAZBGddBCZtBH7L
BEDsBCB/AgB/Av8xJDIkMyQ0JDUk

```

On startup, the display shows the program. Commands are:

* r - runs the program (switches to output screen)
* s - single steps the program
* q - quits the interpreter
* 1 - shows output screen (white cursor is current output position)
* 2 - shows program screen (red cursors is current program position)

When an input command is executed, the display switches to the output screen. Input is echoed to the output screen. For ascii input, only characters in the range 32-255 are accepted. For numeric input, only values in the range -32768 to 32767 are allowed, press enter to complete input (sorry, no backspace).

I really should add a stack screen as well.

**Update**

Here's the original assembly source code, assembled using A86. It's quite long:

```
  enter 64,0
  xor di,di
  mov ax,ds
  add ah,10h
  mov [bp-2],ax   ; program
  mov [bp-14],ax  ; current display
  add ah,10h
  mov w[bp-22],di ; stack off
  mov [bp-20],ax  ; stack seg
  mov w[bp-6],di  ; exit status
  mov w[bp-8],di  ; size of field -8=lines,-7=columns
  mov w[bp-12],di ; output window position
  add ah,10h
  mov w[bp-10],ax; output segment
  mov w[bp-24],MoveRight

  ; clear output
  mov es,ax
  xor ax,ax
  mov cx,8000h
  rep stosw

  ; random seed
  mov ah,2ch
  int 21h
  mov w[bp-16],dx

  ; get filename
  mov dx,StrNoFile
  mov bl,[80h]
  xor bh,bh
  sub bl,1
  jge NoError

Error:
  call ClearScreen
  mov ah,9
  int 21h
  leave
  ret

NoError:
  ; open file
  mov b[82h+bx],0
  mov ax,3d00h
  mov dx,82h
  int 21h
  mov dx,StrBadFile
  jc Error
  mov bx,ax
  ; clear program
  mov es,[bp-2]
  mov cx,8000h
  xor ax,ax
  rep stosw
  ; read file
ReadLoop:
  mov cx,1
  mov dx,EOP
  mov ah,3fh
  int 21h
  mov dx,StrBadRead
  jc Error
  or ax,ax
  jz EOF
  mov al,b[EOP]
  cmp al,10
  je EOL
  cmp al,32
  jb ReadLoop
  stosb
  jmp ReadLoop
EOL:
  mov ax,di
  cmp al,[bp-7]
  jb l9
  mov [bp-7],al
l9:
  inc b[bp-8]
  and di,0ff00h
  add di,100h
  jmp ReadLoop
EOF:
  mov ah,3eh
  int 21h
  or di,di
  mov dx,StrEmptyFile
  jz Error
  ; initialise
  mov ax,3
  int 10h
  xor bx,bx ; PC
  ; execute
Redraw:
  call DisplayProgram
WaitForInput:
  mov ah,7
  int 21h
  cmp al,'q'
  je Quit
  cmp al,'r'
  je DoRun
  cmp al,'1'
  je ShowIO
  cmp al,'2'
  je ShowProgram
  cmp al,'s'
  jne WaitForInput
  ; single step
  call Execute
  jmp Redraw

ShowIO:
  mov ax,[bp-10]
  mov [bp-14],ax
  jmp Redraw

ShowProgram:
  mov ax,[bp-2]
  mov [bp-14],ax
  jmp Redraw

DoRun:
  mov ax,[bp-10]
  mov [bp-14],ax
  call DisplayProgram
  call Execute
  cmp b[bp-6],0
  je DoRun
  jmp Redraw

Quit:
  call ClearScreen
  leave
  ret

ClearScreen:
  mov ax,0b800h
  mov es,ax
  mov ax,720h
  mov cx,8000h
  rep stosw
  ret

DisplayProgram:
  pusha
  push ds
  mov ds,[bp-14]
  mov ax,0b800h
  mov es,ax
  mov ch,25
  xor di,di
  xor si,si
  mov ah,7
l1:
  mov cl,80
l2:
  lodsb
  stosw
  dec cl
  jnz l2
  add si,256-80
  dec ch
  jnz l1
  push bx
  mov ax,[bp-14]
  cmp ax,[bp-2]
  mov dl,0cfh
  je l33
  mov bx,[bp-12]
  mov dl,0f0h
l33:
  cmp bl,80
  jae l3
  cmp bh,25
  jae l3
  mov al,bh
  mov ah,160
  mul ah
  add al,bl
  adc ah,0
  add al,bl
  adc ah,0
  mov di,ax
  inc di
  mov al,dl
  stosb
l3:
  pop bx
  pop ds
  popa
  ret

Execute:
  mov es,[bp-2]
  mov al,es:[bx]

  cmp al,'0'
  jb NotPush
  cmp al,'9'
  ja NotPush

  ; push number
  mov ah,0
  sub al,'0'
PushValueUpdatePC:
  call PushValue
UpdatePC:
  jmp [bp-24]

MoveLeft:
  or bl,bl
  jnz MoveLeftNoWrap
  mov bl,[bp-7]
MoveLeftNoWrap:
  dec bl
  ret

MoveRight:
  inc bl
  cmp bl,[bp-7]
  jne ret
  xor bl,bl
  ret

MoveUp:
  or bh,bh
  jnz MoveUpNoWrap
  mov bh,[bp-8]
MoveUpNoWrap:
  dec bh
  ret

MoveDown:
  inc bh
  cmp bh,[bp-8]
  jne ret
  xor bh,bh
  ret

PushValue:
  push es
  les di,[bp-22]
  stosw
  mov [bp-22],di
  pop es
  ret

PopValue:
  push es
  les di,[bp-22]
  xor ax,ax
  or di,di
  jz PopValueZero
  sub di,2
  mov ax,es:[di]
  mov [bp-22],di
PopValueZero:
  pop es
  ret

NotPush:
  mov si,Functions-3
NextFunction:
  add si,3
FindFunction:
  cmp b[si],255
  je Endsearch
  cmp b[si],al
  jne NextFunction
  mov ax,[si+1]
  or ax,ax
  je EndSearch
  jmp ax
  ret

EndSearch:
  mov dx,StrEndSearch
  jmp Error

DoStringMode:
  call UpdatePC
  mov al,es:[bx]
  cmp al,'"'
  je UpdatePC
  mov ah,0
  call PushValue
  jmp DoStringMode

PopTwoValues:
  call PopValue
  mov cx,ax
  jmp PopValue

DoAdd:
  call PopTwoValues
  add ax,cx
  jmp PushValueUpdatePC

DoSub:
  call PopTwoValues
  sub ax,cx
  jmp PushValueUpdatePC

DoMultiply:
  call PopTwoValues
  imul cx
  jmp PushValueUpdatePC

DoDivide:
  call PopTwoValues
  cwd
  idiv cx
  jmp PushValueUpdatePC

DoModulo:
  call PopTwoValues
  cwd
  idiv cx
  mov ax,dx
  jmp PushValueUpdatePC

DoNot:
  call PopValue
  or ax,ax
  mov ax,1
  jz DoNotZero
  dec ax
DoNotZero:
  jmp PushValueUpdatePC

DoGreaterThan:
  call PopTwoValues
  cmp ax,cx
  mov ax,1
  jg DoGreaterThanIs1
  dec ax
DoGreaterThanIs1:
  jmp PushValueUpdatePC

DoMoveRight:
  mov [bp-24],MoveRight
  jmp UpdatePC

DoLeftRight:
  call PopValue
  or ax,ax
  jz DoMoveRight

DoMoveLeft:
  mov [bp-24],MoveLeft
  jmp UpdatePC

DoMoveUpDown:
  call PopValue
  or ax,ax
  jz DoMoveDown

DoMoveUp:
  mov [bp-24],MoveUp
  jmp UpdatePC

DoMoveDown:
  mov [bp-24],MoveDown
  jmp UpdatePC

DoRandomDirection:
  mov ax,[bp-16]
  mov dx,31821
  mul dx
  add ax,13849
  mov [bp-16],ax
  and al,6
  add ax,Movements
  mov si,ax
  lodsw
  mov [bp-24],ax
  jmp UpdatePC

Movements:
  dw MoveUp, MoveDown, MoveLeft, MoveRight

DoDuplicate:
  call PopValue
  call PushValue
  jmp PushValueUpdatePC

DoSwap:
  call PopTwoValues
  xchg ax,cx
  call PushValue
  mov ax,cx
  jmp PushValueUpdatePC

DoPop:
  call PopValue
  jmp UpdatePC

DoPopPrint:
  call PopValue
  or ax,ax
  jns Positive
  neg ax
  push ax
  mov al,'-'
  call PrintChar
  pop ax
Positive:
  push bx
  mov bx,EOP
DivLoop:
  xor dx,dx
  mov cx,10
  div cx
  add dl,'0'
  mov [bx],dl
  inc bx
  or ax,ax
  jnz DivLoop
PrintLoop:
  dec bx
  mov al,[bx]
  call PrintChar
  cmp bx,EOP
  jne PrintLoop
  pop bx
  jmp UpdatePC

PrintChar:
  cmp al,10
  je AsciiCR
  push es
  les di,[bp-12]
  stosb
  mov ax,di
  cmp al,80
  jne NoLF
  add di,256-80
NoLF:
  mov [bp-12],di
  pop es
  ret
AsciiCR:
  mov b[bp-12],0
  inc b[bp-11]
  ret

DoPopAsciiPrint:
  call PopValue
  call PrintChar
  jmp UpdatePC

DoTrampoline:
  call UpdatePC
  jmp UpdatePC

DoPut:
  call GetCoord
  call PopValue
  push es
  mov es,[bp-2]
  mov es:[si],al
  pop es
  jmp UpdatePC

GetCoord:
  call PopValue
  mov cl,[bp-8]
DoGet1:
  or ax,ax
  jns DecrementY
  add al,cl
  adc ah,0
  jmp DoGet1
DecrementY:
  div cl
  mov cl,ah
  mov ch,0
  call PopValue ; x
  push cx
  mov cl,[bp-7]
DoGet2:
  or ax,ax
  jns DecrementX
  add al,cl
  adc ah,0
  jmp DoGet2
DecrementX:
  div cl
  mov al,ah
  pop cx ; ax=x, cx=y
  mov ah,cl
  mov si,ax
  ret

DoGet:
  call GetCoord
  push es
  mov es,[bp-2]
  mov al,es:[si]
  pop es
  mov ah,0
  jmp PushValueUpdatePC

DoInput:
  push [bp-14]
  mov ax,[bp-10]
  mov [bp-14],ax
  xor si,si
  xor cl,cl
DoInput1:
  call DisplayProgram
  mov ah,7
  int 21h
  cmp al,'-'
  jne DoInputEnter
  or cl,cl
  jnz DoInput1
  inc cl
  call PrintChar
  jmp DoInput1

DoInputEnter:
  cmp al,13
  jnz DoInputDigit

  pop [bp-14]
  mov ax,si
  or cl,cl
  jz DoInput3
  neg ax
DoInput3:
  jmp PushValueUpdatePC

DoInputDigit:
  mov ch,al
  sub al,'0'
  cmp al,9
  ja DoInput1
  mov ah,0
  push ax
  mov al,10
  mul si
  or dx,dx
  pop dx
  jnz DoInput1
  test ah,80h
  jnz DoInput1
  add dx,ax
  test dh,80h
  jnz DoInput1
  mov si,dx
  mov al,ch
  call PrintChar
  jmp DoInput1

DoInputAscii:
  push [bp-14]
  mov ax,[bp-10]
  mov [bp-14],ax
  call DisplayProgram
DoInputAscii1:
  mov ah,7
  int 21h
  cmp al,32
  jb DoInputAscii1
  push ax
  call PrintChar
  pop ax
  mov ah,0
  pop [bp-14]
  jmp PushValueUpdatePC

DoExit:
  mov b[bp-6],1
  ret

Functions:
  db '+' ; Addition: Pop a then b, push a+b
  dw DoAdd
  db '-' ; Subtraction: Pop a then b, push b-a
  dw DoSub
  db '*' ; Multiplication: Pop a then b, push a*b
  dw DoMultiply
  db '/' ; Integer division: Pop a then b, push b/a, rounded down. If a is 0, result is undefined
  dw DoDivide
  db '%' ; Modulo: Pop a then b, push the remainder of the integer division of b/a. If a is 0, result is undefined
  dw DoModulo
  db '!' ; Logical NOT: Pop a value. If the value is 0, push 1; otherwise, push 0.
  dw DoNot
  db '`' ; Greater than: Pop a then b, push 1 if b>a, otherwise 0.
  dw DoGreaterThan
  db '>' ; Start moving right
  dw DoMoveRight
  db '<' ; Start moving left
  dw DoMoveLeft
  db '^' ; Start moving up
  dw DoMoveUp
  db 'v' ; Start moving down
  dw DoMoveDown
  db '?' ; Start moving in a random cardinal direction
  dw DoRandomDirection
  db '_' ; Pop a value; move right if value=0, left otherwise
  dw DoLeftRight
  db '|' ; Pop a value; move down if value=0, up otherwise
  dw DoMoveUpDown
  db '"' ; Start string mode: push each character's ASCII value all the way up to the next "
  dw DoStringMode
  db ':' ; Duplicate value on top of the stack
  dw DoDuplicate
  db '\' ; Swap two values on top of the stack
  dw DoSwap
  db '$' ; Pop value from the stack
  dw DoPop
  db '.' ; Pop value and output as an integer
  dw DoPopPrint
  db ',' ; Pop value and output as ASCII character
  dw DoPopAsciiPrint
  db '#' ; Trampoline: Skip next cell
  dw DoTrampoline
  db 'p' ; A "put" call (a way to store a value for later use). Pop y then x then v, change the character at the position (x,y) in the program to the character with ASCII value v
  dw DoPut
  db 'g' ; A "get" call (a way to retrieve data in storage). Pop y then x, push ASCII value of the character at that position in the program
  dw DoGet
  db '&' ; Input an integer (may be multiple characters and may be negative) and push it
  dw DoInput
  db '~' ; Input a single character from stdin and push its ASCII value
  dw DoInputAscii
  db '@' ; End program
  dw DoExit
  db ' ' ; NOP
  dw UpdatePC
  db 0 ; NOP
  dw UpdatePC
  db 255

StrNoFile:
  db "1$";"No File$"
StrBadFile:
  db "2$";"Bad File$"
StrBadRead:
  db "3$";"Bad Read$"
StrEmptyFile:
  db "4$";"Empty File$"
StrEndSearch:
  db "5$";"Bad Instruction$"
EOP:

```

# Answer
> 7 votes
# C (gcc), ~~853 815 801 787 770 748 735 745~~ 737 bytes

```
#define z(a,b);a(){b;}
#define Y*s
#define Z*s--
S[1<<20],Y=S,x,y,m,r,c=-1,t,n=80;char M[2000]z(b,Y=!Y)z(G,m=1)z(k,x&1?r-=x-2:(c-=x-1))z(H,Z)z(E,Y%=Z)z(K,scanf("%d",++s))z(B,Y*=Z)z(A,Y+=Z)z(i,putchar(Z))z(a,Y-=Z)z(I,printf("%d ",Z))z(d,Y/=Z)z(g,Y=Y++)z(L,x=2)z(R,x=0)z(w,Y++^=Z^=Y++^=Z)z(U,x=3)z(h,Z?L():R())z(e,Y=Z<Y)z(J,Y=M[Z*n+Y])z(j,M[Z*n+Z]=s[-2];Z)z(D,x=1)z(v,Z?U():D())z(l,*++s=getchar())F();(*f[])()={[33]=b,G,k,H,E,K,[42]=B,A,i,a,I,d,[58]=g,0,L,0,R,F,[92]=w,0,U,h,e,['g']=J,['p']=j,['v']=D,['|']=v,0,l}z(F,f["><^v"[rand()&3]]())main(C,V)int**V;{for(t=open(V[1],!memset(M,32,2000));read(t,&C,1);)C-10?M[y*n+x++]=C:(x=!++y);for(R();m|t-64;m?t-34?*++s=t:(m=0):t>47&t<58?*++s=t-48:f[t]&&f[t]())k(),t=M[(r=(r+25)%25)*n+(c=(c+n)%n)];}

```

Try it online!

The program is loaded into an array and the interpreter enters the main loop; the byte at the current program counter is the offset of an array of function pointers, each function performs the operation required by that instruction. String mode and numeric literals are special cases that are handled differently.

Slightly golfed less

```
#define z(a,b);a(){b;}
#define Y*s
#define Z*s--
S[1<<20],Y=S,x,y,m,r,c=-1,t;
char M[2000]
z(b,Y=!Y)                  /* ! */
z(G,m=1)              /* string mode */
z(k,x&1?r-=x-2:(c-=x-1))   /* # */
z(H,Z)                     /* $ */
z(E,Y%=Z)                  /* % */
z(K,scanf("%d",++s))       /* & */
z(B,Y*=Z)                  /* * */
z(A,Y+=Z)                  /* + */
z(i,putchar(Z))            /* , */
z(a,Y-=Z)                  /* - */
z(I,printf("%d ",Z))       /* . */
z(d,Y/=Z)                  /* / */
z(g,Y=Y++)                 /* : */
z(L,x=2)                   /* < */
z(R,x=0)                   /* > */
z(w,Y++^=Z^=Y++^=Z)        /* \ */
z(U,x=3)                   /* ^ */
z(h,Z?L():R())             /* _ */
z(e,Y=Z<Y)                 /*\` */
z(J,Y=M[Z*80+Y])           /* g */
z(j,M[Z*80+Z]=s[-2];Z)     /* p */
z(D,x=1)                   /* v */
z(v,Z?U():D())             /* | */
z(l,*++s=getchar())        /* ~ */
F();                       /* ? */
(*f[])()={[33]=b,G,k,H,E,K,
          [42]=B,A,i,a,I,d,
          [58]=g,0,L,0,R,F,
          [92]=w,0,U,h,e,
          ['g']=J,['p']=j,
          ['v']=D,['|']=v,0,l}
z(F,f["><^v"[rand()&3]]()) /* ? */
main(C,V)int**V;{
 /* load */
 for(t=open(V[1],!memset(M,32,2000));read(t,&C,1);)
  C-10?M[y*80+x++]=C:(x=!++y);
 /* execute */
 for(R();m|t-64;m?t-34?*++s=t:(m=0):t>47&t<58?*++s=t-48:f[t]&&f[t]())
  k(),
  t=M[(r=(r+25)%25)*80+(c=(c+80)%80)];
}

```

Edit: Improved test coverage and fixed bugs. Test suite largely lifted from esolang-park

# Answer
> 5 votes
## Delphi, 970 842

Since I did the Fish golf first, I just copied that and changed the interpretation to use Befunge-93 specs (which are simpler than Fish) so I mainly had to strip things away.

In the next revision I won 64 characters by implementing the movement code using 2 instead of 4 variables. Oh, and I inverted the stack, removing the need for a length variable. Another nice win is the '?' (random direction) instruction - I just change it into one of the four directions and let them handle it.

```
const X=80;var f:TextFile;c,s:String;i,p,d,A:Int16;procedure U(v:Int8);begin s:=Chr(v)+s;end;function O:Int8;begin if s=''then Exit(0);O:=Ord(s[1]);Delete(s,1,1)end;procedure E;begin i:=(p div X)+(d div X);p:=i*X+(p+d)mod X;i:=Ord(c[1+p])end;begin Assign(f,ParamStr(1));Reset(f);for A:=1to 26do begin ReadLn(f,s);c:=c+s+StringOfChar(' ',X-Length(s))end;d:=1;p:=-d;repeat E;A:=i;case i-32of1,63,92:A:=Ord(O=0);2:repeat E;U(i)until i=A;5,15,26,60:A:=O;31:i:=Ord('<>^v'[1+Random(4)]);71,80:A:=X*O+O+1;6:Read(A);94:Read(PChar(@A)^)end;if i=58then U(A);case i-32of 16..25:U(i-48);11:U(O+O);13:U(-O+O);10:U(O*O);15:U(O div A);5:U(O mod A);64:U(Ord(O<O));28,30:d:=i-61;62:d:=-X;86:d:=X;63:d:=2*A-1;92:d:=2*A*X-X;2,4:O;60:s:=Chr(O)+Chr(A)+s;14:Write(O,' ');12:Write(Chr(O));3:E;80:c[A]:=Chr(O);71:U(Ord(c[A]));32:Exit;1,6,26,94:U(A)end;until 0=1;end.

```

Here the indented and commented code :

```
{debug}uses Windows;{}
const
  X=80;
var
  // f is the source file
  f:TextFile;
  // c is the entire codebox (a 2-dimensional program)
  c,
  // s is the stack (kept as a string)
  s:String;
  // i is the current instruction read from the program
  i,
  // p is the position in the program
  p,
  // d is the delta for each step
  d,
  // A is a temporary variable (only uppercase var, to coincide with comments)
  A
  :Int16;

procedure U(v:Int8); // PUSH
begin
  // Push value onto the stack:
  s:=Chr(v)+s;
end;

function O:Int8; // POP
begin
  // Pop value from the stack :
  if s=''then Exit(0);
  O:=Ord(s[1]);
  Delete(s,1,1)
end;

procedure E; // STEP
begin
//{debug}Sleep(3);{}
  // Note : x-step needs to stay on same line, y-step needs to stay on same column
  i:=(p div X)+(d div X);
//  i:=i mod 25;// Enable this to wrap y-edge too
  p:=i*X+(p+d)mod X;
  i:=Ord(c[1+p])
end;

begin
  // Open file given at the command-line, and read & expand it's lines into our program buffer :
  Assign(f,ParamStr(1));
  Reset(f);
  for A:=1to 26do
  begin
    ReadLn(f,s);
    c:=c+s+StringOfChar(' ',X-Length(s))
    {debug};SetLength(c,A*X)
  end;
  // s:=''; Since we read 1 line too many above, s should always be empty now
  d:=1;
  p:=-d;
  repeat
    // Take a step (which gives a new 'i'nstruction) and make a copy of the stack :
    E;

    // Prevent begin+end pairs by handling instructions in 3 consecutive case blocks; This is applied to
    // all situations where this saves 1 or more characters, justifying the cost for another case-block.

    // Shorten '"' (>2) string-collecting, by remembering the quote character in A :
    A:=i;

    // Shorten a few cases by preparing variables so they can be shared with eachother and the 3rd case-block below :
    case i-32of // Note : The instruction is decreased by 32, resulting in less digits in the cases below!
      // Shorten '!' (>1), '_' (>63) and '|' (>92), by remembering Ord(O=0) in A :
      1,63,92:A:=Ord(O=0);
      // Shorten '"' string-collecting, by pushing the entire string here (the opening quote was remembered in A) :
      2:repeat E;U(i)until i=A; // Note :  We stop at the closing character, so the next block will still handle 'i'!
      // These instructions all need to Pop A, so write it just once here :
      5,15,26,60:A:=O;
      // Shorten '?' (>31): Choose a random direction instruction and let the 3rd case-block handle it :
      31:i:=Ord('<>^v'[1+Random(4)]);
      // Shorten 'g' (>71) and 'p' (>80): Calculate A so that the 3rd case-block doesn't need a begin+end pair :
      71,80:A:=X*O+O+1; // Note : This assumes Delphi evaluates leftmost call to O first!
      // Shorten '&' by reading a number from the input into A :
      6:Read(A);
      // Shorten '!' Prevent begin+end for input retrieval, by reading the input into A here :
      94:Read(PChar(@A)^) // Note : This case is last, because it ends on ')', which avoids a closing ';'
    end;

    // Shorten ':' (>58-32=26): Share implementation with '&' (>6) and '~' (>94) by pushing first copy of A (read above) here
    if i=58then U(A);

    // This 3rd case-block contains the final code for all statements :
    case i-32of // Note : The instruction is decreased by 32, resulting in less digits in the cases below!
      //'0'..'9': Push this number on the stack
      16..25:U(i-48);
      //'+': Addition: Pop A then B, push A+B
      11:U(O+O); // Note : A and B are inverted, but order is irrelevant here
      //'-': Subtraction: Pop A then B, push B-A
      13:U(-O+O); // Note : Delphi evaluates left-to-right, so we need to reverse the operation
      //'*': Multiplication: Pop a then b, push a*b
      10:U(O*O); // Note : A and B are inverted, but order is irrelevant here
      //'/': Integer division: Pop A then B, push B/A, rounded down. If A is 0, result is undefined
      15:U(O div A); // if A=0then U(0)else U(O mod A);
      //'%': Modulo: Pop A then B, push the remainder of the integer division of B/A. If a is 0, result is undefined
       5:U(O mod A); // if A=0then U(0)else U(O mod A);
      //'`': Greater than: Pop A then B, push 1 if B>A, otherwise 0.
      64:U(Ord(O<O)); // Note : Delphi evaluates left-to-right, so we need to reverse the test
      //'<': Start moving left
      //'>': Start moving right
      28,30:d:=i-61;
      //'^': Start moving up
      62:d:=-X;
      //'v': Start moving down
      86:d:=X;
      //'_': Pop a value; move right if value=0, left otherwise
      63:d:=2*A-1; // Note : A is already determined as Ord(O=0) in 1st case block
      //'|': Pop a value; move down if value=0, up otherwise
      92:d:=2*A*X-X; // Note : A is already determined as Ord(O=0) in 1st case block
      //'"': Start string mode: push each character's ASCII value all the way up to the next "
      //'$': Pop value from the stack
      2,4:O;
      //'\': Swap two values on top of the stack
      60:s:=Chr(O)+Chr(A)+s; // Note : A was Popped in 1st case block
      //'.': Pop value and output as an integer
      14:Write(O,' ');
      //',': Pop value and output as ASCII character
      12:Write(Chr(O));
      //'#': Trampoline: Skip next cell
      3:E;
      //'p': A "put" call (a way to store a value for later use). Pop y then x then v, change the character at the position (x,y) in the program to the character with ASCII value v
      80:c[A]:=Chr(O); // Note : A was Popped in 1st and 2nd case block, calculating y*width+x
      //'g': A "get" call (a way to retrieve data in storage). Pop y then x, push ASCII value of the character at that position in the program
      71:U(Ord(c[A])); // Note : A was Popped in 1st and 2nd case block, calculating y*width+x
      //'@': Rotates the top 3 values on the stack clockwise, respectively. (eg. if your stack is 1,2,3,4, would result in 1,4,2,3)
      32:Exit;
      //'!': Logical NOT: Pop a value. If the value is 0, push 1; otherwise, push 0.
      //'&':  Input a number from stdin and push its value
      //':': Duplicate value on top of the stack
      //'~':  Input a single character from stdin and push its ASCII value
      1,      // Note for '!' : A is already determined as Ord(O=0) in 1st case block
      6,
      26,     // Note for ':' : First A was already pushed once above
      94:U(A) // Note for '~' : Read() into A was done in 1st case block
    end;
  until 0=1;
end.

```

Output from compat.bf :

```
OOB get returns 0
Cells are unsigned 8 bit
Edge jumps work
Negative remainders work
@ in stringmode works

```

Output from b93 :

```
` works
: works
0-9 probably work
$ works
Westwards edge jump arrives at 79
0! is 1
5! is 0

```

Edit history:

(970-64=906) : Reimplemented movement, using 2 instead of 4 variables

(906-9=897) : Moved more calculations into 1st and 2nd case-blocks

(897-11=886) : Skip intermediate variable for all double-pop instructions

(886-6=880) : Read 1 input line extra to clear 's'tack

(880-14=866) : Simplified '?' by changing it into one of the 4 direction-instructions

(866-8=858) : Removed one case block

(858-13=845) : Fixed edge-jump, simplifying direction handling. Use 8 bit stack.

(845-3=842) : Combined left-right direction instruction into a single expression

---
Tags: code-golf, interpreter, stack, befunge
---