title: The Uncommon Factor Number

text:
# Question
Title: The Uncommon Factor Number
*Based on a chat message*

## The Challenge

Given an input number \\$n \> 9\\$, construct its reverse, ignoring leading zeros. Then, construct a list of all prime factors that the number and its reverse *don't* have in common. Multiply those factors together to create the ***Uncommon Factor Number*** of the input.

Or, to put it another way: if \\$\text{rev}(n)\\$ denotes the decimal reversal of integer \\$n\\$, calculate the product of \\$n\\$ and \\$\text{rev}(n)\\$ divided by the square of the \\$\gcd(n, \text{rev}(n))\\$.

Output that number.

### Worked examples

For example, \\$2244\\$ reverses to \\$4422\\$. The prime factors of the first are \\$\[2, 2, 3, 11, 17\]\\$ and the prime factors of the reverse are \\$\[2, 3, 11, 67\]\\$. The numbers not in common multiplicities are \\$\[2, 17, 67\]\\$, so \\$2278\\$ is the output.

For another example, \\$1234\\$ reverses to \\$4321\\$. The product is \\$5332114\\$ and the GCD is \\$1\\$, so the output is \\$5332114\\$.

## Further clarifications

Obviously a palindromic number will have all its factors in common with its reverse, so in such a case the output is \\$1\\$ \\$\left(\frac{n\times n}{n^2}\right)\\$. Obviously, it's also possible for the output to be the multiplication all factors (i.e., the gcd is \\$1\\$ -- the input and its reverse are co-prime), as in the case of the \\$1234\\$ example.

## Rules

* The input and output can be assumed to fit in your language's native integer type.
* The input and output can be given in any convenient format.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* If possible, please include a link to an online testing environment so other people can try out your code!
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

## Examples

```
in
out

17
1207

208
41704

315
1995

23876
101222302

```

# Answer
# 05AB1E, 6 bytes

### Code

```
Â‚D¿÷P

```

Uses the **05AB1E** encoding. Try it online!

### Explanation

```
Â‚        # Get the array [input, reversed(input)]
  D       # Duplicate that array
   ¿      # Calculate the GCD of the array
    ÷     # Divide each element in the array by the GCD
     P    # Product of that array

```
> 6 votes

# Answer
# J, 18 bytes

```
".@|.@":(*%*:@+.)]

```

Try it online!

Alternatively (credit to @Adnan's approach for the second one),

```
".@|.@":(*%2^~+.)]
".@|.@":*/@(,%+.)]

```

# J, 15 bytes (@miles's solution)

```
*/@(,%+.)|.&.":

```

# Explanation

This is just a straightforward implementation of the algorithm given by the OP.

```
".@|.@":(*%*:@+.)]
                 ]  n (input)
".@|.@":            n reversed
         *          Product of the two
          %         Divided by
              +.      GCD
           *:         Squared

```

# Explanation, @miles's solution

Very clever.

```
*/@(,%+.)|.&.":
         |.&.":  Reverse digits
           &.":   Convert to string, apply next function, and undo conversion
         |.       Reverse
   (,%+.)        Divide n and reverse(n) by GCD of both
*/               Product

```
> 5 votes

# Answer
# Mathematica, 33 bytes

```
#(s=IntegerReverse@#)/GCD[#,s]^2&

```

Try it online!
> 4 votes

# Answer
# Jelly, 8 bytes

```
,ṚḌµ:g/P

```

Try it online!
> 3 votes

# Answer
# , ~~108~~ 89 bytes

*-19 bytes thanks to plannapus for his gcd algorithm*

```
function(n){k=1:nchar(n)-1
q=1:n
(r=sum(n%/%10^k%%10*10^rev(k)))*n/max(q[!r%%q&!n%%q])^2}

```

This will attempt to allocate at least one vector of size `4*n` bytes (and I think as many as 4), so this will throw a memory error for sufficiently large `n`.

Try it online!
> 2 votes

# Answer
# JavaScript, ~~67~~ ~~64~~ ~~60~~ 59 bytes

So many bytes just to reverse the number :(

Takes input as a string. 1 byte saved thanks to l4m2.

```
f=(n,x=n,y=r=[...n].reverse().join``)=>y?f(n,y,x%y):n*r/x/x

```

Try it online!
> 2 votes

# Answer
## Haskell, 44 bytes

```
f x|r<-read$reverse$show x=x*r`div`gcd x r^2

```

Try it online!
> 2 votes

# Answer
# Python 3, ~~73~~ 68 bytes

*-5 bytes thanks to Mr. Xcoder.*

```
import math
def f(n):g=int(str(n)[::-1]);print(n*g/math.gcd(n,g)**2)

```

Try it online!
> 1 votes

# Answer
# Pyth, 13 bytes

```
/*QKs_`Q^iKQ2

```

**Try it here!**

# Pyth, 15 bytes

This uses Adnan's approach and takes input as a String.

```
KsM_BQ*Fm/diFKK

```

**Try it here**
> 1 votes

# Answer
# Japt, ~~13~~ ~~12~~ 11 bytes

```

sw
*V/yU ²
```

Try it

---

## Explanation

Implicit input of integer `U`. The empty line at the beginning, prevents the following line from overwriting `U`

```
sw

```

Convert `U` to a string (`s`), reverse it (`w`), convert back to an integer and assign to variable `V`.

```
*V

```

Multiply `U` by `V`.

```
/

```

Divide.

```
yU

```

GCD of `V` and `U`.

```
²

```

Squared. Implicit output of resulting integer.

---

## Alternative, 13 bytes

Just because I like being able to use `N`.

```
NpUsw)mxNry)×

```

Try it
> 1 votes

# Answer
# MATL, ~~13~~ ~~12~~ 11 bytes

```
tVPU*1MZdU/

```

Try it online! Or verify all test cases.

### Explanation

```
t      % Imoplicit input: number. Duplicate
VPU    % String representation, flip, evaluate. This reverses digits
*      % Multiply input and reversed-digit version
1M     % Push the input and reversed-digit version again
Zd     % Greatest common divisor
U      % Square
/      % Divide. Implicit display

```
> 1 votes

# Answer
# Neim, 11 bytes

```
₁₁ᛦ

```

Try it online!

No GCD built-in. ;-;
> 1 votes

# Answer
# Husk, 10 bytes

```
S¤§÷o□⌋*i↔

```

Try it online!

-1 thanks to H.PWiz.
-1 thanks to Zgarb.
> 1 votes

# Answer
# x86 Machine Code, 39 bytes

```
;;; Obtain a "reversed" version of the input value.
;;;
;;; To do this, each iteration of a loop, we take the input value modulo 10,
;;; add that to our accumulator (EDI), multiply the accumulator by 10, and
;;; divide the input value by 10. x86's DIV instruction does both modulo and
;;; division as a single operation, with the cost of clobbering two output
;;; registers (EAX and EDX). We clobber the input value throughout the loop
;;; (the way we know we're done is when it becomes 0---that means that we have
;;; pulled all of the digits off of it), so we need to save a copy of it first.
89 C8           mov    eax, ecx     ; make copy of input
31 FF           xor    edi, edi     ; clear accumulator
6A 0A           push   10
5E              pop    esi          ; set ESI to 10
             Reverse:
0F AF FE        imul   edi, esi     ; accumulator *= 10
99              cdq                 ; zero EDX in preparation for division
F7 F6           div    esi          ; EDX:EAX / 10 (EAX is quot, EDX is rem)
01 D7           add    edi, edx     ; accumulator += remainder
85 C0           test   eax, eax     ; was quotient 0?
75 F4           jnz    Reverse      ; if not, keep looping and extracting digits

;;; At this point, EAX is 0 (clobbered throughout the loop),
;;; ECX still contains a copy of our original input, and
;;; EDI contains the 'reversed' input.
89 C8           mov    eax, ecx     ; make another copy of the input
F7 E7           mul    edi          ; multiply input (implicit EAX operand)
                                    ;  by 'reversed', with result in EDX:EAX
                                    ;  (note: EDX will be 0)

;;; Compute the greatest common denominator (GCD) of the input and
;;; the 'reversed' values, using a subtraction-based algorithm.
             GCD_0:
39 CF           cmp    edi, ecx     ; compare the two values
72 02           jb     GCD_1        ; go to GCD_1 if less than
87 F9           xchg   ecx, edi     ; swap values
             GCD_1:
29 F9           sub    ecx, edi     ; subtract
75 F6           jnz    GCD_0        ; if sum != 0, go back to the top

;;; Square the GCD.
0F AF FF        imul   edi, edi

;;; Divide the product of input and 'reversed' by the square of the GCD.
;;; Remember from above that the product of input and 'reversed' is in
;;; the EAX register, and we can assume EDX is 0, so we don't need to do
;;; a CDQ here in preparation for the division. Using EAX as the implicit
;;; source operand saves us a byte when encoding DIV.
F7 F7           div    edi

;;; The DIV instruction placed the quotient in EAX,
;;; which is what we want to return to the caller.
C3              ret

```

The above function computes the "uncommon factor number" of the specified input parameter. Following the register-based \__fastcall calling convention, the parameter is passed in the `ECX` register. The result is returned in the `EAX` register, as with all x86 calling conventions.

**Try it online!**

This took an awfully long time to write in such a compact form, but it was a fun exercise. Lots of contortions to get the most optimal register scheduling possible, within the constraints of the x86 `DIV` instruction's implicit operands and trying to use short encodings of `MUL` and `XCHG` instructions whenever possible. I'd be very curious to see if someone can think of another way to shorten it further. My brain was quite fried by the end. Thank a compiler next time you see one! (Although this is *way* better code than what a compiler would generate... Especially if you tweaked it slightly without size constraints, removing things like `XCHG`.)
> 1 votes

# Answer
# Jelly, 7 bytes

```
ṚḌæl:gɗ

```

Try it online!

-1 byte thanks to ovs

Similar to Erik's Jelly answer, but uses a dyadic route rather than monadic lists.

Uses the formula found by ovs

$$\text{UCF}(n) = \frac{\text{lcm}(n,\text{rev}(n))}{\gcd(n, \text{rev}(n))}$$

## How it works

```
ṚḌæl:gɗ - Main link. Takes n on the left
Ṛ       - Split n into digits and reverse
 Ḍ      - Convert back into an integer; rev(n)
      ɗ - Combine the previous three links into a dyad
           with n on the right and rev(n) on the left:
  æl    -   lcm(n,rev(n))
     g  -   gcd(n, rev(n))
    :   -   Divide lcm(n,rev(n)) by gcd(n, rev(n))

```
> 1 votes

# Answer
# APL (Dyalog Extended), 9 bytes

```
⊢(∧÷∨)⌽⍢⍕

```

Try it online!

$$\text{UCF}(n) = \frac{n\times \text{rev}(n)}{\gcd(n, \text{rev}(n))^2} = \frac{\text{lcm}(n,\text{rev}(n))}{\gcd(n,\text{rev}(n))} = \frac{\text{lcm}}{\gcd}(n,\text{rev}(n))$$

reverse  under  conversion to string, then apply `∧÷∨` (lcm ÷ gcd) between the result and and the original argument.
> 1 votes

# Answer
# Pyt, 11 bytes

```
ĐĐ₫Đ3Ș*↔Ǥ²/

```

Try it online!

| Code | Stack | Description |
| --- | --- | --- |
| Đ | n,n | Implicit input; duplicate top of stack |
| Đ | n,n,n | Duplicate top of stack |
|  | n,n,rev(n) | Reverse the digits of the top of the stack |
| Đ | n,n,rev(n),rev(n) | Duplicate top of stack |
|  | n,rev(n),rev(n),n | Flip the order of the top three items on the stack |
| * | n,rev(n),rev(n)\*n | Multiply the top two items on the stack |
|  | rev(n)\*n,rev(n),n | Flip the stack |
| Ǥ² | rev(n)\*n,gcd(n,rev(n))^2 | Take the gcd of n and rev(n) and square it |
| / | rev(n)\*n/(gcd(n,rev(n))^2) | Divide; implicit print |
> 1 votes

# Answer
# Java 8, ~~158~~ ~~150~~ ~~148~~ ~~138~~ ~~125~~ ~~123~~ ~~116~~ 107 ~~\+ 19~~ bytes

```
i->{int o,r,f,t=f=i;i=r=i.valueOf(""+new StringBuffer(t+"").reverse());while(t>0)t=i%(i=t);return f/i*r/i;}

```

Try it online!
> 0 votes

# Answer
# Python 2, 70 bytes

Thanks to i cri everytim.

```
def f(n):g=int(`n`[::-1]);print n*g/gcd(n,g)**2
from fractions import*

```

Try it online!

# Python 2, 77 bytes

Note that in Python 2, you cannot use the `math.gcd()` method, and you must do it "by hand".

```
y=lambda a,b:b and y(b,a%b)or a
def f(n):g=int(`n`[::-1]);print n*g/y(n,g)**2

```

Try it online!
> 0 votes

# Answer
# Perl 5, 72 bytes

71 bytes of code + 1 flag (`-p`)

```
$t=$_*($b=reverse);($_,$b)=(abs$_-$b,$_>$b?$b:$_)while$_-$b;$_=$t/$_**2

```

Try it online!
> 0 votes

# Answer
# Pyke, 8 bytes

```
_]FbP).^B

