title: Which side has more?

text:
# Question
Title: Which side has more?
The challenge is to golf a program when given a string composed of any number of asterisks, then a comma, than any number of asterisks, say which side has more.

The asterisk-strings can be empty.

# Output

`0` for ties.

`1` for the left.

`2` for the right.

# Examples

Input: `***,****` Output: `2`

Input: `***,` Output: `1`

Input: `***,***` Output: `0`

Input: `,` Output: `0`

# Scoring

This is . Shortest answer wins.

# Answer
# Python 2, 25 bytes

```
lambda s:cmp(s[::-1],s)%3

```

Try it online!
> 19 votes

# Answer
# ///, ~~60~~ ~~64~~ 28 bytes

```
/*,*/,//,*/2//*,/1//,/0//*//

```

Try it online!

Found out most of my program was unnecessary, -32 bytes.

I made this program when I was learning the language, and decided to post it as a question.
> 8 votes

# Answer
# 05AB1E, 6 bytes

```
Â.S(3%

```

**Try it online!**

### How?

Note that `','` is greater than `'*'`.

```
Â.S(3%
Â      - input, reversed(input) (say a, b)
 .S    - compare: 1 if a > b; -1 if a < b; 0 if a = b
   (   - negate
    3  - push three
     % - modulo

```
> 7 votes

# Answer
# C (gcc), ~~65~~ \\$\cdots\\$ ~~54~~ 47 bytes

Saved a 10 bytes thanks to dingledooper!!!
Saved a byte thanks to ceilingcat!!!
Saved 7 bytes thank to l4m2!!!

```
f(c){c=strlen(c)-strspn(c,"*")*2;c=c>1?2:c!=1;}

```

Try it online!
> 6 votes

# Answer
# Gema, 20 characters

```
*,*=@cmps{*;*;2;0;1}

```

Sample run:

```
bash-5.0$ echo -n '***,****' | gema '*,*=@cmps{*;*;2;0;1}'
2

```

Try it online! / Try all test cases online!
> 4 votes

# Answer
# Bash \+ Standard utilities, 28 bytes

```
dc<<<1`tr *, 1d`1-dd*v/3+3%p

```

Try it online!
> 4 votes

# Answer
# sed -E, 30 bytes

```
s/(.*),\1/0/;s/.+0/1/;s/0.+/2/

```

Try it online!
> 4 votes

# Answer
# K (ngn/k), ~~17~~ 16 bytes

**Solution:**

```
{2/c<|c:#'","\x}

```

Try it online!

**Explanation:**

```
{2/c<|c:#'","\x} / the solution               -> e.g. 1         e.g. 2     e.g. 3
{             x} / lambda taking implicit 'x' -> "***,****"     "***,"     "***,***"
          ","\   / split string on comma      -> ("***";"****") ("***";"") ("***";"***")
        #'       / count length of each       -> 3 4            3 0        3 3
      c:         / store as c                 -> 3 4 (noop)     3 0        3 3
     |           / reverse it                 -> 4 3            0 3        3 3
   c<            / is c less than this?       -> 1 0            0 1        0 0
 2/              / convert from base 2        -> 2              1          0

```

**Extra:**

* **13 bytes** if it doesn't need to be a function `2/c<|c:#'","\`
> 4 votes

# Answer
# Jelly,  ~~7~~  6 bytes

```
,ṚMḄ2c

```

A monadic Link accepting a list of characters which yields an integer in \\$\[0,2\]\\$.

**Try it online!**

### How?

Note that `','` is greater than `'*'`.

```
,ṚMḄ2c - Main Link: s                     e.g.:  "*,"          ",*"          ","
 Ṛ     - reverse (s)                             ",*"          "*,"          ","
,      - pair (s) with (that)                    ["*,",",*"]   [",*","*,"]   [",",","]
  M    - indices of maximal values               [2]           [1]           [1,2]
   Ḅ   - convert from base 2, say x              2             1             4
    2  - two                                     2             2             2
     c - (2) choose (x) - i.e. binomial(2,x)     1             2             0
       - implicit print (a list with a single element prints the element)

```
> 3 votes

# Answer
# JavaScript (ES6),  ~~26~~  25 bytes

*Saved 1 byte thanks to @tsh*

Taking advantage of the looser output rules: this versions returns `0` for ties, `undefined` for left or `*` for right.

```
s=>(s+0)[s.search`,`*2+1]

```

Try it online!

---

# JavaScript (ES6), 31 bytes

Returns a Boolean value instead of **0** / **1**.

```
s=>([a,b]=s.split`,`,a<b?2:a>b)

```

Try it online!
> 3 votes

# Answer
# Perl 5 \+ `-pl`, 21 bytes

```
/,/;$_=$`cmp$';s;-1;2

```

Try it online!
> 3 votes

# Answer
# APL (Dyalog Unicode), ~~20~~ ~~19~~ 13 bytesSBCS

Whooping -6 thanks to @Bubbler.

```
(⊃3|⍒-⍋)⊂,⊂∘⌽

```

Try it online! This should be golfable as there are some things I am repeating there but I am not sure how to do it yet.

## APL (Dyalog Unicode), 19 bytesSBCS

```
{3|×1+(2×⍵⍳',')-≢⍵}

```

Try it online!
> 3 votes

# Answer
# APL (Dyalog Extended), 9 bytes

```
(⊥⍋|⍒)⊢⍮⌽

```

Try it online!

### How it works

```
(⊥⍋|⍒)⊢⍮⌽  ⍝ left '*,' | right ',*' | equal ','
      ⊢⍮⌽  ⍝ Length-2 nested vector of self and reverse
  ⍋        ⍝ Grade up; order of indices to make it ascending-sorted
           ⍝ 1 2       | 2 1        | 1 2
    ⍒      ⍝ Grade down; order of indices to make it descending-sorted
           ⍝ 2 1       | 1 2        | 1 2
   |       ⍝ Right modulo left
           ⍝ 0 1       | 1 0        | 0 0
 ⊥         ⍝ From base 2 to integer
           ⍝ 1         | 2          | 0

```
> 3 votes

# Answer
# Ruby -nl, 18 bytes

```
~/,/;p ($`<=>$')%3

```

Try it online!

Takes input from STDIN. Compares the regex match groups `$`` and `$'`, which are set equal to everything on the left and right of the comma, respectively.
> 3 votes

# Answer
# Japt, ~~9~~ 8 bytes

Returns `true/false` instead of `1/0`

```
>Ô?2:U<Ô

>Ô?2:U<Ô     :Implicit input of string U
>            :Greater than
 Ô           :  U reversed
  ?          :If true
   2         :  Literal 2
    :        :Else
     U<Ô     :  U less than U reversed?

```

Try it

# Original, 9 bytes

5 bytes just to handle the I/O requirements :\

```
q, mÊrÎu3

```

Try it

```
q, mÊrÎu3     :Implicit input of string
q,            :Split on ","
   m          :Map
    Ê         :  Length
     r        :Reduce by
      Î       :  Sign of difference
       u3     :Positive modulo 3

```

If we could take a space delimited string as input then -2 bytes:

```
¸mÊrÎu3

```

If we could take an array as input then -1 more byte:

```
mÊrÎu3

```

And, if we could use any 3 distinct values for the output then -2 more bytes:

```
mÊrÎ

```
> 2 votes

# Answer
# Io, 51 bytes

Mod3 doesn't work in Io. Too bad.

```
method(x,I := -x compare(x reverse);if(I== -1,2,I))

```

Try it online!
> 2 votes

# Answer
# C (gcc), 83 bytes

```
x;f(char*z){char*Z,*W;for(Z=z;44-*Z++;);for(W=Z;*W++;)Z--;x=!!x*((x=z-Z+1)<0?1:2);}

```

Try it online!

# C (gcc), 58 bytes

```
f(z,Z)long z,Z;{Z-=strlen(Z=index(z,44))+z-1;z=Z<0?2:!!Z;}

```

Try it online!
> 2 votes

# Answer
# brainfuck, 57 bytes

```
-[>>,<--[>-<++++++]>-]<+[<<,]>[<-->+[<+>+]]-[<+>-----]<-.

```

Try it online!

It spreads `*` on the tape and checks if the second branch went past the first.
> 2 votes

# Answer
# Retina, ~~15~~ 13 bytes

```
(.*),\1$

\*+

```

Try it online!

If the right-hand-side has an equal or less number of `*`'s, then those `*`'s are removed from both sides, along with the `,`.

Then the number of runs of `*`'s are counted.
> 2 votes

# Answer
# Java 10, ~~74~~ ~~51~~ 50 bytes

```
s->(Long.signum(s.indexOf(44)*2-s.length()+1)+3)%3

```

-24 bytes thanks to *@OlivierGrégoire*.

Try it online.

**Explanation:**

```
s->{                          // Method with String parameter and long return-type
  Math.signum(                //  Take the signum of:
   s.indexOf(44)              //   The index of ',' (codepoint 44)
   *2                         //   multiplied by 2
   -s.length()                //   Subtract the entire length of the input
   +1                         //   And add 1
  +3)                         //  Then increase that result by 3
  %3                          //  And take modulo-3 on it

```
> 2 votes

# Answer
# Excel, ~~64~~ ~~63~~ 62 bytes

```
=IF(LEN(A1)+1=2*FIND(",",A1),0,IF(LEN(A1)<2*FIND(",",A1),1,2))

```

-1 byte thanks to Dominic van Essen -1 byre thanks to Chronocidal
> 2 votes

# Answer
# Ruby -n, ~~21~~ 20 bytes

```
p (~/,/*2<=>~/.$/)%3

```

Try it online!
> 2 votes

# Answer
# , ~~19~~ 18 bytes

```
3|i.&','*@--:@<:@#

```

Try it online!

### How it works

```
3|i.&','*@--:@<:@#
           -:@<:@# halved (length-1) of list
                   (where , would be in a balanced list)
  i.&','           position of the ,
        *@-        signum'd difference between both
3|                 mod 3

```

## Alternative version, 19 bytes

This inserts `-` and `+` between the bit mask of the string: `**,* -> 1 1 0 1 -> 1 + (1 + (0 - 1)))` to get the difference between both sides. Then both signum and mod 3 like other solutions.

```
3|[:*'*'-`+@.[/@:=]

