26
\$\begingroup\$

The world is a five by five array of cells. It wraps on all sides. It can be visualized like...

XXXXX
XXXXX
XXOXX
XXXXX
XXXXX

You are an O. You love to travel the world, and you do so according to the following rules (let C be the current day):

  • On prime days, you feel nostalgic. Return to where you started yesterday.
  • On odd days, you feel homesick. Move one horizontal step closer to home, if possible, and one vertical step closer to home, if possible. Ignore world wrapping for the purpose determining closeness.
  • On even days, you feel adventurous. Move C / 2 steps south.
  • On square days, you feel adventurous. Move to the east wall.
  • On Fibonacci days, the world expands southward by one row.
  • On triangular days, the world expands eastward by one column.

If two or more of the above rules would apply at the same time, apply them in the order listed. For example, on an odd prime day, first return to where you started yesterday, and then move one step closer to home.

You live at the center of the (initial) world, i.e. position (2,2), zero-indexed from the Northwest corner. You begin your journey there on day one.

Input

A single integer, N.

Output

Your X and Y coordinate on the Nth day, zero-indexed from the Northwest corner, separated by a single space.

Test Case With Explanation

Given an input of 3, the correct output is:

2 3

We can work through this one day at a time. Starting on day 1, we need to apply the following moves:

  1. Odd, square, Fibonacci, and triangular
  2. Prime, even, and Fibonacci
  3. Prime, odd, Fibonacci, and triangular

In visual form:

     Day 1       Day 2       Day 3
XXXXX      XXXXXX      XXXXXX      XXXXXXX
XXXXX      XXXXXX      XXXXXX      XXXXXXX
XXOXX  ->  XXXXOX  ->  XXXXXX  ->  XXXOXXX
XXXXX      XXXXXX      XXOXXX      XXXXXXX
XXXXX      XXXXXX      XXXXXX      XXXXXXX
           XXXXXX      XXXXXX      XXXXXXX
                       XXXXXX      XXXXXXX
                                   XXXXXXX

Additional Test Cases

Courtesy of Martin Büttner's reference solution (please note that you should output only a single coordinate, not all of them):

Input:  1     2     3     4     5     6     7     8     9     10    11    12    13    14     15    16    17    18    19    20    21    22    23
Output: 4 2   2 3   3 2   6 4   2 2   2 5   2 2   2 6   7 5   7 0   6 4   6 0   5 3   5 10   4 9   9 6   3 8   3 6   2 7   2 6   2 5   2 4   2 4

This is code golf. The shortest submission wins.

\$\endgroup\$
  • 6
    \$\begingroup\$ I need to do this in O! \$\endgroup\$ – kirbyfan64sos Nov 3 '15 at 16:50
4
\$\begingroup\$

Pyth, 157 156 153 bytes