```

Try it here!

Takes input as a string.

```
_         -    reversed(input)
 ]        -   [^, input]
  FbP)    -  for i in ^:
   b      -     int(^)
    P     -    factors(^)
      .^  -  xor_seq(^)
        B - product(^)

```
> 0 votes

# Answer
# Ohm, 9 bytes

```
DR«D]Æ┴/µ

```

Try it online!
> 0 votes

# Answer
# Vyxal, 7 bytes

```
Ṙ∆Ŀ?Ḃġ/

```

Try it Online!

```
Ṙ       # Reverse
 ∆Ŀ     # LCM with that
   ?    # Take input
    Ḃ   # Dupe-reverse
     ġ  # GCD
      / # Quoitent

```

Would be 5 bytes if parallel apply worked with digraphs.
> 0 votes

# Answer
# J-uby, 25 bytes

Uses ovs' technique.

```
:/%[:lcm%r=S|:~|Z,:gcd%r]

```

Attempt This Online!

## Explanation

```
:/ % [:lcm % r = S | :~ | Z, :gcd % r]

             r = S | :~ | Z             # Helper function: Convert to string, reverse, convert back to int
:/ % [                     ,         ]  # Divide...
      :lcm % r                          #   LCM of input and its reverse by
                             :gcd % r   #   GCD of input and its reverse

```

## J-uby, 32 bytes

We can get rid of the awkward helper function `r` but at a cost of seven bytes:

```
:/%(-[:%&:lcm,:%&:gcd]^(S|:~|Z))

```

Attempt This Online!
> 0 votes

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


# Question
Title: Smallest and largest 100-bit square with maximum Hamming weight
# Introduction

In the binary representation of a \\$k-\\$bit \\$(k\>1)\\$ square number \\$n^2, \\$ not all bits can be \\$1\\$. The maximum number of \\$1\\$-bits (Hamming weight, \\$B\\$ for short) is given in A357658, but only up to \\$k=95\\$ bits.

An example of a \\$99\\$-bit square is \\$B(796095014224053^2)=87\\$. The records in A357304 show that \\$B(m^2)\<88\\$ for a \\$100\\$-bit square \\$m^2\\$, and that the computation is feasible.

# Challenge

Your task is to write a **fastest-code** program which determines

* \\$B\_{max}(n^2)\\$
* \\$n\_{min}\\$
* \\$n\_{max}\\$

in the range of \\$100\\$-bit squares \\$n^2\\$ with \\$796131459065722\le n\le 1125899906842623\\$

with the smallest number \\$n\_{min}\\$ and the largest number \\$n\_{max}\\$ such that \\$B(n\_{min}^2)=B(n\_{max}^2)=B\_{max}\\$.

A brute force calculation visiting all squares \\$n^2\\$ in the given range is possible, but takes a very long time, even if the multiplication is implemented efficiently with the instruction set for the available hardware. See this question on Stack Overflow.

Is it possible to avoid actually performing all the multiplications? The program that determines the 3 numbers \\$B\_{max}, n\_{min}, n\_{max}\\$ in the shortest run time wins.

# Test

To test the order of magnitude of a program's speed, it can be applied to the interval \\$1085300000000000\le n \le 1085312000000000\\$. The interval contains \\$2\\$ numbers with \\$82\\$ \\$1\\$-bits. The length of this interval is approximately \\$1/27500\\$ of the total range to be searched. You can then decide if you want to try the full range.

The results will be used in a planned extension of the OEIS sequences A357658, A357659, and A357660, giving credit to the authors of the fastest programs.

# Answer
# Rust w/ Rayon -- 0.9s runtime, 6.7s cputime for whole range

```
(1/99) a=0 1 (best: 0)
(2/49) b=2 4 (best: 50)
(3/27) a=1 49 (best: 72)
(4/23) b=3 188 (best: 76)
(5/21) a=2 1176 (best: 78)
(6/17) b=4 4332 (best: 82)
(7/15) a=3 18424 (best: 84)
(8/15) b=5 65220 (best: 84)
(9/15) a=4 211876 (best: 84)
(10/15) b=6 721396 (best: 84)
(11/15) a=5 1906884 (best: 84)
(12/15) b=7 6249964 (best: 84)
(13/14) a=6 13983816 (best: 85)
(14/14) b=8 44156732 (best: 85)

B_max: 85
n_min: 933544295655093
n_max: 1125891114428899

Found values: 1121216655081291 1043134657624555 1120665056942829 1116514939453621 933544295655093 1125074802425067 1124798782678823 1125891114428899 1090147221387163

100 85 933544295655093 1125891114428899

________________________________________________________
Executed in  909.41 millis    fish           external
   usr time    6.70 secs      0.00 micros    6.70 secs
   sys time    0.02 secs    516.00 micros    0.02 secs

```

Output of `time max_square 100`

Tested on my laptop with 4 cores (8 virtual) @ ~4.5 GHz

```
use std::{str::FromStr, collections::HashSet};
use rayon::prelude::*;
use std::sync::{Arc, Mutex};
use std::sync::atomic::{AtomicU32, Ordering};
use rayon::iter;

fn solve(n: u32, verbose: bool) {
    if n < 6 {
        match n {
            1 => {println!("1 1 1 1")},
            2 => {println!("None")},
            3 => {println!("3 1 2 2")},
            4 => {println!("4 2 3 3")},
            5 => {println!("5 3 5 5")},
            _ => {println!("Error");}
        }
        return;
    }
    let mut best = Solution::new(n);
    let mut a = 0;
    let mut b = 2;
    while best.get_best() + a + b <= n {
        let cost_a = calculate_cost_a(n, a);
        let cost_b = calculate_cost_b(n, b);
        if cost_a < cost_b {
            if verbose {eprintln!("({}/{}) a={} {} (best: {})", a+b-1, n - best.get_best() - 1, a, cost_a, best.get_best());}
            step_a(n, a, &mut best);
            a += 1;
        } else {
            if verbose {eprintln!("({}/{}) b={} {} (best: {})", a+b-1, n - best.get_best() - 1, b, cost_b, best.get_best());}
            step_b(n, b, &mut best);
            b += 1;
        }
    }
    let solutions = best.solutions.lock().unwrap();
    if verbose {
        eprintln!("");
        eprintln!("B_max: {}", best.get_best());
        eprintln!("n_min: {}", solutions.iter().min().expect("No solutions"));
        eprintln!("n_max: {}", solutions.iter().max().expect("No solutions"));
        eprintln!("");
        eprint!("Found values: ");
        for z in solutions.iter() {
            eprint!("{} ", z);
        }
        eprintln!("");
        eprintln!("");
    }
    println!("{} {} {} {}", n, best.get_best(), solutions.iter().min().expect("No solutions"), solutions.iter().max().expect("No solutions"));
}

fn calculate_cost_a(n: u32, a: u32) -> i64 {
    let a = a as i64;
    let n = n as i64;
    binomial((n-1)/2, a)
}

fn step_a(n: u32, a: u32, best: &Solution) {
    let h = n / 2;
    iter::split(
        Combinator::with_prefix_postfix(n, a, 1, 1, (1 << h) - 1, h),
        split_combinator).flatten_iter()
        .for_each(|z|{
            best.update(isqrt(z));
        }
    );
}

fn calculate_cost_b(n: u32, b: u32) -> i64 {
    let b = b as i64;
    let n = n as i64;
    (1..b/2 + 1).map(|i| (1<<i) * binomial(n/2 - 1 - 2*i, b - 2*i)).sum::<i64>() * 2
}

fn step_b(n: u32, b: u32, best: &Solution) {
    let m = (1 << ((n + 1) / 2)) - 1;
    for k in 0..b/2 {
        let w = ((n + 1) / 2) - 3 - 2*k;
        iter::split(Combinator::new(w, b - 2 - 2*k, 1, 3), split_combinator).flatten_iter()
            .for_each(|a| {
                let x = modsqrt(w + 3, a) << k;
                let mut z = 1 << ((n + 1) / 2);
                let step_size = 1 << (((n + 1) / 2) - 1 - k);
                while z > 0 {
                    z -= step_size;
                    best.update((z + x)&m);
                    best.update((z - x)&m);
                }
            }
        );
    }
}

fn modsqrt(n: u32, a: i128) -> i128 {
    let mut x = 1;
    let m = (1<<n) - 1;
    for _ in 3..n {
        x = (((x*x - a) >> 1) + x) & m;
    }
    x
}

fn isqrt(n: i128) -> i128 {
    let mut x = (n as f64).sqrt() as i128;
    if x*x <= n {
        x += 1;
        while x*x <= n {
            x += 1;
        }
        x-1
    } else {
        x -= 1;
        while x*x > n {
            x -= 1;
        }
        x
    }
}

fn binomial(n: i64, k: i64) -> i64 {
    let k = std::cmp::min(k, n-k);
    if k < 0 {return 0;}
    if k == 0 {return 1;}
    let mut c: i64 = 1;
    for i in 0..(k as i64) {
        c = (c * (n-i)) / (i + 1);
    }
    c
}

struct Combinator {
    curr: i128,
    mask: i128,
    offset: u32,
    min: i128,
    max: i128,
    k: u32,
}

impl Combinator {
    fn new(width: u32, num_zeros: u32, mask: i128, offset: u32) -> Combinator {
        Combinator { curr: (1 << width) - (1 << num_zeros), mask: mask, offset: offset, min: 0, max: binomial(width as i64, num_zeros as i64) as i128, k: width - num_zeros }
    }

    fn with_prefix_postfix(full_width: u32, num_zeros: u32, prefix: i128, prefix_width: u32, postfix: i128, postfix_width: u32) -> Combinator {
        let width = full_width - prefix_width - postfix_width;
        Combinator::new(width, num_zeros, (prefix << (width + postfix_width)) + postfix, postfix_width)
    }
}

// calculates the next combination, in reverse lexicographic order
fn next_combination(n: i128) -> i128 {
    if n&1 == 0 {return n - (((n^(n-1))+1)>>2);}
    let a = (n^(n+1))>>1;
    let na = n-a;
    if na == 0 {return na;}
    let b = ((na ^ (na-1))>>2) - a;
    if b == 0 {return na - 1;}
    let b = b >> b.trailing_zeros();
    na - 1 - b
}

impl Iterator for Combinator {
    type Item = i128;

    fn next(&mut self) -> Option<Self::Item> {
        if self.min == self.max {return None;}
        let curr = self.curr;
        self.max -= 1;
        self.curr = next_combination(curr);
        Some(self.mask | (curr << self.offset))
    }
}

// combinatorial number system
fn ntoc(n: i128, k: i128) -> i128 {
    if k == 0 {return 0;}
    if n == 0 {return (1<<k) - 1;}
    let mut x = k;
    let mut xck = 1; // x choose k
    let mut x1ck = k+1; // x+1 choose k
    while x1ck <= n {
        xck = x1ck;
        x += 1;
        x1ck = (xck * (x + 1)) / (x + 1 - k);
    }
    ntoc(n - xck, k-1) + (1 << x)
}

fn split_combinator(c: Combinator) -> (Combinator, Option<Combinator>) {
    if c.max - c.min <= 100000 {return (c, None);}
    let midpoint = c.min + (c.max - c.min) / 2;
    (Combinator {curr: ntoc(midpoint, c.k as i128), min: c.min, max: midpoint, mask: c.mask, offset: c.offset, k: c.k}, Some(Combinator {curr: c.curr, min: midpoint, max: c.max, mask: c.mask, offset: c.offset, k: c.k}))
}

struct Solution {
    best: AtomicU32,
    minz: i128,
    maxz: i128,
    solutions: Arc<Mutex<HashSet<i128>>>,
}

impl Solution {
    fn update(&self, z: i128) {
        if z < self.minz {return;}
        if z > self.maxz {return;}
        let z2 = z*z;
        let z2c = z2.count_ones();
        let prev = self.best.fetch_max(z2c, Ordering::Relaxed);
        if z2c < prev {return;}
        let mut solutions = self.solutions.lock().unwrap();
        if z2c > prev {
            solutions.clear();
        }
        solutions.insert(z);
    }
    fn new(width: u32) -> Solution {
        Solution {best: AtomicU32::new(0), minz: isqrt((1 << (width - 1)) - 1) + 1, maxz: isqrt(1 << width), solutions: Arc::new(Mutex::new(HashSet::new()))}
    }
    fn get_best(&self) -> u32 {
        self.best.load(Ordering::Relaxed)
    }
}

fn main() {
    let args: Vec<String> = std::env::args().collect();
    let i = match args.len() {
        2 => (1, true),
        3 => {
            if args[1] == "-q" {
                (2, false)
            } else if args[2] == "-q" {
                (1, false)
            } else {
                println!("Usage: max_square [-q] [number of bits]");
                return;
            }
        },
        _ => {
            println!("Usage: max_square [-q] [number of bits]");
            return;
        },
    };
    if let Ok(n) = u32::from_str(&args[i.0]) {
        solve(n, i.1);
    } else {
        println!("Error reading args");
    }
}

