37
\$\begingroup\$

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
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Are we guaranteed that the input will always lead to a collision before we get to 100? \$\endgroup\$ Nov 7, 2016 at 10:22
  • \$\begingroup\$ Yes. More generally, so long as your code works for the provided test cases you're good to go. \$\endgroup\$
    – H Walters
    Nov 7, 2016 at 10:43
  • 1
    \$\begingroup\$ Is there a specific place you (the turtle) starts? \$\endgroup\$
    – user41805
    Nov 7, 2016 at 11:31
  • \$\begingroup\$ @KritixiLithos No. The left/top/right/bottom of the grid are defined by how the turtle travels, which depends on f and b. \$\endgroup\$
    – H Walters
    Nov 7, 2016 at 15:29
  • 1
    \$\begingroup\$ @Dave If f=b you go on forever. Otherwise you would always collide. (Furthermore, unless f=b, you have at most 4*f*b steps before you collide with your path). \$\endgroup\$
    – H Walters
    Aug 25, 2017 at 8:11

8 Answers 8

5
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Heh, those N,4N patterns are pretty cool. \$\endgroup\$
    – steenbergh
    Nov 7, 2016 at 12:08
  • \$\begingroup\$ 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 \$\endgroup\$ Nov 7, 2016 at 12:15
  • \$\begingroup\$ 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? \$\endgroup\$
    – Copper
    Nov 7, 2016 at 12:17
  • \$\begingroup\$ p[(x,y)] => p[x,y] (not sure if it works in Python 2, though) \$\endgroup\$
    – shooqie
    Nov 8, 2016 at 11:02
4
\$\begingroup\$

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!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ If 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. \$\endgroup\$
    – Neil
    Nov 7, 2016 at 12:57
  • \$\begingroup\$ 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 \$\endgroup\$
    – Karl Napf
    Nov 7, 2016 at 14:30
  • 1
    \$\begingroup\$ @KarlNapf Fixed. \$\endgroup\$
    – steenbergh
    Nov 7, 2016 at 19:13
3
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

C, 305 Bytes

Thanks to @ceilingcat for finding a much better (and shorter) version

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

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);}
\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat. Thanks for that. You are really good at this. I don't think I have one answer that hasn't been made shorter with your magic. \$\endgroup\$ Jun 13, 2020 at 8:17
1
\$\begingroup\$

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>

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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