```

Try it online!

### How it works

```
3|[:*'*'-`+@.[/@:=]
     '*'         =] '***,*' -> 1 1 1 0 1
        -`+@.[      a function that chooses - or + based on the left argument
              /@:   puts this function inbetween: 1+(1+(1+(0-1))) = 2
  [:*               signum: 2 -> 1
3|                  mod 3

```
> 2 votes

# Answer
# Befunge-93, 31 bytes

```
2>1~:1+v
p^_"$"2 0
.@^-","_$2\-

```

Try it online!

After initially pushing `2` to the stack, we push `1` for every `*` we encounter. After finding the `,`, we start popping them instead. When we run out of input we subtract the top of the stack from 2, resulting in the correct output values.
> 2 votes

# Answer
# Python 3, 56 60 bytes

-4 bytes thanks to math junkie

A third approach to this in python.

```
def f(x):a,b=x.split(',');return(1,0,2)[((a<b)-(a>b))+1]

```

Try it online!
> 2 votes

# Answer
# PHP, ~~55~~ ~~51~~ 47 bytes

```
fn($s)=>(3+(($a=explode(',',$s))[0]<=>$a[1]))%3

```

Try it online!

This is the best I have so far.. Gosh, longer than Java and C :O

EDIT: saved 4 bytes using value of `$v`, now shorter than C!

EDIT2: thanks a lot to 640KB for finding the finely elegant way to have the right numbers! -4 bytes

Much shorter with only distinct values instead of fixed numbers requirement:

# PHP, 39 bytes

```
fn($s)=>($a=explode(',',$s))[0]<=>$a[1]

```

Try it online!
> 2 votes

# Answer
## Excel,  ~~*44*~~  40 Bytes

```
=MOD(3-SIGN(1+LEN(A1)-2*FIND(",",A1)),3)

```

Finds the difference between Total Length + 1 and twice the position of the comma (Negative: Left; Zero: Tie; Positive: Right), use `SIGN` to convert these into `-1`, `0` and `1`. Then subtract this from 3 to give `4`/`0`/`2`, and take the Modulo Base 3 (`1`, `0`, `2`)

**Old version: 44 Bytes**

```
=MID(102,2+SIGN(1+LEN(A1)-2*FIND(",",A1)),1)

```

Finds the difference between Total Length + 1 and twice the position of the comma (Negative: Left; Zero: Tie; Positive: Right), use `SIGN` to convert these into `-1`, `0` and `1`, add 2 (`1`, `2`, `3`), and then use `MID` to take the first, second or third digit from `102`, respectively.

(Using `MID` saved 3 bytes over using `CHOOSE`)

I also experimented with a more maths-based approach (Multiply the Sign by 1.5, round it in the Positive direction with `CEILING`, then take the Absolute value), but that was 51 bytes instead.
> 2 votes

# Answer
# C (gcc) \- 67 bytes

This is a complete program and can be compiled with gcc. Input is the first command line argument and output is the exit status.

```
main(u,v)int**v;{u=strlen(*++v)-strspn(*v,"*")*2;exit(u>1?2:u!=1);}

```
> 2 votes

# Answer
# AWK `-F,`, ~~24~~ ~~22~~ 20+3 = 23 bytes

```
$0=$2>$1?2:($1>$2)""

```

Try it online!

*Edit: amazingly, golfing-away 2 bytes has actually made it (a bit) more readable*

Commented version:

```
$0=             # set the line to
    $2>$1 ?     # if $2>$1 (alphabetic comparison)
            2   # 2
    :           # otherwise
      ($1>$2)   # logical: 1 for $1>$2, 0 if not
             "" # append "" to force text output
                # otherwise awk won't print zero

# use default behaviour to print line

```
> 1 votes

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

```
lambda x:y.index(max(y))+1if len({*(y:=x.split(","))})>1else 0

```

Try it online!

I know that there is a shorter python solution already posted, but `cmp` doesn't exist in python 3. And don't bother trying to use bitwise operators to increment the value... it ends up being the same byte count.
> 1 votes

# Answer
# Ruby `-nlaF,`, 22 bytes

```
p ($F[0]<=>$F[1]||1)%3

```

Try it online!
> 1 votes

# Answer
# , ~~46~~ 45 bytes

(or 42 bytes using TRUE/FALSE instead of 1/0)

```
d=scan(,'',,,',');`if`(d[2]>d,2,1-!d[2]<d[1])

```

Try it online!

*Edit: -1 byte thanks to Giuseppe*
> 1 votes

# Answer
# Befunge-93, 48 bytes

```
>~:1+!#v_","-!#v_1+
^ p 0 +$#99 "-"<
+1`_: #<.@.

```

Try it online!

Adds one for each character it encounters, until it sees a `,`; in that case, the program self modifies to start subtracting one for each character it encounters. After seeing the end of the string, it checks whether the tally is 0, less than 0, or something else, and prints 0, 2 or 1 accordingly.
> 1 votes

# Answer
# SimpleTemplate, 66 bytes

This was quite fun!

Uses the most basic and naive approach, but the shortest one i can come up with as well.

```
{@ifargv.0 is equalargv.1}0{@elseifargv.0 is lowerargv.1}2{@else}1

```

---

That's quite a mess, lets explore it:

```
{@if argv.0 is equal to argv.1}
    {@echo 0}
{@else if argv.0 is lower than argv.1}
    {@echo 2}
{@else}
    {@echo 1}
{@/}

```

Should be self-explanatory.
A string is considered lower or higher depending on it's length and the characters on it are lower numerically (e.g.: `b > a`).

To turn into a function, all it needs is that the `{@echo}` is converted to `{@return}`.
Due to a bug (version 0.83), you can't return `0`, but you can return `"0"`.

---

You can test this on http://sandbox.onlinephpfunctions.com/code/683ec5b3e71cfb4f2bb78267125330b077248ef7
> 1 votes

# Answer
# , 38 bytes

```
sign(-diff(nchar(scan(,'',,,','))))%%3

```

Try it online!

Credit to Dominic van Essen for the `sep` argument to `scan()`, which I probably use less often than I should.

Ports the mod 3 approach found in a few other answers.
> 1 votes

# Answer
# Golfscript, 22 bytes

```
','/).@).@;@>@@>2 0if+

```

Try it online!

```
code   | explanation                      | example
','/   | split input at ',' into list     | "*,**" -> ["*", "**"]
).     | uncons from the right and double | ["*", "**"] -> ["*"] "**" "**"
@).    | put list on tos and do it again  | ["*"] "**" "**" -> "**" "**" [] "*" "*"
@;     | discard empty list               | "**" "**" [] "*" "*" -> "**" "**" "*" "*"
@>     | pull up a "right" and compare    | "**" "**" "*" "*" -> "**" "*" 0
@@     | pull up remaining elements       | "**" "*" 0 -> 0 "**" "*"
>2 0if | compare, if 1 replace with two   | 0 "**" "*" -> 0 2
+      | add the results                  | 0 2 -> 2

```
> 1 votes

# Answer
# Pyth, 16 bytes

```
%_._h.+mldcQ","3

```

Try it online!
> 1 votes

# Answer
# Python 3.8, 32 bytes

```
lambda s:((r:=s[::-1])!=s)+(r<s)

```

Try it online!

It is just one byte shorter than other Python 3.x

```
lambda s:(s[::-1]!=s)+(s[::-1]<s)

```
> 1 votes

# Answer
# 05AB1E, 14 bytes

```
[ÂQ#',¡ć@>,q}0

```

Try it online!

A weird program method, I know, but hey, it works! The `ÂQ` part is from this answer regarding 05AB1E golfing tips
> 0 votes

# Answer
# Octave / MATLAB, ~~41~~ 38 bytes

```
@(x)mod(sign(2*find(x-42)-nnz(x)-1),3)

```

Try it online!
> 0 votes

# Answer
# Charcoal, 18 bytes

```
⊞υθ⊞υ⮌θＩ⁻²↨⮌⌕Ａυ⌈υ²

```

Try it online! Link is to verbose version of code. Based on @JonathanAllen's answer. Explanation:

```
⊞υθ⊞υ⮌θ

```

Push the input and its reverse to the predefined empty list.

```
         υ  List of input and reverse
        ⌈   Take the maximum
     ⌕Ａυ    Get the indices of that in the list
    ⮌       Reverse the list of indices
   ↨      ² Convert from base 2
 ⁻²         Subtract from 2
Ｉ           Cast to string
            Implicitly print

```

When the input equals its reverse, both indices `0, 1` are returned, and `10` equals 2 in base 2, while if the left side has more then the maximum is at index `1`, while if the right side has more then the maximum is at index `0`. Subtracting this from 2 results in the desired value.
> 0 votes

# Answer
# T-SQL, 43 bytes

```
DECLARE @ varchar(max)='*,**'

PRINT(3+sign(charindex(',',@)*2+~len(@)))%3

```
> 0 votes

# Answer
# Stax, 9 7 bytes

```
üJN☺ïS♂

```

Run and debug it

Unpacked:

```
',/E|$3%

```

-2 bytes thanks to recursive
> 0 votes

# Answer
# PowerShell, 59 bytes

```
$a,$b=$i.split(',');if($a-gt$b){1}elseif($a-eq$b){0}else{2}

```

Try it online!
> 0 votes

# Answer
# FEU, ~~30~~ 26 bytes

Saved 4 bytes by using map instead of multiple substitutes

```
m/(\**),\1/0/\*+0/1/0\*+/2

```

Try it online!

## Explanation

```
m                          # Map mode, execute multiple substitutions
 /(\**),\1/0               # Replaces the balance of the sides with 0
            /\*+0/1        # If there are asterisks on the left of 0, replace with 1
                   /0\*+/2 # If there are asterisks on the right of 0, replace with 2

```
> 0 votes

---
Tags: code-golf
---


title: Sum of Fibonacci numbers

text:
# Question
Title: Sum of Fibonacci numbers
I found this task here.

> Given the ith (1\<=i\<=35) Fibonacci number F(i) calculate the sum of the ith till i+9th number F(i)+F(i+1)+...+F(i+9) and the last digit of the i+246th one F(i+246)

I have been trying to solve this using python and some tricks(Binnet's formula and a tricky recurrence):

```
 f=lambda n:((1+5**.5)**n-(1-5**.5)**n)/(2**n*5**.5)
 exec"n=input();print int(55*f(n)+88*f(n+1)+f(n+6)%10);"*input()

```

but I didn't yet managed to squeeze thought the give source code limit which is 111 and mine is 115,any hints how to improve my solution?

I am a rather newbie to python so any sort of help resulting in a successful solution will be much appreciated.

Thanks,

PS:After posting the same question in stackoverflow I thought that this should be more appropriate here as this site is precisely for Puzzles and Codegolf.

# Answer
# GolfScript 28 26 characters

Since the problem is here we might as well golf it. Anyone who plan on participating on spoj.pl better close their eyes while they read this.

```
~](;{11.@5+{.@+}*;.10%+n}%

```

It basically says: For all input, start with the numbers 11 and 11, do input+5 Fibonacci iterations, discard the highest of the two results, add itself mod 10 to the lowest result, done. As a formula this can be describes as `11*Fib(input+6) + (11*Fib(input+6)) mod 10`.

Why does this work? It is simply a condensed way of calculating two second identities in the same run, one could start at \[0 1\] and \[55 89\], do a run on both of the same length and subtract the first result from the second to get the sum of a series of 10 Fibonacci numbers, but one may as well do the subtraction on the initial sets, thus getting the set \[55 88\], that can be stepped back a few steps to \[11 11\] which is short to write.

The Fibonacci series mod 10 has a period of 60, so `Fib(i+246) mod 10 = Fib(i+6) mod 10`.
> 7 votes

# Answer
# Python, 99 98 93 characters

```
F=[0,1]
exec'F+=[F[-2]+F[-1]];'*300
exec'G=F[input():];print sum(G[:10])+G[246]%10;'*input()

```
> 4 votes

# Answer
# Perl, 78

```
sub F{$c=shift;$c>1?F($c-2)+F($c-1):$c}$_=<>;$x=F($_+11)-F($_+1);print$x+$x%10
```

This makes use of my observation that

* the sum of `F(i)` to `F(i+9)` is equal to `F(i+11) − F(i+1)` — proof:

```
   F(i) + F(i+1) + F(i+2) + F(i+3) + F(i+4) + F(i+5) + F(i+6) + F(i+7) + F(i+8) + F(i+9)
=      F(i+2)    +     F(i+4)      +     F(i+6)      +     F(i+8)      +    F(i+10)
=      F(i+2)    - F(i+3) + F(i+5) +     F(i+6)      +     F(i+8)      +    F(i+10)
=           -F(i+1)       +      F(i+7)              +     F(i+8)      +    F(i+10)
=           -F(i+1)       +              F(i+9)                        +    F(i+10)
=           -F(i+1)       +                           F(i+11)

```
* `F(i+246) mod 10` is equal to `(F(i+11) − F(i+1)) mod 10` (discovered by experimentation; no idea how to prove this)
> 3 votes

# Answer
# 05AB1E, 10 bytes

```
31Sb+ÅfÆ¤+

```

Port of *@Timwi*'s Perl answer, so make sure to upvote him as well!

Try it online or verify the first \\$\[0,n\]\\$ test cases.

A straight-forward implementation would be **11 bytes** instead:

```
9ÝƵ‘ª+Åf`θO

```

Try it online or verify the first \\$\[0,n\]\\$ test cases.

**Explanation:**

```
31S          # Push 31 as a list of digits: [3,1]
   b         # Convert both to a binary string: [11,1]
    +        # Add each to the (implicit) input-integer: [i+11,i+1]
     Åf      # Get the n'th Fibonacci number for each: [F(i+11),F(i+1)]
       Æ     # Reduce the pair by subtracting: F(i+11)-F(i+1)
        ¤    # Get its last digit (without popping)
         +   # And add it to the result
             # (after which it is output implicitly)

9Ý           # Push a list in the range [0,9]: [0,1,2,3,4,5,6,7,8,9]
  Ƶ‘         # Push compressed integer 246
    ª        # Append it to the list: [0,1,2,3,4,5,6,7,8,9,246]
     +       # Add each to the (implicit) input-integer:
             #  [i,i+1,i+2,i+3,i+4,i+5,i+6,i+7,i+8,i+9,i+246]
      Åf     # Get the n'th Fibonacci number for each
        `    # Pop the list, and push all values separated to the stack
         θ   # Pop the last number (the F(i+246)), and only leave its last digit
          O  # Sum all values on the stack
             # (after which the resulting sum is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Ƶ‘` is `246`.
> 0 votes

---
Tags: code-golf, math, integer, fibonacci
---


# Question
Title: Determine if a grid contains another grid
# Challenge

Create a function takes in two 2-dimensional arrays of characters (or strings if the programming language does not have characters as a datatype) as inputs: a and b. If your language does not support these inputs, you may use any other standard one-byte variable.

Your task is to determine if b contains a. If this is so, return true. Otherwise, return false.

# Sample Test Cases

```
a:

123
456
789

b:

123
456
789

```

should return true.

```
a:

code
golf

b:

thisis
code!!
golf!!
ohyeah

```

should return true.

```
a:

abcd
efgh
ijkl

b:

abcdef
ghijkl
mnopqr

```

should return false.

```
a:

abc
def

b:

1abc2
3def4
5ghi6

```

should return true

```
a:

ab
cd

b:

#ab##
##cd#

```

should return false

This is so least bytes wins.

# Answer
# Brachylog (v2), 4 bytes

```
s\s\

```

Try it online!

Most easily run as a full program, as usual for a , with *a* specified as a command-line argument, *b* on standard input. The question asks for a function, and the program also works as a function, with *b* on the left, *a* on the right, and output via producing an exception if and only if the decision is false.

## Explanation

```
s\s\
s     a substring of rows of {the left input}
 \…\  assert rectangular; swap row and column operations
  s   a substring of <s>rows</s> columns of {the above matrix}
      {implicit} assert that the result can be {the right input}

```

The "assert rectangular" is, obviously, pointless, as the question guarantees that already. The rest of the program does the grid-finding for us by identifying a substring of the rows and of the columns, i.e. a submatrix.

## Meta-discussion

We've had a very similar question before; I'd expect most answers to one question to be modifiable into answers to the other. I think this is the neater version of it, though.
> 9 votes

# Answer
# Python 2, 67 bytes

```
f=lambda a,b,r=4:b*r and f(a,b[1:],r)|f(a,zip(*b)[::-1],r-1)or a==b

```

Try it online!

Takes input as lists of tuples of characters.

Tries all sub-grids of `b` and checks if `a` is among them. The sub-grids are generated by recursively branching on either removing the first row of `b` or rotating it 90 degrees. After exactly four rotations, checks if the trimmed down `b` is equal to `a`.
> 7 votes

# Answer
# , ~~21~~ ~~15~~ ~~8~~ 7 bytes

```
1#.,@E.

```

Try it online!

*-7 bytes thanks to Bolce Bussiere*

## original answer

## , ~~21~~ 15 bytes

```
<@[e.&,$@[<;.3]

```

Try it online!

*-6 bytes thanks to FrownyFrog*

## how

* `<@[` boxed left arg
* `$@[<;.3]` all rectangles in the right arg with the same shape as the left arg
* now pass those as the left and right arg to...
* is the left arg an elm of the right arg, after flattening both `e.&,`
> 5 votes

# Answer
# Charcoal, 26 bytes

```
⌈⭆η⭆ι⁼θＥ✂ηκ⁺Ｌθκ¹✂νμ⁺Ｌ§θ⁰μ¹

```

Try it online! Link is to verbose version of code. Heavily based on my answer to Count the contiguous submatrices, the only difference being that instead of taking the sum of the matches I take the maximum, and because of the implicit string conversion due to the use of  the result is already a string which saves a byte.
> 5 votes

# Answer
# Wolfram Language (Mathematica), ~~46~~ 37 bytes

```
Partition[#2,Dimensions@#,1]~FreeQ~#&

```

Try it online!

Returns `True` if b does *not* contain a, and `False` if it does.
> 4 votes

# Answer
# 05AB1E, 10 bytes

```
øŒεøŒI.å}à

```

Takes `b` as first input, `a` as second. Both inputs as character-matrices.

Port of *@Mr.Xcoder*'s 05AB1E answer for this related challenge, so make sure to upvote him!

Try it online or verify all test cases.

**Explanation:**

```
øŒ          # Get the sublists of every column of the (implicit) input `b`
  ε         # Map each list of sublists to:
   øŒ       #  Get the sublists of every column again
            #  (now we have all sub-matrices of `b`)
     I.å    #  Check if the second input `a` is in this list of sub-matrices
        }à  # After the map: check if any are truthy by taking the maximum
            # (which is output implicitly as result)

```
> 4 votes

# Answer
## JavaScript (ES6), ~~131 112~~ 105 bytes

**105 bytes:**

```
f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&x.some((c,j)=>n.every((l,z)=>(m[i+z]+'').indexOf(l,j)==2*j)))

```

Try it online!

Changes:

* `m[i]` into `x` and `n[z]` into `l`: *Totally forgot that these variables were already instanciated*
* `&&` into `&`: *Both sides of the operator are already booleans so a bitwise operator will work*

---

**112 bytes:**

```
f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&&m[i].some((c,j)=>n.every((l,z)=>(m[i+z]+'').indexOf(n[z],j)==2*j)))

```

Try it online!

Changes:

* `map((c,j)=>{...}).some(s=>s)` into `some((c,j)=>{...})`: *Redundancy*
* `m[i+z].join()` into `m[i+z]+''`: *A shorter way to convert the array into a string*
* `indexOf(n[z].join(),j)` into `indexOf(n[z],j)`: *The* `indexOf` *method already converts* `n[z]` *into a string*

---

**131 bytes:**

```
f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&&m[i].map((c,j)=>n.every((l,z)=>m[i+z].join().indexOf(n[z].join(),j)==2*j)).some(s=>s))

```

Try it online!

Readable:

```
function f (m, n) {
  return m.some((x, i) => {
    return i <= m.length - n.length
      && m[i].map((c, j) => {
        return n.every((l, z) => {
          return m[i + z].join().indexOf(n[z].join(), j) == 2 * j
        })
      })
        .some(s => s)
  })
}

```

Instead of compairing individual values, I checked if the lines from grid N were included in the lines of grid M, and if so, at which indexes. If all of the lines are included starting from the same index then the grid N is contained in the grid M.
> 4 votes

# Answer
# APL (Dyalog Unicode), 3 bytes

```
1∊⍷

```

Try it online!

It's like this question was made for APL!

## Explanation

```
  ⍷   ⍝ 'find', returns a matrix with '1' in all positions where the first matrix is contained in the second
1∊    ⍝ checks if '1' is a member of this matrix

```
> 4 votes

# Answer
# Python 2, ~~106~~ ~~118~~ 113 bytes

```
lambda a,b,L=len:any(sum(A==B[j:j+L(A)]for A,B in zip(a,b[i:]))==L(a)for i in range(L(b))for j in range(L(b[0])))

```

Try it online!
> 3 votes

# Answer
# PowerShell, ~~71~~ ~~102~~ ~~85~~ 98 bytes

thanks @Jo King; test cases added.

```
param($a,$b)!!($a|%{$p=[regex]::Escape($_)
$b|sls $p -a -ca|% m*}|group index|?{"$a"-ceq$_.Group})

```

Try it online!

Less golfed:

```
param($a,$b)

$matches = $a|%{
    $pattern = [regex]::Escape($_)
    $b|Select-String $pattern -AllMatches -CaseSensitive|% Matches
}

$relevantGroupsByMatchPosition = $matches|group index|?{
    "$a"-ceq$_.Group  # the '$_.Group' contains matches in source order
                      # -ceq is case sensitivity equation operator
                      # -ceq performs an implicit conversion to the left operand type
}

!!($relevantGroupsByMatchPosition)  # true if the variable is not $null

```
> 2 votes

# Answer
## Javascript, 150 bytes

```
f=(a,b)=>{_='length';for(r=i=0;i<=b[_]-a[_];i++)for(j=0;j<=b[0][_]-a[0][_];j++){u=0;a.map((l,y)=>l.map((c,x)=>u=u||b[i+y][j+x]!=c));r=r||!u;}return r}

```

Try it online
> 1 votes

# Answer
# JavaScript (V8), 81 bytes

```
(m,n)=>m[s='some']((a,i)=>a[s]((b,j)=>!n[s]((c,k)=>c[s]((d,l)=>m[i+k][j+l]!=d))))

```

Try it online!
> 0 votes

# Answer
# Octave/Matlab, ~~47~~ ~~45~~ ~~44~~ 40/38 bytes

* -2 Default output to `ans`
* -1 Trace of inner product is the sum of the squares of the elements. Therefore use `trace(a*a')` instead of `sum(a(:).^2)`
* -4 Use `find` instead of `any(any(...))` since any non-zero output of `find` is considered as a logical truth, and Matlab/Octave is 1-indexed.
* -2 but only in Matlab, since the second argument to `xcorr2` does not need to be made numeric and is implicitly converted to whatever is the first argument's type.

## Octave

```
@(a,b)find(xcorr2(a*1,b*1)==trace(a*a'))

```

Try it online!

## Matlab

```
@(a,b)find(xcorr2(a*1,b)==trace(a*a'))

```

This works by computing the 2D cross-correlation function of matrices `a` and `b` (in a numeric from), and then checking whether an entry corresponding to a perfect overlap exists.
> 0 votes

---
Tags: code-golf, string, decision-problem, grid, subsequence
---


title: A subset of Verbal arithmetic

text:
# Question
Title: A subset of Verbal arithmetic
Implement a verbal arithmetic solver of several same sequence of numbers added together:

```
  TWO
+ TWO
-----
 FOUR

  REPEAT
  REPEAT
  REPEAT
+ REPEAT
--------
 ANDSTOP

  SPEED
+ SPEED
-------
  KILLS

```

There are some restrictions: each letter should represent different digits, and no letter can be zero.

Implement the solver as a function of the operands, the sum and number of repetitions returns a list of solutions (solution: the tuple of resulting operand and sum). For example:

```
f(['T','W','O'], ['F','O','U','R'], 2) == [(734, 1468)]

```

You do not need to represent variables as letters, and you do not need to use a hash in the solution. Brute-force search allowed.

Shortest code wins.

# Answer
## Mathematica

Spaces added for clarity. Not much golfed.
Need to use greek letters because the input letters are treated as symbols.

```
F[σ_ ,ρ_ ,τ_]:=
 (φ = FromDigits;
 Rest@Union[
   If [ τ * φ@σ == φ@ρ, {φ@σ,φ@ρ} ] /.#& /@
 (Thread[Rule[ σ ∪ ρ , # ] ] & /@ Permutations[Range@9, {Length[σ ∪ ρ] }])])

```

Usage:

```
F[{r,e,p,e,a,t},{a,n,d,s,t,o,p},3]
{{819123,2457369}}

F[{s,p,e,e,d},{k,i,l,l,s},3]
{}

F[{t,w,o},{f,o,u,r},2]
{{734,1468},{836,1672},{846,1692},{867,1734},{928,1856},{938,1876}}

```

It didn't find any solution for the SPEED+SPEED+SPEED = KILLS ... is that a bug?

**Edit**

Allowing zero, it finds the following solutions for the SPEED+SPEED+SPEED = KILLS equation:

```
{{10887,32661},{12667,38001},{23554,70662},
 {23664,70992},{25334,76002},{26334,79002}}

```

**Edit**

According to comment:

```
F[{s, p, e, e, d}, {k, i, l, l, s}, 2]

{{21776,43552},{21886,43772},{23556,47112},{27331,54662},
 {29331,58662},{42667,85334},{45667,91334},{46557,93114}}

```
> 3 votes

# Answer
**Python**

```
def f(A,B,N):
 D={}
 r=[]
 for j in A:D[j]=0
 for j in B:D[j]=0
 x=len(D)
 for i in xrange(10**(x-1),10**x):
        c=str(i)
        s={}
        for j in c:s[j]=0
        if(len(s)-x or '0' in c):continue
        k=P=Q=0
        for j in D:D[j]=int(c[k]);k+=1
        for j in A:P=P*10+D[j]
        for j in B:Q=Q*10+D[j]
        if(P*N==Q):r.append((P,Q))
 return r
print f(['T','W','O'], ['F','O','U','R'], 2)

```

http://ideone.com/4wIQe
> 1 votes

# Answer
### scala:  333  289

```
type S=String
def d(x:S,m:Map[Char,Int])={var s=0
for(c<-x;k=m.find(_._1==c);v=(k.get)._2){s*=10
s+=v}
s}
def s(t:Int,f:S,p:S):Unit={
def c(m:Map[Char,Int])=d(f,m)*t==d(p,m)
val g=f.toSet++p
val m=g.zip(util.Random.shuffle((1 to 9).toSeq).take(g.size))
if(c(m.toMap))print(m)else s(t,f,p)}

```

Usage:

```
s (2,"SPEED","KILLS")
Set((D,7), (K,8), (I,5), (E,6), (S,4), (L,3), (P,2))

s(4,"REPEAT","ANDSTOP")
// endless loop :)

```
> 1 votes

# Answer
## PHP (200)

This function takes a very long time to execute and uses lots of memory, but it satisfies the criteria.

```
function f($o,$s,$n){$w=count_chars(($c=join($o)).$d=join($s),3);while(++$i<pow(10,9)){if(($u=count_chars($i,3))&&$u[0]*$u[8]&&($n*$a=strtr($c,$w,$i))==$b=strtr($d,$w,$i))$x[]=array($a,$b);}return$x;}

```

Sample usage:

```
$a=array('T','W','O');
$b=array('F','O','U','R');
$c=f($a, $b, 2); // returns an array of tuples that satisfy the equation

```

Un-golfed explanation:

```
function solve($operand, $sum, $num) {
  // convert the operand and sum arrays into strings, join them, then get a string containing the unique characters
  $operand_string = join($operand);
  $sum_string = join($sum);
  $unique_chars = count_chars($operand_string . $sum_string, 3);

  // loop from 1 to 10^9
  while (++$i < pow(10,9)) {
    // get the unique digits in $i
    $unique_digits = count_chars($i, 3);
    // check whether the first digit is non-zero (count_chars sorts in ascending order)
    // and whether the ninth digit is non-zero, these conditions guarantee that $i
    // is a permutation of 1...9
    if ($u[0] * $u[8]) {
      // translate the operand and sum into numbers, then check if the operand * num = sum
      $translated_operand = strtr($operand_string, $unique_chars, $i);
      $translated_sum = strtr($sum_string, $unique_chars, $i);
      if ($num * $translated_operand == $translated_sum) {
        // add the solution to the solutions array
        $solutions[] = array($translated_operand, $translated_sum);
      }
    }
  }
  // return the solutions array
  return $solutions;
}

```

If we're allowed to input the operand and sum as strings instead of arrays, then I can skip the join operations and save 20 characters to put the total at 180.
> 0 votes

# Answer
# 05AB1E, 24 bytes

```
žhœï²JÙ©gδ£εUε®X‡].Δ`¹*Q

```

Takes two loose inputs, the first being the integer and the second as a pair of words (i.e. first input = `4`, second input = `["ANDSTOP","REPEAT"]`).

Try it online. Brute-force approach, so unfortunately it's extremely slow; it's barely able to output the result for the first test case in ~45 seconds on TIO.

**Explanation:**

```
žh       # Push builtin "0123456789"
  œ      # Get all 3628800 (10!) permutations of this string of digits
   ï     # Cast each to an integer to remove leading 0s from some items
         # (otherwise ["0264","132"] would be the output for the first test case)
²        # Push the second input-pair
 J       # Join them together
  Ù      # Uniquify the letters
   ©     # Store it in variable `®` (without popping)
    g    # Pop and push its length to get the amount of unique letters
     δ   # For each permutation:
      £  #  Only keep the first unique-length amount of digits
ε        # Map each shortened string of digits to:
 U       #  Pop and store the current string of digits in variable `X`
  ε      #  Map over the two words of the (implicit) second input-pair
   ®     #   Push the unique letters from variable `®`
    X    #   Push the current digits we're mapping over from variable `X`
     ‡   #   Transliterate the letters to digits in the input-string we're mapping over
]        # Close the nested maps
 .Δ      # Find the first pair of integers which is truthy for:
   `     #  Pop and push them separated to the stack
    ¹*   #  Multiply the second (top) value by the first input
      Q  #  And check if it's now equal to the first value
         # (after which the result is output implicitly)

```
> 0 votes

---
Tags: code-golf
---


title: The matrix has U

text:
# Question
Title: The matrix has U
Given a matrix of size at least 3×3 formed by positive integers, determine if it contains at least one "U" pattern, defined as

```
+ + + - - - + +
+ + - N - N - +
+ + - N - N - +
+ + - N N N - +
+ + + - - - + +

```

where

* `N` is the same number, repeated in those seven positions
* `-` (optional) represents any number different than `N`. Each `-` can be a different number
* `+` (optional) represents any number. Each `+` can be a different number.

The amount of `+` and `-` entries obviously depends on the size of the matrix. In particular, some `-` may not exist because the pattern is adjacent to a matrix border. The above representation corresponds to a 5×8 matrix.

The pattern must have the specified orientation. Reflections or rotations are not valid.

# Test cases

### Truthy

* Pattern with `N=8`:

```
 3 4 7 5 6 5 4 8
 8 7 3 8 5 8 2 4
 9 9 9 8 7 8 1 3
 4 5 3 8 8 8 3 6
 6 8 9 2 3 2 1 4

```
* Same pattern with some `N` values nearby:

```
 3 4 7 5 6 5 8 8
 8 7 3 8 5 8 2 4
 9 9 9 8 7 8 1 3
 4 5 3 8 8 8 3 6
 6 8 8 2 3 2 1 4

```
* Pattern with `N=3`, touching a matrix border:

```
 7 5 4 7 5 4 5 6
 7 1 5 3 5 3 6 3
 3 5 3 3 9 3 2 3
 3 1 2 6 7 3 3 3
 4 5 2 8 9 6 8 4

```
* Pattern with `N=4`, touching a matrix corner:

```
 4 1 4 6
 4 3 4 3
 4 4 4 5
 7 5 3 5

```
* Two patterns, with `N=5` and `N=9`:

```
 6 7 9 4 5 6 7
 5 2 5 9 8 9 8
 5 1 5 9 6 9 3
 5 5 5 9 9 9 4
 8 7 6 1 3 2 5

```
* Pattern with `N=3`, and broken pattern with `1`:

```
 1 2 1 2 3 2 3
 1 2 1 2 3 2 3
 1 1 1 1 3 3 3

```
* Numbers can be greater than `9`; here `N=25`:

```
 23 56 34 67 34  3
 34 25  4 25 48 49
 24 25 97 25 56 56
 12 25 25 25 32 88

```
* Minimalistic case, `N=2`:

```
 2 1 2
 2 5 2
 2 2 2

```

### Falsy

* Nothing special here:

```
 7 8 6 5 4
 3 4 5 6 3
 3 5 6 4 4
 7 8 9 3 2

```
* Rotated or reflected patterns are not valid:

```
 9 9 9 3 7 7 7 5
 4 4 9 2 7 8 7 6
 9 9 9 8 7 9 7 4

```
* Some `-` entry spoils the pattern

```
 9 5 5 6 5
 3 8 5 9 5
 2 9 5 5 5

```
* Some `-` entry spoils the pattern, even if the result would be a "U" with longer horns

```
 7 8 5 2 5
 9 2 5 6 5
 3 8 5 9 5
 2 9 5 5 5

```
* Minimalistic case, no pattern

```
 9 9 9
 9 8 9
 9 9 9

```

# Additional rules

* You can choose to output:
    + Any two distinct values/arrays/strings... depending on whether the matrix contains the specified pattern or not; or
    + Anything truthy if the matrix contains the specified pattern, and anything falsy otherwise. The specific truthy and falsy values/arrays/strings... can be different for different inputs.
* The code should work in theory for matrices of arbitrarily large size, containing arbitrarily large numbers. In practice, it is acceptable if the program is limited by time, memory or data-type restrictions.
* Input and output are flexible as usual. Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
* Shortest code in bytes wins.

# Answer
> 6 votes
# APL (Dyalog Extended), ~~62~~ ~~51~~ 45 bytes (SBCS)

-6 based on fireflame241's solution.

```
⍲,(⍱{'GILNQRS'≡⎕A[⍸,⍵]~'AEUY'}⌺5 5⍤=)¨∘⊂0⍪0,⊢

```

Try it online!

# Answer
> 16 votes
# JavaScript (ES7),  ~~124 110~~  105 bytes

Returns a Boolean value.

```
m=>m.some((r,y)=>r.some((v,x)=>(g=n=>n--?v==(m[y+~-(n/5)]||0)[x+n%5-1]^144140166590/3**n%3&&g(n):1)(24)))

```

Try it online!

### How?

For each reference cell of value \\$v\\$ at \\$(x,y)\\$ in the input matrix \\$m\\$, we test 24 neighbor cells.

The constant \\$144140166590\\$ is \\$111210001101011010121112\_3\\$ in base 3. By reversing the digits and rearranging them into a 5x5 matrix, this gives:

$$\begin{pmatrix}2&1&1&1&2\\ 1&\color{red}0&1&0&1\\ 1&0&1&0&1\\ 1&0&0&0&1\\ 2&1&1&1&-\end{pmatrix}$$

where:

* the cell in red is the reference cell
* \\$0\\$ means that this cell must be equal to \\$v\\$
* \\$1\\$ means that this cell must be different from \\$v\\$
* \\$2\\$ means that we don't care

The bottom-right cell of the matrix is ignored, but it should be a \\$2\\$ anyway (for *we don't care*).

The \\$n\\$-th cell to test (0-indexed) is the cell whose coordinates are:

$$\big(x+(n\bmod 5)-1,y+\lfloor n/5\rfloor-1\big)$$

The corresponding value in the above matrix is given by:

$$V=\left\lfloor\frac{144140166590}{3^n}\right\rfloor\bmod 3$$

We do a bitwise XOR between the cell comparison test and \\$V\\$:

```
 is equal |  V  | XOR | success?
----------+-----+-----+--------------------------
     0    |  0  |  0  | no (should be equal)
     1    |  0  |  1  | yes
----------+-----+-----+--------------------------
     0    |  1  |  1  | yes
     1    |  1  |  0  | no (should be different)
----------+-----+-----+--------------------------
     0    |  2  |  2  | yes \__ always
     1    |  2  |  3  | yes /   ≠ 0

```

If all 24 tests are successful, we've found a valid `U`.

# Answer
> 10 votes
# Julia 0.6, ~~78~~ 75 bytes

```
x->any(n->7∈conv2(reshape(digits(287035908958,3)-1,5,5),1÷-~abs(x-n)),x)

```

Try it online!

Uses 2D-convolution to find the pattern encoded in the magic constant. The constant is derived via base 3 digits similarly to Arnauld's answer, but with 0 and 2 swapped. This way, after subtracting 1, we get the following correspondence: `N = 1, '+' = 0, '-' = -1`.

The input matrix is transformed to `N = 1, everything else = 0`. After convolution, the middle cell of the found pattern will accumulate a total of 7 (for the number of N's in the U-shape). If any of required N's is missing, the sum will not reach 7, and if an N (= 1) is present in the forbidden position, it will gain a negative contribution due to the multiplication by -1 in the pattern.

# Answer
> 4 votes
# APL (Dyalog Extended), 62 bytes

```
{{∨/∊({7 9 12 14 17 18 19≡1 5 21 25~⍨⍸,⍵}⌺5 5)¨(,⍵)=¨⊂⍵}0⍪0,⍵}

```

Try it online! (includes the new test case).

My first APL golf! Returns a `1` if there is a `U`, or `0` otherwise.

# Answer
> 4 votes
# Charcoal, 58 bytes

```
⊙θ∧‹¹κ⊙ι∧‹¹μ⬤θ⬤ν∨‹³⁺↔⁻ξ⊖κ↔⁻ρ⊖μ⁼⁼λπ∧›²↔⁻ξ⊖κ∨⁼¹↔⁻ρ⊖μ∧⁼ξκ⁼ρ⊖μ

```

Try it online! Link is to verbose version of code. Takes input as an array and outputs a Charcoal boolean, i.e. `-` if it contains U, nothing if not. Explanation:

```
⊙θ∧‹¹κ

```

Find a valid bottom row where:

```
⊙ι∧‹¹μ

```

Find a valid right column where:

```
⬤θ⬤ν

```

All elements of the array must satisfy:

```
∨‹³⁺↔⁻ξ⊖κ↔⁻ρ⊖μ

```

The element has a Manhattan distance from the centre of the U of more than 3, or...

```
⁼⁼λπ

```

... the equality of the element with the outer element matches:

```
∧›²↔⁻ξ⊖κ

```

The vertical distance of the element from the centre of the U is less than 2, and...

```
∨⁼¹↔⁻ρ⊖μ

```

... the horizontal distance of the element from the centre of the U is exactly 1, or...

```
∧⁼ξκ⁼ρ⊖μ

```

... the element is the bottom centre of the U.

# Answer
> 3 votes
# , 68 bytes

Builds up 16 U's with the 16 possible combinations of 0 and 1 in the corners, then looks for them in the position matrix of each number.

```
[:+./@,(0 4 4|.#:20 20 28(,4 4&#:)"p./i.16)E."2/[:(="{~,)4|:@|.@,&_]

```

Try it online!

---
Tags: code-golf, decision-problem, integer, matrix, pattern-matching
---


# Question
Title: The one counting challenge to rule them all!
## Background

Mathematicians are interested in all kinds of algebraic structures, e.g. groups, rings, boolean algebras. Generally, we have several operations (addition, multiplication, meet, join, etc.), and some equational relationships on the operations (e.g. associativity of multiplication). This makes up an **algebraic theory**. Formally, we want \\$k\\$ functions, the \\$i\\$-th of which takes \\$s\_i\\$ arguments. We also want some equalities to hold between the functions. In our case, we only consider equalities between expressions of depth at most 2, e.g. \\$f(g(x), h(x, y), h(y, z), f(x, y, w, z))\\$. The equalities should hold whatever values you plug in for the variables.

Let's take a quick example. A **semigroup** is such an algebraic structure. We need to have one function \\$f\_1\\$, with \\$s\_1=2\\$. There is just one equational relationship: \\$f\_1(f\_1(x, y), z) = f\_1(x, f\_1(y, z))\\$.

We are interested in **models** of the algebraic theories. A model, simply put, is just an implementation of the functions. We choose an underlying set \\$M\\$, and we implement the required functions \\$f\_i\\$ as taking \\$s\_i\\$ arguments from the set \\$M\\$, and returning an element of \\$M\\$, so that the equations hold when you plug in any element of \\$M\\$ for the variables. For example, if we take \\$M = \\{0,1,2\\}\\$, and \\$f\_1\\$ to be the addition modulo 3, we get a model for the semigroup. The **order** of a model is simply the size of \\$M\\$. So the model above has order 3.

Suppose that, for a fixed algebraic theory, there are two models, with underlying set \\$M\\$ and \\$N\\$, and functions \\$f\_i\\$ and \\$g\_i\\$, respectively. If, after some relabeling of the elements, two models become exactly the same, we say they are **isomorphic**. In that case, the two models are essentially the same, and usually we don't care about their difference.

> More formally, if we can find a mapping \\$\sigma: M \to N\\$ such that \\$g\_i(\sigma(m\_1), \sigma(m\_2), \dots, \sigma(m\_{s\_i})) = \sigma(f\_i(m\_1, \dots, m\_{s\_i}))\\$, we say that \\$\sigma\\$ is a **morphism**. Furthermore, if there is another morphism \\$\pi : N \to M\\$, and \\$\sigma(\pi(x)) = x\\$, \\$\pi(\sigma(y)) = y\\$ holds for every \\$x \in N, y\in M\\$, we say that the two models are isomorphic.

# Task

Your challenge is a very natural question that arises when studying algebraic theories.

> Given an algebraic theory (whose equations involve only expressions of depth at most 2) and a natural number \\$n\\$, compute the number of distinct models of order \\$n\\$, up to isomorphism.

You may write a function or a complete program. You can suppose the input is reasonably parsed for you. See the examples. Standard loopholes apply. This is , so the program with the shortest byte length wins.

## Example Cases

```
Input: The theory of groupoids. There is one function f taking 2 arguments.

f(f(x, y), z) = f(x, f(y, z))

n = 2.

Output: 5.

```

We'll fully work this out. For the rest of the example cases the basic idea is the same.

Let's take `M = {0, 1}`, the actual labelling of the elements obviously doesn't affect the outcome. We have four values to decide on, `f(0, 0)`, `f(0, 1)`, `f(1, 0)`, `f(1, 1)`. Let's case split on `f(0, 1)`.

* **Case 1:** `f(0, 1) = 0`. So `0 = f(0, 1) = f(f(0, 1), 1) = f(0, f(1, 1))`. We further case split on `f(1, 1)`.

+ **Case A:** `f(1, 1) = 0`. Then `0 = f(0, f(1, 1)) = f(0, 0)`. If further, `f(1, 0) = 0`, then `f` is a constant function, and obviously satisfies the equation. If `f(1, 0) = 1`, then `1 = f(1, 0) = f(1, f(1, 1)) = f(f(1, 1), 1) = f(0, 1) = 0`, contradiction.
    + **Case B:** `f(1, 1) = 1`. Let's consider `f(0, 0)`.
        - **Case i:** `f(0, 0) = 0`. Then `f(1, 0) = f(f(1, 1), 0) = f(1, f(1, 0))`. If `f(1, 0) = 1`, plugging that in yields `1 = f(1, 1) = 0`, contradiction. SO `f(1, 0) = 0`. So `f(x, y) = x and y`, which satisfies the equation, as you learned early in discrete mathematics.
        - **Case ii:** `f(0, 0) = 1`. Then `f(1, 0) = f(f(0, 0), 0) = f(0, f(0, 0)) = f(0, 1) = 0`. So the whole thing is just the `xnor` function.

Now let's look back: we've already got the constant function `0`, the boolean `and`, and `xnor`. We proceed:

* **Case 2:** `f(0, 1) = 1`. We could do the case analysis all over again. But note that everything exactly mirrors case 1, except that `0` and `1` are inverted, and the two arguments of `f` is swapped. Since swapping the arguments doesn't affect associativity, we immediately get what we wanted: the constant function `1`, the boolean `nand` and `xor`.

Now we need to make sure they are all non-isomorphic. In fact, the two constant functions are isomorphic, since the relabelling that swaps `0` and `1` converts between them. So we've got 5 different possibilities.

```
Input: There are three functions f, g, h taking 1, 2 and 0 arguments, respectively.
The equations are:

g(g(x, y), z) = g(x, g(y, z))
g(x, f(x)) = h()
g(f(x), x) = h()
g(h(), x) = x
g(x, h()) = x

n = 3

Output: 1.

```

You may assume that the functions are labeled with natural numbers, here we use letters to make it more readable. Note that the expressions on both sides of the equalities should be implemented as trees or nested lists. You can assume that such trees are passed to your function as argument, so you can skip the parsing part. But in case you want to fiddle with `eval`-like stuff you can also accept string input.

The model of this algebraic theory is exactly the groups. And all groups of order 3 are isomorphic to \\$\mathbb Z\_3\\$, which takes the underlying set to be \\$\\{0,1,2\\}\\$, and `g` is the addition modulo 3, `f` is negation, `h()` equals 0. Then the equations translate to:

* \\$(x + y) + z = x + (y + z)\\$;
* \\$x + (-x) = 0\\$;
* \\$(-x) + x = 0\\$;
* \\$0 + x = x\\$;
* \\$x + 0 = x\\$.

These are just the familiar properties of addition.

```
Input: Same as previous, except `n = 6`.

Output: 2.

```

In fact, for this algebraic theory, the answer should be the very first sequence of OEIS, which demonstrates the importance of such sequences.

---

```
Input: There are 4 functions f, g, h, i, that takes 2, 2, 0, 1 arguments, repectively. The equations are:

f(f(x, y), z) = f(x, f(y, z))
g(g(x, y), z) = g(x, g(y, z))
f(x, y) = f(y, x)
f(i(x), x) = h()
f(h(), x) = x
g(x, f(y, z)) = f(g(x, y), g(x, z))
g(f(y, z), x) = f(g(y, x), g(z, x))

n = 10.

Output: 4.

```

This is OEIS A027623.

```
Input: There is just 1 function f taking 1 argument. The equations are:

f(x) = f(x)
f(f(y)) = f(f(y))

n = 30

Output: 10712682919341.

```

> Note that the equations are redundant. `f` is simply any function. We draw a directed edge from `a` to `b` if `f(a) = b`, this produces a graph where every vertex's out-degree is 1. Since we consider things up to isomorphism, we need to count such graphs with unlabeled nodes. We first consider a connected component. Since the out-degree is always 1, you can uniquely follow the edges until you hit a previously visited vertex. This produces a cycle (possibly with length 1 or 2). We consider the rest of the vertices in this connected component. They have to be on trees rooted on the cycle. Counting such graphs should be standard practice. The number of connected component is A002861, and the total number is A001372.

```
Input: 2 functions f, g both taking 2 arguments.

f(x, y) = f(y, x)
g(x, y) = g(y, x)
f(f(x, y), z) = f(x, f(y, z))
g(g(x, y), z) = g(x, g(y, z))
f(x, g(x, y)) = x
g(x, f(x, y)) = x

Output: OEIS A006966.

```

It is clear that this challenge is a very general generalization of various counting problems.

---

Below are some degenerate corner cases.

```
Input: There are no functions. There are no equalities. n = 7.

Output: 1.

```

This is just finding sets with 7 elements, and if there are bijections between two sets they count as the same. Of course, there are bijections between every two sets with 7 elements. So the answer is 1.

```
Input: There are no functions. The only equality is x = y. n = 7.

Output: 0.

```

The equalities should hold for all `x` and `y`. So there can only be at most 1 distinct element, but we require 7.

```
Input: Same as above, except `n = 1`.

Output: 1.

```

```
Input: Any algebraic theory, n = 0.

Output: 1. (Regardless of the theory.)

```

# Answer
# Haskell,  ~~482~~ ... ~~408~~ 402 bytes

* -5 thanks to @ovs
* -18 by inlining functions that are used just once
* -12 by introducing short names of constants and removing parentheses
* -11 by making a function local so it can take less arguments
* -29 thanks to @Laikoni and @Trebor
* -6 bytes by preferring list comprehension to `filter`, and turn `F Int[A]` into `Q[A]Int` for 1 space (I changed the letter to ease the changing of the test cases).

```
import Data.List
data A=Q[A]Int|V Int
t=map
w=sequence
y(V i)=i
y(Q l _)=maximum$0:t y l
(0!_)_=1
(n!e)q=c[b|m<-w$t(a.(n^))e,let b=[\b->f!!sum(zipWith(*)b(t(n^)r))|f<-m],and[h l==h r|(l,r)<-q,v<-a$1+y l`max`y r,let h(V i)=v!!i;h(Q e f)=b!!f$h<$>e]]where;a i=w$r<$[1..i];d#w=all(\p->or[(t(.t(p!!))d!!f)q/=(t((p!!).)w!!f)q|(f,z)<-zip r e,q<-a z])$permutations r;c[]=0;c x=1+c(filter(head x#)x);r=[0..n-1]

```

Try it online!

The function `(!)` accepts input as `(n ! arities) equations`, where `n` is the given `n`, `arities` is a list of \\$s\_i\\$, as specified in the challenge, `equations` should be in the predefined datatype `A`, whose ungolfed version reads

```
data Expression
  = Func Int [Expression] | Var Int

```

An expression is either a `Var` variable, indexed by natural numbers (here `Int` saves bytes), or `Func i [arg1, arg2, arg3, ...]`, which is just the \\$i\\$-th function, applied to the list of arguments. I have entered the equations in the footer in TIO, in case you are interested. (`Func Int [Expression]` becomes `Q[A]Int` in the golfed code to save one space.)

As mentioned by @fireflame241 it is very hard to get anything interesting done within the time limit. Nonetheless I've written a decent set of tests to check against OEIS.

---

Ungolfed version (still messy but hopefully the comment makes it clear):

```
import           Data.List

data Expression
  = Func Int [Expression] | Var Int deriving (Show)

tabulate n arity f =
  intercalate
    "\n"
    [ "f" ++ show assv ++ " = " ++ show (f assv)
    | assv <- sequence (replicate arity [0 .. n - 1])
    ]

showModel n arities m =
  intercalate "\n\n" [tabulate n a f | (a, f) <- zip arities m]

-- auxiliary function to find the largest variable number
-- this is less efficient, but saves the hassle of having to bookkeep the used variables
vars (Var i)    = i
vars (Func _ l) = maximum $ 0 : map vars l  -- the 0 is to avoid empty lists

-- evaluates an expression in the model `funcs`
evaluate :: [[Int] -> Int] -> [Int] -> Expression -> Int
evaluate funcs varass (Var i) = varass !! i
evaluate funcs varass (Func f es) = funcs !! f $ map (evaluate funcs varass) es

-- auxiliary function to generate all possible variable assignments
varasss n l r = sequence (replicate (1 + max (vars l) (vars r)) [0 .. n - 1])

-- I think this can be further golfed, but havent come up with good ones yet
checkValid ::
     Int -> [Int] -> [(Expression, Expression)] -> [[Int] -> Int] -> Bool
checkValid n arities equations funcs =
  and
    [ evaluate funcs v l == evaluate funcs v r
    | (l, r) <- equations
    , v <- varasss n l r
    ]

-- generates all models. The outer list comprehension runs over a cartesian product M1 * M2 * ...,
-- where Mi is the (flattened) table of all the possible implementation of the i-th function
-- Then the complicated `sum $ zipWith` stuff computes the index of the flattened table Mi
-- from the un-flattened index
allModels :: Int -> [Int] -> [[[Int] -> Int]]
allModels n arities =
  [ [\b -> f !! (sum $ zipWith (*) b (map (n ^) [0 ..])) | f <- m]
  | m <-
      sequence (map (\i -> sequence (replicate (n ^ i) [0 .. n - 1])) arities)
  ]

-- see if two models are identical, by comparing the values.
ident :: Int -> [Int] -> [[Int] -> Int] -> [[Int] -> Int] -> Bool
ident n arities m1 m2 =
  and
    [ (m1 !! f) assv == (m2 !! f) assv
    | f <- [0 .. length arities - 1]
    , assv <- sequence (replicate (arities !! f) [0 .. n - 1])
    ]

-- see if two models are isomorphic, by testing all permutations.
-- (p !!) computes the permutation
-- the mysterious `((p!!).)` was generated by http://pointfree.io/ from `(\f -> \i -> p !! (f i))`.
-- It is understandable, but I couldnt have come up with that ;)
isom :: Int -> [Int] -> [[Int] -> Int] -> [[Int] -> Int] -> Bool
isom n arities m1 m2 =
  or
    [ ident n arities (map (flip (\i -> ($map (p !!) i))) m1) $map ((p !!) .) m2
    | p <- permutations [0 .. n - 1]
    ]

-- used to partition the valid models into isomophic classes
-- This was taken from one of my projects, which ultimately
-- comes from some StackOverflow code snippet, which Ive lost the source
splitOffFirstGroup :: (a -> a -> Bool) -> [a] -> ([a], [a])
splitOffFirstGroup equal xs@(x:_) = partition (equal x) xs
-- splitOffFirstGroup _     []       = ([],[])  -- Not really necessary

equivalenceClasses _ [] = 0
equivalenceClasses equal xs =
  let (fg, rst) = splitOffFirstGroup equal xs
   in 1 + equivalenceClasses equal rst

-- putting everything together...
answer 0 _ _ = 1  -- corner case
answer n arities equations =
  equivalenceClasses (isom n arities) $
  filter (checkValid n arities equations) $ allModels n arities

```
> 6 votes

# Answer
# Python 3, ~~393~~ 382 bytes

*-11 bytes thanks to @ovs*

```
from itertools import*
T=tuple
P=product
def C(A,e,n):
 G=range(n);t=0;c=[]
 for m in P(*[[dict(zip(P(*[G]*a),o))for o in P(*[G]*n**a)]for a in A]):
  E=lambda x,f:f[x]if x*0==0else m[x[0]][T(E(s,f)for s in x[1:])]
  if m not in c: c+=[T({T(r[a]for a in k):r[f[k]]for k in f}for f in m)for r in permutations(G)];t+=all(E(q[0],f)==E(q[1],f)for q,N in e for f in P(*[G]*N))
 return t

```

Try it online!

Takes each equation in the list as a pair of two expressions (LHS and RHS) and the number of free variables. Each expression is a tree representation, where the first non-negative integer of each list represents the index of the function, and the rest of the list are the function's arguments. (Uncomment the second-to-last line of the TIO link to see what the input looks like). The footer performs a bunch of parsing on the input string before passing to the function.

This generates all possible mappings of inputs to outputs for each function and tests if each one works. Ideally implemented, this general algorithm would have worst-case time complexity something like \\$O(\frac{n^{\sum A}LEn^L}{n!})\\$ (very slow), where \\$n\\$ is the order the given, \\$\sum A\\$ is the sum of the arities of the functions, \\$L\\$ is the average length of each equation (the whole equation is evaluated), and \\$E\\$ is the number of equations. There are \\$n^{\sum A}\\$ possible models, but sets of \\$n!\\$ on average are mutually isomorphic. Each class of models gets tested once (Ideally, we could ignore all but \\$1\\$ of each class, but it is not trivial to skip over isomorphic models. Hence, there is probably a full \\$n^{\sum A}\\$ term added for my implementation, and even higher since it checks for `dict` membership in a list of `dict`s). In the worst case, all of these \\$n^{\sum A}/n!\\$ models are valid, but they have to be verified by checking all \\$E\\$ equations and all \\$n^L\\$ possible inputs, each of which take (on average across the equations) \\$L\\$ time to evaluate. In the average case, I"m guessing only the log of this number has to be checked, so the average case would be roughly \\$O(\frac{n^{\sum A}L\log(En^L)}{n!})=O(\frac{n^{\sum A}L^2\log(E)}{n!})\\$. In the best case, for example with the equation `x=y`, each model gets invalidated with the first or second check (`0=0` ... `0=1`), so best case is \\$O(\frac{n^{\sum A}}{n!})\\$.

With these unwieldy time complexities, I have had to (greatly) shrink some of the orders input in order to run on TIO. The OEIS sequences that list millions of elements were generated with some specialized algorithm or formula. However, this has to run in the general case, so it can't easily make logical deductions that a human can (SAT is NP-hard, so I doubt the time complexity can be much improved).

### Commented golfed code

```
from itertools import*

T=tuple
P=product

def C(A,e,n):
    G=range(n);
    t=0;# t: total number of models found so far
    c=[]    # c: list of isomorphic models of those already considered
            # A set would be better for time, but it takes a few too many bytes
            # to stringify dicts in a consistent way
    for m in P(   # m is a model
        *[
            [
                dict(zip(
                    P(*[G]*a), # inputs
                    o
                ))
                for o in P(*[G]*n**a) # possible outputs
            ]
            for a in A    # Why does this have to be enclosed in a list?
        ]   # P: choose one mapping for each function
    ):
        # I place the definition of E here so it can take advantage of scope to access m,n
        E=lambda x,f:f[x]if x*0==0else m[x[0]][T(E(s,f)for s in x[1:])] # E: evaluate an eXpression given free variables f
        # haven't already considered an isomorphic model:
        if m not in c:\
            c+=[    # append all isomorphic models
                T(
                    {
                        T(r[a]for a in k):r[f[k]]  # apply mapping
                        for k in f     # to keys (inputs) and values (outputs)
                    }
                    for f in m
                )
                for r in permutations(G) # r is a remapping, e.g. [0,2,1] on n=3 swaps 2 and 1
            ];\
            t+=all( # is the model valid?
                E(q[0],f)==E(q[1],f)        # LHS and RHS are equal
                    for q,N in e            # when given each possible list of free variables
                    for f in P(*[G]*N)
            )
    return t

```

### General idea

```
from itertools import*

def execute(expr,free_vars,model,n):
    try:
        func_id, *params = expr
        params = tuple(execute(subexpr,free_vars,model,n) for subexpr in params)
        return model[func_id][params]
    except:
        # expr is an int ==> a variable
        return free_vars[expr]

def get_all_models():
    return product(
        *[
            [
                {i:o for i,o in zip(
                    product(*[range(n)]*arity), # inputs
                    output
                )}
                for output in product(*[range(n)]*n**arity)
            ] # possible outputs
            for arity in arities    # Why does this have to be enclosed in a list?
        ]
    )

def relabellings(model,n):
    return [
        tuple(
            {
                tuple(relabelling[a] for a in k): relabelling[e]
                for k,e in func.items()
            }
            for func in model
        )
        for relabelling in permutations(range(n))
    ]

def model_works(model, equations, n):
    return all(
        execute(eq[0],free_vars,model,n) == execute(eq[1],free_vars,model,n)
            for eq, num_free_vars in equations
            for free_vars in product(*[range(n)]*num_free_vars)
    )

def count(arities, equations, n):
    total=0
    considered = []
    for model in get_all_models():
        if model in considered:
            continue
        for r in relabellings(model, n):
            considered.append(r)
        if model_works(model, equations, n):
            total += 1
    return total

```
> 4 votes

---
Tags: code-golf, abstract-algebra, logic
---


title: Helicopter challenge

text:
# Question
Title: Helicopter challenge
There is a helicopter flying **500** meters from the ground. It can fly up **100** meters, which takes **1.0 secs**. Or if it doesn't fly up it will fall 200 meters, which also takes **1.0 secs** \- This means if the instruction is **anything** other than "Fly" the helicopter falls. Build a program that takes input of a list of instructions, telling the helicopter when to fly and when not to. **When the helicopter falls it should output the time counter**.

INPUT:

> Fly Dance Fly Golf Fly Fly

OUTPUT:

> 8.5 secs

Walkthrough:

> 1) Fly == Fly so +100 = 600m
>
> 2) Dance != Fly so -200 = 400m
>
> 3) Fly == Fly so +100 = 500m
>
> 4) Golf != Fly so -200m = 300m
>
> 5) Fly == Fly so +100 = 400m
>
> 6) Fly == Fly so +100 = 500m
>
> 7) NO INSTRUCTIONS so -200 = 300m
>
> 8) NO INSTRUCTIONS so -200 = 100m
>
> 9) NO INSTRUCTIONS so -100 = 0m (This takes 0.5 seconds)