```

## Explanation

We'll let \\$n\\$ be the number of bits (100) in the squares we're searching.

This algorithm has two types of steps that corresponding to fixing the most significant / least significant half of the square.

While there are possible solutions remaining, we chose between the two step types based on which would require fewer operations.

#### Step type \\$a\\$:

Range over all integers \\$x\\$ with \\$\left\lceil\frac{n}{2}\right\rceil-1\\$ bits of which \\$a\\$ are zero.

For each \\$x\\$ there is at most one natural number \\$z\\$ for which

$$ \underbrace{1x0\ldots0}\_{n\text{ bits}} \le z^2 \le \underbrace{1x1\ldots1}\_{n\text{ bits}} $$

After updating our solutions with those \\$z^2\\$, assuming we already checked the previous values of \\$a\\$, we now know that all unchecked squares have at least \\$a+1\\$ zeros in the first half.

#### Step type \\$b\\$:

Range over integers \\$k\\$ and \\$x\\$ where \\$2+2k\le b\\$ and \\$x\\$ has \\$\left\lceil\frac{n}{2}\right\rceil-3-2k\\$ bits of which \\$b-2-2k\\$ are zero.

For each \\$x\\$, \\$k\\$ there are \\$4\cdot2^k\\$ values of \\$z\\$ (mod \\$2^{\left\lceil\frac{n}{2}\right\rceil}\\$) satisfying

$$ z^2\equiv \underbrace{x001\[00\]\times k}\_{\left\lceil\frac{n}{2}\right\rceil\text{ bits}}\mod2^{\left\lceil\frac{n}{2}\right\rceil} $$

After updating our solutions with those \\$z^2\\$, assuming we already checked the previous values of \\$b\\$, we now know that all unchecked squares have at least \\$b+1\\$ zeros in the first half.

## Output for n from 3 to 126

```
3 1 2 2
4 2 3 3
5 3 5 5
6 3 7 7
7 5 11 11
8 4 13 15
9 6 21 21
10 6 27 27
11 8 45 45
12 8 53 53
13 9 75 89
14 9 101 117
15 13 181 181
16 11 217 235
17 13 362 362
18 12 437 491
19 14 627 723
20 15 923 949
21 16 1241 1241
22 16 1619 1773
23 17 2505 2891
24 18 3915 3915
25 19 5221 5747
26 20 6475 7093
27 21 11309 11309
28 22 15595 16203
29 23 19637 19637
30 24 31595 31595
31 25 44491 44491
32 25 61029 64747
33 26 69451 86581
34 27 113447 113447
35 28 185269 185269
36 29 244661 244661
37 30 357081 357081
38 31 453677 453677
39 31 642119 738539
40 34 980853 980853
41 33 1380917 1481453
42 34 1961706 2079669
43 37 2965685 2965685
44 37 3923411 3923411
45 38 5931189 5931189
46 38 8096813 8222581
47 39 11862197 11862965
48 39 16244453 16244453
49 41 22193965 22193965
50 41 32988235 32988235
51 42 43586515 47450235
52 44 57804981 57804981
53 44 94905541 94905541
54 44 115609962 134053275
55 46 164382389 177549685
56 47 268123979 268123979
57 47 320528203 379526189
58 49 528407335 528407335
59 50 657506485 657506485
60 51 888717493 888717493
61 52 1510322221 1510322221
62 52 2100772683 2111529939
63 53 2630119323 2630119323
64 54 4227325771 4227325771
65 55 5853487285 5853487285
66 55 8580481947 8580481947
67 57 10520476455 10520476455
68 57 14878203147 17110519093
69 58 21040953067 24295633269
70 59 31469977781 31469977781
71 62 48589783221 48589783221
72 63 66537313397 66537313397
73 62 97179566261 97179566442
74 63 133074626794 133074626794
75 64 194366549037 194366549037
76 64 259365748555 274835944267
77 66 388730126517 388730126517
78 66 475016392885 540779528373
79 68 759031429451 759031429451
80 68 1064500084555 1081632748507
81 68 1503999171957 1554929409435
82 69 2055848542027 2197923974325
83 70 2576736968885 3109840793419
84 72 3646667521867 4362198168395
85 72 5384675514549 6216643955893
86 73 8445509046091 8791729601637
87 74 11620627528805 11937419436213
88 76 17435796250805 17435796250805
89 76 21537910687315 24879106612889
90 77 34895284158283 34895284158283
91 77 39275570260917 49752141391123
92 78 60940798018325 68134217006923
93 80 93089098383179 93089098383179
94 80 121861586862261 139768858984629
95 81 184920521899109 199030966469849
96 82 222524145495085 222524145495085
97 85 398064946368587 398064946368587
98 84 461438710099403 562672855105355
99 87 796095014224053 796095014224053
100 85 933544295655093 1125891114428899
101 88 1592054863872923 1592054863872923
102 88 2233021208375059 2233021208375059
103 89 3153273599102795 3153273599102795
104 90 4498915668727861 4498915668727861
105 92 6354993066190667 6354993066190667
106 91 7790298568288075 8721180941868443
107 92 12709986132381334 12711635715085643
108 93 18005548694652121 18005548694652121
109 94 25469208479569437 25469208479569437
110 94 30874441840049387 36004547995030069
111 95 47233732013276085 50801164553247509
112 96 66646890995961483 72057405025529767
113 99 101480601046523531 101480601046523531
114 98 143542302959229109 143542302959229109
115 99 202961202093047062 202961202093047062
116 101 269614819660724085 269614819660724085
117 101 403417952942237229 403417952942237229
118 101 529472308325235947 576458535517221045
119 103 808844333869390923 808844333869390923
120 103 970104967079909557 1143803445656875189
121 104 1578696363991412555 1630401033738048053
122 106 1996776422069106507 2156918025961517429
123 106 2688433943050910795 3260133329992761163
124 107 4575515161264941861 4605489388616186187
125 108 6518622390190614475 6518622390190614475
126 110 7977185712837244873 7977185712837244873

________________________________________________________
Executed in  498.22 secs    fish           external
   usr time   65.63 mins   15.29 millis   65.63 mins
   sys time    0.03 mins   19.41 millis    0.03 mins

```
> 6 votes

# Answer
# Going further

```
49 41 22193965 22193965
50 41 32988235 32988235
51 42 43586515 47450235
52 44 57804981 57804981
53 44 94905541 94905541
54 44 115609962 134053275
55 46 164382389 177549685
56 47 268123979 268123979
57 47 320528203 379526189
58 49 528407335 528407335
59 50 657506485 657506485
60 51 888717493 888717493
61 52 1510322221 1510322221
62 52 2100772683 2111529939
63 53 2630119323 2630119323
64 54 4227325771 4227325771
65 55 5853487285 5853487285
66 55 8580481947 8580481947
67 57 10520476455 10520476455
68 57 14878203147 17110519093
69 58 21040953067 24295633269
70 59 31469977781 31469977781
71 62 48589783221 48589783221
72 63 66537313397 66537313397
73 62 97179566261 97179566442
74 63 133074626794 133074626794
75 64 194366549037 194366549037
76 64 259365748555 274835944267
77 66 388730126517 388730126517
78 66 475016392885 540779528373
79 68 759031429451 759031429451
80 68 1064500084555 1081632748507
81 68 1503999171957 1554929409435
82 69 2055848542027 2197923974325
83 70 2576736968885 3109840793419
84 72 3646667521867 4362198168395
85 72 5384675514549 6216643955893
86 73 8445509046091 8791729601637
87 74 11620627528805 11937419436213
88 76 17435796250805 17435796250805
89 76 21537910687315 24879106612889
90 77 34895284158283 34895284158283
91 77 39275570260917 49752141391123
92 78 60940798018325 68134217006923
93 80 93089098383179 93089098383179
94 80 121861586862261 139768858984629
95 81 184920521899109 199030966469849
96 82 222524145495085 222524145495085
97 85 398064946368587 398064946368587
98 84 461438710099403 562672855105355
99 87 796095014224053 796095014224053
100 85 933544295655093 1125891114428899
101 88 1592054863872923 1592054863872923
102 88 2233021208375059 2233021208375059
103 89 3153273599102795 3153273599102795
104 90 4498915668727861 4498915668727861
105 92 6354993066190667 6354993066190667
106 91 7790298568288075 8721180941868443
107 92 12709986132381334 12711635715085643
108 93 18005548694652121 18005548694652121
109 94 25469208479569437 25469208479569437
110 94 30874441840049387 36004547995030069
111 95 47233732013276085 50801164553247509
112 96 66646890995961483 72057405025529767
113 99 101480601046523531 101480601046523531
114 98 143542302959229109 143542302959229109
115 99 202961202093047062 202961202093047062
116 101 269614819660724085 269614819660724085
117 101 403417952942237229 403417952942237229
118 101 529472308325235947 576458535517221045
119 103 808844333869390923 808844333869390923
120 103 970104967079909557 1143803445656875189
121 104 1578696363991412555 1630401033738048053
122 106 1996776422069106507 2156918025961517429
123 106 2688433943050910795 3260133329992761163
124 107 4575515161264941861 4605489388616186187
125 108 6518622390190614475 6518622390190614475
126 110 7977185712837244873 7977185712837244873

```

127 overflows basic type X( (maybe) Odd

Try it online!

All files.tar.xz
> 4 votes

# Answer
# c++ - 6s whole range (single threaded)

Attempt this online!

This algorithm has two stages where the first stage checks some very unlikely possibilities for optimal squares. Then stage 2 checks the rest of the possibilities, and gains a massive performance boost from the knowledge of stage one.

More specifically we are interested in where the zeroes are in the square. In stage 1 we assume all but at most `max_upper_zeros` are located in the lower half (bottom 50 bits) of the square. We just brute force trough all possible upper halves of the square, check if they have a square root and if so, remember that value as a potential solution.

Now in stage 2 we enumerate all possibilities, except the ones checked in stage 1. Thus in stage 2 we can assume that the upper half contains at least `max_upper_zeros + 1` zeros.

This algorithm has "steps". In step `b` we enumerate all possible lower segments of `b` bits of the root. At step 50 we have enumerated all possible roots and can calculate how many ones the corresponding squares have.

As stated, this would not make the calculation any faster than brute force, however we can use the following trick: the `b` lowest bits of the root determine the `b` lowest bits of the square. Therefore we can get an upper bound to the number of ones in the square from the lowest `b` bits, which allows us to discard numbers at early steps of stage 2.

The stage 2 algorithm is run with a "target hamming weight" `tg`. This is the (minimum) number of ones that we want in the square. We start with `tg=100` and decrement until we find solutions.

The stage 2 algorithm in the following code is quite optimized since I invented it first. It has manual tail-call elimination and it only considers odd numbers (odd solutions can be trivially converted to even solutions). The variable p stores the number of bits in the initial segment with a bias given by `tg` and `max_upper_zeros`.

The code outputs some stats to stderr and writes the solution to stdout.

```
#include <vector>
#include <algorithm>
#include <iostream>
#include <bit>
#include <cmath>

const int LIM = 50;
const int TB = LIM*2;
const unsigned long long RANGE_START = 796131459065722;
const unsigned long long RANGE_END = 1125899906842623;

std::vector<unsigned long long> solutions = {};

// Stage 2
void count(int tg, int b, int p, unsigned long long v) {
    unsigned __int128 mul = v * (unsigned __int128)v;
    while (b < LIM) {
        int bit = (mul >> b) & 1;
        unsigned long long vp = v | (1ull << b);
        p+= bit;
        b+= 1;
        // Here we discard solutions that don't have enough ones
        // in the first b bits
        if (p < b) {
            return;
        }
        count(tg, b, p, vp);
    }
    if (__builtin_expect(std::__popcount(mul) >= tg, 0)) {
        // Account for taking into account only odd numbers
        while (RANGE_START > v) {
            v<<= 1;
        }
        if (RANGE_START <= v && v <= RANGE_END) {
            std::cerr << "Found solution " << v << std::endl;
            solutions.push_back(v);
        }
    }
}

unsigned long long isqrt(unsigned __int128 x) {
    unsigned long long apprx = (unsigned long long) sqrt((double)x);
    while (apprx * (unsigned __int128) apprx > x) {
        apprx-= 1;
    }
    return apprx;
}

int main() {
    // First try to find solutions with at most max_upper_zeros zeros in the upper half
    const int max_upper_zeros = 7;

    std::vector<unsigned long long> initial_solutions = {};
    int best_hamming_weight = 0;

    unsigned long long upper_neg = 0;
    while (upper_neg < (1ull << LIM)) {
        unsigned long long upper = ((1ull << LIM)-1)^upper_neg;
        unsigned __int128 m = ((unsigned __int128)upper << LIM);

        unsigned long long v = isqrt(m);
        do {
            unsigned __int128 mul = v * (unsigned __int128)v;
            unsigned long long upp = mul >> LIM;
            if (upp > upper) {
                break;
            }
            if (upp < upper) {
                continue;
            }
            int ones = std::__popcount(mul);
            if (ones >= best_hamming_weight && RANGE_START <= v && v <= RANGE_END) {
                if (ones > best_hamming_weight) {
                    initial_solutions.clear();
                    best_hamming_weight = ones;
                }
                initial_solutions.push_back(v);
            }
        } while (v++);
        if (std::__popcount(upper_neg) == max_upper_zeros) {
            upper_neg = (upper_neg | (upper_neg - 1)) + 1;
        } else {
            upper_neg+= 1;
        }
    }

    std::cerr
    << "First stage found the following solutions with hamming weight "
    << best_hamming_weight << ":" << std::endl;
    for (auto &s: initial_solutions) {
        std::cerr << s << std::endl;
    }

    // Then use this knowledge to calculate solutions more efficiently
    int tg = TB;;
    for (; tg >= best_hamming_weight; --tg) {
        count(tg, 1, 1 + TB - tg - max_upper_zeros, 1);
        std::cerr << "Calculated target " << tg << std::endl;
        if (!solutions.empty()) {
            break;
        }
    }

    if (tg + 1 == best_hamming_weight) {
        solutions.insert(solutions.end(),initial_solutions.begin(),initial_solutions.end());
    }

    unsigned long long min = *std::min_element(solutions.begin(), solutions.end());
    unsigned long long max = *std::max_element(solutions.begin(), solutions.end());
    int ones = std::__popcount(min * (unsigned __int128)min);

    std::cout << ones << std::endl << min << std::endl << max << std::endl;

    return 0;
}