=Z=b5aYA,2 2FNtUhQI&!tPN<1NA@Y_2)Iq*2/N2NA,G%+H/N2b)EL-+b<b2<2bAyM,GH)J@N2Iq/NJJA,tZH)=TU2W<hTNIqNeT=hbBE=TX_T1sT))=J0W!<NJIqN/*JhJ2=hZBE=hJ))aY(GH;jd,GH

You can try it out here.

This was a fun problem to golf! I'm still getting used to Pyth, but it's a really great language.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Pyth! One golf I see right away: If you want to make a 2 element list/tuple, use , - that's what it's there for. \$\endgroup\$ – isaacg Nov 6 '15 at 21:55
  • \$\begingroup\$ There are more place for this golf thoughout the code - (G%+H/N2b), (GH), (tZH). \$\endgroup\$ – isaacg Nov 7 '15 at 3:22
12
\$\begingroup\$

Haskell, 394 bytes

z=0<1
p d y c|all((0<).mod d)[2..d-1]=y|z=c
g x=x-signum(x-2)
e d(x,y)h|odd d=(g x,g y)|z=(x,mod(y+div d 2)h)
s d c@(_,y)w|d==(floor$sqrt$fromIntegral d)^2=(w-1,y)|z=c
f d a b m|b>d=m|b==d=(+1)<$>m|z=f d b(a+b)m
d%m@(w,h)|elem d[div(n*n-n)2|n<-[1..d+1]]=(w+1,h)|z=m
i=fst.c
j=snd.c
c d|d<1=((2,2),(5,5))|z=(s d(e d(p d(i$d-2)$i$d-1)$snd$j$d-1)$fst$j$d-1,d%(f d 1 1$j$d-1))
main=readLn>>=print.i

It can definitely be optimised and also after quickly checking for correctness it looks like I'm getting different results than the one posted. I'll come back and check more thoroughly my code when I have more time ^^

Nice problem by the way!

EDIT: edited my solution taking into account the precious advice given by Zgarb. It now works perfectly!

EDIT2: thanks to nimi I have made the code even smaller. I am now also doing the checks for even and odd in one function instead of two which overall decreases the count from 446 to 414 bytes.

EDIT3: further improved from 414 to 400 bytes. Thanks nimi for another 2 bytes, you're on fire! :)

EDIT4: 4 more bytes by nimi :)

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to PPCG! A couple of quick hints: 0<1 is shorter than otherwise, and 0/=mod x y can be shortened to 0<mod x y. Also, 1==mod(d)2 is odd d and 0==mod(d)2 is even d. \$\endgroup\$ – Zgarb Nov 3 '15 at 19:39
  • \$\begingroup\$ @Zgarb nice tricks, I am indeed pretty new at this whole code golf thing. How does 0<1 instead of otherwise work though? \$\endgroup\$ – basile-henry Nov 3 '15 at 19:41
  • 1
    \$\begingroup\$ Also, I think your definition of triangular numbers is wrong (I'm assuming that's in the function t), since elem d[1..div(d*d-d)2] is true for all d > 2. \$\endgroup\$ – Zgarb Nov 3 '15 at 19:41
  • \$\begingroup\$ otherwise is just another name for True. \$\endgroup\$ – Zgarb Nov 3 '15 at 19:42
  • \$\begingroup\$ Thank you very much, yeah you're right I tried to do triangular numbers too fast... \$\endgroup\$ – basile-henry Nov 3 '15 at 19:43
5
\$\begingroup\$

C, 425 396 bytes

typedef struct{int x,y,b,r}c;S,p,n;s(d){return(S=sqrt(d))*S==d;}c m(d){if(!d)return(c){2,2,4,4};c q,l=m(d-1);for(p=1,n=d;--n;p=p*n*n%d);if(p&&d>1)q=m(d-2),l.x=q.x,l.y=q.y;if(d%2)l.x-=l.x>2?1:l.x<2?-1:0,l.y-=l.y>2?1:l.y<2?-1:0;else l.y+=d/2,l.y=l.y>l.b?l.y-l.b-1:l.y;if(s(d))l.x=l.r;if(s(5*d*d+4)||s(5*d*d-4))l.b++;if(s(8*d+1))l.r++;return l;}main(i){scanf("%d",&i);printf("%d %d",m(i).x,m(i).y);}

There are parts to this that could be improved, but it works for the test cases.


Explanation

typedef struct {
    int x,y,b,r
} c; //c will hold the information for each day

//determines if a number is a perfect square
S,p,n;
s(d) {
    return (S=sqrt(d))*S==d;
}

c m(d) {
    if(!d)
        return (c){2,2,4,4}; //returns the initial information if the day is 0

    c q,l=m(d-1); //gets the information for the previous day
    for (p=1,n=d;--n;p=p*n*n%d); //tests if the number is prime

    if (p&&d>1)
        q=m(d-2),l.x=q.x,l.y=q.y; //changes the position to what it was at the end of the day 2 days ago if the day is prime
    if (d%2)
        l.x-=l.x>2?1:l.x<2?-1:0,l.y-=l.y>2?1:l.y<2?-1:0; //moves the position towards (2,2) if the day is odd
    else
        l.y+=d/2,l.y=l.y>l.b?l.y-l.b-1:l.y; //moves down if the day is even
    if (s(d))
        l.x=l.r; //moves east if the day is a perfect square
    if (s(5*d*d+4)||s(5*d*d-4))
        l.b++; //expands world down if the day is a fibonacci number
    if (s(8*d+1))
        l.r++; //expands world right if the day is a triangular number
    return l;
}

main(i) {
    scanf("%d",&i);
    printf("%d %d",m(i).x,m(i).y);
}
\$\endgroup\$
3
\$\begingroup\$

Perl 5, 284 bytes

@s=([2,2]);@n=(2,2);@f=(0,1);$w=$h=5;for(1..<>){$f[$_+1]=$f[$_]+$f[$_-1];$t[$_]=$_*($_+1)/2;$s[$_]=[@n];@n=@{$s[$_-1]}if(1 x$_)!~/^1$|^(11+?)\1+$/;($_%2)&&($n[0]-=($n[0]<=>2),$n[1]-=($n[1]<=>2))or$n[1]=($n[1]+$_/2)%$h;$n[0]=$w-1if(int sqrt$_)**2==$_;$h++if$_~~@f;$w++if$_~~@t}say"@n"

283 bytes, plus 1 for -E flag instead of -e

Same code but with more whitespace, more parentheses, and longer variable names:

@start=([2,2]);
@now=(2,2);
@fibonacci=(0,1);
$width = ($height=5);
for my $iterator (1 .. <>) {
  $fibonacci[$iterator+1] = $fibonacci[$iterator] + $fibonacci[$iterator-1];
  $triangular[$iterator] = $iterator * ($iterator+1) / 2;
  $start[$iterator] = [@now];
  @now = @{ $start[$iterator-1] } if ((1 x $iterator) !~ /^1$|^(11+?)\1+$/); # prime
  $now[0] -= ($now[0] <=> 2) , $now[1] -= ($now[1] <=> 2) if ($iterator % 2 != 0); # odd
  $now[1] = ($now[1] + $iterator / 2) % $height if ($iterator % 2 == 0); # even
  $now[0] = $width - 1 if ((int sqrt $iterator) ** 2 == $iterator); # square
  $height ++ if $iterator ~~ @fibonacci;
  $width ++ if $iterator ~~ @triangular;
}
say "@now";

I am confident that this can be golfed further.

\$\endgroup\$
2
\$\begingroup\$

Javascript, 361 359 bytes

N=>{for(c=1,x=y=v=w=j=k=2,h=z=5;c<=N;c++,j=v,k=w,v=x,w=y){m=Math;p=(n,c)=>n%c!=0?c>=n-1?1:p(n,++c):0;[x,y]=c==2||p(c,2)&&c!=1?[j,k]:[x,y];p=x=>x+(x<2?1:x>2?-1:0);c%2?[x,y]=[p(x),p(y)]:y+=c/2;m.sqrt(c)==~~m.sqrt(c)?x=z-1:0;f=(n,c,d)=>d<c?0:d==c?1:f(c,n+c,d);f(1,2,c)||c==1?h++:0;t=(n,c)=>n*++n/2==c?1:--n*n/2>c?0:t(++n,c);t(1,c)?z++:0;x%=z;y%=h}return x+" "+y}

The code use Destructuring assignment. It's only supported in Firefox and Safari right now.

Explanation

N=>{
// C => the day, x,y => position, v,w => position at the start of the day, 
// j,k => position of yesterday
for(c=1,x=y=v=w=j=k=2,h=z=5;c<=N;c++,j=v,k=w,v=x,w=y){
    m=Math;

    // Prime Function for C > 2. Recursive call to save a loop.
    p=(n,c)=>n%c!=0?c>=n-1?1:p(n,++c):0;
    // Assign x and y to yesterday
    [x,y]=c==2||p(c,2)&&c!=1?[j,k]:[x,y];

    // Function to move closer to home
    p=x=>x+(x<2?1:x>2?-1:0);
    c%2?[x,y]=[p(x),p(y)]:y+=c/2;

    // Square check
    m.sqrt(c)==~~m.sqrt(c)?x=z-1:0;

    // Fibonnacci function for C > 1
    f=(n,c,d)=>d<c?0:d==c?1:f(c,n+c,d);
    f(1,2,c)||c==1?h++:0;

    // Triangle function
    t=(n,c)=>n*++n/2==c?1:--n*n/2>c?0:t(++n,c);
    t(1,c)?z++:0;

    // Stay in bounds
    x%=z;y%=h
}
// Output
return x+" "+y}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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