title: Cartesian - polar conversion couple

text:
# Question
Title: Cartesian - polar conversion couple
We don't have a challenge for conversion between Cartesian and polar coordinates, so ...

### The challenge

Write **two programs** (or functions) in the same language:

* one that converts from polar to Cartesian coordinates, and
* the other from Cartesian to polar coodrinates.

The **score** is the sum of the two program lengths in bytes. Shortest wins.

For reference, the following figure (from the Wikipedia entry linked above) illustrates the relationship between Cartesian coordinates \\$(x, y)\\$ and polar coordinates \\$(r, \varphi)\\$:

### Additional rules

* Input and output are flexible as usual, except that they **cannot** be in the form of **complex numbers** (which would trivialize the problem). Of course, the program can use complex numbers internally, just not as input or output. Input and output methods can be different for the two programs.
* You can choose to input and output the angle \\$\varphi\\$ either in **radians** or in **degrees**; and to limit its values to any 2π-radian or 360º-degree **interval**.
* Builtins for coordinate conversion are allowed. If you use them, you may want to include another solution without the builtins.
* Floating-point number limitations (accuracy, allowed range of values) are acceptable.
* Programs or functions are allowed. Standard loopholes are forbidden.

### Test cases

Values are shown rounded to 5 decimals. Angles are in radians in the interval \\$\[0, 2\pi)\\$.

```
Cartesian: x, y       <-->      Polar: r, ϕ
------------------              ------------------

2.5, -3.42                       4.23632, -0.93957
3000, -4000                      5000, -0.92730
0, 0                             0, <any>
-2.08073, 4.54649                5, 2
0.07071, 0.07071                 0.1, 0.78540

```

# Answer
> 4 votes
# 10 (5 + 5)

## to polar, 5 bytes

```
*.@j.

```

Try it online!

## to cartesian, 5 bytes

```
+.@r.

```

Try it online!

Both of these amount to one built-in for the poler/cc conversion, combined with another builtin for the complex/x-y conversion.

# Answer
> 9 votes
# Python, 49 + 48 = 97 bytes

-2 thanks to @Seb

```
lambda r,a,n=9e9:((x:=r*(a/n-1j)**n).real,x.imag)
```

Attempt This Online!

```
lambda x,y,n=1e-9:(abs(c:=x+1j*y),(c**n).imag/n)
```

Doesn't use any libraries, no exp, no sin, no cos, etc.

### How?

All based on \\$\tan(x)\approx x\quad|x|\ll1\\$ and \\$e^x\approx(1+x/n)^n\quad n\gg 1\\$

# Answer
> 5 votes
# Wolfram Language (Mathematica), 14+11=25 bytes

```
AbsArg[#+I#2]&
AngleVector

```

Try it online!

Input `[x,y]`/`[{r,ϕ}]` and output `{r,ϕ}`/`{x,y}`.

```
       #+I#2    convert to complex
AbsArg[     ]   get abs (r) and arg (ϕ)

```

```
AngleVector     built-in.

```

# Answer
> 4 votes
# Desmos, 33+19 = 52 score

Both functions take in two arguments representing either polar or Cartesian coordinates (depending on which function is being used), and returns a list representing the converted coordinates.

### Cartesian to polar: 33 bytes

```
f(a,b)=[(aa+bb)^{.5},arctan(b,a)]

```

### Polar to Cartesian: 19 bytes

```
g(a,b)=[cosb,sinb]a

```

---

Try Both Online On Desmos!

Try Both Online On Desmos! - Prettified

# Answer
> 4 votes
# Mathematica, 18+20 = 38 bytes

```
ToPolarCoordinates

```

```
FromPolarCoordinates

```

Try it online!

For the `<any>` case, it will output a warning and use `Indeterminate`.

In some cases, it will not directly return the number, and instead return something like `ArcTan[4/3]` or `5*Cos[2]`. If that's not allowed:

# Mathematica, 21+23 = 44 bytes

```
N@*ToPolarCoordinates
N@*FromPolarCoordinates

```

Try it online!

# Answer
> 4 votes
# Pip `-p`, 10 + 12 = 22 bytes

Polar to Cartesian:

```
a*[CObSIb]

```

Takes angle in radians. Outputs a list containing x and y. Try it online!

Cartesian to polar:

```
PRT$+SQgbATa

```

Outputs radius and angle (in radians) on separate lines. Try it online!

### Explanations

```
a*[CObSIb]
            a is radius, b is angle
  [      ]  List containing
   COb       Cosine of b
      SIb    Sine of b
a*          Multiply each by a

PRT$+SQgbATa
              a is x-coordinate, b is y-coordinate, g is list containing both
     SQg      Square both coordinates
   $+         Fold the list of squares on addition
 RT           Square root
P             Print
        bATa  Two-argument arctangent of b and a
              Autoprint

```

# Answer
> 3 votes
# Jelly, 7 + 6 bytes = 13

#### Polar to Cartesian:

```
×ıÆe×Æi

```

A dyadic Link accepting \\$\theta\\$ on the left and \\$r\\$ on the right that yields a list \\$\[x, y\]\\$.

**Try it online!**

#### Cartesian to polar:

```
æịA,æA

```

A dyadic Link accepting \\$y\\$ on the left and \\$x\\$ on the right that yields a list \\$\[r, \theta\]\\$.

**Try it online!**

### How?

```
×ıÆe×Æi - Link: theta; r
 ı      - the imaginary unit, i
×       - (theta) multiplied by (i)
  Æe    - apply the exponential function -> e^(i.theta)
    ×   - multiply that by r -> r.e^(i.theta)
     Æi - Separate that into real and imaginary parts

```

```
æịA,æA - Link: y; x
æị     - y+i.x
  A    - absolute value -> r (same as for x+iy - we've just reflected in Re=Im)
    æA - atan2(y, x) -> theta (by definition)
   ,   - pair

```

---

Alternative \\$7\\$ byte Polar to Cartesian: `ÆẠ,ÆSƊ×`
(pair `,` the cosine `ÆẠ` and sin `ÆS` of `Ɗ` \\$\theta\\$ and multiply `×` by \\$r\\$).

# Answer
> 3 votes
# Factor, 16 + 15 = 31 bytes

```
[ rect> >polar ]

```

Try it online!

```
[ cis * >rect ]

```

Try it online!

`cis` does `e^(x*i)` and `cis *` is 1 byte shorter than `polar>`.

# Answer
> 3 votes
# x86 64-bit machine code, 23 + 13 = 36 bytes

```
D9 06 D9 07 D9 F3 D9 07 D8 C8 D9 06 D8 C8 DE C1 D9 FA D9 1E D9 1F C3
D9 07 D9 FB D8 0E D9 1F D8 0E D9 1E C3

```

Try it online!

These functions take addresses of two 32-bit floating-point numbers in RDI and RSI, and modify those numbers. The first transforms x,y into ϕ,r and the second does the opposite.

In assembly:

```
f:                      # FPU register stack contents
    fld DWORD PTR [rsi] #          y
    fld DWORD PTR [rdi] #      x   y
    fpatan              #          ϕ
    fld DWORD PTR [rdi] #      x   ϕ
    fmul st(0), st(0)   #     x²   ϕ
    fld DWORD PTR [rsi] #  y  x²   ϕ
    fmul st(0), st(0)   # y²  x²   ϕ
    faddp               #  x²+y²   ϕ
    fsqrt               #      r   ϕ
    fstp DWORD PTR [rsi]#          ϕ
    fstp DWORD PTR [rdi]#
    ret

g:                      # FPU register stack contents
    fld DWORD PTR [rdi] #          ϕ
    fsincos             # cosϕ  sinϕ
    fmul DWORD PTR [rsi]#    x  sinϕ
    fstp DWORD PTR [rdi]#       sinϕ
    fmul DWORD PTR [rsi]#          y
    fstp DWORD PTR [rsi]#
    ret

```

# Answer
> 3 votes
# Prolog (SWI), 43+37=80 bytes

### Cartesian to Polar, 43 bytes

```
X+Y+R+T:-R is(X^2+Y^2)^0.5,T is atan2(Y,X).

```

Try it online!

### Polar to Cartesian, 37 bytes

```
R+T+X+Y:-X is R*cos(T),Y is R*sin(T).

```

Try it online!

# Answer
> 2 votes
# Python, 48+48 = 96 bytes

```
lambda*t:(hypot(*t),atan2(*t))
from math import*
```

Attempt This Online!

-4 bytes thanks to xnor.

```
lambda a,b:(a*cos(b),a*sin(b))
from math import*
```

Attempt This Online!

# Answer
> 2 votes
# MATLAB/Octave, 9+9=18 bytes, builtins

Simple builtins, convert between (x,y) and (angle\[radians\],radius)

### Cartesian to polar:

```
@cart2pol

```

Try it online!

### Polar to cartesian:

```
@pol2cart

```

Try it online!

# 23+29=52 bytes, without builtins

Same input/output as before

### Cartesian to polar:

```
@(x,y)[atan2(y,x),abs(x+y*i)]

```

Try it online!

### Polar to cartesian:

```
@(a,r)r*[cos(a),sin(a)]

```

Try it online!

# Answer
> 2 votes
# SageMath, ~~69~~ 68 bytes

```
lambda x,y:((x^2+y^2)^.5,arctan2(y,x))
lambda r,t:(r*cos(t),r*sin(t))

```

Try it online!

*Adjusted score correctly thanks to Steffan.*
*Saved a byte thanks to Luis Mendo!!!*

# Answer
> 2 votes
# 05AB1E (legacy), 7 + 22 = 29 bytes

### Polar to Cartesian (7 bytes):

```
.¾¹.½‚*

```

Loose inputs in the order \\$\phi,r\\$; outputs as a pair \\$\[x,y\]\\$.

Try it online or verify all test cases.

### Cartesian to Polar (22 bytes):

```
nOtI`’£×.aÇâ2(ÿ,ÿ)’.E‚

```

Input as a pair in the order \\$\[x,y\]\\$; outputs as a pair \\$\[r,\phi\]\\$.

Try it online or verify all test cases.

**Explanation:**

```
.¾      # Calculate the cosine of the first (implicit) input ϕ
  ¹.½   # Also push the sine of the first input ϕ
     ‚  # Pair them together
      * # Multiply them to the second (implicit) input r
        # (after which the pair is output implicitly as result)

```

Although 05AB1E does have tangent, sine, and cosine builtins, it lacks arctan; arcsin; and arccos builtins (both with 1 or 2 arguments). So we'll use a Python eval for it instead (hence the use of the legacy version of 05AB1E)†:

```
n       # Get the square of the values in the (implicit) input-pair [y,x]
 O      # Sum them together
  t     # Take the square root of that
I       # Push the input-pair [x,y]
 `      # Pop and push both separated to the stack
  ’£×.aÇâ2(ÿ,ÿ)’
        # Push dictionary string "math.atan2(ÿ,ÿ)",
        # where the two `ÿ` are replaced with `y,x` respectively
   .E   # Evaluate and execute it as Python code
‚       # Pair it with the earlier calculated sqrt(y²+x²)
        # (after which it is output implicitly as result)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `’£×.aÇâ2(ÿ,ÿ)’` is `"math.atan2(ÿ,ÿ)"`.

† The new version of 05AB1E is possible as well, but `.E` is eval as Elixir instead of Python, in which case the `math.atan2(a,b)` would be `:math.atan2(a,b)`, which is 1 byte longer.

# Answer
> 2 votes
# , 30+24=54 bytes

### Cartesian to polar, 30 bytes

```
\(x,y)c(Mod(z<-x+1i*y),Arg(z))
```

Attempt This Online!

No imaginary numbers for +2:

```
\(x,y)c((x^2+y^2)^.5,atan2(y,x))
```

Attempt This Online!

### Polar to cartesian, 24 bytes

```
\(r,a)r*c(cos(a),sin(a))
```

Attempt This Online!

# Answer
> 2 votes
# Lua, 41 + 41 = 82 bytes

**Cartesian to Polar, 41 bytes**

```
x,y=...print((x^2+y^2)^.5,math.atan(y,x))

```

Try it online!

**Polar to Cartesian, 41 bytes**

```
r,t=...print(r*math.cos(t),r*math.sin(t))

```

Try it online!

# Answer
> 1 votes
# Vyxal, 10 + 7 = 17 bytes

## Cartesian to Polar, 10 bytes

```
²∑√?Ṙƒ/∆T"

```

Try it Online!

## Polar to Cartesian, 7 bytes

```
⁰₍∆c∆s*

```

Try it Online!

# Answer
> 1 votes
# C (gcc), 88 bytes

```
C(x,b,t)float*x,t;{t=x[1];x[1]=b?*x*sin(t):atan(t/(*x));*x=b?*x*cos(t):sqrt(*x**x+t*t);}

```

# 86 bytes

2 bytes can be saved by inverting the order of the cartesian coordinates, that is, \\$(y, x)\\$ instead of \\$(x, y)\\$,

```
C(x,b,t)float*x,t;{t=x[1];x[1]=b?*x*cos(t):atan(*x/t);*x=b?*x*sin(t):sqrt(*x**x+t*t);}

```

Try it online!

Pointer `x` is used for both input and output. `b` specifies which conversion must be applied (`0` for cartesian to polar, any non-zero value for polar to cartesian).

The solution is not made up by two different functions, but I think should be acceptable.

# 62 + 53 = 115 bytes

As two separate functions:

```
A(x,t)float*x,t;{t=x[1];x[1]=atan(t/(*x));*x=sqrt(*x**x+t*t);}
B(x,t)float*x,t;{t=x[1];x[1]=*x*sin(t);*x=*x*cos(t);}