Each instruction should be separated by a space, and if the instuction isn't fly, then automatically fall. When the program runs out of instructions automatically fall. Your program **must** output in (float)secs, and if it takes =\> 60.0 seconds display in mins and seconds eg. 1 mins 32.0 secs

Seconds are float **decimal** values, minutes are whole interger values. Also note capitalization does **not** matter your program should work for capitals or no capitals.

This is code-golf so the least NO bytes wins!

# Answer
> 3 votes
# Python, ~~100~~ ~~92~~ 89 bytes

```
lambda I:sum(reduce(lambda(a,s),i:(a+(a>0)*(-1,.5)[i=='Fly'],s+(a>0)),I.split(),(2.5,0)))

```

try it online

# Answer
> 3 votes
# 05AB1E, 31 bytes

```
l#ā«'¤†Q3*Í5šηO.γd}нRć;sg+60‰0Û

```

Follows the challenge to the letter. Input as a space-delimited string, and output as a list `[sec]` or `[min,sec]`, where `sec` is a float and the potential `min` is an integer.

If taking the input as a list of strings is allowed, the `#` could be removed.
If outputting as `[min,sec]` even if `min` is 0 is allowed, the tailing  can be removed.

Try it online or verify a few more test cases.

**Explanation:**

```
l                             # Convert the (implicit) input-string to lowercase
                              #  i.e. "Fly Dance Fly Golf FLY fLy"
                              #   → "fly dance fly golf fly fly"
 #                            # Split it on spaces
                              #  → ["fly","dance","fly","golf","fly","fly"]
  ā                           # Push a list in the range [1, length]
                              # (without popping the list itself)
                              #  → [1,2,3,4,5,6]
   «                          # Merge it to the list of words
                              #  → ["fly","dance","fly","golf","fly","fly",1,2,3,4,5,6]
    '¤†                      '# Push dictionary string "fly"
       Q                      # Check for each word (or integer) if it's equal to "fly"
                              # (1 if truthy; 0 if falsey)
                              #  → [1,0,1,0,1,1,0,0,0,0,0,0]
        3*                    # Multiply each by 3
                              #  → [3,0,3,0,3,3,0,0,0,0,0,0]
          Í                   # Decrease each by 2 (so 1 if truthy; -2 if falsey)
                              #  → [1,-2,1,-2,1,1,-2,-2,-2,-2,-2,-2]
           5š                 # Prepend a 5 to this list
                              #  → [5,1,-2,1,-2,1,1,-2,-2,-2,-2,-2,-2]
             η                # Get all prefixes of this list
                              #  → [[5],[5,1],...[[5,1,-2,1,-2,1,1,-2,-2,-2,-2,-2,-2]]
              O               # Sum each prefix
                              #  → [5,6,4,5,3,4,5,3,1,-1,-3,-5,-7]
               .γ }           # Consecutive group the values by:
                 d            #  Where the value is >= 0
                              #   → [[5,6,4,5,3,4,5,3,1],[-1,-3,-5,-7]]
                }н            # After the group-by, only leave the first group
                              #  → [5,6,4,5,3,4,5,3,1]
                  Rć          # Reverse and extract the head,
                              # so we've extracted the last item loose to the stack
                              #  → [3,5,4,3,5,4,6,5] and 1
                    ;         # Halve that last item
                              #  → [3,5,4,3,5,4,6,5] and 0.5
                     sg       # Swap to get the list, and pop and push its length
                              #  → 8
                       +      # Add it to the halved last item
                              #  → 8.5
                        60‰   # Take the divmod-60
                              #  → [0,8.5]
                           0Û # And remove a potential leading 0
                              #  → [8.5]
                              # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `'¤†` is `"fly"`.

