title: Missile-mounted cameras

text:
# Question
Title: Missile-mounted cameras
You are employed as Administrator in charge of Road Maintenance and Planning. The intelligence division of the Agency for Road Maintenance and Planning has come up with a brilliant and not at all inefficient way to take random sample pictures of the roads: missiles with cameras on them.

In this genius and not at all wasteful technique, smart non-explosive missiles are sent hurtling down each road. Each missile moves in a straight line and captures images at equal spatial intervals. Eventually the Agency will get a good overall sample of the state of affairs for each road. On Masagaki Road, for example, images are captured at positions 1, 4, 5, 6, 8, 11, 12 and 14:

`1 X X 4 5 6 X 8 X X 11 12 X 14` (X represents no image)

Your job is to find the largest number of images that could have been captured by the camera on a single missile. A single camera could have captured the three images at positions 4, 5, 6 (having a spacing of 1); the three images at positions 4, 6, 8 (spacing 2); or the three images at 4, 8, 12 (spacing 4). However, here the answer is four: positions 5, 8, 11, 14 (spacing 3).

**Input:** a sequence of \\$1\leq n\leq1000\\$ unique integers, each satisfying \\$1\leq i\leq1000000\\$, representing the positions of the images captured for a certain road. These will be given from smallest to largest.

**Output:** a single integer representing the largest number of images that could have been captured by a single camera.

## Sample 1

Input: `1 4 5 6 8 11 12 14`

Output: `4`

## Sample 2

Input: `5 8 9 10 12 15 16 17`

Output: `3`

---

* ; the shortest code in bytes wins.
* The linked rules apply.
* Please explain your code.
* Please link to Try It Online! or another online demo.

---

Inspired by 'Air Drop' (AIO 2007, Senior)

# Answer
> 9 votes
# Python 2, 74 bytes

```
lambda l:max(reduce(lambda i,x:i+(a+i*(b-a)==x),l,0)for a in l for b in l)

```

Try it online!

Tries every possible sequence of the form `a,b,...` with `a` and `b` in the input `l`.

To find the smallest index `i` of this arithmetic progression that's outside `l`, we do something a bit unusual. Instead of counting up the progression to find an element not in `l`, we iterate over `l`, taking advantage of it being sorted. For each successive element `x` of `l`, we move to the next index in the arithmetic progression if its current value matches `x`, and stay at the current index otherwise.

# Answer
> 7 votes
# 05AB1E, 8 bytes

```
æʒ¥Ë}€gà

```

Try it online!

```
æ          # power set
 ʒ  }      # filtered by:
  ¥        #  deltas
   Ë       #  all equal
     €g    # length of each
       à   # maximum

```

# Answer
> 3 votes
# Python 2, 98 bytes

```
f=lambda l,i=1:i/l[-1]or max(f(l,i+1),*[g(a,l,i)for a in l])
g=lambda a,l,i:a in l and-~g(a+i,l,i)

```

Try it online!

A function that takes in a list of integers and returns the max number of images

**Approach**: Try for each element `a` in the list, and for each increment `i` in the range `1` to `max(l)`.

# Answer
> 3 votes
# Charcoal, 22 bytes

```
Ｉ⊟Φ⊕Ｌθ⊙θΦ⌈θ¬⁻⁺×…⁰ι⊕νλθ

```

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

```
     θ                  Input array
    Ｌ                   Length
   ⊕                    Incremented
  Φ                     Filter over implicit range
       θ                Input array
      ⊙                 Any element where
          θ             Input array
         ⌈              Maximum
        Φ               Filter over implicit range where
               …⁰ι      Range of length given by outer index
              ×   ⊕ν    Multiplied by incremented inner index
             ⁺      λ   Offset by selected element
            ⁻        θ  Set difference with input array
           ¬            Is empty (i.e. this is a subset)
 ⊟                      Take the last (i.e. highest) element
Ｉ                       Cast to string for implicit print

```

The second `Φ` would be  except Charcoal doesn't support this.

# Answer
> 2 votes
# Red, 127 bytes

```
func[b][m: 0 repeat s t: last b[n: 1 forall b[d: s until[either
find b b/1 + d[n: n + 1][m: max n m n: 1 d: t]t < d: d + s]]]m]

```

Try it online!

Naive imperative solution.

## Explanation:

```
f: func [b][
    m: 0                                 ; the max number of images so far
    repeat s t: last b [                 ; s (for step) is a list 1..last
        n: 1                             ; current max
        forall b [                       ; iterate over the input
            d: s                         ; current step
            until [                      ; and do the following :
                either find b b/1 + d [  ; if there is a number in the list that is equal
                                         ; to the current number + the current step
                    n: n + 1             ; increase the current max
                ][                       ; else
                    m: max n m           ; update max,
                    n: 1                 ; reset current max
                    d: t                 ; and set the current step at the last number
                ]
                t < d: d + s             ; until current step is beyond the last number
            ]

        ]
    ]
    m                                    ; return max
]

```

# Answer
> 2 votes
# JavaScript (ES6), 89 bytes

```
A=>A.reduce((a,x)=>[...a,...a.map(y=>x-2*y[0]+y[1]?y:(b+=!!y[b],[x,...y]))],[[]],b=0)|b+1

```

Try it online!

### Commented

```
A =>                  // A[] = input array
  A.reduce((a, x) =>  // for each value x in A[],
                      // using a[] as the previous list of lists:
    [                 //   build a new list of lists:
      ...a,           //     append all previous lists stored in a[]
      ...a.map(y =>   //     for each list y[] in a[]:
        x -           //       if both y[0] and y[1] are defined
        2 * y[0] +    //       and (x - y[0]) is not equal
        y[1] ?        //       to (y[0] - y[1]):
          y           //         leave y[] unchanged
        :             //       else:
          ( b +=      //         increment b if:
              !!y[b], //           y[b] is defined (i.e. the length of y[] is b+1)
            [x, ...y] //         prepend x to y[]
          )           //
      )               //     end of map()
    ],                //   end of the new list of lists
    [[]],             //   start with a[] containing a single empty list
    b = 0             //   start with b = 0
  )                   // end of reduce()
  | b + 1             // return b + 1

```

# Answer
> 1 votes
# Perl 5, 111 bytes

```
$_=max(map{$j=$_;(grep{(reduce{$a.(' 'x(-1+$b-length$a)).'x'}@F)=~join'.'x$j,('x')x$_}1..$F[-1])[-1]}0..$F[-1])

```

Try it online!

# Answer
> 1 votes
# Jelly, 8 bytes

```
ŒPIE$ƇṪL

```

A monadic Link accepting a list which yields an integer.

**Try it online!**

### How?

We are looking for the longest sub-sequence which has equal incremental differences, this just filters all sub-sequences in length order and takes the length of the last one.

```
ŒPIE$ƇṪL - Link: list of numbers
ŒP       - powerset (all sub-sequences ordered by length)
    $    - last two links as a monad:
  I      -   incremental differences (e.g. [4, 7, 11] -> [7-4,11-7] = [3,4])
   E     -   all equal?
      Ṫ  - tail
       L - length

```

# Answer
> 0 votes
# Erlang (escript), 102 bytes

Port of xnor's Python 2 answer.

```
f(R)->lists:max([lists:foldl(fun(X,I)->I+(case A+I*(B-A)==X of true->1;_->0 end)end,0,R)||A<-R,B<-R]).

```

Try it online!

---
Tags: code-golf, number, sequence, integer
---


# Question
Title: Determine the lexicographical permutation your code is in
~~Write a program that outputs the number 0.~~

That's a bit trivial, isn't it?

Let's sort all distinct permutations of your code in lexicographical order. When **any** of these codes are run, it should output the its location in the array (0-indexed or 1-indexed).

This means that your code must be the lexicographically smallest permutation of your code possible.

For example, if your code is `ABB`, then `ABB` -\> 0; `BAB` -\> 1; `BBA` -\> 2.

## Rules

* Out of all distinct permutations of your code, it must be the lexicographically smallest.
* Your program must be at least **3** bytes long.
* "Output" represents any acceptable output: on the stack, to STDOUT, as a return value, as an exit code, etc.
* Your program is to not take any form of input.
* This is , so **longest** code wins.

# Answer
# brainfuck, bytes = score

```
...

```

Try it online!

**How it works**: this program only has one distinct permutation and it outputs 0. It trivially satisfies all the other restrictions. The score can be made arbitrarily large by adding more `.`.
> 5 votes

# Answer
# Python 2, score = arbitrary

```
000

```

Try it online!

Returns through exit code, which is always `0`.
The source code is `0` repeated arbitrary many times. Since there's only 1 permutation of the source code, the permutation number is always `0`.
> 4 votes

# Answer
# !@#$%^&\*()\_+, 548+++ bytes

```
#^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

```

Try it online!

This can also be just`#^^`. # prints and ^ increments. Please tell me if this is not lexicographic order, instead of downvoting.
> 4 votes

# Answer
# dc, Arbitrarily large number of bytes.

```
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

```

Try it online!

No matter how many `0`s you write, it will leave a `0` on the stack, which is an acceptable output form for the challenge. (The `p` in the TIO footer prints the stack so you can see what it is.)

Of course, the only permutation is the program itself.
> 2 votes

# Answer
# MathGolf, 3 bytes (3 distinct permutations)

Outputs via unary, with a different set of output: `2 -> 3 -> 4`.

```
00\

```

Try it online!

## Explanation

```
00\
00  Push 2 0's
  \ Swap (resuting in 2 0's)

0\0
0   Push 0
 \  Swap
  0 Push 0 (3 0's)

\00
\   Swap the empty stack (appends 2 0's)
 0  Push 0
  0 Push another 0 (resulting in 4 0's)

```
> 1 votes

---
Tags: source-layout, code-bowling
---


title: Add Numbers deux — Bitwise Addition

text:
# Question
Title: Add Numbers deux — Bitwise Addition
Your job is to implement bitwise addition.

To ensure that this is done, you will compute and print the result of addition without carry (or bitwise XOR). Then, you will compute the carry of the addition (bitwise AND) and multiply it by two (bitwise left shift). If the carry is nonzero, then you add the carry and the previous result until the carry is zero, at which point you stop producing output. If all is done correctly, the final result printed should be the sum of the two integers that you received as input.

Here's an ungolfed reference implementation in C:

```
#include <stdio.h>

void print_add(unsigned a, unsigned b)
{
    unsigned carry;

    while(b)
    {
        carry = a & b;
        a ^= b;
        printf("%u\n", a);
        b = carry << 1;
    }
}

```

## Input

Two positive integers in any convenient format.

## Output

A list of positive integers in any convenient format representing each result of addition without carry. Leading/trailing whitespace/newlines are allowed.

## Rules

## Testcases

```
1, 1 -> 0, 2
3, 17 -> 18, 16, 20
6, 7 -> 1, 13
21, 19 -> 6, 36, 32, 40
10, 9 -> 3, 19
20, 20 -> 0, 40

```

Your code must work for at least all pairs of positive integers that your integer type can represent the sum of.

# Answer
# JavaScript (ES6), 34 bytes

Takes input as `(A)(B)`, where `A+B` is a positive-looking 32-bit integer, i.e. less than 0x80000000.