```

Try it online!

2 bytes can be saved using the same trick as above described.

# Answer
> 1 votes
# lin, 28 + 17 = 45 bytes

To Polar (`[a b] -> [a b]`):

```
"2^.$_ +.5^"".$_.~ atant", Q

```

To Cartesian (`a b -> [a b]`):

```
"cos *""sin *", Q

```

Try it here!

For testing purposes:

```
[2.5 3.42_ ][3000 4000_ ][0 0][2.08073_ 4.54649][0.07071 0.07071] ;
( ;.+.$_.; \form.'.$$ " -> "join outln ).'
"2^.$_ +.5^"".$_.~ atant", Q
"cos *""sin *", Q

```

## Explanation

Prettified code:

```
( 2^.$_ + .5^ )(.$_.~ atant ) , Q
( cos * )( sin * ) , '

```

Both of these expressions utilize a somewhat odd feature of lin. Data structures of strings/functions\* passed to certain commands will "fork" and execute each function, preserving the structure's shape. For example:

```
1 2 [( 1+ )( 2+ )] es

```

would leave on the stack:

```
1 2 [[1 3] [1 4]]

```

The `Q` command ("quarantine") executes a function on an isolated copy of the current stack and pushes the resulting top item. So the following:

```
1 2 [( 1+ )( 2+ )] Q

```

would leave on the stack:

```
1 2 [3 4]

```

\*: In lin, strings and functions are the same datatype.

# Answer
> 1 votes
# PARI/GP, 34 + 24 = 58 bytes

```
f(x,y)=[abs(z=x+I*y),if(z,arg(z))]
g(r,a)=r*[cos(a),sin(a)]
```

Attempt This Online!

---
Tags: code-golf, math, number, arithmetic, floating-point
---


title: Collatz Encoding

text:
# Question
Title: Collatz Encoding
#### The Collatz Conjecture

The famous Collatz Conjecture (which we will assume to be true for the challenge) defines a sequence for each natural number, and hypothesizes that every such sequence will ultimately reach 1. For a given starting number N, the following rules are repeatedly applied until the result is 1:

While N \> 1:

* If N is even, divide by 2
* If N is odd, multiply by 3 and add 1

### Collatz Encoding

For this challenge, I have defined the **Collatz encoding** of a number, such that the algorithm specified in the conjecture may be used to map it to another *unique* number. To do this, you start with a 1 and at each step of the algorithm, if you divide by 2 then append a `0`, otherwise append a `1`. This string of digits is the binary representation of the encoding.

As an example we will compute the Collatz Encoding of the number 3, with the appended digits marked. The sequence for 3 goes

(1) 3 -\>1 10 -\>0 5 -\>1 16 -\>0 8 -\>0 4 -\>0 2 -\>0 1.

Therefore, our encoding is `208` (11010000 in binary).

### The Challenge

Your challenge is to write a function or program which takes an integer (**n\>0**) as input, and returns its Collatz encoding. This is a code golf challenge, so your goal is to minimize the number of bytes in your answer.

* For the edge case n=1, your solution should return `1`, because no iterations are computed and every encoding starts with a `1`.
* Floating point inaccuracies in larger results are acceptable if your language cannot handle such numbers accurately (encodings on the order of 10^40 as low as 27)

### Test Cases

I have written a reference implementation (Try It Online!) which generates the encodings of the first 15 natural numbers:

```
  1 | 1
  2 | 2
  3 | 208
  4 | 4
  5 | 48
  6 | 336
  7 | 108816
  8 | 8
  9 | 829712
 10 | 80
 11 | 26896
 12 | 592
 13 | 784
 14 | 174352
 15 | 218128

```

# Answer
> 13 votes
# Python 2, 49 bytes

```
f=lambda n,x=1:1/n*x or f(n/2-n%2*~n,x-n%2*~x<<1)

```

Try it online!

### Explanation

Notice the following: if `n` is odd, `3*n+1` must be even. This means that in the odd case, we can combine two steps into one, with `(3*n+1)/2`. Although it seems more complicated, the formula actually becomes much shorter:

```
[n/2,(3*n+1)/2][n%2]
[n/2,n+n/2+1][n%2]
n/2+[0,n+1][n%2]
n/2+n%2*(n+1)
n/2+n%2*-~n
n/2-n%2*~n

```

Then, to calculate the Collatz encoding, we'll append `[0]` if `n` is even, and `[1, 0]` if `n` is odd. Working on integers, we see that `x` becomes `[x*2,x*4+2][n%2]`. This can be further reduced to `x-n%2*~x<<1` (proof is left as an exercise to the reader).

# Python 2, 50 bytes

```
f=lambda n,x=1:1/n*x or f(n/2-n%2*~n<<n%2,x*2+n%2)

```

Try it online!

The "obvious" method to compute the next term would be `[n/2,3*n+1][n%2]`, but we can do better with a little bit magic: `n/2-n%2*~n<<n%2`. It can be derived by working backwards:

```
[n/2,3*n+1][n%2]
[n/2,(3*n+1)/2][n%2]<<n%2
n/2+[0,n+1][n%2]<<n%2
n/2+n%2*(n+1)<<n%2
n/2+n%2*-~n<<n%2
n/2-n%2*~n<<n%2

```

# Answer
> 12 votes
# JavaScript (ES6), 41 bytes

```
f=(n,o=1)=>n>1?f(n&1?n*3+1:n/2,2*o|n&1):o

```

Try it online!

### Commented

```
f = (             // f is a recursive function taking:
  n,              //   n = input
  o = 1           //   o = output, initialized to 1
) =>              //
n > 1 ?           // if n is still greater than 1:
  f(              //   do a recursive call:
    n & 1 ?       //     if n is odd:
      n * 3 + 1   //       use 3n + 1
    :             //     else:
      n / 2,      //       use n / 2
    2 * o | n & 1 //     append the parity bit of n to the output
  )               //   end of recursive call
:                 // else:
  o               //   we're done: return the output

```

# Answer
> 11 votes
# FRACTRAN, 11 fractions (72 bytes) and reversible

$$\frac{7}{13},\frac{11}{17},\frac{247}{35},\frac{338}{441},\frac{104}{21},\frac{425}{209},\frac{153}{44},\frac{85}{49},\frac{169}{22},\frac{17}{7},\frac{195}{11}$$

The input is \\$11\cdot 2^{n-1}\\$ and the output is \\$11\cdot 5^{k-1}\\$ where \\$k\\$ is the Collatz encoding of \\$n\\$. (Note: it doesn't halt there. It will go on to generate all the other redundant encodings of this technically multivalued function, for every number of \\$4,2,1\\$ cycles.)

If you replace all the instructions with their reciprocals and give it \\$11\cdot 5^{k-1}\\$ as input, it will compute \\$11\cdot 2^{n-1}\\$.

# Answer
> 6 votes
# Python 3.8 (pre-release), 55 bytes

```
f=lambda n,e=1:e*(n<2)or f(n*3//(6-5*(c:=n%2))+c,2*e+c)

```

Try it online!

This one uses an extra byte to do integer division since otherwise the answers accrue floating point innacuracy. I decided to submit the one with the extra `/` because Python can handle arbitrarily large integers according to your memory.

# Answer
> 6 votes
# Haskell, ~~55~~ ~~53~~ 49 bytes

*-2 bytes thanks to Unrelated String*

```
a?n|n<2=a|p<-mod n 2=(2*a+p)?(6^p*n`div`2+p)
(1?)

```

The solution is the anonymous function `(1?)`. Attempt This Online!

### Explanation

Port of my BQN solution, essentially. We define an infix function `?` that takes an accumulator `a` and a number `n`:

```
a ? n

```

When `n` is 1, just return the accumulator:

```
    | n < 2 = a

```

Otherwise, calculate `n` mod 2 and assign to `p` (for "parity"):

```
    | p <- mod n 2

```

Compute the new accumulator and number, and recurse:

```
        = (2 * a + p) ? (6 ^ p * n `div` 2 + p)

```

The new accumulator is simply twice the current accumulator plus the parity (`2 * a + p`). The Collatz function calculation is a little more involved:

```
6^p*n`div`2+p
6^p            6 to the power of the parity (1 if even, 6 if odd)
   *n          Times n (n if even, 6*n if odd)
     `div`2    Int-divided by 2 (n `div` 2 if even, 3*n if odd)
           +p  Plus the parity (n `div` 2 if even, 3*n+1 if odd)

```

Then our solution is simply `?` with a first argument (initial accumulator value) of 1.

# Answer
> 6 votes
# K (ngn/k), 31 bytes

```
2/1 :':2!(1<){(-2!x;1+3*x)2!x}\

```

Try it online!

# Answer
> 6 votes
# x86 32-bit machine code, 20 bytes

```
41 D1 E9 73 0A 6B C9 06 83 C1 04 0F 29 C0 F9 D1 D0 E2 ED C3

```

Try it online!

Uses the `fastcall` calling convention – argument in ECX, result in EAX.

In assembly:

```
s:  inc ecx     # Add 1 to restore the value of ECX.
    shr ecx, 1  # Shift ECX right by 1; the low bit goes into CF.
    jnc a       # Jump if CF=0 (the number was even).
    imul ecx, 6 # Multiply ECX by 6.
    add ecx, 4  # Add 4 to ECX, producing 3n+1 where n is the original value
    .byte 0x0F  # Effectively skip an instruction by making it part of a harmless "movaps xmm0, xmm0".
f:  sub eax, eax        # (Start here.) Set EAX to 0.
    stc         # Set CF to 1.
a:  rcl eax, 1  # Append CF to the bits of EAX.
    loop s      # Subtract 1 from ECX and jump if it's nonzero.
    ret         # Return.

```

# Answer
> 5 votes
# Pip, ~~27~~ 26 bytes

```
Wa>1Io.:Y%aa:6Ey*a/2+y;FBo

```

Attempt This Online!

### Explanation

```
Wa>1Io.:Y%aa:6Ey*a/2+y;FBo
                            a is first cmdline input; o is 1 (implicit)
W                           While
 a>1                        a is greater than 1:
         %a                  Parity of a (0 if even, 1 if odd)
        Y                    Yank into y variable
     o.:                     Concatenate to o in-place
    I                        If new value of o is truthy (which is always the case):
             6Ey              6 to the power of y (1 if a is even, 6 if odd)
                *a            Times a
                  /2          Divided by 2 (a/2 if even, 3*a if odd)
                    +y        Plus y (a/2 if even, 3*a+1 if odd)
           a:                 Assign that result back to a
                      ;     (Needed for parsing)
                       FBo  Convert the final value of o from binary
                            Autoprint

```

# Answer
> 4 votes
# C (gcc), 49 bytes

```
e;f(n){for(e=1;~-n;n=n%2?++e,3*n+1:n/2)e+=e;n=e;}

```

Try it online!

Inputs an integer.
Returns its Collatz encoding.

# Answer
> 4 votes
# Husk, 17 bytes

```
ḋ:1m%2↑←¡?o→*3½%2

```

Try it online!

Should be golfable. Ties `ḋ:1hm%2U¡?o→*3½%2` courtesy of @Razetime.

```
        ¡            Infinitely iterate on the argument:
         ?     %2    if even,
              ½      halve, else
          o→*3       3n+1.
      ↑←             Take while != 1,
   m%2               map mod 2,
 :1                  prepend 1,
ḋ                    convert from binary.

```

Only reason I thought to use Husk for this is this *almost* works:

# Husk, 19 bytes

```
ḋ:1↔tḋ€Σ¡ṁ§eDo/3←;1

```

Try it online!

Unfortunately manages to give 3840 instead of 829712 for 9, by virtue of not actually caring about the paths deterministically chosen (takes 28 to 85 as well as 14).

```
        ¡              Infinitely iterate
                 ;1    starting from [1]
         ṁ             concat-map
          §e           \n -> [   ,      ]
            D                 2*n
             o/3←                  n-1/3 ,
       Σ               concatenate the iterations,
      €                find the first 1-index of the input in them,
     ḋ                 convert to binary,
    t                  remove the leading 1,
   ↔                   reverse,
 :1                    put the leading 1 back,
ḋ                      and convert from binary.

```

# Answer
> 4 votes
# K (ngn/k), ~~53~~ ~~52~~ ~~48~~ 46 bytes

```
*|{$[1=n:*x;:x;*p;1+3*n;-2!n],2/|p:2 0!'x}/|1,

```

Try it online!

Pretty straightforward stab at this. Recurse with accumulator carrying both the number and the encoding.

-1 found a byte by using encode
-4 trying to remember lessons coltim passed on. (use tacit)
-2 don’t need list syntax

# Answer
> 4 votes
# Python 3.8 (pre-release), 50 bytes

```
f=lambda n,x=0:4//n*x/2or f(1-6*n//(l:=n^-n),~x*l)

```

Try it online!

Returns a float (+1 byte for int).

Test harness from @dingledooper or whoever they nicked it from ;-)

How?

Straight-forward recursion with one twist: Group n steps down, 1 step up into one iteration. This avoids branching at the expense of a slightly more complicated body. Detail: Recall that `n^-n` clears the lowest set bit in `n` and sets all above including the sign bit, so this is effectively the same as `-2 * (n&-n)`

# Answer
> 3 votes
# Haskell, 107 bytes

```
s d 0=0
s(a:q)n=a*2^n+(s q$n-1)
f n|n<2=[]|even n=0:f(div n 2)|1>0=1:f(n*3+1)
r 1=1
r n=s(1:f n)$length$f n
```

Attempt This Online!

I am new to Haskell golf, so I apologize for any bits of this that are outrageously ungolfed.

# Answer
> 3 votes
# Retina 0.8.2, ~~72~~ 68 bytes

```
.+
$*1;1
{+`^(1+)\1;(1+)
$1;$2$2
^1;(1+)
$.1
(1+);(1+)
1$1$1$1;1$2$2

```

Try it online! Link is to test suite that computes the results from `1` to `n`. Explanation:

```
.+
$*1;1

```

Convert `n` to unary and pair it with an initial output value of `1`.

```
{`

```

Repeat while the input is paired.

```
+`^(1+)\1;(1+)
$1;$2$2

```

While `n` is even, halve it and double the output value.

```
^1;(1+)
$.1

```

If `n` is `1`, then delete it and convert the output to decimal.

```
(1+);(1+)
1$1$1$1;1$2$2

```

Otherwise, triple `n`, double the output, and increment both of them.

After porting to Retina 1, it's possible to golf the answer down to 53 bytes, but for some reason it becomes inordinately slow:

```
.+
_;$&*
+`(_+);(_+)\2(_?)
$1$1$3;$2$.3*$(4*_5*$2
\G_

```

Try it online! Link includes faster test cases. Explanation:

```
.+
_;$&*

```

Convert `n` to unary and pair an initial output value of `1` with it.

```
+`(_+);(_+)\2(_?)
$1$1$3;$2$.3*$(4*_5*$2

```

While `n` is greater than `1`, perform a Collatz step on it, updating the output value appropriately. Here `$1` is the previous output value, `$2` is `n//2` (integer division) and `$3` is `n%2`, thus `n` is replaced by `n//2+n%2*(n//2*5+4)` which computes equal to `n*3+1` when `n` is odd.

```
\G_

```

Convert the output value to decimal and delete `n`.

# Answer
> 3 votes
# Factor \+ `math.extras project-euler.014`, 59 bytes

```
[ collatz [ < ] monotonic-count rest 1 prefix 48 v+n bin> ]

```

Try it online!

There is no way Factor would be competitive using the mathy recursive algorithm. Too many symbols means too much whitespace. So we take advantage of the fact that Factor has a built-in collatz sequence word and a simple way to detect increases in a sequence.

## Explanation

```
                       ! 3
collatz                ! { 3 10 5 16 8 4 2 1 }
[ < ] monotonic-count  ! { 0 1 0 1 0 0 0 0 }          (did it increase? then 1)
rest 1 prefix          ! { 1 1 0 1 0 0 0 0 }          (change first element to 1)
48 v+n                 ! { 49 49 48 49 48 48 48 48 }  (add 48 [equivalent to "11010000"])
bin>                   ! 208                          (convert from binary)

```

# Answer
> 3 votes
# Re:direction, ~~42~~ 38 bytes

```
++v
v>
<
+>+
>v
+> >
v
+> >>
> >v
+ >>

```

Try it online!

The following notation will be used for the contents of the queue: a number means that many s, and `|` means one . If the input number is N, the initial queue is `N|`, but for the purpose of this program, it's better to view it as `N|0`.

This program works through the Collatz iterations, while having the second number be 1 less than a number containing the result bits. It does two iterations at a time for odd numbers greater than 1. The possibilities are as shown:

# Answer
> 2 votes
# BQN, ~~36~~ 31 bytes

*-5 bytes inspired by ovs*

```
1⊸{a1:a;(p+2×)p+÷2÷6⋆p←2|}

```

Anonymous function that takes an integer and returns its Collatz encoding. Try it at BQN online

### Explanation

```
1⊸{a1:a;(p+2×)p+÷2÷6⋆p←2|}
  {                            }  Function of two arguments (right argument is the
                                  number, left argument calculates the answer):
   a1:                            Given left argument a and right argument 1,
       a                           return a
        ;                          Otherwise,
                                  call this function recursively
                                   with new right argument:
                            2|     Current number mod 2
                          p←        Store that value in p (for parity)
                        6⋆          6 to that power (1 for even numbers, 6 for odd)
                      2÷            2 divided by that amount (2 or 1/3)
                    ÷              Current number divided by that (x/2 or x*3)
                  p+                Add p (x/2+0 or x*3+1)
         (      )                  and new left argument:
            2×                     Current accumulator times 2
          p+                         Plus p

1⊸                                Call that function with a left argument of 1

```

Somewhat surprisingly, there seem to be no floating point errors from dividing by 3 until the numbers get too large to store as integers anyway.

# Answer
> 2 votes
# Charcoal, 30 bytes

```
Ｎθ⊞υ¹Ｗ⊖θ≔⎇↨⁰⊞Ｏυ﹪θ²⊕×³θ÷θ²θＩ↨²υ

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ

```

Input `n`.

```
⊞υ¹

```

Start with a Collatz encoding of `1`.

```
Ｗ⊖θ

```

Repeat until `n=1`.

```
≔⎇↨⁰⊞Ｏυ﹪θ²⊕×³θ÷θ²θ

```

Save `n%2` to the encoded value, and switch on that to halve or increment and triple `n` as appropriate. (Note that in order to avoid floating-point inaccuracy, I've used an integer halve, which is a byte longer than a floating-point halve.)

```
Ｉ↨²υ

```

Output the encoded value converted from base 2.

# Answer
> 2 votes
# Jelly, 14 bytes

```
×3‘$HḂ?’Ð¿Ḃṙ-Ḅ

```

Try it online!

## How it works

```
×3‘$HḂ?’Ð¿Ḃṙ-Ḅ - Main link. Takes n on the left
        Ð¿     - While loop, collecting each iteration i:
       ’       -   Condition: i > 1
      ?        -   Body: If:
     Ḃ         -     Condition: Bit; i % 2
   $           -     True:
×3             -       3i
  ‘            -       3i+1
    H          -     False: Halve
          Ḃ    - Bit of each i
           ṙ-  - Rotate the final 1 to the front
             Ḅ - Convert from binary

```

# Answer
> 2 votes
# Rust, ~~77 67~~ 61 bytes

-10 bytes, thanks @alephalpha.
-6 bytes, thanks @Juan Ignacio Díaz

```
|mut n|{let mut b=1;while n>1{b=2*b+n%2;n=[n/2,3*n+1][n%2]}b}

```

Try it online!

If overflows are not okay we can use ~~81~~ 74 (-6 bytes, thanks @Juan Ignacio Díaz) bytes instead and write

```
|mut n|{let mut b=1.;while n!=1{if n%2>0{b=2.*b+1.;n=3*n+1;}b*=2.;n/=2;}b}

```

Try it online!

which returns the value as a float, so it doesn't overflow for an input of 27. Instead it returns 4272797808638851700000000000000000, which is 137289440854955024 too small.

# Answer
> 1 votes
# tinylisp 2, 78 bytes

```
(d E(\(N(A 1))(?(= N 1)A(E(?(o N)(+(* 3 N)1)(/ N 2))(+(o N)A A

```

Try it at Replit: enter the above definition, and then on the next line call it like `(E 7)`, or test multiple arguments with something like `(map E (1to 10))`.

### Ungolfed/explanation

Another port of my BQN answer.

```
(def encode           ; Define encode
 (lambda              ; as a lambda function
  (num (accum 1))     ; that takes a number and an accumulator that defaults to 1:
  (if (= num 1)       ;  If num is 1,
   accum              ;   return accum
   (encode            ;  Else, do a recursive call with these arguments:
    (if (odd? num)    ;   First argument: if num is odd,
     (+ (* 3 num) 1)  ;    3 * num + 1
     (/ num 2))       ;    else num / 2
    (+ (odd? num)     ;   Second argument: add 1 if num is odd, 0 otherwise
     accum            ;    to accum
     accum)))))       ;    and accum again--thus, 2 * accum + (num mod 2)

```

# Answer
> 1 votes
# PARI/GP, 47 bytes

```
f(n,i=1)=if(n<2,i,f(if(n%2,3*n+1,n/2),2*i+n%2))
```

Attempt This Online!

# Answer
> 1 votes
# C, ~~75~~ 54 bytes

Edit: 54 bytes, credit to ceilingcat.

```
c(n,x){for(x=1;n>1;n=n%2?x++,n*3+1:n/2)x+=x;return x;}

```

Works with gcc and clang. Test main: `main(){for(int i=1;i<16;i++) printf("%d\n",c(i));}`

Takes and returns int16\_t. Beware of the dreaded integer overflow.

**81 chars, not conforming to requirements, but no overflow:**

```
#define P putchar(4
c(n){P 9);for(;n>1;){if(n%2){n=n*3+1;P 9);}else{n/=2;P 8);}}}

```

Prints as binary to stdout.

# Answer
> 1 votes
# 05AB1E, 17 bytes

```
[D#ÐÉi3*>ë;])ÉÁ2β

```

Try it online or verify all test cases.

**Explanation:**

```
[          # Loop indefinitely:
 D         #  Duplicate the current value
           #  (which will be the implicit input in the first iteration)
  #        #  If it's equal to 1: stop the infinite loop
   Ð       #  Triplicate the current value
    Éi     #  Pop one, and it it's odd:
      3*   #   Multiply the value by 3
        >  #   And add 1
     ë     #  Else (it's even instead):
      ;    #   Halve it
]          # Close the if-else statement and loop
 )         # Wrap all values on the stack into a list
  É        # Check for each value whether it's odd
   Á       # Rotate the list once towards the right
    2β     # Convert it from a binary-list to an integer
           # (after which the result is output implicitly)

```

# Answer
> 1 votes
# , 58 bytes

```
f=function(n,o=1,m=n%%2)`if`(n>1,f((5*m+1)*n/2+m,2*o+m),o)

```

Try it online!

Recursive function.

---

# , 58 bytes

```
function(n){while(n>1){T=T*2+(m=n%%2)
n=(5*m+1)*n/2+m}
+T}

```

Try it online!

Non-recursive approach, same length.

# Answer
> 1 votes
# Desmos, ~~83~~ 80 bytes

```
i->i+si+sk,n->(floor(n/2)+kn+k)(k+1)s
s=max(0,sign(n-1))
k=mod(n,2)
i=1
n=\ans_0

```

Try it on Desmos!

*-3 bytes thanks to Aiden Chow*

# Answer
> 1 votes
# Wolfram Language(Mathematica), 61 bytes

Try it online!

```
f[n_,i_:1]:=If[n<2,i,f[If[Mod[n,2]==1,3n+1,n/2],2i+Mod[n,2]]]

```

# Answer
> 0 votes
# MathGolf, 16 bytes

```
┴ò_■_@<\_┴←¬]y░å

```

Try it online.

Unfortunately there seem to be some bugs in MathGolf with the  and `ä` builtins, since this should have been possible in 12 bytes instead: `┴ô_■‼<_┴←¬]ä`..

**Explanation:**

```
┴                # Check if the (implicit) input is equal to 1
          ←      # While false with pop,
 ò               # execute the following 6 characters as inner code-block:
  _              #  Duplicate the current value
   ■             #  Pop the copy, and push its Collatz value
    _            #  Duplicate that Collatz value
     @           #  Triple-swap the top three values on the stack: a,b,b → b,a,b
      <          #  Pop the top two and push a<b
       \         #  Swap the top two values
        _        #  Duplicate the top value
         ┴       #  Pop the copy, and check if it's equal to 1
           ¬     #  Rotate the stack once, so this duplicated 1 is at the front
            ]    # Wrap the entire stack into a list
             y   # Join it together to a number
              ░  # Convert it to a string
               å # Convert it from a binary-string to an integer
                 # (after which the entire stack is output implicitly)

```

# Answer
> 0 votes
# Burlesque, 41 bytes

```
1{J2dv{2./}{3.*+.}IE}C~J1Fi.+1+]m{2.%}2ug

```

Try it online!

```
1        # Continuation takes last (1) value from stack
{
 J       # Duplicate
 2dv     # Divisible by two
 {2./}   # Halve
 {3.*+.} # *3+1
 IE      # If else
}C~      # Continue infinitely
J        # Duplicate
1Fi      # Find index of 1
.+       # Take that many
1+]      # Prepend 1
m{2.%}   # Map mod 2
2ug      # Read as binary digits

```

# Answer
> 0 votes
# Batch, 152 bytes

```
@if %1==1 echo 1&exit/b0
@set n=%1&set s=1
:l
@set/at=%n%%%2,s=%s%*2
@if %t%==1 (set/an=%n%*3+1,s=%s%+1)else set/an=%n%/2
@if %n% gtr 1 goto:l
@echo %s%

```

# Answer
> 0 votes
# APL(Dyalog Unicode), ~~40~~ 34 bytes SBCS

```
{⍺←⊂1⋄⍵=1:⍺⋄(p+2×⍺)∇p+⍵÷2÷6*p←2|⍵}

```

Try it on APLgolf!

Reworked to use the same idea as BQN.

---
Tags: code-golf, math, binary
---


# Question
Title: Intersection area of two rotated rectangles
Given two rectangles, which are possibly not in the orthogonal direction, find the area of their intersection.

## Input

You may take the rectangles as input in one of the following ways:

* The coordinates of the four vertices of the rectangle. These coordinates are guaranteed to represent a rectangle.
* The coordinates of the center of the rectangle, the width, the height, and the angle of rotation.
* The coordinates of the center of the rectangle, half the width, half the height, and the angle of rotation.
* The coordinates of the four vertices of the unrotated rectangle, and the angle of rotation. Since the unrotated rectangle is in the orthogonal direction, its coordinates can be represented by four numbers instead of eight. You may choose to rotate about either the center of the rectangle or the origin.

The angle can be either in degrees or radians. It can be either counterclockwise or clockwise.

You don't need to take the two rectangles in the same way.

## Output

The area of the intersection of the two rectangles.

The output must be within a relative or absolute error of \\$10^{-3}\\$ of the expected answer for the given test cases.

This means that, if the expected answer is \\$x\\$, and your answer is \\$y\\$, then \\$y\\$ must satisfy \\$|x - y| \leq \max(10^{-3}, 10^{-3} x)\\$.

This is , so the shortest code in bytes wins.

## Test cases

In the test cases, the rectangles will be given in the format `[x, y, w, h, a]`, where `(x, y)` is the center of the rectangle, `w` is the width, `h` is the height, and `a` is the angle of rotation in radians. The angle is measured counterclockwise from the positive x-axis.

```
[[0.0,0.0,1.0,1.0,0.0], [0.0,0.0,1.0,1.0,0.0]] -> 1.0
[[0.0,0.0,1.0,1.0,0.0], [0.0,0.0,1.0,1.0,0.785398]] -> 0.828427
[[-3.04363,2.24972,4.58546,9.13518,2.46245], [-3.2214,4.88133,9.71924,8.41894,-2.95077]] -> 31.9172
[[-0.121604,-0.968191,4.37972,3.76739,0.378918], [-2.64606,4.07074,5.22199,0.847033,-0.785007]] -> 0.0
[[-2.00903,-0.801126,9.90998,6.7441,-1.69896] ,[-2.6075,4.35779,4.29303,8.99664,-0.644758]] -> 14.5163
[[-3.29334,-1.24609,8.73904,3.86844,-2.90883], [-3.77132,-0.751654,1.14319,6.62548,0.806614]] -> 5.26269
[[3.74777,3.13039,1.94813,6.56605,1.53073], [1.20541,4.38287,5.16402,3.75463,-1.66412]] -> 4.89221
[[2.40846,1.71749,7.71957,0.416597,-2.4268], [-0.696347,-2.3767,5.75712,2.90767,3.05614]] -> 0.000584885
[[3.56139,-2.87304,8.19849,8.33166,1.00892], [3.03548,-2.46197,8.74573,7.43495,-2.88278]] -> 54.0515
[[3.49495,2.59436,8.45799,5.83319,0.365058], [3.02722,1.64742,1.14493,2.96577,-2.9405]] -> 3.3956

```

# Answer
# Python \+ Shapely, 88 bytes

```
lambda x,y:Polygon(x).intersection(Polygon(y)).area
from shapely.geometry import Polygon

```

Takes a list of ordered vertex coordinates for both rectangles (or any polygons) as input.

A solution using Shapely 2.0, but I'm working on golfing an awfully long solution which uses line-line intersection and the shoelace formula.
> 9 votes

# Answer
# Mathematica ~~60~~ 36 or ~~222~~ 175 bytes

**Pure coordinate input:**

```
Area@RegionIntersection[Polygon/@#]&

```

Thanks to @alephalpha and @att!

**`{x,y,w,h,a}` \- input:**

```
Area@RegionIntersection[Polygon/@((s=Sin@#5;c=Cos@#5;v1=#4s;v2=#3c;v3=#4c;v4=#3s;
.5{{v1+v2,v4-v3},{v2-v1,v3+v4},{-v1-v2,v3-v4},{v1-v2,-v3-v4}}+Table[{#1,#2},4])&@@@#)]&;

```

Expanded version self-explained:

```
Area@RegionIntersection[
  Polygon /@
   (
    With[
       {v1 = Sin@#[[5]] #[[4]],
        v2 = Cos@#[[5]] #[[3]],
        v3 = Cos@#[[5]] #[[4]],
        v4 = Sin@#[[5]] #[[3]]},
       .5 {{v1 + v2, v4 - v3}, {v2 - v1, v3 + v4 }, {- v1 - v2,
           v3 - v4 }, {v1 - v2, -v3 - v4}} +
        Table[{#[[1]], #[[2]]}, 4]] & /@ ##
    )
  ]&

```

A bit non-code golf, cause `Area` and `RegionIntersection` are extra-power built-ins. But this is working answer anyway =)
> 7 votes

# Answer
# Desmos, 229 bytes (non-competing)

```
u(x)=\frac{\operatorname{sign}(x)+1}{2}
t(a,b,c,d,x,y)=u(c-abs((x-a.x)\cos(b)-(y-a.y)\sin(b)))u(d-abs((x-a.x)sin(b)+(y-a.y)cos(b)))
f(a,b,c,d,g,h,i,j)=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}t(a,b,c,d,x,y)t(g,h,i,j,x,y)dxdy

```

Try it online!

Takes input as center point, rotation angle (radians), half width, half height, and then the same for the second rectangle.

First we define `u` to be the step function, then we define `t` to take a rectangle and coordinates x, y, and using transformations and the step function return 1 if the point is in the rectangle and 0 if it isn't. Then for `f` we simply multiply `t` applied to each rectangle, giving us a function which is 1 in the intersection and 0 otherwise. The we simply integrate this over x and y and we have the area.

So why non-competing? It doesn't meet the accuracy requirement. The theory here is sound, and I'm not enough of an expert in Desmos to know the technical reasons it isn't accurate, but in general Desmos is only so good at integrals. You may think it has to do with the bounds being \\$-\infty\\$ to \\$\infty\\$, but I tried finite (\\$-5\\$ to \\$5\\$) bounds as well and it made no difference. I *think* if the requirement was \\$10^{-2}\\$, it would actually pass, but alas.
> 2 votes

# Answer
# MATLAB, 344 bytes

344 bytes, maybe golfed more.

```
R=@(r1,r2)polyshape((r1(3)/2*[-1 1 1 -1])'*cos(r1(5))-(r1(4)/2*[-1 -1 1 1])'*sin(r1(5))+r1(1), (r1(3)/2*[-1 1 1 -1])'*sin(r1(5))+(r1(4)/2*[-1 -1 1 1])'*cos(r1(5))+r1(2)).intersect(polyshape((r2(3)/2*[-1 1 1 -1])'*cos(r2(5))-(r2(4)/2*[-1 -1 1 1])'*sin(r2(5))+r2(1),(r2(3)/2*[-1 1 1 -1])'*sin(r2(5))+(r2(4)/2*[-1 -1 1 1])'*cos(r2(5))+r2(2))).area

```

---

Single file that can directly run:

```
%test_CGCC256396.m
R = @(r1, r2) polyshape((r1(3)/2*[-1 1 1 -1])'*cos(r1(5))-(r1(4)/2*[-1 -1 1 1])'*sin(r1(5))+r1(1), (r1(3)/2*[-1 1 1 -1])'*sin(r1(5))+(r1(4)/2*[-1 -1 1 1])'*cos(r1(5))+r1(2)).intersect(polyshape((r2(3)/2*[-1 1 1 -1])'*cos(r2(5))-(r2(4)/2*[-1 -1 1 1])'*sin(r2(5))+r2(1), (r2(3)/2*[-1 1 1 -1])'*sin(r2(5))+(r2(4)/2*[-1 -1 1 1])'*cos(r2(5))+r2(2))).area;
rectangle_intersection = @(rect1, rect2) R(rect1, rect2);

rectangles = [
    [0.0,0.0,1.0,1.0,0.0],
    [0.0,0.0,1.0,1.0,0.0],
    [0.0,0.0,1.0,1.0,0.0],
    [0.0,0.0,1.0,1.0,0.785398],
    [-3.04363,2.24972,4.58546,9.13518,2.46245],
    [-3.2214,4.88133,9.71924,8.41894,-2.95077],
    [-0.121604,-0.968191,4.37972,3.76739,0.378918],
    [-2.64606,4.07074,5.22199,0.847033,-0.785007],
    [-2.00903,-0.801126,9.90998,6.7441,-1.69896] ,
    [-2.6075,4.35779,4.29303,8.99664,-0.644758],
    [-3.29334,-1.24609,8.73904,3.86844,-2.90883],
    [-3.77132,-0.751654,1.14319,6.62548,0.806614],
    [3.74777,3.13039,1.94813,6.56605,1.53073],
    [1.20541,4.38287,5.16402,3.75463,-1.66412],
    [2.40846,1.71749,7.71957,0.416597,-2.4268],
    [-0.696347,-2.3767,5.75712,2.90767,3.05614],
    [3.56139,-2.87304,8.19849,8.33166,1.00892],
    [3.03548,-2.46197,8.74573,7.43495,-2.88278],
    [3.49495,2.59436,8.45799,5.83319,0.365058],
    [3.02722,1.64742,1.14493,2.96577,-2.9405]
    ];

for i = 1:2:size(rectangles,1)
    rect1 = rectangles(i,:);
    rect2 = rectangles(i+1,:);
    area = rectangle_intersection(rect1, rect2);
    fprintf("Intersection area of rectangle %d and %d: %f\n", i, i+1, area);
end

```

```
Intersection area of rectangle 1 and 2: 1.000000
Intersection area of rectangle 3 and 4: 0.828427
Intersection area of rectangle 5 and 6: 31.917167
Intersection area of rectangle 7 and 8: 0.000000
Intersection area of rectangle 9 and 10: 14.516304
Intersection area of rectangle 11 and 12: 5.262695
Intersection area of rectangle 13 and 14: 4.892207
Intersection area of rectangle 15 and 16: 0.000585
Intersection area of rectangle 17 and 18: 54.051499
Intersection area of rectangle 19 and 20: 3.395599

```

---

Ungolfed version, with detailed code comment

```
function area = rectangle_intersection(rect1, rect2)
  % rect1 and rect2 are arrays of the form [x, y, w, h, a]
  % where (x, y) is the center of the rectangle, w is the width,
  % h is the height, and a is the angle of rotation in radians.

  % create polygons representing the rectangles
  poly1 = create_polygon(rect1);
  poly2 = create_polygon(rect2);

  % find the intersection of the polygons
  poly_intersect = intersect(poly1, poly2);

  % calculate the area of the intersection
  area = poly_intersect.area;
end

function poly = create_polygon(rect)
  % create a polygon representing the given rectangle
  x = rect(1); y = rect(2); w = rect(3); h = rect(4); a = rect(5);

  % calculate the coordinates of the corners of the rectangle
  corners = [-w/2 -h/2; w/2 -h/2; w/2 h/2; -w/2 h/2];

  % rotate the corners by the angle a
  rot_mat = [cos(a) sin(a); -sin(a) cos(a)];
  corners = corners * rot_mat;

  % translate the corners to the center of the rectangle
  corners(:,1) = corners(:,1) + x;
  corners(:,2) = corners(:,2) + y;

  % create the polygon
  poly = polyshape(corners(:,1), corners(:,2));
end

```
> 1 votes

---
Tags: code-golf, math, geometry
---


title: Record Least Uncommon Multiple Counts

text:
# Question
Title: Record Least Uncommon Multiple Counts
The Greatest Common Divisor, or **gcd**, of two positive integers \\$x\\$ and \\$y\\$ is the largest positive integer that divides both \\$x\\$ and \\$y\\$.

The Least Common Multiple, or **lcm**, of two positive integers \\$x\\$ and \\$y\\$ is the smallest positive integer that is a multiple of \\$x\\$ and \\$y\\$.

We define the Least Uncommon Multiple (**lum**) of \\$x\\$ and \\$y\\$ to be \\$\frac{\text{lcm}(x,y)}{\text{gcd}(x,y)}\\$.

We define the Least Uncommon Multiple Count (**lucm**) of \\$n\\$ as the number of positive integer pairs \\$x,y\\$ such that \\$x,y\leq n\\$ and \\$lum(x,y)=n\\$.

For example, \\$lucm(2)=2\\$, as \\$lum(1,2)=lum(2,1)=2\\$, while \\$lum(1,1)=lum(2,2)=1\\$.

Another example:

| \\$lum(x,y)\\$ | 1 | 2 | 3 | 4 | 5 | 6 |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 1 | 2 | 3 | 4 | 5 | **6** |
| 2 | 2 | 1 | **6** | 2 | 10 | 3 |
| 3 | 3 | **6** | 1 | 12 | 15 | 2 |
| 4 | 4 | 2 | 12 | 1 | 20 | **6** |
| 5 | 5 | 10 | 15 | 20 | 1 | 30 |
| 6 | **6** | 3 | 2 | **6** | 30 | 1 |

\\$lucm\\$(6) is the number of times 6 appears in the above table, which is 6. Thus \\$lucm(6)=6\\$.

##

We define the sequence \\$H\\$ as follows: \\$h\_i=lucm(i)\\$ for all positive integers \\$i\\$. \\$H\\$ begins as follows: 1, 2, 2, 2, 2, 6, 2, 2, 2, 6...

I was playing around with \\$H\\$, and what caught my interest was the set of numbers for which \\$lucm(n)\\$ was greater than that of any of the smaller integers. For example, \\$lucm(6)=6\\$, which is greater than any of the previous values in the sequence. We will call these numbers the Progressive Maxima of \\$H\\$. The first few progressive maxima of \\$H\\$ occur at \\$n=1,\ 2,\ 6,\ 12,\ 20,\ 30\ldots\\$

The challenge, should you choose to accept it, is to write code that calculates the most Progressive Maxima of \\$H\\$ within 1 minute without any hard-coding of the sequence.

### Scoring

Using the following Python code as the reference code:

```
from math import gcd
counter=1
prev_prog_max=1
prev_prog_max_val=1
counts={1:1}
print(1,1,1)
ctr=2
while True:
    for j in range(1,ctr):
        q=ctr*j/(gcd(ctr,j)**2)
        if q>=ctr and q in counts.keys():
            counts[q]+=2
        else:
            counts[q]=2
    if counts[ctr]>prev_prog_max_val:
        counter+=1
        print(counter,ctr,counts[ctr])
        prev_prog_max=ctr
        prev_prog_max_val=counts[ctr]
    ctr+=1

```

Take the number of progressive maxima your code returns in one minute, and divide it by the number of progressive maxima the reference code returns in one minute on your computer. The resulting value is your score. Highest score wins.

For example, say my code returned 140 progressive maxima in 1 minute, and the reference code returned 45. My score would be \\$\frac{140}{45}=\frac{28}{9}=3.\overline{09}\approx3.1\\$.

If there is a tie, the earliest answer wins.

---

My current best, which I will post as a non-competing answer in a month after the last answer for this question, returned 389 progressive maxima in 1 minute, while the reference code returned 45. My score would thus be \\$\sim\\!\\!8.64\\$. I'm completely confident that I've gotten all of the elements of \\$H\\$ that are less than 1 billion, and pretty confident that I have all such elements under 1 quadrillion (though it took me about 3-4 days of runtime to get them).

# Answer
> 6 votes
# Python \+ SymPy, \\$119/47\approx 2.532\\$ on my computer

```
from sympy.ntheory.factor_ import udivisors

def lucm(n):
    return sum(2*d for d in udivisors(n) if d * d < n)

counter = 1
prev_prog_max = 1
prev_prog_max_val = 1
print(1, 1, 1)
ctr = 2

while True:
    count = lucm(ctr)
    if count > prev_prog_max_val:
        counter += 1
        print(counter, ctr, count)
        prev_prog_max = ctr
        prev_prog_max_val = count
    ctr += 1

```

The `udivisors` function returns a list of unitary divisors of a number. A unitary divisor of \\$n\\$ is a divisor \\$d\\$ of \\$n\\$ such that \\$d\\$ and \\$n/d\\$ are coprime.

In fact, for two positive integers \\$a,b\\$, let \\$g=\gcd(a,b)\\$, then we can write \\$a=gc,b=gd\\$ for some coprime \\$c,d\\$, and we have \\$\operatorname{lcm}(a,b)=gcd\\$, \\$\operatorname{lum}(a,b)=cd\\$.

Now assume that \\$0\<a,b\le n\\$, \\$\operatorname{lum}(a,b)=n\\$. Then \\$c,d\\$ must be unitary divisors of \\$n\\$, and \\$g\le n/\max(c,d)\\$. So, for each unitary divisor \\$d\\$ of \\$n\\$ (and \\$c=n/d\\$), there are \\$n/\max(c,d)=\min(c,d)\\$ corresponding \\$(a,b)\\$'s such that \\$\operatorname{lum}(a,b)=n\\$.

So the total number of such \\$(a,b)\\$'s is \\$\sum\_{d\ \mid\ n\atop\gcd(d,n/d)=1}\min(d,n/d)\\$. This equals to \\$\sum\_{d\ \mid\ n,\ d^2\<n\atop\gcd(d,n/d)=1}2d\\$, except the special case \\$n=1\\$.

# Answer
> 5 votes
# , \\$178/48 \approx 3.708 \\$

Based on alephalpha's comment, powered by J's fast prime factorisation.

```
LUCM =: {{+/(<.|.)*/y^|:#:i.2^#y}}
main =: {{
'N C M' =. 1
echo 1 1 1
while. 1 do.
  N =. N+1
  L =. LUCM ^/__ q: N
  if. L>M do.
    C =. C+1
    M =. L
    echo C,x:N,M
  end.
end.
}}
main ''

```

Attempt This Online!

The function `LUCM` takes the prime factorisation of a number as the prime powers, e.g. 120 as `8 3 5` (`2^3 3^1 5^1`), and computes the LUCM from that.

# Answer
> 4 votes
# Mathematica 13.2 ~~112/48~~ 113/48 \\$\approx 2.35\\$

PyCharm 2020 + Python 3.8 was used for run Python code.
Thanks to @alephalpha for the cool math idea, please vote for his answer!

```

Clear[lucm]; lucm = Compile[{{n, _Integer}}, If[n == 1, 1,
2 Total@Select[Divisors[n], #^2 < n && GCD[#, Quotient[n, #]] == 1 &]]];

TimeConstrained[n = 1; count = 1; max = 0;
 While[True,
  res = lucm[n];
  If[res > max, max = res; Print[count, " ", n, " ", res]; count += 1];
  n += 1
  ], 60]; count

```

Some tips for Mathematica speed optimization:

* Switch on "Launch parallel kernels" → "At startup"
* Use `Compile[]` with type declaration
* Use real numbers for arithmetics to avoid long exact integer calculation,
but integers for such built-ins as `GCD[]`, `Divisors[]` etc.
* In old posts you can find a statement that old-school `Do[]`,`If[]` etc work faster than such built-ins as `Select[]`, `Reap[]/Sow[]` etc.
That is not the case at all!
* Run your program several times (maybe with small values) before the final trial.
Mathematica uses cache ;)
* Unfortunately there is no recurrent function for `Divisors[]`, but it is known that Mathematica effectively uses the results of previous calculations

# Answer
> 4 votes
## Pythran 206/46 ~ 4.5 on my laptop

Please note that this approach is on my laptop limited by available memory; the 206 were computed in well under 1 minute.

@alephalpha's method with minor tweaks:

* keep lists of primes and decompositions found so far aroundas we are spending the memory anyway a simple sieve is more efficient
* use the rather crude bound lumc(n) \<= 2^#distinct prime factors x sqrt n for some branch cutting
* use Pythran acceleration (this is he most impactful)

Code:

accel.py (this must be Pythran compiled)

```
from numpy import prod

# pythran export resdivsum(int32 [:],int,int,int,int)
# pythran export decomp(int32 [:,:])
# pythran export master(int32 [:,:],int,int)

def resdivsum(pp,mxdef,thmx,P,Q):
    if mxdef<0:
        return 0,mxdef
    ppp = prod(pp)
    if ppp*P < Q:
        ref = 2**len(pp) * thmx
        out = prod(pp+1)*P
        return out,mxdef - ref + out
    elif ppp*Q > P:
        out = 0
        inc,mxdef = resdivsum(pp[:-1],mxdef,thmx,P*pp[-1],Q)
        if mxdef < 0:
            return out+inc,mxdef
        out += inc
        inc,mxdef = resdivsum(pp[:-1],mxdef,thmx,P,Q*pp[-1])
        return out+inc,mxdef
    return 0,mxdef

def decomp(dec):
    m,n = dec.shape
    for i in range(2,m):
        if dec[i,-1] <= 0:
            ib = -dec[i,-1] or i
            ii = -ib
            dec[i,-1] = 0
            for j in range(i,m,i):
                ii += 1
                if ii == 0:
                    dec[j,-1] = -ib
                elif ii == ib:
                    ii = 0
                else:
                    dec[j,dec[j,-1]] = i
                    dec[j,-1] += 1

def master(dec,j,mxv):
    m,n = dec.shape
    lumc = 0
    while lumc <= mxv and j<m:
        j+=1
        d = dec[j]
        s = d[-1]
        d = d[:s]
        thmx = int(j**0.5)
        mxdef = (thmx<<s-1) - mxv
        lumc,defct = resdivsum(d,mxdef,thmx,1,1)
    return lumc,j

```

toplevel script (Python 3)

```
import time
from numpy import zeros,int32
from accel import resdivsum,decomp,master

# total time
tt = 60

r = time.perf_counter()

decompositions = zeros((100000000,10),int32)
decomp(decompositions)
print(time.perf_counter()-r)
maxidx = [0,1]
maxval = [0,0]
n = 1
rm = 1
print(1,1,1)
while time.perf_counter() < r+tt:
    lumc,n=master(decompositions,n,maxval[rm])
    if n==len(decompositions):
        break
    rm += 1
    maxidx.append(n)
    maxval.append(lumc)
    print(rm,maxidx[rm],2*maxval[rm])

```

# Answer
> 2 votes
# SageMath, \\$113/35 \approx 3.23 \\$ on SageMathCell

Based on @alephalpha's answer, made a little change.

**Thanks to @alephalpha for the cool math idea, please vote for his answer!**

---

Competition code, run it online!

```
from sage.arith.misc import divisors
import timeit
import math

def lucm(n):
    return sum(2*d for d in divisors(n) if gcd(n // d, d) == 1 and d * d < n)

counter = 1
prev_prog_max = 1
prev_prog_max_val = 1
print(1, 1, 1)
ctr = 2

start_time = timeit.default_timer()

while True:
    elapsed_time = timeit.default_timer() - start_time
    if elapsed_time > 60:
        break

    count = lucm(ctr)
    if count > prev_prog_max_val:
        counter += 1
        print(counter, ctr, count)
        prev_prog_max = ctr
        prev_prog_max_val = count
    ctr += 1

print("end")

```

Reference code, run it online!

```
from math import gcd
import timeit

counter=1
prev_prog_max=1
prev_prog_max_val=1
counts={1:1}
print(1,1,1)
ctr=2

start_time = timeit.default_timer()

while True:
    elapsed_time = timeit.default_timer() - start_time
    if elapsed_time > 60:
        break
    for j in range(1,ctr):
        q=ctr*j/(gcd(ctr,j)**2)
        if q>=ctr and q in counts.keys():
            counts[q]+=2
        else:
            counts[q]=2
    if counts[ctr]>prev_prog_max_val:
        counter+=1
        print(counter,ctr,counts[ctr])
        prev_prog_max=ctr
        prev_prog_max_val=counts[ctr]
    ctr+=1
print("end")

```

---
Tags: math, sequence, fastest-code
---


title: Salacious Bacon Tripod

text:
# Question
Title: Salacious Bacon Tripod
In a certain chatroom, we like making acronym jokes about the build tool we use called sbt. While it usually stands for "**S**cala **B**uild **T**ool", we aim to come up with all sorts of meanings, such as:

* Stupid Brick Teeth
* Sussy Baka Training
* Shady Blue Tourists
* Seriously Big Toes
* Silly Bear Topics
* Salacious Bacon Tripod
* Syringed Baby Toys
* Schadenfreude Bringing Trains
* Several Belated Tanks
* Slightly Better Tiet (because piet doesn't start with a T)

As you can see, the meaning of "sbt" changes each time, and the words used are never repeated. Today's challenge is to generalise this to a block of text.

## Challenge

Your task is to replace all instances of an acronym in a large block of text with a different meaning each time. To do so, you'll be given a string representing the haystack text and the acronym to change, as well as a list of words starting with each letter in the acronym.

For the acronym "sbt", you'll receive: the large text to change, the acronym, a list of words starting with "s", a list of words starting with "b" and a list of words starting with "t".

To each occurrence of the acronym, replace it with a uniformly randomly chosen word from each word list. To make sure the same set of words aren't used twice, one a word is chosen from a list, it can't be used again.

## Worked Example

Given the following text:

```
I think it might be possible to make an sbt wrapper to allow it to be
used without a shell. That means that instead of having to launch the
sbt console each time, you'll be able to use sbt commands straight
from the command line.

```

The acronym `"sbt"` and the following word lists:

```
["stupid", "sussy", "shady", "seriously", "silly", "salacious", "syringed", "several", "schadenfreude", "slightly"]
["brick", "baka", "blue", "big", "bear", "bacon", "baby", "bringing", "belated", "better"]
["teeth", "training", "tourists", "toes", "topics", "tripod", "toys", "trains", "tanks", "tiet"]

```

Valid outputs might include:

```
I think it might be possible to make an salacious bacon tripod wrapper to
allow it to be used without a shell. That means that instead of having to
launch the several big teeth console each time, you'll be able to use silly
blue toys commands straight from the command line.

I think it might be possible to make an stupid bear training wrapper to
allow it to be used without a shell. That means that instead of having to
launch the schadenfreude brick topics console each time, you'll be able to
syringed baka tripod sbt commands straight from the command line.

I think it might be possible to make an sussy baka toes wrapper to
allow it to be used without a shell. That means that instead of having to
launch the stupid brick teeth console each time, you'll be able to use
salacious baby topics commands straight from the command line.

```

Note that the above paragraphs have been line-wrapped for formatting reasons. They would otherwise be on a single line.

## Rules

* Only acronyms surrounded by spaces or EOF should be replaced. That means that `"sbt"` in something like `"whomsbted"` should not be replaced with an expanded meaning. `"sbt."` shouldn't be expanded either. But `"sbt"` at the start or end of the long text should be replaced.
* Acronyms will only contain distinct letters.
* The acronym will be case-sensitive. If the acronym is `"sbt"`, only `"sbt"` should be placed, not `"SbT"`, `"sbT"`, `"SBT"` and other variations.
* Inputs can be taken in any reasonable and convenient format.
* Inputs can be taken in any order.
* Output can be given in any reasonable and convenient format.
* Each word in expanded meanings should have an equal chance of being included given it hasn't already been used. This can be achieved by removing the chosen word from the word list.
* None of the inputs will be empty.
* You can assume that the word lists will have at least as many words as there are occurrences of the acronym in the large text. They may be different lengths to each other though.

## Test Cases

Format:

```
text
acronym
word lists
---
possible output

```

```
"I think it might be possible to make an sbt wrapper to allow it to be used without a shell. That means that instead of having to launch the sbt console each time, you'll be able to use sbt commands straight from the command line."
"sbt"
["stupid", "sussy", "shady", "seriously", "silly", "salacious", "syringed", "several", "schadenfreude"]
["brick", "baka", "blue", "big", "bear", "bacon", "baby", "bringing", "belated"]
["teeth", "training", "tourists", "toes", "topics", "tripod", "toys", "trains", "tanks"]
---
"I think it might be possible to make an salacious bacon tripod wrapper to allow it to be used without a shell. That means that instead of having to launch the several big teeth console each time, you'll be able to use silly blue toys commands straight from the command line."

```

```
"y'all ever just see a meme and rofl so hard that you rofl into a sharp object and rofl harder?"
"rofl"
["rinse", "rake", "randomise", "risky"]
["original", "orderly", "optimal", "omega"]
["flower", "flatten", "filibuster", "foxes"]
["linguistics", "legacies", "landings", "loses"]
---
"y'all ever just see a meme and rinse orderly flower landings so hard that you rake original filibuster loses into a sharp object and risky optimal flatten legacies harder?"

```

```
"Keg is a golfing language created by lyxal in 2018. Not to be confused with an actual beer keg, Keg is an acronym that stands for Keyboard Golfed. That's ironic, because Keg is horrible at golfing."
"Keg"
["Kaleidoscopes", "Keyboard", "King"]
["energetically", "eagerly", "entertains", "enrage"]
["goombas", "ginger", "google", "grams", "good"]
---
"Keyboard entertains ginger is a golfing language created by lyxal in 2018. Not to be confused with an actual beer keg, King eagerly grams is an acronym that stands for Keyboard Golfed. That's ironic, because Kaleidoscopes enrage goombas is horrible at golfing."

```

This is , so the answer with the lowest boring young train egg count in each language wins.

*Update: Turns out jokes about acronymised software tools aren't as unique as I thought - npm seems to have been doing it for ages on their website. Rip lol*

# Answer
> 8 votes
# JavaScript (Node.js), 93 bytes

-N bytes thanks to Arnoud and I4m2

```
(d,a,b)=>a.split` `.flatMap(e=>e==d?b.map(c=>c.splice(c.length*Math.random(),1)):[e]).join` `

```

Attempt This Online!

# Answer
> 8 votes
# \>\<\> (Fish), 429 bytes

```
i:>:?v~:>:?v~0i06.
1-/  \:i$fp
1f@:$~v?::i/.09-1p+
 :@:i:/.29-1p$0+f+*@}}@:{:{~v?
 .32-1p@i+f+*@}}@:{:{$@:$@:$/
    .a1${~\
>:?v;.7*93^?('!':i~\
/  >1-}$:@$:@-fg:?!^i:@=?!v~1+{
("!"o?)0:::r-1rio~~&v?:&:$/.8+1f~v?
+bc-1ogf-&:&+]}:{[4:/.61r$0 ~?)2l/.8
>:?v~0$06.>{:}*$:@+f+0$:&g:?v~:1c./:&:&go1-fb.
   \:f1+g0c.                >   :?^~00&p1-' 'o0a.
>:0>$:?v~0$:?v~3,$:@$:@)?v~
/-%1:,3< /a7$x$2+>3*$1-ac .
\$1+2c.  \+d.\$1+/.ab~$+1/

```

Try it, but only if you are very patient

Takes input like this, over stdin:

* Length prefixed acronym
* Length prefixed array of length prefixed options
* Length prefixed text

Works by inserting words into the code box at (length of acronym) * word + index of letter position. Each word is reversed, and column 0 is the lengths.

To generate a random number, first we log3 the max value, then we repeat adding 0, 1 or 2 depending on where the `x` takes us. Then we need to check if we are more than the max, in which case restart. Because the log is inaccurate we there is a 2/3 chance of rejection for the example test case.

We set the length of each word to 0 to mark it as already covered. If we select a word that has been tried previously we also just retry the RNG.

## Slightly More Detailed Explanation

```
i:>:?v~:>:?v~0i06.
1-/  \:i$fp

```

This places the acronym at row F, and a column of (length of acronym - index in acronym) in the code box. Note this will place it in reverse order. We keep the length on the stack.

```
1f@:$~v?::i/.09-1p+
 :@:i:/.29-1p$0+f+*@}}@:{:{~v?
 .32-1p@i+f+*@}}@:{:{$@:$@:$/
    .a1${~\

```

This is actually 3 nested loops, first over the lists of list of words, then over the words in each list, then over the letters in each word. The `{:{:@}}@*+f+` is the code to find the vertical position of each word, unfortunately it's very and and needs to be repeated twice :/ Once for writing the letters then again for writing the length.

```
    .a1${~\
>:?v;.7*93^?('!':i~\

```

Now we start reading the actual text. For each letter, check if it matches the nth letter of the acronym. Repeat till the first error, or until the acronym ends.

```
("!"o?)0:::r-1rio~~&v?:&:$/.8+1f~v?
+bc-1ogf-&:&+]}:{[4:/.61r$0 ~?)2l/.8

```

Since we don't print the letters in case they match the acronym, in case of a error we need to print again the first N letters of the acronym. This is the bottom row. The top row prints the rest of the letters of the word, until a space or less.

```
>:?v~0$06.>{:}*$:@+f+0$:&g:?v~:1c./:&:&go1-fb.
   \:f1+g0c.                >   :?^~00&p1-' 'o0a.

```

In case the acronym is matched, we jump here. First, `f+1g0c` gets the number of words for each letter. We then jump to `0c` which is the RNG.

When the RNG returns we get the word at that index, and print it. We also check if the word has already been used (it's length is 0) if so we retry another random number.

```
>:0>$:?v~0$:?v~3,$:@$:@)?v~
/-%1:,3< /a7$x$2+>3*$1-ac .
\$1+2c.  \+d.\$1+/.ab~$+1/

```

This is the RNG. Since the one random instruction in \>\<\> is x, this is a bit tricky. x changes the cursor to a random direction. The left loop does a log3, the right loop has a x, and adds either 0, 1, or 2 to the accumulator, then multiplies by 3. Finally, we check if the new number is indeed less than the target. (`)?v+`)If not we try again.

# Answer
> 6 votes
# Jelly, ~~19~~ 15 bytes

```
ḲḢ€K$}⁵⁼$¡€KɓẊ€

```

Try it online!

*-4 bytes and fixed thanks to lyxal :P*

Full program taking the text, wordlists, and acronym as successive command line arguments.

```
Ḳ                  Split the text on spaces
            ɓẊ€    and shuffle the wordlists.
          €        For each word in the split text:
      ⁵⁼$¡         If it's equal to the acronym,
 Ḣ€  }             destructively take the head of each wordlist
   K$              and join the words on spaces.
           K       Join the results on spaces.

```

I might have gotten too caught up earlier in thinking of a vectorization trick for checking if a word (right) matches the acronym as reconstructed from the wordlists (left), which also incorrectly replaces prefixes of the acronym:

```
a          Apply vectorized logical AND
 "         to corresponding elements (leaving excess unchanged) of the lists and
  W€}      the word with each letter wrapped in its own list.
     ¥Ƒ    Are the wordlists unchanged by this?

```

# Answer
> 6 votes
# 05AB1E, 12 bytes

```
#Š€.røðý.;ðý

```

Inputs in the order \\$sentence, words, acronym\\$, where \\$words\\$ is a list of lists of strings.

Try it online or verify all test cases.

**Explanation:**

```
#            # Split the first (implicit) input-sentence by spaces
 Š           # Triple-swap it with the other two implicit inputs, so the stack order
             # becomes: sentence-list, acronym, words-2D-list
  €          # Map over each inner list of words in the 2D list:
   .r        #  Randomly shuffle them
     ø       # Zip/transpose; swapping rows/columns (discarding any trailing words)
      ðý     # Join each inner list of words by spaces
        .;   # Replace every first occurrence of the acronym with these parts one by one
             # in the sentence-list
          ðý # Join the sentence back together with space delimiter
             # (after which it is output implicitly as result)

```

# Answer
> 6 votes
# Japt `-S`, ~~15~~ 14 bytes

It's been a *long* day, so I'm happy I got this down from the 26 bytes I had on my first pass. There's still probably another byte or ~~3~~ 2 to be saved, perhaps with a different approach, but this'll do for now.

Takes the string as the first input, the acronym as the second, and the replacements, as a 2D array, as the third.

```
¸cÈ¶V?WËjDÊö:X

```

Try it

```
¸cÈ¶V?WËjDÊö:X     :Implicit input of string U, acronym V and 2D array W
¸                  :Split U on spaces
 c                 :Flat map by
  È                :Passing each X through the following function
   ¶V              :  Is equal to V
     ?             :  If so
      WË           :    Map each D in W
        j          :      Remove (mutating original) & return element at 0-based index
         DÊ        :        Length of D
           ö       :        Random number in range [0,DÊ)
            :X     :  Else return X
                   :Implicit output, joined with spaces

```

# Answer
> 4 votes
# Charcoal, 31 bytes

```
⪫Ｅ⪪θ ⎇⁼ιη⪫Ｅη§⊞Ｏυ‽⁻Φζ⁼λ§ν⁰υ±¹ ι

```

Try it online! Link is to verbose version of code. Takes the list of all the words as a single argument. Explanation:

```
   θ                            Input sentence
  ⪪                             Split on spaces
 Ｅ                              Map over words
       ι                        Current word
      ⁼                         Equals
        η                       Input acronym
     ⎇                          If true then
           η                    Input acronym
          Ｅ                     Map over letters
                   ζ            Input words
                  Φ             Filtered where
                     λ          Current letter
                    ⁼           Equals
                      § ⁰       First letter of
                       ν        Current word
                 ⁻              Set difference with
                         υ      Predefined empty list
                ‽               Random element
             ⊞Ｏυ                Push to predefined empty list
            §             ±¹    Last element (i.e. the one just pushed)
         ⪫                      Join on spaces
                             ι  Otherwise current word
⪫                               Join on spaces
                                Implicitly print

```

27 bytes with a slightly more contrived input format:

```
⪫Ｅ⪪θ ⎇⁼ιη⪫Ｅη§⊞Ｏυ‽⁻§ζλυ±¹ ι

```

Try it online! Link is to verbose version of code. Explanation: As above except

```
                   ζ        Input dictionary
                  §         Indexed by
                    λ       Current letter

```

25 bytes by assuming that the lists of words are in the same order as the acronym:

```
⪫Ｅ⪪θ ⎇⁼ιη⪫Ｅζ§⊞Ｏυ‽⁻λυ±¹ ι

```

Try it online! Link is to verbose version of code. Takes a list of word lists as the third argument. Explanation: As above except

```
           ζ                Input word lists
          Ｅ                 Map over lists
                  λ         Current list
                 ⁻          Set difference with
                   υ        Predefined empty list
                ‽           Random element
             ⊞Ｏυ            Push to predefined empty list
            §       ±¹      Last element (i.e. the one just pushed)

```

# Answer
> 4 votes
# Vyxal, ~~20~~ 14 bytes

*-6 bytes from @AndrovT*

```
⌈?\%VṄ?vÞ℅∩vṄ%

```

Try it Online!

## Explanation

```
⌈?\%VṄ?vÞ℅∩vṄ%
⌈               # Split implicit first input (text) by spaces
 ?              # Take second input (acronym)
  \%V           # Replace all instances of second input in first with "%"
  Ṅ             # Rejoin the split list with spaces
    ?           # Take third input (list of lists of substitute words)
     vÞ℅        # Randomly permute each of the lists in the third input
        ∩       # Transpose
         vṄ     # Join each row of transposed list
           %    # Format string: replace all "%" from original string with entries from the transposed list

```

# Answer
> 4 votes
# Go, 207 bytes

```
import(."math/rand";."strings")
type Q=string
func f(s,a Q,W[][]Q)Q{S:=Split(s," ")
for i:=range S{w:=[]Q{}
for n:=range a{w=append(w,W[n][Intn(len(W[n]))])}
if S[i]==a{S[i]=Join(w," ")}}
return Join(S," ")}

```

Attempt This Online!

Pass in the arguments `sentence, acronym, wordlists`.

# Answer
> 3 votes
# Python, ~~145 134~~ 133 bytes

```
lambda t,a,w,r='':[*map(shuffle,w)]+[x==a and[(r:=r+l.pop()+' ')for l in w]or(r:=r+x+' ')for x in t.split()]and r
from random import*

```

Attempt This Online!

# Answer
> 3 votes
# C (gcc), ~~416~~ ~~366~~ 347 bytes

* -69 thanks to ceilingcat

Takes acronym word lists in acronym letter order.

```
#define P putchar(j)
**A,b,c,j,k,l,u,*z;f(s,t,a)char*s,***a;{for(l=j=strlen(t),A=calloc(j+1,8);u=j--;*(A[j]=calloc(k,8))=k)for(k=0;a[j][k++];);for(;j=*s;s++)if(isspace(j))u=!P;else if(u)P;else if(strncmp(s,t,l)|!isspace(s[l])*s[l])u=P+1;else for(b=0,s+=l-1;z=A[b];z[c]=printf(" %s"+!b++,a[b][c-1]))for(k=rand(c=wcslen(z))%--*z;k--;)for(;z[++c];);}

```

Try it online!

Ungolfed version:

```
int **A, // shadow usage array
    b, c, // row and column during array processing
    j, // string processing current character
    k, // selected index
    l, // acronym string length
    u, // string processing state
    *z; // row alias
void f(const char *s, // input string
       const char *t, // acronym string
       const char ***a) { // word lists array
  for(l=j=strlen(t), A=calloc(j+1, sizeof(int *)); // construct shadow array
      j--; *(A[j]=calloc(k, sizeof(int)))=k) // zero-initialize each usage list and indicate size
    for(k=0; a[j][k++];);

  for(u=0; j=*s; s++) // process string, initial state is in whitespace
    if(isspace(j)) putchar(j), u=0; // whitespace: print and set state
    else // non-whitespace
      if(u) putchar(j); // already in non-whitespace, will not be the acronym: print
      else
        if(strncmp(s,t,l) | // coming from whitespace: is the acronym?
           !isspace(s[l])*s[l]) // is there whitespace or NUL after?
            u=!!putchar(j); else // no, print and set non-whitespace

            for(s+=l-1, b=0; z=A[b]; // position source and string; for each acronym letter
                z[c]=printf(" %s"+!b++,a[b][c-1])) // mark word as used and print word
              for(k=rand(c=wcslen(z))%--*z; k--;) for(; z[++c];); // get random word, skipping used words
}

```

# Answer
> 3 votes
# Wolfram Language (Mathematica), 110 bytes

```
Table[StringReplace[#1,RegularExpression["\\b"<>#2<>"\\b"]->i],{i,StringRiffle/@Transpose[RandomSample/@#3]}]&

```

Try it online!

# Answer
> 2 votes
# Scala, 215 bytes

Golfed version. Try it online!

```
type Q=String
def f(s:Q,a:Q,W:Array[Array[Q]]):Q={val S=s.split(" ");for(i<-S.indices){val w=ArrayBuffer[Q]();for(n<-W.indices){w+=W(n)(Random.nextInt(W(n).length))};if(S(i)==a)S(i)=w.mkString(" ")};S.mkString(" ")}

```

Ungolfed vesrion. Try it online!

```
import scala.util.Random
import scala.collection.mutable.ArrayBuffer

object Main {
  type Q = String

  def f(s: Q, a: Q, W: Array[Array[Q]]): Q = {
    val S = s.split(" ")
    for (i <- S.indices) {
      val w = ArrayBuffer[Q]()
      for (n <- W.indices) {
        w += W(n)(Random.nextInt(W(n).length))
      }
      if (S(i) == a) S(i) = w.mkString(" ")
    }
    S.mkString(" ")
  }

  def main(args: Array[String]): Unit = {
    Random.setSeed(System.currentTimeMillis())

    println(f("I think it might be possible to make an sbt wrapper to allow it to be used without a shell. That means that instead of having to launch the sbt console each time, you'll be able to use sbt commands straight from the command line.", "sbt", Array(Array("stupid", "sussy", "shady", "seriously", "silly", "salacious", "syringed", "several", "schadenfreude"), Array("brick", "baka", "blue", "big", "bear", "bacon", "baby", "bringing", "belated"), Array("teeth", "training", "tourists", "toes", "topics", "tripod", "toys", "trains", "tanks"))))
  }
}

```

# Answer
> 1 votes
# Python, 112 bytes

```
lambda t,a,w:[t:=t.replace(a," ".join(x),1)for x in zip(*(sample(x,len(x))for x in w))]and t
from random import*

```

Attempt This Online!

---
Tags: code-golf, string, random
---


title: When will the DVD logo hit the corner?

text:
# Question
Title: When will the DVD logo hit the corner?
One of my favorite memes is the bouncing DVD logo. Yet silly but extremely satisfying, a DVD logo keeps bouncing on a screen and if you ever happened to watch this screensaver, you were most likely anxiously waiting for the logo to exactly hit the corner.

I know part of the fun is the waiting, but let's try to predict when the DVD logo will hit the corner of the screen.

# Task

Given the dimensions and initial coordinates of the logo and the size of the grid, calculate when the logo will hit any corner for the first time.

# Specs

* In this challenge, the logo will be represented by a rectangle and the screen by a grid. The grid will always be bigger than the logo.
* The logo's starting movement will be southeast. The logo only moves diagonally. Horizontal and vertical speeds are the same and stays the same.
* The unit of time for this challenge is represented as a movement of 1 grid square in a certain direction.
* If the logo already starts in a corner, the expected answer is 0 (the logo is already touching a corner).
* The initial coordinates of the logo represents the top-left corner of the logo.
* The starting logo position will not extend outside the grid.
* You can assume for this challenge that the logo will eventually hit a corner.
* Input is flexible, read it however you see fit for you.
* Standard loopholes are not allowed.

# Example

In the example below, the initial coordinates of the logo is `i=(1,1)`, the size of the grid is `g=(20,20)`, the dimensions of the dvd logo is `d=(10,5)`.

It took `29 units of time` to reach a corner.

# Test Cases

```
Format:
i , g , d --> output

#Special cases: logo starting in the four corners
(10,15), (20,20), (10,5) --> 0
(10,0), (20,20), (10,5) --> 0
(0,0), (20,20), (10,5) --> 0
(0,15), (20,20), (10,5) --> 0
#Special cases: logo starting glued to all walls
(0,7), (30,20), (7,12) --> 161
(7,0), (30,20), (7,12) --> 16
(23,3), (30,20), (7,12) --> 69
(11,8), (30,20), (7,12) --> 104
# Other test cases
(1,1), (20,20), (10,5) --> 29
(11,8), (24,50), (7,12) --> 448
(11,8), (50,24), (7,12) --> 376
(5,8), (48,39), (31,3) --> 352

```

This is , so shortest answers in bytes wins!

# Answer
# Wolfram Language (Mathematica), 27 bytes

```
ChineseRemainder[-#,#2-#3]&

```

Try it online!

This is the least \\$t\ge0\\$ such that \\$i+t\equiv0\pmod{g-d}\\$.
> 42 votes

# Answer
# Python, 59 bytes

### -1 thanks to @xnor

```
f=lambda i,I,g,G,d,D:i%(g-d)+I%(G-D)and-~f(i+1,I+1,g,G,d,D)

```

Attempt This Online!

Based on the observation that we can "unroll" the box and let the logo fly in a straight line.
> 22 votes

# Answer
# C (gcc), ~~55~~ 54 bytes

```
f(A,B,x,y,a,b){for(x-=a,a=0;A++%x|B++%(y-b);a++);b=a;}

```

Try it online!

Saved 1 thanks to @G B

*f(A,B,x,y,a,b){* function tacking :

* A B as position
* x y as grid size
* a b as logo size

*for(x-=a,y-=b* stretches grid to remove logo space.

*A++%x|B++%y* checks if both bounds are reached using positions % new grid sizes
> 8 votes

# Answer
# Jelly,  ~~11~~  10 bytes

Followed att's description in their Mathematica answer.

```
_µ0+⁵ọẠʋ1#

```

A full program that accepts `g`, `d`, `i` and prints the result.

**Try it online!**

### How?

```
_µ0+⁵ọẠʋ1# - Main Link: grid-dimensions (g), DVD-dimensions (d)
_          - g subtract d (vectorises)
 µ         - start a new monadic chain - f(g-d)
  0        - set the left argument "Step" to 0 (right argument is g-d by default)
         # - count up and find...
        1  - ...the first truthy result of:
       ʋ   -   last four links as a dyad - f(Step, g-d):
    ⁵      -     program's third argument -> initial-state (i)
   +       -     add to Step (vectorises)
     ọ     -     multiplicity (vectorises) (number of times each Step+i value
                                            divides the respective g-d value)
      Ạ    -     all? (are both non-zero?)
           - implicit print

```
> 7 votes

# Answer
# Vyxal, 12 bytes

```
λ‹?+??-ḊA;ṅ‹

```

Try it online! Test suite.

Similar to @att's answer.

```
λ‹?+??-ḊA;ṅ‹
λ        ;ṅ   # Find the first positive integer t>0 such that:
 ‹?+   ḊA     #  t-1+x for each x in i are both divisible by, respectively...
    ??-       #  g[0]-d[0] and g[1]-d[1].
           ‹  # Subtract one from this.

```
> 6 votes

# Answer
# Ruby, ~~56 ...~~ 50 bytes

```
->r,c,h,w,d,v{a=-r%h-=d;a+=h while(c+a)%(w-v)>0;a}

```

Try it online!

### How it works:

First, unwrap the box, and reduce the coordinates. It will take `a` steps to reach the vertical boundary, and after that it will take `h-d` steps to reach the next. So we only need to check if we hit the horizontal boundary every `h-d` steps.
> 6 votes

# Answer
# Java, ~~73~~ 69 bytes

```
(i,I,g,G,d,D)->{int r=0;for(;(i-r)%(d-g)+(I-r--)%(D-G)>0;);return~r;}

```

Port of *@att*'s Mathematical answer.

Try it online.

**Explanation:**

```
(i,I,g,G,d,D)->{      // Method with 6 integer parameters and integer return-type
  int r=0;            //  Create a result-integer `r`, starting at 0
  for(;(i-r)%(d-g)    //  Loop as long as (i-r) modulo (d-g)
       +(I-r--)%(D-G) //  and (I-r) modulo (D-G) added together
       >0;);          //  is not 0 yet
                      //  (and decrease `r` by 1 after this check with `r--`)
  return~r;}          //  After the loop, return -r-1 as result

```
> 3 votes

# Answer
# PARI/GP, 49 bytes

```
f(i,g,d,n)=lift(chinese([Mod(-i[n++],m)|m<-g-d]))

```

Attempt This Online!

A port of @att's Mathematica answer.

---

# PARI/GP, 50 bytes

```
f(g,h,d,e)=t(i,j)=if(i%(g-d)+j%(h-e),1+t(i+1,j+1))

```

Attempt This Online!

A port of @loopy walt's Python answer. This is a curried function that takes input as `f(g1,g2,d1,d2)(i1,i2)`.
> 3 votes

# Answer
# 05AB1E, 10 bytes

```
-U∞<.Δ+XÖP

```

Another port of *@att*'s Mathematica answer, so make sure to upvote him as well!

Inputs in the order \\$d,g,i\\$.

Try it online or verify all test cases.

**Explanation:**

```
-        # Decrease the first two (implicit) inputs from one another: [g₁-d₁, g₂-d₂]
 U       # Pop and store this pair in variable `X`
∞        # Push an infinite positive list: [1,2,3,...]
 <       # Decrease each by 1 to make it a non-negative list: [0,1,2,...]
  .Δ     # Find the first integer `y` in this list which is truthy for:
    +    #  Add it to the third (implicit) input: [i₁+y, i₂+y]
     X   #  Push pair `X`
      Ö  #  Check if the pairs are divisible: [(i₁+y)%(g₁-d₁)==0, (i₂+y)%(g₂-d₂)==0]
       P #  Product to check if both are truthy: ((i₁+y)%(g₁-d₁)==0)*((i₂+y)%(g₂-d₂)==0)
         # (after which the found result is output implicitly)

```
> 2 votes

# Answer
# Charcoal, 34 bytes

```
≔Ｅ²Ｎθ≔Ｅ²ＮηＵＭη⁻ιＮ≔⁰ζＷ⊙⁺θζ﹪κ§ηλ≦⊕ζＩζ

```

Try it online! Link is to verbose version of code. Explanation:

```
≔Ｅ²Ｎθ

```

Input the initial coordinates of the logo.

```
≔Ｅ²Ｎη

```

Input the size of the grid.

```
ＵＭη⁻ιＮ

```

Subtract the dimensions of the logo from the size of the grid.

```
≔⁰ζ

```

Start at `0` units of time.

```
Ｗ⊙⁺θζ﹪κ§ηλ

```

Move the logo by the current time and wrap it back into the grid. Until the sides of the logo line up with the sides of the grid...

```
≦⊕ζ

```

... increment the time.

```
Ｉζ

```

Output the final time.
> 2 votes

# Answer
# Python 3 \+ SymPy, 127 bytes

A port of @att's answer.

---

Golfed version. Try it online!

```
from sympy.ntheory.modular import crt
from numpy import array as A
f=lambda i,g,d:crt((A(g)-A(d)).tolist(),(-A(i)).tolist())[0]

```

Ungolfed version. Try it online!

```
from sympy.ntheory.modular import crt
import numpy as np

def chinese_remainder(i, g, d):
    i_array = -np.array(i)
    gd_array = np.array(g) - np.array(d)
    return crt(gd_array.tolist(), i_array.tolist())[0]

test_cases = [
    ([10, 15], [20, 20], [10, 5]),
    ([10, 0], [20, 20], [10, 5]),
    ([0, 0], [20, 20], [10, 5]),
    ([0, 15], [20, 20], [10, 5]),
    ([0, 7], [30, 20], [7, 12]),
    ([7, 0], [30, 20], [7, 12]),
    ([23, 3], [30, 20], [7, 12]),
    ([11, 8], [30, 20], [7, 12]),
    ([1, 1], [20, 20], [10, 5]),
    ([11, 8], [24, 50], [7, 12]),
    ([11, 8], [50, 24], [7, 12]),
    ([5, 8], [48, 39], [31, 3])
]

# Use the test_cases list defined above
for input_tuple in test_cases:
    print(f"{input_tuple} -> {chinese_remainder(*input_tuple)}")

```
> 0 votes

---
Tags: code-golf, grid
---


title: May the wind be always at your back

text:
# Question
Title: May the wind be always at your back
You are Odysseus, and are finally free from Calypso (who has kept you captive for many years) after you drugged her while she was sleeping1. You wish to return to your homeland of Ithaca, but the ship you've stolen is a bit damaged and cannot steer. However, you have also stolen a map which contains the location of Calypso’s island as well as the locations of Ithaca and the small islands that lie in between, as well as information about the wind currents of the area. Your ship can only sail by the wind currents, but you get to choose the direction you start in (north, south, east, west). If the currents bring you to another island, you also get to choose the direction in which you depart that island.

Can you get home to Ithaca?

\[1\] Because that definitely happens in the epic.

## Input Format

The input consists of:

* positive integers w and h
* a w-by-h grid of characters representing the map, where:
    + `~` denotes calm sea
    + `^` denotes a wind blowing north
    + `v` denotes a wind blowing south
    + `<` denotes a wind blowing west
    + `>` denotes a wind blowing east
    + `c` denotes Calypso's island, your starting point
    + `i` denotes Ithaca, the destination
    + `*` denotes an intermediate island

Each “wind” character moves you one cell in the direction of the wind, and winds never form loops (i.e. there is no way to get trapped in a cycle of winds).

You may take input however you want (reading a file, from STDIN, as function parameters etc.)

## Output

Output a truthy value if it is possible to get to Ithaca, and a falsy value if that is not possible.

## Test Cases

```
w=10, h=5
~^~~~~~~~~
~c>>*>>v~~
~v~~v~~v~~
~>>*<~~*>i
~~~v~~~~~~
Expected Output: True
Explanation: Go east, then east again, then east again

```

```
w=8, h=5
~~~~~~~~
~~>>v~~~
<<c~~~~~
~~>~i~~~
~~~~~~~~
Expected Output: False
Explanation: There are two paths that lead to cells neighboring Ithaca,
but there is no wind on those cells.

```

```
w=5, h=2
<c>>>
~v~~i
Expected Output: False
Explanation: Although you can get to a distance of one cell away from
Ithaca, the wind on that cell is eastward which pushes Odysseus
off the map instead of to Ithaca.

```

```
w=20, h=6
~~~~~~~~~~~~~~~~~~~~
~~v<<<<<<*<<>>>v>~~~
~~i~<<*<<<<c~~~*~~~~
~~~~~~^~~~~v~~~^~~~~
~~~~~~<<*>>>>>>^~~~~
~~~~~~~~~~~~~~~~~~~~
Expected Output: True
Explanation: North, then West

```

```
w=20, h=6
~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~*<<>>>v>~~~
~~i<v<*<<<<c~~~*~~~~
~~~~v~^~~~~v~~~^~~~~
~~~~v~<<*>>>>>>^~~~~
~~~~v~~~~~~~~~~~~~~~
Expected Output: False
Explanation: Although there is a wind leading to Ithaca, it is inaccessible.

```

Standard loopholes are prohibited. This is , so the shortest solution in bytes in each language wins.

# Answer
# Python 3.8 (pre-release), 176 bytes

```
lambda w,h,b:b.find('i')in(r:={b.find('c')})|{r.update(*([{(d:={'<':i-1,'>':i+1,'^':i+~w,'v':i-~w}).get(b[i],i)},{*d.values()}][b[i]in'*c']for i in r if-1<i<len(b)))for _ in b}

```

Try it online!

Ungolfed

```
def f(w,h,b):
  r = {b.find('c')}
  for _ in b:
    for i in list(r):
      if 0 <= i < len(b):
        d = {'<':i-1,'>':i+1,'^':i-w-1,'v':i+w+1}
        if b[i] in '*c':
          r.update(d.values())
        r.add(d.get(b[i],i))
  return b.find('i') in r

```
> 8 votes

# Answer
# JavaScript (Node.js), ~~178~~ ~~173~~ ~~171~~ 168 bytes

```
s=>!/i/.test(s.map((_,i)=>_.map((_,j)=>_=='c'&&g(j,i,668)),g=(x,y,w)=>w--&&g(x,y,w>>3,w%=8,x+=--w%2,b=s[y+=--w%2]||0,b[x]=c='*<^>v'.indexOf(b[x]),~c&&g(x,y,c||668)))+s)

```

Try it online!

Treat destination as glory hole
> 7 votes

# Answer
# Python 3, 361 bytes

```
e=enumerate
d={"^":(0,-1),"v":(0,1),"<":(-1,0),">":(1,0),"~":(0,0)}
def f(g,x=e,y=0,V=[]):
	if x==e:x,y=[(x,y)for y,r in e(g)for x,c in e(r)if c=="c"][0]
	if(x,y)in V or x<0 or x>=len(g[0])or y<0 or y>=len(g):return 0
	v=g[y%len(g)][x%len(g[0])]
	if v in d:a,b=d[v];return f(g,x+a,y+b,V+[(x,y)])
	return v=="i"or any(f(g,x+j,y+k,V+[(x,y)])for j,k in d.values())

```

Try it online!

-26 bytes thanks to l4m2
> 5 votes

# Answer
# Charcoal, 59 bytes

```
ＷＳ⊞υιυＷ№ＫＡiＦＬυＦＬ§υ⁰«Ｊλκ¿⁼iＫＫ«ＵＭＫＶ⎇№⁺c*§v<^>νμiμ~»»≔¬№ＫＡcθ⎚θ

```

Try it online! Link is to verbose version of code. Doesn't bother with the dimensions, just takes a newline terminated list of strings for the map. Explanation:

```
ＷＳ⊞υιυ

```

Input the map and print it to the canvas.

```
Ｗ№ＫＡi

```

Repeat while there are still potential source squares.

```
ＦＬυＦＬ§υ⁰«

```

Loop over all squares of the map.

```
Ｊλκ¿⁼iＫＫ«

```

If the current square is a potential source square, then...

```
ＵＭＫＶ⎇№⁺c*§v<^>νμiμ

```

... mark adjacent squares that can move to the current square as potential source squares, and...

```
~»»

```

... mark this square as seen.

```
≔¬№ＫＡcθ

```

Record whether the initial square was found to be a potential source square.

```
⎚θ

```

Clear the canvas and output the result.
> 5 votes

# Answer
# JavaScript (ES6), 114 bytes

As suggested by @tsh, we can save many bytes if we take the grid as an array of characters (with line-feeds) along with its width.

Expects `(width)(grid)`. Returns `0` or `1`.

```
w=>g=(m,p=m.indexOf('c'),c=m[p])=>c=='i'|[m[p]=0,1,2,3].some(i=>"<^>v"[i]==c|c=='*'|c=='c'&&g(m,--i%2+p-~-i%2*~w))

```

Try it online!

---

# JavaScript (ES6),  ~~148~~  143 bytes

*Saved 5 bytes thanks to @l4m2*

Expects a matrix of characters. The dimensions are ignored. Returns `0` or `1`.

```
f=(m,y=m.findIndex(r=>i=~r.indexOf('c')),x=~i,c=(r=m[y]||0)[x])=>c=='i'|[r[x]=0,1,2,3].some(i=>"^<v>"[i]==c|c<'+'|c=='c'&&f(m,y+--i%2,x+~-i%2))

```

Try it online!

### Commented

```
f = (                     // f is a recursive function taking:
  m,                      //   m[] = input matrix
                          //   (x, y) = current position with:
  y = m.findIndex(r =>    //     y initialized to the index of the row r[] ...
    i = ~r.indexOf('c')   //     ... which contains 'c' at position ~i
  ),                      //
  x = ~i,                 //     x initialized to ~i
  c = (                   //   c = character at (x, y),
    r = m[y] || 0         //       or undefined if we're out of bounds
  )[x]                    //
) =>                      //
  c == 'i' |              // success if c == 'i'
  [r[x] = 0, 1, 2, 3]     // invalidate r[x]
  .some(i =>              // for i = 0 to i = 3:
    "^<v>"[i] == c |      //   if c is equal to the character for this direction
    c < '+' |             //   or c is '*' (intermediate island)
    c == 'c' &&           //   or c is 'c' (starting point):
      f(                  //     do a recursive call:
        m,                //       pass m[]
        y + --i % 2,      //       add dy to y
        x + ~-i % 2       //       add dx to x
      )                   //     end of recursive call
  )                       // end of some()

```
> 5 votes

# Answer
# Python 2, ~~234~~ ~~201~~ 198 bytes

Full program, outputs by exit code. Started out as a golf of hyper-neutrino's answer.

-9 bytes thanks to l4m2!

```
g=input()
W=len(g[0])
a=[divmod(`g`.find("c")-2,W+4)]
for y,x in a:A,B,C,D,E,F=map(((g+["~"*W])[y]+"~")[x].__eq__,"><v^~i");a+={(y+a%3+1/~-F,x+a/3-1)for a in{3+3*A-3*B-~C-D}-{4-E}or[3,5,1,7]}-set(a)

```

Try it online!
> 4 votes

# Answer
# , ~~232~~ ~~230~~ ~~203~~ 198 bytes

```
f=function(m,p=which(m=="c",T))`if`(sd(!p|p>dim(m)),F,{x=regexpr(m[p],"><^v*c~i",f=T)
m[p]="~"
d=matrix(c(1:-1,0,0,-1:1),2)
`if`(x>6,x-7,`if`(x>4,any(apply(d,2,function(e)f(m,p+e))),f(m,p+d[,x])))})

```

Try it online!

Recursive function expecting the map as a character matrix.

**How?**

```
possible_to_get_to_ithaca=
f=function(m,               # recursive function f, m=map as a matrix
    p=which(m=="c",T)){     # p=current position, initialized to position of 'c'
    if(any(p<1|p>dim(m)))   # if p is off the map, return FALSE
      return(F)
    x=m[p]                  # set x to contents of current position
    m[p]="~"                # and set the current position to "~" to stop backtracking
    if(x=="i")return(T)     # if x is "i" then we've arrived: return TRUE
    if(x=="~")return(F)     # if x is "~" then we're becalmed: return FALSE
    if(x=="*"|x=="c"){      # if x is an island, try all 4 directions
      return(any(
        apply(cbind(a<-c(0,0,1,-1),rev(a)), # matrix of all 4 possible offsets
          1,function(b)     # try each offset b
          f(m,p+b))))       # recursive call to f with new position p
    } else                  # else move with the wind
      return(               # recursive call to f with p offset by wind
        f(m,p+c((x==">")-(x=="<"),(x=="v")-(x=="^"))))
}

```
> 4 votes

# Answer
# Scala, 319 bytes

It can be golfed more.

A port of @gsitcia's answer.

Try it online!

```
def f(w:Int,h:Int,b:String)={val r=mutable.Set(b.indexOf('c'));b.foreach(_=>r++=r.toList.filter(i=> 0<=i && i<b.length).flatMap(i =>{val d = Map('<' -> (i - 1), '>' -> (i + 1), '^' -> (i - w - 1), 'v' -> (i + w + 1)); if (b(i) == '*' || b(i)== 'c') d.values else List(d.getOrElse(b(i),i))}));r.contains(b.indexOf('i'))}

```

Ungolfed version:

```
import scala.collection.mutable

object TestCases {
  val cases = List(
    (10, 5, """\
      |~^~~~~~~~~
      |~c>>*>>v~~
      |~v~~v~~v~~
      |~>>*<~~*>i
      |~~~v~~~~~~""".stripMargin, true),
    (8, 5, """\
      |~~~~~~~~
      |~~>>v~~~
      |<<c~~~~~
      |~~>~i~~~
      |~~~~~~~~""".stripMargin, false),
    (5, 2, """\
      |<c>>>
      |~v~~i""".stripMargin, false),
    (20, 6, """\
      |~~~~~~~~~~~~~~~~~~~~
      |~~v<<<<<<*<<>>>v>~~~
      |~~i~<<*<<<<c~~~*~~~~
      |~~~~~~^~~~~v~~~^~~~~
      |~~~~~~<<*>>>>>>^~~~~
      |~~~~~~~~~~~~~~~~~~~~""".stripMargin, true),
    (20, 6, """\
      |~~~~~~~~~~~~~~~~~~~~
      |~~~~~~~~~*<<>>>v>~~~
      |~~i<v<*<<<<c~~~*~~~~
      |~~~~v~^~~~~v~~~^~~~~
      |~~~~v~<<*>>>>>>^~~~~
      |~~~~v~~~~~~~~~~~~~~~""".stripMargin, false),
    (2, 2, """\
      |ci
      |>>""".stripMargin, true)
  )
}

object Main {
  def f(w: Int, h: Int, b: String): Boolean = {
    val r = mutable.Set(b.indexOf('c'))
    for (_ <- b) {
      for (i <- r.toList) {
        if (0 <= i && i < b.length) {
          val d = Map('<' -> (i - 1), '>' -> (i + 1), '^' -> (i - w - 1), 'v' -> (i + w + 1))
          if (b(i) == '*' || b(i) == 'c') {
            r ++= d.values
          }
          r += d.getOrElse(b(i), i)
        }
      }
    }
    r.contains(b.indexOf('i'))
  }

  def main(args: Array[String]): Unit = {
    var success = true

    for ((w, h, b, c) <- TestCases.cases) {
      if (f(w, h, b) != c) {
        if (!success) println()
        println("Test Failed!")
        println(s"w=$w, h=$h, $c")
        println(b)
        success = false
      }
    }
    if (success) {
      println("All tests passed!")
    }
  }
}

```
> 0 votes

---
Tags: code-golf, grid, path-finding
---