# Answer
> 2 votes
# Perl, 90 bytes

```
$a=5;
$_++,$a+=shift=~/Fly/?1:-2 while$a;
$==$_/60;
$_%=60;
say+($=?"$= mins ":"")."$_ secs"

```

Accepts input as command-line parameters. Run as

```
perl -E '$a=5;$_++,$a+=shift=~/Fly/?1:-2 while$a>0;$==$_/60;$_%=60;say+($=?"$= mins ":" ")."$_ secs"' Fly Dance Fly Fly Golf

```

Starts `$a` at 5, and increases it by 1 every time it finds "Fly", decrements by 2 otherwise. Keeps going until `$a` is non-positive, and counts how many iterations it took to get there. `$=` is special and forces its value to be an integer, so `$==$_/60` only takes the integer portion of the division, ignoring the rest. Everything else is self-explanatory, I feel.

# Answer
> 2 votes
# C 93

**Thanks to @ceilingcat for finding a ***much*** shorter version**

```
i,h=5;main(c,v)int**v;{for(;h>0;)h+=*v[(++i<c)*i]-'ylF'?-2:1;printf("%f secs\n",i-(h<0)*.5);}

```

Try it online!

# Answer
> 2 votes
# Burlesque, 64 bytes

```
wdm{"Fly"=={1}{-2}IE}@5+]q++pa{0.>}TWsa-.j[~2./.+J60./foJ60.*j.-

```

