Fizz Buzz for Turtles

36

4

Problem Description

Imagine you're a turtle on a grid. You're given two numbers f and b, and you're facing east. You perform a march across the grid, counting each of the cells you encounter, according to the following rules:

  • By default, you write the count to the cell you're in, then walk forward.
  • If the count is divisible by f, you write F to the cell you're in, then turn right, then walk forward.
  • If the count is divisible by b, you write B to the cell you're in, then turn left, then walk forward.
  • If the count is divisible by both f and b, you write FB to the cell you're in, then walk forward.
  • If you reach a square you've already been to, you stop.

For example, following these rules using f = 3 and b = 5 will generate a pattern like this:

    F 28 29 FB  1  2  F
   26                 4
 F  B                 B  F
23                       7
22                       8
 F  B                 B  F
   19                11
    F 17 16 FB 14 13  F

The challenge

Write a program or function that accepts two numbers as input, corresponding to f and b, and produces as output the pattern for these numbers given by the rules above.

Formatting requirements:

  • Each cell is two characters wide
  • Cell contents are right aligned within these two characters
  • Cells on the same row are delimited by a space
  • The first column of cells must contain a non-empty cell
  • All rows must contain non-empty cells
  • Trailing whitespace is not required, but allowed
  • However, the total width of each row must not exceed 3 times the number of non-empty columns

Your code must work for provided test cases.

Standard loopholes are disallowed.

This is code golf; shortest answer in bytes wins.

Test cases

(f=3, b=5 case repeated here as a courtesy convenience).

f=3, b=5 ->
    F 28 29 FB  1  2  F
   26                 4
 F  B                 B  F
23                       7
22                       8
 F  B                 B  F
   19                11
    F 17 16 FB 14 13  F

f=4, b=10 ->
 F 25 26 27  F
23          29
22        1  2  3  F
21                 5
FB                 6
19                 7
18           B  9  F
17          11
 F 15 14 13  F

f=3, b=11 ->
 F 16 17  F
14       19
13     1  2  F
 F  B        4
   10        5
    F  8  7  F

f=5, b=9 ->
    F 41 42 43 44  1  2  3  4  F
   39                          6
   38                          7
   37                          8
 F  B                          B  F
34                               11
33                               12
32                               13
31                               14
 F 29 28  B              B 17 16  F
         26             19
          F 24 23 22 21  F

f=5, b=13 ->
    F 31 32 33 34  F
   29             36
   28        1  2  3  4  F
   27                    6
 F  B                    7
24                       8
23                       9
22              B 12 11  F
21             14
 F 19 18 17 16  F

H Walters

Posted 2016-11-07T02:21:58.600

Reputation: 1 536

1Are we guaranteed that the input will always lead to a collision before we get to 100? – Martin Ender – 2016-11-07T10:22:25.970

Yes. More generally, so long as your code works for the provided test cases you're good to go. – H Walters – 2016-11-07T10:43:13.447

1Is there a specific place you (the turtle) starts? – user41805 – 2016-11-07T11:31:47.000

@KritixiLithos No. The left/top/right/bottom of the grid are defined by how the turtle travels, which depends on f and b. – H Walters – 2016-11-07T15:29:48.860

Are f and b always integers? – corvus_192 – 2016-11-07T16:37:05.300

@corvus_192 Yes. – H Walters – 2016-11-07T16:47:23.773

Out of curiosity, is there an easy way to tell whether some pair f,b will lead to a collision? Will they all at some point? – Dave – 2017-08-24T14:08:38.050

@Dave If f=b you go on forever. Otherwise you would always collide. (Furthermore, unless f=b, you have at most 4fb steps before you collide with your path). – H Walters – 2017-08-25T08:11:19.080

Answers

1

JavaScript (ES6), 230 240

