title: Mirrored Digital Clock

text:
# Question
Title: Mirrored Digital Clock
Many digital clocks display the time using simplified digits comprised of only seven different lights that are either on or off:

When mirrored horizontally, the digits `018` don't change because they are symmetrical. Also, the digits `2` and `5` get swapped, `2` becoming `5` and vice versa. All the other digits become invalid when mirrored.

Thus, given a 24-hour digital clock, there are many clock readings such that the mirrored image of the digital display is also a valid clock reading. Your task is to output all such clock readings along with the mirrored readings.

For example, `22:21` becomes `15:55`, and `00:15` becomes `21:00`. On the other hand, `12:34` or `16:27` are no longer valid when mirrored (digits `34679` become invalid), and neither are `22:22` or `18:21`, because, as there are only 24 hours in a day and 60 minutes in an hour, no sane clock would display `55:55` or `12:81`.

### Task

Write a program or a function that takes no input and outputs all valid pairs in ascending order as shown below:

```
00:00 - 00:00
00:01 - 10:00
00:05 - 20:00
00:10 - 01:00
00:11 - 11:00
00:15 - 21:00
00:20 - 05:00
00:21 - 15:00
00:50 - 02:00
00:51 - 12:00
00:55 - 22:00
01:00 - 00:10
01:01 - 10:10
01:05 - 20:10
01:10 - 01:10
01:11 - 11:10
01:15 - 21:10
01:20 - 05:10
01:21 - 15:10
01:50 - 02:10
01:51 - 12:10
01:55 - 22:10
02:00 - 00:50
02:01 - 10:50
02:05 - 20:50
02:10 - 01:50
02:11 - 11:50
02:15 - 21:50
02:20 - 05:50
02:21 - 15:50
02:50 - 02:50
02:51 - 12:50
02:55 - 22:50
05:00 - 00:20
05:01 - 10:20
05:05 - 20:20
05:10 - 01:20
05:11 - 11:20
05:15 - 21:20
05:20 - 05:20
05:21 - 15:20
05:50 - 02:20
05:51 - 12:20
05:55 - 22:20
10:00 - 00:01
10:01 - 10:01
10:05 - 20:01
10:10 - 01:01
10:11 - 11:01
10:15 - 21:01
10:20 - 05:01
10:21 - 15:01
10:50 - 02:01
10:51 - 12:01
10:55 - 22:01
11:00 - 00:11
11:01 - 10:11
11:05 - 20:11
11:10 - 01:11
11:11 - 11:11
11:15 - 21:11
11:20 - 05:11
11:21 - 15:11
11:50 - 02:11
11:51 - 12:11
11:55 - 22:11
12:00 - 00:51
12:01 - 10:51
12:05 - 20:51
12:10 - 01:51
12:11 - 11:51
12:15 - 21:51
12:20 - 05:51
12:21 - 15:51
12:50 - 02:51
12:51 - 12:51
12:55 - 22:51
15:00 - 00:21
15:01 - 10:21
15:05 - 20:21
15:10 - 01:21
15:11 - 11:21
15:15 - 21:21
15:20 - 05:21
15:21 - 15:21
15:50 - 02:21
15:51 - 12:21
15:55 - 22:21
20:00 - 00:05
20:01 - 10:05
20:05 - 20:05
20:10 - 01:05
20:11 - 11:05
20:15 - 21:05
20:20 - 05:05
20:21 - 15:05
20:50 - 02:05
20:51 - 12:05
20:55 - 22:05
21:00 - 00:15
21:01 - 10:15
21:05 - 20:15
21:10 - 01:15
21:11 - 11:15
21:15 - 21:15
21:20 - 05:15
21:21 - 15:15
21:50 - 02:15
21:51 - 12:15
21:55 - 22:15
22:00 - 00:55
22:01 - 10:55
22:05 - 20:55
22:10 - 01:55
22:11 - 11:55
22:15 - 21:55
22:20 - 05:55
22:21 - 15:55
22:50 - 02:55
22:51 - 12:55
22:55 - 22:55

```

A trailing or a leading newline is allowed. Having a few spaces directly before a linefeed is also allowed. The times must be in format `hh:mm`, padded with zeros when necessary.

This is , so the shortest answer in bytes wins. As usual, standard loopholes are disallowed.

# Answer
> 2 votes
# 05AB1E, 34 bytes

```
0125DâDâεÂ5nÂ‡í)}ʒ€н25‹P}':ý… - ý»

```

Try it online!

**Explanation**

```
0125                                # push "0125"
    Dâ                              # cartesian product with itself
      Dâ                            # cartesian product with itself
        ε       }                   # apply to each
         Â                          # bifurcate
          5nÂ                       # push 25 bifurcated
             ‡                      # transliterate
              í                     # reverse each
               )                    # wrap in a list
                 ʒ      }           # filter each on
                  €н                # head of each
                    25‹             # less than 25
                       P            # product
                         ':ý        # merge on ":"
                            … - ý   # merge on " - "
                                 »  # join on newlines

```

# Answer
> 6 votes
# Python 2, ~~187~~ ~~180~~ ~~178~~ 177 bytes

```
R=range(11)
for t in['0000111122201250125012'[j::11]+':'+'0001112255501501501015'[i::11]for i in R for j in R]:print t+' - '+''.join(map(dict(zip('0125:','0152:')).get,t))[::-1]

```

Try it online!

Thanks for +1 Kevin Cruijssen.

# Answer
> 5 votes
# APL (Dyalog Unicode), 84 bytesSBCS

Complete program outputting to STDOUT. Requires `⎕IO` (**I**ndex **O**rigin) to be `0` which is default on many systems.

```
{0::⋄∧/23 59≥⍎¨(':'≠t)⊆t←⌽'015xx2xx8x:'[⎕D⍳i←∊⍺':'⍵]:⎕←1↓⍕i'-'t}⌿1↓¨⍕¨100+0 60⊤⍳1440

```

Try it online!

`⍳1440` that many **ɩ**ntegers

`0 60⊤` convert to mixed-base ∞,60

`100+` add 100 (this pads the needed 0s)

`⍕¨` format (stringify) each

`1↓¨` drop the first character from each (this removes the leading 1s)

`{``}⌿` apply the following anonymous function column-wise ( is top hour,  is minute)

`0::` if any error happens, return nothing

try:

`'015xx2xx8x:'[``]` index this string with:

`∊⍺':'⍵` the **ϵ**nlisted (flattened) list of hour, colon, minute

`i←` stored in `i` (for **i**nput)

`⎕D⍳`**ɩ**ndices of each character in the list of **D**igits

reverse that

`t←` store as `t` (for **t**ime)

`(``)⊆` group runs where:

`':'≠t` colon differs from `t`

`⍎¨` execute (evaluate) each

`23 59≥` Boolean for each whether they are less than or equal to 23 and 59 respectively

`∧/` are both true?

`:` if so, then:

`⍕i'-'t` the formatted (space-separated) list of input, dash, time

`1↓` drop the first (space)

`⎕←` output to STDOUT

# Answer
> 4 votes
# Python 2, ~~279~~ ~~277~~ 255 bytes

```
for h in range(1440):
 q=[[[0,(a+"52")[(a=="2")+(a=="5")*2]][a in"01825"]for a in c]for c in[("%02d"%e)[::-1]for e in[h%60,h/60]]]
 if all(q[0]+q[1]):
	z=[int(''.join(j))for j in q]
	if(z[1]<60)*(z[0]<24):print"%02d:%02d - %02d:%02d"%(h/60,h%60,z[0],z[1])

```

Try it online!

# Credits

* 279 bytes reduced to 256 by dylnan.
* 256 bytes reduced to 255 by FlipTrack.

# Answer
> 4 votes
# Retina, 57 bytes

```

 -
+m`^.{3,9}$
0$&0¶1$&1¶2$&5¶5$&2
A`\b2?5
\b\d.
$&:
O`

```

Try it online! Explanation:

```

 -

```

Insert the separator.

```
+m`^.{3,9}$
0$&0¶1$&1¶2$&5¶5$&2

```

Generate all possible sets of four mirrored digits.

```
A`\b2?5

```

Delete those with illegal hours.

```
\b\d.
$&:

```

Insert the colons.

```
O`

```

Sort into order.

# Answer
> 3 votes
# Clean, ~~269~~ ... ~~172~~ 170 bytes

```
import StdEnv
?n=toChar n+'0'
$c|c<2=c=7-c
n=[0,1,2,5]
t=flatlines[u++[' - ':v]\\[u,v]<-[[map?[a,b,10,x,y],map?[$y,$x,10,$b,$a]]\\a<-n,b<-n,x<-n,y<-n]|['23:59']>=max u v]

```

Try it online!

Ungolfed:

```
import StdEnv
numeral n = toChar (n+48)
mirror 2 = 5
mirror 5 = 2
mirror c = c
digits = [0, 1, 2, 5]
times
    = flatlines [ // flatten with interspersed newlines
        original ++ [' - ' : reflection] // insert separator
        \\ // generate all pairs of times and their mirrored copies
        [original, reflection] <- [
            [map numeral [a, b, 10, x, y], map (numeral o mirror) [y, x, 10, b, a]]
            \\ // generate every combination of display digits
            a <- digits,
            b <- digits,
            x <- digits,
            y <- digits
            ]
        | ['23:59'] >= max original reflection // make sure both times actually exist
        ]

```

# Answer
> 2 votes
# Pyth, 48 bytes

```
Lj\:c2bjf!:T"5.:|25:"0mj" - ",ydyX_d`25)^"0125"4

```

Try it online!

Generates all possible combinations of `0125` and then manipulates them into the times. These are in the correct order because they are generated in lexicographic order. Finally, this filters out the extra invalid times by removing lines that match the regex `5.:` or `25:`. Sadly, it doesn't seem like compression works nicely on any of the strings that this program uses, unless I've made an error or oversight.

# Answer
> 2 votes
# Perl 5, 147 bytes

```
map{$h=0 x($_<10).$_;map{$_="0$_"if$_<10;say"$h:$_ - $q:$i"if($i=reverse$h=~y/25/52/r)<60&&"$h$_"!~/[34679]/&&($q=reverse y/25/52/r)<24}0..59}0..23

```

Try it online!

# Answer
> 2 votes
# Japt v2 (+ `-R`), 51 bytes

```
G²Çs4 ùT4 i':2Ã®+" - "+Zw r\d_^Z>1})r3,5Ãkf/5.|25):

```

Test it online!

### Explanation

```
G²Ç   s4 ùT4 i':2Ã ®   +" - "+Zw r\d_  ^Z>1})r3,5Ã kf/5.|25):
G²oZ{Zs4 ùT4 i':2} mZ{Z+" - "+Zw r\dZ{Z^Z>1})r3,5} kf/5.|25):/   Ungolfed

G²              Calculate 16**2, or 256.
  oZ{       }   Create the range [0...256) and map each integer Z to:
Zs4               Convert Z to a base-4 string.  [0, 1, 2, 3, 10, ..., 3331, 3332, 3333]
    ùT4           Pad-left with 0's to length 4. [0000, 0001, 0002, ..., 3331, 3332, 3333]
        i':2      Insert a colon at index 2.     [00:00, 00:01, 00:02, ..., 33:31, 33:32, 33:33]

mZ{      }      Map each string Z in the resulting array to:
Zw r\dZ{     }    Reverse Z, and replace each digit Z' with
        Z^Z>1       Z' xor'd with (Z>1). This turns 2 to 3 and vice versa.
                  We now have [00:00, 10:00, 30:00, 20:00, 01:00, ..., 12:22, 32:22, 22:22]
Z+" - "+          Append this to Z with " - " in between. This gives
                    [00:00 - 00:00, 00:01 - 10:00, 00:02 - 30:00, ..., 33:32 - 32:22, 33:33 - 22:22]
r3,5              Replace all 3s in the result with 5s.
                    [00:00 - 00:00, 00:01 - 10:00, 00:02 - 50:00, ..., 55:52 - 52:22, 55:55 - 22:22]

k               Remove all results that
 f/5.|25):/       match the regex /(5.|25):/g. This removes times with impossible hours.

                Implicit: output result of last expression, joined with newlines (-R)

```

# Answer
> 1 votes
# JavaScript (ES6), 142 bytes

```
f=(n=0)=>n<176?(s=(g=n=>d[n>>2]+d[n&3])(n%4*4|n/4&3,d='0152')+':'+g(n>>6|(n/4&12)),s<'25'?g(n>>4,d='0125')+`:${g(n&15)} - ${s}
`:'')+f(n+1):''

```

Try it online!

# Answer
> 1 votes
# Charcoal, 59 bytes

```
Ｆ012Ｆ0125Ｆ0125Ｆ015¿›‹⁺ικ25⁼⁺λμ25«ικ:λμ - Ｆ⟦μλ3κι⟧§015::2Ｉν⸿

```

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

```
Ｆ012Ｆ0125Ｆ0125Ｆ015

```

Create four nested loops for the unmirrored digits.

```
¿›‹⁺ικ25⁼⁺λμ25«

```

Check that neither the hours nor minutes is 25. (Mirroring the 25 minutes will result in 25 hours, so that's a no-go.)

```
ικ:λμ -

```

Print the unmirrored time.

```
Ｆ⟦μλ3κι⟧§015::2Ｉν⸿

```

Print the mirrored time by converting the reversed digits (or `3` for the colon) from string to integer and looking them up in a translation table.

Alternatively, also for 59 bytes:

```
Ｆ¹¹Ｆ¹⁶¿⁻¹¹κ¿⁻²﹪κ⁴«≔⟦÷ι⁴﹪ι⁴¦⁴÷κ⁴﹪κ⁴⟧θＦθ§0125:λ - Ｆ⮌θ§0152:λ⸿

```

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

```
Ｆ¹¹Ｆ¹⁶

```

Create loops for the hours and minutes.

```
¿⁻¹¹κ¿⁻²﹪κ⁴«

```

Exclude `25` and also any minutes ending in `2`.

```
≔⟦÷ι⁴﹪ι⁴¦⁴÷κ⁴﹪κ⁴⟧θ

```

Convert the hours and minutes to base 4.

```
Ｆθ§0125:λ

```

Print the digits looked up in a translation table.

```
 -

```

Print the separator.

```
Ｆ⮌θ§0152:λ⸿

```

Print the reversed digits looked up in a mirrored translation table.

# Answer
> 1 votes
# Jelly, ~~72~~ ~~66~~ ~~62~~ 55 bytes

```
®ṢiÐ€Uị®
“0152:”©ṢṖp`⁺ḣ176j€“:”µ;"Ç€⁾25ẇ$ÐṂœs€2j€“ - ”Y

```

