title: Find the longest rep digit

text:
# Question
Title: Find the longest rep digit
Your task is to take a positive number as input, **n**, and output the length of the longest rep-digit representation of **n** in any base. For example 7 can be represented as any of the following

```
111_2
21_3
13_4
12_5
11_6
10_7
7_8

```

The rep-digits are `111_2` and `11_6`, `111_2` is longer so our answer is 3.

This is a question so answers will be scored in bytes, with fewer bytes being better.

# Test Cases

```
1   -> 1
2   -> 1
3   -> 2
4   -> 2
5   -> 2
6   -> 2
7   -> 3
8   -> 2
9   -> 2
10  -> 2
11  -> 2
26 -> 3
63  -> 6
1023-> 10

```

# Sample implementation

Here is an implementation in Haskell that can be used to generate more test cases.

```
f 0 y=[]
f x y=f(div x y)y++[mod x y]
s x=all(==x!!0)x
g x=maximum$map(length.f x)$filter(s.f x)[2..x+1]

```

Try it online!

# Answer
# Jelly,  ~~9~~  7 bytes

-2 thanks to caird coinheringaahing (`‘Ḋ$` -\> `‘€` and use of the newer alias for `Ðf`, `Ƈ`.)

```
b‘€EƇZL

```

A monadic link accepting and returning numbers

**Try it online!** or see a test suite (inputs one to 32 inclusive).

### How?

```
b‘€EƇZL - Link: number, n
  €     - for each (i in [1..n]):
 ‘      -   increment = i+1
        - -> [2,3,4,...,n+1]
b       - convert (n) to those bases
    Ƈ   - filter keep if:
   E    -   all elements are equal
     Z  - transpose
      L - length (note:  length of the transpose of a list of lists is the length of the
        -                longest item in the original list, but shorter than L€Ṁ)

```

---

Or maybe I should have done:

```
b‘€EƇZLo1

```

...just for the `Lo1`z.
> 11 votes

# Answer
## JavaScript (ES6), 62 bytes

```
f=(n,b=2,l=0,d=n)=>d?n%b<1|n%b-d%b?f(n,b+1):f(n,b,l+1,d/b|0):l
```

```
<input oninput=o.textContent=f(this.value)><pre id=o>
```
> 9 votes

# Answer
# Haskell, ~~86~~ ~~81~~ 79 bytes

*2 bytes saved thanks to Laikoni*

```
0!y=[]
x!y=mod x y:div x y!y
length.head.filter(all=<<(==).head).(<$>[2..]).(!)

```

Try it online!

Since this has died down a bit, here's my approach. It's a golfed version of the sample code I made for the question. I think it can definitely be shorter. I just thought I'd put it out there.
> 6 votes

# Answer
# Husk, ~~13~~ 11 bytes

-2 bytes thanks to zgarb

```
L←fȯ¬tuMBtN

```

Try it online!
> 5 votes

# Answer
# 05AB1E, 8 bytes

```
L>вʒË}нg

```

Try it online!

-1 thanks to kalsowerus.
> 4 votes

# Answer
# Mathematica, 71 bytes

```
Max[L/@Select[Array[a~IntegerDigits~#&,a=#,2],(L=Length)@Union@#==1&]]&

```

Try it online!
> 3 votes

# Answer
# Brachylog, 12 bytes

```
+₁⟦₁b∋;?ḃ₍=l

```

Try it online!
> 2 votes

# Answer
# Python 3, ~~92~~ 87 bytes

5 bytes thanks to Halvard Hummel.

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

```

Try it online!
> 2 votes

# Answer
# APL (Dyalog Unicode), ~~28~~ 26 bytes

Saved 2 bytes thanks to Adám!

```
{⌈/≢¨⍵/⍨1=≢∘∪¨⍵}⊢⊥⍣¯1⍨¨1+⍳

```

Try it online!

Pretty straightforward implementation.

```
{⌈/≢¨⍵/⍨(1=≢∘∪)¨⍵}⊢⊥⍣¯1⍨¨1+⍳
                           1+⍳ ⍝ Make a range [2, n + 1]
                          ¨   ⍝ For each b in that range
                   ⊢⊥⍣¯1⍨    ⍝ Interpret n in base b (gives a vector of integers)
     ⍵/⍨                      ⍝ Keep the representations where
         1=≢∘∪¨⍵             ⍝ it's a repdigit
              ¨⍵             ⍝ For every representation,
          ≢∘∪                 ⍝ is the length of it, without duplicates
        1=                    ⍝ equal to 1?
   ≢¨                         ⍝ Get the length of each of the remaining representations
 ⌈/                           ⍝ Get the biggest length

```
> 2 votes

# Answer
# Husk, 7 bytes

```
LḟEMBtN

```

Try it online!

### Explanation

```
LḟEMBtN
     tN  on numbers 2,3,4...
   MB    map input to digits in base 2,3,4...
 ḟE      find first list that only has one unique element
L        length of that

```
> 2 votes

# Answer
# Mathematica, 58 bytes

```
FirstCase[#~IntegerDigits~Range[#+1],l:{a_ ..}:>Tr[1^l]]&

```

Throws an error (because base-1 is not a valid base), but it is safe to ignore.

Of course, it is okay to take the length of the first repdigit (`FirstCase`), since numbers in lower bases cannot be shorter than in higher bases.
> 1 votes

# Answer
## CJam (17 bytes)

```
{_,2>3+fb{)-!}=,}

```

Online test suite. This is an anonymous block (function) which takes an integer on the stack and leaves an integer on the stack.

Works with brute force, using `3` as a fallback base to handle the special cases (input `1` or `2`).
> 1 votes

# Answer
# Perl 6, 49 bytes

```
{+first {[==] $_},map {[.polymod($^b xx*)]},2..*}

```

Try it online!

### Explanation

```
{                                               }  # A lambda.
                  map {                   },2..*   # For each base from 2 to infinity...
                        .polymod($^b xx*)          #   represent the input in that base,
                       [                 ]         #   and store it as an array.
  first {[==] $_},                                 # Get the first array whose elements
                                                   # are all the same number.
 +                                                 # Return the length of that array.

```

The polymod method is a generalization of Python's `divmod`: It performs repeated integer division using a given list of divisors, and returns the intermediate remainders.
It can be used to decompose a quantity into multiple units:

```
my ($sec, $min, $hrs, $days, $weeks) = $seconds.polymod(60, 60, 24, 7);

```

When passing a lazy sequence as the list of divisors, `polymod` stops when the quotient reaches zero. Thus, giving it an infinite repetition of the same number, decomposes the input into digits of that base:

```
my @digits-in-base-37 = $number.polymod(37 xx *);