(f,b)=>(d=>{for(g=[s=x=y=d];!(r=g[y]=g[y]||[])[x];d&1?d&2?y?--y:g=[,...g]:++y:d&2?x?--x:g=g.map(r=>[,...r]):++x)o=++s%f?'':(++d,'F'),s%b||(--d,o+='B'),r[x]=o||s})(0)||g.map(r=>[...r].map(c=>` ${c||' '}`.slice(-2)).join` `).join`
`

Less golfed

(f,b)=>{
  for(g=[s=x=y=d=0]; !(r = g[y]= g[y]||[])[x]; )
  {
    o=++s%f?'':(++d,'F')
    s%b||(--d,o+='B')
    r[x]=o||s,
    d&1
      ? d&2 ? y ? --y : g=[,...g] : ++y
      : d&2 ? x ? --x : g=g.map(r=>[,...r]) : ++x
  }
  return g.map(r=>[...r].map(c=>` ${c||' '}`.slice(-2)).join` `)
          .join`\n`
}

Test

F=
(f,b)=>(d=>{for(g=[s=x=y=d];!(r=g[y]=g[y]||[])[x];d&1?d&2?y?--y:g=[,...g]:++y:d&2?x?--x:g=g.map(r=>[,...r]):++x)o=++s%f?'':(++d,'F'),s%b||(--d,o+='B'),r[x]=o||s})(0)||g.map(r=>[...r].map(c=>` ${c||' '}`.slice(-2)).join` `).join`
`


function update()
{
  var i = I.value.match(/\d+/g)||[],f=+i[0],b=+i[1]
  O.textContent = (f>0 & b>0) ? F(f,b) : ''
}  

update()
<input id=I value="3 5" oninput="update()">
<pre id=O></pre>

edc65

Posted 2016-11-07T02:21:58.600

Reputation: 31 086

5

Python 2, 379 338 326 bytes

Takes input as two numbers, separated by a comma. Eg. 4,5 or (4,5)

d=x=y=i=q=Q=e=E=0
p={}
f,b=input()
while(x,y)not in p:
 i+=1;l,r=i%b<1,i%f<1;d=(d+r-l)%4;p[x,y]=[[`i`,'F'][r],' F'[r]+'B'][l].rjust(2);q=min(q,x);Q=max(Q,x);e=min(e,y);E=max(E,y)
 if d%2:x+=(d==1)*2-1
 else:y+=(d!=2)*2-1
h,w=E-e+1,Q-q+1
A=[h*['  ']for x in' '*w]
for x,y in p:A[x-q][y-e]=p[x,y]
print'\n'.join(map(' '.join,A))

Version that works if path is longer than 99, 384 343 330 bytes

Shows 2 significant digits.

d=x=y=i=q=Q=e=E=0
p={}
f,b=input()
while(x,y)not in p:
 i+=1;l,r=i%b<1,i%f<1;d=(d+r-l)%4;p[x,y]=[[`i%100`,'F'][r],' F'[r]+'B'][l].rjust(2);q=min(q,x);Q=max(Q,x);e=min(e,y);E=max(E,y)
 if d%2:x+=(d==1)*2-1
 else:y+=(d!=2)*2-1
h,w=E-e+1,Q-q+1
A=[h*['  ']for x in' '*w]
for x,y in p:A[x-q][y-e]=p[x,y]
print'\n'.join(map(' '.join,A))

Examples:

input=(4,16)

 F 21 22 23  F
19          25
18          26
17          27
FB  1  2  3  F
15           5
14           6
13           7
 F 11 10  9  F

input=(6,7) (truncating version)

                                              F 63 64 65 66 67 FB  1  2  3  4  5  F                                             
                               F 57 58 59 60  B                                   B  8  9 10 11  F                              
                              55                                                                13                              
                   F 51 52 53  B                                                                 B 15 16 17  F                  
                  49                                                                                        19                  
                  48                                                                                        20                  
          F 45 46  B                                                                                         B 22 23  F         
         43                                                                                                          25         
         42                                                                                                          26         
         41                                                                                                          27         
    F 39  B                                                                                                           B 29  F   
   37                                                                                                                      31   
   36                                                                                                                      32   
   35                                                                                                                      33   
   34                                                                                                                      34   
 F  B                                                                                                                       B  F