Try it online!

```
wd         # Split into words
m{         # Map
 "Fly"==   # word is "Fly"?
 {1}{-2}IE # If fly 1 else -2
}
@5+]       # Prepend 5.0
q++pa      # Calculate partial sums
{0.>}TW    # Take until 0 or less
sa-.       # Length of this -1 (to account for pushed 5.0)
j[~2./     # Take the remaining height /2
.+         # Add this time
############ Mins Secs ##############
J60./fo    # Calc number of mins
J60.*      # N mins * 60
j.-        # Calc seconds over

```

If we don't have to deal with the mins/secs rule:

# Burlesque, 49 bytes

```
wdm{"Fly"=={1}{-2}IE}@5+]q++pa{0.>}TWsa-.j[~2./.+

```

Try it online!

# Answer
> 1 votes
# PHP, ~~55~~ 54 bytes

```
for($h=5;$h>0;)$h+='Fly'==$argv[++$i]?:-2;echo$h/2+$i;

```

Loops through command line arguments; run with `-r`.

Height is divided by 100 to simplify output and calculation: If height is below zero (i.e. -100m),
adding half of it (-50 divided by 100: -.5) to the time removes half a second from the result.

That combined with the magic of Elvis golfed ~~5~~ 6 bytes from my initial program.

# Answer
> 1 votes
## Mathematica 211 bytes