Try it online!

Niladic program. I got the double product of `'0125'` idea from the 05AB1E answer by Emigna but the rest I did without consulting that since the languages diverge after that. There are probably opportunities for golfing, possibly by a lot.

**Explanation**

The program works as follows:

* Take all products of length four of the list of characters `'0125'` with `“0152:”©ṢṖp`⁺`. `©` copies the string `'0152:'` to the register for use later. `ṢṖ` sorts then pops the last element of the string → `'0125'`.  duplicates the product link.
* `ḣ176` removes any times with format `25xx` or `5xxx` (not valid hours).
* `j€“:”` joins each pair of digits with a `':'`. e.g. `['05'],['21']]``'05:12'`.
* `Ç€` applies the first link to each of these times. It finds the index of each character in the string `'0125:'` then for each of those indices gets the character in the string `'0152:'` and reverses it. This is the mirror operation (reversing and swapping `2`s and `5`s).
* `µ;"` concatenates the original time with the mirrored time → `'05:2115:20'`
* `⁾25ẇ$ÐṂ` filters out the times with the substring `'25'`. This catches any time pairs with mirrored half `25:xx` or `5x:xx`. *Note*: I don't know why the `$` is necessary. Perhaps someone could golf it out with the proper syntax but I'm not sure.
* Split each of these times into two halves (`œs€2`) then join them with the string `' - '` (`j€“ - ”`). `'05:2115:20'``'05:21 - 15:20'`.
* Finally, `Y` joins all the strings with a newline and everything is implicitly printed.

**Old versions**

62 bytes

```
i@€®ị“:0152”
“:0125”©Ḋp`⁺ḣ176j€“:”µ,"UÇ€$F€⁾25ẇ$ÐṂœs€2j€“ - ”Y

```

Try it online!

66 bytes

```
“0125”
i@€¢ị“0152”
UṚÇ€
Ñp`⁺ḣ176µ,"Ç€j€€“:”j€“ - ”¹⁾2 ẇ$ÐṂ⁾25ẇ$ÐṂY

```

Try it online!

72 bytes

```
⁾25
i@€¢µẋ@€¢ṙ"
Ṛµ;@""Ç€Ḣ€€
“0125”p`⁺j€“:”ḣ176µ,"Ç€j€“ - ”¹⁾2 ẇ$ÐṂÑẇ$ÐṂY

```

Try it online!

# Answer
> 1 votes
# C (gcc), ~~175~~ 174 bytes

One off thanks to @Steadybox.

```
char*p,s[14],*e;f(t){for(t=0;sprintf(p=s,"%02d:%02d -",t/100,t%100),t<2400;)if(t++%10^2&&!strpbrk(s,"346789")&&t%100^26){for(e=s+12;p<e;p++)*e--=*p^7*(*p>49&*p<58);puts(s);}}

```

Try it online!

# Answer
> 1 votes
# Befunge, 178 bytes

```
>0>:5g"7"`>v1\,+55<
v_^#`+87:+1_4>99p\ :99gg48 *-:55+/"0"+,55+%"0"+,":",\v
>$1+:55v v,," - "_^#-5g99,+"0"%+55,+"0"/+55:-*84gg99:<
v_@#!`+< >,\5^
 !"%*+,/4569RSTW
 *R4!+S5%/W9",T6

```

Try it online!

# Answer
> 1 votes
# Kotlin, ~~205~~ 207 bytes

```
(0..1439).map{"%02d : %02d".format(it/60,it%60)}.let{it.map{i->i to i.reversed().map{x->"25180:X52180:".let{it[it.indexOf(x)+7]}}.joinToString("")}.filter{(_,b)->it.contains(b)}.map{(a,b)->println("$a-$b")}}

```

## Beautified

```
    (0..1439)
        .map { "%02d : %02d".format(it / 60, it % 60) }              // Make the times
        .let { it.map {i->
                i to i.reversed().map {x->                         // Pair it with the reversed times
                    "25180:X52180:".let{ it[it.indexOf(x)+7] }     // - X means bad times are removed
                }.joinToString("")                                 // - Make the string
            }.filter {(_,b)-> it.contains(b) }                     // Remove the unpaired times
                .map { (a, b) -> println("$a - $b") }              // Print out the pairs
        }

```

## Test

```
fun main(args: Array<String>) {
    f()
}

fun f() =
(0..1439).map{"%02d:%02d".format(it/60,it%60)}.let{it.map{i->i to i.reversed().map{x->"25180:X52180:".let{it[it.indexOf(x)+7]}}.joinToString("")}.filter{(_,b)->it.contains(b)}.map{(a,b)->println("$a-$b")}}

```

## TIO

TryItOnline

## Edits

# Answer
> 1 votes
# Deadfish~, 9627 bytes

```
{iiiii}ddcc{i}c{d}cc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicc{i}c{d}cc{dddd}iic{iiii}ddcc{i}c{d}cic{dd}iiic{i}iiic{d}dddc{ii}dddcdc{i}c{d}cc{dddd}iic{iiii}ddcc{i}c{d}ciiiiic{dd}dc{i}iiic{d}dddc{ii}ddcddc{i}c{d}cc{dddd}iic{iiii}ddcc{i}c{d}icdc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicic{i}dc{d}cc{dddd}iic{iiii}ddcc{i}c{d}icc{dd}iiic{i}iiic{d}dddc{ii}dddcc{i}dc{d}cc{dddd}iic{iiii}ddcc{i}c{d}iciiiic{dd}dc{i}iiic{d}dddc{ii}ddcdc{i}dc{d}cc{dddd}iic{iiii}ddcc{i}c{d}iicddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciiiiiciiiiic{d}cc{dddd}iic{iiii}ddcc{i}c{d}iicdc{dd}iiic{i}iiic{d}dddc{ii}dddciiiiciiiiic{d}cc{dddd}iic{iiii}ddcc{i}cdddddcdddddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciic{i}ddc{d}cc{dddd}iic{iiii}ddcc{i}cdddddcddddc{dd}iiic{i}iiic{d}dddc{ii}dddcic{i}ddc{d}cc{dddd}iic{iiii}ddcc{i}cdddddcc{dd}dc{i}iiic{d}dddc{ii}ddcc{i}ddc{d}cc{dddd}iic{iiii}ddcic{i}dc{d}cc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicc{i}c{d}icdc{dddd}iic{iiii}ddcic{i}dc{d}cic{dd}iiic{i}iiic{d}dddc{ii}dddcdc{i}c{d}icdc{dddd}iic{iiii}ddcic{i}dc{d}ciiiiic{dd}dc{i}iiic{d}dddc{ii}ddcddc{i}c{d}icdc{dddd}iic{iiii}ddcic{i}dc{d}icdc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicic{i}dc{d}icdc{dddd}iic{iiii}ddcic{i}dc{d}icc{dd}iiic{i}iiic{d}dddc{ii}dddcc{i}dc{d}icdc{dddd}iic{iiii}ddcic{i}dc{d}iciiiic{dd}dc{i}iiic{d}dddc{ii}ddcdc{i}dc{d}icdc{dddd}iic{iiii}ddcic{i}dc{d}iicddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciiiiiciiiiic{d}icdc{dddd}iic{iiii}ddcic{i}dc{d}iicdc{dd}iiic{i}iiic{d}dddc{ii}dddciiiiciiiiic{d}icdc{dddd}iic{iiii}ddcic{i}dcdddddcdddddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciic{i}ddc{d}icdc{dddd}iic{iiii}ddcic{i}dcdddddcddddc{dd}iiic{i}iiic{d}dddc{ii}dddcic{i}ddc{d}icdc{dddd}iic{iiii}ddcic{i}dcdddddcc{dd}dc{i}iiic{d}dddc{ii}ddcc{i}ddc{d}icdc{dddd}iic{iiii}ddciic{i}ddc{d}cc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicc{i}cdddddcdddddc{dddd}iic{iiii}ddciic{i}ddc{d}cic{dd}iiic{i}iiic{d}dddc{ii}dddcdc{i}cdddddcdddddc{dddd}iic{iiii}ddciic{i}ddc{d}ciiiiic{dd}dc{i}iiic{d}dddc{ii}ddcddc{i}cdddddcdddddc{dddd}iic{iiii}ddciic{i}ddc{d}icdc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicic{i}dcdddddcdddddc{dddd}iic{iiii}ddciic{i}ddc{d}icc{dd}iiic{i}iiic{d}dddc{ii}dddcc{i}dcdddddcdddddc{dddd}iic{iiii}ddciic{i}ddc{d}iciiiic{dd}dc{i}iiic{d}dddc{ii}ddcdc{i}dcdddddcdddddc{dddd}iic{iiii}ddciic{i}ddc{d}iicddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciiiiiciiiiicdddddcdddddc{dddd}iic{iiii}ddciic{i}ddc{d}iicdc{dd}iiic{i}iiic{d}dddc{ii}dddciiiiciiiiicdddddcdddddc{dddd}iic{iiii}ddciic{i}ddcdddddcdddddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciic{i}ddcdddddcdddddc{dddd}iic{iiii}ddciic{i}ddcdddddcddddc{dd}iiic{i}iiic{d}dddc{ii}dddcic{i}ddcdddddcdddddc{dddd}iic{iiii}ddciic{i}ddcdddddcc{dd}dc{i}iiic{d}dddc{ii}ddcc{i}ddcdddddcdddddc{dddd}iic{iiii}ddciiiiiciiiiic{d}cc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicc{i}c{d}iicddc{dddd}iic{iiii}ddciiiiiciiiiic{d}cic{dd}iiic{i}iiic{d}dddc{ii}dddcdc{i}c{d}iicddc{dddd}iic{iiii}ddciiiiiciiiiic{d}ciiiiic{dd}dc{i}iiic{d}dddc{ii}ddcddc{i}c{d}iicddc{dddd}iic{iiii}ddciiiiiciiiiic{d}icdc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicic{i}dc{d}iicddc{dddd}iic{iiii}ddciiiiiciiiiic{d}icc{dd}iiic{i}iiic{d}dddc{ii}dddcc{i}dc{d}iicddc{dddd}iic{iiii}ddciiiiiciiiiic{d}iciiiic{dd}dc{i}iiic{d}dddc{ii}ddcdc{i}dc{d}iicddc{dddd}iic{iiii}ddciiiiiciiiiic{d}iicddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciiiiiciiiiic{d}iicddc{dddd}iic{iiii}ddciiiiiciiiiic{d}iicdc{dd}iiic{i}iiic{d}dddc{ii}dddciiiiciiiiic{d}iicddc{dddd}iic{iiii}ddciiiiiciiiiicdddddcdddddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciic{i}ddc{d}iicddc{dddd}iic{iiii}ddciiiiiciiiiicdddddcddddc{dd}iiic{i}iiic{d}dddc{ii}dddcic{i}ddc{d}iicddc{dddd}iic{iiii}ddciiiiiciiiiicdddddcc{dd}dc{i}iiic{d}dddc{ii}ddcc{i}ddc{d}iicddc{dddd}iic{iiii}dcdc{i}c{d}cc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicc{i}c{d}cic{dddd}ic{iiii}dcdc{i}c{d}cic{dd}iiic{i}iiic{d}dddc{ii}dddcdc{i}c{d}cic{dddd}ic{iiii}dcdc{i}c{d}ciiiiic{dd}dc{i}iiic{d}dddc{ii}ddcddc{i}c{d}cic{dddd}ic{iiii}dcdc{i}c{d}icdc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicic{i}dc{d}cic{dddd}ic{iiii}dcdc{i}c{d}icc{dd}iiic{i}iiic{d}dddc{ii}dddcc{i}dc{d}cic{dddd}ic{iiii}dcdc{i}c{d}iciiiic{dd}dc{i}iiic{d}dddc{ii}ddcdc{i}dc{d}cic{dddd}ic{iiii}dcdc{i}c{d}iicddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciiiiiciiiiic{d}cic{dddd}ic{iiii}dcdc{i}c{d}iicdc{dd}iiic{i}iiic{d}dddc{ii}dddciiiiciiiiic{d}cic{dddd}ic{iiii}dcdc{i}cdddddcdddddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciic{i}ddc{d}cic{dddd}ic{iiii}dcdc{i}cdddddcddddc{dd}iiic{i}iiic{d}dddc{ii}dddcic{i}ddc{d}cic{dddd}ic{iiii}dcdc{i}cdddddcc{dd}dc{i}iiic{d}dddc{ii}ddcc{i}ddc{d}cic{dddd}ic{iiii}dcc{i}dc{d}cc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicc{i}c{d}icc{dddd}ic{iiii}dcc{i}dc{d}cic{dd}iiic{i}iiic{d}dddc{ii}dddcdc{i}c{d}icc{dddd}ic{iiii}dcc{i}dc{d}ciiiiic{dd}dc{i}iiic{d}dddc{ii}ddcddc{i}c{d}icc{dddd}ic{iiii}dcc{i}dc{d}icdc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicic{i}dc{d}icc{dddd}ic{iiii}dcc{i}dc{d}icc{dd}iiic{i}iiic{d}dddc{ii}dddcc{i}dc{d}icc{dddd}ic{iiii}dcc{i}dc{d}iciiiic{dd}dc{i}iiic{d}dddc{ii}ddcdc{i}dc{d}icc{dddd}ic{iiii}dcc{i}dc{d}iicddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciiiiiciiiiic{d}icc{dddd}ic{iiii}dcc{i}dc{d}iicdc{dd}iiic{i}iiic{d}dddc{ii}dddciiiiciiiiic{d}icc{dddd}ic{iiii}dcc{i}dcdddddcdddddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciic{i}ddc{d}icc{dddd}ic{iiii}dcc{i}dcdddddcddddc{dd}iiic{i}iiic{d}dddc{ii}dddcic{i}ddc{d}icc{dddd}ic{iiii}dcc{i}dcdddddcc{dd}dc{i}iiic{d}dddc{ii}ddcc{i}ddc{d}icc{dddd}ic{iiii}dcic{i}ddc{d}cc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicc{i}cdddddcddddc{dddd}ic{iiii}dcic{i}ddc{d}cic{dd}iiic{i}iiic{d}dddc{ii}dddcdc{i}cdddddcddddc{dddd}ic{iiii}dcic{i}ddc{d}ciiiiic{dd}dc{i}iiic{d}dddc{ii}ddcddc{i}cdddddcddddc{dddd}ic{iiii}dcic{i}ddc{d}icdc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicic{i}dcdddddcddddc{dddd}ic{iiii}dcic{i}ddc{d}icc{dd}iiic{i}iiic{d}dddc{ii}dddcc{i}dcdddddcddddc{dddd}ic{iiii}dcic{i}ddc{d}iciiiic{dd}dc{i}iiic{d}dddc{ii}ddcdc{i}dcdddddcddddc{dddd}ic{iiii}dcic{i}ddc{d}iicddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciiiiiciiiiicdddddcddddc{dddd}ic{iiii}dcic{i}ddc{d}iicdc{dd}iiic{i}iiic{d}dddc{ii}dddciiiiciiiiicdddddcddddc{dddd}ic{iiii}dcic{i}ddcdddddcdddddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciic{i}ddcdddddcddddc{dddd}ic{iiii}dcic{i}ddcdddddcddddc{dd}iiic{i}iiic{d}dddc{ii}dddcic{i}ddcdddddcddddc{dddd}ic{iiii}dcic{i}ddcdddddcc{dd}dc{i}iiic{d}dddc{ii}ddcc{i}ddcdddddcddddc{dddd}ic{iiii}dciiiiciiiiic{d}cc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicc{i}c{d}iicdc{dddd}ic{iiii}dciiiiciiiiic{d}cic{dd}iiic{i}iiic{d}dddc{ii}dddcdc{i}c{d}iicdc{dddd}ic{iiii}dciiiiciiiiic{d}ciiiiic{dd}dc{i}iiic{d}dddc{ii}ddcddc{i}c{d}iicdc{dddd}ic{iiii}dciiiiciiiiic{d}icdc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicic{i}dc{d}iicdc{dddd}ic{iiii}dciiiiciiiiic{d}icc{dd}iiic{i}iiic{d}dddc{ii}dddcc{i}dc{d}iicdc{dddd}ic{iiii}dciiiiciiiiic{d}iciiiic{dd}dc{i}iiic{d}dddc{ii}ddcdc{i}dc{d}iicdc{dddd}ic{iiii}dciiiiciiiiic{d}iicddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciiiiiciiiiic{d}iicdc{dddd}ic{iiii}dciiiiciiiiic{d}iicdc{dd}iiic{i}iiic{d}dddc{ii}dddciiiiciiiiic{d}iicdc{dddd}ic{iiii}dciiiiciiiiicdddddcdddddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciic{i}ddc{d}iicdc{dddd}ic{iiii}dciiiiciiiiicdddddcddddc{dd}iiic{i}iiic{d}dddc{ii}dddcic{i}ddc{d}iicdc{dddd}ic{iiii}dciiiiciiiiicdddddcc{dd}dc{i}iiic{d}dddc{ii}ddcc{i}ddc{d}iicdc{dddd}ic{iiii}cddc{i}c{d}cc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicc{i}c{d}ciiiiic{dddd}dddc{iiii}cddc{i}c{d}cic{dd}iiic{i}iiic{d}dddc{ii}dddcdc{i}c{d}ciiiiic{dddd}dddc{iiii}cddc{i}c{d}ciiiiic{dd}dc{i}iiic{d}dddc{ii}ddcddc{i}c{d}ciiiiic{dddd}dddc{iiii}cddc{i}c{d}icdc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicic{i}dc{d}ciiiiic{dddd}dddc{iiii}cddc{i}c{d}icc{dd}iiic{i}iiic{d}dddc{ii}dddcc{i}dc{d}ciiiiic{dddd}dddc{iiii}cddc{i}c{d}iciiiic{dd}dc{i}iiic{d}dddc{ii}ddcdc{i}dc{d}ciiiiic{dddd}dddc{iiii}cddc{i}c{d}iicddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciiiiiciiiiic{d}ciiiiic{dddd}dddc{iiii}cddc{i}c{d}iicdc{dd}iiic{i}iiic{d}dddc{ii}dddciiiiciiiiic{d}ciiiiic{dddd}dddc{iiii}cddc{i}cdddddcdddddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciic{i}ddc{d}ciiiiic{dddd}dddc{iiii}cddc{i}cdddddcddddc{dd}iiic{i}iiic{d}dddc{ii}dddcic{i}ddc{d}ciiiiic{dddd}dddc{iiii}cddc{i}cdddddcc{dd}dc{i}iiic{d}dddc{ii}ddcc{i}ddc{d}ciiiiic{dddd}dddc{iiii}cdc{i}dc{d}cc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicc{i}c{d}iciiiic{dddd}dddc{iiii}cdc{i}dc{d}cic{dd}iiic{i}iiic{d}dddc{ii}dddcdc{i}c{d}iciiiic{dddd}dddc{iiii}cdc{i}dc{d}ciiiiic{dd}dc{i}iiic{d}dddc{ii}ddcddc{i}c{d}iciiiic{dddd}dddc{iiii}cdc{i}dc{d}icdc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicic{i}dc{d}iciiiic{dddd}dddc{iiii}cdc{i}dc{d}icc{dd}iiic{i}iiic{d}dddc{ii}dddcc{i}dc{d}iciiiic{dddd}dddc{iiii}cdc{i}dc{d}iciiiic{dd}dc{i}iiic{d}dddc{ii}ddcdc{i}dc{d}iciiiic{dddd}dddc{iiii}cdc{i}dc{d}iicddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciiiiiciiiiic{d}iciiiic{dddd}dddc{iiii}cdc{i}dc{d}iicdc{dd}iiic{i}iiic{d}dddc{ii}dddciiiiciiiiic{d}iciiiic{dddd}dddc{iiii}cdc{i}dcdddddcdddddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciic{i}ddc{d}iciiiic{dddd}dddc{iiii}cdc{i}dcdddddcddddc{dd}iiic{i}iiic{d}dddc{ii}dddcic{i}ddc{d}iciiiic{dddd}dddc{iiii}cdc{i}dcdddddcc{dd}dc{i}iiic{d}dddc{ii}ddcc{i}ddc{d}iciiiic{dddd}dddc{iiii}cc{i}ddc{d}cc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicc{i}cdddddcc{dddd}dddc{iiii}cc{i}ddc{d}cic{dd}iiic{i}iiic{d}dddc{ii}dddcdc{i}cdddddcc{dddd}dddc{iiii}cc{i}ddc{d}ciiiiic{dd}dc{i}iiic{d}dddc{ii}ddcddc{i}cdddddcc{dddd}dddc{iiii}cc{i}ddc{d}icdc{d}ddddddc{i}iiic{d}dddc{i}iiiiiicic{i}dcdddddcc{dddd}dddc{iiii}cc{i}ddc{d}icc{dd}iiic{i}iiic{d}dddc{ii}dddcc{i}dcdddddcc{dddd}dddc{iiii}cc{i}ddc{d}iciiiic{dd}dc{i}iiic{d}dddc{ii}ddcdc{i}dcdddddcc{dddd}dddc{iiii}cc{i}ddc{d}iicddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciiiiiciiiiicdddddcc{dddd}dddc{iiii}cc{i}ddc{d}iicdc{dd}iiic{i}iiic{d}dddc{ii}dddciiiiciiiiicdddddcc{dddd}dddc{iiii}cc{i}ddcdddddcdddddc{d}ddddddc{i}iiic{d}dddc{i}iiiiiiciic{i}ddcdddddcc{dddd}dddc{iiii}cc{i}ddcdddddcddddc{dd}iiic{i}iiic{d}dddc{ii}dddcic{i}ddcdddddcc{dddd}dddc{iiii}cc{i}ddcdddddcc{dd}dc{i}iiic{d}dddc{ii}ddcc{i}ddcdddddcc