31                                                                                                                            37
30                                                                                                                            38
29                                                                                                                            39
28                                                                                                                            40
27                                                                                                                            41
FB                                                                                                                            FB
25                                                                                                                            43
24                                                                                                                            44
23                                                                                                                            45
22                                                                                                                            46
21                                                                                                                            47
 F  B                                                                                                                       B  F
   18                                                                                                                      50   
   17                                                                                                                      51   
   16                                                                                                                      52   
   15                                                                                                                      53   
    F 13  B                                                                                                           B 55  F   
         11                                                                                                          57         
         10                                                                                                          58         
         09                                                                                                          59         
          F 07 06  B                                                                                         B 62 61  F         
                  04                                                                                        64                  
                  03                                                                                        65                  
                   F 01 00 99  B                                                                 B 69 68 67  F                  
                              97                                                                71                              
                               F 95 94 93 92  B                                   B 76 75 74 73  F                              
                                              F 89 88 87 86 85 FB 83 82 81 80 79  F

@Edit: Thanks to Jonathan Allan, Copper, and shooqie for savings me a bunch of bytes.

TFeld

Posted 2016-11-07T02:21:58.600

Reputation: 19 246

Heh, those N,4N patterns are pretty cool. – steenbergh – 2016-11-07T12:08:13.880

Good job. You can change while((x,y)not in p.keys()): to while(x,y)not in p: and for x,y in p.keys(): to for x,y in p. You can change l,r=i%b==0,i%f==0 to l,r=i%b<1,i%f<1 and d=(d+[0,1][r]-[0,1][l])%4 to d=(d+r-l)%4. You can change s=[[`i`,'F'][r],' F'[r]+'B'][l].rjust(2);p[(x,y)]=s to p[(x,y)]=[[`i`,'F'][r],' F'[r]+'B'][l].rjust(2). There may be more – Jonathan Allan – 2016-11-07T12:15:34.833

You can save a byte with h*[' ']for x in range instead of [' ']*h for x in range. Also, x+=[-1,1][d==1] can be replaced with x+=(d==1)*2-1, and y+=[1,-1][d==2] can be replaced with y+=(d!=2)*2-1. Also, is f,b=inputtt a typo? – Copper – 2016-11-07T12:17:19.420

p[(x,y)] => p[x,y] (not sure if it works in Python 2, though) – shooqie – 2016-11-08T11:02:35.483

4

Excel VBA, 347 421 bytes

New version, to deal with the whitespace-requirements. Not having this in my first version was an oversight n my part, but this takes its toll in the bytecount... It now cuts and pastes the used range to cell A1.

Sub t(f, b)
x=70:y=70:Do:s=s+ 1
If Cells(y,x).Value<>"" Then
ActiveSheet.UsedRange.Select:Selection.Cut:Range("A1").Select:ActiveSheet.Paste:Exit Sub
End If
If s Mod f=0 Then Cells(y,x).Value="F":q=q+1
If s Mod b=0 Then Cells(y,x).Value=Cells(y,x).Value & "B":q=q+3
If Cells(y,x).Value="" Then Cells(y,x).Value=s
Select Case q Mod 4
Case 0:x=x+1
Case 1:y=y+1
Case 2:x=x-1
Case 3:y=y-1
End Select:Loop:End Sub

Here's the old version that did not move the end result to A1