```
> 2 votes

---
Tags: binary, fastest-code, bitwise
---


title: CGAC2022 Day 19: I Made It Out Of Clay

text:
# Question
Title: CGAC2022 Day 19: I Made It Out Of Clay
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

Happy Hanukkah!

A beloved Hanukkah tradition for many, the game of Dreidel (*s'vivon* in Hebrew) is a betting game (for money or for chocolate *gelt* (coins)) centered on the titular spinning tops called dreidels. Dreidels have four sides: נ (nun), ג (gimel), ה (hei), and ש (shin), an acronym for the phrase "neis gadol haya sham": a great miracle happened there, referring to the famous Hanukkah miracle.

The game starts with an ante of one coin put forth by all players. Then, players take turns spinning the dreidel and lose or gain money according to the following rules:

* נ (nun): Do nothing
* ג (gimel): Win all the money in the pot
* ה (hei): Win half the money in the pot, rounding up
* ש (shin): Add one coin to the pot

If at any point the pot becomes empty, all players put forth one coin. If a player must put forth a coin and they have none, they are out of the game. The game ends when players agree to stop or when only one player is remaining.

---

## Task

Your task is to implement the game of Dreidel.

Input:

* (mapping: str -\> int) A number of players, guaranteed to be ≥2, each represented by a string. Each player maps to the starting number of coins for that player, guaranteed to be ≥1.
* (int) The number of rounds, guaranteed to be ≥1. (In each round, every player who's still in the game will spin the dreidel once).

Output:

* (mapping: str -\> int) Each player and their corresponding final number of coins at the end of the game.

Rules:

* Standard rules of apply. Shortest answer in bytes wins!
* Dreidel outcomes must be random, and must appear with the same probability (25% for each outcome).
* Any reasonable form of input or output is allowed. For instance, to represent the mapping of players to coins, one can use a Python-style dictionary, an array of pairs, etc. The mapping need not have a consistent ordering.
    + All players must be represented in the output, even if they have no money left.
* You can use whatever order for the players within each round is easiest, as long as each player who's still in the game spins once per round.

Notes:

* It is not guaranteed that the total number of coins at the end of the game is equal to the total number of coins at the beginning of the game (there may be some left over in the pot.)

Examples: (bear in mind that results are random)

```
>>> dreidel({"Abraham": 5, "Batya": 5, "Claire": 5}, 3)
{"Abraham": 3, "Batya": 8, "Claire": 4}

>>> dreidel({"David": 3, "Eliana": 9, "Fievel": 2, "Gabriella": 2}, 15)
{"David": 0, "Eliana": 16, "Fievel": 0, "Gabriella": 0}

```

# Answer
# Python, ~~197~~ 195 bytes

-2 bytes thanks to @Arnauld using `-~p//2` instead of `p//2+p%2`

```
from random import*
def f(n,c,m,i=0,p=0,s=0):
 l=len(c);v=-~c[x:=i%l]and[-1,0,p,~-p//2][i//l&(s<0)and randrange(4)];c[x]+=v
 if~-l-c.count(-1)and-~i<m*l:f(n,c,m,i+1,w:=p-v*(c[x]>=0),[s-1,l][w<1])

```

Attempt This Online!

Takes in the mapping as a list of names `n` and a list of coin counts `c` which are the same length, along with a number of rounds `r`.

Modifies the list of coins in place; the values indicate the number of coins, except for if `c[i]` is `-1`, which indicates that person `n[i]` is out of the game.

It works recursively, storing the following between calls (in addition to the current number of coins):

* `i`: How many players have played so far
* `p`: the size of the pot
* `s`: If positive, how many players need to contribute to the pot (set to `len(c)` when the pot is empty, otherwise decreased by one every call)
> 4 votes

# Answer
# Python 3, ~~317 303 311 318 294~~ 270 bytes

```
def f(p,r):
 m=len(p)
 for k in p:p[k]-=1
 for _ in range(r):
  for i in p:
   if p[i]<0:continue
   x=randrange(4)
   if x<1:p[i]+=m;m=0
   if x<2:p[i]-=~m//2;m+=~m//2
   if x>2:m+=p[i]>0;p[i]-=1
   if m<1:
    for j in p:m+=p[j]>0;p[j]-=1
 return p
from random import*

```

Try it online!

* Thanks to Neil for spotting a bug (303 -\> 311)
* Thanks to AAM111 for cutting out the `import math` and spotting a bug (311 -\> 318)
* Thanks to c-- for some golfing suggestions (318 -\> 294 and 294 -\> 270)

Players that are out are shown as having negative coins.

### Explanation

```
def f(p,r):                                # Create a function, f, which takes in the player dictionary, p, and the number of rounds, r
 m=len(p)                                  # Assign the money pot, m, to the number of players
 for k in p:p[k]-=1                        # And subtract one from each of the players (each player gives one coin to the pot)
 for _ in range(r):                        # Loop r times (r rounds)
  for i in p:                              # Go through each of the players
   if p[i]<0:continue                      # If they are out of the game (money = -1), skip their turn
   x=randrange(4)                          # Spin the dreidel (0 to 3)
   if x<1:0                                # If it's 0, do nothing
   elif x<2:p[i]+=m;m=0                    # If it's 1, add all the money from m to that player and set m to 0
   elif x<3:a=(int(m)+m%2)//2;p[i]+=a;m-=a # If it's 2, add half the money to that player and reduce m
   else:m+=1;p[i]-=1                       # If it's 3, add 1 to m and remove 1 from the player
   if m<1:                                 # If m is 0
    for j in p:                            # Go through each player
     if p[j]>0:p[j]-=1;m+=1                # If they're not out of money, reduce by one and add that to m
     else:p[j]=-1                          # Otherwise, set their money to -1 (they are now out)
 return p                                  # At the end of all the rounds, return the final dictionary
from random import*                        # Import the random library for the dreidel

```
> 4 votes

# Answer
# Charcoal, 112 bytes

```
≔Ｌθζ≧×ＬθηＵＭθ⊖ιＷ∧η⊖ＬΦθ¬‹κ⁰«≔§Ｅθλ±ηεＦ¬‹§θε⁰«≔‽⁴κ≔⎇‹κ²κ÷ζ～κκ§≔θε⁻§θεκＦ¬‹§θε⁰≧⁺κζ»Ｆ¬ζ«≔ＬΦθ›λ⁰ζＵＭθ⊖λ»≦⊖η»ＵＭθ⎇›⁰ι⁰ι⭆¹θ`

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
≔Ｌθζ

```

Each player puts one coin into the pot.

```
≧×Ｌθη

```

The total potential number of plays is the number of players multiplied by the number of rounds.

```
ＵＭθ⊖ι

```

Subtract one coin from each player (which they put into the pot above).

```
Ｗ∧η⊖ＬΦθ¬‹κ⁰«

```

Repeat while there are still plays left and multiple players playing.

```
≔§Ｅθλ±ηε

```

Get the current player.

```
Ｆ¬‹§θε⁰«

```

If they are not out of the game:

```
≔‽⁴κ

```

Spin the dreidel, producing a random number from `0` to `3`.

```
≔⎇‹κ²κ÷ζ～κκ

```

If it is less than `2` then the player loses this amount, otherwise they lose the pot divided by the bitwise not of the random number. Since the latter is negative, they win either the pot or half of the pot rounded up.

```
§≔θε⁻§θεκ

```

Subtract the loss from the player.

```
Ｆ¬‹§θε⁰≧⁺κζ

```

If the player is still in the game then add the player's loss to the pot.

```
»Ｆ¬ζ«

```

If the pot is now zero:

```
≔ＬΦθ›λ⁰ζ

```

Put a coin into the pot for each player that is still in the game.

```
ＵＭθ⊖λ

```

Subtract one coin from each player.

```
»≦⊖η

```

Move on to the next player.

```
»ＵＭθ⎇›⁰ι⁰ι

```

Set the coins of players that are out of the game to `0`.

```
⭆¹θ

```

Output the final number of coins for each player.

I wrote this version before all of the rules had been clarified, so it appears that I might be able to save 16 bytes by considering the players in reverse order, not refreshing the pot if the first player scoops it on their very last spin, and outputting arbitrary negative values for players who are out of the game:

```
≔⁰ζ≧×ＬθηＷ∧η⊖ＬΦθ¬‹κ⁰«Ｆ¬ζ«≔ＬΦθ›λ⁰ζＵＭθ⊖λ»≦⊖η≔§ＥθληεＦ¬‹§θε⁰«≔‽⁴κ≔⎇‹κ²κ÷ζ～κκ§≔θε⁻§θεκＦ¬‹§θε⁰≧⁺κζ»»⭆¹θ

```

Attempt This Online! Link is to verbose version of code.
> 3 votes

# Answer
# JavaScript, ~~167~~ ~~165~~ 164 bytes

Been a long, long time since I tried golfing anything this complex in JS. So much so that I made a complete *mess* of things in my initial solution! This version seems to work properly, although it's pretty hideous.

---

Takes the player data as a 2D-array. Call with `f(rounds)(players)`. Mutates the original input array. Remove the `&&--n` to ignore the rounds and allow the game to play through to the last player standing.

```
(n,p=o=0)=>g=a=>a.map(x=>x.o||(p||a.map(x=>x[1]?--x[++p,1]:x.o||=++o),x.o||(r=[0,p,p+1>>1,-1][Math.random()*4|0],r+1||x[1]?x[p-=r,1]+=r:x.o=++o),x))[o+1]&&--n&&g(a)

```

Attempt This Online!

Saved 2 bytes thanks to l4m2

## Explanation

```
(n,                           // Take the number of rounds as n
p=o=0)=>                      // Initialise p (the pot) and o (players out of the game) as 0
g=a=>                         // Named function taking the array of players as a
a.map(x=>                     // Map each x in a
  x.o||(                      // Return property o of x (initially undefined) OR
    p||a.map(x=>              // If p is 0 then map each x in a
      x[1]?                   // If the 2nd element (coins) of x is not 0
       --x[++p,1]             // Decrement it and increment p
       :x.o||=++o             // Else get the OR of x.o and o incremented, eliminating the current player
    ),x.o||(                  // Return x.o OR
      r=                      // Assign to r
        [0,p,p+1>>1,-1]       // Array of all possible results
        [Math.random()*4|0],  // Get a random element
      r+1||x[1]?              // If r is not -1 or the player has coins
       x[p-=r,1]+=r           // Increment their coins by r and decrement p by r
       :x.o=++o               // Else increment o and assign it to x.o, eliminating the current player
    )                         //
  ,x)                         // Return x
)[o+1]                        // If there are at least 2 players left in the game
&&--n                         // And we have rounds left to play
&&g(a)                        // Then call g again

```
> 3 votes

# Answer
# C `-m32`, ~~233~~ 220 bytes + 4 bytes = 224 bytes

-9 bytes thanks to ceilingcat

(linebreaks for "readability")

```
m;k;i;j;l;f(p,r)int*p;{
for(l=wcslen(p);k<l;k+=2)p[k]--;
for(srand(p);r--;m=l/2)
for(i=0;i<l;k=rand(i+=2)%4)
if(~p[i])if(k?k<2?p[i]+=m,m=0:k<3?p[i]+=j=m-m/2,m-=j:++m,p[i]--:0,!m)
for(j=0;j<l;j+=2)p[j]>0?p[j]--,m++:(p[j]=-1);}

```

Try it online!

This is basically a port of The Thonnu's python answer.

The input is an `int[]` of the form `{5, "Abraham", 5, "Batya", 5, "Claire", 0};`, which is why the loops count by 2. This array will be modified by the function. We can get the length of that with `wcslen`.

Ungolfed old version:

```
f(int *ptr, int rounds) {
    int length = wcslen(ptr);
    int money = length / 2; // one for each player
    srand(ptr);
    for (int i = 0; i < length; i += 2) ptr[i]--; // Decrement each by one
    for (; rounds--; ) {
        for (int i = 0; i < length; i += 2) {
            int k = rand() % 4;
            int half_pot = money / 2 + money % 2;
            if (ptr[i] >= 0) {
                k ?
                    k < 2 ? ptr[i] += money, money = 0 :
                    k < 3 ? ptr[i] += half_pot, money -= half_pot
                    : ++money, ptr[i]--
                : 0;
                if (!money) {
                    for (int j = 0; j < length; j += 2) {
                        if (ptr[j] > 0) {
                            ptr[j]--;
                            money++;
                        } else {
                            ptr[j] = -1;
                        }
                    }
                }
            }
        }
    }
}