```

# Answer
> 0 votes
# C, 225 bytes

```
h,m,l,r,d=10,L[]={0,1,5,9,9,2,9,9,8,9};M(h,m){l=L[h%d]*d+L[h/d];r=L[m%d]*d+L[m/d];return L[h%d]<9&L[h/d]<9&L[m%d]<9&L[m/d]<9;}f(){for(h=0;h<24;++h)for(m=0;m<60;++m)M(h,m)&l<60&r<24&&printf("%02d:%02d - %02d:%02d\n",h,m,r,l);}

```

Since there is no C answer, I post my own. Some other approach might be shorter.

Try it online!

---
Tags: code-golf, kolmogorov-complexity, clock
---


title: Compile Commentscript

text:
# Question
Title: Compile Commentscript
Commentscript is a variant on Javascript that I made up for the purpose of this question. Only commented-out code is evaluated.

Javascript has two types of comments:

```
// this is a single line comment, which starts with `//` and ends on a newline.

/*
This is a multiline comment.
It starts with /* and ends with */

```

Example:

```
//console.log('goodbye world')
console.log('hello world')

```

will output `goodbye world` to the console.

Your challenge is to compile Commentscript code into regular Javascript.

## Scoring

This is code-golf, so shortest bytes wins!

## Clarifications

Nested comments like `// comment // nested comment` should just have the top-level comment removed, for example `comment // nested comment`.

To avoid complications, comments in strings should be read as comments, e.g. `'abc //' def //ghi` =\> `' def //ghi`

Newlines from single line comments should be kept, but ones by multiline comments shouldn't.

Ignore shebangs, e.g. `#! /usr/bin/env node`

```
//a
//b
=>
a
b

/*a*/

/*b*/
=>
ab

```

## Test cases

```
//console.log('hello world') => console.log('hello world')

//console.log('hello world')//do stuff => console.log('hello world')//do stuff

/*var a = 5;*/function f(){}/*console.log(a)*/ => var a = 5; console.log(a)

/////////// => /////////

//console.log('hello world')/*More nested comments*/ => console.log('hello world')/*More nested comments*/

"abc //" def //ghi => " def //ghi

//a
//b
=>
a
b

/*a*//*b*/ => ab

//a

//b

//c
=>
a
b
c

/*
for(var x of array){
    console.log(x)
}
*/
=>
for(var x of array){
    console.log(x)
}

/*
//this is a comment
*/

=>

//this is a comment

#!/usr/bin/env node =>  [NOTHING]

```

# Answer
> 2 votes
# Retina 0.8.2, 63 bytes

```
(//.*|/\*(.|¶)*?\*/|¶)|.
$1
//(.*)|/\*((.|¶)*?)\*/|(¶)¶*
$1$2$4

```

Try it online! Link includes test cases, but the newline-collapsing rule means that they're not double-separated on output. Explanation:

```
(//.*|/\*(.|¶)*?\*/|¶)|.
$1

```

Delete anything not a newline or comment.

```
//(.*)|/\*((.|¶)*?)\*/|(¶)¶*
$1$2$4

```

Keep the content of comments and one newline of consecutive newlines.

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


title: Highest single-turn score in Match Land

text:
# Question
Title: Highest single-turn score in Match Land
## Background

*Match Land* is a mobile game that falls into the Match-3 genre (think Bejeweled or Candy Crush Saga series): swap two orthogonally adjacent pieces to make a 3-in-a-row or longer. However, Match Land has an additional rule that makes the game much more interesting.

Once you make a valid match-3 move, the matched blocks are not removed immediately; instead, you get a small time window where you can create more/longer match-3 chains by swapping not-yet-matched blocks. If you make a wrong swap (that does not create a new match or extend existing matches), your turn ends immediately.

