title: Downward Number Race

text:
# Question
Title: Downward Number Race
Your task is to create a program that adds random numbers to previous sums in the ultimate number racing showdown.

Each racer (column) starts at 0 and adds either 1 or 0 to the previous sum at each step of the race until all of the racers reach the score required to win. The 1 or 0 should be chosen at random (the standard definition of random can be found here). The output will show the result of the race, with each column representing one racer, in this format:

```
>> racers:5,score needed:2

0 0 0 0 0 # all racers start at 0
+ + + + + # add
1 0 0 0 1 # random 1 or 0
= = = = = # equals
1 0 0 0 1 # sum
+ + + + +
0 0 0 0 1
= = = = =
1 0 0 0 2 # winner!
+ + + +
1 1 1 1
= = = =
2 1 1 1
  + + +
  1 1 1
  = = =
  2 2 2   # losers

```

*Note: only the numbers, +, and = need to be included in the output.*

## Input

Your program will accept the following two parameters as input:

1. the number of racers (columns), which must be greater than two
2. the score required to win, which must be greater than one

This is code-golf--the program with the least bytes wins.

*Edit: there's a non-enforceable max score of 9--this is to preserve the integrity of the column. Also, spaces between columns can be omitted in the output.*

# Answer
## Jelly, ~~37~~ ~~36~~ 33 bytes

```
,‘X
0Ç<³$Ð¿µżIFµ“+=”ṁṖ⁸żF
ÇÐ¡Ḋz⁶G

```

3 bytes thanks to Dennis.

Try it online

## Explanation

```
,‘X                    Helper link. Argument: n. Radomly return n or n+1.

 ‘                     Increment n
,                      Pair. Yield [n, n+1]
  X                    Return a random item from the pair.

0Ç<³$Ð¿µżIFµ“+=”ṁṖ⁸żF   Monadic link. Argument: s. Generate one racer.

0                       Start with value 0.
  <³$Ð¿µ                While value is less than s:
 Ç                        Use helper link to increment current value.
                        Collect intermediate results in a list.
         I              Compute consecutive differences.
        ż               Zip intermediate results with their next increment value 0 or 1.
          Fµ            Flatten. Let's call the current list A.
                        Odd items of A are racer state and even items are random 0 or 1.
            “+=”        Yield "+=".
                 Ṗ      Yield A without its last element.
                ṁ       Mold i.e Repeat the characters of the string until it contains length(A)-1 characters.
                  ⁸ż    Zipwith. Pair the elements of A with the correponding characters
                    F   Flatten.

ÇÐ¡ṫ2z” G               Main link. Arguments: s (score needed), r (#racers)

ÇÐ¡                     Call the link above r times.
                        Generate a list of r racers.
   Ḋ                    Remove first element of the list (its a garbage s value)
    z⁶                  Transpose with space as fill value.
      G                 Grid. Format the result.

```
> 5 votes

# Answer
# Pyth, ~~38~~ 34 bytes

```
~~j.tm+j\=jL\+C,.u+NYJ.WnsHQ+ZO2Y0J+\=QE~~
j.tmj\=jL\+.T,.u+NYJ.WnsHQ+ZO2Y0JE

```

Try it online!
> 5 votes

# Answer
## TSQL, ~~367~~ ~~345~~ 341 bytes

Golfed

```
DECLARE @r int=20, -- racers
        @g char=2  -- goal

DECLARE @ varchar(99)=REPLICATE('0',@r)a:PRINT @
DECLARE @A varchar(99)='',@s varchar(99)='',@i int=0WHILE @i<@r
SELECT
@i+=1,@A+=char(43-x*11),@s+=IIF(x=1,' ',LEFT(y,1)),@=RIGHT(@,@r-1)+IIF(x=1,' ',REPLACE(LEFT(@,1)+y,@g+1,' '))FROM(SELECT
IIF(LEFT(@,1)IN('',@g),1,0)x,ROUND(RAND(),0)y)z
PRINT @A+'
'+@s+'
'+REPLACE(@A,'+','=')IF @>''goto a

```

Try it online

Ungolfed:

```
DECLARE @r int=10, -- racers
        @g char=2  -- goal

DECLARE @ varchar(99)=REPLICATE('0',@r)
a:
PRINT @
DECLARE @A varchar(99)='',@s varchar(99)='',@i int=0

WHILE @i<@r
  SELECT
    @i+=1,
    @A+=char(43-x*11),
    @s+=IIF(x=1,' ',LEFT(y,1)),
    @=RIGHT(@,@r-1)+IIF(x=1,' ',REPLACE(LEFT(@,1)+y,@g+1,' '))
  FROM(SELECT IIF(LEFT(@,1)IN('',@g),1,0)x,ROUND(RAND(),0)y)z

PRINT @A+'
'+@s+'
'+REPLACE(@A,'+','=')

IF @>''GOTO a

```

Note that the random seed on the test site will always be the same, giving the same result each time, in studio management it will give different results. Can use different values for racers and goal to get a different picture
> 2 votes

# Answer
# Python 3, 237 bytes

```
from random import*
def f(n,t):
 x='0'*n,;i=j=0;y=''
 while' '*n!=x[i]:
  if j==n:j=0;x+=y,;y='';print(x[i]);i+=1
  y+=' 'if x[i][j]in(' ',str(t))else eval(["'+'","str(randint(0,1))","'='","str(int(x[i-3][j])+int(x[i-1][j]))"][i%4]);j+=1

```

A function that takes input via argument and prints to STDOUT. This approach makes use of the fact that the output follows a cycle of period four, of the form '+ value = value', for all racers. By using a counter modulo four, a list containing the desired value for each step as a string can be indexed into, and the result evaluated using Python's eval function.

**How it works**

```
from random import*                       Import Python's random module to access the
                                          randint function
def f(n,t):                               Function with input number of racers n and target
                                          number t
x='0'*n,;i=j=0;y=''                       Initialise return tuple storage x, state number
                                          i, racer number j and append string y for x
while' '*n!=x[i]:                         Loop through all j for some i. If the current
                                          state consists only of spaces, all racers have
                                          finished, so stop
y+=...eval([...][i%4])...                 Index into list, using i mod 4, to find the
                                          desired process for the cycle step, and append to
                                          y
(If first step of cycle)
...+...                                   Plus sign
(If second step of cycle)
...str(randint(0,1))...                   Random number from (0,1)
(If third step of cycle)
...=...                                   Equals sign
(If fourth step of cycle)
...str(int(x[i-3][j])+int(x[i-1][j]))...  Addition of random number to previous racer
                                          'score'
...' 'if x[i][j]in(' ',str(t))...         But append space if the racer has previously
                                          finished, or has reached the target
...j+=1                                   Increment j
if j==n:j=0;x+=y,;y='';print(x[i]);i+=1   If j=n, all j must have been looped through.
                                          Reset j, append new state y to x, reset y, print
                                          current state to STDOUT and increment i. When
                                          this first executes, x contains only the initial
                                          state, meaning that this is printed and the cycle
                                          starts with the second state.

```

Try it on Ideone
> 1 votes

# Answer
# Python 2, 191 bytes

```
from random import*
def c(p,w,r=[],l=0):
 while p:
	p-=1;s='0'
	while`w`>s[-1]:s+="+%s="%randint(0,1);s+=`eval(s[-4:-1])`;l+=2
	r+=[s]
 for z in map("".join,zip(*(t+l*' 'for t in r))):print z

```

Try it online!

---

# Python 3, 200 bytes

```
from random import*
def c(p,w,r=[],l=0):
 while p:
  p-=1;s='0'
  while str(w)>s[-1]:s+="+%s"%randint(0,1);s+="=%s"%eval(s[-3:]);l+=2
  r+=[s]
 for z in map("".join,zip(*(t+l*' 'for t in r))):print(z)

```

Try it online!
> 1 votes

# Answer
**Python 2, 278 bytes**

```
import random
r=5
w=2
s=(0,)*r
while s.count(w)<len(s):
    print ''.join(map(lambda a:str(a),s))+"\n"+'+'*len(s)
    s = tuple(map(lambda x: x<w and x+random.randrange(2) or x,s))
    print ''.join(map(lambda a:str(a), s))+"\n"+'='*len(s)
    s = tuple([x for x in s if x!= w])

```

where r is the no. of racers and w is the score to win

Try it here!
> 0 votes

# Answer
# Perl 5, 150 bytes

```
$,=$";say@n=(0)x(@e=('=')x(@p=('+')x<>));$t=<>;while(grep$_<$t,@n){@r=map{$_+=($g=0|rand 2);$g}@n;for$l(p,r,e,n){say map{$n[$_]>$t?$":$$l[$_]}0..$#n}}

```

Try it online!

First input is number of racers, second is score needed.
> 0 votes

---
Tags: code-golf
---


# Question
Title: Fundamental Solution of the Pell Equation
Given some positive integer \\$n\\$ that is not a square, find the fundamental solution \\$(x,y)\\$ of the associated Pell equation

$$x^2 - n\cdot y^2 = 1$$

### Details

* The fundamental \\$(x,y)\\$ is a pair of integers \\$x,y\\$ satisfying the equation where \\$x\\$ is minimal, and positive. (There is always the trivial solution \\$(x,y)=(1,0)\\$ which is not counted.)
* You can assume that \\$n\\$ is not a square.

### Examples

```
 n           x    y
 1           -    -
 2           3    2
 3           2    1
 4           -    -
 5           9    4
 6           5    2
 7           8    3
 8           3    1
 9           -    -
10          19    6
11          10    3
12           7    2
13         649    180
14          15    4
15           4    1
16           -    -
17          33    8
18          17    4
19         170    39
20           9    2
21          55    12
22         197    42
23          24    5
24           5    1
25           -    -
26          51    10
27          26    5
28         127    24
29        9801    1820
30          11    2
31        1520    273
32          17    3
33          23    4
34          35    6
35           6    1
36           -    -
37          73    12
38          37    6
39          25    4
40          19    3
41        2049    320
42          13    2
43        3482    531
44         199    30
45         161    24
46       24335    3588
47          48    7
48           7    1
49           -    -
50          99    14
51          50    7
52         649    90
53       66249    9100
54         485    66
55          89    12
56          15    2
57         151    20
58       19603    2574
59         530    69
60          31    4
61  1766319049    226153980
62          63    8
63           8    1
64           -    -
65         129    16
66          65    8
67       48842    5967
68          33    4
69        7775    936
70         251    30
71        3480    413
72          17    2
73     2281249    267000
74        3699    430
75          26    3
76       57799    6630
77         351    40
78          53    6
79          80    9
80           9    1
81           -    -
82         163    18
83          82    9
84          55    6
85      285769    30996
86       10405    1122
87          28    3
88         197    21
89      500001    53000
90          19    2
91        1574    165
92        1151    120
93       12151    1260
94     2143295    221064
95          39    4
96          49    5
97    62809633    6377352
98          99    10
99          10    1

```

Relevant OEIS sequences: A002350 A002349 A033313 A033317

# Answer
> 16 votes
# Piet, 612 codels

Takes *n* from standard input. Outputs *y* then *x*, space-separated.

Codel size 1:

Codel size 4, for easier viewing:

## Explanation

Check out this NPiet trace, which shows the program calculating the solution for an input value of 99.

I'm not sure whether I'd ever heard of Pell's equation before this challenge, so I got all of the following from Wikipedia; specifically, these sections of three articles:

Basically, what we do is this:

1. Get \\$n\\$ from standard input.
2. Find \\$\lfloor\sqrt n\rfloor\\$ by incrementing a counter until its square exceeds \\$n\\$, then decrement it once. (This is the first loop you can see in the trace, at top left.)
3. Set up some variables for calculating \\$x\\$ and \\$y\\$ from the continued fraction of \\$\sqrt n\\$.
4. Check whether \\$x\\$ and \\$y\\$ fit Pell's equation yet. If they do, output the values (this is the downwards branch about 2/3 of the way across) and then exit (by running into the red block at far left).
5. If not, iteratively update the variables and go back to step 4. (This is the wide loop out to the right, back across the bottom, and rejoining not quite halfway across.)

I frankly have no idea whether or not a brute-force approach would be shorter, and I'm not about to try it! Okay, so I tried it.

# Answer
> 10 votes
# Piet, 184 codels

This is the brute-force alternative I said (in my other answer) that I didn't want to write. It takes over 2 minutes to compute the solution for *n* = 13. I really don't want to try it on *n* = 29... but it checks out for every *n* up to 20, so I'm confident that it's correct.

Like that other answer, this takes *n* from standard input and outputs *y* then *x*, space-separated.

Codel size 1:

Codel size 4, for easier viewing:

## Explanation

Here's the NPiet trace for an input value of 5.

This is the most brutal of brute force, iterating over both \\$x\\$ and \\$y\\$. Other solutions might iterate over \\$x\\$ and then calculate \\$y=\sqrt{\frac{x^2-1}{n}}\\$, but they're *wimps*.

Starting from \\$x=2\\$ and \\$y=1\\$, this checks whether \\$x\\$ and \\$y\\$ have solved the equation yet. If it has (the fork at the bottom near the right), it outputs the values and exits.