```
(s=ToString;t=Length[#[[;;(FirstPosition[#,x_/;x<=0,1]-1/. 0->Length@#)]]]&[x=500+Accumulate[If[#=="Fly",100,-200]&/@(StringSplit@#)]];
If[#>=60,s@Floor[#/60]~~" min ",""]~~s@Mod[#,60]~~ " sec"&[t+x[[t]]/200.])&

```

This algorithm assumes the flight ends when the altitude reaches 0 for the first time. Looking at some of the other answers, I think people have the helicopter flying below ground level. I don't allow "touch and go" either.

Ungolfed:

```
in="Fly Dance Fly Golf Fly Fly";
s=ToString;StringSplit@in
If[#=="Fly",100,-200]&/@%
altList=500+Accumulate@%
l=Length@altList
(* find last positive before first nonpositive *)
FirstPosition[altList,x_/;x<=0,1]-1
t=Length[altList[[;;(%/. 0->l)]]]
t+altList[[t]]/200.
If[%>=60,s@Floor[%/60]~~" min ",""]~~s@Mod[%,60]~~ " sec"

```

# Answer
> 0 votes
# APL (Dyalog Classic), 80 bytes

Caveat: case sensitive.

This will return (minutes, seconds) if the flight takes more than 59 seconds, otherwise – only seconds.