Exact rules for this challenge are as follows (I don't play this game right now, so the details might be different from the actual game. And the details not relevant to this challenge are omitted):

* The game is played on a rectangular board. It is turn-based, and the player can make one or more moves in a turn.
* The board is filled with tiles, each of which has one of six different types (denoted 1 to 6 in the examples later).
* The player makes a *"match"* (three or more same tiles in a row, horizontally or vertically) by swapping two orthogonally (horizontally or vertically) adjacent tiles. The action of swapping two tiles is called a *"move"*.
* After the initial match, the player can make an additional move if the move extends the length of an existing match or it creates at least one new match (3-in-a-row).

In the following example, B4-C4 and B3-B4 are valid moves but A3-B3 is not (simply moving the 4 adjacent to an existing match without creating a 3-in-a-row is not valid):

```
  | 1  2  3  4
--+------------
A | 2  1  4  3
B | 1  2  3  4
C |(4)(4)(4) 5

```
* The player cannot move already matched tiles.

For example, consider the following 5x7 board (with coordinates for ease of explanation):

```
  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  4  3  5  2  4
B | 3  2  1  4  1  3  5
C | 4  2  4  4  3  1  4
D | 2  4  3  1  4  2  3
E | 2  4  2  2  3  3  4

```

The player can make a move at A3-A4 to match three 4's:

```
  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  3 (4) 5  2  4
B | 3  2  1 (4) 1  3  5
C | 4  2  4 (4) 3  1  4
D | 2  4  3  1  4  2  3
E | 2  4  2  2  3  3  4

```

Then D7-E7 to match some 3's:

```
  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  3 (4) 5  2  4
B | 3  2  1 (4) 1  3  5
C | 4  2  4 (4) 3  1  4
D | 2  4  3  1  4  2  4
E | 2  4  2  2 (3)(3)(3)

```

Then C5-D5 (note that a match is extended only if the new tile to be matched is aligned with the existing match, so the 3 moving into D5 is not matched with the existing E5-E7):

```
  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  3 (4) 5  2  4
B | 3  2  1 (4) 1  3  5
C | 4  2 (4)(4)(4) 1  4
D | 2  4  3  1  3  2  4
E | 2  4  2  2 (3)(3)(3)

```

You can continue this until you run out of possible moves.

I found a sequence of 9 moves from the initial state that matches **26** tiles in total (not confirmed yet if it is optimal):

```
C1-C2 B1-B2 A2-B2 C5-D5 D6-E6 E5-E6 D3-D4 B6-C6 B3-B4

  | 1  2  3  4  5  6  7
--+---------------------
A |(2) 3 (4) 3  5  2  4
B |(2)(4)(4)(1)(1)(1) 5
C |(2)(4)(4)(4)(4)(3) 4
D |(2)(4) 1 (3)(3)(3)(3)
E |(2)(4)(2)(2)(2)(3) 4

```

## Challenge

Given a board state in Match Land, output the maximum number of tiles that can be matched in a single turn.

The input is a 2D array of integers from 1 to 6 inclusive. You can use any equivalent representation of a rectangular 2D array in your language, and any 6 distinct values in place of the integers. You can further assume that the input does not already have any 3-in-a-rows (as is the case in the actual game), and it has at least one valid initial move.

Standard rules apply. Shortest code in bytes wins. Imaginary brownie points for a solution that is provably correct and works reasonably fast in practice.

## Test cases

```
Input:
1 1 2 1 1
Output: 4

Input:
1 1 2
2 2 3
3 3 1
Output: 9

Input:
2 2 1 2 1
2 1 2 1 2
3 2 1 2 1
Output: 14 (A3-A4, B4-B5, B2-B3, B3-B4, C3-C4)

Input:
3 2 1 2 2
2 1 2 1 2
3 2 1 2 1
Output: 12 (B4-C4, B2-C2, A2-A3)
(I believe matching 13 tiles is impossible without breaking existing matches)

```

# Answer
# JavaScript (ES6),  ~~315 307~~  303 bytes

Brute force, but quite fast on the test cases.

```
f=(m,T=M=0,C=c=>m.map((r,y)=>r.map((_,x)=>c(x,y,1,0)|c(x,y,0,1))))=>C((x,y,X,Y,r=m[y],v=r[x],R=m[y+Y]||0,V=R[X+=x])=>V<8&v<8&&(Y=m.map(r=>[...r]),r[x]=V,R[X]=v,a=[n=0,1,2],C((x,y,w,z)=>a.some(p=i=>p-(p=(m[y+z*i]||0)[x+w*i]&7))||a.map(i=>n+=(R=m[y+z*i])[i=x+w*i]<(R[i]|=8)))|n&&f(m,T+n),m=Y),M=T>M?T:M)|M

```

Try it online!

### Commented and speed-optimized

By adding a cache, we can make it fast enough to solve the 7x5 example given in the challenge in a few seconds.

A solution for 30 tiles in 11 moves is:

```
A4-B4 B5-C5 C4-D4 C3-D3 B3-C3 B1-B2 D7-E7 A7-B7 E1-E2 D1-E1 C1-C2

```

```
f = (
  // m[] is the input grid
  m,
  // T is the current score, M is the best score
  T = M = 0,
  // ungolfed version only: keep track of the moves and use a cache
  P = [],
  S = new Set,
  // C is a helper function that walks through all cells and invokes a callback
  // function with the position (x, y) and a vector (+1, 0) or (0, +1)
  C = c => m.map((r, y) => r.map((_, x) => c(x, y, 1, 0) | c(x, y, 0, 1))),
  B
) =>
// cache hit? (ungolfed version only)
( S.has(key = JSON.stringify(m))
  ||
  // look for all pairs of cells that can be swapped
  C((x, y, X, Y, r = m[y], v = r[x], R = m[y + Y] || 0, V = R[X += x]) =>
    // valid only if none of them already belongs to a match
    // ungolfed version only: also make sure they're not equal
    V < 8 && v < 8 && v ^ V && (
      // make a backup of the grid
      B = m.map(r => [...r]),
      // swap the cells
      r[x] = V,
      R[X] = v,
      // check the grid
      a = [n = 0, 1, 2],
      C((x, y, w, z) =>
        // 3 cells in a row?
        a.some(p = i =>
          p - (p = (m[y + z * i] || 0)[x + w * i] & 7)
        ) ||
        // if yes, mark them as matched and increment n for each new cell
        a.map(i =>
          n += (R = m[y + z * i])[i = x + w * i] < (R[i] |= 8)
        )
      ) | n &&
      // do a recursive call if at least one new cell was added
      f(m, T + n, [...P, [[x, y], [X, y + Y]]], S),
      // restore the grid
      m = B
    ),
    // update M to max(M, T)
    M = T > M ? (best = P, T) : M,
    // update the cache (ungolfed version only)
    S.add(key)
  ),
  [ best, M ]
)

```

Try it online!
> 6 votes

# Answer
# , 239 bytes

```
f=function(m,x=!m,w=nrow(m),`+`=sum,`/`=c){for(i in seq(m))for(j in 0:1){l=m
k=i--(i%%w&!j)-j*w*(i>w)
l[i/k]=l[k/i]
n=0
for(d in 1:2)n=t(n|apply(l,d,function(v,r=rle(v)$l)unlist(Map(rep,r>2,r)))&!+x[i/k])
if(+n>+x)F=max(F,+n,f(l,t(n)))}
F}

```

Try it online!

### Semi-ungolfed

```
# m - input matrix
# x - matrix of existing matches initialized with FALSEs of the shape of m
# w - number of rows
f = function(m, x=!m, w=nrow(m)) {
  # loop through each cell in m twice:
  # once for a vertical match and once for a horizontal one
  for(i in seq(m)) for(j in 0:1) {
    # Work on a copy of m
    l = m
    # The index of the cell to swap:
    # one cell down from i (except the last row), or
    # one cell left from i (except the first column)
    k = i + (i%%w&!j) - j*w*(i>w)
    # Swap ith and kth cell
    l[c(i,k)] = l[c(k,i)]
    # Record new matches, start with 0
    n = 0
    # If neither i, nor k was matched earlier, check both dimensions:
    if(!any(x[c(i,k)])) for(d in 1:2) {
      # Find runs of 3-in-a-row across the given dimension:
      # take Run Length Encoding of a row/column,
      # expand it so that runs longer than 2 get mapped to TRUE
      # e.g.: 1 2 2 2 3 3 => F T T T F F,
      # then logical OR with previous n
      n = n | apply(l, d, function(v, r=rle(v)$l)unlist(Map(rep, r>2, r)))
      # Apply always collects the results columnwise, so that
      # a transpose is necessary to make the results conformable
      n = t(n)
    }
    # If there are new matches compared to previous iteration
    if(sum(n)>sum(x))
      # Call itself recursively with the modified input l, and
      # n transposed to original shape, as new existing matches
      # The maximum of all iterations will be the final result
      F = max(F, sum(n), f(l,t(n)))
  }
  F
}

```
> 2 votes

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


title: Determine win in Tictactoe

text:
# Question
Title: Determine win in Tictactoe
Let's play some code golf!

Given a tic-tac-toe board state (Example:)

```
|x|x|o|
|x|o|x|
|o|o|x|

```

Determine whether a game is a `win` a `lose` or `cat`. Your code should output any of these options given a state. The above game should output `lose`

Just to be clear: a win is defined as any 3 `x`s in a row (diagonal, horizontal, vertical). a lose is 3 `o`s in a row, while a `cat` game in none in a row.

To make things interesting, you get to determine your input structure for the state- which you must then explain. For instance `xxoxoxoox` is a valid state as seen above where each of the characters is read from left to right, top to bottom. `[['x','x','o'],['x','o','x'],['o','o','x']]` is the game in multidimensional array read in a similar way. While `0x1a9` which is hex for `110101001` might work as a suitable compression where `1` can be manipulated for `x`s and `0` can be manipulated for `o`.

But those are just some ideas, I'm sure you might have many of your own.

Ground rules:

1. Your program must be able to accept any viable state.
2. The form of input must be able to represent any state.
3. The input cannot be redundant, meaning each cell must only appear in one location.
4. "The win state must be determined from the board"
5. Assume a complete board
6. `Win` before `lose` for instance in the case 'xxxoooxxx'

Lowest character count wins

# Answer
## Ruby 2.0, 85 characters

Here's a simple bitmask-based solution in Ruby:

```
d=gets.hex
$><<[292,146,73,448,56,7,273,84].map{|m|d&m<1?:lose:d&m<m ?:cat: :win}.max

```

The board is represented as a hex number, made up of nine bits corresponding to the nine squares. 1 is an `X`, 0 is an `O`. This is just like the `0x1a9` example in the question, though the `0x` is optional!

There's probably a better way to do the bitmasks then just hardcoding a big list. I'll happily take suggestions.

See it running on Ideone here.
> 11 votes

# Answer
# Mathematica, 84 chars

```
a=Input[];Which[Max@#>2,win,Min@#<1,lose,1>0,cat]&@{Tr@a,Tr@Reverse@a,Tr/@a,Total@a}

```

Input format: `{{1, 1, 0}, {1, 0, 1}, {0, 0, 1}}`
> 10 votes

# Answer
# Bash: ~~283~~ ~~262~~ 258

Featuring a relatively friendly interface.

```
t(){ sed 's/X/true/g;s/O/false/g'<<<$@;}
y(){ t $(sed 's/X/Q/g;s/O/X/g;s/Q/O/g'<<<$@);}
f(){($1&&$2&&$3)||($1&&$5&&$9)||($1&&$4&&$7)||($2&&$5&&$8)||($3&&$5&&$7)||($3&&$6&&$9)||($4&&$5&&$6)||($7&&$8&&$9)}
f $(t $@)&&echo win||(f $(y $@)&&echo lose)||echo cat

```

To execute `bash tictactoe.sh O X O X O X X O X`

Note: the list of 9 positions is a standard matrix representation. It doesn't matter if the board is represented as column major or row major, read from left to right or top to bottom - games of noughts and crosses (or tic tac toe if you insist) are symmetrical, so input order should be irrelevant to the result in every correct implementation, as long as input is linear.

Edit: Thanks to h.j.k for shorter function syntax suggestion.
> 7 votes

# Answer
# Befunge 93 - 375

Takes a binary string as input.

```
99>~\1-:!!|>v
>0v>v>v   >^$>v
^+ + +    0<:p:
>#+#+#+    ^246
^+ + +    0<265
>#+#+#+    ^pp6
^+ + +    0<2++
 #+#+#+     55p
   0 0      552
  >^>^>0v   +46
v+ + +  <   ppp
>0 + + + v  444
   v!!-3:<< 246
  v_"ni"v   ppp
  0v" w"<   :+:
  \>,,,,@   266
  ->,,,@    555
  !^"cat"_^ 645
  !>:9-! ^  +:+
  >|        p:p
   >"eso"v  6p6
 @,,,,"l"<  246
            p2p
            >^
  v       <^  <

```

Reads the string. Bruteforce writes it (the right most vertical strip) as a matrix in between the

```
^+ + +
>#+#+#+
^+ + +
>#+#+#+
^+ + +
 #+#+#+

```

adding lattice (idk). Determins the sum of the columns, rows, and two diagnals. Compares those values to 3 ("win") or 0 ("lose"), else if all the values equal 1 or 2 then draw ("cat").
> 6 votes

# Answer
# Python 2 - 214 bytes

```
b=eval(raw_input())
s=map(sum,b)
w,l='win','lose'
e="if min(s)<1:print l;a\nif max(s)>2:print w;a"
exec e+'\ns=map(sum,zip(*b))\n'+e
m=b[1][1]
for i in 0,2:
 if m==b[0][i]==b[2][abs(i-2)]:print[l,w][m];a
print'cat'

```

I'm sure there are improvements to be made.

To run:

```
python2 tictactoe.py <<< '[[1,1,1],[1,0,1],[0,1,0]]'

```

which represents this board:

```
X|X|X
-----
X|O|X
-----
0|X|0

```

Exits with a `NameError` exception in every case except `cat`.
> 3 votes

# Answer
## GolfScript, 63 + 27 = 90 bytes

I originally submitted the following 27-byte entry that exploited a loophole in the rules (as written at the time of submission) allowing a redundant input encoding:

```
70&.{~"win""lose"if}"cat"if

```

The input format for this entry is a string consisting of eight octal digits, each (redundantly) encoding three consecutive board squares:

* The first three digits each encode a single row of the board, from top down and left to right.
* The following three digits each encode a single column of the board, from left to right and top down.
* The final two digits each encode one of the diagonals (first from top left to bottom right, then from bottom left to top right).

To encode a sequence (row / column / diagonal) of three squares as an octal digit, replace every `x` in the sequence with a 1 and every `o` with a 0, and interpret the resulting sequence of ones and zeros as a binary number between 0 and 7 inclusive.

This input format is quite redundant (all board positions are encoded at least twice, with the center position encoded four times), but it *does* unambiguously represent any possible state of a completely filled tic-tac-toe board, and does not *directly* encode the winner into the input.

The input may, optionally, contain spaces or other delimiters between digits. In fact, all the program *really* cares about is whether or not the input string contains the digits `7` or `0`.

For example, the example board:

```
|x|x|o|
|x|o|x|
|o|o|x|

```

may be represented by the input:

```
651 643 50

```

To make testing the program above easier, I also provided a 63-byte GolfScript program to convert an ASCII art board layout, as shown above, into an input string suitable for this program:

```
."XOxo"--[{1&!}/]:a[3/.zip"048642"{15&a=}%3/]{{2base""+}%}%" "*

```

This converter ignores any characters other than `x` and `o`, in either case, in its input. It produces a single digit string (complete with space delimiters as shown above) suitable for feeding into the win-determining program above, so **the concatenation of these two programs can be used to determine the winner directly from the ASCII art board**, and thus still qualifies as a valid entry under the current challenge rules:

```
."XOxo"--[{1&!}/]:a[3/.zip"048642"{15&a=}%3/]{{2base""+}%}%" "*70&.{~"win""lose"if}"cat"if

```

Try it online!

Of course, the input format converted is not particularly well optimized and the combined program could easily be golfed further. However, rather than attempting to re-golf a six-year-old solution, I prefer to just keep it as close to its originally submitted form as current rules permit.

Ps. Here's a reverse converter, just to demonstrate that the redundant input format for the 27-byte version indeed does unambiguously represent the board:

```
.56,48>-- 3<{2base-3>{"ox"=}%n}%"|".@@*+);

```
> 3 votes

# Answer
## Haskell, 146 chars

> To make things interesting, you get to determine your input structure for the state- which you must then explain.

OK :). My representation of a board is one of those 126 characters

> ĻŃŇŉŊœŗřŚşšŢťŦŨųŷŹźſƁƂƅƆƈƏƑƒƕƖƘƝƞƠƤƳƷƹƺƿǁǂǅǆǈǏǑǒǕǖǘǝǞǠǤǯǱǲǵǶǸǽǾȀȄȍȎȐȔȜȳȷȹȺȿɁɂɅɆɈɏɑɒɕɖɘɝɞɠɤɯɱɲɵɶɸɽɾʀʄʍʎʐʔʜʯʱʲʵʶʸʽʾˀ˄ˍˎː˔˜˭ˮ˰˴˼̌

Here's the solution in 146 chars :

```
main=interact$(\x->case(head x)of h|elem h "ĻŃœťŦŨųŷŹƁƂƅƈƕƠƤƳƿǂǆǞǤǵǾȀȳȿɁɅɑɒɘɝɠɤɵɽʀʐʽʾː˭ˮ˰˴˼̌"->"lose";h|elem h "ƏƝƞƹǁǈǑǝȍȺɆɈɶɾʎʸ"->"cat";h->"win")

```

And here's how it works, as an haskell script :