If not, it continues left, where \\$y\\$ is incremented and compared to \\$x\\$. (Then there's some direction-twiddling to follow the zig-zag path.)

This last comparison is where the path splits around the mid-left. If they're equal, \\$x\\$ is incremented and \\$y\\$ is set back to 1. And we go back to checking if it's a solution yet.

I still have some whitespace available, so maybe I'll see if I can incorporate that square-root calculation without enlarging the program.

# Answer
> 6 votes
# Brachylog, 16 bytes

```
;1↔;Ċz×ᵐ-1∧Ċ√ᵐℕᵐ

```

Try it online!

### Explanation

```
;1↔                Take the list [1, Input]
   ;Ċz             Zip it with a couple of two unknown variables: [[1,I],[Input,J]]
      ×ᵐ           Map multiply: [I, Input×J]
        -1         I - Input×J must be equal to 1
          ∧        (and)
           Ċ√ᵐ     We are looking for the square roots of these two unknown variables
              ℕᵐ   And they must be natural numbers
                   (implicit attempt to find values that match those constraints)

```

# Answer
> 6 votes
# Pari/GP, 34 bytes

PARI/GP almost has a built-in for this: `quadunit` gives the fundamental unit of the quadratic field \\$\mathbb{Q}(\sqrt{D})\\$, where \\$D\\$ is the discriminant of the field. In other words, `quadunit(4*n)` solves the Pell's equation \\$x^2 - n \cdot y^2 = \pm 1\\$. So I have to take the square when its norm is \\$-1\\$.

I don't know what algorithm it uses, but it even works when \\$n\\$ is not square-free.

Answers are given in the form `x + y*w`, where `w` denotes \\$\sqrt{n}\\$.

```
n->(a=quadunit(4*n))*a^(norm(a)<0)

```

Try it online!

# Answer
> 4 votes
# Wolfram Language (Mathematica), 46 bytes

```
FindInstance[x^2-y^2#==1&&x>1,{x,y},Integers]&

```

Try it online!

# Answer
> 4 votes
# 05AB1E, ~~17~~ ~~16~~ 14 bytes

Saved a byte thanks to *Kevin Cruijssen*.
Outputs `[y, x]`

```
∞.Δn*>t©1%_}®‚

```

Try it online!

**Explanation**

```
∞                 # from the infinite list of numbers [1 ...]
 .Δ        }      # find the first number that returns true under
   n              # square
    *             # multiply with input
     >            # increment
      t©          # sqrt (and save to register as potential x)
        1%        # modulus 1
          _       # logical negation
            ®‚    # pair result (y) with register (x)

```

# Answer
> 4 votes
# Java 8, ~~74~~ ~~73~~ 72 bytes

```
n->{int x=1;var y=.1;for(;y%1>0;)y=Math.sqrt(-x*~++x/n);return x+" "+y;}

```

-1 byte thanks to *@Arnauld*.
-1 byte thanks to *@OlivierGrégoire*.

Try it online.

**Explanation:**

```
n->{                 // Method with double parameter and string return-type
  int x=1;           //  Integer `x`, starting at 1
  var y=.1;          //  Double `y`, starting at 0.1
  for(;y%1>0;)       //  Loop as long as `y` contains decimal digits:
    y=               //   Set `y` to:
      Math.sqrt(     //    The square-root of:
        -x*          //     Negative `x`, multiplied by
           ~++x      //     `(-x-2)` (or `-(x+1)-1)` to be exact)
                     //     (because we increase `x` by 1 first with `++x`)
               /n);  //     Divided by the input
  return x+" "+y;}   //  After the loop, return `x` and `y` with space-delimiter as result

```

# Answer
> 3 votes
# R,  ~~66~~ ~~56~~ ~~54~~ ~~53~~ ~~52~~ ~~47~~ 45 bytes

a full program

```
n=scan();while((x=(1+n*T^2)^.5)%%1)T=T+1;x;+T

```

~~-1 -2~~  thanks to @Giuseppe

-7 thanks to @Giuseppe & @Robin Ryder -2 @JAD

# Answer
> 3 votes
# Jelly, 40 bytes

```
½©%1İ$<®‘¤$Ð¿¹;Ḋ$LḂ$?Ḟṭ@ṫ-ṚZæ.ʋ¥ƒØ.,U¤-ị

```

Try it online!

An alternative Jelly answer, less golfy but more efficient algorithmically when x and y are large. This finds the convergents of the regular continued fraction that approximate the square root of n, and then checks which solve the Pell equation. Now correctly finds the period of the regular continued fraction.

Thanks to @TimPederick, I’ve also implemented an integer-based solution which should handle any number:

# Jelly, 68 bytes

```
U×_ƭ/;²®_$÷2ị$}ʋ¥µ;+®Æ½W¤:/$$
¹©Æ½Ø.;ÇƬṪ€F¹;Ḋ$LḂ$?ṭ@ṫ-ṚZæ.ʋ¥ƒØ.,U¤-ị

```

Try it online!

For example, the solution for 1234567890 has 1936 and 1932 digits for the numerator and denominator respectively.

# Answer
> 2 votes
# JavaScript (ES7), 47 bytes

```
n=>(g=x=>(y=((x*x-1)/n)**.5)%1?g(x+1):[x,y])(2)

```

Try it online!

Below is an alternate **49-byte** version which keeps track of \\$x²-1\\$ directly instead of squaring \\$x\\$ at each iteration:

```
n=>[(g=x=>(y=(x/n)**.5)%1?1+g(x+=k+=2):2)(k=3),y]

```

Try it online!

Or we can go the non-recursive way for **50 bytes**:

```
n=>eval('for(x=1;(y=((++x*x-1)/n)**.5)%1;);[x,y]')

```

Try it online!

# Answer
> 2 votes
# Haskell, 46 bytes

A straightforward brute force search. This makes use of the fact that a fundamental solution \\$(x,y)\\$ satisfying \\$x^2 - ny^2 = 1 \\$ must have \\$y \leq x\\$.

```
f n=[(x,y)|x<-[1..],y<-[1..x],x^2-n*y^2==1]!!0

```

Try it online!

# Answer
> 2 votes
# TI-BASIC,  ~~44~~  ~~42~~ 41 bytes

```
Ans→N:"√(N⁻¹(X²-1→Y₁:1→X:Repeat not(fPart(Ans:X+1→X:Y₁:End:{X,Ans

```

Input is \\$n\\$.
Output is a list whose values correspond to \\$(x,y)\\$.

Uses the equation \\$y=\sqrt{\frac{x^2-1}{n}}\\$ for \\$x\ge2\\$ to calculate the fundamental solution.
The current \\$(x,y)\\$ pair for that equation is a fundamental solution iff \\$y\bmod1=0\\$.

**Examples:**

```
6
               6
prgmCDGF12
           {5 2}
10
              10
prgmCDGF12
          {19 6}
13
              13
prgmCDGF12
       {649 180}

```

**Explanation:**

```
Ans→N:"√(N⁻¹(X²+1→Y₁:1→X:Repeat not(fPart(Ans:X+1→X:Y₁:End:{X,Ans  ;full logic

Ans→N                                                              ;store the input in "N"
      "√(N⁻¹(X²+1→Y₁                                               ;store the aforementioned
                                                                   ; equation into the first
                                                                   ; function variable
                     1→X                                           ;store 1 in "X"
                         Repeat not(fPart(Ans          End         ;loop until "Ans" is
                                                                   ; an integer
                                              X+1→X                ;increment "X" by 1
                                                    Y₁             ;evaluate the function
                                                                   ; stored in this variable
                                                                   ; at "X" and leave the
                                                                   ; result in "Ans"
                                                           {X,Ans  ;create a list whose
                                                                   ; values contain "X" and
                                                                   ; "Ans" and leave it in
                                                                   ; "Ans"
                                                                   ;implicitly print "Ans"

```

---

**Note:** TI-BASIC is a tokenized language. Character count does ***not*** equal byte count.

# Answer
> 2 votes
# MATL, 17 bytes

```
`@:Ut!G*-!1=&fts~

```

Try it online!

### Explanation

The code keeps increasing a counter *k* = 1, 2, 3, ... For each *k*, solutions *x*, *y* with 1 ≤ *x**k*, 1 ≤ *y**k* are searched. The process when some solution if found.

This procedure is guaranteed to find only one solution, which is precisely the fundamental one. To see why, note that

1. Any solution *x*\>0, *y*\>0 for *n*\>1 satisfies *x*\>*y*.
2. If *x*,*y* is a solution and *x*',*y*' is a different solution then necessarily *x**x*' *and* *y**y*'.

As a consequence of 1 and 2,

* When the procedure stops at a given *k*, only *one* solution exists for that *k*, because if there were two solutions one of them would been found earlier, and the process would have stopped with a smaller *k*.
* This solution is the fundamental one, because, again, if there were a solution with smaller *x* it would have been found earlier.

```
`       % Do...while
  @:U   %   Push row vector [1^2, 2^2, ..., k^2] where k is the iteration index
  t!    %   Duplicate and transpose. Gives the column vector [1^2; 2^2; ...; k^2]
  G*    %   Multiply by input n, element-wise. Gives [n*1^2; n*2^2; ...; n*k^2]
  -     %   Subtract with broadcast. Gives a square matrix of size n
  !     %   Transpose, so that x corresponds to row index and y to column index
  1=&f  %   Push row and column indices of all entries that equal 1. There can
        %   only be (a) zero such entries, in which case the results are [], [],
        %   or (b) one such entry, in which case the results are the solution x, y
  ts~   %   Duplicate, sum, negate. This gives 1 in case (a) or 0 in case (b)
        % End (implicit). Proceed with next iteration if top of the stack is true;
        % that is, if no solution was found.
        % Display (implicit). The stack contains copies of [], and x, y on top.
        % The empty array [] is not displayed

```

# Answer
> 2 votes
# Python 2, 49 bytes

```
a=input()**.5
x=2
while x%a*x>1:x+=1
print x,x//a

```

Try it online!

Finds `x` as the smallest number above 1 where `x % sqrt(n) <= 1/x`. Then, finds `y` from `x` as `y = floor(x / sqrt(n))`.

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), ~~70~~ 69 bytes

```
n=>{int x=1;var y=.1;for(;y%1>0;)y=Math.Sqrt(-x*~++x/n);return(x,y);}

```

Port of my Java 8 answer, but outputs a tuple instead of a string to save bytes.

Try it online.

# Answer
> 1 votes
# Jelly, 15 bytes

```
‘ɼ²×³‘½µ⁺%1$¿;®

```

Try it online!

A full program that takes a single argument `n` and returns a tuple of `x, y`.

# Answer
> 1 votes
# Husk, 12 bytes

```
ḟΛ¤ȯ=→*⁰□π2N

```

Try it online!

## Explanation

```
ḟΛ¤ȯ=→*⁰□π2N  Input is n, accessed through ⁰.
           N  Natural numbers: [1,2,3,4,..
         π2   2-tuples, ordered by sum: [[1,1],[1,2],[2,1],[1,3],[2,2],..
ḟ             Find the first that satisfies this:
 Λ             All adjacent pairs x,y satisfy this:
  ¤     □       Square both: x²,y²
   ȯ  *⁰        Multiply second number by n: x²,ny²
     →          Increment second number: x²,ny²+1
    =           These are equal.

```

# Answer
> 1 votes
# APL(NARS), 906 bytes

```
r←sqrti w;i;c;m
m←⎕ct⋄⎕ct←0⋄r←1⋄→3×⍳w≤3⋄r←2⋄→3×⍳w≤8⋄r←w÷2⋄c←0
i←⌊(2×r)÷⍨w+r×r⋄→3×⍳1≠×r-i⋄r←i⋄c+←1⋄→2×⍳c<900⋄r←⍬
⎕ct←m

r←pell w;a0;a;p;q2;p2;t;q;P;P1;Q;c;m
   r←⍬⋄→0×⍳w≤0⋄a0←a←sqrti w⋄→0×⍳a≡⍬⋄m←⎕ct⋄⎕ct←0⋄Q←p←1⋄c←P←P1←q2←p2←0⋄q←÷a
L: t←p2+a×p⋄p2←p⋄p←t
   t←q2+a×q
   :if c≠0⋄q2←q⋄:endif
   q←t
   P←(a×Q)-P
   →Z×⍳Q=0⋄Q←Q÷⍨w-P×P
   →Z×⍳Q=0⋄a←⌊Q÷⍨a0+P
   c+←1⋄→L×⍳(1≠Q×¯1*c)∧c<10000
   r←p,q
   :if c=10000⋄r←⍬⋄:endif
Z: ⎕ct←m

```

Above there are 2 functions sqrti function that would find the floor square root and pell function would return Zilde for error, and is based reading the page http://mathworld.wolfram.com/PellEquation.html it would use the algo for know the sqrt of a number trhu continue fraction (even if i use one algo for know sqrt using newton method) and stop when it find p and q such that

```
 p^2-w*q^2=1=((-1)^c)*Qnext

```

Test:

```
  ⎕fmt pell 1x
┌0─┐
│ 0│
└~─┘
  ⎕fmt pell 2x
┌2───┐
│ 3 2│
└~───┘
  ⎕fmt pell 3x
┌2───┐
│ 2 1│
└~───┘
  ⎕fmt pell 5x
┌2───┐
│ 9 4│
└~───┘
  ⎕fmt pell 61x
┌2────────────────────┐
│ 1766319049 226153980│
└~────────────────────┘
  ⎕fmt pell 4x
┌0─┐
│ 0│
└~─┘
  ⎕fmt pell 7373x
┌2───────────────────────────────────────────────────────────┐
│ 146386147086753607603444659849 1704817376311393106805466060│
└~───────────────────────────────────────────────────────────┘
  ⎕fmt pell 1000000000000000000000000000002x
┌2────────────────────────────────────────────────┐
│ 1000000000000000000000000000001 1000000000000000│
└~────────────────────────────────────────────────┘

```