```

I use this here because it allows arbitrarily high bases, in contrast to the string-based `.base` method which only supports up to base 36.
> 1 votes

# Answer
## TI-BASIC, 37 bytes

```
Input N
For(B,2,2N
int(log(NB)/log(B
If fPart(N(B-1)/(B^Ans-1
End

```

Prompts for N, returns output in Ans.

# Explanation

As an overview, for each possible base B in sequence it first calculates the number of digits of N when represented in base B, then checks whether N is divisible by the value represented by that same number of 1-digits in base B.

```
Input N            Ask the user for the value of N.
For(B,2,2N         Loop from base 2 to 2N. We are guaranteed a solution
                   at base N+1, and this suffices since N is at least 1.
int(log(NB)/log(B  Calculate the number of digits of N in base B,
                   placing the result in Ans.
                   This is equivalent to floor(log_B(N))+1.
          (B-1)/(B^Ans-1   The value represented by Ans consecutive
                           1-digits in base B, inverted.
If fpart(N         Check whether N is divisible by the value with Ans
                   consecutive 1-digits, by multiplying it by the inverse
                   and checking its fractional part.
                   Skips over the End if it was divisible.
End                Continue the For loop, only if it was not divisible.
                   The number of digits of N in base B is still in Ans.

```
> 1 votes

# Answer
# K (ngn/k), 24 bytes

```
{|/x{#{1=#?x}#y\x}'2+!x}

```

Try it online!

* `x{...}'2+!x` call the inner `{...}` lambda on the input `n`, paired up with each number from `2..n+1`
    + `y\x` convert the input to the current base
    + `{1=#?x}#` filter down to representations containing only a single unique digit
    + `#` return the length of this representation (`0` if it contained multiple digits)
* `{|/...}` return the maximum across all potential bases
> 1 votes

# Answer
# Pyth, 13 bytes

```
lhf!t{TjLQ}2h

```

Try it online!
> 0 votes

# Answer
# Java 8, 111 bytes

```
n->{int r=0,i=1,l;for(String t;++i<n+2;r=(l=t.length())>r&t.matches("(.)\\1*")?l:r)t=n.toString(n,i);return r;}

```

Byte-count of 111 is also a rep-digit. ;)

**Explanation:**

Try it here.

```
n->{                            // Method with Integer as parameter return-type
  int r=0,                      //  Result-integer
      i=1,                      //  Index-integer
      l;                        //  Length-integer
  for(String t;                 //  Temp-String
      ++i<n+2;                  //  Loop from 2 to `n+2` (exclusive)
      r=                        //    After every iteration, change `r` to:
        (l=t.length())>r        //     If the length of `t` is larger than the current `r`
        &t.matches("(.)\\1*")?  //     and the current `t` is a rep-digit:
         l                      //      Change `r` to `l` (the length of the rep-digit)
        :                       //     Else:
         r)                     //      Leave `r` as is
    t=n.toString(n,i);          //   Set String representation of `n` in base-`i` to `t`
                                //  End of loop (implicit / single-line body)
  return r;                     //  Return the result-integer
}                               // End of method

```
> 0 votes

# Answer
# Java 8, 79 bytes

A lambda from `Integer` to `Integer`.

```
n->{int m,b=2,l;for(;;b++){for(m=n,l=0;m>0&m%b==n%b;l++)m/=b;if(m<1)return l;}}

```

## Ungolfed lambda

```
n -> {
    int m, b = 2, l;
    for (; ; b++) {
        for (m = n, l = 0; m > 0 & m % b == n % b; l++)
            m /= b;
        if (m < 1)
            return l;
    }
}

```

Checks radices in increasing order from 2 until a rep-digit radix is found. Relies on the fact that the smallest such radix will correspond to a representation with the most digits.

`m` is a copy of the input, `b` is the radix, and `l` is the number of digits checked (and ultimately the length of the radix-`b` representation).
> 0 votes

# Answer
## Burlesque, 24 bytes

(see correct solution below)

```
J2jr@jbcz[{dgL[}m^>]

```

See in action.

```
J2jr@ -- boiler plate to build a list from 2..N
jbcz[ -- zip in N
{dgL[}m^ -- calculate base n of everything and compute length
>]    -- find the maximum.

```

At least if my intuition is right that a rep-digit representation will always be longest? Otherwise uhm...

```
J2jr@jbcz[{dg}m^:sm)L[>]

:sm -- filter for "all elements are the same"

```
> 0 votes

# Answer
# Ruby, 60 bytes

```
->n{(2..n).filter_map{d=n.digits _1
!d.uniq[1]&&d.size}.max}

```

Attempt This Online!
> 0 votes

---
Tags: code-golf, base-conversion
---


title: Do the NP: find the largest clique

text:
# Question
Title: Do the NP: find the largest clique
# Background

At the time of writing this, the P vs NP problem is still unsolved, but you might have heard of Norbert Blum's new paper claiming proof that P != NP, which is already suspected to be erroneous (but we will see).

The problem discussed in this paper is the clique problem. At least that's what I read in a newspaper article, so correct me if I'm wrong, but in any case, I'd like you to write a program that solves the following variant:

# The task

Assume we have a large school with lots of students. Each of these students has some friends at this school. A **clique** of students is a group consisting only of students who are friends with **each other member**.

Your program will receive pairs of students who are friends as its input. From this information, the program must find the **size of the largest clique**. Students are identified by *integer IDs*.

If you prefer mathematical terms, this means you're fed the edges of an undirected graph, identified by two nodes each.

### Input

Your input will be a non-empty list of positive integer pairs, e.g. `[[1,2],[2,5],[1,5]]`. You can take this input in any sensible form, e.g. as an array of arrays, as lines of text containing two numbers each, etc ...

### Output

The expected output is a single number `n >= 2`: the size of the largest clique. With the example input above, the result would be `3`, as all students (`1`, `2` and `5`) are friends with each other.

### Test cases

```
[[1,2]]
=> 2

[[1,2],[3,1],[3,4]]
=> 2

[[1,2],[2,5],[1,5]]
=> 3

[[2,5],[2,3],[4,17],[1,3],[7,13],[5,3],[4,3],[4,1],[1,5],[5,4]]
=> 4 (the largest clique is [1,3,4,5])

[[15,1073],[23,764],[23,1073],[12,47],[47,15],[1073,764]]
=> 3 (the largest clique is [23,764,1073])

[[1296,316],[1650,316],[1296,1650],[1296,52],[1650,711],[711,316],[1650,52],
 [52,711],[1296,711],[52,316],[52,1565],[1565,1296],[1565,316],[1650,1565],
 [1296,138],[1565,138],[1565,711],[138,1650],[711,138],[138,144],[144,1860],
 [1296,1860],[1860,52],[711,1639]]
=> 6 (the largest clique is [52,316,711,1296,1565,1650])

```

You can use this (stupid) reference implementation (prints extra output with `-d` flag) for verifying the results of other test cases.

# The rules

1. Your program doesn't need a defined result on invalid input. So you can assume that:
    * you will always get **at least one pair** of IDs
    * each pair consists of two different IDs
    * no pair appears twice (swapping the places of the IDs would still be the same pair)
2. Your algorithm isn't allowed to set an upper bound on input size. Purely technical limitations and limitations set by your language/environment (like stack size, computation time, etc) are of course inevitable.
3. Standard loopholes are forbidden.
4. This is , so the shortest code, measured in bytes, wins.
5. If your algorithm has polynomial time complexity, you score `-1` immediately regardless of your code size, but in that case, you might want to submit your solution somewhere else. ;)

# Answer
# Jelly,  ~~15 18~~  16 bytes

+3 bytes to fix bugs in my method.
-2 bytes thanks to miles (noting that **n×(n-1)÷2 = nC2**)

```
ẎQL©c2⁼Lȧ®
ŒPÇ€Ṁ

```

A monadic link taking the list of friendships (edges) and returning an integer.

**Try it online!** forms the power-set of the edges in memory so is inefficient both in space and time (yep,that's **O(2n)** folks)!

### How?

```
ẎQL©c2⁼Lȧ® - Link 1, isClique?: list, edges  e.g. [[1,3],[2,3],[3,4],[4,1],[4,2],[2,1]]
Ẏ          - tighten                              [ 1,3 , 2,3 , 3,4 , 4,1 , 4,2 , 2,1 ]
 Q         - de-duplicate (gets unique ids)          [1,3,2,4]
  L        - length (get number of people involved)  4
   ©       - (copy to the register)
    c2     - combinations of 2 (z-choose-2)          6
       L   - length (of edges)                       6
      ⁼    - equal?                                  1
         ® - recall value from register              4
        ȧ  - logical and                             4
           - (Note: the number of edges of a clique of size n is n*(n-1) and we're
           -  guaranteed no repeated edges and that all edges are two distinct ids)

ŒPÇ€Ṁ - Link: list of lists, edges
ŒP    - power-set (all possible sets of edges (as lists))
  Ç€  - call last link (1) as a monad for €ach
    Ṁ - maximum

```
> 6 votes

# Answer
# Mathematica, 34 bytes

```
Tr[1^#&@@FindClique[#<->#2&@@@#]]&

```

Basically FindClique does the job and "finds a largest clique in the graph g."
All the other stuff is converting input-list into graph

**Input**

> \[{{2, 5}, {2, 3}, {4, 17}, {1, 3}, {7, 13}, {5, 3}, {4, 3}, {4, 1}, {1, 5}, {5, 4}}\]

**Output**

> 4

**Input**

> \[{{1296, 316}, {1650, 316}, {1296, 1650}, {1296, 52}, {1650, 711}, {711, 316}, {1650, 52}, {52, 711}, {1296, 711}, {52, 316}, {52, 1565}, {1565, 1296}, {1565, 316}, {1650, 1565}, {1296, 138}, {1565, 138}, {1565, 711}, {138, 1650}, {711, 138}, {138, 144}, {144, 1860}, {1296, 1860}, {1860, 52}, {711, 1639}}\]

**Output**

> 6

*thanx @Kelly Lowder for -10 bytes*
> 13 votes

# Answer
# Jelly, 20 bytes

```
ŒPẎ€µQL’=ċÐ€`ẠµÐfṪQL

```

Try it online!

Of course this doesn't deserve the million :p

This would've beat Pyth, if not for the `µ(...)µ` and 2-byte `Ðf`.
> 6 votes

# Answer
# , 36 bytes

```
[:>./](#(]*[=2!])#@~.@,)@#~2#:@i.@^#

```

Try it online!

Runs in time *O*(2*n*) where *n* is the number of pairs.

A faster solution for 65 bytes is

```
3 :'$>{._2{~.@((+.&(e.&y)&<|.)@(-.,-.~)&>/#&,/:~@~.@,&.>/)~^:a:y'

```

Try it online!

## Explanation

```
[:>./](#(]*[=2!])#@~.@,)@#~2#:@i.@^#  Input: list of pairs
                                   #  Length
                           2      ^   2^n
                               i.@    Range [0, 2^n)
                            #:@       Binary
                         #~           Copy
      (                )@             For each
                      ,                 Flatten
                   ~.@                  Unique
                 #@                     Length
        (       )                       Dyad with RHS at previous and LHS as next
               ]                          Get RHS
             2!                           Binomial coefficient, choose 2
            =                             Equals
           [                              Get LHS
          *                               Times
         ]                                Get RHS
       #                                Length
[:>./                                 Reduce using maximum

```
> 3 votes

# Answer
# Python 2, 180 bytes

```
G=input()
m=0
L=len
for i in range(2**L(G)):
 u=[];p=sum([G[j]for j in range(L(G))if 2**j&i],u)
 for j in p:u+=[j][j in u:]
 m=max(m,L(u)*all(p.count(j)==L(u)-1for j in u))
print m

```

Try it online!

-2 thanks to shooqie.
-1 thanks to Mr. Xcoder.
-3 thanks to recursive.
> 2 votes

# Answer
# Pyth, 19 bytes

```
l{ef.AqLtl{T/LTTsMy

```

Try it here.
> 2 votes

# Answer
# 6502 machine code (C64), 774 703 bytes

(I just **had** to do this, my C64 can do everything ... hehe)

**hexdump:**

```
00 C0 A9 00 A2 08 9D 08 00 CA 10 FA A2 04 9D FB 00 CA 10 FA 20 54 C0 B0 20 AD
C9 C2 AE CA C2 20 92 C1 B0 31 8D 31 C0 AD CB C2 AE CC C2 20 92 C1 B0 23 A2 FF
20 FE C1 90 DB 20 6A C2 20 C1 C1 B0 05 20 6A C2 50 F6 A5 FB 8D D3 C2 20 43 C1
A9 CD A0 C2 20 1E AB 60 A2 00 86 CC 8E 61 C0 20 E4 FF F0 FB A2 FF C9 0D F0 10
E0 0B 10 0C 9D BD C2 20 D2 FF E8 8E 61 C0 D0 E5 C6 CC A9 20 20 D2 FF A9 0D 20
D2 FF A9 00 9D BD C2 AA BD BD C2 F0 5C C9 30 30 0E C9 3A 10 0A 9D CD C2 E8 E0
06 F0 4C D0 E9 C9 20 D0 46 A9 00 9D CD C2 E8 8E BC C0 20 EB C0 AD D3 C2 8D C9
C2 AD D4 C2 8D CA C2 A2 FF A0 00 BD BD C2 F0 0F C9 30 30 21 C9 3A 10 1D 99 CD
C2 C8 E8 D0 EC A9 00 99 CD C2 20 EB C0 AD D3 C2 8D CB C2 AD D4 C2 8D CC C2 18
60 38 60 A2 FF E8 BD CD C2 D0 FA A0 06 88 CA 30 0A BD CD C2 29 0F 99 CD C2 10
F2 A9 00 99 CD C2 88 10 F8 A9 00 8D D3 C2 8D D4 C2 A2 10 A0 7B 18 B9 53 C2 90
02 09 10 4A 99 53 C2 C8 10 F2 6E D4 C2 6E D3 C2 CA D0 01 60 A0 04 B9 CE C2 C9
08 30 05 E9 03 99 CE C2 88 10 F1 30 D2 A2 06 A9 00 9D CC C2 CA D0 FA A2 08 A0
04 B9 CE C2 C9 05 30 05 69 02 99 CE C2 88 10 F1 A0 04 0E D3 C2 B9 CE C2 2A C9
10 29 0F 99 CE C2 88 10 F2 CA D0 D9 C8 B9 CD C2 F0 FA 09 30 9D CD C2 E8 C8 C0
06 F0 05 B9 CD C2 90 F0 A9 00 9D CD C2 60 85 0A A4 09 C0 00 F0 11 88 B9 D5 C2
C5 0A D0 F4 8A D9 D5 C3 D0 EE 98 18 60 A4 09 E6 09 D0 01 60 A5 0A 99 D5 C2 8A
99 D5 C3 98 99 D5 C4 18 60 A6 0B E4 09 30 01 60 BD D5 C5 C5 0B 30 09 A9 00 9D
D5 C5 E6 0B D0 E9 A8 FE D5 C5 8A 29 01 D0 02 A0 00 BD D5 C4 59 D5 C4 9D D5 C4
59 D5 C4 99 D5 C4 5D D5 C4 9D D5 C4 A9 00 85 0B 18 60 A8 A5 0C D0 08 A9 20 C5
0D F0 21 A5 0C 8D 1E C2 8D 21 C2 A5 0D 09 60 8D 1F C2 49 E0 8D 22 C2 8C FF FF
8E FF FF E6 0C D0 02 E6 0D 18 60 86 0E 84 0F A5 0D 09 60 8D 54 C2 49 E0 8D 5F
C2 A6 0C CA E0 FF D0 10 AC 54 C2 88 C0 60 10 02 18 60 8C 54 C2 CE 5F C2 BD 00
FF C5 0E F0 04 C5 0F D0 E0 BD 00 FF C5 0E F0 04 C5 0F D0 D5 38 60 A2 00 86 FC
86 FD 86 FE BD D5 C4 A8 A6 FE E4 FC 10 11 BD D5 C7 AA 20 2B C2 90 14 E6 FE A6
FE E4 FC D0 EF A6 FD BD D5 C4 A6 FC E6 FC 9D D5 C7 E6 FD A6 FD E4 09 D0 16 A6
FB E4 FC 10 0F A2 00 BD D5 C7 9D D5 C6 E8 E4 FC D0 F5 86 FB 60 A0 00 84 FE F0
B5

```

### Online demo

Usage: Start with `sys49152`, then enter the pairs one per line like e.g.

```
15 1073
23 764
23 1073
12 47
47 15
1073 764

```

Backsapce **isn't** handled during input (but if you use `vice`, just copy&paste your input into the emulator). Enter an empty line to start calculation.

This is too large to post an explanatory disassembly listing here, but you can browse the ca65-style assembly source. The algorithm is very inefficient, it generates every possible permutation of the nodes and with each of these greedily builds a clique by checking all the edges. This allows for a *space efficiency* of **O(n)** (kind of important on a machine with this little RAM), but has **horrible** *runtime efficiency* **(\*)**. The theoretical limits are up to 256 nodes and up to 8192 edges.

* -71 bytes: optimized routine for checking edges and zeropage usage

---

There's a larger (883 805 bytes) version with better features:

* visual feedback during calculation (each permutation of the nodes changes the border color)
* uses bank switching to store the edges in the RAM "hidden" by the ROMs to conserve space
* outputs the size **and** the nodes of the maximal clique found

**Online demo**

**Browse source**

---

**(\*)** The last test case takes something between 12 and 20 hours (I was sleeping when it finally finished). The other test cases finish at worst within some minutes.
> 2 votes

# Answer
# 05AB1E, 19 bytes

```
æ€˜ʒDÙg<s{γ€gQP}θÙg

```

Try it online!
> 1 votes

# Answer
# Pyth, 28 bytes

```
l{sSef<T.{SMQm.{ft{T.Cd2yS{s

```

Try it online

### Explanation

```
l{sSef<T.{SMQm.{ft{T.Cd2yS{s
                         S{sQ  Get the distinct nodes in the (implicit) input.
                        y      Take every subset.
             m      .Cd2       Get the pairs...
                ft{T           ... without the [x, x] pairs...
              .{               ... as sets.
     f<T                        Choose the ones...
        .{  Q                   ... which are subsets of the input...
          SM                    ... with edges in sorted order.
    e                           Take the last element (largest clique).
l{sS                            Get the number of distinct nodes.

```
> 1 votes

# Answer
# Python 3, 162 159 bytes

```
lambda x,f=lambda x:{i for s in x for i in s}:len(f(x))if all([(y,z)in x or(z,y)in x for y in f(x)for z in f(x)if y<z])else max(c(x.difference({y}))for y in x)

```

Try it online!

Function c takes vertices in the form of a set of sorted tuples ({(x,y),...} where x is less than y). A function called "entry" is in the TIO header to test with data in list of unsorted lists format. If clique, returns length. If not clique, returns max clique size of vertices, minus a vertice for each vertice in vertices. Exceeds time on last test case in TIO

Update: "or(z,y)in x" portion added to remove dependency on sortedness "f=lambda x:{i for s in x for i in s}" instead of itertools.chain wrapped in set.

-minus 3 bytes thanks to @Jonathan Allen
> 1 votes

# Answer
# Jelly, 28 bytes

```
œ^e³;U¤
Œcç/Ðfœ|Ṣ¥/€QµÐĿ-ịḢL

```

Try it online!

Faster solution that is able to solve the last test case in a second on TIO.
> 1 votes

# Answer
# Java + Guava 23.0, 35 + 294 = 329 bytes

```
import com.google.common.collect.*;
a->{int l=0,o=1,c,z=a.size();for(;o>0&l<z;){o=0;c:for(Iterable<int[]>s:Sets.combinations(a,l*(l+1)/2)){Multiset<Integer>m=TreeMultiset.create();for(int[]x:s){m.add(x[0]);m.add(x[1]);}c=m.elementSet().size();for(int e:m.elementSet())if (m.count(e)!=c-1)continue c;l+=o=1;break;}}return z<3?2:l;}

```

This algorithm is not graphing, but instead is generating all combinations of pairs, of a specific size. I feed all pair-combinations into a multiset and check that they all have the expected size (the number of unique entries - 1). If they do, I found a clique and I go look for a bigger one.

From the Guava library, I use the new `combinations` method, and the tool-collection-type `Multiset`.

# Ungolfed

```
import com.google.common.collect.*;
import java.util.function.*;

public class Main {

  public static void main(String[] args) {
    ToIntFunction<java.util.Set<int[]>> f
        = a -> {
          int l = 0, o = 1, c, z = a.size();
          for (; o > 0 & l < z;) {
            o = 0;
            c:
            for (Iterable<int[]> s : Sets.combinations(a, l * (l + 1) / 2)) {
              Multiset<Integer> m = TreeMultiset.create();
              for (int[] x : s) {
                m.add(x[0]);
                m.add(x[1]);
              }
              c = m.elementSet().size();
              for (int e : m.elementSet()) {
                if (m.count(e) != c - 1) {
                  continue c;
                }
              }
              l += o = 1;
              break;
            }
          }
          return z < 3 ? 2 : l;
        };
    int[][][] tests = {
      {{1, 2}},
      {{1, 2}, {3, 1}, {3, 4}},
      {{1, 2}, {2, 5}, {1, 5}},
      {{2, 5}, {2, 3}, {4, 17}, {1, 3}, {7, 13}, {5, 3}, {4, 3}, {4, 1}, {1, 5}, {5, 4}},
      {{15, 1073}, {23, 764}, {23, 1073}, {12, 47}, {47, 15}, {1073, 764}},
      {{1296, 316}, {1650, 316}, {1296, 1650}, {1296, 52}, {1650, 711}, {711, 316}, {1650, 52}, {52, 711}, {1296, 711}, {52, 316}, {52, 1565}, {1565, 1296}, {1565, 316}, {1650, 1565}, {1296, 138}, {1565, 138}, {1565, 711}, {138, 1650}, {711, 138}, {138, 144}, {144, 1860}, {1296, 1860}, {1860, 52}, {711, 1639}}
    };
    for (int[][] test : tests) {
      java.util.Set<int[]> s = new java.util.HashSet<int[]>();
      for (int[] t : test) {
        s.add(t);
      }
      System.out.println(f.applyAsInt(s));
    }
  }
}

```
> 1 votes

# Answer
# Python 2, 102 bytes

```
def f(g):
 x=g
 while x:y=x;x=map(set,{tuple(u|v)for u in x for v in x if u^v in g})
 return len(y[0])

```

Try it online!
> 1 votes

# Answer
# C (gcc), ~~790 778 757 748 731 687 642~~ 632 bytes

```
typedef struct F F;typedef struct{int c,p;F**m;}g;struct F{int d;g f;};g*a,S,y,q,*x=&y,*p=&q,Q;A(g*g,F*s){g->c++[g->m=g->c-g->p?g->m:realloc(g->m,(g->p+=32)*20)]=s;}i,c[999],b,j,k,l,*s;*B(d){s=0;for(i=S.c;i--;)s=S.m[i]->d-d?s:S.m[i];!s?s=calloc(5,4),*s=d,A(&S,s):0;s=s;}F*u,*v;E(){for(i=-1;b=++i<S.c;b&&A(x,S.m[i]))for(l=x->c;k=l--*b;b&=!k)for(j=(Q=x->m[l]->f).c;j--&&(k=Q.m[j]->d-S.m[i]->d););x->c>p->c?a=x,x=p,p=a:0;x->c=0;}main(){for(;~scanf("%d %d",&a,&b)&&A(&(u=B(a))->f,v=B(b))|~A(&v->f,u););for(E();b<S.c;)c[b]>=b?c[b++]=0:E(S.m[b]=a,S.m[i]=S.m[b],a=S.m[i=b%2*c[b]++]);for(printf("%d,",i=p->c);i--;)printf(" %d",p->m[i]->d);}

```

This is a slightly golfed version of the reference implementation. Thanks to @jdt for -5. Try it online!

Slightly golfed less

```
typedef struct F F;
// student group
typedef struct{
  int c, // count
      p; // capacity
  F**m;  // members
}g;
// student
struct F{
  int d; // id
  g f;   // friends
};
g*a,S,y,q,*x=&y,*p=&q,Q;
A(g*g,F*s){
  g->c++[g->m=g->c-g->p?g->m:realloc(g->m,(g->p+=32)*20)]=s;
}
i,c[999],b,j,k,l,*s;
*B(d){
  s=0;
  for(i=S.c;i--;)
    s=S.m[i]->d-d?s:S.m[i];
  !s?
    s=calloc(5,4),
    *s=d,
    A(&S,s)
  :
    0;
  s=s;
}
F*u,*v;
E(){
  for(i=-1;b=++i<S.c;b&&A(x,S.m[i]))
    for(l=x->c;k=l--*b;b&=!k)
      for(j=(Q=x->m[l]->f).c;j--&&(k=Q.m[j]->d-S.m[i]->d););
  x->c>p->c?
    a=x,
    x=p,
    p=a
  :
    0;
  x->c=0;
}
main(){
  for(;~scanf("%d %d",&a,&b)&&A(&(u=B(a))->f,v=B(b))|~A(&v->f,u););
  for(E();b<S.c;)
    c[b]>=b?
      c[b++]=0
    :
      E(S.m[b]=a,S.m[i]=S.m[b],a=S.m[i=b%2*c[b]++]);
  for(printf("%d,",i=p->c);i--;)
    printf(" %d",p->m[i]->d);
}

```
> 0 votes

# Answer
# Pyth, 17 bytes

```
l{seq#.c{sT2tySSM

```

Try it online!

* `SSM`: Sort each edge, then sort the edges.
* `y`: Form all subsets of edges, with each subset in sorted order. The subsets are ordered by increasing length.
* `t`: Remove the first subset, which is the empty subset, as it would cause the program to crash.
* `q#`: Filter over the subsets on the following resulting in an identical list of edges as the particular subset.
* `{sT`: Sum the list and deduplicate, giving all vertices in any of the edges. If the subset was a clique, the vertices will be in sorted order.
* `.c ... 2`: All distinct pairs of vertices, in sorted order.
* `e`: The filter returns all cliques. Take the last clique, which is the largest clique.
* `{s`: Sum and deduplicate, giving the vertices in the largest clique.
* `l`: Length of the longest clique.

Apparently, during the brief window from May 2017 to Nov. 2017, during which this challenge was posted, `sY` returned an empty list, rather than 0, as it currently does, so the `t` could have been removed for -1 byte. Before and after, this would cause a crash. See commit 5b973af89b, which was the most recent commit when this challenge was posted.
> 0 votes

---
Tags: code-golf, graph-theory
---


# Question
Title: SKI calculus golf: Half of a Church numeral
## Background

SKI combinator calculus, or simply SKI calculus, is a system similar to lambda calculus, except that SKI calculus uses a small set of *combinators*, namely `S`, `K`, and `I` instead of lambda abstraction. Unlike lambda calculus, beta reduction is possible only when a combinator is given enough arguments to reduce.

The three combinators in SKI calculus are defined as follows:

$$ \begin{aligned} S\\;x\\;y\\;z & \overset{S}{\implies} x\\;z\\;(y\\;z) \\ K\\;x\\;y & \overset{K}{\implies} x \\ I\\;x & \overset{I}{\implies} x \end{aligned} $$

For example, the SKI expression \\$ e=S(K(S\\;I))K \\$ is equivalent to the lambda expression \\$ λx.λy.y\\;x \\$, as applying two arguments to \\$ e \\$ reduces to the desired result:

$$ \begin{aligned} S(K(S\\;I))K\\;x\\;y & \overset{S}{\implies} (K(S\\;I)x)(K\\;x)y \\ & \overset{K}{\implies} S\\;I(K\\;x)y \\ & \overset{S}{\implies} (I\\;y)(K\\;x\\;y) \\ & \overset{I,K}{\implies} y\\;x \end{aligned} $$

It is known that any lambda expression can be converted to a SKI expression.

A Church numeral is an encoding of natural numbers (including zero) as a lambda expression. The Church encoding of a natural number \\$ n \\$ is \\$ λf. λx. f^n\\;x \\$ \- given a function \\$ f \\$ and an argument \\$ x \\$, \\$ f \\$ repeatedly applied to \\$ x \\$ \\$ n \\$ times.

It is possible to construct a lambda expression (and therefore a SKI expression) that performs various arithmetic (e.g. addition, multiplication) in Church encoding. Here are a few examples of Church numerals and Church arithmetic functions: (The given SKI expressions are possibly not minimal.)

$$ \begin{array}{r|r|r} \text{Expr} & \text{Lambda} & \text{SKI} \\ \hline 0 & λf. λx. x & K\\;I \\ 1 & λf. λx. f\\;x & I \\ 2 & λf. λx. f(f\\;x) & S (S (K\\;S) K) I \\ \text{Succ} \\; n & λn. λf. λx. f(n\\;f\\;x) & S (S (K\\;S) K) \\ m+n & λm. λn. λf. λx. m\\;f(n\\;f\\;x) & S (K S) (S (K (S (K\\;S) K))) \end{array} $$

## Challenge

Write an SKI expression that accepts a Church numeral of \\$ n \\$ and evaluates to the Church numeral of \\$ \lfloor n/2 \rfloor \\$.

## Scoring and winning criterion

The score is the total number of `S`, `K`, and `I` combinators used. The submission with the lowest score wins.

Here is a Python script to check the correctness and score of your SKI expression. For the record, I have a (relatively naïve) solution of score 126.

# Answer
# 40 combinators

```
S(S(SI(K(S(S(KS)K)(K(S(S(KS)(S(KK)S))(K(S(KK)(S(S(KS)K)))))))))(K(S(SI(K(KI)))(K(KI)))))(KK)

```

Try it online!

Generated with a little help from a slightly modified version of my answer to Combinatory Conundrum:

$$\begin{align\*} \textit{zero} &= λf. λx. x = KI \\ \textit{succ} &= λn. λf. λx. f\\,(n\\,f\\,x) = S(S(KS)K) \\ \textit{zero-pair} &= λf. f\\,\textit{zero}\\,\textit{zero} = S(SI(K\\,\textit{zero}))(K\\,\textit{zero}) \\ \textit{next-pair-helper} &= λf. λm. λn. f\\,n\\,(\textit{succ}\\,m) \\ &= S(S(KS)(S(KK)S))(K(S(KK)\\,\textit{succ})) \\ \textit{next-pair} &= λp. λf. p\\,(\textit{next-pair-helper}\\,f) \\ &= S(S(KS)K)(K\\,\textit{next-pair-helper}) \\ \textit{half} &= λn. n\\,\textit{next-pair}\\,\textit{zero-pair}\\,K \\ &= S(S(SI(K\\,\textit{next-pair}))(K\\,\textit{zero-pair}))(KK) \end{align\*}$$
> 15 votes

# Answer
# 31 combinators

```
S(S(S(SI(K(S(S(KS)(S(KK)S))(K(S(KK)(S(S(KS)K)))))))(KK))(K(KI)))(K(KI))

```

Try it online!

$$\begin{align\*} \textit{zero} &= λf. λx. x = KI \\ \textit{succ} &= λn. λf. λx. f\\,(n\\,\\,f\\,\\,x) = S(S(KS)K) \\ \textit{fst} &= λm. λn. m = K \\ \textit{next} &= λg. λm. λn. g\\,\\,n\\,(\textit{succ}\\,\\,m) = S(S(KS)(S(KK)S))(K(S(KK)\\,\textit{succ})) \\ \textit{half} &= λn. n\\,\\,\textit{next}\\,\\,\textit{fst}\\,\\,\textit{zero}\\,\\,\textit{zero} = S(S(S(SI(K\\,\textit{next}))(K\\,\textit{fst}))(K\\,\textit{zero}))(K\\,\textit{zero}) \end{align\*}$$
> 4 votes

# Answer
# 56 combinators

```
S(K(SI(KK)))(S(SI(K(S(S(K(S(K(S(S(K(S(KS)K))S)(KK)))(S(K(SI))K)))(SI(K(KI))))(S(K(S(S(KS)K)))(SI(KK))))))(K(S(SI(K(KI)))(K(KI)))))

```

Try it online!

This is the hand-optimized version of my own solution (originally of score 126). I also used the "pair" construct, but in rather basic way.

$$ \begin{align\*} \textit{zero} &= λf. λx. x = KI \\ \textit{succ} &= λn. λf. λx. f\\,(n\\,f\\,x) = S(S(KS)K) \\ \textit{pair} &= λx. λy. λf. f\\,x\\,y \\ \textit{zero-pair} &= \textit{pair}\\,\textit{zero}\\,\textit{zero} \\ \textit{fst} &= λp. p\\,(λx. λy. x) \\ \textit{snd} &= λp. p\\,(λx. λy. y) \\ \textit{next-pair} &= λp. \textit{pair}\\,(\textit{snd}\\,p)\\,(\textit{succ}\\,(\textit{fst}\\,p))\\ \textit{half} &= λn. \textit{fst}\\,(n\\,\textit{next-pair}\\,\textit{zero-pair}) \end{align\*} $$

Then I used \\$SKIBC\\$-conversion. Those reverse-applications generated lots of \\$C\\$s (\\$C = (S (S (K (S (K S) K)) S) (K K))\\$), which turned out to be very heavy even after reduction.
> 3 votes

# Answer
# 45 combinators

```
S(K(SI(KK)))(S(SI(K(SI(K(S(K(S(S(KS)(S(K(SI))K))))(S(KK)(S(KK)(S(S(KS)K)))))))))(K(S(SI(K(KI)))(K(KI)))))

```

From `\n.(\p.p(\xy.x))(n(\p.p(\xyf.fy(\fz.f(xfz))))(\f.f00))`.
> 2 votes

---
Tags: atomic-code-golf, combinatory-logic
---


# Question
Title: CGAC2022 Day 12: Santa's gift and the laser lock
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

There's a good news and a bad news.

Good news: you got a Christmas present from Santa. (Already?! Christmas is two weeks away!)

Bad news: the present is locked with a laser lock. And a note next to it says:

> Only the ones who can properly open the lock deserve the present inside. If you force it or fail to open in 24 hours, the present will turn into a piece of coal.

You carefully examine the laser lock. It has a laser, a sensor, and a grid of square cells. Some cells already have a piece of mirror, and some of the empty ones are colored red; the others are green.

```
          +-+-+-+-+-+-+-+
laser --> |G|G|R|\|G|G|G|
          +-+-+-+-+-+-+-+
          |\|R|/|G|R|G|\| --> sensor
          +-+-+-+-+-+-+-+

```

You immediately think, "Aha, so I'm supposed to place some mirrors on some of the green cells so the laser goes to the sensor."

So one possible solution to the above would be:

```
          +-+-+-+-+-+-+-+
laser --> |.|.|R|\|.|/|\|
          +-+-+-+-+-+-+-+
          |\|R|/|\|R|/|\| --> sensor
          +-+-+-+-+-+-+-+

```

## Task

In this task, the positions of the laser and the sensor are fixed, and the height of the grid is always 2. Given the state of the lock as a 2-by-N grid, output a possible solution.

The input grid is given as a 2D string like

```
GGR\GGG
\R/GRG\

```

but the following variations (and combinations thereof) are allowed:

* an array of rows / a matrix / a flattened string or array
* charcodes instead of characters
* transposed grid (in other words, columns instead of rows)
* lowercase instead of uppercase

The output must be in the same format as the input, with each `G` replaced with `.` (nothing) or one of `\/` (a mirror). Replacing all `R`s with `.` in addition to the above is allowed.

```
..R\./\  or  ...\./\
\R/\R/\      \./\./\

```

You may assume that the solution always exists. If there are multiple solutions, you may output any one of them.

No other alternative I/O formats are allowed.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
G
G
->
\
\

GG
RG
->
.\
R\

G\/R/\/GG
GRGGGRGR\
->
\\/R/\/.\
\R...R/R\

G\
G\
->
.\ or .\ or .\
.\    /\    \\

```

# Answer
> 6 votes
# JavaScript (Node.js), 128 bytes

```
f=a=>[...'./\\'].some(c=>(b=a.replace(/g/,c))<a?f(b):b.split`
`.map(v=>p=v==['\\\\','//'][p]?1-p:p/ /r|\./.test(v[p]),p=0)|p)&&b

```

Try it online!

\\$O\left(3^n\right)\\$ solution. Input a multiple line string as transposed matrix with lowercase letters.

> Is this somehow *"if you force it"*?

```
f=(
  a // the input grid
)=>
[...'./\\'].some(c=> // for each possible replacement of letter "g"
  (b=a.replace(/g/,c)) // replace the first occurrence of "g"
    <a? // if any "g" exists (replaced successfully)
        // or the string is out of "g" otherwise
      f(b): // recursively try next "g"s
      b.split`\n`.map(v=> // for each column of a possible replacement
        p=v==['\\\\','//'][p]?1-p: // If the pattern is '//' or '\\' it reflect laser to another row
        p/ /r|\./.test(v[p]) // if the cell is 'r' or '.', it keeps laser on the same row (p/1==p); otherwise, set to invalid values (NaN or Infity)
      ,p=0) // the laser starts from first row
      |p)&&b // if the laser finally output from second row, "b" is a solution we found

```

---

# JavaScript (Node.js), 142 bytes

```
f=([x,y,...a],p=[],q,h=s=>q&&!/(.).(?!\1)[^RG]|[^.].R/.test(s+x+y)&&q+s,o=h(x+'.')||h`..`,O=h`//`)=>x?f(a,h('.'+y,q=p)||h`..`||O,o||h`\\\\`):q

```

Try it online!

\\$O(n)\\$ solution. Input transposed flatten string with uppercase letters.

```
f=(
  [x,y, // for each column of the grid, "x" and "y" are two cells on this column
  ...a], // the remaining grid
  p=[], // A solution where laser on the first row, or falsy if impossible
  q, // A solution where laser on the second row, or falsy if impossible
  h=s=> // "s" is a possible replacement of current column
    // if the laser can running on row "p" ("p" is reassigned later)
    // and the replacement of current column is valid
    // then we got a solution
    p&&!/(.).(?!\1)[^RG]|[^.].R/.test(s+x+y)&&p+s,
    o=h('\\\\')
)=>x? // if any more columns here
  f(a,
    h(D='..')||h('.'+y)||h('//',p=q), // all possible patterns where laser on first row
    o||h(D,p=q)||h(x+'.') // all possible patterns where laser on second row
  ):q

```

---

Only valid patterns are:

```
Laser -> \
         \ -> Laser

Laser -> . -> Laser
         ?

         / -> Laser
Laser -> /

         ?
Laser -> . -> Laser

```

So we only need to verify all these patterns and treat all other patterns as invalid.

# Answer
> 4 votes
# Charcoal, ~~93~~ 74 bytes

```
⊞υ\ＦＥθ⁺ι§ηκ≔ΣＥυΦ⟦⁺⭆κ⎇νμ⁻\/μ×²§κ⁰⁺κ⪫⪪ιG¦.⟧⎇ν№α§ι⁼§κ⁰/⬤ι№⁺G§κ⁰ξυ⪪Φ⊟Φυ⌕\ικ²‖↙

```

Attempt This Online! Link is to verbose version of code. Explanation: Inspired by the alternate input format, this sticks to the original input format and pays the 8 byte penalty for transposing the input and output.

```
⊞υ\

```

Start with a single state of the beam in the top row. The first character of the state is `\` if the beam is in the top and `/` if the beam is in the bottom row, while the remaining characters are the columns processed so far in a flattened representation.

```
ＦＥθ⁺ι§ηκ

```

Transpose the input and loop over each column. (Note: row/column here refer to the original input, not the transposed version.)

```
≔ΣＥυΦ⟦⁺⭆κ⎇νμ⁻\/μ×²§κ⁰⁺κ⪫⪪ιG¦.⟧⎇ν№α§ι⁼§κ⁰/⬤ι№⁺G§κ⁰ξυ

```
* `⭆κ⎇νμ⁻\/μ` \- Flips the row of the state.
* `⪫⪪ιG¦.` \- Replaces `G`s in the current column with `.`s
* `№α§ι⁼§κ⁰/` \- Checks whether the current cell is empty.
* `⬤ι№⁺G§κ⁰ξ` \- Checks whether both the rows can contain the correct mirror.

Loop over the current states, collecting states where the beam switches or doesn't switch appropriately depending on whether the column can have the correct mirrors or there is an empty space in the current cell.

```
⪪Φ⊟Φυ⌕\ικ²

```

Output any state which has the beam in the bottom row.

```
‖↙

```

Transpose the output.

66 bytes using the new transposed input format:

```
⊞υ\ＷＳ≔ΣＥυΦ⟦⁺⭆κ⎇νμ⁻\/μ×²§κ⁰⁺κ⪫⪪ιG¦.⟧⎇ν№α§ι⁼§κ⁰/⬤ι№⁺G§κ⁰ξυ⪪Φ⊟Φυ⌕\ικ²

```

Attempt This Online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation: As above but simply uses `ＷＳ` to iterate over the input and doesn't need to transpose at the end either of course.

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

I/O format: matrix of ASCII codes.

I would probably have golfed this differently if I had noticed the rule about removing all G's earlier.

```
m=>(g=(x,y=0,d=1,_,r=m[y],c=r[x])=>c?c%9&2?c%2^y^d&&g(x+!d,y^d,!d):d&&g(x+1,y)||c==71&&g(x,y,d,r[x]=y^d?92:47):y&&m.map(r=>r.map(c=>c-71?c:46)))(0)

```

Try it online!

# Answer
> 2 votes
# Python, ~~309~~ ~~281~~ 243 bytes

```
lambda a:max(map(lambda t,b=0:all(i%2^1and(s:=j)or s==j=="\\/"[b]and~(b:=b^1)or(s,j)[b]in".R"for i,j in E(t))and t*b or"",["".join(sum(zip(a.split("G"),[*g,""]),()))for g in product(*["\\/."]*a.count("G"))]))
from itertools import*
E=enumerate

```

Attempt This Online!

-a massive 38 bytes thanks to @tsh.

Saved 20 bytes by switching to a flattened transposed string for input and output. Brute force solution. Explanation:

```
["".join(sum(zip(a.split("G"),[*g,""]),()))for g in product(*["\\/."]*a.count("G"))]

```

Generates all possible substitutions for `"G"` using

```
product(*["\\/."]*a.count("G"))

```

The cartesian product of `\/.` repeated for every occurence of `"G"`, where each combination is

```
"".join(sum(zip(a.split("G"),[*g,""]),()))

```

Manually mapped to the input string to replace the respective `"G"`'s.

```
lambda t,b=0:all([i%2^1and(s:=j)or s==j=="\\/"[b]and~(b:=b^1)or(s,j)[b]in".R"for i,j in E(t)])and t*b or""

```

The testing function is then mapped over the generated combinations, which checks for every column that either:

* `s==j=="\\/"[b]` the correct mirror for the given laser row `b` is in that column. `~(b:=b^1)` is used to switch the laser row
* `(s,j)[b]in".R"` the laser row in the column is `R` or `.`
* `or ""` outputs an empty list if above two tests fail
* `t*b` outputs the combination tested if the laser is on the bottom row for the last column, otherwise an empty list

`i%2^1and(s:=j)or` is used to generate the column pairs from the transposed flattened list by storing a value on every even iteration and testing on every odd iteration

Then `max()` is used to return a correct solution from the test results of all combinations

# Answer
> 2 votes
# Pip, ~~92~~ ~~75~~ 71 bytes

```
@FI{WG N({UQaQ"\/"@i&Ui|a@iN".R"}M<>a)&aX%i}M J(a^'GWV_)MCP:"\/."Ma@*'G

```

Try It Online!

-~~17~~ 21 bytes thanks to @DLosc

Port of my Python answer. I'm sure there are some further golfs that can be done. I could save a byte by outputting the list of all possible solutions as in @KevinCruijssen's answer. Explanation:

```
J(a^'GWV_)MCP:"\/."Ma@*'G

```

Generates all possible combinations using the cartesian product of `"\/."` by the number of `"G"` in the input

```
WG N({UQaQ"\/"@i&Ui|a@iN".R"}M<>a)&aX%i

```

Is the testing function that is mapped over all combinations. `WG` is required to reset the global variable `i`, which is used to store the laser row.

```
@FI

```

Finally filters out all falsy values from the output list, giving only the list of solutions. `@` outputs the first in the list.

# Answer
> 1 votes
# Python3, 350 bytes:

```
def f(b):
 q=[(0,0,[*map(list,b.replace('R','.').replace('G','.').split('\n'))])]
 while q:
  x,y,B=q.pop(0)
  if(x,y)==(1,len(B[0])):return B
  try:
   B=eval(str(B))
   if(V:=B[x][y])in'\\/':B[(X:=x+[-1,1][V=='\\'])][y]=V;q+=[(X,y+1,B)]
   else:j=eval(str(B));j[x][y]=(K:='\\/'[x]);j[(X:=x+[-1,1][K=='\\'])][y]=K;q+=[(x,y+1,B),(X,y+1,j)]
  except:1

```

Try it online!

# Answer
> 1 votes
# 05AB1E, ~~61~~ 50 bytes

```
…\/.I'G¢ãε'GsS.;}ʒ0U¶¡ε„\\º2äXèQiX_Uë„R.yXèå}Ā}PX*

```

Takes the input as a transposed multiline string. Outputs a list of all possible results (`R` remains `R`).

Try it online or verify all test cases.

**Explanation:**

Partially inspired by *@tsh*'s JavaScript's answer, so also checks pairs as:

```
0 → \
    \ → 1

    / → 0
1 → /

0 → . → 0
    *

0 → R → 0
    *

    *
1 → . → 1

    *
1 → R → 1

anything else: invalid

```

```
…\/.              # Push string "\/."
    I'G¢         '# Count how many "G" are in the input-string
        ã         # Get the cartesian product of "\/." with this count
         ε        # Map over each string:
              .;  #  Replace in the (implicit) input-string every first occurrence of
          'G     '#  character "G", one by one with
            sS    #  the characters in the current string
         }        # Close the map
ʒ                 # Filter this list of potential results with:
 0U               #  (Re)set `X` to 0
 ¶¡               #  Split the multiline string on newlines
   ε              #  Map over each pair:
    „\\           #   Push string "\\"
       º          #   Mirror it to "\\//"
        2ä        #   Split it into two parts: ["\\","//"]
          Xè      #   Get the 0-based `X`'th string in this pair
    Qi            #   If it's equal to the current pair we're mapping over:
      X_U         #    Invert `X` (0 becomes 1 and vice versa)
                  #    (and implicitly map to the implicit input-string)
     ë            #   Else:
         yXè      #    Get the 0-based `X`'th character from the current pair
      „R.   å     #    Check if this character is in string "R."
     }Ā           #   After the if-else: Python-style trutify the value
                  #   (0 remains 0; everything else becomes 1)
   }P             #  After the map: check if all are truthy by taking the product
     X*           #  Multiply it by `X` to check whether we've ended at the bottom row
                  # (after which the filtered results are output implicitly)

```

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


title: Convert an integer to IEEE 754 float

text:
# Question
Title: Convert an integer to IEEE 754 float
The task is simple: given a 32 bit integer, convert it to its floating point value as defined by the IEEE 754 (32-bit) standard.
To put it another way, interpret the integer as the bit-pattern of an IEEE binary32 single-precision float and output the numeric value it represents.

## IEEE 754 single precision

*Here is a converter for your reference.*

Here is how the format looks, from Wikipedia's excellent article:

The standard is similar to scientific notation.

The sign bit determines whether the output is negative or positive. If the bit is set, the number is negative otherwise it is positive.

The exponent bit determines the exponent (base 2), it's value is offset by 127. Therefore the exponent is \\$2^{n-127}\\$ where n is the integer representation of the exponent bits.

The mantissa defines a floating point number in the range \\$\[1,2)\\$. The way it represents the number is like binary, the most significant bit is \\$\frac 1 2\\$, the one to the right is \\$\frac 1 4\\$, the next one is \\$\frac 1 8\\$ and so on... A one by default is added to the value, implied by a non-zero exponent.

Now the final number is: $$\text{sign}\cdot 2^{\text{exponent}-127}\cdot \text{mantissa}$$

## Test cases

```
1078523331 ->   3.1400001049041748046875
1076719780 ->   2.71000003814697265625
1036831949 ->   0.100000001490116119384765625
3264511895 -> -74.24919891357421875
1056964608 ->   0.5
3205496832 ->  -0.5625
0          ->   0.0
2147483648 ->  -0.0 (or 0.0)

```

For this challenge assume that cases like `NaN` and `inf` are not going to be the inputs, and subnormals need not be handled (except for `0.0` which works like a subnormal, with the all-zero exponent implying a leading 0 bit for the all-zero mantissa.) You may output `0` for the case where the number represented is `-0`.

This is , so the shortest answer in bytes wins.

# Answer
# Python, 55 bytes

Correct as per original challenge description (always add 2^23 to mantissa) but not per IEEE.

```
lambda i:-(i>>31or-1)*2**((i>>23)%256-129)*(i/8**7%4+4)

```

Attempt This Online!

Direct bit twiddling, no casting.

# Python, 69 bytes

At last proper IEEE, I think (thanks @Neil).

```
lambda i:-(i>>31or-1)*2**((e:=i>>23&255)-126-(e>0))*(i/2**23%1+(e>0))

```

Attempt This Online!

# Python NumPy, 47 bytes

```
lambda i:int32(i).view("f4")
from numpy import*

```

Attempt This Online!

Boring use of builtin "view" or "reinterpret" casting. Note that we can save the "u" from `uint32` without issues.
> 18 votes

# Answer
# x86 32-bit machine code, 5 bytes

```
D9 44 24 04 C3

```

Try it online!

Following the `cdecl` calling convention, this takes the 32-bit integer on the stack and returns the result on the FPU register stack.

In assembly:

```
f:  fld DWORD PTR [esp + 4]
    ret

```

(`fld` does everything that is needed. The integer is placed below the return address on the stack, hence the `+ 4` to get to it.)
> 17 votes

# Answer
# Rust, 14 bytes

```
f32::from_bits

```

Not even reached the 30 byte min limit for posts
> 14 votes

# Answer
# C (GCC) without reliance on undefined behaviour, ~~41~~ 40 bytes

```
#define f(x)((union{int a;float b;})x).b

```

Attempt This Online!

Type-punning through pointers does normally work, but the compiler is free to do strange optimisations which can stop it working. A union makes this explicit in ways the compiler understands. It can also potentially be evaluated at compile time instead of at run time.

Note that it's best practise in C/C++ to use parentheses around the input value to a function-like macro and around the result, so you don't get unwanted interactions with precedence rules if this is used in a more complex statement. This would add 4 extra bytes to the total. For the tests defined in the question, we don't need this.

(Thanks @ceilingcat for spotting an unneeded space.)
> 9 votes

# Answer
# C++ (GCC / Clang / MSVC), 39 bytes

```
#define f(x)__builtin_bit_cast(float,x)

```

Try it online!
> 8 votes

# Answer
# Factor, 10 bytes

```
bits>float

```

Try it online!
> 7 votes

# Answer
# C (gcc), ~~36~~ ~~34~~ ~~30~~ 23 bytes

```
#define f(x)*(float*)&x

```

Try it online!

-2 thanks to m90

-4 thanks to Digital Trauma and mousetail

-7 thanks to jdt

Unsafe code go brr

```
#define f(x)*(float*)&x // Macrotaking an int, returning a float
#define f(x)            // Boilerplate
                     &x   // Pointer to the input
             (float*)     // Reinterpret it as a pointer to a float instead of an int
            *             // Get the value at that pointer, now a float

```
> 6 votes

# Answer
# JavaScript (ES6), 50 bytes

*-16 bytes (!) thanks to @Neil*

```
n=>new Float32Array(new Int32Array([n]).buffer)[0]

```

Try it online!
> 6 votes

# Answer
# Java, 21 bytes

```
Float::intBitsToFloat

```

Attempt This Online!

Builtin :P
> 6 votes

# Answer
# Charcoal, 45 bytes

```
Ｎθ≔Ｘ²¦²³η≔﹪÷θη²⁵⁶ζＩ∧ζ××⁺﹪θηηＸ²⁻ζ¹⁵⁰∨‹θＸ²¦³¹±¹

```

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

```
Ｎθ

```

Input the integer.

```
≔Ｘ²¦²³η

```

Calculate `2²³` as it gets used often enough to make it worthwhile. (It was originally only used twice but it was still worthwhile then. I then golfed a byte off by introducing a third use, which also avoided the use of `Incremented` which is buggy on TIO, otherwise I would have had to have used ATO instead.)

```
≔﹪÷θη²⁵⁶ζ

```

Extract the exponent. This is needed because an exponent of `0` needs to be special-cased. (Normally this results in a subnormal, but fortunately the only subnormals that we need to support are `0` and `-0`.)

```
Ｉ∧ζ××

```

If the exponent is zero, output zero, otherwise output the product of...

```
⁺﹪θηη

```

... the bottom `23` bits of the input integer, with a `1` bit prepended, ...

```
Ｘ²⁻ζ¹⁵⁰

```

... 2 to the power of the exponent, adjusted by `150` instead of `127` to shift the mantissa bits by `23`, and...

```
∨‹θＸ²¦³¹±¹

```

... the sign bit.
> 6 votes

# Answer
# ARM Thumb machine code, 2 bytes

`arm-none-eabi-g++` defaults to `-mfloat-abi=soft`, so `float` is passed/returned in general-purpose integer registers. (Godbolt)

ARM's standard calling convention passes the first arg in `r0`, which is also the return-value register. So all we need to do is return with `bx lr` (2 bytes).

```
// float f(int)
  // machine code hex        // assembly
  70 47                      bx lr

```

**The same trick can work for any ISA if you can justify a custom calling convention**. Normally that's fine, but on machines that use IEEE754 FP the challenge reduces to type-punning, and a calling convention that trivializes it is less interesting. e.g. for x86, you could normally justify taking an integer arg in XMM0, which is where you'd want a scalar `float`. (Tips for golfing in x86/x64 machine code)

## x86-64 machine code, with custom calling convention, 1 byte

**1-byte `c3 ret` for x86-64.**

Another justification could be that we take the input by reference and update in-place. Like C `void f(void*p){}` \- mutate the pointed-to `int` object from `int` to `float`, which is a no-op in asm.

(As a C function, that wouldn't make it well-defined to point a `float*` at an `int`, still a strict-aliasing violation. It might make it work in practice if it couldn't be inlined, forcing the compiler to keep its hands off. But this is a machine code answer. Obviously in real asm you'd never call this, it doesn't do anything.)

## x86-64 machine code with AMD64 System V calling convention, 5 bytes

It's the same length as a `call` instruction, making it pointless not to inline, but whatever. :/

```
   66 0f 6e c7             movd   xmm0,edi
   c3                      ret

```

AVX `vmovd xmm0,edi` is the same 4-byte length.

### x86 with custom 3DNow! calling convention, 4 bytes

Did anyone ever use the low element of an mm register for scalar float with 3DNow!, like how SSE/SSE2 use the bottom of an `xmm` register for scalar float/double? Possible, although there aren't scalar 3DNow! instructions like SSE `addss`, only packed float like `pfadd`. So you might get slowdown from subnormals in the high half. Still it's plausible.

```
# int arg in EDI,  float return value in MM0
    0f 6e c7                movd   mm0,edi
    c3                      ret

```
> 6 votes

# Answer
# Python, 55 bytes

```
lambda n:unpack('f',pack('I',n))[0]
from struct import*

```

Attempt This Online!
> 5 votes

# Answer
# Python, ~~69~~ ~~67~~ 65 bytes

```
lambda x:((x&8388607)/2**23+1)*2**((x>>23&255)-127)*(1-(x>>30&2))

```

Attempt This Online!
> 3 votes

# Answer
# Ruby, 29 bytes

Same technique as solid.py's Python answer.

```
->n{[n].pack(?I).unpack1(?f)}

```

Attempt This Online!
> 3 votes

# Answer
# Go, 29 bytes

```
import."math"
Float32frombits

```

Attempt This Online!

wow builtins
> 3 votes

# Answer
# PARI/GP, 53 bytes

```
n->(1-n>>31*2)*if(e=n>>23%256,(1+n/2^23%1.)<<(e-127))

```

Attempt This Online!
> 3 votes

# Answer
# C++ (GCC), 30 bytes

```
[](int x){return*(float*)&x;};

```

This is just Seggan's C answer using C++11's lambda syntax instead of a named function.
> 2 votes

# Answer
# MATL, 7 bytes

```
7Y%10Z%

```

Try it at MATL online! Or verify all test cases.

### Code explanation

```
      % Implicit input: number in 'double' data type
7Y%   % Cast to 'uint32'
10Z%  % Convert to 'single' without changing underlying data
      % Implicit display

```
> 2 votes

# Answer
# J-uby, 27 bytes

Port of my Ruby answer.

```
-[I]|~:pack&?I|~:unpack1&?f

```

Attempt This Online!

## Explanation

```
  -[I] |            # Construct an array with one element (the input), then
  ~:pack & ?I |     # pack it into a binary string
  ~:unpack1 & ?f |  # unpack it into a float

```
> 1 votes

# Answer
# C# (.NET Core 6), 30 bytes

```
BitConverter.Int32BitsToSingle

```

.NET Fiddle!
> 1 votes

# Answer
# JavaScript (Node.js), 48 bytes

```
f=x=>x<0?-f(x^1<<31):x>>24?f(x-2**23)*2:x/2**149

```

Try it online!

No cast
> 1 votes

---
Tags: code-golf, conversion, floating-point
---


# Question
Title: Generate number set with conditions using n numbers
Generate \\$T=\\{T\_1,...,T\_x\\}\\$, the minimum number of \\$k\\$-length subsets of \\$\\{1,...,n\\}\\$ such that every \\$v\\$-length subset of \\$\\{1,...,n\\}\\$ is a subset of some set in \\$T\\$

1. Here, \\$n \> k \> v\\$ and \\$v \ge 2\\$
2. Any number can appear only once in 1 set
3. Order of numbers is not important

Answer with code & explanation

## Test Cases

\\$(n,k,v) \to output \\$

```
(4, 3, 2)  ->  {1  2  3}
               {1  2  4}
               {1  3  4}

(10, 6, 3) ->  {1  2  3  4  5  7}
               {2  3  4  5  6  8}
               {3  4  5  6  7  9}
               {4  5  6  7  8 10}
               {1  5  6  7  8  9}
               {2  6  7  8  9 10}
               {1  3  7  8  9 10}
               {1  2  4  8  9 10}
               {1  2  3  5  9 10}
               {1  2  3  4  6 10}

```

# Answer
# Jelly, 15 bytes

```
œcŒPṚœc€⁵ẎQLƲÞṪ

```

A full program that accepts alphabet size (n), block size (k), and subset size (v) and prints a minimum covering design.

**Try it online!**

### How?

Naive brute-force, and about as inefficient as possible!

```
œcŒPṚœc€⁵ẎQLƲÞṪ - Main Link: n, k
œc              - k-combinations of [1..n] without repeats
  ŒP            - powerset
    Ṛ           - reverse (to be from longest to shortest)
             Þ  - (stable) sort (these proposed solutions) by:
            Ʋ   -   last four links as a monad:
        ⁵       -     with right argument = third program argument (v)
       €        -       for each k-tuple in the proposed solution:
     œc         -         v-combinations of the k-tuple
         Ẏ      -     tighten to a list of the covered v-tuples
          Q     -     deduplicate
           L    -     length -> number of distinct v-tuples covered
              Ṫ - tail -> i.e. (one of) the shortest valid proposed solution(s)
                - implicit print

```

---

#### Aside:

A greedy method of adding the lexicographically first unused block that covers the most so far uncovered subsets gets an optimal covering design *sometimes* and a fairly good alternative (slightly larger number of blocks) other times. Using other orderings (than lexicographic) with the same selection criteria will find optimal coving designs *sometimes* too. See New Constructions for Covering Designs (Daniel M. Gordon, Greg Kuperberg, Oren Patashnik)

This Python code does this with the lexicographic ordering - it gets a different, optimal solution for `n=10 k=6 v=3` (also 10 blocks), but a non-optimal one for (for example) `n=6 k=4 v=3` (one too many blocks).
> 4 votes

# Answer
# Vyxal, 14 bytes

```
ɾḋṗṘµ⁰vḋÞfUL;t

```

Try it Online!

Basically a port of Jelly, aka extremely slow.

Explanation coming soon.
> 3 votes

# Answer
# JavaScript (ES10), 188 bytes

Another brute-force solution that is unlikely to solve the second test case before the heat death of the universe.

Results are 0-indexed.

```
(n,k,v)=>(g=(v,i=n,a=[])=>i--?g(v,i,a).concat(g(v-1,i,[i,...a])):v?[]:[a],F=s=>s.find(c=>g(v).every(b=>c.some(a=>b.every(v=>a.includes(v)))))||F(s.flatMap(a=>g(k).map(b=>[...a,b]))))([[]])

```

Try it online!

## Commented

### Helper function

\\$g\\$ is a helper function that, given \\$v\\$, returns the list of all subsets of \\$\[0\dots n-1\]\\$ of length \\$v\\$. (Note that it is meant to be defined in the scope of the main function so that \\$n\\$ is known.)

```
g = (                   // g is a recursive function taking:
  v,                    //   v = expected length
  i = n,                //   i = counter, initialized to n
  a = []                //   a[] = current subset
) =>                    //
  i-- ?                 // decrement i; if it was not zero:
    g(                  //   do a recursive call where
      v, i, a           //     nothing is changed
    )                   //
    .concat(            //   append the result of
      g(                //   another recursive call where
        v - 1,          //     v is decremented
        i,              //     and
        [i, ...a]       //     i is inserted at the beginning of a[]
      )                 //
    )                   //
  :                     // else:
    v ? []              //   ignore this subset if its length is not v
      : [a]             //   otherwise, append it to the output list

```

### Main function

```
(n, k, v) => (          // f is the main function, taking n, k, v
  F =                   // F is a recursive function taking a list of
  s =>                  // lists of k-subsets
  s.find(c =>           // is there a list c[] in s[] satisfying ...
    g(v)                //   build all v-subsets
    .every(b =>         //   for each v-subset b[]:
      c.some(a =>       //     is there some k-subset a[] in c[] ...
        b.every(v =>    //       such that each value v in b[] ...
          a.includes(v) //         can be found in a[]?
        )               //       end of every()
      )                 //     end of some()
    )                   //   end of every()
  )                     // end of find()
  ||                    // if no solution was found:
    F(                  //   do a recursive call:
      s.flatMap(a =>    //     for each entry a[] in s[]:
        g(k)            //       build all k-subsets
        .map(b =>       //       for each k-subset b[]:
          [...a, b]     //         append b[] to a[]
        )               //       end of map()
      )                 //     end of flatMap()
    )                   //   end of recursive call
)([[]])                 // initial call to F with a single empty list

```
> 3 votes

# Answer
# Python, ~~168~~ 165 bytes

```
from itertools import*
def f(n,k,v):
 c,r,i=combinations,range(n),0
 while i:=i+1:
  for t in c(c(r,k),i):
   if not{*c(r,v)}-{*chain(*[c(s,v)for s in t])}:return t
```

Attempt This Online!

## Explanation

A brute-force solution. It iterates through all possible sizes of output sets \\$i=1,2,\ldots\\$, then checks the condition on each, and returns the first set of sets that meets the condition.

---

-3 bytes from @Steffan for extraneous parens
> 2 votes

# Answer
# JavaScript (Node.js), 173 bytes

```
(n,k,v)=>(h=(e,...z)=>(g=(k,m=n,z=[])=>m--?[...g(k,m,z),...g(~-k,m,[m,...z])]:k?[]:[z])(v).every(i=>e.join`
`.match(i.join`,(.*,)?`))?e:h(...z,...g(k).map(x=>[...e,x])))([])

```

Try it online!

```
(n,k,v)=>(
  h=(e,...z)=> // Take first
    g(v).every( // For each n choose v
      i=>e
        .join`\n` // Arrays separated by newline
                  // which won't match `.`
        .match(i.join`,(.*,)?`))?
                  // Match at least one line
        e:h(...z,...g(k).map(x=>[...e,x]))
            // If one fail then append another and throw to end
)
([]) // Starts with nothing

```

See Arnauld's answer for explanation of `g`
> 0 votes

---
Tags: code-golf, number, combinatorics, open-ended-function
---


title: CGAC2022 Day 14: Chimney cleaning

text:
# Question
Title: CGAC2022 Day 14: Chimney cleaning
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

As we all know, Santa comes down the chimney to deliver presents to good kids. But chimneys are normally full of smoke, and the Elves are worried about Santa's health. So they decide to blow the smoke out using an electronic air blower.

A chimney is modeled as a rectangular grid. The number in each cell represents the amount of smoke in the region. The left and right sides are walls, the top is open, and the air blower is blowing wind from the bottom.

```
||========||
||  |99|  ||
||--+--+--||
||  |  |24||
||--+--+--||
||36|  |12||
||--+--+--||
||  |  |  ||
||--+--+--||
||  |50|  ||
||^^^^^^^^||

```

Every second, the following happens in order. At any step, the smoke that goes outside of the chimney through the top is excluded from simulation.

1. The smoke is blown up one cell upwards.
2. The smoke diffuses to adjacent (4-way) cells (including outside).
    * Let's say a cell contains `n` amount of smoke. Then, for each available direction, exactly `floor(n/5)` amount of smoke moves in that direction.

Given the initial state above, smoke will move and diffuse as follows:

```
After step 1:
||========||
||  |  |24||
||--+--+--||
||36|  |12||
||--+--+--||
||  |  |  ||
||--+--+--||
||  |50|  ||
||--+--+--||
||  |  |  ||
||^^^^^^^^||

After step 2: (1 second passed)
||========||
||7 |4 |14||
||--+--+--||
||15|9 |10||
||--+--+--||
||7 |10|2 ||
||--+--+--||
||10|10|10||
||--+--+--||
||  |10|  ||
||^^^^^^^^||

2 seconds passed:
||========||
||8 |12|5 ||
||--+--+--||
||11|6 |8 ||
||--+--+--||
||7 |10|6 ||
||--+--+--||
||4 |4 |4 ||
||--+--+--||
||  |2 |  ||
||^^^^^^^^||

5 seconds passed:
||========||
||5 |1 |5 ||
||--+--+--||
||1 |4 |1 ||
||--+--+--||
||  |  |  ||
||--+--+--||
||  |  |  ||
||--+--+--||
||  |  |  ||
||^^^^^^^^||

```

This chimney is completely clear of smoke after 7 seconds.

## Task

Given a 2D grid of non-negative integers which represents the current state of smoke in the chimney, simulate the chimney as specified above and output the state 1 second later. You may assume that the chimney is at least 2 units wide and 2 units tall.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
[[0, 99, 0], [0, 0, 24], [36, 0, 12], [0, 0, 0], [0, 50, 0]]
-> [[7, 4, 14], [15, 9, 10], [7, 10, 2], [10, 10, 10], [0, 10, 0]]
-> [[8, 12, 5], [11, 6, 8], [7, 10, 6], [4, 4, 4], [0, 2, 0]]
-> [[7, 7, 7], [8, 5, 6], [5, 6, 5], [0, 2, 0], [0, 0, 0]]
-> [[7, 4, 5], [4, 5, 4], [1, 3, 1], [0, 0, 0], [0, 0, 0]]
-> [[5, 1, 5], [1, 4, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
-> [[1, 4, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
-> [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

```

# Answer
> 3 votes
# Python3, 301 bytes:

```
E=enumerate
def f(b):
 while any(map(any,b)):
  T=[]
  for x,r in E(b):
   for y,c in E(r):
    b[x][y]=0;p=x-1
    if x:
     b[p][y]=c
     for X,Y in(0,1),(-1,0),(1,0),(0,-1):
      K=0<=y+Y<len(b[0]);b[p][y]-=c//5*K
      if-1<p+X<len(b):T+=K*[(p+X,y+Y,c//5)]
  for x,y,v in T:b[x][y]+=v
  yield b

```

Try it online!

# Answer
> 3 votes
# , 71 61 58 bytes

```
0(1}.$$,+[:(+/-1&#.)5<.@%~,*1=[:|@-/~$j./@#:i.@#@,)@,0,~}.

```

Try it online!

# Answer
> 2 votes
# JavaScript (Node.js), 108 bytes

```
a=>a.map((r,y)=>r.map((c,x)=>(g=c=>p+2&&c/5*(p-y<3)+c%5*!p--+g((R=a[y-~(p>1)])?R[x+p%2]??R[x]:0)|0)(c,p=3)))

```

Attempt This Online!

For cell (x, y), the value after function is:

```
sum(
  floor(a[x,y]/5) only if (y is not 0),
  floor(a[x,y+1]/5),
  floor(a[x-1,y+1]/5),
  floor(a[x+1,y+1]/5),
  floor(a[x,y+2]/5),
  a[x,y+1] mod 5,
  floor(a[x,y+1]/5) only if (x is one of edge),
)

```

# Answer
> 2 votes
# Pip, ~~125~~ 129 bytes

```
@<($+(({(FL1ZGc*l)RA_bMS[a-1;a+1;a+c<c*l&a+c|a;a-c>=0&a-c|a]}MU{[a;b//5;h:#\a+1]}ME(k:WV(@>aAL2ZG(l:#@a))))AE(_-4*(_//5)Mk))UWh)

```

Try It Online!

I feel like there should be a much neater and golfier way of doing this in pip, but I couldn't figure it out

Edit: forgot to delete the temporary last row

# Answer
> 1 votes
# Charcoal, ~~46~~ 42 bytes

```
ＩΦＥ⊞ＯθＥ⌊θ⁰Ｅι⁺λΣＥθΣＥν∧⁼¹⁺↔⁻κξ↔⁻μρ⁻÷∧ξπ⁵÷λ⁵κ

```

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

```
        θ                                   Input array
       ⌊                                    Minimum (any) row
      Ｅ                                     Map over cells
         ⁰                                  Zero
   ⊞Ｏ                                       Push to
     θ                                      Input array
  Ｅ                                         Map over rows
           ι                                Current row
          Ｅ                                 Map over cells
             λ                              Current value
            ⁺                               Plus
                θ                           Input array
               Ｅ                            Map over rows
                   ν                        Inner row
                  Ｅ                         Map over cells
                      ¹                     Literal integer `1`
                     ⁼                      Equals
                          κ                 Outer row index
                         ⁻                  Minus
                           ξ                Inner row index
                        ↔                   Absolute value
                       ⁺                    Plus
                              μ             Outer cell index
                             ⁻              Minus
                               ρ            Inner cell index
                            ↔               Absolute value
                    ∧                       Logical And
                                   ξ        Inner row index
                                  ∧         Logical And
                                    π       Inner cell value
                                 ÷          Integer divided by
                                     ⁵      Literal integer `5`
                                ⁻           Minus
                                       λ    Outer cell value
                                      ÷     Integer divided by
                                        ⁵   Literal integer `5`
                 Σ                          Take the sum
              Σ                             Take the sum
 Φ                                          Filtered where
                                         κ  Row index is not zero
Ｉ                                           Cast to string
                                            Implicitly print

```

For instance, in the example of `[[[0, 99, 0], [0, 0, 24], [36, 0, 12], [0, 0, 0], [0, 50, 0]]]`, when the outer loop is processing the `24` and the inner loop is processing the `12`, the cells are found to be adjacent, so `12/5=2` is diffused into the outer cell but `24/5=4` is diffused out, while when the inner loop is processing the two zero cells also adjacent to the `24` there is nothing to diffuse in while `4` still diffuses out each time. This results in a net total of `24+2-4+0-4+0-4=14` in that cell.

# Answer
> 1 votes
# JavaScript (ES2020), 129 bytes

```
m=>[...m,m[0].fill(0)].map((r,y,m)=>r.map((v,x)=>[-1,s=0,1,2].map(d=>s-=1/(V=m[y+d%2]?.[x+~-d%2])?~(V/5)-~(v/5):0)|v+s)).slice(1)

```

Attempt This Online!

# Answer
> 1 votes
# Python3 + scipy, 173 bytes (broken)

To be clearest, this solution doesn't *exactly* work, but its so close to working and uses a different method than the other answers now for potentially a big byte savings, so I decided to post it to see if someone can get inspired to get it over the line.

```
from scipy.signal import convolve2d as c
import numpy as n
g=lambda i:c(n.vstack([[0,0,0],i[1:],[0,0,0]]),[[0,1/5,0],[1/5,1/5,1/5],[0,1/5,0]],'same','symm')[1:].astype(int)

```

Run online at onecompiler.com

### Output

Given the first test case:

```
[[ 0 99  0]
 [ 0  0 24]
 [36  0 12]
 [ 0  0  0]
 [ 0 50  0]]

```

This outputs:

```
[[ 7  4 12]
 [14  9  9]
 [ 7 10  2]
 [10 10 10]
[ 0 10  0]]

```

Instead of the expected:

```
[[ 7  4 14]
 [15  9 10]
 [ 7 10  2]
 [10 10 10]
 [ 0 10  0]]

```

### Explained

```
import scipy
import scipy.signal
import numpy as np
# We can solve this with matrix convolutions and row shifts in fewer operations (and hopefully less bytes)
# than iteration.
def g_ungolfed(i):
    # 1. pad arrays with 0-rows on both y-sides
    ## Slicing the first row off lets smoke 'escape' out of the top during the initial shift
    ## Padding the first row with a temp row lets smoke 'escape' out the top during dispersion.
    ## Padding the last row lets us shift the smoke up 1 row later on
    i_padded = np.vstack([[0,0,0],i[1:], [0,0,0]])
    print("padded", i_padded)
    # 2. Run the convolution to do the smoke pattern
    ## define a convolution kernel to follow the 20% smoke dispersal pattern --
    k = [
        [0,1/5,0],
        [1/5,1/5,1/5],
        [0,1/5,0],
    ]
    ## mode="same" keeps the output matrix in the same dimensions as the i_padded input
    ## boundary="symm" handles the correct behavior for the smoke-fill pattern on the left-right boundaries of the chimney
    # The floor(n/5) integer division isn't respected here which is why the results are wrong.
    dispersed = scipy.signal.convolve2d(i_padded, k, mode="same", boundary="symm")
    # 3. Slice off the temp top row
    print("intermediate", dispersed)
    dispersed_shifted = dispersed[1:]
    # 4. cast the results to int
    return dispersed_shifted.astype(int)

```

# Answer
> 1 votes
# Python 3, 149 bytes

```
lambda m:[o:=[[0]*len(m.pop(0))],[[n[1]%5+sum(i//5for i in n)for n in zip(x,y,y[1:]+[y[-1]],[y[0]]+y[:-1],z)]for x,y,z in zip(o+m,m+o,m[1:]+o+o)]][1]

```

Try it online!

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