Sub t(f,b)
x=70:y=70:Do:s=s+1:if Cells(y,x).Value<>"" then exit sub
If s Mod f=0 Then
Cells(y,x).Value="F":q=q+1
End If
If s Mod b=0 Then
Cells(y,x).Value=Cells(y,x).Value & "B":q=q+3
End If
If Cells(y,x).Value="" Then Cells(y,x).Value=s
Select Case q mod 4
Case 0:x=x+1
Case 1:y=y+1
Case 2:x=x-1
Case 3:y=y-1
End Select:Loop:End Sub

Starts at 70, 70 (or BR70 in Excel) and walks around it. Function is called with the f and b as parameters: Call t(4, 16)

@Neil just saved me a bunch of bytes, thanks!

steenbergh

Posted 2016-11-07T02:21:58.600

Reputation: 7 772

1If you replace q=q-1 with q=q+3 and Select Case q with Select Case q Mod 4 then you can get rid of the preceding two statements. – Neil – 2016-11-07T12:57:42.920

However, the total width of each row must not exceed 3 times the number of non-empty columns I guess this was added to avoid just setup a big grid and start somewhat the away from the border – Karl Napf – 2016-11-07T14:30:32.057

1@KarlNapf Fixed. – steenbergh – 2016-11-07T19:13:18.553

3

Excel VBA, 284 278 277 261 259 255 254 253 251 Bytes

Subroutine that takes input as values, F, B and outputs to cells on the Sheets(1) Object (which is restricted to the Sheets(1) object to save 2 Bytes)

Sub G(F,B)
Set A=Sheet1
R=99:C=R
Do
I=I+1
Y=Cells(R,C)
If Y<>""Then A.UsedRange.Cut:[A1].Select:A.Paste:End
If I Mod F=0Then Y="F":J=J+1
If I Mod B=0Then Y=Y+"B":J=J+3
Cells(R,C)=IIf(Y="",i,Y)
K=J Mod 4
If K Mod 2Then R=R-K+2 Else C=C+1-K
Loop
End Sub

Usage:

Call G(3, 4)

Taylor Scott

Posted 2016-11-07T02:21:58.600

Reputation: 6 709

2

C, 349 Bytes

#define z strcpy(G[x][y],
char G[99][99][3];d=3,x=49,y=49,i=1,q,s=99,t,u=99,v;F(f,b){for(;!*G[x][y];i++){q=(!(i%f))<<1|!(i%b);q==3&&z"FB");if(q==2)z"F"),d=(d+3)%4;if(q==1)z"B"),d=(d+1)%4;!q&&sprintf(G[x][y],"%d",i);if(d%2)x+=d-2;else y+=d-1;s=s>x?x:s;t=t<x?x:t;u=u>y?y:u;v=v<y?y:v;}for(y=u;y<=v;puts(""),y++)for(x=s;x<=t;x++)printf("%2s ",G[x][y]);}

Try it online!

A slightly more indented version:

#define z strcpy(G[x][y],
char G[99][99][3];
d=3,x=49,y=49,i=1,q,s=99,t,u=99,v;

F(f,b)
{
    for(;!*G[x][y];i++)
    {
        q=(!(i%f))<<1|!(i%b);
        q==3&&z"FB");
        if(q==2)z"F"),d=(d+3)%4;
        if(q==1)z"B"),d=(d+1)%4;
        !q&&sprintf(G[x][y],"%d",i);
        if(d%2)x+=d-2;else y+=d-1;
        s=s>x?x:s;t=t<x?x:t;u=u>y?y:u;v=v<y?y:v;
    }
    for(y=u;y<=v;puts(""),y++)for(x=s;x<=t;x++)printf("%2s ",G[x][y]);
}

Here is a 364 byte version that handles numbers bigger than 100

#define g G[x][y]
#define z strcpy(g,
char G[99][99][9];d=3,x=49,y=49,i=1,q,s=99,t,u=99,v;F(f,b){for(;!*g;i++){q=(!(i%f))<<1|!(i%b);q==3&&z"FB");if(q==2)z" F"),d=(d+3)%4;if(q==1)z" B"),d=(d+1)%4;!q&&sprintf(G[x][y],"%2d",i);if(d%2)x+=d-2;else y+=d-1;s=s>x?x:s;t=t<x?x:t;u=u>y?y:u;v=v<y?y:v;}for(y=u;y<=v;puts(""),y++)for(x=s;x<=t;x++)printf("%2s ",g+strlen(g)-2);}