```
> 1 votes

---
Tags: code-golf, random, game
---


# Question
Title: CGAC2022 Day 18: Light all of the candles
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

It's Hanukkah! Unfortunately, it appears some of the candles in your menorah have been blown out. You've got a lighter on hand, but it doesn't work quite right. Whenever you use your lighter at position k, the candles at positions k-1, k, and k+1 all toggle. Let's see an example. We'll represent our candles as a binary sequence with 1 being the "lit" state.

```
[1, 1, 1, 1, 0, 1, 1, 1, 1]  initial
[1, 1, 1, 0, 1, 0, 1, 1, 1]  light 4
[1, 1, 0, 1, 0, 0, 1, 1, 1]  light 3
[0, 0, 1, 1, 0, 0, 1, 1, 1]  light 1
[1, 1, 1, 1, 0, 0, 1, 1, 1]  light 0
[1, 1, 1, 1, 1, 1, 0, 1, 1]  light 5
[1, 1, 1, 1, 1, 1, 1, 0, 0]  light 7
[1, 1, 1, 1, 1, 1, 1, 1, 1]  light 8

```

## The challenge

To cover our candelabra bases, we'll be working with any n\>0 candles. Given the initial state of the candles as input, you must output a lighter usage sequence which will result in all of the candles being lit. Input and output can be taken in any reasonable form for a sequence. Output can be 0 or 1 indexed, but all numbers must fall within the range of the length (ie. no using the lighter at -1). You may assume that the input is always solvable, and you need only output one valid solution.

## Test cases

These examples are zero indexed.

```
[1, 1, 1, 1, 0, 1, 1, 1, 1] -> [4, 3, 1, 0, 5, 7, 8]
[0, 1, 1, 1, 1, 1, 1, 1, 1] -> [1, 2, 4, 5, 7, 8]
[1, 0, 1, 1, 1, 1, 1, 1, 1] -> [0, 1, 2, 4, 5, 7, 8]
[0, 0, 0, 0, 0, 0, 0, 0, 0] -> [1, 4, 7]
[1, 1, 1, 1, 1, 1, 1, 1, 1] -> []
[1, 1, 1, 0, 1, 1, 1] -> [0, 1, 3, 5, 6]
[0, 1, 1, 1, 1, 1, 1] -> [0, 2, 3, 5, 6]
[1, 1, 1, 1, 1, 1, 1] -> []
[0, 0] -> [0]
[0] -> [0]
[1] -> []

```

# Answer
> 9 votes
# Jelly, 19 or 18 bytes

```
’1;Ø1ị^ḊƲƬṖḢ€ṪỊ‘&ƲT

```

Try it online! (note: this solution produces 1-based output but the footer which tries all test cases converts the output format to 0-based to make it easier to compare to the given examples)

This works as either a function or full program. Input is taken from a function argument or command-line argument as an array of 0 (unlit) / 1 (lit). Output is an array of the 1-based indexes of the candles that should be lit, and the order will be a suitable order in which you could light them.

The `T` at the end is what specifies the output format as the indexes of all the candles that should be lit. If you remove it, you instead get an array which specifies, for each candle, whether to light it or not (via the truthiness or falsiness of the element), although the truthy values could be either 1 or 2. I'm not sure whether that's a valid output format; if it is, that saves a byte.

## Algorithm

Most of the other answers here are brute-forcing, and the others are solving equations in order to solve the problem semi-efficiently. However, it's actually possible to solve the problem in linear time using an algorithm customised for the problem, and the linear-time algorithm comes out shorter than all the other answers so far.

The first observation is that the order in which the candles are lit doesn't matter; additionally, lighting the same candle twice cancels itself out. So all that we need to do is to identify the set of candles that need to be lit, and we can assume without loss of generality that the candles are lit from left to right.

Now imagine an algorithm that moves from candle to candle, from left to right, deciding whether or not to light each candle as it goes. If it's currently at the second candle or later, there actually isn't a decision to be made here; if the candle to the left of the current candle is unlit, it'd better light the current candle, because otherwise there's no way the candle to the left will ever be lit; and if the candle to the left of the current candle is lit, it can't light the current candle because then the candle to the left would be permanently extinguished.

This means that the only decision that has to be made is whether or not to light the first candle; after that all decisions are forced. In turn, that means that it's possible to "brute-force" the solution by only checking two possibilities, with the first candle lit and with the first candle unlit. As it happens, if the number of candles is equal to 2 modulo 3, either both of these possibilities will work or neither will; if the number of candles is unequal to 2 modulo 3, exactly one will work.

My conversion of this algorithm to Jelly works by storing the row of candles as integers for which only the bottom two bits are relevant; the 1s bit specifies the current state of the candle in the scenario where the first candle was lit, and the 2s bit specifies the current state of the candle in the scenario where the first candle wasn't lit. Using XOR operations to do the toggles means that we're processing both of the scenarios in parallel, by focusing on different bits – in other words, this is SIMD Jelly that actually vectorises on the processsor! All that then needs to be implemented is to simulate the two possible starting states in parallel, then see which of them worked. (Because the challenge says "You may assume that the input is always solvable, and you need only output one valid solution.", this solution picks one of the two scenarios arbitrarily if both of them work or if neither of them work; the latter situation shouldn't occur and the former situation allows either solution.)

One thing that makes the answer a little more confusing: because only the bottom two bits of the integers matter, the obvious choice would be to use 0, 1, 2, 3, but I actually used -2, -1, 0, 1 because it was slightly golfier. Additionally, a bit being clear means that the candle is *lit*, and a bit being set means that the candle is *unlit*, the other way round from the intuitive meaning; again, this was just because it was slightly golfier. Thus, 0 means that a candle is lit in both scenarios; -1 means that a candle is unlit in both scenarios; 1 means that the candle is lit if and only if the first candle was left unlit; -2 means that the candle is lit if and only if the first candle was lit.

## Explanation

```
’1;Ø1ị^ḊƲƬṖḢ€ṪỊ‘&ƲT
’                      decrement each:
                         maps a    lit candle (1) to 0
                         maps an unlit candle (0) to -1
 1;                    prepend 1; this inserts a "zeroth candle" that
                         determines whether to light the first candle
         Ƭ             loop until a previously seen output is observed:
        Ʋ                (the loop body contains four commands)
     ị                   take the following elements from {the loop variable}:
   Ø1                      the first element, and the first element again
      ^                  bitwise XOR {corresponding elements of that list} with
       Ḋ                   {the loop variable} minus its first element
          Ṗ            take all but the last element of
                         {the history of the loop variable's values}
            €          replace each element of {that curtailed history}
           Ḣ             with its first element
                       {this is the value Ʋ refers to later}
             Ṫ         take its last element
              Ị        0 if {the last element} is <-1 or >1, 1 otherwise
               ‘       increment this
                &      bitwise AND with
                 Ʋ       the value as of four commands ago
                         {except its last element, due to Ṫ}
                  T    take the 1-based indexes of all truthy elements

```

The main loop that simulates the behaviour of all the candles is `Ø1ị^ḊƲƬ` (here, `Ƭ` specifies that there is a loop and what type of loop it is, `Ʋ` is what specifies how many commands to loop over, and the rest of it is the loop body). The idea is that the loop variable stores the current state of all the relevant candles (i.e. the candle that we're considering whether to light, plus one candle to its left and all candles to its right); the first element of the loop variable determines whether the first three candles should have their lighting status toggled (i.e. the second candle is lit), but because the first element will become irrelevant after this point, the required functionality is to delete the first element of the array and XOR it with the second and third (which can be expressed tersely in Jelly by forming a list of two copies of the first element, and XORing corresponding elements with the tail of the loop variable – elements beyond the first two remain untouched).

Things get a bit weird at the end of the loop, but this solution just allows the weirdness to happen and fixes it up later. This sort of loop iterates until it sees an output it's previously seen. The last iteration that actually represents candles is the iteration where the algorithm is considering whether to light the last candle; at this point, the array is two elements long, consisting of the states of the penultimate and last candles (let's call these *x* and *y*, so the array is `[*x*, *y*]`). For a possibility to be valid, *x* and *y* must be in the same state as each other at this point, either both lit or both unlit (otherwise, either the first candle was wrong or the problem is unsolvable). The next loop iteration should conceptually be on a 1-element list, but the algorithm always toggles two elements of the list, so the loop variable will now be `[*x*^*y*, *x*]`. Continuing to calculate, on the iteration after that, the loop variable will be `[*y*, *x*^*y*]`, and on the iteration after that, it will be `[*x*, *y*]`, i.e. a repeat. So the loop must end after at most three 2-element loop variables.

As it happens, these last three variables must always be distinct from each other. To prove this, consider the two scenarios (first candle lit, and first candle unlit), and consider which candles have differing actions in both scenarios (i.e. candles on which the algorithm uses the lighter in one scenario, but not in the other). It's fairly easy to see that the positions of these differing candles follow a regular repeating pattern (of two differing candles followed by one non-differing candle), regardless of which candles were initially lit; this implies that on any three consecutive iterations of the loop, their internal states must be different from each other (otherwise, the information needed to maintain this regular repeating pattern would be lost).

This in turn means that the history of loop iterations will contain the useful iterations that specify the history of what happened to the candles, plus two more: `[*x*^*y*, *x*]` and `[*y*, *x*^*y*]`. The latter is useless, and gets discarded by . However, the former starts with the value `*x*^*y*`, which is useful because a scenario is valid if and only if *x* and *y* are equal in that scenario. The value of `*x*^*y*` therefore specifies which scenarios are valid: 0 means that they're both valid, 1 means that only the scenario where the first candle was unlit is valid, -2 means that only the scenario where the first candle was lit is valid, and -1 means that they are both invalid. This value is then used to select a scenario: I chose the first-candle-lit scenario only when the value is -2, and the first-candle-unlit scenario otherwise, because this makes it possible to map the `*x*^*y*` value onto an integer with the relevant bit set in only two commands ( that checks whether the value is in the range `-1..1` inclusive, and an increment).

Once the algorithm has chosen a scenario, it then needs to work out which candles were lit in that scenario; this can be done simply by looking at the first element of the loop variable as of each loop iteration (which is why `µ` was used to save the history of the loop), and using a bitwise AND to extract the relevant bit.

The loop iteration history is therefore being used for two different purposes, but both of them only care about the first element of the loop variable. This makes it possible to rewrite the history to remove all but the first element of each element, which saves a byte later because it means that the "keep only the first element" command  doesn't need to be written twice.

Thanks to @Jonathan Allan for saving a byte – normally I use `µ` to mark values that need to be reused later in the code, but `Ʋ` also works in this context. Although this doesn't save any bytes directly, its positioning to the right of the `&` means that it separates the `&` from the `T`, preventing them accidentally (and incorrectly) parsing as a group, thus meaning that no extra bytes need be wasted to make the `T` parse correctly.

# Answer
> 7 votes
# PARI/GP, 54 bytes

```
a->matsolvemod(matrix(#a,,i,j,(i-j)^2<2),2,[!t|t<-a]~)

```

Attempt This Online!

Returns a binary array of which candle get lighted.

---

# PARI/GP, 72 bytes

```
a->k=0;[k|t<-a,matsolvemod(matrix(#a,,i,j,(i-j)^2<2),2,[!t|t<-a]~)[k++]]

```

Attempt This Online!

\\$1\\$-indexed.

This is solving linear equations \\$AX=B\\$ over the field \\$\mathbb{F}\_2\\$. The vector \\$B\\$ is the element-wise negation of out input. The matrix is \\$A = (a\_{ij})\\$, where \\$a\_{ij} = 1\\$ whenever \\$|i-j|\<2\\$, and \\$0\\$ otherwise. After that we just take the indices of \\$1\\$'s in the solution \\$X\\$.

The matrix \\$A\\$ is singular when the length of the input satisfies \\$n\equiv2\pmod 3\\$. So I have to use the built-in `matsolvemod` instead of simply multiplying the inverse matrix.

# Answer
> 5 votes
# Python NumPy, 71 bytes

```
lambda N:where(~N*mat(tril(triu(N==N,-1),1)).I%2)[1]
from numpy import*

```

Attempt This Online!

Port of @alephalpha's PARI/GP answer (but 0-indexed).

# Answer
> 5 votes
# 05AB1E, 22 bytes

```
TS¹gã.ΔÐ¦0ª^s0š^^P}∞sÏ

```

Try it online!

\\$O(n2^n)\\$ brute force.

-1 byte: append only one 0

```
TS¹gã.ΔÐ¦0ª^s0š^^P}∞sÏ
TS                      # digits of 10 (pushes ["1", "0"])
  ¹g                    # length of input
    ã                   # cartesian power
     .Δ            }    # first where the following is true:
       Ð                #   triplicate
        ¦               #   tail
         0ª             #   append 0
           ^            #   xor
            s           #   swap
             0š         #   prepend 0
               ^        #   xor
                ^       #   xor with implicit input
                 P      #   product
                   ∞sÏ  # truthy indicies

```

# 05AB1E, 33 bytes

```
¦1ª^ΔDNo3*.$0Þ«^}ćiR5bÞ^R1ë0}ª∞sÏ

```

Try it online!

\\$O(n log(n))\\$. Uses the same idea as alephalpha's answer but it implements the algorithm for solving \\$A{\bf x} = {\bf b}\\$. Unfortunately it's longer than just brute force.

```
¦1ª^ΔDNo3*.$0Þ«^}