```
{(1+⍵≥60)⌷⍵(⍵(⌊÷,⊢|⊣)60)},{(⍵⍳0)⌊¯0.5+⍵⍳¯1}{5++\¯2@~(4×≢⍵)↑{⍵≡'Fly'}¨' '(≠⊆⊢),⍵}

```

Try it online!

Without conversion to minutes it's 54 bytes:

```
{(⍵⍳0)⌊¯0.5+⍵⍳¯1}{5++\¯2@~(4×≢⍵)↑{⍵≡'Fly'}¨' '(≠⊆⊢),⍵}

```

# Answer
> 0 votes
# Javascript, 137

```
a=>{for(s=5,i=0,a=a.toLowerCase().split(" ");s>=0;){s+=a[i]&&a[i++]=="fly"?1:-2}return parseInt(i/60)+"min "+(i%60+s/2).toFixed(1)+"sec"}

```

Try it online!

Test:

```
"Fly fly fly fly fly fly fly fly hi test flu fly fly Fly fly fly fly fly flu flu FLY fly fly Fly fly fly fly fly fly fly fly dance again now fly fly fly fly fLy fly fly flu flu fly Fly fly flY flY fly fly fly fly go flu flu fly fly fly fly fly fly fly win flu fly "

```

Result:

```
1min 17.5sec

```

# Answer
> -1 votes
# Python 2, ~~85~~ 91 bytes

```
t=2.5+input().upper().split().count('FLY')*1.5
print('%d mins'%(t/60))*(t>59),`t%60`,'secs'

```

Takes input on STDIN, surrounded by quotes (single or double). Simply counts the number of `Fly`s there are in the input, performs some path to calculate the number of seconds, then formats it.

Now case-insensitive!

*Fixed a bug with the same bytecount thanks to Jonathan Allan!*

*Saved 2 bytes thanks to Shebang!*

# Answer
> -1 votes
# Scala, 88 bytes

```
s=>{val n=s.split(" ").count("Fly"==)*1.5+2.5
(if(n<60)""else n/60+"min ")+n%60+" secs"}

```

Ungolfed:

```
s=>{
  val n=s.split(" ").count("Fly"==)*1.5+2.5
  (
    if(n<60)
      ""
    else
      (n/60)+"min "
  )
  +(n%60)
  +" secs"
}

```

Uses the same formula as Copper's python answer.

# Answer
> -1 votes
# AWK, 150 bytes

Below is a rather straightforward implementation in AWK, the nice thing about it is that you can run it interactively and feed it by typing commands by hand (just don't forget to remove RS=" ", if you want one command per line).

**Golfed**

```
awk 'BEGIN{RS=" ";h=500;t=0}toupper($0)~/FLY/{h+=100;t+=1;next}{h-=200;t+=1;}END{t+=h/200;F=(t>59?"%d mins ":"%.0d") "%.1f secs";printf F,t/60,t%60;}'

```

**Test**

```
echo "Fly Dance FLy Golf Fly Fly" |\
awk 'BEGIN{RS=" ";h=500;t=0}toupper($0)~/FLY/{h+=100;t+=1;next}{h-=200;t+=1;}END{t+=h/200;F=(t>59?"%d mins ":"%.0d") "%.1f secs";printf F,t/60,t%60;}'

8.5 secs

```

---
Tags: code-golf, number
---


title: What are these letters?

text:
# Question
Title: What are these letters?
So what might be the shortest language for this simple task?

## Task:

You are given an input of type `String` \- the string is a `valid` hexadecimal number (`[0-9A-F]`). Convert it to a decimal number and print it to the console.

## Tests:

```
HEX -> DEC
1 -> 1
98 -> 152
539 -> 1337
1337 -> 4919
A5F9 > 42489
F -> 15

```

## Win Condition:

This is code golf - shortest code wins.

## Rules:

* You **must** take the input(like function parameter) as String.
* You **must** return the result as String.

# Answer
> 4 votes
# 05AB1E, 1 byte

```
H

```

Try it online!

---

Am I missing something? I feel like... I feel like I am.

---

If "print as a string" implies "surround result with quotes":

# 05AB1E, 5 bytes

```
H'".ø

```

Try it online!

---

05AB1E is based in Python, so it doesn't really matter if it's a string, integer or whatever; `H` will convert an integer, a string, a Ferrarri or 27 gnomes on patrol into hex. Given, the latter two aren't valid, it will error upon trying to execute or return the original string with no function applied.

# Answer
> 2 votes
# Haskell, ~~24~~ ~~23~~ 22 bytes

```
show.abs.read.("0x"++)

```

Thanks to @user9549915 for saving a byte

Try it online!

# Answer
> 2 votes
# JavaScript (Node.js), ~~20~~ ~~15~~ 14 bytes

Thanks to l4m2 for catching my stupid mistake and saving me a byte. :)

```
x=>'0x'+x-0+''

```

Try it online!

# JavaScript (Node.js), 15 bytes

```
x=>'0x'+x-[]+''

```

Try it online!

# Original 20 bytes

```
l=>''+parseInt(l,16)

```

Try it online!

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

My first JS golf!

```
x=>''+eval('0x'+x)

```

Try it online!

Just prepends `0x` to the input and evaluates that, since it then represents a hexadecimal number in JS. Finally, we need to concatenate the empty string to convert to string.

# Answer
> 2 votes
# Python 2, 20 bytes

```
lambda s:`int(s,16)`

```

Try it online!

# Answer
> 2 votes
# , 6 bytes

```
":@dfh

```

Try it online! (Contains a test suite, including type checking the parameters and the return value.)

This is pretty simple:

```
":@dfh
   dfh    obtain *d*ecimal *f*rom *h*ex
  @       then
":        format the result (cast to string)

```

# Answer
> 2 votes
# Jelly, 8 bytes

```
⁾0x;ŒVṾ

```

This is a monadic link that takes a string as argument and returns a string.

Try it online!

### How it works

```
⁾0x;ŒVṾ  Monadic link. Argument: s (string)

⁾0x;     Prepend "0x" to s.
    ŒV   Eval as Python code.
         This returns the result as an integer.
      Ṿ  Uneval; turn the integer into its string representation.

```

# Answer
> 2 votes
# \>\<\>, 23 bytes

```
0l1=?n88+*{'0'-:a)7*-+!

```

Try it online!

If the hex can be contain lowercase letters instead of uppercase, we can do it in 17 bytes:

```
0l1=?n88+*{e0p +!

```

# Answer
> 2 votes
# Java 8, 24 bytes

```
s->Long.valueOf(s,16)+""

```

Try it online here.

# Answer
> 2 votes
# Charcoal, 6 bytes

```
Ｉ⍘↧Ｓ¹⁶

```

Try it online! Link is to verbose version of code. Save 1 byte if the input can be in lower case. Charcoal doesn't automatically convert numbers to decimal on output, so the cast operator is necessary anyway. Explanation:

```
   Ｓ    Input string
  ↧     Lower case
    ¹⁶  Literal 16
 ⍘      Base conversion
Ｉ       Cast to string
        Implicitly print

```

# Answer
> 2 votes
# Excel, 14 bytes

```
=0&HEX2DEC(A1)

```

Concatenates a leading `0` to convert to String. I.e. `042489`

---

# Excel, 20 bytes

```
=TEXT(HEX2DEC(A1),0)

```

Naive solution.

---

Format both outputs verified as String (`=T(B2)`)

# Answer
> 2 votes
# Pyth, 5 4 bytes

`iz16`

Parses input as a hex number and returns the base 10 equivalent.

# Answer
> 1 votes
# Stax, 3 bytes

```
i|H

```

Run and debug it

`i` ensures that the input doesn't get automatically evaluated as an integer, and `|H` converts from/to hexadecimal. The link above is for the online interpreter, but the language really does use `stdin` and `stdout`. The C# implementation of the language does this, which is available from the repository above.

# Answer
> 1 votes
# , 27 bytes

```
paste(strtoi(scan(,""),16))

```

Try it online!

`strtoi` will always return a number of type `integer` which is a signed 32-bit integer type, and `paste` implicitly converts to `character`, as required.

# Answer
> 1 votes
# Jelly, 10 bytes

```
ØHiÐ€ɠ’ḅ⁴Ṿ

```

Try it online!

## How it works

```
ØHiÐ€ɠ’ḅ⁴Ṿ - Main link, no arguments

ØH         - Yield the string “0123456789ABCDEF”. Call that H
     ɠ     - Read a line from STDIN, e.g. “A5F9”. Call that A
   Ð€      - For each character in A
  i   ’    - Get the 0-based index of that character in H
        ⁴  - Yield 16
       ḅ   - Convert from base
         Ṿ - Convert to string

```

# Answer
> 1 votes
# dc, 5 bytes

```
16i?p

```

Try it online!

Rather trivial. If input really needs to be a *string* vs. the language's natural hex input, then `16i?xp` takes care of that in 6 bytes.

# Answer
> 1 votes
# Julia, 23 bytes

```
!s=dec(parse(Int,s,16))

```

Try it online!

`dec` appears to be shorter than `repr` or `string`.

# Answer
> 1 votes
# Ruby, 14 bytes

```
p gets.to_i 16

```

Try it online!

# Answer
> 1 votes
# APL (Dyalog), 13 bytes