Jerry Jeremiah

Posted 2016-11-07T02:21:58.600

Reputation: 1 217

1

PHP, 292 bytes

for($x=$y=$u=$l=0;!$q[$x][$y];$s="") {
    ++$i%$argv[1]?:$a-=1+$s="F";
    $i%$argv[2]?:$a+=1+$s.="B";
    $q[$x][$y]=$s?:$i;
    $z=[1,-2,-1,2][$a=($a+4)%4];
    $y+=$z%2;
    $x+=~-$z%2;
    $u>$y?$u=$y:$d>$y?:$d=$y;
    $l>$x?$l=$x:$r>$x?:$r=$x;
}
for(;$l++<=$r;print"\n")for($j=$u-1;$j++<=$d;)echo str_pad($q[$l-1][$j],3," ",0);

Try it online!

Indents are for clarity, not counted.

Follows much the same algorithm as the Perl answer. Track where the turtle has been in a 2D array, $a tracks where the turtle is facing, and $u, $d, $l, $r track the boundaries for printing. str_pad allows us to ensure that each entry is exactly 3 spaces wide for the print formatting.

For some reason I can't fathom, PHP doesn't mind me not initializing half the variables to 0, but screws up the formatting if I don't initialize others, even though it usually treats uninitialized variables as 0 when they're first used. Hence the $x=$y=$u=$l=0 bit.

Xanderhall

Posted 2016-11-07T02:21:58.600

Reputation: 1 236

1

Perl, 275 bytes

Indentation is provided for readability and is not part of the code.

($f,$e)=@ARGV;
for($i=$x=1,$y=0;!$m{"$x,$y"};$i++){
    ($g,$m{"$x,$y"})=$i%$e&&$i%$f?($g,$i):$i%$f?($g+1,B):$i%$e?($g-1,F):($g,FB);
    ($g%=4)%2?($y+=$g-2):($x+=1-$g);
    ($a>$x?$a:$b<$x?$b:$x)=$x;
    ($c>$y?$c:$d<$y?$d:$y)=$y
}
for$k($c..$d){
    printf("%*s",1+length$i,$m{"$_,$k"})for$a..$b;
    say
}

Explanation:

The code works by keeping track of a hash of all places the turtle has been, and the appropriate value, stored in %m. For example: in 3 5, $m{0,2} contains 2, and $m{1,-3} = 26. It continues in this fashion until it reaches a place that has already been defined. Additionally, it keeps track of the current boundaries of the turtle's path, using $a,$b,$c,$d as maximums and minimums.

Once it reaches a place it has already been, it prints the path using the boundaries, everything padded with spaces.

There is no limit to the size of the path, nor the size of the numbers.

Gabriel Benamy

Posted 2016-11-07T02:21:58.600

Reputation: 2 827

0

Python 2, 267 262 258 249 245 243 bytes

f,b=input()
X=x=Y=y=i=p=0
g={}
S=sorted
while(p in g)<1:i+=1;g[p]='F'[i%f:]+'B'[i%b:]or`i`;p+=1j**(i/f-i/b);X,_,x=S([X,x,int(p.real)]);Y,_,y=S([Y,y,int(p.imag)])
j=Y
while j<=y:print' '.join(g.get(i+j*1j,'').rjust(2)for i in range(X,x+1));j+=1

Try it online!

Arfie

Posted 2016-11-07T02:21:58.600

Reputation: 1 230

Asked: 2016-11-07T02:21:58.600

Viewed: 1 087 times

Active: 2020-02-10T04:28:14.870