AoCG2021 Day 17: Langton's Hexa-Virus

Question

The story continues from AoC2017 Day 22, Part 2.

The damn virus that was infecting a grid computing cluster now has jumped to a hexagonal computing cluster! In this cluster, the computers are connected in the honeycomb-like shape, and each computer has three neighbors.

 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  .x  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  ..

Initially, the cluster is completely clean, and the virus is at x, facing east. At each tick, the virus moves in the following manner:

If the current computer is clean, infect it, turn left (60 degrees), and move forward once (move to the neighboring computer in that direction).
Otherwise (the current computer is infected), clean it, turn right, and move forward once.

Some initial iterations look like this (generated using this program; . is clean, * is infected, x is the virus at a clean computer, and X is the virus at an infected one):

 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  .x  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  x.  .
 ..  .*  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  .x  .. 
.  ..  *.  .
 ..  .*  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  x*  .. 
.  ..  *.  .
 ..  .*  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .x  *.  .
 ..  .*  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *.  .
 ..  x*  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *.  .
 ..  *X  .. 
.  ..  ..  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *.  .
 ..  *.  .. 
.  ..  x.  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *.  .
 ..  *.  .. 
.  ..  *x  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *.  .
 ..  *.  x. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  *x  .
 ..  *.  *. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  **  .. 
.  .*  X*  .
 ..  *.  *. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  ..  .
 ..  *X  .. 
.  .*  .*  .
 ..  *.  *. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  ..  .. 
.  ..  x.  .
 ..  *.  .. 
.  .*  .*  .
 ..  *.  *. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  .. 

 ..  .x  .. 
.  ..  *.  .
 ..  *.  .. 
.  .*  .*  .
 ..  *.  *. 
.  ..  **  .
 ..  ..  .. 
.  ..  ..  .
 ..  ..  ..

A better visualization can be seen here (pdf).

The number of infected computers at each iteration is A269757:

0, 1, 2, 3, 4, 5, 6, 5, 6, 7,
8, 9, 8, 7, 8, 9, 10, 11, 10, 9,
10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
18, 17, 16, 17, 18, 19, 20, 19, 18, 19,
20, 21, 22, 21, 20, 19, 18, 19, 20, 21,
22, 21, 20, 21, 22, 23, 24, 23, 22, 21,
20, 21, 22, 23, 24, 23, 22, 23, 24, 25, 26, ...

Your task is to output the sequence. Standard code-golf rules and sequence I/O methods apply. (0-based and 1-based indexing allowed.) The shortest code in bytes wins.

tsh · Accepted Answer · 2021-12-19 05:23:54Z

JavaScript (Node.js), 67 bytes

n=>(g=d=>n--?g(d+(g[t=d*2/3&3,[x+=--t%2,y+=--t%2]]^=2)-1):d)(x=y=0)

Try it online!

Remove all spaces from OP's example, we got:

......
......
......
......
...x..
......
......
......
......

......
......
......
...x..
...*..
......
......
......
......

......
......
...x..
...*..
...*..
......
......
......
......

......
......
..x*..
...*..
...*..
......
......
......
......

......
......
..**..
..x*..
...*..
......
......
......
......

......
......
..**..
..**..
..x*..
......
......
......
......

......
......
..**..
..**..
..*X..
......
......
......
......

......
......
..**..
..**..
..*...
...x..
......
......
......

......
......
..**..
..**..
..*...
...*x.
......
......
......

......
......
..**..
..**..
..*.x.
...**.
......
......
......

......
......
..**..
..**x.
..*.*.
...**.
......
......
......

......
......
..**..
..*X*.
..*.*.
...**.
......
......
......

......
......
..*X..
..*.*.
..*.*.
...**.
......
......
......

......
...x..
..*...
..*.*.
..*.*.
...**.
......
......
......

...x..
...*..
..*...
..*.*.
..*.*.
...**.
......
......
......

And you will find out the pattern: "Up, Up, Left, Down, Down, Right". That's how \$ \lfloor \frac{2}{3}\cdot d \rfloor \$ comes.