```
⍕16⊥(⎕D,⎕A)⍳⊢

```

Try it online!

# Answer
> 1 votes
# Japt, 4 bytes

Outputting as a string doubles the byte count!

```
nG s

```

Try it

# Answer
> 1 votes
## Batch, 15 bytes

```
@cmd/cset/a0x%1

```

If input via command-line argument is unacceptable, then for 26 bytes:

```
@set/ph=
@cmd/cset/a0x%h%

```

# Answer
> 1 votes
# WinDbg, 15 bytes

```
.printf"%d",$u0

```

Input is done by first setting the pseudo-alias `$u0` with the input string and then running the code (eg- to set pseudo-alias: `r$.u0=a5f9`).

Prints the input, conversion from hex to decimal is implicit.

How it works:

```
.printf"%d",        $$ Prints a decimal
            $u0     $$ The decimal to print

```

If the extra sugar that WinDbg prints when evaluating an expression is allowed:

## WinDbg, 4 bytes

```
?$u0

```

How this one works:

```
?                  $$ Evaluates an expression
 $u0               $$ The expression to evaluate

```

This one would have output like this (for input= A5F9):

```
Evaluate expression: 42489 = 0000a5f9

```

# Answer
> 1 votes
# C# .NET, 34 bytes

```
s=>System.Convert.ToInt32(s,16)+""

```

I have the feeling this is overly long, but the alternative `s=>int.Parse(s,System.Globalization.NumberStyles.HexNumber)+""` is even worse..

Try it online.

# Answer
> 1 votes
# Perl 5 `-lp`, 6 bytes

```
#!/usr/bin/perl -lp
$_=hex

```

Try it online!

# Answer
> 1 votes
# Io, 24 bytes

```
method(x,x fromBase(16))

```

Try it online!

# Answer
> 0 votes
# Tcl, 20 bytes

```
proc D n {expr 0x$n}

```

Try it online!

# Answer
> 0 votes
# Tcl, 19 bytes

```
puts [expr 0x$argv]

```

Try it online!

# Answer
> 0 votes
# Coconut, 15 bytes

```
str..int$(?,16)

```

Try it online!

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


title: Archimedes's cattle problem

text:
# Question
Title: Archimedes's cattle problem
> Compute, O friend, the number of the cattle of the sun which once grazed upon the plains of Sicily, divided according to color into four herds, one milk-white, one black, one dappled and one yellow. The number of bulls is greater than the number of cows, and the relations between them are as follows:
>
> **White bulls \\$= (\frac{1}{2} + \frac{1}{3})\\$ black bulls + yellow bulls,**
> **Black bulls \\$= (\frac{1}{4} + \frac{1}{5})\\$ dappled bulls + yellow bulls,**
> **Dappled bulls \\$= (\frac{1}{6} + \frac{1}{7})\\$ white bulls + yellow bulls,**
> **White cows \\$= (\frac{1}{3} + \frac{1}{4})\\$ black herd,**
> **Black cows \\$= (\frac{1}{4} + \frac{1}{5})\\$ dappled herd,**
> **Dappled cows \\$= (\frac{1}{5} + \frac{1}{6})\\$ yellow herd,**
> **Yellow cows \\$= (\frac{1}{6} + \frac{1}{7})\\$ white herd.**
>
> If thou canst give, O friend, the number of each kind of bulls and cows, thou art no novice in numbers, yet can not be regarded as of high skill. Consider, however, the following additional relations between the bulls of the sun:
>
> **White bulls + black bulls = a square number,**
> **Dappled bulls + yellow bulls = a triangular number.**
>
> If thou hast computed these also, O friend, and found the total number of cattle, then exult as a conqueror, for thou hast proved thyself most skilled in numbers.
>
> \- Archimedes

Some clarifications:

* black herd = black bulls + black cows, white herd = white bulls + white cows, etc.
* \\$(\frac{1}{2} + \frac{1}{3})\\$ black bulls + yellow bulls, means only the black bulls get the coefficient
* A square number is a number which can be represented as `n * n` where n is an integer
* A triangular number is a number which can be represented as `1 + 2 + ... + (n - 1) + n`

# Task

Write a program/function to output the size of the smallest herd that could satisfy both the first and second parts of the above problem.

# Output

You must output this number. Standard Output rules for integers apply.

# Scoring

This is so shortest bytes wins.

---

Hash of decimal representation of answer for easy checking:

* sha256 (with newline): `4fce7274734a18e9d27592e59480b50876da243de4caef4323f783339c456a7c`
* sha256 (without newline): `8500b362f3d6b5e96c775ca16d1475b519ff18669b0f6f3d35e4fb23d2c18d01`

---

*Inspired by The Archimedes Number - Numberphile*

# Answer
> 13 votes
# Sledgehammer, ~~67~~ ~~66~~ 26 bytes

## -40 bytes thanks to @GregMartin and I also no longer have any idea about how my answer works

Completes in less than a few seconds!

```
⡇⣄⠀⠇⣺⠇⢞⡞⣵⣍⠪⢺⡇⠜⢂⡒⢃⠦⠲⣎⠇⠣⡔⢻⡦⠔

```

Mathematica code:

```
Floor[Divide[25194541,184119152] * (NumberFieldFundamentalUnits@Sqrt[4729494])^4658]

```

(the reason for the Divide is that by default Mathematica represents `x/y` as `x * y^-1`, which is half a byte longer in Sledgehammer).

# Answer
> 12 votes
# Wolfram Language (Mathematica), ~~84~~ 83 bytes

```
224571490814418y^2/.{1}.FindInstance[x^2-410286423278424y^2==1&&x>1,{x,y},Integers]

```

Try it online!

-1 byte thanks to @J42161217.

Gives the identical result to the existing Sledgehammer solution. Uses the Pell equation directly to find the required y, and substitutes into the formula for the desired value. One problem was that the OEIS didn't have the correct constant factor (which must be multiplied by 4456749).

This one should be easier to port to other languages, since the Pell equation can be brute-forced using just integers.

### Deriving the formula

Start with the minimal solution of the linear equations, which is already present on MathWorld, where \\$W,X,Y,Z\\$ denote white, black, dappled, and yellow bulls and \\$w,x,y,z\\$ denote the cows, and \\$S\\$ is the grand total:

$$ W,X,Y,Z = 10366482, 7460514, 7358060, 4149387 \\ w,x,y,z = 7206360, 4893246, 3515820, 5439213 \\ W+X = 17826996, Y+Z = 11507447, S = 50389082 $$

Now we need to find the integer multiple of all the values such that \\$(W+X)n\\$ is a square and \\$(Y+Z)n\\$ is a triangular number (which can be alternatively written as "8 times that plus 1 is a square"):

$$ (W+X)n = x^2 \\ 8(Y+Z)n + 1 = y^2 $$

Note that \\$W+X\\$ is squarefree except for having the prime factor 2 twice, so \\$x\\$ must be a multiple of \\$\frac{W+X}{2}\\$. Substitute \\$x=\frac{W+X}{2}x\_1\\$, then we get

$$ n = \frac{W+X}{4}x\_1^2 $$

Substitute this into the equation for \\$y\\$ and rearrange a bit, then we get

$$ y^2 - 2(W+X)(Y+Z)x\_1^2 = 1 $$

So the \\$2(W+X)(Y+Z)\\$ is where the number 410286423278424 comes from. Now assume we solved it; then we have the value for \\$x\_1\\$. The final answer we want is \\$S n\\$, or

$$ S n = \frac{W+X}{4}Sx\_1^2 $$

where \\$\frac{W+X}{4}S\\$ evaluates to 224571490814418.

# Answer
> 10 votes
# JavaScript (Node.js),  ~~373 ... 304~~  296 bytes

Returns a BigInt of 206545 digits.

Most BigInt literals in the code are stored as strings in base 119. This saves 8 bytes but leads to many unprintable characters. Below is a sanitized version without this compression scheme.

```
_=>[...1e9+[9542]].map(i=>M.push(m=([a,b,c]=m,[d,e,f]=M[i-2]||m,[v=a*d+b*f,a*e+b*d,u=c*d+a*f])),m=[0x4EDF512CD794532694B80D70C2648ADB08931n,0x119A739D926824D28537A6B609D64903072098n,0x16163EA6FB9A566AD5B17C9614A6476F10864n],M=[[0x104941B82B6E51BED5n,0n,0x48F880D7EEB3F6CAAn]])&&v*u*v*u*48222351474n/4657n

```

Try it online!

Note: Interestingly, it takes 6 times longer to turn the number into a string than to compute it (~2400ms and ~400ms on TIO respectively).

## How?

### Preamble

Node is definitely not the right tool for the job. We need to use an algorithm relying on integers exclusively and we don't have any advanced math built-in at our disposal.

It would probably be possible to solve the Pell equation used by Bubbler, but given the magnitude of the number we're looking for, I doubt that a size-optimized version of such an algorithm would return anything in a reasonable amount of time.

In order to get something that actually works, I've decided to use the formula described in the next paragraph.

### Formula

This is an implementation of the method described in *A simple solution to Archimedes' cattle problem* by Antti Nygrén, whose final formula is:

$$\begin{pmatrix}v\\u\end{pmatrix}=\begin{pmatrix}a\_1&a\_2\\a\_3&a\_1\end{pmatrix}^{1164}\times\begin{pmatrix}r\_1\\r\_2\end{pmatrix}$$

$$T=6299\times 957\times u^2v^2+\frac{21054639\times 957\times u^2v^2}{4657}$$

with:

$$\begin{align}&a\_1=109931986732829734979866232821433543901088049\\ &a\_2=392567302329690546856394748066206816187916440\\ &a\_3=30784636507697855142356992218944109072681060\\ &r\_1=300426607914281713365\\ &r\_2=84129507677858393258\end{align}$$

### Implementation

We start with `m = [a1, a2, a3]` and `M = [[r1, 0, r2]]`.

We iterate through the list `[...1e9 + [9542]]` which expands to:

```
['1','0','0','0','0','0','0','0','0','0','9','5','4','2']

```

For each value \\$i\\$ in the above list:

* we build the vector `[a,b,c]` from `m`
* we build the vector `[d,e,f]` from either `M[i-2]` if it exists, or `m` otherwise
* we update `m` to `[v,v',u]` where:

$$\begin{pmatrix}v&v'\\u&\color{grey}{u'}\end{pmatrix}=\begin{pmatrix}a&b\\c&a\end{pmatrix}\times\begin{pmatrix}d&e\\f&d\end{pmatrix}=\begin{pmatrix}ad+bf&ae+bd\\cd+af&\color{grey}{ce+ad}\end{pmatrix}$$

Note: we don't need \\$u'\\$, so it's not computed at all
* we push the new instance of `m` into `M`

During the first 10 iterations, `M[i-2]` is undefined and `m` is used instead. So we essentially just square the original matrix 10 times. In other words, we compute:

$$\begin{pmatrix}a\_1&a\_2\\a\_3&a\_1\end{pmatrix}^{1024}$$

During the next 3 iterations, we multiply by previous occurrences of `m`: `M[9-2]`, `M[5-2]` and `M[4-2]`, which correspond to the original matrix to the power of \\$128\\$, \\$8\\$ and \\$4\\$ respectively in order to reach:

$$\begin{pmatrix}a\_1&a\_2\\a\_3&a\_1\end{pmatrix}^{1024+128+8+4}=\begin{pmatrix}a\_1&a\_2\\a\_3&a\_1\end{pmatrix}^{1164}$$

The last iteration is a multiplication by `M[0]` where we've stored `[r1, 0, r2]` at the very beginning of the process, leading to:

$$\begin{pmatrix}v&\color{grey}{v'}\\u&\color{grey}{u'}\end{pmatrix}=\begin{pmatrix}a\_1&a\_2\\a\_3&a\_1\end{pmatrix}^{1164}\times\begin{pmatrix}r\_1&\color{grey}{0}\\r\_2&\color{grey}{r\_1}\end{pmatrix}$$

At this point, \\$v\\$ and \\$u\\$ are set correctly and we just need to compute:

$$\frac{v^2u^2\times 48222351474}{4657}$$

# Answer
> 6 votes
# Python 2, 166 bytes

```
u=0x104941b82b6e51bed5
v=0x48f880d7eeb3f6caa
k=2*u*v
a=0x4edf512cd794532694b80d70c2648adb08931
exec"u,v=a*u+7766*k*v,a*v+609*k*u;"*1164
print u*u*v*v*48222351474/4657

```

Try it online!

Based on Arnauld's formula and method. I start with an initial `u,v`, and update them by a 2\*2 matrix operation 1164 times. I looked for constants sharing large common factors and extracted those.

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