There is a limit for cycles in the loop in sqrti function, and a limit for cycles for the loop in Pell function, both for the possible case number are too much big or algo not converge... (I don't know if sqrti converge every possible input and the same the Pell function too)

# Answer
> 1 votes
# MathGolf, 12 bytes

```
ökî²*)_°▼Þ√î

```

Try it online!

I'm throwing a Hail Mary when it comes to the output formatting. If it's not allowed, I have a solution which is 1 byte longer. The output format is `x.0y`, where `.0` is the separator between the two numbers.

## Explanation

```
ö       ▼      do-while-true with popping
 k             read integer from input
  î²           index of current loop (1-based) squared
    *          multiply the two
     )         increment (gives the potential x candidate
      _        duplicate TOS
       °       is perfect square
         Þ     discard everything but TOS
          √    square root
           î   index of previous loop (1-based)

```

I took some inspiration from Emigna's 05AB1E answer, but was able to find some improvements. If the separator I chose is not allowed, add a space before the last byte for a byte count of 13.

# Answer
> 0 votes
# Groovy, 53 bytes

```
n->x=1;for(y=0.1d;y%1>0;)y=((++x*x-1)/n)**0.5;x+" "+y

```

Try it online!

Port of Kevin Cruijssen's Java and C# answers

# Answer
> 0 votes
# Pyth, 15 bytes

```
fsIJ@ct*TTQ2 2J

```

Try it online here. Output is `x` then `y` separated by a newline.

# Answer
> 0 votes
# Wolfram Language (Mathematica), 41 bytes

```
{1//.y_/;!NumberQ[x=√(y^2#+1)]:>y+1,x}&

```

is the 3-byte Unicode character #221A. Outputs the solution in the order (y,x) instead of (x,y). As usual with the imperfect `//.` and its limited iterations, only works on inputs where the true value of `y` is at most 65538.

Try it online!

# Answer
> 0 votes
# \>\<\>, 45 bytes

```
11v
+$\~:1
:}/!?:-1v?=1-*}:{*:@:{*:
$  naon;>

```

Try it online!

Brute force algorithm, searching from `x=2` upwards, with `y=x-1` and decrementing on each loop, incrementing `x` when `y` reaches 0. Output is `x` followed by `y`, separated by a newline.

# Answer
> 0 votes
# C# (Visual C# Interactive Compiler), 69 bytes

```
n=>{for(int x=2,y;;x++)for(y=0;y<=x;y++)if(x*x-y*y*n==1)return(x,y);}

```

Try it online!

# Answer
> 0 votes
# Python 3, 75 bytes

```
lambda i:next((x,y)for x in range(2,i**i)for y in range(x)if~-x**2==i*y**2)

```

Try it online!

# Explanation

Brute force. Using $$x\<i^i$$ as an upper search bound, which is well below the definite upper limit of the fundamental solution to Pell's equation $$x\leq i!$$

This code would also run in Python 2. However, the range() function in Python 2 creates a list instead of a generator like in Python 3 and is thus immensely inefficient.

---

With inifinte time and memory, one could use a list comprehension instead of the iterator and save 3 bytes like so:

# Python 3, 72 bytes

```
lambda i:[(x,y)for x in range(i**i)for y in range(x)if~-x**2==i*y**2][1]

```

Try it online!

# Answer
> 0 votes
# Python 2, 64 bytes

```
f=lambda n,x=2,y=1:x*x-n*y*y-1and f(n,x+(x==y),y*(y<x)+1)or(x,y)

```

Try it online!

Returns `(x, y)`.

---
Tags: code-golf, math, number-theory, abstract-algebra, polynomials
---


title: Alphanumeric Line and Curve Counting

text:
# Question
Title: Alphanumeric Line and Curve Counting
Given an input string, write a program that outputs the total number of lines and curves it has.

## The Challenge

* Take input from `STDIN`, or any other input method.
* Output to `STDOUT`, or any other output method, the total number of lines and curves contained in the string, *in that order*, based on the below table in the code snippet.
* Any non-alphanumeric characters should be ignored.
* Standard loopholes are forbidden.
* This is , so shortest code wins.

## Clarifications

* The lines and curves are determined by the font used on Stackexchange for `code blocks`.
* Circles (like `O, o, 0`) and dots (`i, j`), are considered to be 1 curve each.
* Input can be a string, list of characters, stream of characters, bytecodes etc.
* Output can be an array of integers, tuple of integers, comma-separated string, etc. *The two numbers must be separate,* so `104` is not valid, but `10,4`, `10 4`, `10\n4`, `[10,4]`, `(10, 4)`, and so on is.
* Heading and trailing whitespace is perfectly acceptable.

### Sample Input and Output

```
# Format: str -> line, curve
hi -> 4, 2
HELLO WORLD -> 20, 4
l33+ 5pEak -> 13, 8
+=-_!...?~`g@#$%^ -> 1, 2
9001 -> 5, 3
O o O o O o -> 0, 6

```

### Character Table

```
Char | Lines | Curves
0    | 1     | 1
1    | 3     | 0
2    | 1     | 1
3    | 0     | 2
4    | 3     | 0
5    | 2     | 1
6    | 0     | 1
7    | 2     | 0
8    | 0     | 2
9    | 0     | 1
A    | 3     | 0
B    | 1     | 2
C    | 0     | 1
D    | 1     | 1
E    | 4     | 0
F    | 3     | 0
G    | 2     | 1
H    | 3     | 0
I    | 3     | 0
J    | 1     | 1
K    | 3     | 0
L    | 2     | 0
M    | 4     | 0
N    | 3     | 0
O    | 0     | 1
P    | 1     | 1
Q    | 0     | 2
R    | 2     | 1
S    | 0     | 1
T    | 2     | 0
U    | 0     | 1
V    | 2     | 0
W    | 4     | 0
X    | 4     | 0
Y    | 3     | 0
Z    | 3     | 0
a    | 0     | 2
b    | 1     | 1
c    | 0     | 1
d    | 1     | 1
e    | 1     | 1
f    | 1     | 1
g    | 1     | 2
h    | 1     | 1
i    | 3     | 1
j    | 1     | 2
k    | 3     | 0
l    | 3     | 0
m    | 3     | 2
n    | 2     | 1
o    | 0     | 1
p    | 1     | 1
q    | 1     | 1
r    | 1     | 1
s    | 0     | 1
t    | 1     | 1
u    | 1     | 1
v    | 2     | 0
w    | 4     | 0
x    | 4     | 0
y    | 1     | 1
z    | 3     | 0

```

# Answer
## Haskell, ~~214~~ ~~199~~ ~~188~~ 175 bytes

```
 g 0=[]
 g n=mod n 5:g(div n 5)
 d#s=sum[n|c<-d,(i,n)<-zip['0'..]$g s,c==i]
 f s=(s#0x300BBD37F30B5C234DE4A308D077AC8EF7FB328355A6,s#0x2D5E73A8E3D345386593A829D63104FED5552D080CA)

```

Try it online!

The numbers of lines and curves are the digits of base-5 numbers and stored as base-16 numbers. Function `g` translates back to base-5.

Edit: -13 bytes thanks to @cole.
> 8 votes

# Answer
# 05AB1E, ~~78~~ ~~69~~ 65 bytes

*-4 bytes thanks to Kevin Cruijssen, Go and check out his even better 05AB1E answer*

```
žKÃÇ48-©•7ć_qýÊΣŸßαŽ_ì¡vFÛ–ÄÔ™”súyån!₁ζB?òrβÂ@µk₆¼×¬°•5в2ä`®èrè‚O

```

Try it online!

Outputs as \[Curve, Line\]

I'm really bad at 05AB1E I just found out. Can definitely save more bytes if I can get 05AB1E to do `è` across my list of lists

---

## Explanation

```
žKÃ                                    #Filter out non alpha-nums
    Ç48-                               #Convert to ascii and subtract 48 so "0" is 0 etc.
        ©                              #Store that for later
          •...•5в                      #De-compress compressed list
                 2ä                    #Split into 2 chunks (lines + curves)
                   `                   #Separate them onto the stack
                    ®                  #Get the value that we stored
                     èrè               #Apply indexing to both lists
                        ‚              #Put our indexed values back into a list
                         O             #Sum our lists

```
> 6 votes

# Answer
# Jelly, 45 bytes

```
ØBċþSḋ“yƘ.ṪñF[)µṡṭɗḌyė$Ṫk“¢⁶KɱzV$QḂḥỵṙu’b5,3¤

```

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

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

### How?

```
ØBċþSḋ“...“...’b5,3¤ - Link: list of characters, T
ØB                   - base-chars = "01...9A...Za...z'
   þ                 - outer product with T using:
  ċ                  -   count occurrences
    S                - sum -> [n(0), n(1), ..., n(9), n(A), ..., n(Z), n(a), ..., n(z)]'
                   ¤ - nilad followed by link(s) as a nilad:
      “...“...’      -   list of two large integers (encoded in base 250)
                5,3  -   five paired with three = [5,3]
               b     -   to base  -> [[Lines(0), Lines(1), ...], Curves(0), Curves(1), ...]
     ḋ               - dot-product

```
> 5 votes

# Answer
# Python 2, ~~159~~ 154 bytes

For any character `lines*4 + curves` gives value from 0 to 16. Base-36 is used to encode these values (1 character = 1 value).

-5 bytes thanks to @Chas Brown

```
lambda s:map(sum,zip(*(divmod(int("5c52c918210000000c615gc9cc5c8gc15291818ggcc00000025155565d6cce915551558gg5c"[ord(x)-48],36),4)for x in s if'/'<x<'{')))

```

Try it online!

# Python 2, 141 bytes

This is a port of my Python3 solution. This version outputs a list of long ints, so it looks like `[4L, 2L]` instead of `[4, 2]`.

```
lambda s:map(sum,zip(*(divmod(int("8BK5NLC8RS10XWUX12BG408C2UELUAFEOVARZKCHEEDDMXG09L48ZG",36)/13**(ord(x)-48)%13,3)for x in s if'/'<x<'{')))

```

Try it online!
> 5 votes

# Answer
# Scala, 235 bytes

```
val a=('0'to'9')++('A'to'Z')++('a'to'z')
def f(s:String)=s.filter(a.contains(_)).map(c=>"gdgkdhfckfdlfgedhddgdcedfgkhfcfceeddkgfggglgilddnhfgggfggceegd"(a.indexOf(c))-'a').map(x=>(x%5,x/5)).foldLeft((0,0))((x,y)=>(x._1+y._1,x._2+y._2))

```

Try it online!

Not so small, probably can be golfed further.
Note: The 52-character string literal is like a dictionary which maps a character to another character which denotes number of lines and curves according to the following table:

```
Curves|Lines
      |0 1 2 3 4
----------------
     0|a b c d e
     1|f g h i j
     2|k l m n o

```
> 5 votes

# Answer
# JavaScript (Node.js), ~~251 219~~ 217 bytes

*-34 bytes from @Expired Data* **:o**

```
_=>_.map(a=>(p+=~~"13103202003101432331324301020202443301011111313332011101124413"[(x=a.charCodeAt()-48)>16?(x-=7)>41?x-=6:x:x])&(o+=~~"10120110210211001001000011211010000021111121120021111111100010"[x]),p=o=0)&&[p,o]

```

Try it online!
> 4 votes

# Answer
# Jelly, 51 bytes

```
ØBiⱮị“Æƭ&¶*ṪḳAøƬsøD<~²ṂvṠỤṣT3rdʠ¬⁻ÇṆṇ.ÑƑaȮż’b5¤s2¤S

```

Try it online!

A monadic link that takes a string as input and returns a list of integers as `[lines, curves]`
> 4 votes

# Answer
# , ~~164~~ 153 bytes

```
function(s,`!`=utf8ToInt,x=(!"

")[match(!s,c(48:57,65:90,97:122),0)])c(sum(x%%5),sum(x%/%5))

```

Try it online!

I had the same idea as nimi's answer using a base 5 encoding but encodes as ASCII characters instead of base 16. Uses `nomatch = 0` in `match` to eliminate non-alphanumeric characters.

Returns `curves lines`.
> 4 votes

# Answer
# Retina 0.8.2, 160 bytes

```
$
¶$`
T`dLl`13103202003101432331324301020202443301011111313332011101124413`^.*
T`dLl`10120110210211001001000011211010000021111121120021111111100010`.*$
.
$*
%`1

```

Try it online! Link includes test cases. Explanation:

```
$
¶$`

```

Duplicate the input string.

```
T`dLl`13103202003101432331324301020202443301011111313332011101124413`^.*

```

Count each character's lines on the first line.

```
T`dLl`10120110210211001001000011211010000021111121120021111111100010`.*$

```

Count each character's curves on the second line.

```
.
$*
%`1

```

Sum the digits separately on each line.
> 4 votes

# Answer
# Charcoal, 60 bytes

```
ＩＥ⟦”)⊞∧cⅉ→ÞＹγμ◧⊞¶u№¶⊘¶∕«⁸””)∨⧴｜υ;↷dLτＩüＯ¦:”⟧Σ⭆Φθ№⭆ι⍘ξφλ§ι⍘λφ

```

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

```
Ｅ⟦”)⊞∧cⅉ→ÞＹγμ◧⊞¶u№¶⊘¶∕«⁸””)∨⧴｜υ;↷dLτＩüＯ¦:”⟧

```

This is an array of two strings `13103202000101111131333201110112441331014323313243010202024433` and `10120110212111112112002111111110001002110010010000112110100000`. The strings are then mapped over.

```
Φθ№⭆ι⍘ξφλ

```

The elements of the input are filtered over whether they are contained within the (62) characters of the default base conversion alphabet.

```
⭆...§ι⍘λφ

```

The elements that remain are then converted from base (62) and this is then indexed into the mapped string.

```
Ｉ...Σ...

```

The digits are summed and cast back to string for implicit print.
> 4 votes

# Answer
# Python 2, ~~179~~ ~~166~~ ~~165~~ 163 bytes

```
lambda s:[sum(p[:max(0,p.find(c))].count(',')for c in s)for p in',02BDJPbdefghjpqrtuy,57GLRTVnv,14AFHIKNYZiklmz,EMWXwx',',02569CDGJOPRSUbcdefhinopqrstuy,38BQagjm']