```

transforms \\${\bf b}\\$ into \\${\bf d}\\$ such that \\$ A{\bf x} = {\bf b} \Leftrightarrow C{\bf x} = {\bf d} \\$ where \\$C = (c\_{ij})\\$, \\$c\_{ij}=1\\$ if \\$i=j+1\\$ or \\$j=n\\$ and \\$n-i\not\equiv 1\pmod{3}\\$ and \\$c\_{ij}=0\\$ otherwise. This is a matrix where all numbers just below the diagonal are 1 and the last column from bottom up is 1, 0, 1, 1, 0, 1 ...

```
ćiR5bÞ^R1ë0}ª

```

uses substitution to finally solve the equation.

# Answer
> 4 votes
# Charcoal, 29 bytes

```
ＩΦＥＸ²Ｌθ⌕Ａ⮌⍘ι²1⬤θ﹪⁺λΣＥ³№ι⊖⁺μν²

```

Try it online! Link is to verbose version of code. Outputs all solutions (e.g. `[1, 1, 0, 1, 1] -> [0, 1] or [3, 4]`; solutions are double-spaced from each other). Explanation: Generates all `2ⁿ` sets of lighter usage and filters out those that don't result in the desired candle state.

```
    ²                           Literal integer `2`
   Ｘ                            Raised to power
      θ                         Input array
     Ｌ                          Length
  Ｅ                             Map over implicit range
           ι                    Current value
          ⍘                     Converted to base
            ²                   Literal integer `2`
         ⮌                      Reversed
       ⌕Ａ                      Find all occurrences of
             1                  Literal string `1`
 Φ                             Filter sets where
               θ                Input array
              ⬤                 All elements satisfy
                     ³          Literal integer `3`
                    Ｅ           Map over implicit range
                      №         Count of
                          μ     Inner index
                         ⁺      Plus
                           ν    Innermost value
                        ⊖       Decremented
                       ι        In current set
                   Σ            Take the sum
                 ⁺              Plus
                  λ             Inner value
                ﹪           ²   Is odd
Ｉ                              Cast to string
                               Implicitly print