```
import Data.List (subsequences, (\\))
import Data.Char (chr)

-- A set of indexes [0-8] describing where on the board pieces of a single color have been played
-- For example the board "OxO;Oxx;xxO" is indexes [0,2,3,8]
type Play = [Int]

-- There are 126 filled tic tac toe boards when X plays first.
--      (This is a combination of 4 OHs among 9 places : binomial(9 4) = 126)
-- perms returns a list of all such possible boards (represented by the index of their OHs).
perms = filter (\x -> 4 == length x) $ subsequences [0..8]

-- We now create an encoding for plays that brings them down to a single char.
-- The index list can be seen as an 9 bit binary word [0,2,3,8] -> '100001101'
-- This, in turn is the integer 269. The possible boards give integers between 15 and 480.
-- Let's call those PlayInts
type PlayInt = Int

permToInt [] = 0
permToInt (x:xs) = (2 ^ x) + permToInt xs

-- Since the characters in the range 15-480 are not all printable. We offset the chars by 300, this gives the range
-- ĻŃŇŉŊœŗřŚşšŢťŦŨųŷŹźſƁƂƅƆƈƏƑƒƕƖƘƝƞƠƤƳƷƹƺƿǁǂǅǆǈǏǑǒǕǖǘǝǞǠǤǯǱǲǵǶǸǽǾȀȄȍȎȐȔȜȳȷȹȺȿɁɂɅɆɈɏɑɒɕɖɘɝɞɠɤɯɱɲɵɶɸɽɾʀʄʍʎʐʔʜʯʱʲʵʶʸʽʾˀ˄ˍˎː˔˜˭ˮ˰˴˼̌
-- Of all distinct, printable characters
uOffset = 300

-- Transform a PlayInt to its Char representation
pIntToUnicode i = chr $ i + uOffset

-- Helper function to convert a board in a more user friendly representation to its Char
-- This accepts a representation in the form "xooxxxoxo"
convertBoard s = let play = map snd $ filter (\(c, i) -> c == 'o') $ (zip s [0..]) :: Play
    in pIntToUnicode $ permToInt play

--
-- Now let's cook some data for our final result
--

-- All boards as chars
allUnicode = let allInts = map permToInt perms
    in map pIntToUnicode allInts

-- Now let's determine which boards give which outcome.

-- These are all lines, columns, and diags that give a win when filled
wins = [
        [0,1,2],[3,4,5],[6,7,8], -- lines
        [0,3,6],[1,4,7],[2,5,8], -- columns
        [0,4,8],[2,4,6] -- diagonals
    ]

isWin :: Play -> Bool
isWin ps = let triplets = filter (\x -> 3 == length x) $ subsequences ps -- extract all triplets in the 4 or 5 moves played
    in any (\t -> t `elem` wins) triplets -- And check if any is a win line

-- These are OH wins
oWins = filter isWin perms
-- EX wins when the complement board wins
xWins = filter (isWin . complement) perms
    where complement ps = [0..9] \\ ps
-- And it's stalemate otherwise
cWins = (perms \\ oWins) \\ xWins

-- Write the cooked data to files
cookData = let toString = map (pIntToUnicode . permToInt) in do
  writeFile "all.txt" allUnicode
  writeFile "cWins.txt" $ toString cWins
  writeFile "oWins.txt" $ toString oWins
  writeFile "xWins.txt" $ toString xWins

-- Now we know that there are 48 OH-wins, 16 stalemates, and 62 EX wins (they have more because they play 5 times instead of 4).
-- Finding the solution is just checking to which set an input board belongs to (ungolfed :)
main = interact $ \x -> case (head x) of -- Only consider the first input char
    h | elem h "ĻŃœťŦŨųŷŹƁƂƅƈƕƠƤƳƿǂǆǞǤǵǾȀȳȿɁɅɑɒɘɝɠɤɵɽʀʐʽʾː˭ˮ˰˴˼̌" -> "lose" -- This string is == oWins
    h | elem h "ƏƝƞƹǁǈǑǝȍȺɆɈɶɾʎʸ" -> "cat" -- And this one == cWins
    h -> "win"

```
> 3 votes

# Answer
## Ruby, 84 characters

```
$><<(gets.tr("01","10")[r=/0..(0|.0.)..0|000(...)*$|^..0.0.0/]?:win:~r ?:lose: :cat)

```

Simple, RegExp based solution. The input format is a 9-digit binary string, e.g. `110101001` for the example board given in the question.

## Ruby, 78 characters

```
$><<(gets.tr("ox","xo")[r=/o...(o|.o.)...o|ooo|o_.o._o/]?:win:~r ?:lose: :cat)

```

Input format: `xxo_xox_oox`
> 3 votes

# Answer
# Python3 - 188 w. different approaches to evaluation

Found the subject yesterday on Reddit and was fascinated. It was a simple code just to determine victory. Same night I made up my own version. Today i found this codegolf thread. \[EDIT: 'blabla'\] I am amazed about the different answers and possibilities within the other languages! Nice!

### 188 Python3 Code

EDIT: Now Meeting Requirements 1-5

Input-Style: Player p=0/1 and board b=(1,1,1,0,1,0,1,0,1)

```
def t(b,p):
    s,c,l,w=0,"cat","loose","win"
    for i in 1,2,3,4:
        u=2*i-1
        a=i*i-5*i+3
        if b[4]==b[4+i]==b[4-i]:
            if p==b[4]:s+=1
            else:s-=1
        if b[u]==b[u+a]==b[u-a]:
            if p==b[u]:s+=1
            else:s-=1
    if s>0:c=w
    if s<0:c=l
    return c

```

## Victory Check Codes

### 103 Python3 - 'Square-Function'

EDIT1: nicer with "a==b==c==p" instead of "a+b+c==3\*p"

```
def t(b,p):
    for i in 1,2,3,4:
        u=2*i-1
        a=i*i-5*i+3
        if b[4]==b[4+i]==b[4-i]==p or b[u]==b[u+a]==b[u-a]==p:return True

```

Explanation: Term for a based on f(u=1)=f(u=7)=1 f(u=3)=f(u=5)=3

### 113 Python3 - 'Magic Square'

Input just with board: Player is „1“, Oponent „0“

```
def t(b):
    n=[x*y for x,y in zip(b,(2,9,4,7,5,3,6,1,8))]
    if 15 in [x+y+z for x in n for y in n if x!=y for z in n if z!=x and z!=y]:return True

```

Explanation: Sum has to be 15 in Magic Square

### 119 Python3 - 'Oneliner'

inspired by Reddit Solution from user 'Xelf'

```
def t(b,p):
    if 3*p in [b[x]+b[y]+b[z] for x,y,z in [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]]:return True

```

---

@Ad Hoc Garf Hunter Thank You for the Feedback! Though i am a bit embarassed and sorry i don´t even know what 'stdin' is about. Just want to contribute some ideas and learn. Thank you for the comment on assignment and whitespaces! I just corrected it. EDIT: Hope to meet the rules now. I understand i could make spaces instead of tabs, but that just looks nasty.
> 3 votes

# Answer
# CJam, ~~39 38~~ 36 characters

```
"ᔔꉚ굌궽渒䗠脯뗠㰍㔚귇籾〳㎪䬔⹴쪳儏⃒ꈯ琉"2G#b129b:c~

```

This is a base converted code for

```
q3/_z__Wf%s4%\s4%]`:Q3'o*#"win"{Q'x3*#"lose""cat"?}?

```

which is 52 characters long.

The input is simply the string representation of the board starting from top left, going row by row. For example:

```
oxooxooox

```

which results in a `win` output. Or

```
oxooxoxox

```

which results in a `cat` output, etc.

The code simply does the following three things:

* `q3/_` \- Split the string into parts of 3, i.e. per row
* `_z` \- Copy the per row array and transpose into per column array.
* `__Wf%s4%` \- Reverse each row and get the left to right diagonal. This is the secondary diagonal of the board.
* `\s4%` \- Get the main diagonal of the board
* `]`` \- Wrap everything in array and stringify the array.

Now we have all possible groups of 3 from the board. We simply check for existence of "ooo" and "xxx" to determine the result.

Try it online here
> 2 votes

# Answer
# Haskell, 169

```
main=interact$(\x->last$"cat":[b|(a,b)<-[("ooo","lose"),("xxx","win")],any(==a)x]).(\x->x++(foldr(zipWith(:))(repeat[])x)++map(zipWith(!!)x)[[0..],[2,1,0]]).take 3.lines

```

Input format: "X" is represented only by `x`, "O" only by `o`. Within each row, characters are simultaneous without spaces, etc. Rows are separated by new lines.

Generates all possible rows/columns/diagonals, then filters `[("ooo","lose"),("xxx","win")]` by their existence on the board, then selects the second word in the tuple, so we know which players won. We prepend `"cat"` so that we can take the last element of the list as our winner. If both players won, `"win"` will be last (list comprehensions maintain order). Since `"cat"` is always first, if a winner exists, it will be chosen, but otherwise a last element still exists as prepending `"cat"` guarantees nonemptyness.

EDIT: Shaved 3 characters by changing last list comprehension to `map`.
> 1 votes

# Answer
## Dart - 119

(See dartlang.org).

Original version using RegExp: 151 chars.

```
main(b,{w:"cat",i,p,z}){
 for(p in["olose","xwin"])
   for(i in[0,2,3,4])
     if(b[0].contains(new RegExp('${z=p[0]}(${'.'*i}$z){2}')))
       w=p.substring(1);
  print(w);
}

```

Input on the command line is 11 characters, e.g., "xxx|ooo|xxx". Any non-xo character can be used as delimiter.

Leading whitespace and newlines should be omitted before counting characters, but I cut away the internal whitespace where possible. I wish there was a smaller way to make the substring.

Recusive bit-base version: 119 chars. Input must be a 9-bit number with 1s representing 'x' and 0s representing 'o'.

```
main(n){
  n=int.parse(n[0]);
  z(b,r)=>b>0?b&n==b&511?"win":z(b>>9,n&b==0?"lose":r):r;
  print(z(0x9224893c01c01e2254,"cat"));
}

```
> 1 votes

# Answer
# Python 2, 99 bytes

Similar to the Ruby answer:

```
def t(b):print['win'if w&b==w else'lose'if w&~b==w else'cat'for w in 448,56,7,292,146,73,273,84][0]

```

The input is the binary format described in the question: `1` for X, `0` for O, left-to-right, top-to-bottom. For example, `0b101001110` represents

```
XOX
OOX
XXO

```

which leads to output: `cat`
> 1 votes

# Answer
# C, 164 bytes

It's midnight here and **I haven't done any testing**, but I'll post the concept anyway. I'll get back to it tomorrow.

User inputs two octal numbers (I wanted to use binary but as far as I know C only supports octal):

`a` represents the centre square, 1 for an X, 0 for an O

`b` is a nine-digit number representing the perimeter squares, circling round the board starting in one corner and finishing in the same corner (with repeat of that corner only), 1 for an X, 0 for an O.

**There are two possible ways to win:**

1. centre square is X (`a`=1) and two opposite squares are also X (`b&b*4096` is nonzero)
2. three adjacent perimeter squares are X (`b/8 & b & b*8` is nonzero.) This is only a valid win if the middle square is an edge square, not a corner square, therefore it is necessary to apply the mask `m` also, to avoid the corner square cases.

**Losing is detected using the variable c, which is the inverse of b.**

```
int a,b,c,m=010101010;
main(){
    scanf("%o%o",a,b);c=b^0111111111;
    printf("%s",(a&&b&b*4096)|(b/8&b&b*8&m)?"win":((!a&&c&c*4096)|(c/8&c&c*8)?"lose":"cat"));
}

```
> 1 votes

# Answer
# Bash, ~~107~~ 103

Generates and runs a sed script.

I/O format: `oxo-oox-xoo` outputs `lose` (use a `-` to separate rows). Input on stdin. Requires GNU sed for the `c` command.

I've interpreted rule 5 as "if both win and lose are possible, choose win".

## Main Code

This is the actual answer.

Nothing interesting really. It defines `$b` as `/cwin` to save characters, then defines the win condition part of the script, then uses `sed y/x/o/\;s$b/close/` to convert `x` to `o` and `cwin` to `close` (thereby generating the lose conditions). It then sends the two things and `ccat` (which will output `cat` if no win/lose condition is matched) to sed.

```
b=/cwin
v="/xxx$b
/x...x...x$b
/x..-.x.-..x$b
/x-.x.-x$b"
sed "$v
`sed y/x/o/\;s$b/close/<<<"$v"`
ccat"

```

## Generated Code

This is the sed script generated and run by the Bash script.

In the regexes, `.` matches any character and after them `cTEXT` prints TEXT and exits if the regex is matched.

This can run as a standalone sed script. It's 125 characters long, you can count it as another solution.

```
/xxx/cwin
/x...x...x/cwin
/x..-.x.-..x/cwin
/x-.x.-x/cwin
/ooo/close
/o...o...o/close
/o..-.o.-..o/close
/o-.o.-o/close
ccat

```
> 1 votes

# Answer
# J - 56 (26?) char

Input is given a 3x3 matrix of nine characters, because J can support that as a datatype, LOL.

```
(win`lose`cat{::~xxx`ooo<./@i.<"1,<"1@|:,2 7{</.,</.@|.)

```

Examples:

```
   NB. 4 equivalent ways to input the example board
   (3 3 $ 'xxoxoxoox') ; (_3 ]\ 'xxoxoxoox') ; ('xxo','xox',:'oox') ; (];._1 '|xxo|xox|oox')