Returns an array.

```
A=>g=B=>B?[A^=B,...g((B&~A)*2)]:[]

```

Try it online!

Or for **35 bytes**, a BigInt version with unlimited input:

```
A=>g=B=>B?[A^=B,...g((B&~A)*2n)]:[]

```

Try it online!

### How?

In order to use only 2 variables and pass a single variable to the recursive function, we apply the XOR right away to `A` and prepend the result to the output array.

Instead of computing `(A AND B) * 2`, we now need to compute `(B AND (A XOR B)) * 2`. Fortunately this can also be expressed as:

```
(B AND (NOT A)) * 2

```

leading to the rather short `(B&~A)*2` in JS syntax.
> 5 votes

# Answer
# sed -En, 120 bytes

```
:L;s/0(.{8})0/a\1a/;s/0(.{8})1/b\1a/;s/1(.{8})0/b\1a/;s/1(.{8})1/a\1b/;tL;y/ab /01\
/;P;s/$/0/;tM;:M;s/\
.(.*1)/\
\1/;tL

```

Try it online!

Or try all the test cases online!

Input: Two 8-bit integers written in binary (on one line, with a space in between them).

Output: Also 8-bit binary numbers.

For convenience this is written for 8-bit integers, but if you want to use 32-bit integers, for instance, just change the instances of `8` in the script to `32`. You can try out the 32-bit version here.
> 5 votes

# Answer
# C (gcc), ~~65~~ \\$\cdots\\$ ~~46~~ 45 bytes

Saved 5 bytes thanks to ceilingcat!!!

```
f(a,b){for(;b;b&=~a,b*=2)printf("%d ",a^=b);}

```

Try it online!
> 4 votes

# Answer
# Bash, ~~69~~ \\$\cdots\\$ ~~56~~ 45 bytes

11 bytes less, thank to Mitchell Spector!

```
d()(echo $[a=$1^$2];((c=$1&$2))&&d $a $[c*2])

```

Try it online!

Commented long version:

```
# Defines function d with parenthesis sub-shell block (commands), rather than
# curly-braces commands block, to save leading space and trailing semicolons.
d ()
(
  # Print and assign new value, using deprecated $[expression] syntax, rather
  # than modern's $((expression)) syntax, saves 2 bytes.
  echo $[a=$1^$2]
  # Bash stand-alone arithmetic expression's return-code, conditions recursive
  # call, with argument 2 computed inline, using deprecated but shorter
  # arithmetic expression.
  ((c=$1&$2)) && d $a $[c*2]
)

```

Note that the shorter but deprecated `$[expression]` syntax is going to be removed in later Bash versions.

See: `man bash` Bash 5.0.3(1)-release

> Arithmetic expansion allows the evaluation of an arithmetic expression and the substitution of the result.
>
> The format for arithmetic expansion is:
>
> ```
> $((expression))
> ```
>
> The old format `$[expression]` is deprecated and will be removed in upcoming versions of bash.

See also: bug-bash ML:

On Sun, Apr 8, 2012 at 12:50 AM, Linda Walsh wrote:

> Re: status on $\[arith\] for eval arith vsl $((arith))?? ... Some linux distributions patch the man page and document $\[ \] as deprecated.
>
> The SUS rationale says:
>
> In early proposals, a form $\[expression\] was used. It was functionally equivalent to the "$(())" of the current text, but objections were lodged that the 1988 KornShell had already implemented "$(())" and there was no compelling reason to invent yet another syntax. Furthermore, the "$\[\]" syntax had a minor incompatibility involving the patterns in case statements.
> 4 votes

# Answer
# Python 2, 39 bytes

```
def f(a,b):1/b;print a^b;f(a^b,(a&b)*2)

```

Try it online!

A recursive function that prints all intermediate values, then terminates with an exception.

---

# Python 2, 41 bytes

```
f=lambda a,b:b*[0]and[a^b]+f(a^b,(a&b)*2)

```

Try it online!

A recursive function that takes in two summands and returns a list of intermediate results.
> 3 votes

# Answer
# Jelly,  ~~12~~  11 bytes

```
&/Ḥṭ^/ƲƬḢ€Ḋ

```

A monadic Link accepting a list of two integers which yields a list of integers.

**Try it online!**

### How?

Note that at the end of proceedings we'll have the sum and a carry of zero, and if we were to compute the addition without carry and the carry once more we'd get the same results, so we can keep going until `[sum-without-carry, carry]` does not change...

```
&/Ḥṭ^/ƲƬḢ€Ḋ - Link: list of two integers, [a,b]
       Ƭ    - Collect up (starting with [a,b]) while results are distinct applying:
      Ʋ     -   last four links as a monad:
 /          -     reduce (current pair, [x,y]) by:
&           -       bitwise AND
  Ḥ         -     double
     /      -     reduce (current pair, [x,y]) by:
    ^       -       bitwise XOR
   ṭ        -     tack -> [x^y, (x&y)*2]
        Ḣ€  - head each
          Ḋ - dequeue (remove a from the front)

```
> 3 votes

# Answer
# MATL, 13 bytes

```
`Z~t1MZ&Et]xx

```

Try it online! Or verify all test cases.

### Explanation

```
`       % Do...while
  Z~    %   Bitwise XOR. Takes the two inputs implicitly the first time
  t     %   Duplicate
  1M    %   Push the inputs of the latest bitwise XOR again
  Z&    %   Bitwise AND
  E     %   Multiply by 2
  t     %   Duplicate. This copy will be used as loop condition
]       % End. If the top of the stack is not 0 a new iteration is run
xx      % Delete top two elements (a 0 from the last bitwise AND and a
        % copy of the result from the last bitwise XOR)
        % Implicitly display

```
> 3 votes

# Answer
## Batch, 68 bytes

```
@if %2==0 exit/b
@set/a"a=%1^%2,b=(%1&%2)*2
@echo %a%
@%0 %a% %b%

```

Explanation:

```
@if %2==0 exit/b

```

Repeat until `b` is zero.

```
@set/a"a=%1^%2,b=(%1&%2)*2

```

Calculate the XOR and the carry.

```
@echo %a%

```

Output the next result.

```
@%0 %a% %b%

```

Restart with the new operands.
> 3 votes

# Answer
# Rust, ~~69~~ 68 bytes

```
|mut a:u8,mut b:u8|while b>0{let c=(a&b)*2;a^=b;b=c;print!("{} ",a)}

```

A port of math junkie's python answer.

Try it on Rust Playground.

I had to use a temporary variable because destructuring in assignments is still being worked on
> 3 votes

# Answer
# Python 2, 44 43 bytes

-1 byte thanks to @SurculoseSputum

```
a,b=input()
while b:a,b=a^b,(a&b)*2;print a

```

Try it online!

Very simple implementation. Pretty much a golfed version of the reference code.
> 2 votes

# Answer
# Javascript ES6, 48 chars, uint32 full support

```
a=>b=>{for(;b;alert(a>>>0))[a,b]=[a^b,(a&b)<<1]}

```

Test with `console.log` instead of alert:

```
f=a=>b=>{for(;b;console.log(a>>>0))[a,b]=[a^b,(a&b)<<1]}

g=(x,y,...res)=>console.log(`=== ${x} ${y} => ${res} ===`)+f(x)(y)

g(2147483648, 2147483648, 0)
g(3000000000, 1, 3000000001)
g(2147483648, 0)
g(1, 1, 0, 2)
g(3, 17, 18, 16, 20)
g(6, 7, 1, 13)
g(21, 19, 6, 36, 32, 40)
g(10, 9, 3, 19)
g(20, 20, 0, 40)
```

```
.as-console-wrapper.as-console-wrapper { max-height: 100vh }
```

# Javascript ES6, 43 chars, int32 except 2\**32

```
a=>b=>{for(;b;alert(a))[a,b]=[a^b,(a&b)*2]}

```

Test with `console.log` instead of alert:

```
f=a=>b=>{for(;b;console.log(a))[a,b]=[a^b,(a&b)*2]}

g=(x,y,...res)=>console.log(`=== ${x} ${y} => ${res} ===`)+f(x)(y)

g(2147483648, 2147483648, 0, 'never')
g(3000000000, 3000000000, 0, 1705032704)
g(3000000000, 1, 3000000001)
g(2147483648, 0)
g(1, 1, 0, 2)
g(3, 17, 18, 16, 20)
g(6, 7, 1, 13)
g(21, 19, 6, 36, 32, 40)
g(10, 9, 3, 19)
g(20, 20, 0, 40)
```

```
.as-console-wrapper.as-console-wrapper { max-height: 100vh }
```

# Javascript ES 2020, 44 chars, infinite integers

```
a=>b=>{for(;b;alert(a))[a,b]=[a^b,(a&b)*2n]}

```

Test with `console.log` instead of alert:

```
alert=x=>console.log(x+"")

f=a=>b=>{for(;b;alert(a))[a,b]=[a^b,(a&b)*2n]}

g=(x,y,...res)=>console.log(`=== ${x} ${y} => ${res} ===`)+f(x)(y)

g(2147483648n, 2147483648n, 0, 4294967296)
g(3000000000n, 3000000000n, 0, 6000000000)
g(3000000000n, 1n, 3000000001)
g(2147483648n, 0)
g(1n, 1n, 0, 2)
g(3n, 17n, 18, 16, 20)
g(6n, 7n, 1, 13)
g(21n, 19n, 6, 36, 32, 40)
g(10n, 9n, 3, 19)
g(20n, 20n, 0, 40)
```

```
.as-console-wrapper.as-console-wrapper { max-height: 100vh }
```
> 2 votes

# Answer
# Charcoal, 24 bytes

```
ＮθＮηＷη«≧＆θη≔⁻｜θιηθ≦⊗η⟦Ｉθ

```

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

```
ＮθＮη

```

Input `a` and `b`.

```
Ｗη«

```

Repeat while `b` is non-zero. This also makes a copy of `b`.

```
≧＆θη

```

Bitwise And `b` with `a`.

```
≔⁻｜θιηθ

```

Bitwise Or `a` with the copy of `b`, and subtract the above value, thus replacing `a` with the Bitwise Xor of `a` and `b`.

```
≦⊗η

```

Bitwise left shift `b` as it is now the carry.

```
⟦Ｉθ

```

Output the value of `a` on its own line.
> 2 votes

# Answer
# C# (Visual C# Interactive Compiler), 48 bytes

```
(a,b,c,d)=>{for(;b>0;c=a&b,d.Add(a^=b),b=c<<1);}

```

Try it online!

This is my first time using a for loop to do operations within the actual iterator, which feels weird, and uncomfortable, but also calming.

Mostly just tried to play with the reference, and make it more compact. Will be returning to this later. Need to double check my answer is fully legal (using the List), but this is my initial attempt.

More Info:

```
(a,b,c,d)=>{         //Pass in variables via lambda expression, and now a  for loop
                     //Note, the c# for statement format is:
                     //for (initializer; condition; iterator)
                     ////body
                     //
    for(             //Start of for loop statement
        ;            //A mustache... jk. I am using no initializers, so just a ";" - totally blank
        b>0;         //My for loop conditional.  I used an int rather than a c bool, which is not as compact, maybe there's a better way
                     //For loop Iterators:
        c=a&b,       //c is carry
        d.Add(a^=b), //Append to end of list: a equals a xor b
        b=c<<1       //left shift
    )                //End Initializers, condition, and iterator parts of for loop
    ;                //Body of for loop (nothing)
}                    //End lambda expression

```
> 2 votes