```

# Answer
> 3 votes
# Pip, ~~75~~ 66 bytes

```
@({$+($BX((^1X3WR0Xk)@(k-_+1,2*k-_+1)Ma)BX\a)=k}FI,(k:#a)CB_MF\,k)

```

Try It Online!

-9 bytes thanks to @DLosc

0 indexed. Verify all test cases here (it's slow)

# Answer
> 3 votes
# JavaScript (V8), 86 bytes

```
f=(x,e=[],i=0)=>1+x[j=i]?f(x.map(v=>j*j--<2^v),[...e,i],++i)||f(x,e,i):/0/.test(x)?0:e

```

Try it online!

-1 from Arnauld

# Answer
> 3 votes
# JavaScript (ES6), 48 bytes

*This is based on ais523's insight*
*-3 thanks to @l4m2*

Returns an array of binary values telling which candles were lit.

```
f=(a,p,b=a.map(q=v=>q^=(p^=v^!q)^v))=>p?b:f(a,1)

```

Try it online! (raw output)

Try it online! (with postprocessing to print a list of indices)

### Commented

```
f = (            // f is a recursive function taking:
  a,             //   a[] = input array
  p,             //   p   = value of the previous candle,
                 //         initially set to either undefined or 1
  b =            //   b[] = output array, built as follows:
    a.map(q =    //     initialize q to a zero'ish value
    v =>         //     for each value v in a[]:
      q ^= (     //       the value of the current candle is v XOR q
        p ^=     //       the value of the previous candle is p
          v ^ !q //       if p is not set, we toggle the current
                 //       candle, implicitly toggle the previous one
      ) ^ v      //       and set q = 1 to toggle the next one
    )            //     end of map()
) =>             //
  p ?            // if the last candle is lit:
    b            //   success: return b[]
  :              // else:
    f(a, 1)      //   try again with p initially set to 1

```

# Answer
> 1 votes
# Python3, 214 bytes:

```
def f(m):
 q,s=[(m,[])],[m]
 while q:
  m,M=q.pop(0)
  if all(m):return M
  for i in range(len(m)):
   U=[*m]
   for j in[-1,0,1]:
    if 0<=i+j<len(m):
     U[i+j]=not U[i+j]
   if U not in s:q+=[(U,M+[i])];s+=[U]

```

Try it online!

# Answer
> 0 votes
# Python, 133 bytes

```
lambda t:max((w:=[j,*(u:=t+[0,0])[:2]])and[i for i in range(len(u)-2)if(w:=[w[1]^(s:=w[0]^1),w[2]^s,u[i+2]])and s]*w[0]for j in[0,1])

```

Attempt This Online!

An alternative Python answer based on @ais523's insight. Not a competitive method compared to @loopywalt's numpy answer, but I thought it was interesting enough to warrant posting.

Interstingly, a recursive solution was the same length, but as it required the inclusion of `f=` in the byte count, it was technically longer.

---
Tags: code-golf
---


title: Multiply or Divide by n

text:
# Question
Title: Multiply or Divide by n
Here's a simple challenge, so hopefully lots of languages will be able to participate.

Given a positive integer \\$n\\$, output \\$A076039(n)\\$ from the OEIS.

That is, start with \\$a(1)=1\\$. Then for \\$n\>1\\$:

$$a(n)=\left\\{ \begin{array}{ll} n\cdot a(n-1), & \text{if } n\>a(n-1) \\ \lfloor a(n-1)/n \rfloor, & \text{otherwise.}\end{array} \\ \right. $$

### Test cases:

```
1 -> 1
2 -> 2 (2 > 1, so multiply)
3 -> 6 (3 > 2, so multiply)
4 -> 1 (4 < 6, so divide and take the integer part)
5 -> 5
6 -> 30
17 -> 221
99 -> 12
314 -> 26

```

More test cases can be found on the OEIS page.

Per usual rules, you can input and output in a generally accepted manner: 1- or 0-based indexing, output an infinite sequence, output the first \\$n\\$ values, output only the \\$n^\text{th}\\$ value, and so forth, but specify that in your answer.

This is , so shortest code in bytes in each language wins!

# Answer
# Jelly, 6 bytes

```
R×:<?/

```

A monadic Link accepting a positive integer, \\$n\\$, which yields a positive integer, \\$a(n)\\$.

**Try it online!** Or see the test-suite.

### How?

```
R×:<?/ - Link:
R      - range -> [1..n]
     / - reduce by (i.e. evaluate f(f(...f(f(f(1,2),3),4),...),n) with this f(a,b):
    ?  -   if...
   <   -   ...condition: (a) less than (b)?
 ×     -   ...then: multiply -> a×b
  :    -   ...else: integer divide -> a//b

```

---

Output the sequence up to \\$a(n)\\$ with:

```
R×:<?\

```
> 18 votes

# Answer
# Scratch 3.0, ~~29~~ 27 blocks/~~234~~ 167 bytes

As SB Syntax:

```
define f(n)
if<(n)=(1)>then
add(1)to[v v
else
f((n)-(1
set[d v]to(item(length of[v v])of[v v
if<(n)>(d)>then
add((n)*(d))to[v v
else
add([floor v] of ((n)/(d)))to[v v]
end
end
when gf clicked
delete all of [v v
ask()and wait
f(answer)

```

Try it on scratch

I'm a little unsure of some input/output methods, so I thought I'd be safe and just make it a full program with a helper function.

Answering this allowed my account to be promoted from "new" to "standard", so that's always fun.

*-67 bytes thanks to @att*
> 15 votes

# Answer
# Shakespeare Programming Language, 221 bytes

```
,.Ajax,.Puck,.
Act I:.Scene I:.[Enter Ajax and Puck]
Ajax:You cat.
Scene V:.
Puck:You is the sum ofYou a cat.
Ajax:Open heart.Is I nicer you?If notYou is the quotient betweenyou I.
      If soYou is the product ofyou I.Let usScene V.

```

Try it online!

Outputs the infinite list. Note however that there is no separator between the output values, so the output is somewhat difficult to read.

My best attempt at adding a separator (a null byte) comes down as

# Shakespeare Programming Language, 297 bytes

```
,.Ajax,.Puck,.Page,.
Act I:.Scene I:.
[Enter Ajax and Puck]
Ajax:You cat.
Scene V:.[Exit Puck][Enter Page]
Ajax:Speak thy.
Page:You is the sum ofYou a cat.
Scene X:.[Exit Page][Enter Puck]
Ajax:Open heart.Is I nicer you?If notYou is the quotient betweenyou I.
      If soYou is the product ofyou I.Let usScene V.

```

Try it online!
> 14 votes

# Answer
# Python 2, ~~47~~ ~~43~~ 39 bytes

Saved 4 bytes thanks to xnor!!!
Saved 4 bytes thanks to Neil!!!

```
r=i=1
while 1:r=r/i or r*i;print r;i+=1

```

Try it online!

Prints \\$\\{a(n)\mid n \in \mathbb{N}\\}\\$ as an infinite sequence.
> 12 votes

# Answer
# , ~~43~~ 39 bytes

-4 bytes thanks to Giuseppe.

```
for(i in 1:scan())T=T%/%i^(2*(i<T)-1);T

```

Try it online!

Outputs the \\$n\\$th term, 1-indexed.

Initializing the sequence with \\$a(0)=1\\$ also works, as the formula then gives \\$a(1)=1\\$ as desired. The variable `T` is coerced to the integer `1`, and we apply repeatedly a more compact version of the formula:

$$a(n)=\left\lfloor \frac{a(n-1)}{n^{2\mathbb{I\_{n\<a(n-1)}} -1}}\right\rfloor $$

(with \\$\mathbb I\\$ the indicator function). This covers both cases of the original definition.
> 11 votes

# Answer
# Haskell, 40 bytes

```
a#n|n>a=a*n|1>0=a`div`n
a=scanl1(#)[1..]

```

Try it online!

* Outputs infinite sequence.

Infix operator # computes next term, we use it to fold all positive integers \[1..\] but using scanl1 instead which gives us all steps.
> 10 votes

# Answer
# APL (Dyalog Unicode), 18 bytes (SBCS)

```
{⍺>⍵:⍺×⍵⋄⌊⍵÷⍺}/⌽ö⍳

```

Try it online!

A barely-golfed but safe function that outputs the nth element of the sequence.

---

# APL (Dyalog Unicode), ~~15~~ 14 bytes (SBCS)

*Saved 1 byte thanks to @Adám*

```
(⌊⊢×⊣*∘×-)/⌽ö⍳

```

Try it online!

Outputs the nth element of the sequence. I just realized that this won't work if \\$n = a(n-1)\\$ because it raises n to the power of \\$n - a(n-1)\\$ and multiplies that by \\$a\\$, although as far as I can tell, this function works until at least n=2,000,000.

```
(⌊⊢×⊣*∘×-)/⌽ö⍳
              ⍳  ⍝ Make a range to n
           ⌽ö   ⍝ Then reverse it and
(⌊⊢×⊣*∘×-)/      ⍝ reduce it with a train:
   ×             ⍝ Multiply
  ⊢             ⍝ a(n-1) with
    ⊣           ⍝ n
     *∘×        ⍝ to the power of the sign of
        -       ⍝ n - a(n-1)
⌊                ⍝ Floor it

```
> 8 votes

# Answer
# Python 3.8+,  ~~45~~  39 bytes

-2 thanks to xnor (`while print(...)!=0:``while[print(...)]:`)
-4 thanks to Neil (`[a*n,a//n][a>n]``a//n or a*n`)

```
a=n=1
while[print(a:=a//n or a*n)]:n+=1

```

A full program which prints \\$a(n)\\$ for all natural numbers.

**Try it online!**

---

As a recursive function, 49:

```
f=lambda v,n=1,a=1:a*(v<n)or f(v,n+1,a//n or a*n)

```
> 8 votes

# Answer
# Forth (gforth), 82 bytes

```
: f 2dup 2dup > if * else swap / then dup . swap drop swap 1+ swap recurse ;
1 1 f

```

Try it online!

Outputs an infinite sequence, separated by spaces.
> 8 votes

# Answer
# Perl 5 `-Minteger` `-061`, ~~36~~, 27 bytes

-9 bytes thanks to @Abigail and @Sisyphus.

outputs an infinite sequence

```
say$/while$/=$//++$i||$/*$i

```

Try it online!
> 7 votes

# Answer
# , 41 bytes

```
for(m in 1:scan())T=`if`(m>T,T*m,T%/%m);T

```

Try it online!

Forced myself not to look at Robin Ryder's R answer before having a go at this. Happily we came up with different approaches to each other, although ~~both seem (so far) to be exactly the same length in bytes~~ sadly for me his one is now 2 bytes shorter...
> 7 votes

# Answer
# C (gcc), 35 bytes

Takes a 1-based starting index and returns the nth sequence value.

```
f(i,j){i=i?i>(j=f(i-1))?j*i:j/i:1;}

```

Try it online!
> 7 votes

# Answer
# JavaScript (Node.js),  ~~38~~  35 bytes

*Saved 3 bytes thanks to @Neil*

Returns the \\$n\\$-th term, 1-indexed.

```
f=(n,k=i=1n)=>i++<n?f(n,k/i||k*i):k

```

Try it online!
> 6 votes

# Answer
# K (oK), ~~22~~ 20 bytes

```
{_x*(1%y;y)y>x}/1+!:

```

Try it online!

Rather than using `$[y>x;y;1%y]`, indexes into the list `(1%y;y)` using the boolean condition `y>x` to save a couple bytes.
> 6 votes

# Answer
# Factor, 45 bytes

```
[ [1,b] 1 [ 2dup < [ * ] [ /i ] if ] reduce ]

```

Try it online!

Straightforward reduction. Takes 1-based index and returns the n-th term.

```
[                         ! anonymous lambda
  [1,b] 1 [ ... ] reduce  ! reduce {1..n} by the following, starting with 1:
    2dup <                !   ( an n -- an n an<n)
    [ * ] [ /i ] if       !   ( a_n+1 ) multiply if an < n, int-divide otherwise
]

```
> 6 votes

# Answer
# Husk, 11 bytes

```
Fμ?*`÷<¹³)ḣ

```

Try it online!

```
F               # Fold a function over
          ḣ     # sequence from 1..input;
 μ?*`÷<¹³)      # function with 2 arguments:
  ?             # if
      <¹³       # arg 2 is smaller than arg 1
   *            # arg 1 times arg 2
    `÷          # else arg 1 integer divided by arg 2

```
> 5 votes

# Answer
# Perl 5 `-Minteger -p`, 35 bytes

```
map$.=$_>$.?$.*$_:$./$_,2..$_;$_=$.

```

Try it online!

Takes `n` as input and prints the `n`<sup>`th`</sup> item in the list.
> 5 votes

# Answer
# 05AB1E, ~~12~~ 10 bytes

Prints the infinite sequence.

```
λN>₁N›i÷ë*

```

Try it online!

**Commented**:

```
λ              # infinite list generation
               # implicitly push a(n-1) (initially 1)
 N>            # push n, since N is 0-indexed, this needs to be incremented
   ₁N›         # is a(n-1) > n-1?
      i÷       # if this is true, integer divide a(n-1) by n
        ë*     # else multiply a(n-1) and n

```
> 5 votes

# Answer
# Forth (gforth), 51 bytes

```
: f 1+ 1 tuck ?do i 2dup <= if * else / then loop ;

```

Try it online!

### Code Explanation

```
: f        \ start word definition
  1+       \ add 1 to n
  1 tuck   \ set up accumulator and loop parameters
  ?do      \ loop from 1 to n (if n > 1)
    i 2dup \ set up top two stack values and duplicate
    <= if  \ if a(n-1) <= n
      *    \ multiply
    else   \ otherwise
      /    \ divide
    then   \ end if
  loop     \ end loop
;          \ end word definition

```
> 5 votes

# Answer
# Java (JDK), 52 bytes

```
n->{int i,a=i=1;for(;i++<n;)a=i>a?i*a:a/i;return a;}

```

Try it online!

Note: Thanks @RedwolfPrograms for -1 Byte and @user for -10(?) bytes.
> 5 votes

# Answer
# Jelly, 11 bytes

```
1’ß×:>@?$Ị?

```

Try it online!

## How it works

```
1’ß×:>@?$Ị? - Main link f(n). Takes n on the left
          ? - If statement:
         Ị  -   If: n ≤ 1
1           -   Then: Yield 1
        $   -   Else:
 ’          -     n-1
  ß         -     f(n-1)
       ?    -     If statement:
     >@     -       If: n > f(n-1)
   ×        -       Then: n × f(n-1)
    :       -       Else: n : f(n-1)

```
> 4 votes

# Answer
# Brachylog, 10 bytes

```
⟦₁{÷ℕ₁|×}ˡ

```

Try it online!

Gives the singleton list `[1]` instead of `1` for n = 1, but nothing out of the ordinary otherwise.

```
         ˡ    Reduce
⟦₁            1 .. n
  {     }     by:
   ÷          integer division
    ℕ₁        if the result is 1 or greater,
      |×      multiplication if not.

```
> 4 votes

# Answer
# Gaia, 9 bytes

```
┅⟪<₌×/?⟫⊢

```

Try it online!

Basically the same as the shorter Jelly answer. 1-indexed, prints `a(n)`, although  could be swapped with  to get the first `n` elements instead.

```
		# implicit input n
┅		# push 1...n
 ⟪      ⟫⊢	# reduce the list by the following function:
  <₌		# push an extra copy of a(i-1) and i and check if less than?
    × ?		# if true, then multiply
     /		# else integer divide
		# implicitly print top of stack

```
> 4 votes

# Answer
# Retina, 58 bytes

```
K`_ _
"$+"+L$`(^_+|_)(?<=(\1)+) (\1)+
_$`$1 $#3*$#2*
r`_\G

```

Try it online! No test suite because of the way the script uses history. Explanation:

```
K`_ _

```

Replace the input with a pair of 1s (in unary). The first is the loop index while the second is the output.

```
"$+"+

```

Loop `n` times.

```
L$`(^_+|_)(?<=(\1)+) (\1)+

```

Divide both the output and the loop index by the loop index, or by 1 if the division would be zero.

```
_$`$1 $#3*$#2*

```

Increment the loop index and multiply the two quotients together. This results in `output/index*index/index` or `output/1*index/1` respectively.

```
r`_\G

```

Convert the final output to decimal.
> 4 votes

# Answer
# PHP, 57 bytes

```
function a($n){return$n?($n>$x=a($n-1))?$x*$n:$x/$n|0:1;}

```

Try it online!
> 4 votes

# Answer
# cQuents, 14 bytes

```
=1:$>Z?$Z:Z_/$

```

Try it online!

## Explanation

```
=1             first term is 1
  :            mode sequence: given n, output nth term; otherwise, output indefinitely
               each term equals:

   $>Z?  :     if n > seq(n - 1)                else
       $Z                        n * seq(n - 1)
          Z_/$                                       seq(n - 1) // n

```
> 4 votes

# Answer
# Wolfram Language (Mathematica), 40 bytes

```
a@1=1;a@n_:=If[#<n,n#,⌊#/n⌋]&@a[n-1]

```

Try it online!

-2 bytes from @att
> 4 votes

# Answer
# Racket, 66 bytes

```
(λ(n)(foldl(λ(x y)((if(< y x)* quotient)y x))1(range 1(+ 1 n))))

```

Try it online!
> 4 votes

# Answer
# IBM/Lous Notes Formula Language, 92 bytes

```
i:=n:=1;o:=0;@While(i<=a;@Set("n";@If(i<n;@Integer(n/i);i*n));@Set("o";o:n);@Set("i";i+1));o

```

A bit lengthy and only posted to see if I can still remember how to use the language. ~~Outputs the first 98 numbers of the sequence and has a leading 0 (not sure if that matters - please comment if so)~~.

**Edit** Updated following feedback from @Giuseppe. Still the same byte count but now takes input from editable field `a` to define the length of the output. Theoretically the formula could calculate to infinity however Notes has a restriction of 64kb on what can be calculated in a field formula (see last screenshot).

There is no TIO for Formula so here are a couple of screenshot:
> 4 votes

# Answer
# , 21 bytes

```
[:(]<.@*[^*@-)/1+i.@-

```

Try it online!

A  port of @user 's APL solution \- don't forget to upvote it!
> 4 votes

# Answer
# MathGolf, ~~11~~ 9 bytes

```
1k{î`<¿*/

```

-2 bytes thanks to *@ovs*.

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

Try it online.

**Explanation:**

```
1         # Push 1
 k{       # Loop the input amount of times:
   î      #  Push the 1-based loop index
    `     #  Duplicate the top two items
     <¿   #  If the current value is smaller than the 1-based loop index: a(n-1)<n:
       *  #   Multiply the value by the 1-based loop index
          #  Else:
       /  #   Integer-divide instead
          # (after the loop, the entire stack joined together is output implicitly)

```
> 4 votes

# Answer
# Husk, 6 bytes

```
Ḟ§|*÷ṫ

```

**Try it online!**

### How?

```
Ḟ§|*÷ṫ - function: integer, n
     ṫ - reversed range -> [n,n-1,...,2,1]
Ḟ      - right-fold using this f(a,b):
 §     -   fork:
  |    -     v logical-OR w
    ÷  -     v: b integer-divide a
   *   -     w: a multiplied by b

```
> 4 votes

# Answer
# Scala, 41 bytes

```
2.to(_)./:(1){(a,n)=>if(n>a)n*a else a/n}

```

Try it online!
> 3 votes

# Answer
# C (gcc), 47 bytes

-1 thanks to ceilingcat.

Displays `x` first sequence elements.

```
p,n;a(x){for(y(n=++p);n++<x;y(p=n>p?p*n:p/n));}

```

Try it online!
> 3 votes

# Answer
# Hy, 54 bytes

```
(defn f[n](or(+(= n 1))(//(f(- n 1))n)(*(f(- n 1))n)))

```

Try it online!

This function outputs the nth value of the sequence.

Ungolfed version:

```
(defn f [n]
  (or (+ (= n 1))
      (// (f (- n 1))
          n)
      (* (f (- n 1))
         n)))

```
> 3 votes

# Answer
# convey, 47 bytes

Generates the sequence.

```
v0
+"
1">">v
 ).*vv
1"#"#%
"}">!`
^0=>#!
._<<,<

```

Try it online!

The top left generates 1, 2, … and copies `"` them into `).`, `*` and `%`. The accumulator on the middle left starts with `1` and is also copied into the operators.

We have then `i >= a`, `i * a` and `a % i`. Based on the conditional, either `i * a` or `i % a` gets picked by taking `!` it 0 or 1 times. For this we need to negate the boolean `0=` for `i * a` and need a lot of crossings `#` to navigate everything into the right place.

When looping to the start, the accumulator passes floor `_.`, and gets copied into the output `"}`, before going into the next round.
> 3 votes

# Answer
# Japt, 12 bytes

Outputs the `n`th term, 1-indexed.

```
È§Y©Y*XªzY}g

```

Try it or run all test cases

```
È§Y©Y*XªzY}g     :Implicit input of integer U
È                :Function taking an integer X & iteration counter Y as input
 §Y              :  X<=Y?
   ©             :  Logical AND with
    Y*X          :  Y*X
       ª         :  Logical OR with
        zY       :  X floor divided by Y
          }      :End function
           g     :Run that function U times, starting with X=1 & Y=2

```
> 2 votes

# Answer
# Perl 5, 51 bytes

```
sub a{my$n=pop;$n<=1?1:$n>($a=a($n-1))?$a*$n:$a/$n}

```

Try it online!

```
sub a {
  my $n=pop;                 # n = input
  $n <= 1           ? 1      # n = 1      → 1
 :$n > ($a=a($n-1)) ? $a*$n  # n > a(n-1) → a(n-1) · n
                    : $a/$n  # n ≤ a(n-1) → ⌊a(n-1) / n⌋ in 'use integer' mode
}

```
> 2 votes

# Answer
# Julia 1.0, 40 bytes

```
a(n)=n<1 ? 1 : n>(A=a(n-1)) ? A*n : A÷n

```

Try it online!
> 2 votes

# Answer
# Charcoal, 17 bytes

```
Ｆ…·²Ｎ≔∨∕ψι×ψιψＩＬψ

```

Try it online! Link is to verbose version of code. Explanation: The string `y` (`ψ`) is initialised to a single null byte.

```
Ｆ…·²Ｎ

```

Loop from `2` to `n`.

```
≔∨∕ψι×ψιψ

```

Try dividing the string into `i` pieces, but if that would result in the empty string, repeat the string `i` times intead.

```
ＩＬψ

```

Output the final length of the string.
> 2 votes

# Answer
# PHP, 41 bytes

```
<?for(;;)echo$x=!$x+$x/++$i|0?:$x*$i,'
';

```

Try it online!

Outputs the infinite sequence. A couple of PHP tricks in use, using `|0` to cast to int, and `!$x` to elegantly handle the first iteration.
> 2 votes

# Answer
# Stax, 9 bytes

```
ü↨╖Γ¥B╢╤┴

```

Run and debug it

The same reduce operation as the Jelly answer.
> 2 votes

# Answer
# Wolfram Language (Mathematica), ~~36~~ 33 bytes

```
Nest[⌊#/++n⌋/. 0->n#&,n=1,#]&

```

Try it online!

0-indexed.
> 2 votes

# Answer
# Pyth, 20 bytes

```
J1V}2hQJ=J?>NJ*NJ/JN

```

Try it online!

1-indexed, outputs the first n values.
> 2 votes

# Answer
# PowerShell Core, 65 bytes

Output the nth value:

```
$r=1
1..$args[0]|%{$r=([Math]::Floor($r/$_),($r*$_))[$_-gt$r]}
$r

```

## Explanations

```
$r=1                           # Initialises the result as 1
1..$args[0]|%{                 # For 1 to the argument
    $r=(                       # In an array calculate the two possible values
        [Math]::Floor($r/$_),  # Divide and floor
        ($r*$_)                # Multiply
    )[$_-gt$r]                 # The condition to decide what index to take
}                              # $true becomes 1 and $false 0
$r                             # Returns the result

```

Does anyone know how to make the `[Math]::Floor` shorter?

Try it online!
> 2 votes

# Answer
# MMIX, 132 bytes (17 instrs)

Given \\$n\\$, returns \\$A076039(n)\\$. Given \\$0\\$, returns \\$A076039(2^{64})\\$ (or, more accurately, runs until the machine breaks, but in theory it would return that).

```
C1010000 E3000001 E3FF0001 E3020000
4A020007 320300FF 44030005 1A0000FF
FE020003 F8000004 F6010002 E3020000
1E0000FF 23FFFF01 27010101 5B01FFF6
F8010000

```

Disassembly:

```
foo SET  $1,$0          // move n to $1
    SETL $0,1           // acc = 1
    SETL $255,1         // i = 1
    SETL $2,0           // top = 0 (comes in handy later)
0H  BNZ  $2,1F          // loop: if(top) goto divide
    CMPU $3,$0,$255
    BP   $3,1F          // if(acc > i) goto divide
    MULU $0,$0,$255     // rH:acc = acc * i
    GET  $2,rH          // top = rH
    JMP  2F             // goto cont
1H  PUT  rD,$2          // rD = top
    SETL $2,0           // top = 0
    DIVU $0,$0,$255     // divide: acc:rR = rD:acc /% i
2H  ADDU $255,$255,1    // i++
    SUBU $1,$1,1        // n--
    PBNZ $1,0B          // ifprob(n) goto loop
    POP  1,0            // return(acc)

```

Note that this returns an incorrect result if the correct result is at least \\$2^{64}\\$. However, the computation is otherwise carried out in terms of 128-bit arithmetic, with the accumulator stored as `$2:$0` (this would break down if two divisions were to occur in a row, but that can't happen).
> 2 votes

# Answer
# Vyxal, 9 bytes

```
ɾ‡<[*|ḭ]R

```

Try it Online!

Port of Jelly answer. That if statement takes up so much bytes tho...

## How?

```
ɾ‡<[*|ḭ]R
ɾ          # Inclusive one range of (implicit) input
        R  # Reduce by:
 ‡         # Next two elements as a lambda
  <        # Is a<b?
   [*      # If so, multiply: a*b
     |ḭ]   # Else, floor divide: a//b

```
> 2 votes

# Answer
# Nibbles, 5.5 bytes (11 nibbles)

```
=\,$?/@$$*@

```

Outputs the first n values.

```
=\              # scan from left across
  ,$            # 1..input
                # with function:
    ?           #   if
     /@$        #   right integer-divided by left
                #   is nonzero:
        $       #     return it
                #   otherwise:
         *@     #     return right multiplied by
                #     (implicitly) left

```
> 2 votes

# Answer
# Bash, 40 bytes

outputs an infinite sequence

```
for((r=1;;));{ echo $[r=++i>r?r*i:r/i];}

```

Try it online!
> 1 votes

# Answer
# Perl 5, 40 + 2 (`-pl` flag) = 42 bytes

```
$==1;map$==$_>$=?$=*$_:$=/$_,2..$_;$_=$=

```

Try it online!
> 1 votes

# Answer
# Crystal, 41 bytes (-2 bytes thanks to Giuseppe)

```
def a(n)n<2?1: n>(f=a(n-1))?n*f: f//n end

```

Try it online!
> 1 votes

# Answer
# SNOBOL4 (CSNOBOL4), 71 bytes

```
	Y =1
R	X =X + 1
	Y =Y * X GT(X,Y)	:S(O)
	Y =Y / X
O	OUTPUT =Y	:(R)
END

```

Try it online!

Prints the sequence forever.
> 1 votes

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


# Question
Title: CGAC2022 Day 20: Reconstruct Santa's Book
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

Oh no, Santa spilled wine all over his great book. Now most of the letters are illegible. How will Santa now know who is *groovy* and who is *unspeakable*?

## Challenge

There was once a sequence of words, like this:

```
groovy groovy groovy unspeakable groovy groovy unspeakable unspeakable

```

However, most of the letters have gone missing and now it looks like this:

```
    v    oo   g      unsp        gr   y gro            b   uns

```

Then squashed together:

```
voogunspgrygrobuns

```

Your task is to recover the *shortest sequence of words* that could reduce to the given damaged string.

Note: The words will never have any overlapping characters. Since the book uses different words in different languages you need to handle different words.

## Test Cases

| Word A | Word B | Sentence | Result |
| --- | --- | --- | --- |
| a | b | ab | a b |
| ab | cd | abcd | ab cd |
| ab | cd | abc | ab cd |
| ab | cd | ac | ab cd |
| ab | cd | bd | ab cd |
| ab | cd | bda | ab cd ab |
| ab | cd | aa | ab ab |
| ooq | dr | ooqdr | ooq dr |
| ooq | dr | oooqdr | ooq ooq dr |
| groovy | unspeakable | voogunspgrygrobuns | groovy groovy groovy unspeakable groovy groovy unspeakable unspeakable |

# Answer
> 5 votes
# 05AB1E, 14 bytes

```
‚[DNãvyJæ³åiyq

```

Try it online!

```
‚[DNãvyJæ³åiyq
‚              # pair
 [             # infinite loop
  D            # double
   N           # push current loop index
    ã          # cartesian power
     v         # for loop
      y        # push current element
       J       # join
        æ      # powerset
         ³å    # does it contain third input?
           iyq # if true, push current element and terminate

```

# Answer
> 4 votes
# Jelly, 16 bytes

I salvaged a previous blunder so this is now almost certainly beatable!

```
eⱮÐƤƤŒP€}SSÐṂḢ€ị

```

A dyadic Link that accepts the sentence on the left and the pair of words on the right and yields a list of words.

**Try it online!**

### How?

Effectively greedily consumes the longest prefix of the remaining sentence that is a substring of one of the words and then adds that word to the, initially empty, result. The actual implementation analyses every sublist of the sentence and identifies the ends of the words and which one each is and then constructs the result.

```
eⱮÐƤƤŒP€}SSÐṂḢ€ị - Link: Sentence, Words
        }        - using the right argument, Words:
       €         -   for each word:
     ŒP          -     powerset -> all substrings of the word
    Ƥ            - for prefixes of Sentence:
  ÐƤ             -   for suffixes of that prefix:
 Ɱ               -     map across the pair of word substring lists with:
e                -       exists in?
         S       - sum the columns -> list of pairs [n,0] or [0,n] where n is
                                      the distance to the next word boundary.
           ÐṂ    - keep those pairs with minimal:
          S      -   sum (i.e the [1,0] and [0,1] entries marking ends of words.)
             Ḣ€  - head each -> 1 if word 1, 0 if word 2
               ị - index (1-based and modular) into (Words)

```

# Answer
> 4 votes
# Python3, 119113 bytes:

```
lambda a,b,s:' '.join(a if x[0]in a else b for x in re.split(f"({'?'.join(a)}?|{'?'.join(b)}?)",s)if x);import re

```

Try it online

# Answer
> 3 votes
# Python3, 190 bytes:

```
Y=lambda a,b:a==''if''in[a,b]else Y(a[a[0]==b[0]:],b[1:])
f=lambda a,b,s,r=[]:r if''==s else f(a,b,s[(M:=max([x for x in range(1,len(s)+1)if Y(s[:x],a)+Y(s[:x],b)])):],r+[[a,b][Y(s[:M],b)]])

```

Try it online!

# Answer
> 3 votes
# Retina, 46 bytes

```
~(L$`¶(.+)
\G$1(?!\G)¶$1
(?<=G\w+)
?
^
L#-2$$`

```

Try it online! Takes the squashed word on the first line and the pair of words on the other two lines. Explanation: Very similar to the extended version below but the last stage hard-codes the number of words.

63 bytes for a version that decodes any number of words with non-overlapping letters:

```
~(L$`¶(.+)
\G$1(?!\G)¶$1
(?<=G\w+)
?
^(?=((!)|[^!])+)
L#-$#2$$`

```

Try it online! Takes the squashed word on the first line and original words on subsequent lines. Explanation:

```
~(

```

Evaluate the output of the rest of the program as a program on the original input.

```
L$`¶(.+)

```

For each original word...

```
\G$1(?!\G)¶$1

```

... construct an anchor to match after the previous word (easiest way to limit the matches to the first line), the word to be processed below, an anchor to not match after the previous word (to ensure at least one letter matched) and a copy of the word on its own line to act as a replacement.

```
(?<=G\w+)
?

```

Suffix `?`s to each letter in the word, making each letter match optionally (but greedily).

```
^(?=((])|[^]])+)
L#-$#2$$`

```

Prefix a List command with the multiple greedy match and replacement option.

In the given example, the resulting program looks like this:

```
L#-2$`\Gg?r?o?o?v?y?(?!\G)
groovy
\Gu?n?s?p?e?a?k?a?b?l?e?(?!\G)
unspeakable

```

Explanation:

```
L#-2$`

```

List matches of two regexes each with their own match result. (In this case only one of the regexes can match at a given point but the `#-` option normally allows Retina to choose which regex depending on which matches earlier in the string.)

```
\Gg?r?o?o?v?y?(?!\G)

```

Greedily match as much of the word `groovy` as possible, matching at least one character.

```
groovy

```

If this match succeeds then the resulting list item is the word `groovy`.

```
\Gu?n?s?p?e?a?k?a?b?l?e?(?!\G)
unspeakable

```

Similarly for the word `unspeakable`.

# Answer
> 3 votes
# JavaScript (Node.js), 83 bytes

```
s=>a=>(g=i=>(e=t=>r=t^1?a[t&1]+[,e(t/2)]:'')(i).match([...s].join`.*`)?r:g(i+1))(1)

```

Try it online!

As a compare with `find`

# Answer
> 3 votes
# JavaScript (Node.js), 77 bytes

```
a=>b=>g=(t,s='',...r)=>s.match([...t].join`.*`)?s:g(t,...r,(s&&=s+' ')+a,s+b)

```

Attempt This Online!

# Answer
> 3 votes
# Charcoal, 30 bytes

```
Ｆθ«Ｆ¬№ωι«≔⎇№ηιηζω⟦ω⟧»≔Φω›λ⌕ωιω

```

Try it online! Link is to verbose version of code. Takes the squashed sentence as the first input. Explanation:

```
Ｆθ«

```

Loop over the characters of the squashed sentence.

```
Ｆ¬№ωι«

```

If the current character isn't present in the current string (initially the empty string), then...

```
≔⎇№ηιηζω

```

... update the current string to the word that contains the current character, and...

```
⟦ω⟧

```

... output that word on its own line.

```
»≔Φω›λ⌕ωιω

```

Delete up to the first occurrence of the current character in the current word.

37 bytes for a version that decodes any number of words with non-overlapping letters:

```
ＳθＷＳ⊞υιＦθ«Ｆ¬№ωι«≔⊟Φυ№λιω⟦ω⟧»≔Φω›λ⌕ωιω

```

Try it online! Link is to verbose version of code. Takes the squashed sentence as the first input followed by a list of newline-terminated words.

# Answer
> 3 votes
# Pyth, 22 bytes

```
Kwm?-dzKzhf!-T+yzyK./w

```

Try it online!

Takes the two words as the first two inputs and the sentence as the third. Returns a list.

Brutally slow brute force method.

### Explanation

```
                          # z=input() implicitly
Kw                        # set K to the second input
                   ./w    # all partitions of the third input (given sorted by number of elements in the partition)
          f               # filter over lambda T
           !              # not (true for empty list)
            -T            # remove from T
              +yzyK       # sum of the power sets of the first two inputs
         h                # take the first element of the filtered list (this will be a valid partition with the least elements)
  m                       # map each element (d) to
   ?-dzKz                 # z if d consists of characters in z, K otherwise

```

# Answer
> 2 votes
# JavaScript (ES10), 86 bytes

Expects `(sentence)(word_list)`. Returns a comma-separated string of words.

```
s=>a=>(g=b=>b.find(w=>w.match([...s].join`.*`))||g(b.flatMap(p=>a.map(q=>p+[,q]))))(a)

```

Try it online!

# Answer
> 2 votes
# Excel (ms365), 241 bytes

Formula in `D1`:

```
=LET(x,SEQUENCE(LEN(C1)),y,SCAN(C1,x,LAMBDA(a,b,LET(z,MAP(x,LAMBDA(c,TEXTJOIN("*",,MID(a,SEQUENCE(c),1)))),SUBSTITUTE(a,TAKE(TOCOL(IF(SEARCH(z,A1:B1),LEFT(a,x),),2),-1),,1)))),TOCOL(IF(FIND(LEFT(VSTACK(C1,FILTER(y,y<>""))),A1:B1),A1:B1,),3))

```

# Answer
> 1 votes
# Pip, 41 bytes

```
Y@_NIag@yMFIc@(@>(aJW"?").`|`.@>(bJW"?"))

```

Try It Online!

Expects the first word, second word and sentence as inputs. Shamelessly stole the regex from @David's answer. Full test suite here (Thanks to @emanresuA for help with the test suite)

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