+---+---+---+---+
|xxo|xxo|xxo|xxo|
|xox|xox|xox|xox|
|oox|oox|oox|oox|
+---+---+---+---+
   (win`lose`cat{::~xxx`ooo<./@i.<"1,<"1@|:,2 7{</.,</.@|.) 3 3 $ 'xxoxoxoox'
lose
   wlc =: (win`lose`cat{::~xxx`ooo<./@i.<"1,<"1@|:,2 7{</.,</.@|.)
   wlc (3 3 $ 'xoxoxooxo')
cat
   wlc (3 3 $ 'xxxoooxxx')
win

```

If we are allowed the Golfscriptish encoding of octal digits redundantly representing the state of each row, column, and diagonal, then it's just 26 characters:

```
   win`lose`cat{::~7 0<./@i.] 6 5 1 6 4 3 5 0
lose
   f=:win`lose`cat{::~7 0<./@i.]
   f  7 0 7 5 5 5 5 5
win

```
> 1 votes

# Answer
# T-SQL (2012),110

`select max(iif(@&m=0,'lose',iif(@&m=m,'win','cat')))from(VALUES(292),(146),(73),(448),(56),(7),(273),(84))z(m)`

Input is a hex number. This is pretty much a translation of the ruby solution into T-SQL pretty nice and neat.
> 1 votes

# Answer
# Java 7, 260 bytes

```
String c(int[]s){int a[]=new int[8],x=0,y;for(;x<3;x++){for(y=0;y<3;a[x]+=s[x*3+y++]);for(y=0;y<3;a[x+3]+=s[y++%3]);}for(x=0;x<9;y=s[x],a[6]+=x%4<1?y:0;a[7]+=x%2<1&x>0&x++<8?y:0);x=0;for(int i:a)if(i>2)return"win";for(int i:a)if(i<1)return"loose";return"cat";}

```

**Ungolfed & test cases:**

Try it here.

```
class M{
  static String c(int[] s){
    int a[] = new int[8],
        x = 0,
        y;
    for(; x < 3; x++){
      for(y = 0; y < 3; a[x] += s[x * 3 + y++]);
      for (y = 0; y < 3; a[x + 3] += s[y++ % 3]);
    }
    for(x = 0; x < 9; y = s[x],
                      a[6] += x % 4 < 1
                               ? y
                               : 0,
                      a[7] += x % 2 < 1 & x > 0 & x++ < 8
                               ? y
                               : 0);
    x = 0;
    for(int i : a){
      if(i > 2){
        return "win";
      }
    }
    for(int i : a){
      if(i < 1){
        return "loose";
      }
    }
    return "cat";
  }

  public static void main(String[] a){
    /*  xxo
        xox
        oox  */
    System.out.println(c(new int[]{ 1, 1, 0, 1, 0, 1, 0, 0, 1 }));
    /*  xxx
        ooo
        xxx  */
    System.out.println(c(new int[]{ 1, 1, 1, 0, 0, 0, 1, 1, 1 }));
    /*  xxo
        oox
        xox  */
    System.out.println(c(new int[]{ 1, 1, 0, 0, 0, 1, 1, 0, 1 }));
  }
}

```

**Output:**

```
loose
win
cat

```
> 1 votes

# Answer
# Bash: 208 chars

```
y(){ tr '01' '10'<<<$@;}
f(){ x=$[($1&$2&$3)|($1&$5&$9)|($1&$4&$7)|($2&$5&$8)|($3&$5&$7)|($3&$6&$9)|($4&$5&$6)|($7&$8&$9)]; }
f $@;w=$x
f $(y $@)
([ $x -eq 1 ]&&echo lose)||([ $w -eq 1 ]&&echo win)||echo cat

```

To execute `bash tictactoe.sh 0 1 0 1 0 1 1 0 1`

Inspired by this answer.
> 1 votes

# Answer
# PowerShell, ~~120~~ ~~116~~ ~~118~~ ~~112~~ ~~106~~ 102 bytes

The more compact pattern inspired by Ventero

Fixed to follow the rule 6.

```
@(switch -r($args){($x='^(...)*111|^..1.1.1|1..(1|.1.)..1'){'win'}($x-replace1,0){'lose'}.{'cat'}})[0]

```

Try it online!
> 1 votes

# Answer
## J - 97 bytes

Well, the simplest approach available. The input is taken as `111222333`, where the numbers represent rows. Read left-to-right. Player is `x` and enemy is `o`. Empty squares can be anything except `x` or `o`.

```
f=:(cat`lose>@{~'ooo'&c)`('win'"_)@.('xxx'&c=:+./@(r,(r|:),((r=:-:"1)(0 4 8&{,:2 4 6&{)@,))3 3&$)

```

Examples: (NB. is a comment)

```
   f 'xoxxoxxox' NB. Victory from first and last column.
win
   f 'oxxxooxxx' NB. Victory from last row.
win
   f 'ooxxoxxxo' NB. The example case, lost to a diagonal.
lose
   f 'xxooxxxoo' NB. Nobody won.
cat
   f 'xoo xx ox' NB. Victory from diagonal.
win

```

### Ungolfed code an explanation

```
row   =: -:"1                        Checks if victory can be achieved from any row.
col   =: -:"1 |:                     Checks if victory can be achieved from any column.
diag  =: -:"1 (0 4 8&{ ,: 2 4 6&{)@, Checks if victory can be achieved from diagonals.
check =: +./@(row,col,diag) 3 3&$    Checks all of the above and OR's them.

f     =: (cat`lose >@{~ 'ooo'&check)`('win'"_)@.('xxx'&check)
Check if you have won ........................@.('xxx'&check)
 If yes, return 'win' .............. ('win'"_)
 If not                   (cat`lose >@{~ 'ooo'&check)
  Check if enemy won ................... 'ooo'&check
   If yes, return 'lose'   ---`lose >@{~
   If not, return 'cat'    cat`---- >@{~

```
> 0 votes

# Answer
## JavaScript, ~~133~~, 114 characters

```
r = '/(1){3}|(1.{3}){2}1|(1.{4}){2}1|(1\|.1.\|1)/';alert(i.match(r)?'WIN':i.match(r.replace(/1/g,0))?'LOSS':'CAT')

```

The input `i` is a simple string with delimiters for the rows, i.e. `100|001|100`

Edit: updated my method to replace the 1s in the regex with zeroes to check for the loss case.
> 0 votes

# Answer
## J : 83

```
(;:'lose cat win'){::~>:*(-&(+/@:(*./"1)@;@(;((<0 1)&|:&.>@(;|.)(,<)|:)))-.)3 3$'x'=

```

Usage: just append a string of x's and o's and watch the magic work. eg. 'xxxoooxxx'.

The inner verb `(+/@:(*./"1)@;@(;((<0 1)&|:&.>@(;|.)(,<)|:)))` basically boxes together the original binary matrix, with the transpose boxed together with the 2 diagonals. These results are razed together ; row sums are taken to determine wins, and then summed. further I'll call this verb `Inner`.

For finding the winner, the difference of the scores between the normal and inversed binary matrices is taken by the hook `(-&Inner -.)`.

The rest of the code simply makes the outputs, and selects the right one.
> 0 votes

# Answer
# APL(NARS), 69 chars, 138 bytes

```
{w←3 3⍴⍵⋄x←(+/1 1⍉⊖w),(+/1 1⍉w),(+⌿w),+/w⋄3∊x:'win'⋄0∊x:'lose'⋄'cat'}

```

The input should be one 3x3 matrix or one linear array of 9 element that can be only 1 (for X) and 0 (for O), the result will be "cat" if nobody wins, "lose" if O wins, "win" if X wins. There is no check for one invalid board or input is one array has less than 9 element or more or check each element \<2.

As a comment: it would convert the input in a 3x3 matrix, and build one array named "x" where elements are the sum each row column and diagonal.

Some test see example showed from others:

```
  f←{w←3 3⍴⍵⋄x←(+/1 1⍉⊖w),(+/1 1⍉w),(+⌿w),+/w⋄3∊x:'win'⋄0∊x:'lose'⋄'cat'}
  f 1 2 3
win
  f 0 0 0
lose
  f 1 0 1  1 0 1  1 0 1
win
  f 0 1 1  1 0 0  1 1 1
win
  f 0 0 1  1 0 1  1 1 0
lose
  f 1 1 0  0 1 1  1 0 0
cat
  f 1 1 0  0 1 0  0 0 1
win
  f 1 1 0  1 0 1  0 0 1
lose

```
> 0 votes

# Answer
# Jelly, 27 bytes

```
ŒD,ŒdḢ€;;ZEƇFṀị“ẏż“¡ṇ⁽“Zƙċ»

```

Try it online!

Input is a list of lists of ints: 0 = nothing, 1 = circle, 2 = cross.

## Explanation

```
ŒD,ŒdḢ€;;ZEƇFṀị“ẏż“¡ṇ⁽“Zƙċ»   Main monadic link
ŒD                            Diagonals
  ,                           Pair with
   Œd                           Antidiagonals
     Ḣ€                       Head (first item) of each
                              [the main diagonal and antidiagonal]
       ;                      Join with the input
        ;                     Join with the input
         Z                      zipped (transposed)
                              [the diagonals, rows and columns]
           Ƈ                  Filter by
          E                     All elements equal?
            F                 Flatten
             Ṁ                Maximum
              ị               Index into (1-indexed)
               “ẏż“¡ṇ⁽“Zƙċ»     ["lose", "win", "cat"]

```
> 0 votes

# Answer
# PowerShell, 174 bytes

```
param($a,$b,$c,$d,$e,$f,$g,$h,$i)@("$a$b$c","$a$d$g","$a$e$i","$b$e$h","$c$e$g","$c$f$i","$d$e$f","$g$h$i")|%{if($_-eq'XXX'){'win';exit}elseif($_-eq'OOO'){'lose';exit}};'cat'

```

Try it online!

Trivial solution.

Takes 9 parameters for each key in board.
> 0 votes

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


title: Zeroes at end of \$n!\$ in base \$m\$

text:
# Question
Title: Zeroes at end of \$n!\$ in base \$m\$
Related: Zeroes at the end of a factorial

Today, we are going to calculate how many zeroes are there at the end of \\$n!\\$ (the factorial of \\$n\\$) in base \\$m\\$.

Or in other words: For given integers \\$n\\$, and, \\$m\\$. Calculate the integer \\$p\\$ which is the highest power of \\$m\\$ dividing \\$n!\\$: \\$p \in \mathbb{N}\_0\\$ which holds \\$ \left( m^p \mid n! \right) \land \left( m^{p+1} \nmid n! \right) \\$. Here, \\$n!\\$ is the factorial of \\$n\\$ which equals to the product of all positive integers less than or equal to \\$n\\$. The value of \\$0!\\$ is \\$1\\$.

## Input / Output

* Two integers \\$n\\$, \\$m\\$.
* One integer: How many zeroes at end of \\$n!\\$ in base \\$m\\$.

## Rules

* As , the shortest codes in bytes win.
* Your program is required to support \\$0\le n\le 1{,}000{,}000\\$; \\$2\le m\le 1{,}000\\$ at least. The program should be able to output correct results for any inputs in above range with reasonable resource (typically, \<1 minutes on a normal laptop).
* As this question is only talking about integers. No floating point errors may allowed in your output. You may, however, output 3.0 when 3 is required. But 2.9999999999999996 is certainly not allowed.

## Testcases

```
      n,    m -> output
      0,    2 -> 0
      1,    2 -> 0
      2,    2 -> 1
      3,    2 -> 1
      4,    2 -> 3
      9,    6 -> 4
     10,  100 -> 1
     80,  100 -> 9
      4,    8 -> 1
     15,   12 -> 5
     16,   12 -> 6
     39,   45 -> 8
    100,    2 -> 97
    100,    3 -> 48
    100,    4 -> 48
    100,    5 -> 24
    100,    6 -> 48
    100,    7 -> 16
    100,    8 -> 32
    100,    9 -> 24
    100,   10 -> 24
    100,   13 -> 7
    100,   36 -> 24
    100,   42 -> 16
    100,   97 -> 1
    100,  100 -> 12
1000000,    2 -> 999993
1000000,    3 -> 499993
1000000,    4 -> 499996
1000000,    6 -> 499993
1000000,    7 -> 166664
1000000,    8 -> 333331
1000000,    9 -> 249996
1000000,  999 -> 27776
1000000, 1000 -> 83332

```

Above \\$n\\$ is written in base 10. You are allowed to receive \\$n\\$ as an array of integers in base \\$m\\$ if you want.

## Related OEIS

It is interesting that this question involve at least 14 sequences on OEIS. Maybe you can find out some helpful formula to solve this problem on it.

OEIS includes sequences for every \\$2 \le m \le 16\\$:

Also, by treating above sequences as a matrix, there are other related sequences:

* A090622: Square array read by antidiagonals of highest power of k dividing n! (with n,k\>1).
* A098094: T(n,k) = greatest e such that k^e divides n!, 2\<=k\<=n (triangle read by rows).
* A011776: a(1) = 1; for n \> 1, a(n) is defined by the property that n^a(n) divides n! but n^(a(n)+1) does not.

# Answer
> 10 votes
# Wolfram Language (Mathematica), 22 bytes

```
#!~IntegerExponent~#2&

```

Try it online!

# Answer
> 5 votes
# Jelly, 12 bytes

```
Æfµ⁹ọ€S:ċⱮ`Ṃ

```

A dyadic Link accepting the base, \\$m\\$, on the left and the factorial-input, \\$n\\$, on the right that yields the number of trailing zeros of \\$n!\_{m}\\$ as an integer.

**Try it online!**

### How?

```
Æfµ⁹ọ€S:ċⱮ`Ṃ - Link: integer, m; integer, n   e.g. 72 100
Æf           - prime factorisation (m)             [ 2, 2, 2, 3, 3]
  µ          - start a new monadic chain - f(x=that)
   ⁹ €       - for each i in [1..n]:
    ọ        -   (i) order (vectorised across x)
                                                   [[0,0,0,0,0],[1,1,1,0,0],[0,0,0,1,1],[2,2,2,0,0],...]
      S      - sum (vectorises)                    [97,97,97,48,48]
          `  - use x as both arguments of:
         Ɱ   -   map across (x) with:
        ċ    -     count occurrences               [ 3, 3, 3, 2, 2]
       :     - integer divide                      [32,32,32,24,24]
           Ṃ - minimum                             24

```

# Answer
> 5 votes
# Python 2, ~~133~~ 130 bytes

Saved **3 bytes** thanks to kops!

```
n,m=input()
f=()
i=2
k=lambda n,p:n and n/p+k(n/p,p)
exec"while m%i<1:m/=i;f+=i,\ni+=1\n"*m
print min(k(n,p)/f.count(p)for p in f)

```

Try it online!

Creates a list of all the prime factors of `m`. The program then computes the highest power of each prime factor that divides `n!` using the `lambda` function `k`. This number is divided by the number of times the prime factor is found in `f`. Finally, the program prints out the `min` of these values.

A math.stackexchange.com question with answers explaining how this works:

https://math.stackexchange.com/questions/391067/power-of-a-number-in-a-factorial

# Answer
> 3 votes
# Jelly, 13 bytes

```
ÆFZọ€Ḣ}S:ʋ@ẎṂ

```

Try it online!

After the `4, 48` fix it's too slow to run all of the test cases in one go, but I think it can still handle them all individually.

I'm not sure why `ɓ` (or `ð` for that matter) refuses to work here.

Takes \\$m\\$ on the left and \\$n\\$ on the right.

```
ÆF               Factor m into [prime, exponent] pairs.
  Z              Zip.
         ʋ@      With [[primes], [exponents]] as the right argument:
    €            For each integer in [1 .. n],
   ọ             how many times is it divisible by
     Ḣ}          each prime? (the list of which is popped from the pair)
       S         Sum the divisibilities,
        :        and floor-divide the sums by the exponents.
           Ẏ     Dump inner lists (not entirely sure why they're singletons),
            Ṃ    and return the minimum.

```

# Answer
> 3 votes
# Charcoal, 49 bytes

```
ＮθＮηＷ¬⁼ηΠυ⊞υ§Φ…·²η¬﹪÷η∨Πυ¹κ⁰Ｉ⌊Ｅυ÷↨Ｅ↨θι↨…↨θιμι¹№υι

```

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

```
ＮθＮη

```

Input `n` and `m`.

```
Ｗ¬⁼ηΠυ⊞υ§Φ…·²η¬﹪÷η∨Πυ¹κ⁰

```

Find `m`'s prime factors.

```
  Ｅυ                    Map over prime factors
       ↨θι              Convert `n` to base `p`
      Ｅ    …↨θιμ        All prefixes
          ↨     ι       Converted from base `p`
     ↨           ¹      Take the sum
    ÷                   Integer divided by
                  №υι   Frequency of prime factor
 ⌊                      Take the minimum
Ｉ                       Cast to string
                        Implicitly print

```

# Answer
> 2 votes
# C (gcc), ~~242~~ 237 bytes

```
f(n,b){int*p=malloc(12*b),d=2,k,l;for(;b/d;++d){for(k=b;k%d<1;k/=d)p[d]++;for(k=2;p[d]&&k<d;p[d]*=d%k++>0);}for(k=0;n/++k;)for(d=2;k/d&&b/d;++d)for(l=k;p[d]&&l%d<1;l/=d)++p[b-~d];for(n=d=0;b/++d;k&&n<1|k/p[d]<n?n=k/p[d]:0)k=p[b-~d];d=n;}

```

Try it online!

---

# Annotated version

```
f(n,b){
 int*p=malloc(12*b) /* Since `b>=2` holds,
                           `12*b>=8*b+8==2*4*(b+1)==2*(b+1)*sizeof(int)`.
                       The pointer `p` represents two sparse arrays of
                       length `b+1` only indexed by primes, the first
                       storing the base's prime factorization.
                       Its latter half's `b+1` elements stores how many of
                       `k`'s (where `1<=k<=n`) prime factors with
                       multiplicities. */
 ,d=2,k,l;
 for(;b/d;++d{      // first half of `p`
  for(k=b;k%d<1;
  k/=d)
   p[d]++;
  for(k=2;p[d]
  &&k<d;
  p[d]*=d%k++>0)
   ;
 }
 for(k=0;n/++k;)    // all factors of $n!$
  for(d=2;k/d
  &&b/d;++d)        // all divisors $d | k$
   for(l=k;p[d]     // which are prime factors of $b$
   &&l%d<1;l/=d)
    ++p[b-~d];
   for(n=d=0;b/++d; /* calculate the minimum of $n!$'s factors
                       weighted according to $b$'s factor's
                       multiplicity */
   k&&n<1|k/p[d]<n
   ?n=k/p[d]:0)
    k=p[b-~d];
 d=n;}              // return

```

Try it online!

# Answer
> 1 votes
# MATLAB, 107 bytes

```
function F(n,m)
for i=1:max(n,m),f{i}=factor(i);end
c=f{m};fix(min(sum([f{1:n}]'==c)./sum(c==c')))
end

```

First get all factors from 1 to the maximum of n or m. This guarantees that all factors of 1-n are captured as well as the factors of m. Then, divide the sum of the appearance of each factor by the duplicity of that factor to determine the minimum amount of pairs of the factors of m appear in n!, which is the maximum power that m can be raised to to divide n!.

For example: F(80,100)

1. f -\> all factors from 1-100 in a 1x100 cell array, where f{i}=factor(i)
2. c -\> \[2 2 5 5\]
3. sum(\[f{1:n}\]'==c) -\> \[78 78 19 19\], there are 78 2s in all of f and 19 5s in all of f.
4. sum(c==c') -\> \[2 2 2 2\], there are two of each factor
5. (3)/(4) -\> \[39 39 9.5 9.5\]. element-wise division shows that at a minimum, 9 whole sets of factors of m are contained in n!'s factors, therefore n! is divisible by at most m^9
6. fix(min(3.3)) -\> 9, which is the correct answer

# Answer
> 1 votes
# Perl 5 -MList::Util, 131 bytes

131 bytes without newlines, indentation and comments.

```
sub f{
  %d=();                                     #init counting hash to empty
  sub e{$M%$_ or$d{$_}++,$M/=$_,redo for@_}  #sub that counts given factors of $M
  e 2..($M=pop);                             #count factors of M
  (%c,%d)=%d;                                #store and reset counts
  for$M(2..pop){e keys%c}                    #count active factors of N! (N=pop)
  ~~min map$d{$_}/$c{$_},keys%d              #how many of last counts in first
}

```

Try it online!

```
print f(100, 13);        # prints 7
print f(1000000, 999);   # prints 27776

```

# Answer
> 0 votes
# Python 3 \+ SymPy, 118 bytes

```
lambda n,m:min(g(n,f)//p for f,p in factorint(m).items())
g=lambda n,p:n and n//p+g(n//p,p)
from sympy.ntheory import*

```

Try it online!

---

This is my reference implementation which generate all testcases:

```
from sympy.ntheory import factorint

def f(n, m):
    factor_count = lambda n, p: n // p + factor_count(n // p, p) if n else 0
    return min(factor_count(n, factor) // power for factor, power in factorint(m).items())

```

---
Tags: code-golf, integer, restricted-time, division, factorial
---


title: Minimally destroy CGCC in Game of Life

text:
# Question
Title: Minimally destroy CGCC in Game of Life
Inspiration

Conway's Game of Life is a well known cellular automaton "played" on an infinite grid, filled with cells that are either alive or dead. Once given an initial state, the board evolves according to rules indefinitely. Those rules are:

* Any live cell with 2 or 3 living neighbours (the 8 cells immediately around it) lives to the next state
* Any dead cell with exactly 3 living neighbours becomes a living cell
* Any other cell becomes a dead cell

Game of Life is known for having simple rules yet structures can quickly become chaotic with minimal change.

Consider the following initial state:

In 5 generations, this reaches this configuration, which is a period 2 oscillator. However, by adding in 8 live cells next to it:

we end up with a completely empty board after 54 generations.

---

Now, consider instead the following initial state:

That is, `CGCC` made up of living cells. Each letter is in a \\$4\times6\\$ bounding box, with a single empty column of cells between boxes, for a total bounding box of \\$19\times6\\$. This is a zoomed-in version.

After 256 generations, the board looks like

From this point, no meaningful change will happen: there are 2 oscillators which do not interact with anything else, and the rest are still lifes.

Your task is to "destroy" this by adding in living cells around the initial configuration.

You will start with the `CGCC` initial state, as shown above. You will add \\$n\\$ living cells to the board. Those cells must be outside of the \\$19\times6\\$ bounding box of the `CGCC` (but may touch against the outside). When this new initial state (with your added cells) is run, it must eventually result in an empty board.

Note that the board is considered infinite, so if your configuration produces any spaceships, it is not a valid configuration.

Your score is equal to \\$n\\$. The lowest score wins, ties are broken by the fewest generations required to empty the board. Please provide either a testing environment to demonstrate your solution, or provide a video/gif of it running.

Here is a pre-filled `CGCC` pattern in a GoL simulator

# Answer
# Score 1, 35 generations

Sorry, but I guess I wrecked the challenge. I brute-forced all meaningful one-dot additions by hand, and found no other answer that wins against this.

## Raw ASCII format

```
 OOO  OOO  OOO  OOO
O    O    O    O
O    O    O    O
O    O OO O    O
O    O  O O    O
 OOO  OO   OOO  OOO

               X

```

## Image of initial state

## Copy.sh export

```
#C Generated by copy.sh/life
x = 19, y = 8, rule = B3/S23
b3o2b3o2b3o2b3o$o4bo4bo4bo$o4bo4bo4bo$o4bob2obo4bo$o4bo2bobo4bo$b3o2b
2o3b3o2b3o$$15bo!

```

Try this pattern on copy.sh!

## Slow animated gif
> 49 votes

# Answer
# \\$n=2\\$, 41 generations

```
#C Generated by copy.sh/life
x = 19, y = 8, rule = B3/S23
11bo$b3o2b3o2b3o2b3o$o4bo4bo4bo$o4bo4bo4bo$o4bob2obo4bo$o4bo2bobo4bo$b
3o2b2o3b3o2b3o$10bo!

```

Run it online here. Here's what the initial position looks like:
> 17 votes

# Answer
# Score 8, 69 generations

This is what I promised for in the comment, but it got already beaten by Dingus...

I can't upload images right now, so I include a text-based initial configuration and the copy.sh export format.

## Raw ASCII format

```
X                  X
 OOO  OOO  OOO  OOO
O    O    O    O
O    O    O    O
O    O OO O    O
O    O  O O    O
 OOO  OO   OOO  OOO
         X

                          X
                         XX
                         X X

```

## Copy.sh export

```
#C Generated by copy.sh/life
x = 28, y = 22, rule = B3/S23
o18bo$b3o2b3o2b3o2b3o$o4bo4bo4bo$o4bo4bo4bo$o4bob2obo4bo$o4bo2bobo4bo$
b3o2b2o3b3o2b3o$9bo$$$$$$$$$$$$26bo$25b2o$25bobo!

```
> 14 votes

---
Tags: code-challenge, cellular-automata, game-of-life
---


title: Network wide reputation survey

text:
# Question
Title: Network wide reputation survey
Given a PPCG user's user ID, calculate how much times is their Each SE site reputation is from average reputation in the Stack exchange sites they have made accounts.

Let me explain, If someone's total network reputation (Total reputation in the stack exchange sites he has participated) is 10k, and if he has participated in 4 sites, then the average network wide reputation will be `2500`

And assume he/she participated in these 4 sites and has these reputation

```
Stack overflow 3000
Code golf and Coding challenges 2000
Mathematics 1500
Super User 4000

```

**So your final output should be:**

```
Stack overflow 1.2x
Code golf and coding challenges 0.8x
Mathematics 0.6x
Super User 1.8x

```

Here the `x` is to express how much times each site reputation is of the average, such as 2500\*1.2=3000

* (No obligation to floor the 1.2)
* (Order of the sites does not matter)
* (You can write the site names uppercase or lowercase or anything, that does not also matter)

Your code will be able to access internet freely.

Input is the **PPCG User ID**.

Trailing/leading whitespace allowed in output, Standard loopholes apply, this is shortest code wins.

# Test case

user 95516 (@rak1507, chosen him/her because have participated in less sites)

For average 943:

```
Code golf and coding challenges 3.57x
Stack overflow 0.21x
Meta stack exchange 0.107x
Puzzling 0.107x

```

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

```
(i,C)=>(p='https://codegolf.stackexchange.com',n=t=a=[],g=(u,c)=>require('https').get(u,r=>r.on('data',d=>i+=d,r.on('end',_=>c(r.headers.location)))))(p+'/users/'+i,l=>g(p+l,_=>g(s=i.match(/ht.+\/s[^"]+\d\/[^?]/)+0,l=>g(new URL(l,s)+'?tab=accounts',_=>i.replace(/unt-[^]+?\n *([\w&].+)[^]+?r".+?([\d,]+)/g,(_,s,r)=>a.push([s,r=r.split`,`.join``,t-=r,n--]))&&C(a.map(([s,r])=>s.replace(/&#?(.+?);/g,(_,m)=>String.fromCharCode('0'+m|0||38))+` ${r/t*n}x`).join`
`)))))

```

Function which accepts a the ID as a string and returns the result to a callback.

I tried to make it robust and it should work for any profile as of time of submission with one possible exception: the accounts tab on the network profile contains a profile summary which can be edited by the user so it's possible for a user to write something to fool the regex in their bio.

## Explanation

```
(i,C)=>(p='https://codegolf.stackexchange.com',
// n = count of sites, t = total sum of reputation, a = array of (siteName, rep) tuples
n=t=a=[],
// Function which performs a GET request.
// The body is appended to `i` and the callback is called with the location header.
g=(u,c)=>require('https').get(u,r=>r.on('data',d=>i+=d,r.on('end',_=>c(r.headers.location))))
// Load the user's PPCG profile.
)(p+'/users/'+i,l=>
// Since we only provided the ID and not the name in the URL, it will return a 301 redirect.
// Load the redirect.
g(p+l,_=>
// The first URL on the body to match this regex is the network profile URL of the user.
// Note that this comes before the custom content in the profile
// (which could contain other network profile URLs).
// This request will result in a 301 if the user's name is different on the
// network profile than PPCG, so the first character plus 0 will force a redirect
// because display names are a minimum of 3 characters long.
g(s=i.match(/ht.+\/s[^"]+\d\/[^?]/)+0,l=>
// Load the accounts tab of the network profile.
g(new URL(l,s)+'?tab=accounts',_=>
// Find each site and reputation count.
i.replace(/unt-[^]+?\n *([\w&].+)[^]+?r".+?([\d,]+)/g,
// Remove the commas from the rep value, populate `a` and add them up for the average.
// decodeURIComponent is annoyingly long but there's no shorter way to correctly display
// sites like the Japanese site which is made solely of URI encoded characters.
(_,s,r)=>a.push([s,r=r.split`,`.join``,t-=r,n--]))&&
// Calculate and print the results.
// There is a lot of bytes dedicated here to unescaping HTML entities because
// unfortunately there's no easy way to correctly display sites like the Japanese site
// which is made solely of HTML encoded characters.
// As far as I can tell the only escapes used in site names are the `&#xXX` style
// and `&`.
C(a.map(([s,r])=>s.replace(/&#?(.+?);/g,(_,m)=>String.fromCharCode(0+m|0||38))+` ${r/t*n}x`).join`
`)))))

```
> 4 votes

# Answer
# PowerShell, 331 bytes

There are some issues with this method, but ones that I'm not sure can be resolved without reworking the problem to use the API rather than web scraping - hidden sites will not be counted via this method, and the user editable portion of the profile page could potentially contain something which fools my Regex.

Definitely room for golfing improvement here, especially in the regex; I will revisit this when I have the time. Here are the user IDs I used for validating: 92116, 99902, 66833, 95516

```
$x=(iwr "codegolf.stackexchange.com/users/$args")-match"https://\w+\.\w+/\w+/\d+/[^""]*(?="")"
$a=(iwr($Matches[0]+"?tab=accounts")|Select-String "2>\s*<a[^>]+>([^<]+)<(.|\n)*?>([0-9,]+)<"-AllMatches).Matches|%{@{n=$_.Groups[1].Value.Trim();r=$_.Groups[3].Value-replace","}}
$a|?{$r+=[Int]$_.r}
$a|%{$_.n+" $($_.r/($r/$a.Count))x"}

```

No TIO, because internet :(

### Example

**Input**:

```
66833      # This is user ChartZ Belatedly, who recommended their ID as a test case.

```

**Output**:

```
Code Golf 24.5032822757112x
Movies & TV 2.72347840181538x
Meta Stack Exchange 1.07869357322311x
Stack Overflow 0.615122781424751x
Science Fiction & Fantasy 0.571440149120674x
Code Review 0.343220682389173x
Interpersonal Skills 0.323608071966934x
Mathematics 0.314693249047735x
Area 51 0.212172785476943x
MathOverflow 0.161358294837507x
English Language & Usage 0.12748196774455x
German Language 0.116784180241511x
Stack Apps 0.0989545344031121x
Computer Science Educators 0.0989545344031121x
Role-playing Games 0.0900397114839128x
Academia 0.0900397114839128x
Mathematica 0.0900397114839128x
Mi Yodeya 0.0900397114839128x
Philosophy 0.0900397114839128x
Arqade 0.0900397114839128x
The Workplace 0.0900397114839128x
Database Administrators 0.0900397114839128x
Puzzling 0.0900397114839128x
Super User 0.0900397114839128x
Physics 0.0900397114839128x
Chemistry 0.0900397114839128x
Personal Finance & Money 0.0900397114839128x
Quantum Computing 0.0900397114839128x
Coffee 0.0900397114839128x
3D Printing 0.0900397114839128x
Medical Sciences 0.0900397114839128x
Economics 0.0900397114839128x
Politics 0.0900397114839128x

```

## Bonus, PowerShell, 347 bytes

This version uses the same metric as SE, in which sites where the user has less than 200 rep are not counted.

```
$x=(iwr "codegolf.stackexchange.com/users/$args")-match"https://\w+\.\w+/\w+/\d+/[^""]*(?="")"
$a=(iwr($Matches[0]+"?tab=accounts")|Select-String "2>\s*<a[^>]+>([^<]+)<(.|\n)*?>([0-9,]+)<"-AllMatches).Matches|%{@{n=$_.Groups[1].Value.Trim();r=[Int]($_.Groups[3].Value-replace",")}}|?{$_.r-ge200}
$a|?{$r+=$_.r}
$a|%{$_.n+" $($_.r/($r/$a.Count))x"}

```

### Example

**Input**:

```
66833      # This is user ChartZ Belatedly, who recommended their ID as a test case.

```

**Output**:

```
Code Golf 7.18671741088289x
Movies & TV 0.798785625054473x
Meta Stack Exchange 0.316376630545307x
Stack Overflow 0.180413119897737x
Science Fiction & Fantasy 0.1676011737021x
Code Review 0.100665291537143x
Interpersonal Skills 0.094912989163592x
Mathematics 0.0922983062665233x
Area 51 0.0622294529502339x

```
> 2 votes

# Answer
# Python 3 \+ Selenium \+ Firefox, 301 bytes

```
from selenium.webdriver import*
D=Firefox()
D.get("http://codegolf.stackexchange.com/users/"+input())
F=D.find_elements_by_css_selector
F('.communities a')[-1].click()
s=[int(j.text[:~9].replace(',',''))for j in F('.account-stat')[::4]]
for i,j in zip(F('h2'),s):print(i.text,str(j*len(s)/sum(s))+'x')

```

This program did not close the Firefox window after execute, you need to close it manually. Input from stdin, output to stdout. You should completely ignore the Firefox window.

```
from selenium.webdriver import*
# start Firefox WebDriver
D=Firefox()
# Ask input for user ID
# Open profile page on CodeGolf.SE
D.get("http://codegolf.stackexchange.com/users/"+input())
# Store find_elements_by_css_selector to save bytes
F=D.find_elements_by_css_selector
# `.communities` is the left pannel of user's communities
# the last link (`a`) in it is accounts tab of user profile on SE
# click to follow the link
F('.communities a')[-1].click()
# `.account-stat` selects all user stat cells
# 4 cells each row, 1st cell each row is reputation, so we [::4]
# the cell contains text like `12,345 reputation`
# We only keep digits and convert to int
s=[int(j.text[:~9].replace(',',''))for j in F('.account-stat')[::4]]
# `h2` selects all nodes for sites name
# for each sites name and its reputation, output as required
for i,j in zip(F('h2'),s):print(i.text,str(j*len(s)/sum(s))+'x')

```

Not much rooms for golfing here. Only golfed things would be `F=D.find_elements_by_css_selector` and `[:~9]`, IMO.
> 2 votes

---
Tags: code-golf, math, stack-exchange-api
---


title: Is q a quadratic residue of n?

text:
# Question
Title: Is q a quadratic residue of n?
Given two inputs `q n` determine if `q` is a quadratic residue of `n`.

That is, is there an `x` where `x**2 == q (mod n)` or is `q` a square mod `n`?

**Input**

Two integers `q` and `n`, where `q` and `n` are any integers `0 <= q < n`.

**Output**

A truthy or a falsey.

Optionally, print any (or all) `x` that is `x**2 == q (mod n)`

**Examples**

```
>>> quadratic_residue(1, 5)
True
>>> quadratic_residue(3, 8)
False
>>> quadratic_residue(15, 22)
True

```

**Rules**

Your code must be a program or a function. The inputs can be in any order. This is code golf, so **shortest code in bytes wins.**

If anything is unclear or otherwise needs fixing, please let me know.

**Bonuses**

* 2-byte bonus if your function accepts `q` as any arbitrary integer.

## Catalogue

```
var QUESTION_ID=65329;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='<h1>'+c.body.replace(OVERRIDE_REG,'')+'</h1>'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery('<a>'+lang+'</a>').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}
```

```
body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table>
```

# Answer
> 7 votes
# Pyth, 9 bytes

```
}Em%*ddQQ

```

Try it online: Demonstration or Test Suite

### Explanation:

```
}Em%*ddQQ   implicit: Q = first input number
  m     Q   map all numbers d of [0, 1, ..., Q-1] to:
    *dd       d*d
   %   Q      mod Q
            this gives the list of all quadratic residues
 E          read another input number
}           check, if it appears in the list of quadratic residues

```

# Answer
> 8 votes
## Mathematica, 25 bytes

```
AtomQ@PowerMod[#,1/2,#2]&

```

Mathematica, being Mathematica, naturally has a builtin for calculating modulo nth roots, via `PowerMod`. If a solution exists the smallest feasible solution is returned, otherwise the original expression (plus a message).

To get an actual truthy/falsy output we pass the result to `AtomQ`, which checks whether an expression can be broken down. Integers are atomic, returning `True`, whilst the non-atomic `PowerMod[q,1/2,n]` returns `False`

Thanks to @MartinBüttner for golf tips and function hunting with me.

# Answer
> 8 votes
# Par, ~~11~~ 9 bytes

```
✶X[²x%)↔,

```

Each character uses just one byte; see here.

## Explanation

```
✶              ## Read two numbers
X              ## Assign second to x
[              ## Map
 ²             ## Square
 x%            ## Mod x
)              ##
↔              ## Swap
,              ## Count

```

Removed two bytes thanks to Jakube.

# Answer
> 7 votes
# LabVIEW, ~~16~~ 15 Equivalent bytes

Counted according to my meta post.

# Answer
> 5 votes
# Matlab, 29

This function squares all numbers from 0 to n and checks whether a square minus q is zero mod n.

```
@(q,n)any(~mod((0:n).^2-q,n))

```

# Answer
> 5 votes
# Haskell, 31 bytes

Saved 3 bytes thanks to Martin Büttner.

```
q#n=elem q[mod(x^2)n|x<-[1..n]]

```

# Answer
> 4 votes
# Prolog (SWI), 34 bytes

**Code:**

```
Q*N:-between(0,N,X),X*X mod N=:=Q.

```

**Explanation:**
Checks if any square between **0** and **N** leaves **Q** when divided by **N**.

**Example:**

```
3*8.
false

15*22.
true

```

Try it online here

# Answer
> 4 votes
## CJam, 11 bytes

```
{_,2f#\f%&}

```

This unnamed block expects `q n` on the stack and leaves `[q]` on the stack as a truthy value or `""` as a falsy value.

Test it here.

Credits to Sp3000 who also came up with this solution but "couldn't be bothered posting".

### Explanation

```
_,  e# Duplicate n and turn into range [0 1 ... n-1]
2f# e# Square each element in the range.
\f% e# Take each element in the range modulo n.
&   e# Set intersection with q to check if any square yields q (mod n).

```

# Answer
> 4 votes
# J, 9 bytes

```
e.]|i.^2:

```

Usage:

```
   1 (e.]|i.^2:) 5
1
   3 (e.]|i.^2:) 8
0
   15 (e.]|i.^2:) 22
1

```

Explanation:

```
e.]|i.^2:
    i.    [0..N-1]
      ^   to the power of
       2: 2 (constant 2 function)
  ]|      mod N
e.        contains Q? (0/1 result)

```

Some J mechanics trivia:

Functions are grouped by 3 iteratively from the right and if there is one left, as in our case (`e. (] | (i. ^ 2:))`), the grouped part is called with the right argument (`N`) and the left out function (`e.`, "contains") called with the original left argument (`Q`) and the result of the grouped part.

(`e.]|i.*i.` and `e.]|2^~i.` also solves the problem with the same length.)

Try it online here.

# Answer
> 3 votes
# Mathematica, 27 bytes

```
PowerModList[#,1/2,#2]!={}&

```

Usage:

```
In[1]:= PowerModList[#,1/2,#2]!={}&[1,5]

Out[1]= True

```

# Answer
> 3 votes
# Javascript ES6, 42 bytes

```
(q,n)=>[...Array(n)].some((x,y)=>y*y%n==q)

```

Credits to @apsilers for serious bytes saved!

# Answer
> 2 votes
## Seriously, 20 bytes

```
,;R@,;╗@%╝`ª╜@%╛=`MΣ

```

Takes input on two lines: `q`, then `n`. Outputs a `0` if `q` is not a quadratic residue of `n`, else a positive number representing how many `x` in `[1, q]` (inclusive) satisfy `x^2 = q (mod n)`.

Try it online (permalinks are having more issues, but you can copy and paste the code into a blank page in the meantime)

Explanation:

```
,;R      get q input, duplicate, push range(1, q+1)
@,;╗     move the list to the back of the stack, get n input, dupe, save in reg 0
@%╝      calculate q mod n and save to reg 1
`ª╜@%╛=` push this function:
  ª╜@%     square top of stack, push reg 0 value (n), swap, and mod
  ╛=       push reg 1 value (q mod n), compare equality (1 if equal else 0)
MΣ       map the function across the range, add results

```

# Answer
> 2 votes
# Python 3, ~~41~~ 40 bytes

Takes `q` and `n` and determines if `q` is in a list of squares from `0` squared to `n-1` squared.

```
lambda q,n:q in[i*i%n for i in range(n)]

```

# Answer
> 2 votes
# Ruby, 33 31 bytes

Saved two bytes thanks to Vasu Adari.

```
->q,n{(1..n).any?{|e|e*e%n==q}}

```

As usual Ruby's not going to beat any of the golfing languages, but it makes a good showing here.

# Answer
> 1 votes
# Julia, 30 bytes

```
f(q,n)=q∈[i^2%n for i=0:n-1]

```

This is a function `f` that accepts two integers and returns a boolean.

Ungolfed:

```
function f(q::Integer, n::Integer)
    # Generate an array of quadratic residues
    x = [i^2 % n for i = 0:n-1]

    # Determine whether q is one of these values
    return q ∈ x
end

```

# Answer
> 1 votes
# , 13 chars / 25 bytes

```
⟦Ѧí]ĉ⇀_²%í≔î)

```

`Try it here (Firefox only).`

# Answer
> 1 votes
# JavaScript (ES6), 43 bytes

```
(q,n)=>eval('for(x=n,r=0;x--;)r+=x*x%n==q')

```

## Explanation

```
(q,n)=>
  eval(`              // eval allows us to use a for loop without {} or return
    for(x=n,r=0;x--;) // iterate over all possible values of x
      r+=x*x%n==q     // r = the number of matching x values
  `)                  // implicit: return r

```

## Test

```
q = <input type="number" id="Q" /><br />
n = <input type="number" id="N" /><br />
<button onclick="result.innerHTML=(

(q,n)=>eval('for(x=n,r=0;x--;)r+=x*x%n==q')

)(+Q.value,+N.value)">Go</button><pre id="result"></pre>
```

# Answer
> 1 votes
# Japt, 10 bytes

```
Vo d_²%V¥U

```

My first official Japt golf ever! Thanks to @ETHProductions for saving a byte!

# Ungolfed / Explanation

```
Vo d_  ²  %V¥ U
Vo dZ{Zp2 %V==U}  // implicit: U,V = inputs
Vo                // Create a range from 0 to n-1
   dZ{         }  // Check if any element Z in the range satisfies the condition:
       Zp2        // Is Z squared...
           %V     // modulo n...
             ==U  // equal to q?
                  // implicit output

```

Try it online!

# Answer
> 0 votes
# C# 6 (.Net Framework 4.6) in LinqPad, 60 Bytes

```
bool b(int q,int n)=>Enumerable.Range(1,n).Any(y=>y*y%n==q);

```

# Answer
> 0 votes
# Milky Way 1.0.2, 41 bytes

```
:>&{~1-:2h<:>n>;:>;<<b?{_a0_^}~;?{_0_1}}!

```

This expects `q` and `n` to be solely on the stack. It outputs a `1` or `0` for the truth and false values, respectively.

# Answer
> 0 votes
# Pari/GP, 25 bytes

```
(q,n)->issquare(Mod(q,n))

```

Try it online!

# Answer
> 0 votes
# JavaScript (Node.js), 33 bytes

```
q=>n=>f=(t=n)=>t&&f(t-1)|t*t%n==q

```

Try it online!

Why no one do this

# Answer
> 0 votes
# C (gcc), ~~49~~ 48 bytes

*-1 byte thanks to ceilingcat*

```
f(q,n,i,a){for(i=n;i--;)a=i*i%n==q?:a;return a;}

```

Try it online!

Does a simple for loop, brute forcing the squares.

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