# Answer
# Java (JDK), 54 bytes

```
(a,b)->{for(;b>0;b=(b&~a)*2)System.out.println(a^=b);}

```

Try it online!
> 2 votes

# Answer
# 05AB1E, 12 bytes

```
Δ`^=y`&D_#·)

```

Try it online!
> 2 votes

# Answer
# K4, ~~32~~ 31 bytes

**Solution:**

```
1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\

```

**Examples:**

```
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\1 1
0 2
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\3 17
18 16 20
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\6 7
1 13
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\21 19
6 36 32 40
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\10 9
3 19
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\20 20
0 40

```

**Explanation:**

Lots of eaches...

```
1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\ / the solution
    (                        )\ / iterate
                        0b\:'   / convert each into into binary
                     @\:        / apply (@) each-left (\:) function to right
             (   ;  )           / two item list
                  &/            / AND
              ~=/               / XOR
         2/:'                   / convert each from binary
     1 2*                       / multiply first item by 1, 2nd by 2
   +                            / flip
  *                             / first
1_                              / drop first element

```
> 1 votes

---
Tags: code-golf
---


# Question
Title: Multiple, Lit Plume, Mute Pill and so on
We say two positive integers are *anagrams* of each other if the digits in one of them (in decimal representation) can be rearranged to form the other. Leading zeros don't count. For example, 110020222 is an anagram of 212102020, but not of 221100011; neither is 22002211 even though it can be written as 022002211.

Interestingly enough, every arithmetic sequence of positive integers contains arbitrarily large sets of elements, all anagrams of each other. In this challenge, we use a special case of this fact.

### Task

For this challenge, you have to write a program or function in a language of your choice, that takes as input two positive integers: `k` and `N`, and outputs `N` *different* positive integers, all of which are multiples of `k` and anagrams of each other.

### Rules

* You can assume `N` is bigger than 1.
* Input and output can be taken in any of the standard ways.
* Standard loopholes are forbidden.
* Output may contain spaces and newlines.

### Winning Criterion

This is , so shortest code in bytes wins.

### Examples

Note that there are more than one possible output (infinitely many, in fact) given any `k` and `N`. Here are some examples:

```
  k  |   N   |  Possible output
-----+-------+------------------
  9  |   4   |  234
     |       |  243
     |       |  342
     |       |  432
-----+-------+------------------
 351 |   6   | 142857
     |       | 428571
     |       | 285714
     |       | 857142
     |       | 571428
     |       | 714285

```

# Answer
> 21 votes
# Python 2, 48 bytes

```
lambda k,N:[k*(10**N**k+10**i)for i in range(N)]

```

Try it online!

For example, `k=12,n=4` produces this list of numbers, written out in lines for clarity, with the `...`'s hiding a big string of zeroes:

```
1200...0000012
1200...0000120
1200...0001200
1200...0012000

```

So, we have a prefix of `k`, followed by another `k` in a position that moves one place left each time, and the rest zeroes. We need the prefix because leading zeroes aren't allowed for the anagrams, so we make it so that all the outputs have the same number of digits.

We leave enough zeroes to ensure that the right string to never bump into the left one. `N**k` zeroes more than suffices for this, giving extremely big numbers; `N+k` or even `N+log_10(k)` would be enough. Note that Python right-associates `10**N**k` as `10**(N**k)`.

Unfortunately this variable bound doesn't lend well to recursive solutions that update `k` as they go. An upper bound on how big `k` can be, even if enormous, would simplify this.

# Answer
> 6 votes
# , 18 bytes

```
10#.[,.[}.[*=@i.@+

```

Try it online!

xnor's wonderful technique, adapted for J. Be sure to upvote him.

### explanation

Taking n=4, k=12 as an example, we notice that...

```
12 0 0 0 0 0 0 0 0 0 0 0 0 12  0  0  0
12 0 0 0 0 0 0 0 0 0 0 0 0  0 12  0  0
12 0 0 0 0 0 0 0 0 0 0 0 0  0  0 12  0
12 0 0 0 0 0 0 0 0 0 0 0 0  0  0  0 12

```

is actually just 12 zipped with a (12 + 4) x (12 + 4) identity matrix, multiplied by 12, with the first 12 rows chopped off.

Then we convert back to numbers with `10#.`

# Answer
> 3 votes
# 05AB1E, 8 bytes

```
m°IL<°+*

```

Port of *@xnor*'s Python 2 answer, so make sure to upvote him!!

Try it online.

A more original (although extremely slow) approach, is this **11-byter**:

```
∞*æIù.Δ€{íË

```

Try it online. (Will time out if \\$N\geq3\\$..)

Both take \\$k\\$ as first input and \\$N\\$ as second.

**Explanation:**

```
m           # Take the 2nd (implicit) input to the power of the 1st (implicit) input: N^k
 °          # Take 10 to the power that: 10^(N^k)
  IL        # Push a list in the range [1, N]
    <       # Decrease it by 1 to make the range [0, N)
     °      # Push 10 to the power for each value: [10^0, 10^1, ..., 10^{N-1}, 10^N]
      +     # Add the earlier 10^(N^k) to each
       *    # And multiply it by the second (implicit) input N
            # (after which the list is output implicitly)

∞           # Push an infinite list of positive integer: [1,2,3,...]
 *          # Multiply each by the first (implicit) input k: [k,2k,3k,...]
  æ         # Take the (lazy) powerset of that infinite list
   Iù       # And only leave the inner lists of a size equal to the second input N
     .Δ     # Find the first inner list which is truthy for:
       €{   #  Sort the digits of each integer in the list
         í  #  in descending order (since we aren't allowed to start with a leading 0)
          Ë #  And check if all are equal
            # (after which the list is output implicitly)

```

# Answer
> 2 votes
# Python 2, 101 bytes

```
k,n=input()
l=[];m=0;s=sorted
while 1:m+=k;l+=m,;t=[x for x in l if s(`x`)==s(`m`)];n==len(t)>exit(t)

```

Try it online!

Generate all multiples `m` of `k`, each time checking if there are `n` anagrams of `m` in the list of current multiples. The result is printed as exit message.

# Answer
> 2 votes
# Retina 0.8.2, 37 bytes

```
^.+
$*0
0(?=.*¶(.+))
$1$`$1$%'¶
¶¶.+

```

Try it online! Takes input in the order `N`, `k`. Uses @xnor's algorithm. Explanation:

```
^.+
$*0

```

Convert `N` to `N` zeros.

```
0(?=.*¶(.+))

```

Match each zero in turn.

```
$1$`$1$%'¶

```

Output `k`, the zeros to the left of this zero, `k` again, then the zeros to the right of this zero.

```
¶¶.+

```

Delete `k`.

Using Retina 1 would save 5 bytes, mostly from the use of `L$` which effectively automatically delets `k`:

```
^.+
*0
L$`0(?=.*¶(.+))
$1$`$1$%'

```

Try it online!

# Answer
> 1 votes
# C (gcc), <sup>~~61~~</sup> 65 bytes

Added 4 bytes to fix a bug kindly pointed out by Kevin Cruijssen.

Uses xnor's idea in his Python answer.

```
i;f(k,n){for(i=0;i<n;)printf("%d%0*d%0*d ",k,n+k+i,k,n+k-i++,0);}

```

Try it online!

# Answer
> 1 votes
# cQuents, 12 bytes

```
&A(t^n^A+t^$

```

Try it online!

Port of xnor's Python answer. Go upvote his answer!

## Explanation

```
              takes two inputs, A n
&             output first n terms in sequence
              each term equals:
 A(           A * (                            )
   t^n^A            10 ** n ** A
        +                        +
         t^$                       10 ** index

```

# Answer
> 1 votes
# APL (Dyalog Classic), 21 bytes

Port of Kevin Cruijssen's 05AB1E answer. Don't forget to upvote him!

```
{⍺×(10*⍵*⍺)+10*¯1+⍳⍵}

```

Try it online!

---
Tags: code-golf, math, number, number-theory
---


title: Generate A065825

text:
# Question
Title: Generate A065825
(This is A065825.) The defaults apply, so you can pick another format other than this one.

Given an input integer `n`, find the smallest number `k` so that there exists an n-item subset of `{1,...,k}` where no three items form an arithmetic progression.

## Procedure

Here, we calculate `A065825(9)`.