loopy walt · Accepted Answer · 2021-12-17 21:05:13Z

6

Python 3, 79, 74 (@xnor), 61 bytes (@tsh)

x={0}
p=c=0
while[print(c)]:c=len(x);p+=1j**(c*2//3&3);x^={p}

Try it online!

Older versions

x={2}
p=c=0
while[print(c)]:x^={p};c+=x>{p}or-1;p+=1j**(c*2//3)*(1j-c%3%2)

Try it online!

x={*()}
p=c=0
while[print(c)]:x^={p};c+=(x>={p})or-1;p+=1j**(c*2//3)*(1j-c%3%2)

Try it online!

set x holds points infected, p is current position and c is current infection count. Note that current heading needn't be tracked because it can be inferred from c%6.

Coordinates are complex numbers. It would be desirable to base them on actual geometry but that has numerical problems. ~~Which is why we use integer coordinates, i.e. an orthogonal grid with only one diagonal direction connected.~~ Instead, we deform the grid by "squeezing out" the unreachable hexagon centres resulting in a square grid (with some connections missing), see picture: hat tip to @tsh for that.

edited Dec 17, 2021 at 21:05

answered Dec 17, 2021 at 3:10

loopy walt

16k2 gold badges10 silver badges65 bronze badges

1

\$\begingroup\$ You can cut the parens around x>={p}. For initializing the set x, it looks like it's fine if starts with some element like x={()}; maybe x={0} could be made to work with rearranging the loop. \$\endgroup\$
– xnor
Dec 17, 2021 at 3:56
\$\begingroup\$ Thx, @xnor. Actually, 2 is unreachable and also allows us to drop the = from >=. \$\endgroup\$
– loopy walt
Dec 17, 2021 at 4:10
\$\begingroup\$ I didn't understand your formula. But maybe x=set() p=c=0 while[print(c)]:x^={p};c=len(x);p+=1j**(c*2//3)*(1j-c%3%2) is 72 bytes. \$\endgroup\$
– tsh
Dec 17, 2021 at 5:56
\$\begingroup\$ Using my formula in my JS post would be 66 bytes: x=set();p=0 while[print(len(x))]:x^={p};p+=1j**(233>>len(x)%6*2&3). &3 is not optional due to floating point errors. \$\endgroup\$
– tsh
Dec 17, 2021 at 6:24
\$\begingroup\$ @tsh at long last I understand what you are doing! But can't you simplify to 1j**(len(x)*2//3&3)? \$\endgroup\$
– loopy walt
Dec 17, 2021 at 7:14

| Show 4 more comments

Neil · Accepted Answer · 2021-12-17 10:22:50Z

Charcoal, 34 28 bytes

ＦＮ«⊞υＬＫＡＰ⎇℅ＫＫψ*Ｍ✳÷×⁴ＬＫＡ³»⎚Ｉυ

Try it online! Link is to verbose version of code. Outputs the first n members of the sequence. Edit: Saved 6 bytes using @loopywait's observation that the direction can be inferred from the infection count. Explanation:

ＦＮ«

Input n and loop that many times.

⊞υＬＫＡ

Save the number of infected computers at this step.

Ｐ⎇℅ＫＫψ*

Flip the current computer between uninfected and infected.

Ｍ✳÷×⁴ＬＫＡ³

Move in a hexagonal pattern on an octagonal grid, based on the number of infected computers. Note that the exact orientation of the grid is not significant, so north west and south east are actually represented by north and south.

»⎚Ｉυ

Output the gathered list of infected computer counts.

Here's a version that you can run locally to animate the progress of infection (the virus itself is not shown):

ＲＦφφ«Ｐ⎇℅ＫＫψ*Ｍ✳÷⊕×⁴ＬＫＡ³

Outputs the first 1,000 steps (the first φ is the animation speed, the second the number of steps). Replace the Ｆ with Ｗ if you want the program to run indefinitely. The extra ⊕ skews north and south back to north west and south east.

\$\begingroup\$ Right tool for the job :) \$\endgroup\$
– Bubbler
Dec 17, 2021 at 1:00 — Bubbler, Dec 17, 2021 at 1:00

G B · Accepted Answer · 2021-12-17 07:49:04Z

2

Ruby, 82 ... 56 bytes

a,*r=c=0;loop{p c+=(r!=r-=[a+=1i**(c*2/3)])?-1:(r<<a;1)}

Try it online!

Saved a lot of bytes by stealing tsh's formula.

edited Dec 17, 2021 at 7:49

answered Dec 17, 2021 at 7:19

G B

21.3k1 gold badge19 silver badges51 bronze badges

\$\begingroup\$ I just tried to remove the &3 in your program, and looks like it still works. Maybe Ruby will not introduce floating point errors in 1i**n where n is positive integer. \$\endgroup\$
– tsh
Dec 17, 2021 at 7:46
\$\begingroup\$ @tsh I was trying that too, I don't understand why it doesn't work in python. Or maybe it does? \$\endgroup\$
– G B
Dec 17, 2021 at 7:48
\$\begingroup\$ Either that or the test cases are not big enough. In Python, you need n>100 for the error to show up. EDIT Wait, there are no test cases...nvm \$\endgroup\$
– loopy walt
Dec 17, 2021 at 7:53
\$\begingroup\$ @tsh I think so, I tested with 100000 iterations and it still holds: Try it online! \$\endgroup\$
– G B
Dec 17, 2021 at 7:57

Add a comment |

alephalpha · Accepted Answer · 2022-01-29 06:53:35Z

2

Pari/GP, 78 bytes

n->for(i=!p=#a=Map(),n,iferr(mapdelete(a,p),e,mapput(a,p,1));p+=I^(#a*2\3));#a

Try it online!

A port of @tsh's JavaScript answer.

edited Jan 29, 2022 at 6:53

answered Dec 17, 2021 at 1:15

alephalpha

46.6k7 gold badges61 silver badges172 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2022-06-24 01:33:59Z

2

Python script in Golly, 179 bytes

from golly import*
new("")
setrule("TriTurmite_120010")
setcell(0,0,2)
run(int(getstring("")))
a=[0,1,0,0,0,1,1,1]
show(str(sum(a[c%8]+a[c//8]for c in getcells(getrect())[2::3])))

Triangular Langton's ant is a built-in rule in Golly. But it simulates the triangular grid in a nontrivial way: two triangular cells are represented by one square cell. So I cannot simply use the getpop built-in.

Screenshot for input 1000. Output is 106:

edited Jun 24, 2022 at 1:33

answered Dec 17, 2021 at 3:49

alephalpha

46.6k7 gold badges61 silver badges172 bronze badges

Add a comment |

tjjfvi · Accepted Answer · 2021-12-17 18:19:39Z

TypeScript Types, 317 bytes

//@ts-ignore
type I<T,P=0,N=[1,0][P]>=T extends[N,...infer T]?T:[...T,P];type M<N,a=[[],[]],b=0,c=0,d=[],e=0,f=[],g=[1,0][c],h=a[0],i=a[1],j=[[I<h,c>,I<i,g>],[h,I<i,c>],[I<h,g>,i]][b]>=N extends d["length"]?f["length"]:j extends e?M<N,j,[1,2,0][b],g,[...d,0],Exclude<e,j>,I<f,1>>:M<N,j,[2,0,1][b],g,[...d,0],e|j,I<f>>

Try It Online!

Ungolfed / Explanation

// Increment/decrement an integer stored as e.g. [0, 0] for 2, [1, 1, 1] for -3, and [] for 0
// Invoked as Inc<T> to increment, or Inc<T, 1> to decrement
type Inc<T, Pos = 0, Neg = [1, 0][Pos]> = T extends [Neg, ...infer T] ? T : [...T, Pos]

type Main<
  // The goal number of steps
  N,
  // Last position; stored using axial coordinates as two integers
  LastPos = [[], []],
  // The current axis; 0 | 1 | 2
  DirAxis = 0,
  // The current direction on the axis; 0 | 1
  DirSign = 0,
  // The number of steps taken so far
  Steps = [],
  // A union of all infected positions
  Infected = 0,
  // A tuple counting how many positions are infected
  InfectedCount = [],
  // The sign opposite DirSign
  OtherSign = [1, 0][DirSign],
  // Calculate the new position based on LastPos, DirAxis, and DirSign
  LastPos0 = LastPos[0],
  LastPos1 = LastPos[1],
  NewPos = [
    [Inc<LastPos0, DirSign>, Inc<LastPos1, OtherSign>],
    [LastPos0, Inc<LastPos1, DirSign>],
    [Inc<LastPos0, OtherSign>, LastPos1]
  ][DirAxis]
> =
  N extends Steps["length"]
    // If N == Steps, return InfectedCount
    ? InfectedCount["length"]
    // Otherwise,
    : NewPos extends Infected
      // If NewPos is in Infected,
      ? Main<
        N,
        NewPos,
        // Cycle DirAxis to the right
        [1, 2, 0][DirAxis],
        // Set DirSign to OtherSign
        OtherSign,
        // Add one to Steps
        [...Steps, 0],
        // Remove NewPos from Infected
        Exclude<Infected, NewPos>,
        // Decrement InfectedCount
        Inc<InfectedCount, 1>
      >
      // Otherwise,
      : Main<
        N,
        NewPos,
        // Cycle DirAxis to the left
        [2, 0, 1][DirAxis],
        // Set DirSign to OtherSign
        OtherSign,
        [...Steps, 0],
        // Add NewPos to Infected
        Infected | NewPos,
        // Increment InfectedCount
        Inc<InfectedCount>
      >

Ezhik · Accepted Answer · 2021-12-18 09:33:58Z

1

Rust, 144 bytes

let(mut x,mut p,mut c)=(vec![],[0,0],0);loop{print!("{}
",c);x.retain(|q|q!=&p);if c==x.len(){x.push(p)}c=x.len();p[c*2/3&1]+=1-2*(c/3&1)as i64}

Try it online!

Port of @loopy walt's algorithm.

answered Dec 18, 2021 at 9:33

Ezhik

7832 silver badges3 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2022-01-29 06:56:56Z

1

Wolfram Language (Mathematica), 58 bytes

(Clear@a;c=p=0;a@_=-1;Do[p+=I^⌊2/3(c+=a@p*=-1)⌋,#];c)&

Try it online!

A port of @tsh's JavaScript answer.

edited Jan 29, 2022 at 6:56

answered Dec 20, 2021 at 1:36

alephalpha

46.6k7 gold badges61 silver badges172 bronze badges

Add a comment |

Stack Exchange Network

AoCG2021 Day 17: Langton's Hexa-Virus

9 Answers 9

JavaScript (Node.js), 67 bytes

Python 3, 79, 74 (@xnor), 61 bytes (@tsh)

Older versions

Charcoal, 34 28 bytes

Ruby, 82 ... 56 bytes

Pari/GP, 78 bytes

Python script in Golly, 179 bytes

TypeScript Types, 317 bytes

Ungolfed / Explanation

Rust, 144 bytes

Wolfram Language (Mathematica), 58 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
hexagonal-grid
or ask your own question.

Hot Network Questions

AoCG2021 Day 17: Langton's Hexa-Virus

9 Answers 9

JavaScript (Node.js), 67 bytes

Python 3, 79, 74 (@xnor), 61 bytes (@tsh)

Older versions

Charcoal, 34 28 bytes

Ruby, 82 ... 56 bytes

Pari/GP, 78 bytes

Python script in Golly, 179 bytes

TypeScript Types, 317 bytes

Ungolfed / Explanation

Rust, 144 bytes

Wolfram Language (Mathematica), 58 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
hexagonal-grid
or ask your own question.