```

Try it online!

Returns a list `[curves, lines]`.
> 4 votes

# Answer
# Python 3, ~~165~~ ~~159~~ ~~148~~ 146 bytes

For any character (including non-alphanumeric) `lines*3 + curves` gives value from 0 to 12, so we can use long base-13 number to encode data. To make it shorter it is converted to base-36.

Thanks to @Chas Brown for great advices.

-2 bytes by converting lambda to program.

```
print(*map(sum,zip(*(divmod(int("8BK5NLC8RS10XWUX12BG408C2UELUAFEOVARZKCHEEDDMXG09L48ZG",36)//13**(ord(x)-48)%13,3)for x in input()if'/'<x<'{'))))

```

Try it online!
> 4 votes

# Answer
# Python 2, 525 bytes

```
l=c=0;e=[(1,1),(3,0),(1,2),(0,2),(3,0),(2,1),(0,1),(2,0),(0,2),(0,1),(3,0),(1,2),(0,1),(1,1),(4,0),(3,0),(2,1),(3,0),(3,0),(1,1),(3,0),(2,0),(4,0),(3,0),(0,1),(1,1),(0,2),(2,1),(0,1),(2,0),(0,1),(2,0),(4,0),(4,0),(3,0),(3,0),(0,2),(1,1),(0,1),(1,1),(1,1),(1,1),(1,2),(1,1),(3,1),(1,2),(3,0),(3,0),(3,2),(2,1),(0,1),(1,1),(1,1),(1,1),(0,1),(1,1),(1,1),(2,0),(4,0),(4,0),(1,1),(3,0)]
d='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
for i in input():
 if i in d:
  p=d.find(i);l+=e[p][0];c+=e[p][1];
print l,c

```

Try it online!

Similar approach to the reference implementation but somewhat shorter.
> 3 votes

# Answer
# Perl 5 `-MList::Util=sum -p`, 180 bytes

```
say sum y/0-9A-Za-z/13103202003101432331324301020202443301011111313332011101124413/r=~/./g;$_=sum y/0-9A-Za-z/10120110210211001001000011211010000021111121120021111111100010/r=~/./g

```

Try it online!
> 2 votes

# Answer
# 05AB1E, 53 bytes

```
•xþ¢*>ÌŸÑå#÷AUI'@æýXÁи<¥èå–ΘηžÎà₅åÇšÄ•5вR2ôžKISk®KèøO

```

Try it online or verify all test cases.

**Explanation:**

```
•xþ¢*>ÌŸÑå#÷AUI'@æýXÁи<¥èå–ΘηžÎà₅åÇšÄ•
                 '# Compressed integer 101629259357674935528492544214548347273909568347978482331029666966024823518105773925160
 5в               # Converted to base-5 as list: [1,0,2,0,0,2,1,0,1,2,0,3,2,0,1,1,0,3,1,1,0,3,0,3,0,4,0,4,0,2,1,0,0,2,1,0,1,2,2,0,1,1,1,0,0,3,0,4,0,2,0,3,1,1,0,3,0,3,1,2,0,3,0,4,1,1,1,0,2,1,0,3,0,3,1,1,0,4,0,4,0,2,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,2,2,3,0,3,0,3,2,1,1,3,1,1,2,1,1,1,1,1,1,1,1,0,1,1,2,0]
   R              # Reverse this list (due to the leading 0)
    2ô            # Split it into pairs: [[0,2],[1,1],[0,1],[1,1],[1,1],[1,1],[1,2],[1,1],[3,1],[1,2],[3,0],[3,0],[3,2],[2,1],[0,1],[1,1],[1,1],[1,1],[0,1],[1,1],[1,1],[2,0],[4,0],[4,0],[1,1],[3,0],[3,0],[1,2],[0,1],[1,1],[4,0],[3,0],[2,1],[3,0],[3,0],[1,1],[3,0],[2,0],[4,0],[3,0],[0,1],[1,1],[0,2],[2,1],[0,1],[2,0],[0,1],[2,0],[4,0],[4,0],[3,0],[3,0],[1,1],[3,0],[1,1],[0,2],[3,0],[2,1],[0,1],[2,0],[0,2],[0,1]]
      žK          # Push builtin string "abc...xyzABC...XYZ012...789"
        IS        # Push the input, split into characters
          k       # Get the index of each of these characters in the builtin-string
           ®K     # Remove all -1 for non-alphanumeric characters that were present
             è    # Use these indices to index into the earlier created pair-list
              ø   # Zip/transpose; swapping rows/columns
               O  # Sum both inner lists
                  # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `•xþ¢*>ÌŸÑå#÷AUI'@æýXÁи<¥èå–ΘηžÎà₅åÇšÄ•` is `101629259357674935528492544214548347273909568347978482331029666966024823518105773925160` and `•xþ¢*>ÌŸÑå#÷AUI'@æýXÁи<¥èå–ΘηžÎà₅åÇšÄ•5в` is `[1,0,2,0,0,2,1,0,1,2,0,3,2,0,1,1,0,3,1,1,0,3,0,3,0,4,0,4,0,2,1,0,0,2,1,0,1,2,2,0,1,1,1,0,0,3,0,4,0,2,0,3,1,1,0,3,0,3,1,2,0,3,0,4,1,1,1,0,2,1,0,3,0,3,1,1,0,4,0,4,0,2,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,2,2,3,0,3,0,3,2,1,1,3,1,1,2,1,1,1,1,1,1,1,1,0,1,1,2,0]`.
> 2 votes

# Answer
# Python 3, 697 bytes

```
def f(s):
    l=0;c=0;d={'0':(1,1),'1':(3,0),'2':(1,2),'3':(0,2),'4':(3,0),'5':(2,1),'6':(0,1),'7':(2,0),'8':(0,2),'9':(0,1),'A':(3,0),'B':(1,2),'C':(0,1),'D':(1,1),'E':(4,0),'F':(3,0),'G':(2,1),'H':(3,0),'J':(1,1),'K':(3,0),'L':(2,0),'M':(4,0),'N':(3,0),'O':(0,1),'P':(1,1),'Q':(0,2),'R':(2,1),'S':(0,1),'T':(2,0),'U':(0,1),'V':(2,0),'W':(4,0),'X':(4,0),'Y':(3,0),'Z':(3,0),'a':(0,2),'b':(1,1),'c':(0,1),'d':(1,1),'e':(1,1),'f':(1,1),'g':(1,2),'h':(1,1),'i':(3,1),'j':(1,2),'k':(3,0),'l':(3,0),'m':(3,2),'n':(2,1),'o':(0,1),'p':(1,1),'q':(1,1),'r':(1,1),'s':(0,1),'t':(1,1),'u':(1,1),'v':(2,0),'w':(4,0),'x':(4,0),'y':(1,1),'z':(3,0)};
    for i in s:
        if i in d:
            l+=d[i][0];c+=d[i][1];
    return l,c

```

A simple first attempt. I put the table into a dictionary, looped through the string, incremented some counters, and returned a tuple. Input is a string.

Try it online!
> 1 votes

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

```
x=>(x=x.Where(n=>n<123&n>47)).Sum(n=>p[n-48]/5)+" "+x.Sum(n=>p[n-48]%5);var p=@"

";

```

Try it online!
> 1 votes

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


title: Generate an Acronym

text:
# Question
Title: Generate an Acronym
This is similar to Making an acronym, but there are several key differences, including the method of fetching the acronym, and this challenge including flexible output.

## Task

Given a string (list of chars/length 1 strings is allowed) containing only printable ASCII, output all capital letters in the input that are either preceded by a space or a dash, or are the first character in the input. Empty string is undefined behavior.

## Test Cases:

Output may be in the format of `"TEST"`, `["T","E","S","T"]`, or whatever else works for you.

```
Self-contained Underwater Breathing Apparatus
SUBA

a Programming Language
PL

NATO Atlantic TREATY Organization
NATO

DEFCON 2
D

hello, world!

light-Emitting dioDe
E

What Does the Fox Say?
WDFS

3D mov-Ies
I

laugh-Out Lou-D
OLD

Best friends FOREVE-r
BF

--

<space>

--  --a -  - --

--  -- -  - -- A
A

Step-Hen@Gmail-Mail Mail.CoM m
SHMM

```

This is , so shortest answer in bytes wins.

# Answer
> 8 votes
# , 7 bytes

```
ÍÕü¼À!õ

```

Try it online!

Here is a hexdump to prove the byte count:

```
00000000: cdd5 fcbc c021 f5                        .....!.

```

Explanation:

```
Í       " Search and replace all occurrences on all lines:
        " (Search for)
 Õ      "   A non-uppercase letter [^A-Z]
  ü     "   OR
      õ "   An uppercase letter
    À!  "   Not preceded by...
   ¼    "   A word-boundary
        " (implicitly) And replace it with:
        "   Nothing

```

This is short all thanks to V's wonderful regex compression.

# Answer
> 8 votes
# , ~~66~~ 63 bytes

```
function(s)(s=substr(strsplit(s,' |-')[[1]],1,1))[s%in%LETTERS]

```

Try it online!

*-3 bytes thanks to Scarabee*

An anonymous function; returns the acronym as a vector `c("N","A","T","O")` which is implicitly printed.

For once, this isn't too bad in R! splits on `-` or `(space)`, takes the first element of each of those, and then returns whichever ones are capitals (`LETTERS` is an R builtin with the capital letters), in order.

# Answer
> 6 votes
# Python 2, ~~59~~ 56 bytes

<sup>-3 bytes thanks to Lynn</sup>

```
lambda s:[b for a,b in zip(' '+s,s)if'@'<b<'['>a in' -']

```

Try it online!

# Answer
> 5 votes
# Javascript 21 bytes

Takes a string input and outputs an array of strings containing the acronym characters

```
x=>x.match(/\b[A-Z]/g)

```

## Explanation

It's just a global regex match for word-boundary followed by a capital letter.

# Answer
> 4 votes
# Dyalog APL, ~~29~~ 23 bytes

*Bonus test case: A Programming Language (APL).*

```
'(?<=^| |-)[A-Z]'⎕S'&'⊢

```

Returns an array of chars (shows as space seperated on TIO).

Try it online!

---

### Older post, 29 bytes

```
{(⎕AV~⎕A)~⍨'(\w)\w+'⎕R'\1'⊢⍵}

```

Try it online!

**How?**

`'(\w)\w+'⎕R` \- replace each cluster of alphabetic chars

`'\1'` \- with its first character

`~⍨` \- remove every char

`(⎕AV~⎕A)` \- that is not an ASCII uppercase

# Answer
> 4 votes
# Retina, ~~21~~ 17 bytes

```
!`(?<=^| |-)[A-Z]

```

Try it online!

### Explanation

Outputs the matches of the regex `(?<=^| |-)[A-Z]` in the input, one per line (`!`).

# Answer
> 3 votes
# C#, ~~84~~ 78 bytes

```
using System.Linq;s=>s.Where((c,i)=>c>64&c<91&(i>0?s[i-1]==32|s[i-1]==45:1>0))

```

*Saved 6 bytes thanks to @jkelm.*

Try it online!

Full/Formatted Version:

```
using System.Collections.Generic;
using System.Linq;

class P
{
    static void Main()
    {
        System.Func<string, IEnumerable<char>> f = s => s.Where((c, i) => c > 64 & c < 91 & (i > 0 ? s[i-1] == 32 | s[i-1] == 45: 1 > 0));

        System.Console.WriteLine(string.Concat(f("Self-contained Underwater Breathing Apparatus")));
        System.Console.WriteLine(string.Concat(f("a Programming Language")));
        System.Console.WriteLine(string.Concat(f("NATO Atlantic TREATY Organization")));
        System.Console.WriteLine(string.Concat(f("DEFCON 2")));
        System.Console.WriteLine(string.Concat(f("hello, world!")));
        System.Console.WriteLine(string.Concat(f("light-Emitting dioDe")));
        System.Console.WriteLine(string.Concat(f("What Does the Fox Say?")));
        System.Console.WriteLine(string.Concat(f("3D mov-Ies")));
        System.Console.WriteLine(string.Concat(f("laugh-Out Lou-D")));
        System.Console.WriteLine(string.Concat(f("Best friends FOREVE-r")));
        System.Console.WriteLine(string.Concat(f(" ")));
        System.Console.WriteLine(string.Concat(f("--  --a -  - --")));
        System.Console.WriteLine(string.Concat(f("--  -- -  - -- A")));

        System.Console.ReadLine();
    }
}

```

# Answer
> 3 votes
# Python, 53 bytes

```
import re
lambda s:re.findall("(?<=[ -])[A-Z]"," "+s)

```

Try it online!

A simple regular expression with a lookahead for space or dash. Rather than matching the start, prepend a space.

# Answer
> 3 votes
# Julia 0.6.0 (57 bytes)

```
s=split(s,r" |-");for w∈s isupper(w[1])&&print(w[1])end

```

Explanation: This is my first code-golf. Pretty straight forward. Split the words, print 1rst upper letter of each.

Probably easy to do better using regex but I am new to this

# Answer
> 2 votes
# Swift 5, 110 bytes

-5 thanks to Cœur

```
import UIKit
func f(s:[String]){for i in zip(s,[" "]+s){if i.0.isUppercase()&&"- ".contains(i.1){print(i.0)}}}

```

---

## Detailed Explanation

* `import Foundation` \- Imports the module `Foundation` that is vital for `zip()`, the main piece of this code.
* `func f(s:[String]){...}` \- Creates a function with a parameter `s`, that is a list of Strings, representing the characters of the input.
* `for i in zip(s,[" "]+s){...}` \- Iterates with `i` through the zip of the input and the input with a space added in the beginning, which is *very* helpful for getting the previous character in the String.
* `if` \- Checks whether:

+ `i.0==i.0.uppercased()` \- The current character is uppercase,
    + `&&"- ".contains(i.1)` \- and If the previous character is a space or a dash.
* If the above conditions are met, then:

+ `print(i.0)` \- The character is printed, because it is part of the acronym.

# Answer
> 2 votes
# Jelly,  ~~11~~  10 bytes

-1 byte thanks to Erik the Outgolfer ( splits at spaces \>\_\<)

```
⁾- yḲḢ€fØA

```

A monadic link taking and returning lists of characters.
As a full program accepts a string and prints the result.

**Try it online!** or see a test suite.

### How?

```
⁾- yḲḢ€fØA - Link: list of characters, x       e.g. "Pro-Am Code-golf Association"
   y       - translate x with:
⁾-         -   literal list of characters ['-',' '] "Pro Am Code golf Association"
    Ḳ      - split at spaces               ["Pro","Am","Code","golf","Association"]
     Ḣ€    - head each (1st character of each)      "PACgA"
        ØA - yield uppercase alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
       f   - filter keep                            "PACA"
           - if running as a full program: implicit print

```

# Answer
> 2 votes
# C# (.NET Core), 108 bytes

```
n=>{var j="";n=' '+n;for(int i=0;++i<n.Length;)if(" -".IndexOf(n[i-1])>=0&n[i]>64&n[i]<91)j+=n[i];return j;}

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 11 bytes

```
'-ð‡ð¡ζнAuÃ

```

Try it online!

# Answer
> 2 votes
# Japt, ~~19~~ ~~16~~ 14 bytes

*-2 bytes thanks to Shaggy*

```
f/^| |-)\A/ mÌ

```

Try it online!

# Answer
> 2 votes
# Perl 5, 25 bytes

**24 bytes code + 1 for `-n`.**

Annoying that `grep -P` support variable length look-behind but Perl doesn't :(.

```
print/(?:^| |-)([A-Z])/g

```

-1 byte thanks to @Dada!

Try it online! \- includes `-l` to run all tests at once.

# Answer
> 2 votes
# MATL, 19 bytes

```
'- 'X{&Yb'^[A-Z]'XX

```

Try it online!

# Answer
> 2 votes
# Brachylog, ~~25~~ ~~23~~ 22 bytes

```
,Ṣ↻s₂ᶠ{h∈" -"&t.∧Ạụ∋}ˢ

```

Try it online!

*(-2 bytes thanks to @Fatalize.)*

```
,Ṣ↻                      % prepend a space to input
   s₂ᶠ                   % get all substrings of length 2 from that, to get prefix-character pairs
      {              }ˢ  % get the successful outputs from this predicate:
       h∈" -"              % the prefix is - or space
               &t.∧        % then the character is the output of this predicate if:
                  Ạụ∋        % the alphabet uppercased contains the character

```

# Answer
> 2 votes
# PowerShell, 43 bytes

```
''+($args|sls '(?<=^| |-)[A-Z]'-a -ca|% m*)

```

Try it online!

Unrolled:

```
''+($args|select-string '(?<=^| |-)[A-Z]' -allmatches -caseSensitive|% matches)

```

# Answer
> 2 votes
# Python 3, 67 bytes

```
lambda x:[c[0]for c in x.replace("-"," ").split()if c[0].isupper()]

```

Try it online!

# Answer
> 1 votes
# Python 3, ~~73~~ 70 bytes

```
lambda n:[n[x]for x in range(len(n))if'@'<n[x]<'['and(' '+n)[x]in' -']

```

Try it online!

---

# Explanation

* `lambda n:` \- Creates an anonymous lambda-function with a String parameter `n`.
* `n[x]` \- Gets the character of `n` at index `x`.
* `for x in range(len(n))` \- Iterates from `0` to the length of `n`, naming the variable `x`.
* `if` \- Checks:

+ `'@'<n[x]<'['` \- If the character is uppercase,
    + `and(' '+n)[x]in' -'` \- And if it is preceded by a space or a dash in the String formed by a space and `n`.

# Answer
> 1 votes
# JavaScript (SpiderMonkey), 62 bytes

```
n=s=>(""+s.match(/([ -]|^)[A-Z]/g)).replace(/[ \-,]|null/g,"")

```

Try it online!

# Answer
> 1 votes
# Pyth, 12 bytes

Created one year after the initial answer.

```
rI#1hMcXQ\-d

```

Try it online!

### Pyth, 21 bytes

Initial answer.

```
:+dQ"(?<=[ -])[A-Z]"1

```

Try it online!

# Answer
> 1 votes
# Pyth, ~~15~~ 16 bytes

```
@rG1<R1:w"[ -]"3

```

Test suite

# Answer
> 1 votes
# QuadS, 17 bytes

```
(?<=^| |-)[A-Z]
&

```

Try it online!

# Answer
> 1 votes
# Bash (grep), ~~29~~ 28 bytes

```
grep -oP'(?<=^| |-)[A-Z]' a

```

A port of my python answer but because `pgrep` supports variable length lookbehinds it's noticeably shorter (even accounting for the overhead of python). Stick the test cases in a file called `a`, output is 1 character per line.

-1 Thanks to Neil

# Answer
> 1 votes
# Pyth, 12 bytes

```
@rG1hMcXz\-d

```

Test suite here.

# Answer
> 1 votes
# RProgN 2, 18 bytes

```
`-` rû#ùr.'[a-z]'-

```

## Explained

```
`-` rû#ùr.'[a-z]'-
`-`                     # Push "-" literal, and " " literal.
    r                   # replace, Replaces all "-"s with " "s.
     û                  # Split, defaultly by spaces.
      #ù                # Push the head function literally.
        r               # Replace each element of the split string by the head function, which gets each first character.
         .              # Concatenate, which collapses the stack back to a string.
          '[a-z]'-      # Push the string "[a-z]" literally, then remove it from the string underneith, giving us our output.

```

Try it online!

# Answer
> 1 votes
# PHP, 62 bytes

```
for(;~$c=$argn[$i++];$p=$c!="-"&$c!=" ")$c<A|$c>Z|$p?:print$c;

```

Run as pipe with `-nR` or try it online.

other solutions:

```
foreach(preg_split("#[ -]#",$argn)as$s)$s[0]>Z|$s<A?:print$s[0];  # 64 bytes
preg_match_all("#(?<=\s|-)[A-Z]#"," $argn",$m);echo join($m[0]);  # 64 bytes
preg_match_all("#(?<=\s|-)\p{Lu}#"," $argn",$m);echo join($m[0]); # 65 bytes

```

# Answer
> 1 votes
## Lua, 79 75 bytes

```
for i=1,#t do for i in(" "..t[i]):gmatch"[%-| ]%u"do print(i:sub(2))end end
```

Try it!

I stuck a print() before the final end in the try it version because otherwise it's a mess. This program perfectly adheres to the requirements of I/O and matching, but without that extra new line it's pretty hard to read.

Input is given in the form of a table of number:string , number incrementing by 1 each time and starting at 1.

Explanation:

It for loops through a gmatch of each input string. The gmatch search is as follows:

\[%-| \] - Group, search for a - or a space

%u - Search for an uppercase character

Then for each match, it prints it out minus the preceding dash or space

Edit: Golfed 4 bytes by removing the declaration of 'a' and adding the space to the input inside the for loop in, as well as changing the sub input to just 2 rather than 2,2 (which produce equivalent results)

# Answer
> 1 votes
## C++, 168 bytes

```
#include<string>
auto a=[](auto&s){auto r=s.substr(0,1);if(r[0]<65||r[0]>90)r="";for(int i=1;i<s.size();++i)if(s[i]>64&&s[i]<91&&(s[i-1]==32||s[i-1]==45))r+=s[i];s=r;};

```

Output done via the parameter

# Answer
> 1 votes
## Ruby, ~~55~~ ~~30~~ 29 + 1 = ~~56~~ ~~31~~ 30 bytes

Run with `-e` flag (+1)

```
p (?-+$_).scan(/[ -]([A-Z])/)

```

Explanation: this is much easier as a regex if there's a hyphen in the beginning to match

Note: this returns a 2d list of characters like `[["S"], ["U"], ["B"], ["A"]]`, which should be fine because

> Output may be in the format of "TEST", \["T","E","S","T"\], or whatever else works for you.

# Answer
> 1 votes
# JavaScript, 49 bytes

```
s=>(s.match(/(^| |-)[A-Z]/g)||[]).map(x=>x[1]||x)

```

Try it online

# Answer
> 1 votes
# Japt, 6 bytes

Outputs an array of characters, or the empty array.

```
f"%b%A

```

Try it

# Answer
> 1 votes
# SNOBOL4 (CSNOBOL4), 86 bytes

```
	S =' ' INPUT
S	S ANY(' -') ANY(&UCASE) . X REM . S	:F(O)
	O =O X	:(S)
O	OUTPUT =O
END

```

Try it online!

```
	S =' ' INPUT					;* prepend a space
S	S ANY(' -') ANY(&UCASE) . X REM . S	:F(O)	;* find an initial
	O =O X	:(S)					;* add to output string
O	OUTPUT =O					;* print
END

```

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


title: Character Frequency in a String

text:
# Question
Title: Character Frequency in a String
Given a string of printable ASCII, output the frequency of each character in that string.

## The Challenge

* Input is given as a string of printable ASCII characters (decimal `[32-126]` inclusive).
* Output the frequency of each character, in ASCII order.
* The output must have a format similar to `[character][separator][count]`. Provided that there is a single, non-newline separating string between the character and its frequency, it is a valid output.
* Output can be a single string, multiple strings, list of 2-tuples, array of tuples, etc.
* Input and output can be given using any convenient method.
* Standard loopholes are forbidden.
* This is , so shortest in bytes wins.

## Sample I/O

```
abcd
//outputs
a: 1
b: 1
c: 1
d: 1

```

```
Over 9001!
//outputs
  [ 1
! [ 1
0 [ 2
1 [ 1
9 [ 1
O [ 1
e [ 1
r [ 1
v [ 1

```

```
--<-<<+[+[<+>--->->->-<<<]>]<<--.<++++++.<<-..<<.<+.>>.>>.<<<.+++.>>.>>-.<<<+.
//outputs (as 2-tuples)
(+,14),(-,13),(.,13),(<,21),(>,13),([,2),(],2)

```

```
Su3OH39IguWH
//outputs (as 2d array)
[[3,2],[9,1],[H,2],[I,1],[O,1],[S,1],[W,1],[g,1],[u,2]]

```

# Answer
# Python 3, ~~50, 43~~, 41 bytes

```
lambda s:{c:s.count(c)for c in sorted(s)}

```

Try it online!
> 12 votes

# Answer
# Ohm v2, 2 bytes

Try it online!

```
      implicit input
S     sort string
 Ö    run-length encoding
      implicitly print

```
> 9 votes

# Answer
# Python 3, 41 bytes

```
lambda s:sorted({*zip(s,map(s.count,s))})

```

Try it online!
> 8 votes

# Answer
# , 13 bytes

```
({.;#)/.~@/:~

```

Try it online!

* `@/:~` sort the input and...
* `/.~` partition it into groups of like items. Apply the following to each group...
* `({.;#)` take the first element `{.` and link it `;` to the number of items in the group `#`
> 7 votes

# Answer
# Brachylog, 2 bytes

```
ọo

```

Try it online!

```
ọ     Occurrences,
 o    sorted.

```

It's essentially the same as using an RLE builtin with the sorting requirement, but if the output could be in any order it would just be .
> 7 votes

# Answer
# APL (Dyalog Extended), 5 bytesSBCS

Anonymous tacit prefix function, returning a two-column table, which by default prints with space as separator between character and count, and line break after each entry.

```
,∘≢⌸∧

```

Try it online!

`,` character followed

by

its tally

for each unique character

in ascending order
> 6 votes

# Answer
# Haskell, ~~52~~ 49 bytes

*-3 bytes thanks to cole!*

```
import Data.List
map((,).nub<*>length).group.sort

```

Try it online!

I know this is too long (especially that import), but I'm new at Haskell golfing and hoping to get better! Outputs as a list of tuples of `(character, count)` (note the `character` is `String`, not a `Char`).
> 6 votes

# Answer
# Perl 6, 15 bytes

```
*.comb.Bag.sort

```

Try it online!

Anonymous code block that takes a string and returns a list of pairs, where the key is the character and the value is the number of occurrences.

### Explanation:

```
*.comb           # Decompose into characters
      .Bag       # Group into unordered bag of character => occurrences
          .sort  # Sort by character

```
> 5 votes

# Answer
# CJam, ~~8~~ 4 bytes

```
$e`p

```

Try it online!

-3 bytes thanks to Jonah, and -1 byte from rule interpretation.

A perfect challenge for CJam. ~~I had hoped that the RLE encode operator would output `[char, count]`, but the order was reversed. Otherwise it would have been a 5-byter.~~ After Jonah's comment, I switched the order of the output. ~~I'm not sure if the first read should be counted, since the standard rules permit input to be on the stack at the start of the program. If that's the case, this answer is one byte shorter.~~ From this meta discussion, I concluded that the read could be placed in the header. Otherwise I could modify the script to be a function without changing the byte count.

## Explanation

```
 $       sort string
  e`     RLE-encode (transforms "aabc" to [[2, "a"], [1, "b"], [1, "c"]]
    p    print

```

**Open question**: would something like this be allowed if transforming the answer to a function, or should the brackets be included in the byte count?
> 5 votes

# Answer
# Bash, ~~27~~ ~~22~~ 20 bytes

```
fold -1|sort|uniq -c

```

Try it online!

*-5 bytes thanks to Neil*

*-2 bytes thanks to Digital Trauma*
> 4 votes

# Answer
# Jelly, ~~6~~ 3 bytes

```
ṢŒr

```

Try it online!

A monadic link taking the string as its argument. Returns a list of lists, each one containing the character and count. The footer formats this as a grid.
> 4 votes

# Answer
# Pyth, 3 bytes

```
r8S

```

Try it online!

Simply run-length encodes (`r8`) the sorted (`S`) input. Output is a list of tuples of `[frequency, character]`.
> 4 votes

# Answer
# T-SQL 2008 query, 130 bytes

```
DECLARE @ varchar(2000)='kabcdda'

SELECT w,sum(1)FROM(SELECT
substring(@,number+1,1)FROM
spt_values WHERE type='P'and
number<len(@))x(w)GROUP BY w
ORDER BY ascii(w)

```

**Try it online**
> 4 votes

# Answer
# PHP, 57 bytes

```
foreach(count_chars($argn,1)as$a=>$b)echo chr($a)," $b
";

```

Try it online!

Input via `STDIN`, run with `php -F`:

```
$ echo Su3OH39IguWH|php -F cc.php
3 2
9 1
H 2
I 1
O 1
S 1
W 1
g 1
u 2

```

Fun fact: this challenge is basically the **Example 1** on the PHP docs for `count_chars()`.
> 4 votes

# Answer
# JavaScript, 58 bytes

```
s=>[...s].sort().flatMap(c=>c>p?[p=[c,1]]:p[1]++&&[],p=[])

```

Try it online!

Thanks Shaggy, -1 byte.

---

# Retina, 18 bytes

```
O`.
(.)\1*
$1,$.&¶

```

Try it online!

I don't speak Retina. I just translated above JavaScript answer to Retina with some searching.

Thanks to Cows quack, -3 bytes.
> 3 votes

# Answer
# PowerShell, ~~27~~ ~~22~~ ~~21~~ 19 bytes

```
$args[0]|sort|group

```

Try it online!

Exactly what it says on the tin. Takes input `$args[0]` via splatting (manifests on TIO as a `[char[]]`), `sort`s it, then `group-object` it into a grouping.

*-8 bytes thanks to mazzy*
> 3 votes

# Answer
# C (gcc), 94 91 bytes

Thanks to Ourous and ceilingcat for their suggestions.

To get the non-newline separator, I'm making use of the fact that negative numbers get a "-" for free! :-)

```
f(char*s){char c[255]={},i=31;for(;*s;)c[*s++]--;for(;++i>0;)c[i]&&printf("%c%d ",i,c[i]);}

```

Try it online!
> 3 votes

# Answer
# Wolfram Language (Mathematica), 34 bytes

```
KeySortBy[ToCharacterCode]@*Counts

```

Try it online!

Returns an association.

---

```
SortBy[ToCharacterCode@@#&]@*Tally

```

Try it online!

Returns a list.
> 2 votes

# Answer
# C# (Visual C# Interactive Compiler), 63 61 bytes

```
s=>s.OrderBy(c=>c).GroupBy(c=>c).Select(g=>(g.Key,g.Count()))

```

Try it online!

Thanks to Expired Data for pointing me towards the C# Interactive Compiler and for showing me the power of dynamics.
> 2 votes

# Answer
# K4, 9 bytes

**Solution:**

```
#:'=x@<x:

```

**Example:**

```
q)k)#:'=x@<x:"Over 9001!"
 | 1
!| 1
0| 2
1| 1
9| 1
O| 1
e| 1
r| 1
v| 1

```

**Explanation:**

```
#:'=x@<x: / the solution
       x: / store input as x
      <   / indices to sort ascending
    x@    / apply (@) to x
   =      / group same values
#:'       / count (#:) each (')

```
> 2 votes

# Answer
# brainfuck, 128 114 bytes

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

```

Try it online!

How it works:

```
-                                          sets cell 0 to 255, which is used to move back to cell 2 later on
>>                                         moves to cell 2
,[                                         we load our first input and loop until there are no more characters to load
[-[>>+<<-]>>]                              keeps moving forward skipping every other cell until it has moved forward the ASCII value of the most recently loaded character
>+<                                        adds one to the next cell for the purpose of later looking at to see how many of that character was entered
+[-<<+]->>                                 goes back to cell 2
,]                                         loads in next character and repeats process if there are remaining characters

+[+>[                                      checks IF the next cell has a value other than 0
<--.                                       then, if true, it prints the ASCII value of the previous cells contents
++<<+++++++[>++++++++<-]>++.               then print ":"
[-]++++++[>>++++++++<<-]>>.                then print the number value of the contents of the current cell
[-].]                                      then print a null character and leaves the if statement
<[>>+<<-]>>]                               continues the same process skipping every other cell, until it repeats 255 times

```

Thanks to Jo King, -14 bytes.

This is my second brainfuck program, first being hello world, and first time golfing, so please let me know what I can do to improve my program and answer!
> 2 votes

# Answer
# APL(NARS), 26 chars, 52 bytes

```
{m,¨+/¨{w=⍵}¨m←k[⍋k←∪w←⍵]}

```

test:

```
  ⎕fmt{m,¨+/¨{w=⍵}¨m←k[⍋k←∪w←⍵]}'is, this good or not?'
┌12─────────────────────────────────────────────────────────────────────────────────┐
│┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐│
││   4│ │ , 1│ │ ? 1│ │ d 1│ │ g 1│ │ h 1│ │ i 2│ │ n 1│ │ o 4│ │ r 1│ │ s 2│ │ t 2││
│└+───┘ └+───┘ └+───┘ └+───┘ └+───┘ └+───┘ └+───┘ └+───┘ └+───┘ └+───┘ └+───┘ └+───┘2
└∊──────────────────────────────────────────────────────────────────────────────────┘

  {m,¨+/¨{w=⍵}¨m←k[⍋k←∪w←⍵]}
                     k←∪w←⍵     copy the argument in w, k is the argument that has unique elements
               m←k[⍋       ]    copy k order, in m, (so m is argument unique ordered)
         {w=⍵}¨m                see each element of m in w, so each element of m generate a len(w) bit list
      +/¨                       sum each bit list above obtain the number of element of m in w
   m,¨                          make couples

```
> 2 votes

# Answer
# Clean, 60 bytes

```
import StdEnv
$s=sort[(c,sum[1\\k<-s|k==c])\\c<-removeDup s]

```

Try it online!

Defines the function `$ :: [Char] -> [(Char, Int)]` giving the result as a list of 2-Tuples.
Uses the element-wise behavior of `<` and thus `sort` on Tuples to ensure codepoint ordering.
> 1 votes

# Answer
# sfk, ~~124~~ ~~87~~ 84 bytes

```
xed -i
+chars
+count -same -case
+xed "_?????*x*[white]?_[parts 6,3,1]_"
+sort -case

```

Try it online!

Gives output in the form `[character]x[count]` with `count` padded to 5 digits.
> 1 votes

# Answer
# JavaScript, 57 bytes

Outputs a 2D-Array. Had to implement a quick & dirty fix for the sorting so I'll need to come back to try to golf that.

```
s=>[...s].map(o=x=>o[x]=-~o[x])&&Object.entries(o).sort()

```

Try It Online!
> 1 votes

# Answer
# Charcoal, 13 bytes

```
ＥΦγ№θι⁺⁺ι №θι

```

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

```
  γ             Printable ASCII
 Φ              Filtered where non-zero
   №            Count of
     ι          Current character in
    θ           Input string
Ｅ               Map over filtered characters
        ι       Current character
       ⁺        Plus a space
      ⁺         Plus
          №     Count of
            ι   Current character in
           θ    Input string
                Implicitly output on separate lines

```
> 1 votes

# Answer
# Japt, ~~10~~ 8 bytes

```
ü
mÎíUmÊ

```

Try it

```
ü\nmÎíUmÊ     :Implicit input of string U
ü             :Split, sort and partition by value
 \n           :Reassign to U
   m          :Map
    Î         :  First element
     í        :Interleave with
      UmÊ     :  Map lengths of U

```
> 1 votes

# Answer
# Kotlin, 75 bytes

```
fun String.c()=toCharArray().sorted().map{Pair(it,count{s->it==s})}.toSet()

```

Try it online!
> 1 votes

# Answer
# Java (JDK), 82 bytes

```
s->s.stream().sorted().distinct().map(c->c+" "+s.stream().filter(x->c==x).count())

```

Try it online!
> 1 votes

# Answer
# Japt, 7 bytes

```
¬ü ®âZl

```

Test it online!
> 1 votes

# Answer
## Haskell, 46 bytes

```
f x=[(c,sum[1|d<-x,d==c])|c<-[' '..],elem c x]

```

Try it online!
> 1 votes

# Answer
# Ruby `-n`, 43 bytes

```
p$_.chars.uniq.sort.map{|c|[c,$_.count(c)]}

```

Try it online!
> 1 votes

# Answer
# Kotlin, 53 bytes

Returns a `Map<Char, Int>` associating characters to frequencies. The map keys are sorted in ASCII order (it's a `java.util.SortedMap` underneath.)

```
{s->s.associateWith{c->s.count{it==c}}.toSortedMap()}

```

Try it online!
> 1 votes

# Answer
# 05AB1E, ~~8~~ 6 bytes

```
SêDŠ¢ø

```

Try it online!
> 1 votes

# Answer
# (in C locale), 32 bytes

```
function(s)table(strsplit(s,''))

```

Try it online!

`strsplit` the input character string by the empty string to separate its characters then `table` builds a contingency table of the unique character counts.
> 1 votes

# Answer
# JavaScript, ~~55~~  ~~48~~  ~~62~~ 57 bytes

```
a=>[...a].sort().map(c=>o.set(c,-~o.get(c)),o=new Map)&&o

```

output is a `Map`

contrary to `Objects`, `Map` remember the order in which values where sets

```
let input = document.getElementById("input")
let run = document.getElementById("run")
let output = document.getElementById("output")

run.onclick = () => {
  output.innerHTML = ""
  func(input.value).forEach((val, key) => output.innerHTML += `'${key}' => ${val}<br>`)
}

let func = a=>[...a].sort().map(c=>o.set(c,-~o.get(c)),o=new Map)&&o
```

```
<input id="input"/>
<button id="run">run</button>
<p id="output"></p>
```

Thanks to Shaggy and Einacio for pointing my flaws

*-5 bytes thanks to Shaggy*
> 1 votes

# Answer
# Forth (gforth), 134 bytes

```
: f here 128 allot dup 128 erase -rot 0 do 2dup i + c@ + 1 swap +! loop drop
128 0 do dup i + c@ ?dup if i emit ." : ". cr then loop ;

```

Try it online!

Limitation: won't work if any character occurs more than 256 times in a single string (to fix this requires an extra ~25 bytes)

### Explanation

* Allocate an area of memory 128 bytes (cells if needed) wide to use as an array/dictionary
* Zero out all bytes/cells in that area
* Loop through string, for each character
    + Add ascii value to array starting address, then increment value at that address by 1
* When finished, loop through array/dictionary and output all chars/values that have a value other than 0

### Code Explanation

```
: f                     \ start new word definition
  here 128 allot        \ allocate 128 bytes to use as an array
  dup 128 erase         \ fill array with zeros
  -rot                  \ stick array address behind string address
  0 do                  \ start counted loop from 0 to string-length - 1
    2dup                \ duplicate array and string address
    i + c@              \ get ascii value of next character in string
    + 1 swap +1         \ add to array address, then add 1 to the value in that array position
  loop                  \ end the loop
  drop                  \ drop the string address [no longer needed]
  128 0 do              \ start a counted loop from 0 to 127
    dup i + c@          \ get value at next array position
    ?dup                \ duplicate if >0
    if                  \ start an if block (if >0)
      i emit            \ output the character
      ." : ".           \ output ": " followed by the number of that char in the string
      cr                \ output a newline
    then                \ end the if block
  loop                  \ end the loop
;                       \ end the word definition

```
> 1 votes

# Answer
# Red, 92 bytes

```
func[s][parse/case sort/case s[any[copy k[copy t skip thru any t](print[t length? to""k])]]]

```

Try it online!
> 0 votes

# Answer
# Perl 5 (`-nF` `-M5.01` `-MList::Util=uniq`), ~~49~~ 41 bytes

41 bytes : `for$a(uniq sort@F){say"$a ",eval"y/$a//"}` doesn't work if input contains a slash. Otherwise, 36 bytes : `for$a(uniq sort@F){say"$a "./\Q$a/g}` doesn't work because of `//g` in scalar context.

```
for$a(uniq sort@F){say"$a ".(()=/\Q$a/g)}

```

TIO

first answer
> 0 votes

# Answer
# Scala, ~~64~~ 62 bytes

```
(x:String)=>x.groupBy(identity).mapValues(_.size).toSeq.sorted

```
> 0 votes

# Answer
# C++ (gcc), 85 bytes

```
#include<map>
auto f(std::string s){std::map<char,int>m;for(int c:s)m[c]++;return m;}

```

Try it online!

This solution makes use of several nice features of std::map:

1. It has a sorted iterator, with default lexicographic ordering.
2. The `[]`-operator default initializes members, in case of int it zeroes it.

Also, C++17 allows for golfing using `auto` and range-for loop.
> 0 votes

# Answer
# SNOBOL4 (CSNOBOL4), 120 bytes

```
	A =&ALPHABET
	I =INPUT
S	O =0
	A LEN(1) . X REM . A	:F(END)
R	I X =	:F(O)
	O =O + 1	:(R)
O	OUTPUT =GT(O) X 0 O	:(S)
END

```

Try it online!

```
	A =&ALPHABET			;* alias for &ALPHABET (256 characters in ascending order)
	I =INPUT			;* read input
S	O =0				;* set counter to 0
	A LEN(1) . X REM . A	:F(END)	;* set X to first letter of A
					;* setting the REMainder to A
					;* and going to END if no letters remain
R	I X =	:F(O)			;* remove the first occurrence of X from I
					;* and output if none are left
	O =O + 1	:(R)		;* increment the counter, going to R
O	OUTPUT =GT(O) X 0 O	:(S)	;* if O > 0,
					;* output X 0 and O in that order
					;* then GOTO S
END

```
> 0 votes

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

```
s=>[...s].sort().reduce((a,b)=>(a[b]=(a[b]||0)+1)&&a,{})

```

Try it online!
> 0 votes

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


title: Decode the Void

text:
# Question
Title: Decode the Void
A void list is a list that at no level contains any non-list objects. Or if you prefer a recursive definition

* The empty list is void
* A list containing only other void lists is void

All void lists have a finite depth.

Here are some examples of void lists (using python syntax):

```
[]
[[]]
[[],[]]
[[[]]]
[[[]],[]]
[[],[[]]]

```

Here are some examples of things that are *not* void lists:

```
["a"]
[[...]]
[1]
2
[[],([],[])]

```

---

# Task

Write two separate functions (or programs if you prefer). One should take a positive integer (you may also include zero if you wish) as an argument and return a void list the other should take a void list and return it an integer. These two functions should always be inverses of each other. That is if you pass the output of `f` into `g` you should get the original input of `f` as the result of `g`. This means the mapping must be 1:1, i.e. for every integer, there may only exist **exactly one** void list for which `g` gives that integer and for every void list there should be exactly one integer for which `f` gives that void list.

You are essentially creating a Bijection

You may choose to use a string representation of a void list (with or without commas and spaces) instead of your languages native list type.

# Scoring

Your score will be the lengths of your two functions together. This is so you should aim to minimize this sum.

# Answer
> 8 votes
# Pyth, 27 + 29 = 56 bytes

`f`:

```
L?bol`NS{sm[d+d]Y]d)ytb]Y@y

```

Test suite

`g`:

```
L?bol`NS{sm[d+d]Y]d)ytb]Yxyl`

```

Test suite

The system is very simple: I generate all possible lists with no more than a certain number of `[`'s. Then, I sort them in such a way that the lists I haven't generated yet would be near the end. This is all done by the function `y`, identical in both programs. It is written as

```
L?bol`NS{sm[d+d]Y]d)ytb]Y

```

Then, I index into this list for `f`, and search through it for `g`.

The number of lists I generate is chosen to be large enough that I have generated all possible lists which would appear at or before the desired location in the infinite sorted list.

The programs allow/return 0 as an option.

# Answer
> 5 votes
# Python 2, 96 bytes

Try it online! to test the bijection.

```
f=lambda l:len(l)and f(l[0])*2+1<<f(l[1:])

```

Takes void lists to non-negative integers. 42 bytes.

```
g=lambda n:n*[g]and[g(n/(n&-n)/2)]+g(len(bin(n&-n))-3)

```

Takes non-negative integers to void lists. 54 bytes. A more recursive attempt gave the same length.

```
g=lambda n,i=0:n*[g]and[g(n/2,i+1),[g(n/2)]+g(i)][n%2]

```

# Answer
> 1 votes
# Java 7, 725 bytes

`f(int)` (**325 bytes**):

```
String f(int i){String s="";for(int j=0,e=0;e<i;e+=v(s))s=Integer.toBinaryString(j++);return"["+s.replace("1","[").replace("0","]")+"]";}int v(String s){for(;!s.isEmpty();s=s.replaceFirst("1","").replaceFirst("0",""))if(s.replace("1","").length()!=s.replace("0","").length()|s.charAt(0)<49|s.endsWith("1"))return 0;return 1;}

```

`g(String)` (**75 + 325 bytes**):

```
int g(String s){int r=0;for(String i="10";!i.equals(s);i=f(++r));return r;}

```

Since method `g` uses method `f` to calculate it's result by looping over possible void-list until it founds the one equal to the one inputted, the bytes of `f` are counted twice (since both methods should be able to run without the other for this challenge).

**Explanation:**

In general, method `f` simply loops over all binary String-representations of integers, and increase a counter every time a valid one is found. Valid binary-Strings for this challenge comply to the following rules: They start with a `1`, and end with a `0`; they have an equal number of 1s and 0s; and every time you remove the first `1` and `0` and validate what is left again, these two rules still apply. After the counter equals the input, it converts that binary-String to a String void-list, by replacing all `1` with `[` and all `0` with `]`.

As for method `g`: We start with `"[]"` (representing void-list `0`), and then continue using method `f` while increasing an integer, until it matches the input-String.

```
String f(int i){         // Method `f` with integer parameter and String return-type
  String s="";           //  Start with an empty String
  for(int j=0,e=0;e<i;   //  Loop as long as `e` does not equal the input
      e+=v(s))           //    And append increase integer `e` if String `s` is valid
    s=Integer.toBinaryString(j++);
                         //   Change `s` to the next byte-String of integer `j`
                         //  End of loop (implicit / single-line body)
  return"["+             //  Return the result String encapsulated in "[" and "]"
    s.replace("1","[").replace("0","]")+"]";
                         //  after we've replaced all 1s with "[" and all 0s with "]"
}                        // End of method `f`

int v(String s){         // Separate method with String parameter and integer return-type
  for(;!s.isEmpty();     //  Loop as long as String `s` isn't empty
      s=s.replaceFirst("1","").replaceFirst("0",""))
                         //    After each iteration: Remove the first "1" and "0"
    if(s.replace("1","").length()!=s.replace("0","").length()
                         //   If there isn't an equal amount of 1s and 0s
       |s.charAt(0)<49   //   or the String doesn't start with a 1
       |s.endsWith("1")) //   or the String doesn't end with a 0
      return 0;          //    Return 0 (String is not valid)
                         //  End of loop (implicit / single-line body)
  return 1;              //  Return 1 (String is valid)
}                        // End of separate method

int g(String s){         // Method `g` with String parameter and integer return-type
  int r=0;               // Result integer
  for(String i="[]";!i.equals(s);
                         //  Loop as long as `i` does not equal the input String
      i=f(++r));         //   After each iteration: Set `i` to the next String in line
  return r;              //  Return the result integer
}                        // End of method `g`

```

**Example input & output cases:**

Try it here. (NOTE: It's pretty slow for the last few test cases. Will take around 10-15 sec for all of them.)

```
0   <-> []
1   <-> [[]]
2   <-> [[][]]
3   <-> [[[]]]
4   <-> [[][][]]
5   <-> [[][[]]]
6   <-> [[[]][]]
7   <-> [[[][]]]
8   <-> [[[[]]]]
9   <-> [[][][][]]
10  <-> [[][][[]]]
11  <-> [[][[]][]]
12  <-> [[][[][]]]
13  <-> [[][[[]]]]
14  <-> [[[]][][]]
50  <-> [[[][[[]]]]]
383 <-> [[[][]][[[][]]]]

```

# Answer
> 1 votes
# K (ngn/k), 49 bytes

```
{$[#x;2/,/1,'&:'o'x;0]}
{$[x;o'|-1+-1-':&|2\x;()]}

```

Try it online!

uses the formula from the example in Bijection: tree-like lists - natural numbers

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

```
f=(n,i)=>n?n&1<<i?[f(i),...f(n>>-~i)]:f(n,-~i):[]
g=([a,...b])=>a?g(b)*2+1<<g(a):0

```

Try it online!

xnor's idea

# Answer
> 0 votes
# Python 3 \- sign/abs, 73 bytes

```
f=lambda n:[[[]]*(n<0),[[]]*abs(n)]
g=lambda l:[-1,1][not l[0]]*len(l[1])

```

Try it online!

Straight forward implementation, supports negative numbers.

Integer `i` is encoded `[sign(i), abs(i)]`, where `sign(i)=[] if i > 0 else [[]]` and `abs(i)=[[]] * i`, i.e. a list of empty lists with length abs(i).

# Python 3 \- binary, 126 bytes

This is a more elaborate version (and a lot longer...), where the absolute value is encoded in a binary list representation.

```
f=lambda n:[[[]]*(n<0),[[[]]*int(i)for i in f"{n:+b}"[1:]]]
g=lambda l:[-1,1][not l[0]]*int(''.join(map(str,map(len,l[1]))),2)

```

Try it online!

# Answer
> 0 votes
# Stax, 33 total bytes

These programs are inverses of each other. They convert to and from all void lists and all non-negative integers, so that includes 0. This seems like it's maybe a famous function from some kind of algebra I don't know. In order to wrap my head around it, I first implemented the programs as functions in python.

```
def convert_to_void(n):
    lst = []
    while n > 0:
        n -= 1
        choices = len(lst) + 1
        choice = n % choices
        cutpoint = len(lst) - choice
        n //= choices
        newgroup = lst[cutpoint:]
        del lst[cutpoint:]
        lst.append(newgroup)
    return lst

def convert_from_void(lst):
    n = 0
    while lst != []:
        newgroup = lst.pop()
        n *= len(lst) + len(newgroup) + 1
        n += len(newgroup) + 1
        lst.extend(newgroup)
    return n

```

The stax programs have the same behavior.

### Non-negative integer → Void list, 15 bytes

```
ƒâ₧~└3BI─¿-rÅ;ì

```

Run and debug it

### Void list → Non-negative integer, 18 bytes

```
Çäê[!σ`c↑Ö§░NR╥ç=Æ

```

Run and debug it

---
Tags: code-golf, open-ended-function, ragged-list
---


# Question
Title: Determining the continued fractions of square roots
The **continued fraction** of a number \\$n\\$ is a fraction of the following form:

$$a\_0 + \cfrac 1 {a\_1 + \cfrac 1 {a\_2 + \cfrac 1 {a\_3 + \cfrac 1 {a\_4 + \ddots}}}}$$

which converges to \\$n\\$.

The sequence \\$a\\$ in a continued fraction is typically written as: \\$\[a\_0; a\_1, a\_2, a\_3, ... a\_n\]\\$.
We will write ours in the same fashion, but with the repeating part between semicolons.

Your goal is to return the continued fraction of the square root of \\$n\\$.

**Input:** An integer, \\$n\\$. \\$n\\$ will never be a perfect square.
**Output:** The continued fraction of \\$\sqrt n\\$.

**Test Cases:**
`2 -> [1; 2;]`
`3 -> [1; 1, 2;]`
`19 -> [4; 2, 1, 3, 1, 2, 8;]`

Shortest code wins. Good luck!

# Answer
> 4 votes
## GolfScript (66 60 chars)

```
~:^,{.*^>}?(:?';'[1?{^1$.*-@/?@+.2$/@@1$%?\- 1$(}do;;]','*1$

```

Warning: most of the `?` in there are the variable representing `floor(sqrt(input))` rather than the builtin. But the first one is the builtin.

Takes input on stdin and outputs to stdout.

Psuedocode of the algorithm (proof of correctness currently left as an exercise for the reader):

```
n := input()
m := floor(sqrt(n))
output(m)
x := 1
y := m
do
  x := (n - y * y) / x
  output((m + y) / x)
  y := m - (m + y) % x
while (x > 1)

```

Yet again I find myself wanting a single operator which takes `a b` on the stack and leaves `a/b a%b` on the stack.

# Answer
> 3 votes
## Python, 95 97 (but correct...)

This uses only integer arithmetic and floor division. This will produce correct results for all positive integer inputs, though if one wants to use a long, they'd have to add a character; for example `m=a=0L`. And of course... wait for a million years for my poor man's floor sqrt to terminate.

```
z=x=m=1
while n>m*m:m+=1
m=y=m-1
l=()
while-z<x:x=(n-y*y)/x;y+=m;l+=y/x,;y=m-y%x;z=-1
print c,l

```

**Output:**

```
n=139
11 (1, 3, 1, 3, 7, 1, 1, 2, 11, 2, 1, 1, 7, 3, 1, 3, 1, 22)

```

edit: now using Peter Taylor's algorithm. That `do...while` was fun.

# Answer
> 2 votes
# Python, 87 82 80

```
x=r=input()**.5
while x<=r:print"%d"%x+",;"[x==r],;x=1/(x%1)
print`int(r)*2`+";"

```

It takes one integer and gives output like:

```
4; 2, 1, 3, 1, 2, 8;

```

# Answer
> 2 votes
## Mathematica 33  31

```
c[n_]:=ContinuedFraction@Sqrt@n

```

Output is in list format, which is more appropriate for Mathematica. Examples:

```
c[2]
c[3]
c[19]
c[139]
c[1999]

(* out *)
{1, {2}}
{1, {1, 2}}
{4, {2, 1, 3, 1, 2, 8}}
{11, {1, 3, 1, 3, 7, 1, 1, 2, 11, 2, 1, 1, 7, 3, 1, 3, 1, 22}}
{44, {1, 2, 2, 4, 1, 1, 5, 1, 5, 8, 1, 3, 2, 1, 2, 1, 1, 1, 1, 1, 1,
  1, 14, 3, 1, 1, 29, 4, 4, 2, 5, 1, 1, 17, 2, 1, 12, 9, 1, 5, 1, 43,
  1, 5, 1, 9, 12, 1, 2, 17, 1, 1, 5, 2, 4, 4, 29, 1, 1, 3, 14, 1, 1,
  1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 8, 5, 1, 5, 1, 1, 4, 2, 2, 1, 88}}

```

# Answer
> 1 votes
## Python (~~136 133~~ 96)

The standard method for continued fractions, extremely golfed.

```
a=input()**.5
D=c=int(a);b=[]
while c!=D*2:a=1/(a%1);c=int(a);b+=[c]
print D,";%s;"%str(b)[1:-1]

```

# Answer
> 1 votes
## Perl, 99 chars

Does *not* screw up on 139, 151, etc. Tested with number ranging from 1 to 9 digits.

```
$"=",";$%=1;$==$-=($n=<>)**.5;
push@f,$==(($s=$=*$%-$s)+$-)/($%=($n-$s*$s)/$%)until$=>$-;
say"$-;@f;"

```

Note: `$%`, `$=`, and `$-` are all integer-forcing variables.

# Answer
> 1 votes
## C, 137

Including the newline, assuming I don't have to roll my own square root.

```
#include<math.h>
main(i,e){double d;scanf("%lf",&d);e=i=d=sqrt(d);while(i^e*2)printf("%d%c",i,e^i?44:59),i=d=1.0/(d-i);printf("%d;",i);}

```

It breaks for sqrt(139) and contains the occasional extra semicolon in the output, but I'm too tired to work on it further tonight :)

```
5
2;4;
19
4;2,1,3,1,2,8;
111
10;1,1,6,1,1,20;

```

# Answer
> 1 votes
# APL(NARS), 111 chars, 222 bytes

```
r←f w;A;a;P;Q;m
m←⎕ct⋄Q←1⋄⎕ct←P←0⋄r←,a←A←⌊√w⋄→Z×⍳w=0
L: →Z×⍳0=Q←Q÷⍨w-P×P←P-⍨a×Q⋄r←r,a←⌊Q÷⍨A+P⋄→L×⍳Q>1
Z: ⎕ct←m

```

The f function is based on the algo one find in the page http://mathworld.wolfram.com/PellEquation.html for solve Pell equation. That f function has its input all not negative number (type fraction too). Possible there is something goes wrong, I remember that √ has, in how I see it, problem for big fraction numbers, as

```
  √13999999999999999999999999999999999999999999999x
1.183215957E23

```

so there would be one function sqrti(). For this reason fraction input (and integer input) has to be \<10^15. test:

```
 ⎕fmt (0..8),¨⊂¨f¨0..8
┌9───────────────────────────────────────────────────────────────────────────────────────────────────────┐
│┌2─────┐ ┌2─────┐ ┌2───────┐ ┌2─────────┐ ┌2─────┐ ┌2───────┐ ┌2─────────┐ ┌2─────────────┐ ┌2─────────┐│
││  ┌1─┐│ │  ┌1─┐│ │  ┌2───┐│ │  ┌3─────┐│ │  ┌1─┐│ │  ┌2───┐│ │  ┌3─────┐│ │  ┌5─────────┐│ │  ┌3─────┐││
││0 │ 0││ │1 │ 1││ │2 │ 1 2││ │3 │ 1 1 2││ │4 │ 2││ │5 │ 2 4││ │6 │ 2 2 4││ │7 │ 2 1 1 1 4││ │8 │ 2 1 4│││
││~ └~─┘2 │~ └~─┘2 │~ └~───┘2 │~ └~─────┘2 │~ └~─┘2 │~ └~───┘2 │~ └~─────┘2 │~ └~─────────┘2 │~ └~─────┘2│
│└∊─────┘ └∊─────┘ └∊───────┘ └∊─────────┘ └∊─────┘ └∊───────┘ └∊─────────┘ └∊─────────────┘ └∊─────────┘3
└∊───────────────────────────────────────────────────────────────────────────────────────────────────────┘
  f 19
4 2 1 3 1 2 8
  f 54321x
233 14 1 1 3 2 1 2 1 1 1 1 3 4 6 6 1 1 2 7 1 13 4 11 8 11 4 13 1 7 2 1 1 6 6 4 3 1 1 1 1 2 1 2 3 1 1 14 466
  f 139
11 1 3 1 3 7 1 1 2 11 2 1 1 7 3 1 3 1 22
  +∘÷/f 139
11.78982612
  √139
11.78982612

```

if the argument is a square of a number it would return one list of 1 only element, the sqrt of that number

```
  f 4
2

```

If it would depend from me, in one exercise without "codegolf" I would prefer the previous edit that use function sqrti()...

---
Tags: code-golf, math, number, rational-numbers
---


title: Virus vs Antidotes code golf

text:
# Question
Title: Virus vs Antidotes code golf
There is a rectangular 2D array containing viruses denoted by 'v', antidote1 denoted by 'a', and antidote2 denoted by 'b' (there are no values other than 'v', 'a' and 'b').

Antidote1 can kill neighboring viruses in horizontal and vertical directions only, but antidote2 can kill neighboring(if any) viruses in horizontal, vertical and diagonal directions.

Once the antidotes are activated, how many viruses will remain at the end?

### Examples:

Input:

```
vv
vv

```

Output: 4

Input:

```
av
vv

```

Output: 1

Input:

```
vvv
vbv
vvv

```

Output: 0

Input:

```
bvb
bav
vab
vvv
vvb
vvv
vvv
bva
vav

```

Output: 3

# Answer
# Python 3, 126 bytes

```
j=''.join
g=lambda*s:eval('j(s)'+4*'.replace("%s%s","%s%s")'%(*'vbbbbvbbavacvaca',))
f=lambda x:j(map(g,*map(g,x))).count('v')

```

Try it online!

-2 bytes thanks to Kevin Cruijssen

# Explanation

Replaces all 'v' to 'b' if found next to 'b'. Next, replaces all 'v' to 'c' if found next to 'a'. A second iteration with the transposed version of the array clears all vertical and diagonal viruses. Finally, it will return the remaining number of 'v's.

---

Without eval:

# Python 3, 133 bytes

```
j=''.join
g=lambda*s,r=str.replace:r(r(r(r(j(s),'vb','bb'),'bv','bb'),'av','ac'),'va','ca')
f=lambda x:j(map(g,*map(g,x))).count('v')

```

Try it online!
> 8 votes

# Answer
# JavaScript (ES7), 108 bytes

Takes input as a matrix of characters.

```
f=m=>(g=(y,X,V)=>m.map(r=>r.map((v,x)=>V?v>f&V>'a'>(x-X)**2+y*y-2?r[x]=n--:0:v<f?g(-y,x,v):n++)|y++))(n=0)|n

```

Try it online!

*Similar to my original answer, but doing `V>'a'>(x-X)**2+y*y-2` is actually 1 byte shorter than using the hexa trick described below. ¯\\\_(ツ)\_/¯*

---

# JavaScript (ES7), 109 bytes

Takes input as a matrix of characters.

```
f=m=>(g=(y,X,V)=>m.map(r=>r.map((v,x)=>V?v>f&(x-X)**2+y*y<V-8?r[x]=n--:0:v<f?g(-y,x,'0x'+v):n++)|y++))(n=0)|n

```

Try it online!

### How?

The quadrance of two points \\$A\_1=(x\_1,y\_1)\\$ and \\$A\_2=(x\_2,y\_2)\\$ is defined as:

$$Q(A\_1,A\_2)=(x\_2−x\_1)^2+(y\_2−y\_1)^2$$

Considering integer coordinates, it looks as follows:

$$\begin{matrix} &8&5&4&5&8\\ &5&2&1&2&5\\ &4&1&\bullet&1&4\\ &5&2&1&2&5\\ &8&5&4&5&8 \end{matrix}$$

Therefore:

* a type A antidote located at \\$A\_1\\$ is able to kill a virus located at \\$A\_2\\$ if \\$Q(A\_1,A\_2)\<2\\$
* a type B antidote located at \\$A\_1\\$ is able to kill a virus located at \\$A\_2\\$ if \\$Q(A\_1,A\_2)\<3\\$

Conveniently, this exclusive upper bound (\\$2\\$ or \\$3\\$) can be obtained by converting the antidote character from hexadecimal to decimal and subtracting \\$8\\$:

* \\$\text{A}\_{16} - 8\_{10} = 2\_{10}\\$
* \\$\text{B}\_{16} - 8\_{10} = 3\_{10}\\$

### Commented

```
f =                      // named function, because we use it to test if a character
                         // is below or above 'm'
m => (                   // m[] = input matrix
  g = (                  // g is a recursive function taking:
    y,                   //   y = offset between the reference row and the current row
    X,                   //   X = reference column
    V                    //   V = reference value, prefixed with '0x'
  ) =>                   //
    m.map(r =>           // for each row r[] in m[]:
      r.map((v, x) =>    //   for each value v at position x in r[]:
        V ?              //     if V is defined:
          v > f &        //       if v is equal to 'v'
          (x - X) ** 2 + //       and the quadrance between the reference point and
          y * y          //       the current point
          < V - 8 ?      //       is less than the reference value read as hexa minus 8:
            r[x] = n--   //         decrement n and invalidate the current cell
          :              //       else:
            0            //         do nothing
        :                //     else:
          v < f ?        //       if v is either 'a' or 'b':
            g(           //         do a recursive call:
              -y,        //           pass the opposite of y
              x,         //           pass x unchanged
              '0x' + v   //           pass v prefixed with '0x'
            )            //         end of recursive call
          :              //       else:
            n++          //         increment n
      ) | y++            //   end of inner map(); increment y
    )                    // end of outer map()
  )(n = 0)               // initial call to g with y = n = 0
  | n                    // return n

```
> 5 votes

# Answer
# 05AB1E, ~~33~~ ~~30~~ 29 bytes

```
2F.•s¯}˜?•2ô€Â2ä`.:S¶¡øJ»}'v¢

```

Try it online or verify a few more test cases.

Port of *@Jitse*'s Python 3 answer, so make sure to upvote him!
-1 byte thanks to *@Jitse*.

**Explanation:**

The legacy version has the advantage of being able to zip/transpose a string-list, where the new version would need an explicit `S` and `J`, since it only works with character-lists. But, the new version is still 3 bytes shorter by using `€Â` in combination with a shorter compressed string. In the legacy version,  would only keep the last value on the stack inside the map, but in the new version, it will keep all values on the stack inside the map.

```
2F                  # Loop 2 times:
  .•s¯}˜?•          #  Push compressed string "vbvabbca"
   2ô               #  Split it into parts of size 2: ["vb","va","bb","ca"]
     €Â             #  Bifurcate (short for duplicate & reverse copy) each:
                    #   ["vb","bv","va","av","bb","bb","ca","ac"]
       2ä           #  Split it into two parts:
                    #   [["vb","bv","va","av"],["bb","bb","ca","ac"]]
         `          #  Push both those lists separated to the stack
          .:        #  Replace all strings once one by one in the (implicit) input-string
            S       #  Then split the entire modified input to a list of characters
             ¶¡     #  Split that list by newlines into sublists of characters
               ø    #  Zip/transpose; swapping rows/columns
                J   #  Join each inner character-list back together to a string again
                 »  #  And join it back together by newlines
}'v¢               '# After the loop: count how many "v" remain

```

See this 05AB1E tip of mine (section *How to compress strings not part of the dictionary?*) to understand why `.•s¯}˜?•` is `"vbvabbca"`.
> 3 votes

# Answer
# Java 10, ~~211~~ ~~209~~ ~~204~~ 202 bytes

```
m->{int i=m.length,j,c=0,f,t,I,J;for(;i-->0;)for(j=m[i].length;j-->0;c+=m[i][j]>98?f/9:0)for(f=t=9;t-->0;)try{f-=m[I=i+t/3-1][J=j+t%3-1]==98||m[I][J]<98&(I-=i-J+j)*I==1?1:0;}finally{continue;}return c;}

```

Modification of my answer for the *All the single eights* challenge.
-9 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
m->{                           // Method with char-matrix parameter & int return-type
  int i=m.length,              //  Amount of rows
      j,                       //  Amount of columns
      c=0,                     //  Virus-counter, starting at 0
      f,                       //  Flag-integer
      t,I,J;                   //  Temp-integers
  for(;i-->0;)                 //  Loop over the rows of the matrix
    for(j=m[i].length;j-->0    //   Inner loop over the columns
        ;c+=                   //     After every iteration: increase the counter by:
            m[i][j]>98         //      If the current cell contains a 'v'
             f/9               //      And the flag is 9:
                               //       Increase the counter by 1
            :0)                //      Else: leave the counter unchanged by adding 0
      for(f=t=9;               //    Reset the flag to 9
          t-->0;)              //    Loop `t` in the range (9, 0]:
         try{f-=               //     Decrease the flag by:
           m[I=i+t/3-1]        //      If `t` is 0, 1, or 2: Look at the previous row
                               //      Else-if `t` is 6, 7, or 8: Look at the next row
                               //      Else (`t` is 3, 4, or 5): Look at the current row
            [J=j+t%3-1]        //      If `t` is 0, 3, or 6: Look at the previous column
                               //      Else-if `t` is 2, 5, or 8: Look at the next column
                               //      Else (`t` is 1, 4, or 7): Look at the current column
            ==98               //      And if this cell contains a 'b'
            ||m[I][J]<98       //      Or if there is an 'a'
              &(I-=i-J+j)*I==1?//      in a vertical/horizontal adjacent cell:
               1               //       Decrease the flag by 1
            :0;                //      Else: leave the flag unchanged by decreasing with 0
         }finally{continue;}   //     Catch and ignore any ArrayIndexOutOfBoundsExceptions,
                               //     which is shorter than manual checks
  return c;}                   //  And finally return the virus-counter as result

```
> 2 votes

# Answer
# Perl (`-00lp`), 82 bytes

Using regex to replace `v` by space, then count the `v`s

```
/.
/;$,="(|..{@-})";$;="(|.{@-,@+})";$_=s/(a$,|b$;)\Kv|v(?=$,a|$;b)/ /s?redo:y/v//

```

TIO
> 1 votes

# Answer
# Charcoal, 39 bytes

```
ＷＳ⊞υι≔⪫υ⸿θＰθ≔⁰ηＦθ«≧⁺›⁼ιv⁺№ＫＭb№ＫＶaηι»⎚Ｉη

```

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

```
ＷＳ⊞υι≔⪫υ⸿θＰθ

```

Join the input strings with `\r` characters and draw the result to the canvas.

```
≔⁰η

```

Clear the number of live virii.

```
Ｆθ«

```

Loop over the characters in the input.

```
≧⁺›⁼ιv⁺№ＫＭb№ＫＶaη

```

If the current character is a virus and there are no adjacent `b`s in any direction or `a`s orthogonally then increment the number of live virii.

```
ι»

```

Repeat with the next character.

```
⎚Ｉη

```

Clear the canvas and print the total number of live virii.
> 1 votes

---
Tags: code-golf
---