We assume you have already looped from 1 to 19, and `k`=20 (it's just an example).

### 1. Generate a range from 1 to k.

```
[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

```

### 2. Pick `n` items from that sequence, following the original order of the sequence.

```
[1 2 6 7 9 14 15 18 20]

```

### 3. No 3 items form an arithmetic progression.

If a sequence has arithmetic progression, it basically means the sequence has the same step between every two consecutive items.

For example, the sequence of positive even numbers (`[2 4 6 8 ...]`) has a consistent step (i.e. `4-2=2`, and `6-4=2`, etc.), so it has arithmetic progression.

The Fibonacci sequence (`[1 1 2 3 5 8 13 21 ...]`) does not have arithmetic progression, since it does not have a consistent step. (`3-2=1`, `5-3=2`, `8-5=3`, etc.)

As an example, let's pick 3 items from our generated sequence.

```
[1 2 6 [7 9 14] 15 18 20]

```

The picked 3-item sequence does not have arithmetic progression, since the differences are respectively `9-7=2` and `14-9=5`.

This has to apply to **every 3-item pair**:

```
[[1 2 6] 7 9 14 15 18 20] (2 -1 =1, 6 -2 =4)
[1 [2 6 7] 9 14 15 18 20] (6 -2 =4, 7 -6 =1)
[1 2 [6 7 9] 14 15 18 20] (7 -6 =1, 9 -7 =2)
[1 2 6 [7 9 14] 15 18 20] (9 -7 =2, 14-9 =5)
[1 2 6 7 [9 14 15] 18 20] (14-9 =5, 15-14=1)
[1 2 6 7 9 [14 15 18] 20] (15-14=1, 18-15=3)
[1 2 6 7 9 14 [15 18 20]] (18-15=3, 20-18=2)

```

Here are some examples of picking non-consecutive items from the output sequence:

```
[1 [2] 6 [7] 9 [14] 15 18 20] (7-2=5,14-7=7)
[[1] 2 6 [7] [9] 14 15 18 20] (7-1=6,9 -7=2)

```

If the above is satisfied for `k`, then `k` is a valid output for `A065825(9)`.

## Test cases

Here is a reference program I use to check my test cases.

```
n       a(n)
1       1
2       2
3       4
4       5
5       9
6       11
7       13
8       14
9       20

```

# Answer
# Jelly, 14 bytes

```
œcœc3IEƇƊÐḟð1#

```

A monadic Link accepting a non-negative integer which yields a non-negative integer.

**Try it online!** (Too inefficient for n=9 within 60s.) Or see the test-suite.

### How?

```
œcœc3IEƇƊÐḟð1# - Link: integer, n
            1# - let k=n and count up to find the first k, for which this is truthy:
           ð   -   dyadic chain - i.e. f(k, n):
œc             -     combinations of length (n) of (implicit [1..k])
         Ðḟ    -     filter discard those n-tuples which are truthy under:
        Ɗ      -       last three links as a monad:
  œc3          -         combinations of length three of (the n-tuple)
     I         -         incremental differences - e.g. [3,6,8]->[6-3,8-6]->[3,2]
       Ƈ       -         filter keep those diffence-pairs which are truthy under:
      E        -           all equal?

```
> 3 votes

# Answer
# Pyth, 17 bytes

```
ff!/#.OZ.cY3.cSTQ

```

Try it online!

`.cSTQ`: generate all list of numbers in the range \[1,T\] with length equal to the input.

`.cY3`: for each of those, generate all length 3 subsequences.

`/#.OZ`: filter for the subsequences where the average is a member of the list. These are the arithmetic progressions.

`f!`: filter for the original lists with no arithmetic progressions

`f`: find the lowest T where at least one list is found.
> 9 votes

# Answer
# Python 3.8, ~~123~~ ~~115~~ ~~96~~ 94 bytes

Another ~~-15~~ -17 bytes thanks to Surcolose Sputum!

```
f=lambda n,k=1:len(d:=f'{k:b}')*all(k>>i&k&k<<i<1for i in range(d.count('1')//n,k))or f(n,k+1)

```

Try it online!

---

# Python 2, ~~147~~ ~~135~~ 124 bytes

-11 bytes thanks to Surcolose Sputum!

```
from itertools import*
f=lambda n,k=1,C=combinations:k*any(all(a+c-b*2for a,b,c in C(w,3))for w in C(range(k),n))or f(n,k+1)

```

Try it online!
> 7 votes

# Answer
# , ~~96~~ 83 bytes

```
k=n=scan();C=combn;`[`=Map;try(while(!any(all[diff[C[C(1:k,n,,F),3],1,2]]))k=k+1);k

```

Try it online!

Full program, returns 1-indexed member of the sequence. Very slow for `n > 8`.
> 6 votes

# Answer
# 05AB1E, 19 bytes

```
∞.ΔLI.Æε3.Æε¥Ë≠}P}à

```

Outputs the \\$n^{th}\\$ value \\$k\\$.

Try it online or verify the first 8 test cases (times out for \\$\geq9\\$).

**Explanation:**

```
∞.Δ                 # Find the first positive integer `k`
   L                # for which its list in the range [1,k]
    I.Æ             # with combinations of the input amount of elements
       ε         }à # contains any combination-list which is truthy for:
        3.Æ         #  When taking all 3-element combinations of the current list
           ε   }P   #  they are all truthy for:
            ¥       #   When taking the forward differences of both pairs in this triplet
             Ë≠     #   they are NOT the same
                    # (after which the resulting `k` is output implicitly)

```
> 5 votes

# Answer
# Ruby, <sup>~~109...94~~</sup> 91 bytes

*-8 bytes thanks to @GB*

```
->n{1.step.find{|k|[*1..k].combination(n).any?{|p|p.combination(3).all?{|a,b,c|b-a!=c-b}}}}

```

Try it online! Takes less than 1 s for \\$n\le9\\$. Times out for \\$n\ge12\\$.
> 4 votes

# Answer
# JavaScript (ES6),  ~~150~~  145 bytes

This is quite inefficient for \\$n\>8\\$.

```
n=>(g=a=>(P=a=>a.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]))(a).some(a=>a[n-1]*P(a).every(([a,b,c,d])=>d|b-a!=c-b))?k:g([...a,++k]))([k=1])

```

Try it online!

## Commented

### Helper function

Since we don't have any combinatorial function available as a built-in, we're going to define just one: \\$P\\$ is a helper function that computes the powerset of a given array.

```
P = a =>
  a.reduce((a, x) =>
    [...a, ...a.map(y => [...y, x])],
    [[]]
  )

```

### Main function

```
n => (                  // n = input
  g = a =>              // g is a recursive function taking a range a[]:
    P(a).some(a =>      //   for each array a[] in the powerset of a[]:
      a[n - 1] *        //     make sure that the length of a[] is at least n
      P(a)              //     compute the powerset of a[]
      .every(           //     for each quad [a,b,c,d] in there,
      ([a, b, c, d]) => //     the test is successful if either:
        d |             //       - d is defined (meaning that this array has
                        //         more than 3 entries)
        b - a != c - b  //       - or a,b,c is not an arithmetic progression
      )                 //     end of every()
    )                   //   end of some()
    ?                   //   if truthy:
      k                 //     success: return k
    :                   //   else:
      g([...a, ++k])    //     try again with k+1 appended to a[]
)([k = 1])              // initial call to g with k = 1 and a = [1]

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 94 bytes

```
(t=1;While[Select[Range@t++~(S=Subsets)~{#},!Or@@(Equal@@Differences@#&/@#~S~{3})&]=={}];t-1)&

```

Try it online! 1-9 takes 1 min
> 3 votes

# Answer
# MATL, 22 bytes

```
`@:GXN!"@IXN!ddA]va~}@

```

Try it online! Or verify test cases `1``8` (test case `9` times out online).

### Explanation

```
`       % Do...while
  @:    %   Push range [1 2 ... k] where is the current iteration index
  G     %   Push input, n
  XN    %   Combinations of the elements [1 2 ... k] taken n at a time. This
        %   gives an n-column matrix where each row is a combination
  !     %   Transpose. Each combination is now a column
  "     %   For each column
    @   %     Push current column
    I   %     Push 3
    XN  %     Combinations of the elements of the current column taken n at
        %     a time. This gives a 3-column matrix
    !   %     Transpose. Each combination is now a column
    dd  %     Consecutive differences along each column, twice. This gives a
        %     row vector containing 0 for columns whose three elements form
        %     an arithmetic progression
    A   %     All. This gives true if all entries of the vector are non-zero;
        %     that is, if there were no arithmetic progressions of length 3
  ]     %   End
  v     %   Concatenate the stack into a column vector
  a~    %   Any, negate. Gives false if any entry from the above vector is
        %   non-zero. This will be used as loop condition; that is, if false
        %   the loop will end
}       % Finally (execute on loop break)
  @     %   Push latest k
        % End (implicit). The top of the stack is used as loop condiion
        % Display (implicit)

```
> 3 votes

# Answer
# Charcoal, ~~40~~ 37 bytes

```
≔⁰ηＷ∨⁻Σ⍘η²ＩθΦη＆η＆×ηＸ²⊕λ×ηＸ⁴⊕λ≦⊕ηＩＬ↨η²

```

Try it online! Link is to verbose version of code. Edit: Saved 3 byte by porting @SurculoseSputum's method. Now too slow for `n>6`. Explanation:

```
≔⁰η

```

Start with an empty bitmask.

```
Ｗ∨⁻Σ⍘η²Ｉθ

```

Repeat while the bitmask contains the wrong number of bits...

```
Φη＆η＆×ηＸ²⊕λ×ηＸ⁴⊕λ

```

... or it contains three terms in arithmetic progression...

```
≦⊕η

```

... increment the bitmask.

```
ＩＬ↨η²

```

Output the the length (in base 2) of the bitmask, which is necessarily equal to `k`.

At a cost of 2 bytes, I can replace `Φη` with `⊙↨η²`, which makes the code fast enough to compute up to `n=9`:

```
≔⁰ηＷ∨⁻Σ⍘η²Ｉθ⊙↨η²＆η＆×ηＸ²⊕λ×ηＸ⁴⊕λ≦⊕ηＩＬ↨η²

```

Try it online! Link is to verbose version of code. (Link only computes `n=8` to avoid unnecessarily overloading TIO.)

Looping over the odd numbers is slightly faster still, but not enough to be able to compute `n>9` on TIO. (It also gives the wrong answer for `n=0`, although that's not required by the question.)
> 3 votes

# Answer
# Retina, 91 bytes

```
.+
*_¶
/^(_)*¶(?<-1>10*)*(?(1)$|1)|1(.)*1(?<-2>.)*(?(2)$)1/{`¶(1*)$
¶0$1
)T`10`d`01*$
r`.\G

```

Try it online! Uses @SurculoseSputum's method, but too slow for `n>8`. Explanation:

```
.+
*_¶

```

Convert `n` to unary, and add a working area for the bitmask.

```
/^(_)*¶(?<-1>10*)*(?(1)$|1)|1(.)*1(?<-2>.)*(?(2)$)1/{`
)`

```

Repeat while the number of bits in the bitmask is not `n`, or there are three bits in the bitmask with identical spacing...

```
¶(1*)$
¶0$1

```

If the bitmask contains no zeros then prefix one.

```
T`10`d`01*$

```

Increment the bitmask.

```
r`.\G

```

Output the length of the bitmask, which is necessarily equal to `k`.

The bitmask computations involve .NET balancing groups.

```
^(_)*¶

```

This captures the unary value of `n`. Since the `*` is outside of the `(_)`, the group is captured `n` times. .NET records each capture as a stack, so `$1` now has a depth of `n`.

```
(?<-1>10*)*

```

This attempts to match the regex `10*`. Each successful match pops one of the captures from the `$1` stack. This continues until the stack is empty or there are no matches.

```
(?(1)$|1)

```

A conditional expression now checks whether the stack is empty. If it is not, then we want this to be because we ran out of `1` bits to match, which will be at the end of the string. If the stack is empty, then we want this to be because there are too many `1` bits, so we should be able to match one.

Note that while Retina will try to backtrack if it fails to match, this necessarily means both that the stack is not empty and that the match is not at the end of the string, i.e. this condition will never succeed in the case where the number of bits is correct.

```
1(.)*1(?<-2>.)*(?(2)$)1

```

In a similar way, we capture a variable number of bits between two `1` bits, and then require that the same number of bits exists between the latter and another `1` bits. Here the condition for a non-empty stack is a logical impossibility (`$` before a `1`) thus requiring the stack to be empty at this point, indicating that the number of bits is the same.
> 3 votes

---
Tags: code-golf, sequence, arithmetic
---


title: Help Beth escape the desert

text:
# Question
Title: Help Beth escape the desert
While similar to the other water-carrying puzzle, the unique aspects of this challenge make it entirely different.

Beth is located at an oasis in the middle of a desert. There is plenty of water in the lake, but unfortunately there are only X buckets, each of which has a capacity of Y liters of water.

Beth can carry 2 buckets in her hands, but to survive, she must drink exactly 1 liter after each kilometer she travels. She can also leave some buckets half-way (water does not evaporate).

## The challenge

Figure out the formula and write the **shortest solution** that will work for positive integer values of X and Y and calculate the **maximum distance** Beth can travel from the oasis. Moving water between the buckets is permitted.

## Example

X=3, Y=5

1. Beth walks 3km with two full buckets. Leaves 1 full bucket behind. The other bucket now has 2L left, which is enough to get home (Beth can have the last drink from the oasis).
2. She leaves with another two full buckets, arriving with 1 full, plus 2 litres in the other (12L total: 5 + 5 + 2).
3. Beth can advance to 6KM point and leave bucket with 4L of water in it.
4. She returns to the 3KM point. She now has exactly 2L to get back to the oasis.
5. Fill up buckets and travel to 6KM point. She now has 8L of water.
6. Continue all the way to 15KM point.

Answer is: 15

## Input / Output

You can define X/Y directly in the code or read from input. Result could be placed in variable or output, whichever is shortest.

# Answer
## JavaScript (ES6), 25 bytes

```
x=>y=>((x<3?x:3)+x)*y/2+1
x=>y=>(x<3?x+x:x+3)*y/2+1
x=>y=>(x<3?x:(x+3)/2)*y+1
x=>y=>(x<3?x:x/2+1.5)*y+1

```

All of these compute the same value; I can't seem to come up with a shorter formulation.

When `x` is less than `3`, you take as much water as you can and walk as far as you can, which is simply `x*y+1`.

When `x` is at least 3, you have to start building caches.

From the oasis, you can leave a full bucket at a distance `y/2` and return to the oasis. You need 2 buckets to do this, but this is not useful if you only have 2 buckets because you want to be able to fill up 2 buckets when you return to the oasis.

From the oasis, with a bucket at a distance `y/2`, you can leave a full bucket at a distance `y` and return to the oasis. You need 3 buckets to do this.

From the oasis, with full buckets at both `y` and `y/2`, you can leave a full bucket at a distance `3y/2` and return to the oasis. You need 4 buckets to do this. You then have to leave a full bucket at a distance of `y/2` and return to the oasis.

Eventually you can end up with a full bucket at `(x-1)y/2`. (You cannot leave a full bucket at `xy/2` because you would not be able to get back to the oasis, as the round trip is `xy`, the total capacity of the buckets.)

Using your remaining buckets, you can leave full buckets at `(x-3)y/2` ... `y` or `y/2`. At this point you simply walk as far as you can, picking up your full buckets as you go. When you reach `(x-1)y/2` you still have two full buckets left, allowing you to reach `(x+3)y/2`.

The extra `1` comes from the quirk in the rules allowing you to walk your last mile without having any water. Although the example shows that you can leave the buckets slightly further away than described above, this actually does not help you walk any further, as you either have to leave less water or drink the water from the bucket as you reach it before you can move on.
> 8 votes

# Answer
# APL (Dyalog Unicode), 12 bytesSBCS

```
1+2÷⍨⊢×⊣+3⌈⊣

```

Dyadic train taking `X` on the left and `Y` on the right.

Try it online! This uses @Neil's first formulation, so be sure to upvote that one as well.

**how it works:**

```
          3⌈⊣ ⍝ Find the maximum between the left (⊣) argument (X) and 3
        ⊣+    ⍝ and sum that to the left (⊣) argument (X),
     ⊢×       ⍝ which we then multiply by the right (⊢) argument (Y)
  2÷⍨         ⍝ and divide by 2.
1+            ⍝ Finish of by adding 1.

```
> 3 votes

# Answer
# 05AB1E, 8 bytes

```
D3‚à+*;>

```

Port of *@Neil*'s formula, so make sure to upvote him!!

$$d\_{X,Y}=\begin{cases} \dfrac{(3+X)\times Y}{2}+1 &\text{ if }X\<3\\ \\ \dfrac{2X\times Y}{2}+1 &\text{ if }X\geq3 \end{cases} $$

Try it online.

**Explanation:**

```
D         # Duplicate the first (implicit) input-integer X
 3‚       # Pair it with 3: [X,3]
   à      # Pop and push its maximum
    +     # Add it to the duplicated X (3+X if X<3; X+X if X>=3)
     *    # Multiply it by the second (implicit) input-integer Y
      ;   # Halve that
       >  # And increase it by 1
          # (after which the result is output implicitly)

```
> 1 votes

---
Tags: code-golf, math, puzzle-solver
---


title: Is this skew symmetry?

text:
# Question
Title: Is this skew symmetry?
In this challenge, your task is to detect (vertical) *Skewer Symmetry*. This means that one half of the pattern can be produced by mirroring the other half along a vertical axis, and then moving it vertically.

For example, the following pattern has skewer symmetry:

```
asdf
jkl;fdsa
    ;lkj

```

Because if you start from the left half...

```
asdf
jkl;

```

...then mirror it along a vertical axis...

```
    fdsa
    ;lkj

```

...then move it down by a character (filling the empty rows with spaces)...

```

    fdsa
    ;lkj

```

...you get the second half.

## Rules:

* You may assume the input is rectangle and has an even number of columns.
* If the pattern itself exhibits reflection symmetry, it is considered skewer symmetry.
* This is strict character by character symmetry, so `[[` is considered symmetrical, but not `[]`.
* You should output truthy if the input has skewer symmetry, falsy otherwise.
* Default I/O rules apply, standard loopholes are banned.

## Test Cases

Truthy cases:

```
asdf
jkl;fdsa
    ;lkj

```

```
asdffdsa

```

```
[

 [

```

```
  ba
abdc
cd

```

Falsy cases:

```
[
 ]

```

```
ab
ba

```

```
aa
a
 a

```

```
a  a
b b

```

```
ab
  b
   a

```

# Answer
# APL (Dyalog Unicode), ~~44~~ 34 bytesSBCS

crossed out ~~44~~ is still regular 44 ;(

Hats off to @Bubbler, @ngn and @TesselatingHeckler as they managed to shave some bytes off of my solution, more or less independently but coming up with the same simplifications.

```
{1∊(l↓⍵)⍷⍨a/⍨∨⌿' '≠a←⊖⍵↑⍨l←2÷⍨≢⍵}⍉

```

Try it online!

Now I'll explain **how it works**:

```
{                                   }⍉  ⍝ We define a monadic function that we apply right after transposing (⍉) the input [this means we will be operating on columns instead of rows]
                              2÷⍨≢⍵    ⍝ Start by finding how many  columns the input has (≢),split that in half (2÷⍨)
                            l←          ⍝   and assign that to l (l←) ...
                        ⍵↑⍨            ⍝ Using it right away to take (↑⍨) l columns from the original input ⍵
                       ⊖               ⍝   which we then reverse (⊖) [effectively flipping the columns upside down]
                     a←                 ⍝   and assign to a (a←)
                 ' '≠                   ⍝ We then compare each character in a to ' '
               ∨⌿                       ⍝   and we "interleave" the logical OR (∨) over the columns (⌿) [to find columns where at least one character is different from ' ']
           a/⍨                          ⍝   finally selecting those columns from a (a/⍨)
         ⍷⍨                             ⍝ Now we superimpose that piece of the original character matrix over all possible locations
   (l↓⍵)                               ⍝   of the columns of ⍵ that remain after we drop (↓) the first l columns [i.e. we take the second half of the columns]
 1∊                                    ⍝   and we look for matches by checking if there is a 1 (Truthy) in any position (∊)

```
> 4 votes

# Answer
# , ~~34~~ ~~23~~ 38 bytes

```
1 e.[:(e.&:((-:@#{.])"1)|."1\.)"2],:|.

```

Try it online!

*thanks to nimi for catching a bug*

Will attempt to regolf the fixed version later.
> 2 votes

# Answer
## Haskell, ~~137~~ ~~135~~ 133 bytes

```
f s=uncurry(#)$unzip$splitAt(div(length$s!!0)2)<$>s
a#b@(x:y)|e$last a++x=init a#y|e$last b++a!!0=b#a|r<-reverse<$>b=a==r
e=all(<'!')

```

Try it online!
> 1 votes

---
Tags: code-golf, decision-problem
---


title: Which number is bigger?

text:
# Question
Title: Which number is bigger?
Define `f(a,b) := a if b=1; a^f(a,b-1) if b>1` (Tetration, where `^` means power) for positive integers `a` and `b`, given four positive integers `a,b,c,d`, compare `f(a,b)` and `f(c,d)`.

Your program should output three constant values to mean "greater", "less" and "equal".

Samples:

```
a b c d f(a,b) output f(c,d)
3 2 2 3 27     >      16
4 2 2 4 256    <      65536
4 1 2 2 4      =      4

```

Lowest time complexity to `max{a,b,c,d}` win, with tie-breaker code length(the shorter the better) and then answer time(the earlier the better).

## Complexity assumption

* Your code should handle `a,b,c,d` up to 100, and your algorithm should handle all legal input
* You can assume integer calculations (that your language directly support) in `O((a+b+c+d)^k)` cost `O(1)` time if can be done in O(1) for 2k bit numbers if k bit computing can be done in O(1)
* For example, both plus(`+`) and multiply(`*`) can be done in O(1) for 2k bit numbers if k bit computing for both can be done in O(1), so both satisy the requirement. It's fine if multiply can't be done without plus, or even if both can't be done without each other.
* Float calculations in `O(log(a+b+c+d))` bit precision in `±2^O((a+b+c+d)^k)`, takes `O(1)`, with same requirements like integer calculations.

# Answer
# Java (JDK 10), 295 bytes

```
int f(Long a,long b,long c,long d){return a>c?-f(c,d,a,b):a<c?b>d?d==1?(a==2&((b==2&c==4)|(b==3&c==16)))|(a==3&b==2&c==27)?0:1:b-d>1?1:f(t(a,b),1,c,d):-1:a<2?0:a.signum(b-d);}long t(long a,long b){long t=1;for(;b-->0;)t=p(a,t);return t;}long p(long a,long b){long p=1;for(;b-->0;)p*=a;return p;}

```

Try it online!

Codes:

* `1` if `a^^b > c^^d`
* `-1` if `a^^b < c^^d`
* `0` is `a^^b == c^^d`
> 2 votes

# Answer
# APL (Dyalog Unicode), ~~30~~ 19 bytesSBCS

```
{f←*/⍴⍨⋄×(f/⍺)-f/⍵}

```

Try it online! Thanks to @ngn for saving 11 bytes by defining tetration in a much clever and shorter way:

```
f ← */⍴⍨   ⍝ Define f to be the tetration function
       ⍨   ⍝ Taking a on the right and b on the left,
      ⍴    ⍝   creating an array of b occurrences of the number a
    */     ⍝ and then building the tower of exponentials.

```

Now if I have a vector with two integers, `f/` applies the function to those two integers, e.g. `f/ 2 4` gives `65536` and `f/ 4 2` gives `256`. We need this in our main function:

```
{f←*/⍴⍨⋄×(f/⍺)-f/⍵}  ⍝ Dyadic function (g) expecting two vectors of 2 integers, e.g. 4 2 g 2 4
{f←*/⍴⍨            }  ⍝ Define the auxiliar function as above
{      ⋄           }  ⍝ and then:
{              f/⍵}   ⍝ Apply aux function to the right vector of integers
{        (f/⍺)     }  ⍝ Apply aux function to the left vector of integers
{             -    }  ⍝ Subtract the two values and finally
{       ×          }  ⍝ get the sign of that difference.

```

This means my function returns 1 if the left integers give a larger value, 0 if they are the same or ¯1 if the left integers give a smaller value.

My original submission had a recursive definition of tetration:

```
{f←{⍵=1:⍺⋄⍺*⍺∇⍵-1}⋄×(f/⍺)-f/⍵}

```

with tetration as:

```
{               }  ⍝ Dyadic function expecting 2 integers
{⍵=1:⍺         }  ⍝ If the right argument is 1, return the left argument;
{      ⋄        }  ⍝ otherwise (separate previous statement from the next one)
{       ⍺*      }  ⍝ Take the left argument to the power of
{         ⍺∇⍵-1}  ⍝ the recursive call of this function with same left argument and decremented right argument.

```
> 2 votes

# Answer
## Haskell, 46 bytes

```
a#1=a
a#b=a^a#(b-1)
(a!b)c d=compare(a#b)(c#d)

```

Prints `GT` for `>`, `LT` for `<` and `EQ`for `=`.

Try it online!
> 1 votes

---
Tags: code-golf, math, fastest-algorithm
---


title: Counting hypercube Tetris pieces

text:
# Question
Title: Counting hypercube Tetris pieces
Consider the Tetris pieces, but made out of some number of (hyper)cubes instead of four squares, where two blocks are considered the same if one is a rotation, reflection, or translation of another. The goal of this challenge is to take two positive integer input values, `n` and `k`, and count the number of \\$n\\$-celled polyominoes consisting of \\$k\\$-dimensional hypercubes.

This is a challenge, so the shortest code wins.

---

# Example

For example, when \\$n = 4\\$ and \\$k = 3\\$ there are seven different shapes:

Notice that the first piece could be made using \\$1\\$-cubes (line segments) instead of cubes, the next four could be made using \\$2\\$-cubes (squares), and only the last two require \\$3\\$-cubes (ordinary cubes). Thus \\$p(4,1) = 1\\$, \\$p(4,2) = 5\\$, and \\$p(4,3) = 7\\$.

---

# Test Data

```
 n | k | p(n,k)
---+---+--------
 1 | 0 | 1
 2 | 0 | 0
 2 | 1 | 1
 3 | 2 | 2
 4 | 1 | 1
 4 | 2 | 5
 4 | 3 | 7
 4 | 4 | 7
 4 | 5 | 7
 5 | 4 | 26
 6 | 3 | 112
 7 | 3 | 607
 8 | 2 | 369

```

# Answer
> 5 votes
# Python 2, 338 335 330

Try it online!

```
from itertools import*
n,k=input()
O=[([0]*k,)]
R=range(k)
exec"O={min(tuple(sorted(zip(*[[x-min(p)for x in p]for p in f])))for q in permutations(zip(*(o+(r,))))for f in product(*[[p,[-x for x in p]]for p in q]))for o in O for s in o for r in[tuple(s[i]+x*(i==j)for i in R)for j in R for x in-1,1]if not r in o};"*~-n
print len(O)

```

Reads n,k as a list from stdin (e.g. `[4,2]`) and prints the number of polyominoes.

Starts with a single polyomino with a single cell at the origin.

`n-1` times, replaces the polyominoes with all possible polyominoes created by adding an adjacent cell to an existing polyomino, and canonizing that polyomino by finding the minimum of all possible rotations of it.

-6 bytes thanks to math junkie, -2 bytes thanks to Surculose Sputum.

---
Tags: code-golf, geometry, combinatorics, polyomino
---


title: Escape the Candlelit Maze

text:
# Question
Title: Escape the Candlelit Maze
*You find yourself in a strange place. A frighteningly dark maze, lit only by dim candles resting in the occasional hallway. Numerous paths lie only in impassable darkness, foreboding and--* ...Hm? What? Pick up a candle and carry it with you? No, no, that would be *extremely* rude.

## The Task

Given a maze as input, output the minimum moves to solve it, or any falsey/invalid output if the maze cannot be solved. The catch: The maze is *very dark*, but is lit by candles placed on some of the grid squares. The player may only move in a direction if they can see light in that direction.

### Rules

* Take the maze as input in any convenient format (string, 1d array, 2d array, etc).
* `x` represents a wall, `@` represents the player, `^` represents a candle and `#` represents the exit.
* The maze will be surrounded on all sides by walls, except for the player's starting space and the exit space, each of which will be in one of the walls. The corners will always be walls.
* The player may only make orthogonal moves one space at a time in the direction of *visible light*. This is either a candle or the exit.
* Candlelight only reaches the space it's on, but is visible from any distance.
* Output the minimum number of legal moves the player can make to reach the exit, or any "invalid" value (such as a negative value, zero, false, the string "Unsolvable!", etc) if the maze is unsolvable within the rules. The player must move into the exit space to solve the maze.
* Standard loophole restrictions and i/o rules apply.

### Test Cases

1-

```
Input:
xxxxxxxxxx
@^x    ^xx
x^  ^xxxxx
xxxx x^  #
x xx x xxx
x ^ ^ ^x x
x xxxx  ^x
xxxxxxxxxx

Output:
15

```

2-

```
Input:
xxxxxxxxxxxx
x^ ^xxxxxxxx
x x        #
x x^xxxx xxx
x xxxx   xxx
x^  ^xxx^xxx
xxxx@xxxxxxx

Output:
19

```

Once the player moves into a space that can see a new light source, such as the exit, they can then start moving towards that light source.

3-

```
Input:
xxxxxxxx
#  xx ^x
xx^  ^xx
x ^xx xx
xxxxx@xx

Output:
Unsolvable

```

4-

```
Input:
xxxxxxxxx
@      ^x
x xxxxx x
x x^   ^x
x x xxxxx
x x^   ^x
x xxxxx x
x^ ^   ^x
xxx#xxxxx

Output:
10

```

The player must take the shortest path.

5-

```
Input:
xxxxxxxxx
x   ^  ^x
xxxx xxxx
#  x    x
x^xx^xxxx
x^   x  x
xxxx x xx
x     ^ x
xxxx@xxxx

Output:
Unsolvable

```

### Scoring

This is , so shortest code in bytes wins.

# Answer
# Retina 0.8.2, 229 bytes

```
T`#^`d
s`@.*
$&_
@\d|@ ( *\d)
@=$1
(\d *) @|\d@
$1=@
m`^(((.))*@.*\n(?<-2>.)*(?(2)$))(\d| ((.*\n)+(?<-3>.)*(?(3)$)\d))
$1=$5
m`^(((.))*)(\d|(\d(.*\n)+(?<-2>.)*(?(2)$)) )(.*\n(?<-3>.)*(?(3)$)@)
$1$5=$7
@
x
}sT`=`@`.*0.*
s`.*0.*

_

```

Try it online! Outputs `0` for unsolvable, since solutions must take at least one step. Explanation:

```
T`#^`d

```

Change the candle and exit to golfier characters, saving 7 bytes

```
s`@.*
$&_

```

If there are still squares to check, then increment the counter. (This allows the loop to terminate once it runs out of squares to check.)

```
@\d|@ ( *\d)
@=$1

```

Mark the square to the right if it is lit.

```
(\d *) @|\d@
$1=@

```

Mark the square to the left if it is lit.

```
m`^(((.))*@.*\n(?<-2>.)*(?(2)$))(\d| ((.*\n)+(?<-3>.)*(?(3)$)\d))
$1=$5

```

Mark the square below if it is lit.

```
m`^(((.))*)(\d|(\d(.*\n)+(?<-2>.)*(?(2)$)) )(.*\n(?<-3>.)*(?(3)$)@)
$1$5=$7

```

Mark the square above if it is lit.

```
@
x

```

Turn the squares that were checked into walls.

```
sT`=`@`.*0.*

```

If the exit still exists, then turn all of the marked squares into squares that need to be checked.

```
}`

```

Repeat the above until the exit is reached or no new steps could be taken.

```
s`.*0.*

```

If the exit was not reached then delete the count.

```
_

```

Convert the count to decimal and delete the input.
> 7 votes

# Answer
# JavaScript (ES6),  ~~196 ... 179~~  177 bytes

Takes input as a matrix of characters. Returns \\$0\\$ if there's no solution.

```
m=>(o=F=(X,Y,n)=>m.map((r,y)=>r.map((c,x)=>n?(h=x-X)*h+(v=y-Y)*v-1?0:c=='#'?o=o<n?o:n:r[(g=w=>1/(C=m[z+=v][w])?g(w+h):C<g)(x,z=Y)&&F(x,y,n+1,r[x]=g),x]=c:c=='@'&&F(x,y,1))))()|o

```

Try it online!

### How?

This is a depth-first search. We first look for the position of the player and then initiate the recursion. We keep track of the number of moves in \\$n\\$ and the length of the shortest path in \\$o\\$.

Given the previous position \\$(X,Y)\\$, we iterate on all cells \\$(x,y)\\$ of the maze and compute \\$dx=x-X\\$ and \\$dy=y-Y\\$. We can move to the new cell if:

* \\$dx^2+dy^2=1\\$
* and the first non-empty cell encountered along the ray \\$(X+k\cdot dx,Y+k\cdot dy),k\>0\\$ is either a candle or the exit

### Commented

```
m => (                           // m[] = input matrix
  o =                            // o = output, initially non-numeric
  F = (X, Y, n) =>               // F is the main recursive function:
    m.map((r, y) =>              //   for each row r[] at position y in m[]:
      r.map((c, x) =>            //     for each character c at position x in r[]:
        n ?                      //       if n is defined:
          (h = x - X) * h +      //         h = dx, v = dy
          (v = y - Y) * v - 1 ?  //         if the quadrance is not equal to 1:
            0                    //           abort
          :                      //         else:
            c == '#' ?           //           if we've reached the exit:
              o = o < n ? o : n  //             update o if n is better
            :                    //           else:
              r[                 //             wrapper to update r[]:
                ( g =            //               we use g to look for a candle
                  w =>           //               or the exit in this direction:
                  1 / (C =       //                 move along (dx, dy) and store
                    m[z += v][w] //                 the content of the cell in C
                  ) ?            //                 if C is a space:
                    g(w + h)     //                   keep moving until it's not
                  :              //                 else:
                    C < g        //                   success if C is not 'x'
                )(x, z = Y)      //               initial call to g at (X, Y)
                &&               //               if the move is valid:
                  F(             //                 do a recursive call:
                    x, y, n + 1, //                   at (x, y) with n + 1
                    r[x] = g     //                   invalidate the current cell
                  ),             //                 end of recursive call
                x                //               actual index in r[] ...
              ] = c              //             ... to restore the cell
        :                        //       else (n undefined):
          c == '@' && F(x, y, 1) //         initiate the recursion if c is '@'
    ))                           //   end of map() loops
)() | o                          // initial call to F; return o

```
> 4 votes

# Answer
# PowerShell 6+ for Windows, 162 bytes

```
$f={param($m,$l)++$l
1..4|%{switch -r($m){'@#'{$l}'@ *[#^]'{&$f($m-replace'@.','x@')$l}}$m=&{($a=$m[-1..-$m.Count])[0]|% t*y|%{-join($a|% Ch*($i++))}}}|sort -t 1}

```

Try it online!

Unrolled:

```
$f = {
    param($maze,$len)   # len = $null if parm omited

    ++$len
    1..4|%{
        #recursive call
        switch -Regex ($maze){
            '@#'{$len}
            '@ *[#^]'{
                &$f ($maze -replace '@.','x@') $len   # leave a wall behind to avoid infinite loops
            }
        }
        #rotate -90
        $maze = &{  # new context to reinit $array and $i
            $array=$maze[-1..-$maze.Count]
            $array[0]|% toCharArray|%{
                -join($array|% Chars($i++))
            }
        }
    }|sort -Top 1          # Powershell 6+ for Windows
#   }|sort|select -First 1 # Powershell 5- for Windows
#   }|sort-object -Top 1   # Powershell for Linux
}

```
> 2 votes

# Answer
# Perl 5, 238 bytes

```
sub f{%s=@_=(1,pop);while(@_){$i=shift;$m=shift;for(1..4){@a=$m=~/.+/g;!$s{$m=join$/,reverse map{$j=$_-1;join'',map/.{$j}(.)/?$1:0,@a}1..length$a[0]}++&&push@_,$i,$m};$_=$m;s/@( *[\^#])/'x@'.substr$1,1/e&&(/#/||return$i)&&push@_,$i+1,$_}}

```

Try it online!

Rotates the maze 90° four times at each position. Easier to regexp-search-replace the entire maze as one string for `@ +[^#]` with `x@` \+ one less space when the next light or end is always ahead if at all. `@^` and `@#` with no space are replaced by `x@` so the `#` disappears which means the exit has been reached and we return `$i` steps taken. Array `@_` contains mazes to try out next. Hash `%s` keeps track of which mazes we've already tried so those are skiped. Nothing left to try in `@_` means no solution is to be found and `0` is returned.
> 1 votes

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


# Question
Title: How to find the original value based on modulus/reminder and some other information
This might be a very basic question in terms of math,

```
x % constant = x_modulus

(x + some_number) % constant = y_modulus

```

Given the value of `x_modulus`, `y_modulus`, `(x + some_number)` and `constant`(common in both), output the value of x itself based on these values.

# Answer
# 05AB1E, 1 byte

Finds the smallest possible value of all values of `x`, takes input as `some_number, constant, x_modulus, y_modulus`

```
α

```

Try it online!

## Explanation

Here are my observations:

* The value of `some_number` is the absolute difference between `x_modulus` and `y_modulus`
* The above value is in turn x's distance with the closest multiple of constant larger than x.

Therefore it's impossible to find what exactly is the value of x. That greatly trivializes the question into a simple absolute difference between `some_number` and `constant`.

The code itself is just absolute difference, I don't feel like explaining it. :D
> 2 votes

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


# Question
Title: Produce an image based on an elementary cellular automata ruleset
# What is elementary cellular automata?

Since I'm not sure I'll be able to explain this so that somebody who has never heard of this is able to understand, I'm giving an explanation from https://mathworld.wolfram.com/ElementaryCellularAutomaton.html

> Elementary cellular automata have two possible values for each cell (0 or 1), and rules that depend only on nearest neighbor values. As a result, the evolution of an elementary cellular automaton can completely be described by a table specifying the state a given cell will have in the next generation based on the value of the cell to its left, the value the cell itself, and the value of the cell to its right. Since there are 2×2×2=2^3=8 possible binary states for the three cells neighboring a given cell, there are a total of 2^8=256 elementary cellular automata, each of which can be indexed with an 8-bit binary number. For example, the table giving the evolution of rule 30 (30=00011110\_2) is illustrated above. In this diagram, the possible values of the three neighboring cells are shown in the top row of each panel, and the resulting value the central cell takes in the next generation is shown below in the center.
>
> The evolution of a one-dimensional cellular automaton can be illustrated by starting with the initial state (generation zero) in the first row, the first generation on the second row, and so on. For example, the figure bellow illustrated the first 20 generations of the rule 30 elementary cellular automaton starting with a single black cell.

# The task

Given a ruleset n, where n is positive and less than 256, produce an image like the one above, with 15 generations (+1 starting gen-0) and 2 colors of your choice. The starting gen-0 is one active cell in the center, like in the image above. You can choose to start from the bottom and work upwards.

# Input

You can take input either as a:

* Binary number (for example, rule 30 would be 00011110 or the reverse 01111000)
* Decimal number (rule 30 would be 30)

You **cannot** take images from external resources, the image should made from scratch by your program.

# Output

Your output should be a 31x16 image, with each row representing a separate generation. Generations should not be given in a mixed order.

# Submissions

Your submission should always contain the following:

1. Your code
2. An image produced by your program, representing a ruleset of your liking. Standard loopholes apply. Your program should work for any n in the range \[0,256).

**Scoring is done by byte count**

## EDIT

As requested, adding some test cases specifically for edge handling.

rule 222:

rule 201:

rule 162:

rule 16:

# Answer
# Python 2, ~~178 167 ...~~ 128 bytes

*-13 bytes thanks to @Surculose Sputum!*

*-2 bytes thanks to @dingledooper!*

*thanks @Surculose Sputum again for saving some bytes and fixing the boundary bug!!!!*

```
n=input()
print'P1 31 16'
c='%061d'%10**30
exec"print' '.join(c[15:46]);c='0'+''.join(n[int(c[u:u+3],2)]for u in range(60));"*16

```

Try it online!

Output a 31x16 pbm image in stdout. You might need a magnifying glass to see those tinnie images though.

> '01111000' =\>  (30 in reverse)
> '01011000' =\>  (26 in reverse)
> 9 votes

# Answer
# Wolfram Language (Mathematica), 42 bytes

¯\\\_(ツ)\_/¯

```
Image@CellularAutomaton[#,{{1},0},15]&

```

> > **n=30**

> > **n=26**

Since this challenged changed to gode-golf I applied the changes that @Dan the Man proposed and saved some bytes.
The images now should have inverted colors
> 8 votes

# Answer
# Sledgehammer, ~~24~~ 19 bytes

<sup>(alternatively, 18.625)</sup>
Obtained from the Wolfram code `ExportString[ArrayPlot[CellularAutomaton[Input[], {{1}, 0}, {15, All}]], "SVG"]`.

Outputs via (as you could easily tell) SVG. The ExportString part can be dropped, but then it will output a Graphics object - it's basically an image, but it's hard to view without loading it into Mathematica or exporting it via Export/ExportString.

```
⣕⢼⡔⡼⣂⡏⢂⠌⢤⡾⣧⣾⢴⠮⣯⠴⢒⣈⣱

```
> 5 votes

# Answer
# 05AB1E, 57 bytes

```
"P1 31 16",¾16иJD"ÿ1ÿ"16E©D¦¨Sðý,31Lε<®s.$3£C7αIsè}J"0ÿ0"

```

a (bad) port of this python answer

Try it online!
> 4 votes

# Answer
# MATL, 36 bytes

*Thanks to @AdHocGarfHunter for pointing out a mistake, now corrected*

```
l30Ya!15:"GyFTYa3YC!XBQ)]v16:46Z)0YG

```

Input is binary in reverse order. Output is white for active cell, black for inactive.

Try it at **MATL Online!**

### Explanation

```
l       % Push 1
30Ya    % Padarray: pads 1 with 30 zeros on each side. Gives a column vector.
        % This large amount of padding is necessary to avoid edge effects in
        % the output
!       % Transpose into a row vector
15:"    % Do the following 15 times
  G     %   Push input
  y     %   Duplicate from below: pushes a copy of the latest row vector
  FTYa  %   Pad with one zero to the left and one to the right
  3YC   %   Matrix of length-3 sliding blocks arranged as columns
  !     %   Transpose. Each block is now a row
  XB    %   Convert each row from binary to a number
  Q     %   Add 1 (this is needed because indexing is 1-based)
  )     %   Index the input with these numbers. This applies the automaton
        %   rule to each length-3 block, producing a new generation
]       % End
v       % Concatenate all row vectors into a matrix
16:46   % Push [16 17 ... 46]: indices of the columns to be kept
Z)      % Use as column indices
0YG     % Write to image file. This is implicitly displayed by MATL Online

```
> 3 votes

# Answer
# Haskell, ~~175~~ ~~158~~ 154 bytes

```
t=take 16
f=t$0:f
(a:b)!s=s<$>p(a:a:b)
p(a:b:c:d)=(4*a+2*b+c):p(b:c:d)
p[a,b]=[4*a+3*b]
m s=putStr"P1 33 16 ">>mapM_ print`mapM_`t(iterate(!(s!!))$f++1:f)

```

Try it online!

Outputs to a pbm file with white being off and black being on. You can switch the on and off colors at no cost to bytes.

## Sample outputs

### Rule 30

* Raw
* Increased size

### Rule 121

* Raw
* Increased Size
> 3 votes

# Answer
# Java, 247 bytes

```
import java.awt.image.*;r->{BufferedImage i=new BufferedImage(31,16,1);int[]p=((DataBufferInt)i.getRaster().getDataBuffer()).getData();p[15]=-1;for(int a=31;a<496;a++)p[a]=r<<31-(p[a==31?0:a-32]<<2&4|p[a-31]<<1&2|p[a==495?0:a-30]&1)>>31;return i;}

```

repl.it

Before minimizing:

```
rule -> {
    BufferedImage image  = new BufferedImage(31, 16, BufferedImage.TYPE_INT_RGB);
    int[]         pixels = ((DataBufferInt)image.getRaster().getDataBuffer()).getData();
    pixels[15]           = -1;
    for (int i = 31; i < 496; i++)
        pixels[i] = rule << 31 - (pixels[Math.max(0, a - 32)] << 2 & 4 |
                                  pixels[i - 31] << 1 & 2 |
                                  pixels[i == 495 ? 0 : i - 30] & 1) >> 31;
    return image;
};

```

Inner magic ungolfed:

```
BOTTOM_LEFT_PIXEL_WHICH_IS_WRITTEN = 465;
int upLeft  = pixels[Math.max(0, i - 32)];
int up      = pixels[i - 31];
int upRight = pixels[i - 30 == BOTTOM_LEFT_PIXEL_WHICH_IS_WRITTEN ? 0 : i - 30];
int code    = ((upLeft << 2) & 4) | ((up << 1) & 2) | (upRight & 1);
int newBit  = (rule >> code) & 1;
pixels[i] = newBit == 0 ? 0x00000000 : 0xFFFFFFFF;

```

Notes: The code could be even shorter if the output image was allowed to be 32 pixels wide instead of 31. It could be even shorter if 'active' pixels may be impossibly invisible dark blue (#000001)

It could surely be shorter with pbm output, but I like to see my stuff directly.
> 2 votes

---
Tags: code-golf, graphical-output, grid, cellular-automata, simulation
---


title: Multiplication algorithm on a 4004

text:
# Question
Title: Multiplication algorithm on a 4004
So I was playing around with this emulator of the Intel 4004 and decided I wanted to set a challenge for myself. The first use for the 4004 was in a calculator, so I decided that I would try to code golf every operator on said calculator(addition, subtraction, multiplication, division, decimal points, and the square root) in hexadecimal. Now this was my first code golf challenge I ever set for myself, like ever, and I am relatively new at coding in general, but I thought it would be a fun thing to try out. This was the code for multiplication, specifically 3\*4(In order to change it, simply replace the nybbles following the Ds\[except for the 0\] with any number you want as long as the product is below 16 and the second and third Ds have the same nybble trailing them):

```
 D4 B1 D3 B0 D3 B2 A0 82 B0 D0 B1 F8 F3 14 12 B1 40 06 B0 92 F3 E0

```

Are there any flaws in my 22-byte design, and is there a way to shorten the code? For reference, the instruction set for the 4004 in binary is in this table: http://www.e4004.szyc.org/iset.html

# Answer
## 4004 machine code, 12 bytes

This is the best code I could come up with using the same I/O as the provided code:

```
D4      LDM 4
B0      XCH R0
D3      LDM 3
F4      CMA
B1      XCH R1
D0      LDM 0
40 09   JUN TEST
        :LOOP
80      ADD R0
        :TEST
71 08   ISZ R1, LOOP
E0      WRM

```

If you omit the first 3 instructions and the last instruction then the inputs become R0 and the accumulator and the accumulator becomes the output.

Note that this does not handle overflow very well at all; you can add in a `CLC` to ensure that it at least calculates it correctly modulo 16, or in case the caller has left the carry set.
> 3 votes

---
Tags: code-golf, arithmetic, tips
---


title: Fermat's factorization helper

text:
# Question
Title: Fermat's factorization helper
We'd like to factorize a semiprime \\$N\\$. The goal of this challenge is to find two small integers \\$u\\$ and \\$v\\$ such that \\$uvN\\$ can be trivially factorized with Fermat's method, thus allowing to easily deduct the factors of \\$N\\$.

## The task

Given a semiprime \\$N\\$ and a positive integer \\$k\\$, we define \\$x\\$ and \\$y\\$ as:

$$x=\lceil\sqrt{kN}\rceil$$ $$y=x^2-kN$$

**Step #1 - Find \\$k\\$**

You first need to find the smallest possible value of \\$k\\$ such that \\$y\\$ is a square number (*aka* perfect square).

This allows to factorize \\$kN\\$ with a single iteration of Fermat's factorization method. More concretely, this immediately leads to:

$$kN=(x+\sqrt{y})\times(x-\sqrt{y})$$

(Update: this sequence is now published as A316780)

**Step #2 - Factorize \\$k\\$**

You then have to find the two positive integers \\$u\\$ and \\$v\\$ such that:

$$uv=k$$ $$cu=x+\sqrt{y}$$ $$dv=x-\sqrt{y}$$

where \\$c\\$ and \\$d\\$ are the prime factors of \\$N\\$.

**Summary**

Your task is to write a program or function that takes \\$N\\$ as input and prints or outputs \\$u\\$ and \\$v\\$ in any order and any reasonable format.

## Example

Let's consider \\$N = 199163\\$

**Step #1**

The smallest possible value of \\$k\\$ is \\$40\\$, which gives:

$$x = \lceil(\sqrt{40 \times 199163})\rceil = 2823$$ $$y = 2823^2 - 40 \times 199163 = 7969329 - 7966520 = 2809 = 53^2$$ $$kN = (2823 + 53) \times (2823 - 53)$$ $$kN = 2876 \times 2770$$

**Step #2**

The correct factorization of \\$k\\$ is \\$k = 4 \times 10\\$, because:

$$kN = 2876 \times 2770$$ $$kN = (719 \times 4) \times (277 \times 10)$$ $$N = 719 \times 277$$

So, the correct answer would be either \\$\[ 4, 10 \]\\$ or \\$\[ 10, 4 \]\\$.

## Rules

* It is not required to strictly apply the two steps described above. You're free to use any other method, as long as it finds the correct values of \\$u\\$ and \\$v\\$.
* You must support all values of \\$uvN\\$ up to the native maximum size of an unsigned integer in your language.
* The input is guaranteed to be a semiprime.
* This is code-golf, so the shortest answer in bytes wins.
* Standard loopholes are forbidden.

## Test cases

```
N          | k    | Output
-----------+------+------------
143        | 1    | [   1,  1 ]
2519       | 19   | [   1, 19 ]
199163     | 40   | [   4, 10 ]
660713     | 1    | [   1,  1 ]
4690243    | 45   | [   9,  5 ]
11755703   | 80   | [  40,  2 ]
35021027   | 287  | [   7, 41 ]
75450611   | 429  | [ 143,  3 ]
806373439  | 176  | [   8, 22 ]
1355814601 | 561  | [  17, 33 ]
3626291857 | 77   | [   7, 11 ]
6149223463 | 255  | [  17, 15 ]
6330897721 | 3256 | [  74, 44 ]

```

## Example implementation

In the snippet below, the \\$f\\$ function is an ungolfed implementation which takes \\$N\\$ as input and returns \\$u\\$ and \\$v\\$.

For illustrative purposes only, the snippet also includes the \\$g\\$ function which takes \\$N\\$, \\$u\\$ and \\$v\\$ as input and computes the factors of \\$N\\$ in \\$O(1)\\$.

```
f = N => {
  for(k = 1;; k++) {
    x = Math.ceil(Math.sqrt(k * N));
    y = x * x - k * N;
    ySqrt = Math.round(Math.sqrt(y));

    if(ySqrt * ySqrt == y) {
      p = x + ySqrt;

      for(u = 1;; u++) {
        if(!(p % u) && !(N % (p / u))) {
          v = k / u;
          return [ u, v ];
        }
      }
    }
  }
}

g = (N, u, v) => {
  x = Math.ceil(Math.sqrt(u * v * N));
  y = x * x - u * v * N;
  ySqrt = Math.round(Math.sqrt(y));
  p = x + ySqrt;
  q = x - ySqrt;
  return [ p / u, q / v ];
}

[
  143, 2519, 199163, 660713, 4690243, 11755703,
  35021027, 75450611, 806373439, 1355814601,
  3626291857, 6149223463, 6330897721
]
.map(N => {
  [u, v] = f(N);
  [c, d] = g(N, u, v);
  console.log(
    'N = ' + N + ', ' +
    'u = ' + u + ', ' +
    'v = ' + v + ', ' +
    'N = ' + c + ' * ' + d
  );
});
```

# Answer
# Mathematica, ~~81~~ 79 bytes

*Thanks to Martin Ender for saving 2 bytes!*

```
(c=Ceiling;For[j=0;z=E,c@z>z,p=(x=c@Sqrt[j+=#])+{z=Sqrt[x^2-j],-z}];p/#~GCD~p)&

```

Pure function taking a semiprime as input and returning an ordered pair of positive integers. The `For` loop implements the exact procedure described in the question (using `#` for the input in place of `n`), with `x` as defined there, although we store `j = k*n` instead of `k` itself and `z=Sqrt[y]` instead of `y` itself. We also compute `p={x+z,x-z}` inside the `For` loop, which ends up saving one byte (on like the seventh try). Then the two desired factors are `(x+z)/GCD[#,x+z]` and `(x-z)/GCD[#,x-z]`, which the concise expression `p/#~GCD~p` computes directly as an ordered pair.

Curiosities: we want to loop until `z` is an integer; but since we're going to use `Ceiling` already in the code, it saves two bytes over `!IntegerQ@z` to define `c=Ceiling` (which costs four bytes, as Mathematica golfers know) and then test whether `c@z>z`. We have to initialize `z` to something, and that something had better not be an integer so that the loop can start; fortunately, `E` is a concise choice.
> 8 votes

# Answer
## JavaScript (ES7), ~~86~~ 81 bytes

```
n=>(g=k=>(y=(n*k)**.5+1|0,y+=(y*y-n*k)**.5)%1?g(k+1):n*u++%y?g(k):[--u,k/u])(u=1)

```

Edit: Saved 4 bytes thanks to @Arnauld.
> 5 votes

# Answer
# APL (Dyalog Unicode), ~~60~~ ~~49~~ 45 bytes

```
{×1|w←⍵∨(⌈+.5*⍨×⍨-⍨⌈×⌈).5*⍨⍵×⍺:⍺∇1+⍵⋄w,⍵÷w}∘1

```

Try it online!

-11b thanks to Adám, -4b courtesy of ngn along with some excellent tips from both on The APL Orchard

## Explanation:

First ever APL answer so might be able to be golfed further! Explanation below is for the 49b solution. Approach pretty much just follows the algorithm in the original post, but uses the GCD to compute the factors once k, x and y are known.

```
{×1|y←.5*⍨(×⍨x←⌈.5*⍨⍵×⍺)-⍵×⍺:⍺∇1+⍵⋄w,⍵÷w←⍵∨x+y}∘1 ⍝
{                                             }∘1 ⍝ dfn; ⍺ is left argument (N), ⍵ is right argument acting as a counter for k incremented each recursion from 1
          (  x←⌈.5*⍨⍵×⍺)-⍵×⍺                      ⍝ Computes x as per question for current k
    y←.5*⍨(×⍨x         )                          ⍝ Computes sqrt(y) from x as per question (×⍨x = x^2). Note that y here actually represents sqrt(y) from the question as we do not need to store actual y
 ×1|y                                             ⍝ Use 1 modulo y and 'direction' to return 0 if y is a whole number, else 1
                            :     ⋄               ⍝ 'guard' - if the evaluation of the left side of : is true, performs the statement immediately following it, otherwise the next statement (separated by ⋄)
                             ⍺∇1+⍵                ⍝ if guard is true, recurse with the same left argument of N, and a right argument of the new k (k+1)
                                   w,⍵÷w←⍵∨x+y    ⍝ if guard is false, computes gcd (∨) of k and (x+y) as one factor (w), and k÷w as the second factor

```
> 5 votes

# Answer
# Python 2, ~~127~~ ~~121~~ ~~117~~ ~~111~~ ~~107~~ ~~104~~ ~~101~~ 99 bytes

*-1 byte thanks to Neil & -3 bytes thanks to ovs*

```
N=input()
k=u=1;p=m=.5
while p%1:p=1+(k*N)**m//1;p+=(p*p-k*N)**m;k+=1
while N*u%p:u+=1
print~-k/u,u

```

Try it Online!

**Curiosities:**

`p` is initialized to `.5` so that the loop condition will be true on the first iteration. Note that it is shorter to store `p` (as `x` \+ `sqrt(y)`) than it is to store each of `x` and `y` separately.
> 4 votes

# Answer
# Axiom, ~~131~~ 115 bytes

```
v(x)==floor(x^.5)::INT;r(n)==(k:=0;repeat(k:=k+1;x:=1+v(k*n);y:=v(x*x-k*n);x^2-y^2=k*n=>break);[w:=gcd(k,x+y),k/w])

```

The function that would resolve question is r(n) above. ungolf and test

```
vv(x)==floor(x^.5)::INT

--(x-y)*(x+y)=k*n
rr(n)==
  k:=0
  repeat
     k:=k+1
     x:=1+vv(k*n)
     y:=vv(x*x-k*n)
     x^2-y^2=k*n=>break
  [w:=gcd(k,x+y),k/w]

(4) -> [[i,r(i)] for i in [143,2519,199163,660713,4690243,11755703]]
   (4)
   [[143,[1,1]], [2519,[1,19]], [199163,[4,10]], [660713,[1,1]],
    [4690243,[9,5]], [11755703,[40,2]]]
                                                      Type: List List Any

```
> 2 votes

---
Tags: code-golf, number-theory, primes
---