title: Golf the repeated totient function

text:
# Question
Title: Golf the repeated totient function
You will take two positive integers `n` and `x` as input, and output Euler's totient function (number of positive integers less than `x` co-prime to `x`) applied `n` times.

# Testcases

```
n x   result
1 10  4
2 10  2
3 10  1
1 100 40
2 100 16
3 100 8
4 100 4
5 100 2
6 100 1

```

# Answer
# 05AB1E, 2 bytes

Code:

Explanation:

```
F   # Do the following n times:
 Õ  #   ..Calculate the totient

```

Uses the **CP-1252** encoding. Try it online!.
> 8 votes

# Answer
# Python 2, ~~84~~ ~~78~~ 70 bytes

```
n,x=input();exec('k=m=1;'+'x-=(x%k<m%k)*x/k;m*=k*k;k+=1;'*x)*n;print x

```

*Thanks to @xnor for golfing off 8 bytes!*

Test it on Ideone.

### Background

By Euler's product formula,

where **φ** denotes Euler's totient function and **p** varies only over prime numbers.

To identify primes, we use a corollary of Wilson's theorem:

### How it works

After reading the input, we construct and execute a certain string. The executed code is roughly equivalent to the following.

```
r = range(x)
for _ in range(n):
    k = 1
    m = 1
    for _ in r:
        x -= (x % k < m % k) * x / k
        m *= k**2
        k += 1

```

The inner loop will set **x = φ(x)**, so executing it **n** times stores the desired output in **x**.

At all times, the variable **m** will be equal to the square of the factorial of **k - 1**. In fact, we set **k = 1** and **m = 0!2 = 1** at the beginning of the inner loop.

**k** varies from its initial value **1** to the initial value of **x** and is incremented each time the sinner loop is executed. **m** is updated accordingly by multiplying it by the "old" value of **k2**.

For the actual calculation of **x**, recall that `m%k` will yield **1** if **m** is prime and **0** if not. This means that `x%k<m%k` will yield **True** if and only if both **k** is a prime number and **x** is divisible by **k**.

In this case, `(x%k<m%k)*x/k` yields **x / k**, and subtracting it from **x** replaces its previous value with **x(1 - 1/k)**, as in Euler's product formula. Otherwise, `(x%k<m%k)*x/k` yields **0** and **x** remains unchanged.
> 5 votes

# Answer
## Actually, 4 bytes

```
`▒`n

```

Try it online!

This program takes `x` as the first input, and `n` as the second input.

Explanation:

```
`▒`n
`▒`n  call the following function n times:
 ▒      totient(x)

```
> 4 votes

# Answer
# MATL, 5 bytes

```
:"_Zp

```

**Try it online!**

```
:        % Take n implicitly. Generate vector [1 2 ... n]
"        % For each loop, that is, repeat n times
  _Zp    %   Euler's totient function. Takes x implicitly first time
         % End for. Display implicitly

```

---

Without using Euler's totient function: **9 bytes**

```
:"t:Zd1=s

```

**Try it online!**

```
:        % Take n implicitly. Generate range [1 2 ... n]
"        % For each loop, that is, repeat n times
  t      %   Duplicate. Takes x implicitly first time. Call that t
  :      %   Range [1 2 ... t]
  Zd     %   GCD of t and [1 2 ... t], elementwise
  1=s    %   How many times the result equals 1: Euler's totient
         % End for. Display implicitly

```
> 3 votes

# Answer
## Mathematica, 17 bytes

```
EulerPhi~Nest~##&

```

An unnamed function which takes `x` as the first argument and `n` as the second. Here `EulerPhi~Nest~##` is short for `Nest[EulerPhi, ##]` and then `##` expands to a sequence of both arguments so we get `Nest[EulerPhi, x, n]`. And `EulerPhi` is of course the totient function.
> 3 votes

# Answer
## Jelly, 3 bytes

```
ÆṪ¡

```

Expects `x` as the first argument and `n` as the second.

Try it online!

This is as straightforward as it gets: `ÆṪ` is the built-in totient function and `¡` applies this function as many times as the second argument.
> 3 votes

# Answer
# J, ~~6~~ 4 bytes

```
5&p:

```

Straight-forward approach. Nests the totient function *n* times on an initial value of *x*.

## Usage

```
   f =: 5&p:
   5 f 100
2

```

## Explanation

Normally, `5&p:` is a monad that computes the totient of its argument. However, when used dyadically, it nests itself on an initial value of its LHS according to the number of times on its RHS.
> 2 votes

# Answer
# Haskell, ~~49~~ ~~46~~ ~~44~~ 40 bytes

Thanks @xnor for another again named solution:

```
x%0=x
x%n=sum[1|1<-gcd x<$>[1..x]]%(n-1)

```

Old version:

The following is an unnamed pointless function that takes two arguments: (Thanks @Lynn for another two bytes!)

```
(!!).iterate(\y->sum[1|t<-[1..y],gcd y t<2])

```

To use it, you can e.g. assign it a name (`f=(!!).(...`) and then call it via `f 10 1` (as an example for the first test case).

Explanation: The lambda function `(\y->sum[1|t<-[1..y],gcd y t<2])` is the totient function. `iterate f x` produces an infinite list `[x,f(x),f(f(x)),f(f(f(x))),...]` and `!!` is just for accessing this list at a specific index.

Older version:

```
x#n=(iterate(\y->sum[1|t<-[1..y],gcd y t<2])x)!!n

```

Usage e.g. for the first test case: `10#1`.
> 1 votes

# Answer
# PARI/GP, 33 bytes

Straightforward iteration:

```
f(n,x)=for(i=1,x,n=eulerphi(n));n

```

Straightforward recursion:

```
f(n,x)=if(x,n,f(eulerphi(n),x-1))

```
> 1 votes

# Answer
# CJam, 20 bytes

```
q~{_mf1|1-{1$\/-}/}*

```

Try it online!

### How it works

```
q~                    Read and evaluate all input. Pushes x and n.
  {               }*  Repeat n times:
   _mf                  Compute the prime factorization of a copy of x.
      1|1-              Add and remove 1 from the prime factorization.
                        | deduplicates and - handles the edge case 1mf -> [1].
          {     }/      For each remaining prime p:
           1$             Push a copy of x.
             \/           Swap with p and divide, pushing x/p.
               -          Subtract from x, pushing x-x/p.

```
> 1 votes

# Answer
## Hoon, 84 bytes

```
|*((pair) ?~(p q $(p (dec p), q (lent (skim (gulf 1 q) |=(@ =(1 d:(egcd +< q))))))))

```

Ungolfed:

```
|*  (pair)
  ?~  p
    q
  %=  $
    p  (dec p)
    q  (lent (skim (gulf 1 q) |=(@ =(1 d:(egcd +< q)))))
  ==

```
> 0 votes

# Answer
# Julia, 36 bytes

```
n\x=n>0?~-n\sum(k->gcd(k,x)<2,1:x):x

```

Try it online!
> 0 votes

# Answer
# Perl 6,  ~~47 45 44 43 42 41~~  39 bytes

```
~~{($^x,{+(^$^x .grep: {$_ gcd$x==1})}...*)[$^n]}
{($^x,{+(^$^x Xgcd $x).grep: *==1}...*)[$^n]}
{($^x,{+grep *==1,(^$^x Xgcd $x)}...*)[$^n]}
{($^x,{+grep *==1,(^$^x Xgcd$x)}...*)[$^n]}
{($^x,{+grep 2>*,(^$^x Xgcd$x)}...*)[$^n]}
{($^x,{+grep 2>*,(^$_ Xgcd$_)}...*)[$^n]}~~
{($^x,{sum 2 X>(^$_ Xgcd$_)}...*)[$^n]}
```

### Explanation:

```
{ # parameters are $n,$x ( declared as placeholder parameters )
  (

    $^x, # seed sequence generator with second argument

    { # parameter is $_
      sum
        2
        X[>] # crossed compared using &infix«>»
        (
          0 ..^ $_ # from 0 up to and excluding the parameter
          X[gcd]   # cross apply &infix:<gcd> with:
          $_       # the parameter
        )
    }

    ...  # keep applying that block

    *    # forever

  )[ $^n ] # grab the one at the index indicated by the first argument
}

```

### Test:

```
use v6.c;
use Test;

my @tests = (
  (1, 10) =>  4,
  (2, 10) =>  2,
  (3, 10) =>  1,
  (1,100) => 40,
  (2,100) => 16,
  (3,100) =>  8,
  (4,100) =>  4,
  (5,100) =>  2,
  (6,100) =>  1,
);

plan +@tests;

my &repeated-totient = {($^x,{sum 2 X>(^$_ Xgcd$_)}...*)[$^n]}

for @tests -> $_ ( :key(@input), :value($expected) ) {
  is repeated-totient(|@input), $expected, .gist
}

```

```
1..9
ok 1 - (1 10) => 4
ok 2 - (2 10) => 2
ok 3 - (3 10) => 1
ok 4 - (1 100) => 40
ok 5 - (2 100) => 16
ok 6 - (3 100) => 8
ok 7 - (4 100) => 4
ok 8 - (5 100) => 2
ok 9 - (6 100) => 1

```
> 0 votes

# Answer
## Javascript, 88 ~~95~~

```
g=(a,b)=>b?g(b,a%b):a==1
t=(x,n=x,o=0)=>n?t(x,--n,o+g(x,n)):o
f=(n,x)=>n?f(n-1,t(x)):x

```

The first function returns true/false if the greatest commom divisor is 1. The second function calculates the *totient*. The third function is a simple recursion to do the totient n times.

I took this idea from the wikipedia link:

> It can be defined more formally as the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) = 1;
> 0 votes

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


title: Settlers of Catan - Longest Road!

text:
# Question
Title: Settlers of Catan - Longest Road!
This is an endgame board of Settlers of Catan:

# Background:

The roads (the long stick pieces) and the settlements (and cities) are rendered by the little huts. We encode the placement of these pieces by using the following scheme: From the top, we have a row horizontal vertices and edges where a road can be placed. Then we have a column of only roads, and so forth. Using R for Red, O for Orange, and B for Blue, and _ for nothing, the pictured board would be encoded as:

```
________RR_R_
__R_
__RR_R_RRR_____R_
B___R
_B_________B__OO_OOR_
B__B_R
BB_BBB_____B____RR_R_
OBB_O
OO__BB_BB__OOO_OO
O_O_
_O_OOO_O_____

```

A board like this will be your input string. Any letter `[A-Z]` may indicate a player color, but there will at most four colors (including empty). Boards are otherwise *guaranteed* to be valid according to the rules of Settlers, which means:

* Each color will have at most two contiguous road networks, which may or may not be broken apart by other players settlements / cities (vertex buildings). See the orange settlement breaking apart the red road on the right side of the sample image.
    + Each road network is guaranteed to have at least one settlement.
* All settlements and cities are guaranteed to be at least **two** edges from the nearest other settlement / city (yours or otherwise)
* One player may only have 15 roads on the game board.
* For Catan enthusiasts: there is no distinction between settlements and cities for the purpose of this problem, so I don't distinguish in the input string.

All this is for the specification of the "input" string.

### Longest Road:

In Settlers, players get two victory points for having the "longest road". This is defined to be: **The longest contiguous single path (measured in roads) from start point to end point, that is not broken up by an opponents settlement or city**. Cycles are okay, as long as you can trace the path from one particular start point to one particular end point. So, a loop of 6 roads plus one road branching off is length 7, but one with two branching off the 6 road loop on opposite sides is still only worth 7.

In the example map, the Red road on the right side is only worth 4, because he is cut off by an Orange settlement on the right side of the board (that's why settlements are included at all). Blue has a road of length 13, and Orange has a road of length 12. Red's top road is only worth 7, because it doesn't connect to the two single roads next to it.

## Output:

All players that have a road of the longest length (it could be more than one if there are ties), followed by a whitespace and/or underscore delimited count in base 10 of how long that road is.

So the output for the example board would be:

```
B 13

```

## The Problem statement:

You may write a program or function, receives the input board via STDIN or as a string argument to your function, which returns the output described above as a string or prints it to STDOUT (or closest alternative). You may optionally include a single trailing newline in the output.

This is , shortest program wins. Standard loopholes are banned, of course.

# Answer
> 4 votes
# Python 2, ~~445~~ 400 bytes

I'm a fan of Settlers, so this challenge was fun.

```
T="^"
Z=26
A=T*52
for i in range(11):A+=(T*(i%2)*3).join(x for x in raw_input()).center(Z,T)
A+=T*52
def f(c,p=0,l=0,B=A):
 b=l;C=B[0:p]+T+B[p+1:];n=(Z,1)[p%2]
 for i in(p<1)*range(390):
    if(i/Z%2<1&i%2>0)|(i/Z%2>0&i%2<1):b=max(b,f(c,i))
 for i in(p-n,p+n)*(B[p]==c):
    for j in(i-Z,i-1,i+1,i+Z)*(B[i]in c+"_"):b=max(b,f(c,j,l+1,C))
 return b
i=l=0
for x in A:
 if x<T:i=f(x)
 if i>l:c=x;l=i
print c,l

```

Score reflects replacing each occurrence of 4 spaces with a tab.

**Explanation**

The lines before the function definition read the input, and build a normalized board into a single string variable. The process inserts "^" characters into the short lines representing the vertical road segments. It also pads the board with "^" characters.

```
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^________RR_R_^^^^^^^
^^^^^^_^^^_^^^R^^^_^^^^^^^
^^^^__RR_R_RRR_____R_^^^^^
^^^^B^^^_^^^_^^^_^^^R^^^^^
^^_B_________B__OO_OOR_^^^
^^B^^^_^^^_^^^B^^^_^^^R^^^
^^BB_BBB_____B____RR_R_^^^
^^^^O^^^B^^^B^^^_^^^O^^^^^
^^^^OO__BB_BB__OOO_OO^^^^^
^^^^^^O^^^_^^^O^^^_^^^^^^^
^^^^^^_O_OOO_O_____^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^

```

When called with the default parameters, the function returns the length of a road of a given color. The first loop is active only when the position (p) parameter was supplied. It recursively finds the length of the road at each valid road position, and keeps track of the longest one. When there is a road at the position parameter, the function recursively adds the length of adjacent roads of the same color. The road is replaced with a "~" in the working copy of the board to ensure it doesn't recount segments that have already been counted.

The code following the function definition calls the function for each color in the board, and prints the highest scoring color and length.

Demo it here

---
Tags: code-golf, path-finding, board-game, hexagonal-grid
---


title: Image Hide-and-Seek

text:
# Question
Title: Image Hide-and-Seek
In this challenge, you need to find a specific pixel within an photograph (taken with a real camera).

You are passed an (R, G, B) tuple and an image, and **you need to return a point (x,y) within the image that matches the RGB color given**. The image may have multiple points that match the color; you only need to find 1.

The *challenge* is that you need to do it **while reading as few pixels as possible**. Your score will be total number of pixels read across all test cases.

If you wish, you can read the entire image into an array of RGB values, as long as you don't do any processing on the pixels. I allow this purely for efficiency purposes. For example, in Python, `list(Image.open("image_name+".jpg").convert("RGB").getdata())` is ok.

Hardcoding locations is not allowed. Your algorithm should work well for more than just the test cases listed below. You are not allowed to save data between test cases. I've chosen RGB values that appear infrequently (`<10`) in the image (in case that makes a difference for your algorithm). If you are using randomness in your algorithm, please set a seed, so that your score is constant.

Images can be found on Github

**Test cases:**

```
image_name:
(r, g, b) [all possible answers]

barn:
(143,91,33) [(887,1096),(2226,1397),(2007,1402),(2161,1508),(1187,1702)]
(53,35,59) [(1999,1260)]
(20,24,27) [(1328,1087),(154,1271)]
(167,148,176) [(1748,1204)]
(137,50,7) [(596,1498)]
(116,95,94) [(1340,1123)]
(72,49,59) [(1344,857),(1345,858),(1380,926),(1405,974),(1480,1117)]
(211,163,175) [(1963,745)]
(30,20,0) [(1609,1462),(1133,1477),(1908,1632)]
(88,36,23) [(543,1494),(431,1575)]
daisy:
(21,57,91) [(1440,1935),(2832,2090),(2232,2130),(1877,2131),(1890,2132)]
(201,175,140) [(1537,1749),(2319,1757)]
(169,160,0) [(2124,759)]
(113,123,114) [(1012,994),(2134,1060),(1803,1183),(1119,1335)]
(225,226,231) [(3207,829),(3256,889),(3257,889),(1434,981),(2599,1118),(2656,1348),(2656,1351)]
(17,62,117) [(2514,3874),(2336,3885)]
(226,225,204) [(3209,812)]
(119,124,146) [(2151,974),(2194,1021),(2194,1022),(2202,1034),(2812,1500)]
(2,63,120) [(2165,3881),(2326,3882),(2330,3882),(2228,3887)]
(200,167,113) [(1453,1759)]
dandelion:
(55,2,46) [(667,825),(668,825)]
(95,37,33) [(1637,1721),(1625,1724),(1405,1753),(2026,2276),(2016,2298)]
(27,41,50) [(1267,126),(424,519),(2703,1323),(1804,3466)]
(58,92,129) [(2213,3274)]
(136,159,105) [(1300,2363),(2123,2645),(1429,3428),(1430,3432),(1417,3467),(1393,3490),(1958,3493)]
(152,174,63) [(2256,2556)]
(78,49,19) [(2128,2836)]
(217,178,205) [(2736,3531)]
(69,95,130) [(870,305),(493,460),(2777,1085),(2791,1292),(2634,3100)]
(150,171,174) [(2816,1201),(2724,2669),(1180,2706),(1470,3215),(1471,3215)]
gerbera:
(218,186,171) [(4282,1342)]
(180,153,40) [(4596,1634),(4369,1682),(4390,1708),(4367,1750)]
(201,179,119) [(4282,1876),(4479,1928)]
(116,112,149) [(5884,252),(4168,371),(4169,372),(4164,384),(5742,576)]
(222,176,65) [(4232,1548)]
(108,129,156) [(5341,3574),(5339,3595),(5302,3734)]
(125,99,48) [(4548,1825),(4136,1932),(5054,2013),(5058,2023),(5058,2035),(5055,2050),(5031,2073)]
(170,149,32) [(4461,1630),(4520,1640)]
(156,185,203) [(3809,108)]
(103,67,17) [(4844,1790)]
hot-air:
(48,21,36) [(1992,1029),(2005,1030),(2015,1034),(2018,1036)]
(104,65,36) [(3173,1890),(3163,1893)]
(169,89,62) [(4181,931),(4210,938),(4330,1046),(4171,1056),(3117,1814)]
(68,59,60) [(1872,220),(1874,220),(1878,220),(1696,225),(3785,429)]
(198,96,74) [(4352,1057)]
(136,43,53) [(1700,931)]
(82,42,32) [(4556,961),(4559,973),(4563,989),(4563,990),(4441,1004),(4387,1126),(4378,1128)]
(192,132,72) [(1399,900),(3105,1822),(3104,1824),(3105,1824),(3107,1826),(3107,1827),(3104,1839),(3119,1852)]
(146,21,63) [(1716,993)]
(125,64,36) [(4332,937)]
in-input:
(204,90,1) [(1526,1997),(1385,2145),(4780,2807),(4788,3414)]
(227,163,53) [(1467,1739),(2414,1925),(2441,2198),(134,2446)]
(196,179,135) [(3770,2740),(1110,3012),(3909,3216),(1409,3263),(571,3405)]
(208,59,27) [(1134,1980),(4518,2108),(4515,2142)]
(149,70,1) [(4499,1790),(2416,2042),(1338,2150),(3731,2408),(3722,2409),(4400,3618)]
(168,3,7) [(987,402),(951,432),(1790,1213),(1790,1214),(1848,1217),(4218,1840),(4344,1870),(1511,1898)]
(218,118,4) [(3857,1701),(1442,1980),(1411,2156),(25,2606)]
(127,153,4) [(3710,2813)]
(224,230,246) [(2086,160),(2761,222),(4482,1442)]
(213,127,66) [(4601,1860),(4515,2527),(4757,2863)]
klatschmohn:
(170,133,19) [(1202,2274),(1202,2275),(957,2493),(1034,2633),(3740,3389),(3740,3391),(3683,3439)]
(162,92,4) [(489,2854)]
(159,175,104) [(3095,2475),(3098,2481)]
(199,139,43) [(1956,3055)]
(171,169,170) [(3669,1487),(3674,1490),(3701,1507)]
(184,115,58) [(1958,2404)]
(228,169,5) [(1316,2336),(1317,2336)]
(179,165,43) [(3879,2380),(1842,2497),(1842,2498)]
(67,21,6) [(1959,2197),(2157,2317),(2158,2317),(2158,2318),(2116,2373)]
(213,100,106) [(1303,1816)]
tajinaste-rojo:
(243,56,99) [(1811,2876),(1668,4141),(2089,4518),(1981,4732),(1659,4778),(2221,5373),(1779,5598),(2210,5673),(2373,5860)]
(147,157,210) [(1835,1028),(1431,3358)]
(114,37,19) [(1792,3572),(1818,3592)]
(108,117,116) [(2772,4722),(1269,5672),(2512,5811),(2509,5830),(2186,5842),(2186,5846),(2190,5851),(2211,5884)]
(214,197,93) [(1653,4386)]
(163,102,101) [(2226,2832),(2213,3683),(1894,4091),(1875,4117)]
(192,192,164) [(2175,2962),(2206,3667),(2315,3858),(1561,3977),(3039,5037),(3201,5641)]
(92,118,45) [(1881,1704),(1983,1877),(2254,2126),(3753,5862),(3766,5883)]
(145,180,173) [(1826,1585)]
(181,124,105) [(1969,3892)]
turret-arch:
(116,70,36) [(384,648),(516,669)]
(121,115,119) [(2419,958)]
(183,222,237) [(172,601),(183,601),(110,611),(111,617)]
(237,136,82) [(2020,282),(676,383),(748,406),(854,482),(638,497),(647,661),(1069,838),(1809,895),(1823,911)]
(193,199,215) [(1567,919),(1793,1047)]
(33,30,25) [(1307,861),(309,885),(1995,895),(504,1232),(2417,1494)]
(17,23,39) [(1745,1033),(788,1090),(967,1250)]
(192,139,95) [(1445,1337)]
(176,125,98) [(1197,1030)]
(178,83,0) [(2378,1136)]
water-lilies:
(86,140,80) [(2322,2855),(4542,3005),(4540,3006),(4577,3019)]
(218,124,174) [(1910,2457)]
(191,77,50) [(2076,1588)]
(197,211,186) [(4402,1894)]
(236,199,181) [(2154,1836)]
(253,242,162) [(1653,1430)]
(114,111,92) [(1936,2499)]
(111,93,27) [(2301,2423),(2127,2592),(2137,2717),(2147,2717)]
(139,92,102) [(1284,2243),(1297,2258)]
(199,157,117) [(3096,993)]

```

# Answer
## Python, score: 14,035,624

First thing's first, here's the code:

```
from heapq import heappush, heappop
from PIL import Image
import random

random.seed(1)

def dist(x, y):
    return sum([(x[i] - y[i]) ** 2 for i in range(3)])

def gradient_descent(image_name, c):
    im = Image.open(image_name + '.jpg').convert('RGB')
    L = im.load()
    sx, sy = im.size
    heap = []
    visited = set()
    count = 0
    points = []
    for i in range(0, sx, sx / 98):
        for j in range(0, sy, sy / 98):
            points.append((i, j))
    for x in points:
        heappush(heap, [dist(c, L[x[0], x[1]]), [x[0], x[1]]])
        visited.add((x[0], x[1]))

    while heap:
        if count % 10 == 0:
            x = random.random()
            if x < 0.5:
                n = heap.pop(random.randint(10, 100))
            else:
                n = heappop(heap)
        else:
            n = heappop(heap)
        x, y = n[1]
        c_color = L[x, y]
        count += 1

        if c_color == c:
            p = float(len(visited)) / (sx * sy) * 100
            print('count: {}, percent: {}, position: {}'.format(len(visited), p, (x, y)))
            return len(visited)

        newpoints = []
        newpoints.append((x + 1, y))
        newpoints.append((x - 1, y))
        newpoints.append((x, y + 1))
        newpoints.append((x, y - 1))
        newpoints.append((x + 1, y + 1))
        newpoints.append((x + 1, y - 1))
        newpoints.append((x - 1, y + 1))
        newpoints.append((x - 1, y - 1))

        for p in newpoints:
            if p not in visited:
                try:
                    d = dist(c, L[p[0], p[1]])
                    heappush(heap, [d, [p[0], p[1]]])
                    visited.add(p)
                except IndexError:
                    pass

```

and here's a gif showing how the algorithm examines pixels:

So, here's what this code is doing: The variable `heap` is a priority queue of `(x, y)` coordinates in the image, sorted by the Euclidean distance of the color at that coordinate to the target color. It gets initialized with 10,200 points which are evenly distributed across the entire image.

With the heap initialized, we then pop off the point with the minimum distance to the target color. If the color at that point has a distance \> 0, that is to say, if the color at that point is NOT the target color, we add the 8 surrounding points from it to `heap`. To ensure that a given point isn't considered more than once, we maintain the variable `visited`, which is a set of all the points that have been examined so far.

Occasionally, instead of directly taking the point with the minimum color distance, we'll randomly choose some other point from *near* the top of the queue. This isn't strictly necessary, but in my testing, it shaves off approximately 1,000,000 pixels from the total score. Once the target color is found, we simply return the length of the `visited` set.

Like @Karl Napf, I ignored the test cases where the specified color was not present in the image. You can find a driver program to run through all the test cases at the GitHub repository I created for this answer.

Here are the results from each specific test case:

```
barn
color: (143, 91, 33), count: 20388 / 0.452483465755%, position: (612, 1131)
color: (53, 35, 59), count: 99606 / 2.21061742643%, position: (1999, 1260)
color: (72, 49, 59), count: 705215 / 15.6512716943%, position: (1405, 974)

daisy
color: (21, 57, 91), count: 37393 / 0.154770711039%, position: (1877, 2131)
color: (169, 160, 0), count: 10659 / 0.0441179100089%, position: (2124, 759)
color: (113, 123, 114), count: 674859 / 2.79326096545%, position: (1119, 1335)
color: (225, 226, 231), count: 15905 / 0.0658312560927%, position: (3256, 889)
color: (17, 62, 117), count: 15043 / 0.0622634131029%, position: (2514, 3874)
color: (226, 225, 204), count: 138610 / 0.573710808362%, position: (1978, 1179)
color: (119, 124, 146), count: 390486 / 1.61623287435%, position: (2357, 917)
color: (2, 63, 120), count: 10063 / 0.0416510487306%, position: (2324, 3882)
color: (200, 167, 113), count: 16393 / 0.06785110224%, position: (1453, 1759)

dandelion
color: (95, 37, 33), count: 10081 / 0.0686342592593%, position: (1625, 1724)
color: (27, 41, 50), count: 2014910 / 13.7180691721%, position: (1267, 126)
color: (58, 92, 129), count: 48181 / 0.328029684096%, position: (1905, 756)
color: (136, 159, 105), count: 10521 / 0.0716299019608%, position: (1416, 3467)
color: (152, 174, 63), count: 10027 / 0.0682666122004%, position: (2256, 2558)
color: (69, 95, 130), count: 201919 / 1.37472086057%, position: (2708, 2943)
color: (150, 171, 174), count: 29714 / 0.202301198257%, position: (1180, 2706)

gerbera
color: (180, 153, 40), count: 21904 / 0.0906612910062%, position: (4459, 1644)
color: (116, 112, 149), count: 14896 / 0.0616549758413%, position: (5884, 252)
color: (222, 176, 65), count: 76205 / 0.315414704215%, position: (4313, 2097)
color: (108, 129, 156), count: 12273 / 0.0507983027994%, position: (5302, 3734)
color: (125, 99, 48), count: 26968 / 0.111621333814%, position: (5054, 2013)
color: (170, 149, 32), count: 89591 / 0.370819746281%, position: (4478, 1647)
color: (156, 185, 203), count: 177373 / 0.734151989118%, position: (4096, 368)
color: (103, 67, 17), count: 11035 / 0.0456741849093%, position: (4844, 1790)

hot-air
color: (48, 21, 36), count: 49711 / 0.24902994992%, position: (1990, 1095)
color: (104, 65, 36), count: 9927 / 0.0497298447599%, position: (3191, 1846)
color: (68, 59, 60), count: 195418 / 0.978957066918%, position: (3948, 470)
color: (82, 42, 32), count: 12216 / 0.0611967143737%, position: (4559, 984)
color: (192, 132, 72), count: 116511 / 0.583668171938%, position: (3103, 1844)

in-input
color: (204, 90, 1), count: 44058 / 0.248299807393%, position: (4695, 2559)
color: (227, 163, 53), count: 12654 / 0.0713147615132%, position: (221, 2384)
color: (196, 179, 135), count: 181534 / 1.02307996812%, position: (1030, 3486)
color: (208, 59, 27), count: 9956 / 0.0561095120614%, position: (4518, 2108)
color: (149, 70, 1), count: 13698 / 0.0771984829467%, position: (3731, 2408)
color: (168, 3, 7), count: 19381 / 0.10922644167%, position: (942, 398)
color: (218, 118, 4), count: 36648 / 0.206538911011%, position: (25, 2606)
color: (224, 230, 246), count: 1076427 / 6.06647185011%, position: (4482, 1442)
color: (213, 127, 66), count: 62673 / 0.353209265712%, position: (4701, 2579)

klatschmohn
color: (170, 133, 19), count: 11535 / 0.0724321530189%, position: (1034, 2633)
color: (162, 92, 4), count: 103795 / 0.651763790429%, position: (489, 2854)
color: (159, 175, 104), count: 10239 / 0.0642941321856%, position: (3098, 2481)
color: (171, 169, 170), count: 10119 / 0.063540611738%, position: (3674, 1490)
color: (184, 115, 58), count: 22425 / 0.140814133632%, position: (1958, 2404)
color: (228, 169, 5), count: 10449 / 0.0656127929688%, position: (1316, 2336)
color: (179, 165, 43), count: 10285 / 0.0645829816905%, position: (1842, 2498)
color: (67, 21, 6), count: 10206 / 0.0640869140625%, position: (2116, 2373)
color: (213, 100, 106), count: 11712 / 0.073543595679%, position: (1303, 1816)

tajinaste-rojo
color: (243, 56, 99), count: 126561 / 0.5273375%, position: (2241, 5424)
color: (114, 37, 19), count: 11285 / 0.0470208333333%, position: (1818, 3583)
color: (108, 117, 116), count: 33855 / 0.1410625%, position: (1269, 5672)
color: (163, 102, 101), count: 1058090 / 4.40870833333%, position: (1546, 4867)
color: (192, 192, 164), count: 10118 / 0.0421583333333%, position: (1919, 3171)
color: (92, 118, 45), count: 13431 / 0.0559625%, position: (3766, 5883)
color: (145, 180, 173), count: 1207713 / 5.0321375%, position: (1863, 955)

turret-arch
color: (116, 70, 36), count: 145610 / 3.23161258822%, position: (96, 671)
color: (183, 222, 237), count: 11704 / 0.259754094722%, position: (140, 604)
color: (237, 136, 82), count: 60477 / 1.34220338231%, position: (1063, 993)
color: (193, 199, 215), count: 359671 / 7.98240046163%, position: (2259, 953)
color: (33, 30, 25), count: 148195 / 3.28898308846%, position: (1307, 861)
color: (17, 23, 39), count: 10601 / 0.235274535044%, position: (2080, 1097)
color: (192, 139, 95), count: 219732 / 4.87664787607%, position: (1127, 970)
color: (176, 125, 98), count: 2471787 / 54.8578942696%, position: (147, 734)

water-lilies
color: (86, 140, 80), count: 10371 / 0.0717376936238%, position: (4542, 3005)
color: (218, 124, 174), count: 25655 / 0.177459312498%, position: (1910, 2457)
color: (197, 211, 186), count: 1144341 / 7.91557073177%, position: (4402, 1894)
color: (253, 242, 162), count: 14174 / 0.0980435897622%, position: (1672, 1379)
color: (111, 93, 27), count: 10405 / 0.0719728764975%, position: (2147, 2717)
color: (199, 157, 117), count: 10053 / 0.0695380420403%, position: (3096, 993)

Total: 14035624

```
> 5 votes

# Answer
## Python, score: 396,250,646

* While there are no PNGs to parse and there are still problems with the testcases, I decided to program anyway.
* Those testcases where the value is not present in the image were ignored (checked against a traditional linear search, which had a score of **544,017,431**)

```
from PIL import Image

def dist(x,y):
 d = 0
 for i in range(3):
  d += (x[i]-y[i])**2
 return d

def mid(x,y):
 return (x+y)/2

class Finder:
 def __init__(self, image_name, c):
  self.image_name = image_name,
  self.c = c
  self.found = False
  self.position = None
  self.im = Image.open(image_name+".jpg").convert("RGB")
  self.L = self.im.load()
  self.visited = set()

 def quadsearch(self,x0,x1,y0,y1):
  if x0==x1 and y0==y1: return
  xm=mid(x0,x1)
  ym=mid(y0,y1)
  R = [
   (x0,xm,y0,ym),
   (xm,x1,y0,ym),
   (x0,xm,ym,y1),
   (xm,x1,ym,y1),
   ]
  P = [(mid(t[0],t[1]), mid(t[2],t[3])) for t in R]
  DR = []
  for i in range(len(P)):
   p = P[i]
   if p in self.visited: continue
   self.visited.add(p)
   u = self.L[p[0], p[1]]
   d = dist(u, self.c)
   if d == 0:
    self.found = True
    self.position = (p[0], p[1])
    return
   DR.append((d,R[i]))
  S = sorted(range(len(DR)), key=lambda k: DR[k][0])
  for i in S:
   if self.found == True: return
   r = DR[i][1]
   self.quadsearch(r[0], r[1], r[2], r[3])

 def start(self):
  sx,sy = self.im.size
  self.quadsearch(0,sx,0,sy)

 def result(self):
  if self.found:
   count = len(self.visited)
   sx,sy = self.im.size
   ratio = float(count)/(sx*sy)
   print len(self.visited), ratio, self.position, self.L[self.position[0], self.position[1]], "=", self.c
  else:
   print self.c, "not found"

if __name__ == "__main__":
 image_name="turret-arch"
 c=(116,70,36)
 F = Finder(image_name, c)
 F.start()
 F.result()

```

It is a recursive quad-section search. Sometimes it finds the correct value in a few percent, sometimes over 75%. Here are the results for all testcases:

`pixels_visited, percentage, (position) (RGB at position) = (RGB searched)`

```
tajinaste-rojo
1500765 0.062531875 (2329, 5146) (243, 56, 99) = (243, 56, 99)
(147, 157, 210) not found
335106 0.01396275 (2116, 5791) (114, 37, 19) = (114, 37, 19)
1770396 0.0737665 (1269, 5672) (108, 117, 116) = (108, 117, 116)
(214, 197, 93) not found
8086276 0.336928166667 (1546, 4867) (163, 102, 101) = (163, 102, 101)
12859 0.000535791666667 (1476, 4803) (192, 192, 164) = (192, 192, 164)
7505961 0.312748375 (3766, 5883) (92, 118, 45) = (92, 118, 45)
15057489 0.627395375 (1871, 1139) (145, 180, 173) = (145, 180, 173)
(181, 124, 105) not found
in-input
35754 0.00201500551852 (4695, 2559) (204, 90, 1) = (204, 90, 1)
5029615 0.283456451895 (10, 2680) (227, 163, 53) = (227, 163, 53)
6986547 0.393744217722 (1383, 3446) (196, 179, 135) = (196, 179, 135)
1608341 0.090642053775 (4518, 2108) (208, 59, 27) = (208, 59, 27)
581774 0.0327873194757 (3750, 2798) (149, 70, 1) = (149, 70, 1)
1302581 0.0734101891628 (4374, 1941) (168, 3, 7) = (168, 3, 7)
6134761 0.345739701008 (25, 2606) (218, 118, 4) = (218, 118, 4)
(127, 153, 4) not found
9760033 0.550050913352 (4482, 1442) (224, 230, 246) = (224, 230, 246)
212816 0.0119937745268 (4701, 2579) (213, 127, 66) = (213, 127, 66)
water-lilies
5649260 0.390767412093 (4577, 3019) (86, 140, 80) = (86, 140, 80)
12600699 0.871608412215 (1910, 2457) (218, 124, 174) = (218, 124, 174)
(191, 77, 50) not found
3390653 0.234536328318 (4402, 1894) (197, 211, 186) = (197, 211, 186)
(236, 199, 181) not found
7060220 0.488365537823 (1672, 1379) (253, 242, 162) = (253, 242, 162)
(114, 111, 92) not found
6852380 0.473988947097 (2147, 2717) (111, 93, 27) = (111, 93, 27)
(139, 92, 102) not found
14105709 0.975712111261 (3096, 993) (199, 157, 117) = (199, 157, 117)
dandelion
(55, 2, 46) not found
9094264 0.619162854031 (1637, 1721) (95, 37, 33) = (95, 37, 33)
2358912 0.16060130719 (1526, 3129) (27, 41, 50) = (27, 41, 50)
11729837 0.798600013617 (1905, 756) (58, 92, 129) = (58, 92, 129)
6697060 0.455954520697 (2246, 2685) (136, 159, 105) = (136, 159, 105)
6429635 0.437747480937 (2148, 2722) (152, 174, 63) = (152, 174, 63)
(78, 49, 19) not found
(217, 178, 205) not found
80727 0.00549611928105 (2481, 3133) (69, 95, 130) = (69, 95, 130)
239962 0.0163372821351 (2660, 917) (150, 171, 174) = (150, 171, 174)
turret-arch
210562 0.0467313240712 (725, 655) (116, 70, 36) = (116, 70, 36)
(121, 115, 119) not found
2548703 0.565649385237 (140, 604) (183, 222, 237) = (183, 222, 237)
150733 0.033453104887 (2165, 601) (237, 136, 82) = (237, 136, 82)
3458188 0.767497003862 (2259, 953) (193, 199, 215) = (193, 199, 215)
2430256 0.539361711572 (265, 1222) (33, 30, 25) = (33, 30, 25)
638995 0.141816103689 (1778, 1062) (17, 23, 39) = (17, 23, 39)
2506522 0.556287895601 (1127, 970) (192, 139, 95) = (192, 139, 95)
1344400 0.298370988504 (147, 734) (176, 125, 98) = (176, 125, 98)
(178, 83, 0) not found
hot-air
17474837 0.875411434688 (1992, 1029) (48, 21, 36) = (48, 21, 36)
1170064 0.0586149905099 (3191, 1846) (104, 65, 36) = (104, 65, 36)
(169, 89, 62) not found
11891624 0.595717352134 (3948, 470) (68, 59, 60) = (68, 59, 60)
(198, 96, 74) not found
(136, 43, 53) not found
12476811 0.625032612198 (4387, 1126) (82, 42, 32) = (82, 42, 32)
4757856 0.238347376116 (3105, 1822) (192, 132, 72) = (192, 132, 72)
(146, 21, 63) not found
(125, 64, 36) not found
daisy
5322196 0.220287235367 (2171, 2128) (21, 57, 91) = (21, 57, 91)
(201, 175, 140) not found
22414990 0.9277629343 (2124, 759) (169, 160, 0) = (169, 160, 0)
20887184 0.864526601043 (1119, 1335) (113, 123, 114) = (113, 123, 114)
595712 0.0246566923794 (2656, 1349) (225, 226, 231) = (225, 226, 231)
3397561 0.140626034757 (2514, 3874) (17, 62, 117) = (17, 62, 117)
201068 0.00832226281046 (1978, 1179) (226, 225, 204) = (226, 225, 204)
18693250 0.773719036752 (2357, 917) (119, 124, 146) = (119, 124, 146)
3091040 0.127939041706 (2165, 3881) (2, 63, 120) = (2, 63, 120)
3567932 0.147677739839 (1453, 1759) (200, 167, 113) = (200, 167, 113)
barn
314215 0.0697356740202 (784, 1065) (143, 91, 33) = (143, 91, 33)
2448863 0.543491277908 (1999, 1260) (53, 35, 59) = (53, 35, 59)
(20, 24, 27) not found
(167, 148, 176) not found
(137, 50, 7) not found
(116, 95, 94) not found
2042891 0.453391406631 (1345, 858) (72, 49, 59) = (72, 49, 59)
(211, 163, 175) not found
(30, 20, 0) not found
(88, 36, 23) not found
klatschmohn
3048249 0.191409829222 (3683, 3439) (170, 133, 19) = (170, 133, 19)
1057649 0.0664133456509 (489, 2854) (162, 92, 4) = (162, 92, 4)
2058022 0.129230138206 (3095, 2475) (159, 175, 104) = (159, 175, 104)
(199, 139, 43) not found
2060805 0.129404892156 (3674, 1490) (171, 169, 170) = (171, 169, 170)
7725501 0.485110247577 (1958, 2404) (184, 115, 58) = (184, 115, 58)
2986734 0.187547095028 (1316, 2336) (228, 169, 5) = (228, 169, 5)
497709 0.0312528257017 (3879, 2379) (179, 165, 43) = (179, 165, 43)
3996978 0.250983720944 (2157, 2318) (67, 21, 6) = (67, 21, 6)
3332106 0.209234167028 (1303, 1816) (213, 100, 106) = (213, 100, 106)
gerbera
(218, 186, 171) not found
9445576 0.390955128952 (4377, 1750) (180, 153, 40) = (180, 153, 40)
(201, 179, 119) not found
6140398 0.254152853347 (5742, 576) (116, 112, 149) = (116, 112, 149)
6500717 0.269066561215 (4233, 1541) (222, 176, 65) = (222, 176, 65)
13307056 0.550782905612 (5302, 3734) (108, 129, 156) = (108, 129, 156)
13808847 0.571552180573 (5058, 2023) (125, 99, 48) = (125, 99, 48)
9454870 0.391339810307 (4478, 1647) (170, 149, 32) = (170, 149, 32)
2733978 0.113160142012 (4096, 368) (156, 185, 203) = (156, 185, 203)
11848606 0.490417237301 (4844, 1790) (103, 67, 17) = (103, 67, 17)

```
> 1 votes

---
Tags: image-processing, fewest-operations
---


title: Convolve integers in subquadratic time

text:
# Question
Title: Convolve integers in subquadratic time
An *linear discrete convolution* is an operation that turns two vectors of numbers into a third vector of numbers by multiplying elements inside-out. Formally, for two vectors `a` and `b` with elements `0` to `n - 1`, the discrete linear convolution of `a` and `b` can be computed with this loop:

```
for i = 0 to 2*n - 2
    c[i] = 0;
    for j = 0 to n - 1
        if i - j >= 0 and i - j < n
            c[i] = c[i] + a[j] * b[i - j];

```

As an example, the convolution of `a = { 1, 2, 3, 4 }` and `b = { 5, 6, 7, 8 }` is `c = { 5, 16, 34, 60, 61, 52, 32 }`. These convolutions appear when doing long multiplication, for example:

```
1234 * 5678 =
         20 24 28 32
      15 18 21 24
   10 12 14 16
 5  6  7  8
--------------------
 5 16 34 60 61 52 32
--------------------
      32
     52
    61
   60
  34
 16
 5
--------------------
 7006652

```

Your task is to write a program or function that, given two arrays (or similar) `a` and `b` of non-negative integers of equal length `n` and optionally, `n` and an output array `c`, computes the linear discrete convolution of `a` and `b` and returns it, assigns it to the parameter `c`. or prints it out. You may also take input from the user while or before your code is running. The following constraints apply:

* Your program must run in subquadratic or o(*n*2) time. An algorithm like the pseudo-code above that runs in quadratic time Θ(*n*2) is invalid.
* You may assume that all integers in in- and output are in the range from 0 to 65535, this also applies to `n`.
* You may not claim that your algorithm runs in subquadratic time because `n` has an upper bound.
* The results must be exact.
* This is code golf, the shortest code in octets wins.
* You may not use existing library routines or similar to compute a Fourier transform or a number theoretic transform or the respective inverse transformations.

# Answer
> 2 votes
# J, 79 bytes, *O*(*n* log *n*)

```
f=:_2&(0((+,-)]%_1^i.@#%#)&f/@|:]\)~1<#
<:@+&#$9(o.f%#)[:+@*/;f@{.&>~2^#@#:@+&#

```

Uses the Convolution theorem which states that the Fourier transform of the convolution of two sequences is equal to the Fourier transform of each sequence multiplied together elementwise.

```
Fourier( Convolve(a, b) ) = Fourier(a) * Fourier(b)
Convolve(a, b) = InverseFourier( Fourier(a) * Fourier(b) )

```

Also uses the fact the the inverse Fourier transform can be applied by using the Fourier transform of the conjugate.

```
InverseFourier(a) = Conjugate( Fourier( Conjugate(a) ) ) / Length(a)

```

I used the FFT implementation from a previous solution. That implementation uses the Cooley-Tukey algorithm for sequences where the length is a power of 2. Therefore, I have to zero-pad the input sequences to the a power of 2 (typically the minimal value that is valid) such that their lengths are greater than or equal to the sum of the lengths of the input sequences.

## Usage

```
   f =: _2&(0((+,-)]%_1^i.@#%#)&f/@|:]\)~1<#
   g =: <:@+&#$9(o.f%#)[:+@*/;f@{.&>~2^#@#:@+&#
   1 2 3 4 g 5 6 7 8
5 16 34 60 61 52 32
   2 4 5 6 1 g 1 2 4 7
2 8 21 46 61 61 46 7

```

Try it online!

## Explanation

An explanation for the FFT portion in J is included in my previous solution to a different challenge.

```
<:@+&#$9(o.f%#)[:+@*/;f@{.&>~2^#@#:@+&#  Input: A on LHS, B on RHS
                                      #  Get the lengths of A and B
                                    +&   Sum them
                                 #:@     Get list of binary digits
                               #@        Length
                             2^           Raise 2 to that power, call it N
                     ;                    Link A and B as a pair of boxed arrays
                          &>~             For each box
                        {.                  Take N values, extending with zeros
                      f@                    Apply FFT to it
               [:  */                    Reduce using multiplication
                 +@                      Conjugate
           f                             Apply FFT
            %                            Divide by
             #                           Length
       9 o.                              Take the real part
     #                                   Get the lengths of A and B
   +&                                    Sum them
<:@                                      Decrement
      $                                  Shape to that length and return

```

# Answer
> 6 votes
## Python 2, 250 bytes, n^log\_2(3)

```
s=lambda a,b,S=1:[x+y*S for x,y in zip(a,b)]
def f(a,A):
 n=len(a);m=n/2
 if m<1:return[a[0]*A[0]]
 if n%2:return f([0]+a,[0]+A)[2:]
 b,c=a[:m],a[m:];B,C=A[:m],A[m:];p=f(b,B);r=f(c,C);z=m*[0];return s(z+z+r,s(z+s(f(s(b,c),s(B,C)),s(p,r),-1)+z,p+z+z))

```

This isn't well golfed, but more a proof of concept of the algorithm. Let's look at a more readable version.

```
s=lambda a,b,S=1:[x+y*S for x,y in zip(a,b)]

def f(a,A):
 n=len(a)
 if n==1:return[a[0]*A[0]]
 if n%2:return f([0]+a,[0]+A)[2:]
 m=n/2
 b,c=a[:m],a[m:]
 B,C=A[:m],A[m:]
 p=f(b,B)
 r=f(c,C)
 q=s(f(s(b,c),s(B,C)),s(p,r),-1)
 z=m*[0]
 return s(z+z+r,s(z+q+z,p+z+z))

```

The idea is to divide and conquer adapting the Karatsuba multiplication algorithm to do convolution. As before, it runs in time `n^log_2(3)`, as it makes 3 recursive calls which shrink the input length in half. This isn't as good as the quasilinear of DFT, but still better than quadratic.

We can think of convolution as multiplication of formal polynomials. Alternatively, if multiplication were done without regrouping, you'd get convolution. So, adapting the algorithm only requires doing vector addition and subtraction instead of the numerical operations. These additions are still linear-time.

Unfortunately for Python, it doesn't have built-in vector addition and subtraction, so we hack together a function `s` to do both: addition by default, and subtraction when passed an optional argument of `-1`. Whenever we add, we make sure to pad with zeroes to avoid truncation.

We handle odd list lengths by padding with a zero to an even length, removing the extraneous zeroes that result.

# Answer
> 1 votes
# Mathematica, 214 bytes, O(n log n)

```
f@{a_}:={a}
f@a_:=#~Join~#+Join[#2,#2]Exp[2.Most@Range[0,1,1/Length@a]Pi I]&@@f/@Thread@Partition[a,2]
(l=Length@#;RotateLeft[Round[#/Length@#]][[-1;;(1-2l);;-1]]&@f[Times@@(f@PadRight[#,2^Floor[2+Log2@l]]&/@{##})])&

```

Function `f` performs FFT, which is called several times. No built-in FFT is used here.

```
%[{1,2,3,4},{5,6,7,8}]
(* {5,16,34,60,61,52,32} *)

```

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


title: The Ever Amplifying Zigzag

text:
# Question
Title: The Ever Amplifying Zigzag
Write a program or function that takes in a positive integer N and outputs the first N numbers of this amplifying zigzag pattern, using only the lines needed:

```
                                         26
                                       25  27                                      .
         10                          24      28                                  .
        9  11                      23          29                              .
 2     8     12                  22              30                          44
1 3   7        13              21                  31                      43
   4 6           14          20                      32                  42
    5              15      19                          33              41
                     16  18                              34          40
                       17                                  35      39
                                                             36  38
                                                               37

```

So, if N is `1` the output is

```
1

```

If N is `2`, the output is

```
 2
1

```

If N is `3` the output is

```
 2
1 3

```

If N is `4` the output is

```
 2
1 3
   4

```

If N is `10` the output is

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

```

If N is `19` the output is

```
         10
        9  11
 2     8     12
1 3   7        13
   4 6           14
    5              15      19
                     16  18
                       17

```

and so on.

# Notes

* Each peak or trough of the zigzag reaches its point one more line away from the line with the `1` on it than the previous peak or trough.
* N is not limited to `44`. The zigzag grows in the same pattern and larger N should be supported.
* Numbers with multiple digits should only "touch" at their corners, as depicted. Make sure this works when N is `100` and above.
* There should be no empty (or space only) lines in the output except one optional trailing newline.
* Any line may have any amount of trailing spaces.

# Scoring

The shortest code in bytes wins. Tiebreaker is earlier answer.

# Answer
# Jelly, ~~41~~ ~~37~~ 29 bytes

```
RDµḌ’½Ċ-*_\x©L€Ṣ.ị®ạ€⁶ẋj"FZj⁷

```

Try it online!

### How it works

```
RDµḌ’½Ċ-*_\x©L€Ṣ.ị®ạ€⁶ẋj"FZj⁷  Main link. Argument: n (integer)

R                              Range; yield [1, ..., n].
 D                             Decimal; yield A =: [[1], ..., [1, 0], ...].
  µ                            Begin a new, monadic chain. Argument: A
   Ḍ                           Undecimal; convert back to falt range.
    ’                          Decrement to yield [0, ..., n-1].
     ½Ċ                        Take the square root and round up (ceil).
       -*                      Elevate -1 to each rounded square root.
         _\                    Cumulatively reduce by subtraction.
                               This yields [1, 2, 1, 0, -1, 0, ...], i.e., the
                               vertical positions of the digits in A.
             L€                Compute the length of each list in A.
           x                   Repeat the nth position l times, where l is the
                               nth length.
            ©                  Copy the result to the register.
               Ṣ               Sort.
                .ị             At-index 0.5; yield the last and first element,
                               which correspond to the highest and lowest position.
                  ạ€®          Take the absolute difference of each position in the
                               register and the extrema.
                               This yields the number of spaces above and below
                               the integers in r as a list of pairs.
                     ⁶ẋ        Replace each difference with that many spaces.
                         F     Flatten the list A.
                       j"      Join the nth pair of strings of spacing, separating
                               by the nth digit in flat A.
                          Z    Zip/transpose the result.
                           j⁷  Join, separating by linefeeds.

```
> 10 votes

# Answer
# PHP, ~~211~~ ~~177~~ ~~164~~ 163 bytes

Predict the peaks with `$n` and increase the array dynamically in either direction, using `($x, $y)` output cursor.

Numbers are aligned with `str_pad()` and the final output is the `implode()` of that array of strings (`$g`).

```
for($x=0,$d=-1,$h=$n=2,$y=$a=1;$a<=$argv[1];$y+=$d){$g[$y]=str_pad($g[$y],$x).$a;$x+=strlen($a);if($a++==$n){$h+=2;$n+=$h-1;$d*=-1;}}ksort($g);echo implode(~õ,$g);

```

## Test it online!

Update: removed 34 bytes by getting rid of the unneeded array\_pad(). Update2: followed @insertusernamehere's advice to shorten it a bit more. Update3: followed @Lynn's advice to save one more byte with ~õ which imposes the use of LATIN-1 charset. (not available in online PHP emulator so not included there)
> 8 votes

# Answer
# Pyth, ~~60~~ ~~53~~ ~~52~~ ~~46~~ ~~42~~ ~~39~~ ~~38~~ ~~36~~ ~~34~~ ~~32~~ 31 bytes

39: It is now on par with the bug-fixed version of Jelly, and I have out-golfed Dennis' competing version!

38: I have out-golfed Dennis!

36: I have out-golfed Dennis again!

34: Even lower than his bug-fixed version!

31: 32 -\> 31 thanks to Dennis.

```
~~J1K.u+N=J_WsI@Y2JtQZjsM.t.e++*]*dl`hkabhSK`hk*]*dl`hkabeSKKd~~
~~J1K.u+N=J_WsI@Y2JtQZjsM.t.eX*]*dl`hkhaeSKhSKabhSKhkKd~~
~~J1K.u+N=J_WsI@Y2JtQZ=-RhSKKjsM.t.eX*]*dl`hkheSKbhkKd~~
~~J1K.u+N=J_WsI@Y2JtQQj-#dsMC.eX*]*dl`hkheSKbhkK~~
~~J1j-#dsMC.eX*]*dl`hkyQ+Qbhkm=+Z=J_WsI@td2J~~
~~J1j-#dsMCmX*]*;l`hdyQ+Q=+Z=J_WsI@td2Jhd~~
~~J1j-#dsMCmX*]*;l`hdyQ+Q=+Z=J_WsI@td2Jh~~
~~J1j-#dsMCmX*]*;l`hdyQ+Q=+Z=@_BJsI@td2h~~
~~j-#dsMCmX*]*;l`hdyQ+Q=+Zsty%s@td2 2h~~
~~j-#dsMCmX*]*;l`hdyQ+Q=+Z@_B1.E@d2h~~
~~JQj-#dsMCmX*]*;l`hdyQ=+J@_B1.E@d2h~~
~~JyQj-#dsMCmX*]*;l`hdJ=+Q@_B1.E@d2h~~
~~j-#dsMCmX*]*;l`hdyQ=+Q@_B1.E@d2h~~
j-#dsMCmX*]*;l`hdyQ=+Q^_1.E@d2h

```

Try it online!

## How it works

```
j-#dsMCmX*]*;l`hdyQ=+Q^_1.E@d2h      input: Q
j-#dsMCmX*]*;l`hdyQ=+Q^_1.E@d2hdQ    implicit filling arguments

       m                        Q    for each number d from 0 to Q-1:
                           @d2           yield the square root of d.
                         .E              yield its ceiling.
                      ^_1                raise -1 to that power. this
                                         yields the desired direction.
                   =+Q                   increment Q by this amount.

               hd                        yield d+1.
              `                          yield its string representation.
             l                           yield its length.
           *;                            repeat " " for that number of times
          ]                              yield a list containing the string above.
         *       yQ                      repeat the list for Q*2 times.
                                         the Q has changed, but Q*2 is
                                         an overshoot that is high
                                         enough, so we don't have to
                                         worry about it.

        X                                in that list, replace the
                                         element with index being the
                                         number generated above
                              hd         with d+1.

      C                              transpose the resulting array.
    sM                               flatten each element.
 -#d                                 remove lines containing only spaces.
                                     (filter on truthiness of set difference with space)
j                                    join by newlines.

```
> 8 votes

# Answer
# MATLAB, 148 bytes

```
n=input('');k=fix(n^.5);m=0;w=1;d=-1;for l=1:n;s=num2str(l);m(k+1,w:w+nnz(s)-1)=s;w=w+nnz(s);k=k+d;d=d*(-1)^(l^.5==fix(l^.5));end;[m(any(m,2),:),'']

```

Note that the spaces are missing in Octave, as MATLAB prints the the character indexed with `0` as a space, while octave does just omit that character.

Explanation:

```
n=input('');
k=fix(n^.5);                    %caculate starting height
m=0;w=1;d=-1;                   %initialize counters and output matrix
for l=1:n;
    s=num2str(l);
    m(k+1,w:w+nnz(s)-1)=s;      %insert current index as a string
    w=w+nnz(s);                 %current horizontal position
    k=k+d;                      %current vertical position
    d=d*(-1)^(l^.5==fix(l^.5)); %if we reached a square number, change direction
end
[m(any(m,2),:),'']              %delete all zero rows

```
> 5 votes

# Answer
## Haskell, ~~144~~ 142 bytes

```
g n|k<-take n$scanl(+)0$[1..]>>= \x->(-1)^x<$[2..2*x]=unlines[[1..n]>>= \x->show x#(k!!(x-1)==y)|y<-[minimum k..maximum k]]
s#g|g=s|1<2=' '<$s

```

Usage example:

```
*Main> putStr $ g 19
         10
        9  11
 2     8     12
1 3   7        13
   4 6           14
    5              15      19
                     16  18
                       17

```

How it works:

```
s#g|g=s|1<2=' '<$s              -- # is a helper function that expects a string s
                                -- and a boolean g. It returns s if g is True, else
                                -- as many spaces as there a characters in s

k<-take n$                      -- bind k to the first n elements of
 [1..]>>= \x->(-1)^x<$[2..2*x]  -- 2*x-1 copies of (-1)^x for each x in [1,2,3,...]
                                -- i.e. [-1, 1,1,1, -1,-1,-1,-1,-1, 1,1,1,1,1,1,1..]
 scanl(+)0                      -- build partial sums, starting with 0
                                -- i.e. [0,-1,0,1,2,1,0,-1,-2,-3,-2,-1...]
                                -- -> k is the list of y coordinates for the
                                --    numbers 1,2,3,...

 [  |y<-[minimum k..maximum k]] -- for all y coordinates in k
      \x->show x#(k!!(x-1)==y)  -- map the # function
  [1..n]>>=                     -- over [1..n] (the x coordinates)
                                -- where # is called with
                                --  s -> a string representation of x
                                --  g -> True if k at index x equals the current y
unlines                         -- join with newlines

```

Edit: Thanks @Lynn for two bytes!
> 3 votes

# Answer
## JavaScript (ES6), 213 bytes

```
with(Math)n=>(a=[...Array(n)].map((_,i)=>n-=1+sqrt(--i)&1||-1).map((e,_,a)=>e-min(...a))).map((e,i)=>r[e][i]=++i,r=[...Array(1+max(...a))].map(_=>a.map((_,i)=>` `.repeat(1+log10(++i)))))&&r.map(a=>a.join``).join`\n`

```

Where `\n` represents a literal newline character. Explanation:

```
with(Math)                          Bring functions into scope
 n=>                                Accepts one parameter
  (a=                               Intermediate result variable
   [...Array(n)].map(               For each number 0..n-1
    (_,i)=>n-=                      Accumulate index for each number
     1+sqrt(--i)&1||-1              Calculate the direction
    ).map((e,_,a)=>e-min(...a))     Scale the smallest index to zero
  ).map((e,i)=>r[e][i]=++i,         Overwrite the padding with 1..n
   r=[...Array(1+max(...a))].map(   Calculate number of lines
    _=>a.map((_,i)=>                For each number 1..n
     ` `.repeat(1+log10(++i)))))    Calculate the padding needed
  &&r.map(a=>a.join``).join`\n`     Join everything together

```

To shorten `pow(-1,ceil(sqrt(i)))` I rewrite it as `sqrt(i-1)&1||-1` however this doesn't work for `i=0` so to fix that I add 1 but this then flips the sign of the result which is why I end up with `n-=`.
> 2 votes

# Answer
# Python 2, 137 bytes

```
l={}
i=x=y=n=v=0
exec"v+=1;l[y]=l.get(y,'').ljust(x)+`v`;x+=len(`v`);i=-~i%-~n;y+=n%4-1;n+=2>>i*2;"*input()
for k in sorted(l):print l[k]

```

View the output on ideone.
> 1 votes

---
Tags: code-golf, ascii-art, number
---


# Question
Title: Convert the first letter of each word to uppercase, and the rest to lowercase
## Description

Your task is to take a string as input, and convert the first letter of each word to uppercase, and the rest to lowercase.

## Test Cases

`Input` =\> `Output`

`ISN'T THIS A REALLY COOL TEST CASE???` =\> `Isn't This A Really Cool Test Case???`
`tHis iS A rEALLY WeiRd SeNTEncE` =\> `This Is A Really Weird Sentence`
`I Like This Sentence` =\> `I Like This Sentence`

### Edit: no built-ins allowed.

---

This is , so lowest byte count wins. Good luck!

# Answer
# , ~~14~~ 8 bytes

```
gu$ògUlW

```

Try it online!

Explanation:

```
gu$       #Make everything lowercase
   ò      #Recursively
    gUl   #Make the current character uppercase
       W  #And move forward a word

```

Here is a 9-byte, non-competing version (the old interpreter had a bug):

```
gu$Ó¼÷/Õ°

```

This version is just a regex:

```
gu$            #Make everything lowercase
   Ó¼÷/Õ°      #Expands into ':s/\<\w/\U\0/g`

```
> 3 votes

# Answer
# Pyth, 6 bytes

```
~~jdm+rhd1rtd0c~~
jdrR4c

```

Test suite.

Split into words, capitalize each, then join by space.

It is not a built-in, because `capitalize` converts `test case` into `Test case` instead of `Test Case`.

### (with built-ins)

```
r5

```

Test suite.
> 2 votes

# Answer
# s-lang, 7 bytes (Non-competing)

### Try it here!

```
w[ ]Cc!

```

## Explanation:

* `w[ ]` splits the input string by spaces
* `C` converts the selection (which is now the split-up words) to lower-case
* `c!` `c` converts the selection to upper-case, but since it uses the parameter `!`, it only converts the first letter of each range of characters in the selection (which are words since we split by spaces)
> 2 votes

# Answer
# Ruby, 29 bytes

```
gets.gsub(/\S+/,&:capitalize)

```

I'm still learning ruby though \>\_\>
> 2 votes

# Answer
## Pyke, 5 bytes

```
cml5J

```

Try it here!

Split, map caps, join
> 1 votes

# Answer
# Python, ~~51~~ bytes

3 bytes thanks to xnor.

```
~~lambda n:' '.join(a.capitalize()for a in n.split())~~
lambda n:' '.join(map(str.capitalize,n.split()))

```

Ideone it!

### using built-in, 28 bytes

```
from string import*
capwords

```

Ideone it!
> 0 votes

# Answer
# Retina, 19 bytes

```
T`L`l
T`l`L`(^|\s).

```

Try it online!
> 0 votes

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


# Question
Title: Here's Bub. A not-so-world-class soccer player
This is Bub. Bub is a soccer player. However, he's not a very good one. He still can't kick the ball to the net! (If you haven't noticed, `@` is the ball.

```
                                                       _____
                                                      |     \
  O                                                   |      \
 \|/                                                  |       \
  |                                                   |  net   \
 / ─   @                                              |_________\

```

To help develop his skills, he's developed a system to help evaluate his performance when he kicks the ball. He's called it the "10 point system."

However, he doesn't know what he needs to do to achieve *x* number of points. You need to help him visualize where the ball will be, so that he can set an expectation of how many points he wants to get. There are 10 points per round that he can achieve.

Therefore, this is your challenge.

Given a number *x*, the number of points Bub gets, output the location of the ball on the field. Here are some helpful markers:

* Bub is exactly 50 spaces away from the net.
* For each point that Bub gets, the ball moves 5 spaces closer to the net. Therefore, if Bub gets 3 points, the ball is 35 spaces away from the net.
* For every 3 points that Bub gets, the ball begins to move in the air! It moves one space up.
* If the number of points Bub gets would move the ball behind the net, you can put the ball anywhere inside the net.

Remember, you need to draw Bub, the ball, and the net.

To get you started, here's an example:

### Number of Points: 5

```
                                                       _____
                                                      |     \
  O                                                   |      \
 \|/                                                  |       \
  |                          @                        |        \
 / ─                                                  |_________\

```

Standard rules apply. Code with the lowest number of bytes wins! Happy golfing!

# Answer
> 3 votes
# Pyth, ~~106~~ 91 bytes

Run-length encoding, followed by internal encoding.

Hexdump:

```
0000000: 4a 63 72 58 2e 22 30 41 01 b6 07 31 11 af 55 c5 JcrX."0A...1..U.
0000010: 16 6f 93 4f ea 90 6b 39 f6 e0 dc 81 43 9d 01 f7 .o.O..k9....C...
0000020: 36 93 ee 4c c8 fa a5 28 70 22 6d 43 2b 35 38 64 6..L...(p"mC+58d
0000030: 38 22 0a 20 2f 4f 5c 5c 5f 7c 2d 22 39 62 6a 58 8". /O\\_|-"9bjX
0000040: 4a 4b 2d 35 2f 68 53 2c 54 51 33 58 40 4a 4b 68 JK-5/hS,TQ3X@JKh
0000050: 53 2c 35 38 2b 34 2a 35 51 5c 40                S,58+4*5Q\@

```

Try it online!

Replace the Unicode character  (U+2500) as a single hyphen.

# Answer
> 3 votes
# JavaScript (ES6), 189

```
f=n=>"       o \\|/ | / -".match(/.../g).map((v,r)=>(v=[...v+' '.repeat(50)+'| '[+!r]+' _'[+(!r|r>4)].repeat(r+4)+'\\_'[+!r]],y-r?0:v[x]='@',v.join``),n<11?0:n=11,x=3+n*5,y=5-(n/3|0)).join`
`

```

**Test**

```
f=n=>"       o \\|/ | / -".match(/.../g).map((v,r)=>(v=[...v+' '.repeat(50)+'| '[+!r]+' _'[+(!r|r>4)].repeat(r+4)+'\\_'[+!r]],y-r?0:v[x]='@',v.join``),n<11?0:n=11,x=3+n*5,y=5-(n/3|0)).join`
`
var n=0

setInterval(function(){
  N.textContent=n,O.textContent=f(n),n=(n+1)&15
},1000)
```

```
<pre id=O></pre><span id=N></span>
```

---
Tags: code-golf, ascii-art
---


title: Count, Replace, Add Up!

text:
# Question
Title: Count, Replace, Add Up!
### Definition

Define the **n**th term of the CRAU sequence as follows.

1. Begin with the singleton array **A = \[n\]**.
2. Do the following **n** times:

For each integer **k** in **A**, replace the entry **k** with **k** natural numbers, counting from **1** to **k**.
3. Compute the sum of all integers in **A**.

For example, if **n = 3**, we start with the list **\[3\]**.

We replace **3** with **1, 2, 3**, yielding **\[1, 2, 3\]**.

We now replace **1**, **2**, and **3** with **1**, **1, 2** and **1, 2, 3** (resp.), yielding **\[1, 1, 2, 1, 2, 3\]**.

Finally, we perform the same replacements as in the previous step for all six integers in the array, yielding **\[1, 1, 1, 2, 1, 1, 2, 1, 2, 3\]**.

The sum of the resulting integers is **15**, so this is the third CRAU number.

### Task

Write a program of a function that, given a strictly positive integer **n** as input, computes the **n**th term of the CRAU sequence.

This is . May the shortest code in bytes win!

### Test cases

```
 1 ->       1
 2 ->       4
 3 ->      15
 4 ->      56
 5 ->     210
 6 ->     792
 7 ->    3003
 8 ->   11440
 9 ->   43758
10 ->  167960
11 ->  646646
12 -> 2496144
13 -> 9657700

```

### Related

# Answer
> 3 votes
# MATL, 5 bytes

```
EGqXn

```

Try it online, or verify all test cases!

Explanation:

```
E       #Double the input
 Gq     #Push "input - 1"
   Xn   #Calculate "nchoosek" on the two numbers

```

# Answer
> 2 votes
# Python, 65 bytes

```
def f(k):
 n,p=2*k,1
 for i in range(1,k):p=p*n//i;n-=1
 return p

```

Explanation: It's a simplified version of n choose k. See this sequence.

# Answer
> 1 votes
## Retina, 27 bytes

```
$
$.`$*
M!&+%`.+(?=1)|^.+
0

```

Input in unary, using `0` as the unary digit.

Try it online!

# Answer
> 1 votes
# J, 5 bytes

```
<:!+:

```

Uses the binomial coefficient of (2*n*, *n*-1).

For **22 bytes**, this is a possible solution based on using the process described in the challenge.

```
[:+/([:;<@(1+i.)"0)^:]

```

## Usage

Note: Extra commands used to format output for multiple input.

```
   f =: <:!+:
   (,.f"0) >: i. 13
 1       1
 2       4
 3      15
 4      56
 5     210
 6     792
 7    3003
 8   11440
 9   43758
10  167960
11  646646
12 2496144
13 9657700

```

## Explanation

```
<:!+:  Input: n
   +:  Double the value of n to get 2*n
<:     Decrement n to get n-1
  !    Calculate the binomial coefficient of (2*n, n-1) and return

[:+/([:;<@(1+i.)"0)^:]  Input: n
                     ]  Identify function, gets the value n
    (     ...     )^:   Repeat the following n times with an initial value [n]
          (    )"0        Means rank 0, or to operate on each atom in the list
             i.           Create a range from 0 to that value, exclusive
           1+             Add 1 to each to make the range from 1 to that value
        <@                Box the value
     [:;                  Combine the boxes and unbox them to make a list and return
[:+/                    Sum the values in the list after n iterations and return

```

---
Tags: code-golf, math, sequence, arithmetic, array
---


title: Tell Me about yourself

text:
# Question
Title: Tell Me about yourself
Your task is to write a self referential program similar to a quine. The objective is to write a program that will generally print to stdout twice whatever the input is. But when it receives the input of "Tell me about your source" it should output its source (like a quine). Also if it receives the query "tell me about your length". It should output its length in utf-8 characters. Like always all standard loopholes are disabled. This is code golf in any language of your choosing.

Sample Input

```
2

```

Sample Output

```
4

```

Sample Input

```
Tell me about your source

```

Sample Output

```
x

```

Sample Input

```
Tell me about your length

```

Sample Output

```
1

```

Clarifications: The input will always be valid your program is always going to receive valid input. Your code is not required to recognize invalid input.

# Answer
# Javascript - ~~93~~ ~~92~~ 89 bytes

Defines a function `f`. Not sure of a better way to return.

```
f=n=>{y="Tell me about your ";x="f="+f;return n==y+"source"?x:n==y+"length"?x.length:2*n}

```
> 1 votes

---
Tags: code-golf, quine
---


title: Ways to get to the number

text:
# Question
Title: Ways to get to the number
Given the input of the first number and the second number (both positive integers, zero exluded), determine in how many ways could you make the second out of the first, using following actions: `+1`,`+2` and `*3`. Operations are simply applied from left to right.

Examples:

1. Input: `1 2`. Output: `1`. I.e, you could only get `2` by doing `+1`, so one way.
2. Input: `1 3`. Output: `3`. I.e, you could get 3 by either doing `+2` or `+1+1`, or `*3`
3. Input: `1 4`. Output: `4`.
4. Input: `2 6`. Output: `6`.
5. Input: `2 7`. Output: `9`.
6. Input: `1 10`. Output: `84`.

In case there're no ways, e.g. `100 100`, or `100 80`, output is `0`.

You could also take input as an array, or string with any convenient separator.

The shortest solution wins.

# Answer
> 1 votes
# Pyth - ~~26~~ 24 bytes

There seems to be a bug in Pyth that's making it take inputs in the wrong order, but it shouldn't matter anyway.

```
/m.vj;+sdzs^Lc3"+1+2*3"S

```

Test Suite.

(`1 10` timed out online, but worked on my computer).

# Answer
> 6 votes
# Javascript ES6, ~~45~~ 44 bytes

```
f=(a,b=B)=>a<(B=b)?f(a+1)+f(a+2)+f(a*3):a==b

```

Example runs:

```
f(1,2)  -> 1
f(2,6)  -> 6
f(1 10) -> 84

```

# Answer
> 1 votes
# Pyth, 29 bytes

```
M?>GH0|qGH+sgLGtBtH?%H3ZgG/H3

```

Try it online!

Defines a function. Added three bytes in the link to call the function.

---
Tags: code-golf, arithmetic, combinatorics, path-finding, counting
---


title: Prove that a Number is Algebraic

text:
# Question
Title: Prove that a Number is Algebraic
Inspired by **this answer** (emphasis mine):

> We will play a game. Suppose you have some number ***x***. You start with ***x*** and then you can add, subtract, multiply, or divide by any integer, except zero. You can also multiply by ***x***. You can do these things as many times as you want. If the total becomes zero, you win.
>
> For example, suppose ***x*** is 2/3. Multiply by 3, then subtract 2. The result is zero. You win!
>
> Suppose ***x*** is 7^(1/3). Multiply by ***x*** , then by ***x*** again, then subtract 7. You win!
>
> Suppose ***x*** is √2+√3. Here it's not easy to see how to win. But it turns out that if you multiply by ***x***, subtract 10, multiply by ***x*** twice, and add 1, then you win. (This is not supposed to be obvious; you can try it with your calculator.)
>
> But if you start with ***x***=π, you cannot win. There is no way to get from π to 0 if you add, subtract, multiply, or divide by integers, or multiply by π, no matter how many steps you take. (This is also not supposed to be obvious. It is a very tricky thing!)
>
> > **Numbers like √2+√3 from which you can win are called algebraic**. Numbers like π with which you can't win are called transcendental.
>
> Why is this interesting? Each algebraic number is related arithmetically to the integers, and the winning moves in the game show you how so. The path to zero might be long and complicated, but each step is simple and there is a path. But transcendental numbers are fundamentally different: they are not arithmetically related to the integers via simple steps.

---

Essentially, you will use the steps used in the question quoted above to "win" the game for given input.

Given a real, algebraic constant `x`, convert the number to zero by using the following allowed operations:

* Add or Subtract an integer.
* Multiply or Divide by a non-zero integer.
* Multiply by the original constant `x`.

Input is a string that may contain integers, addition, subtraction, multiplication, division, exponentiation (your choice of `**` or `^`, exponents are used to represent roots), and parentheses. Spaces in the input are optional, but not in the output. You should output the steps necessary to obtain a result of zero, so multiplying by `7` as one step would be output as `*7`. A trailing space and/or newline is allowed.

### Examples

```
0               ->  +0 (or any other valid, or empty)
5/7 + 42        ->  -42 *7 -5 (or shorter: *7 -299)
2^(1/3)         ->  *x *x -2
5*(3**(1/4))    ->  *x *x *x -1875
2^(1/2)+3^(1/2) ->  *x -10 *x *x +1

```

Shortest code wins.

# Answer
# SageMath, 108 bytes

```
def f(s):p=map('{:+} '.format,numerator(minpoly(sage_eval(s)/1)));return'*'+p[-1][1:]+'*x '.join(p[-2::-1])

```

Try it on SageMathCell.

Explanation:

Evaluate the string symbolically as an algebraic number (`sage_eval()`). Every algebraic number is a zero of some polynomial *a*\[0\] + *a*\[1\] *x*^1 + *a*\[2\] *x*^2 + ⋯ + *a*\[n\] *x*^*n* with rational coefficients *a*\[0\], …, *a*\[*n*\] (`minpoly()`). Multiply all the coefficients by their common denominator to turn them into integers (`numerator()`), then write this polynomial in the desired output format,

```
*a[n] +a[n-1] *x +a[n-2] *x … *x +a[1] *x +a[0]

```

### SageMath, 102 bytes, almost

```
lambda s:(lambda a,*p:'*%d'%a+'*x'.join(map(' {:+} '.format,p)))(*numerator(minpoly(1/sage_eval(s))))

```

This works for all inputs *except* 0, because a polynomial for 1/*α* is a polynomial for *α* with the coefficients reversed. :-(
> 3 votes

# Answer
## Mathematica, ~~194~~ ~~224~~ 192 bytes

```
""<>Cases[HornerForm@MinimalPolynomial[ToExpression@#,x]//.{Times->t,x^a_:>Fold[#2~t~#&,x~Table~a],a_~t~b_~t~c_:>a~t~t[b,c]},a_~b_~_:>{b/.t:>"*"/.Plus:>If[a>0,"+",""],ToString@a," "},{0,∞}]&

```

Here  is the three byte unicode character representing infinity in Mathematica.

Since input is a string, 13 bytes are lost on `ToExpression@` which interprets the string input as an algebraic expression.

```
HornerForm@MinimalPolynomial[2^(1/2)+3^(1/2), x]

```

Would return something like

```
1 + x^2 (-10 + x^2)

```

The next replacement rule massages this into something that is structurally like

```
1 + (x * (x * (-10 + (x * (x)))))

```

This Horner form can be visualized like a tree:

We, by the rules of OP start out with the deepest leaf on the right.

`Cases` goes through the expression, starting at the deepest level, taking each parent node and its left leaf and assembling this into a table such as

```
"*" "x"   " "
""  "-10" " "
"*" "x"   " "
"*" "x"   " "
"+" "1"   " "

```

`""<>` concatenates everything with the empty string.
> 1 votes

---
Tags: code-golf, math
---


title: Illiteral Prime numbers

text:
# Question
Title: Illiteral Prime numbers
Your challenge is to write a program (full program, not a function), that will take an integer and output all prime numbers up to (including) the given integer. Output is any readable list containing all integer primes (array, string, 1 prime per line, whatever you want) and must run to stdout or equivalent.

Simple? Here's the twist:

You may not use literals in your program. These include:

* Literal numbers (0 through 9)
* Literal strings (in quotes)

You may not use built in prime checks

EDIT: A *prime check* is a built in function that

* Returns if a number is a prime number
* Returns a prime number
* Returns a list of prime numbers

You may code your own functions that do the above

Prime factorisation functions are allowed

As this is code-golf, shortest answer in bytes wins

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

### Six byte solution

Since prime factorisation is now allowed, this is my six byte solution:

```
LDÒ€gÏ

```

Explanation:

```
L       # Create the list [1, ..., input]
 D      # Duplicate this list
  Ò     # Get the prime factorisation of each number
   €g   # Get the length of each prime factorisation (length 1 = prime)
     Ï  # Keep the numbers for which is the index is equal to 1

```

Uses **CP-1252** encoding. Try it online!.

---

### Previous solution

Uses Wilson's theorem. Code:

```
LÐ<!n%Ï

```

Explanation:

```
L        # Generate the list [1, ..., input].
 Ð       # Triplicate the list.
  <      # Decrement the last one by one.
   !     # Take the factorial.
    n    # Square each.
     %   # Modulo the list by [1, ..., input].
      Ï  # Take the values for which the indices are equal to 1.

```

Visual explanation for input **n = 9**:

```
 Command - Stack

L        # [1, 2, 3, 4, 5, 6, 7, 8, 9]
 Ð       # [1, 2, 3, 4, 5, 6, 7, 8, 9] × 3
  <      # [1, 2, 3, 4, 5, 6, 7, 8, 9] × 2, [0, 1, 2, 3, 4, 5, 6, 7, 8]
   !     # [1, 2, 3, 4, 5, 6, 7, 8, 9] × 2, [1, 1, 2, 6, 24, 120, 720, 5040, 40320]
    n    # [1, 2, 3, 4, 5, 6, 7, 8, 9] × 2, [1, 1, 4, 36, 576, 14400, 518400, 25401600, 1625702400]
     %   # [1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 1, 0, 1, 0, 1, 0, 0]

```

Which leaves us (using `Ï`):

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

    2  3     5     7

```

Uses **CP-1252** encoding. Try it online!.
> 8 votes

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

*1 byte saved thanks to Dennis.*

```
Ṗ!²%ḊT‘

```

Try it online!

This is my first (working) Jelly program. I have no idea what I'm doing. :P

Also uses Wilson's theorem.
> 6 votes

# Answer
# 05AB1E, 2 bytes

```
!f

```

Allowing prime factorization makes this a bit too easy...

Try it online!

### How it works

```
!   Compute the factorial of the input.
 f  Find its prime factors.

```
> 6 votes

# Answer
# Pyth, 11 bytes

```
f!%h.!tTTtS

```

Try it online.

Uses Wilson's theorem. Not my own idea (suggested to DenkerAffe by Leaky Nun & used already by Adnan), so I'm making it a community wiki.
> 5 votes

# Answer
## JavaScript (ES6), 98 bytes

```
alert([...Array(-~(n=prompt())).keys()].filter(n=>n>!!n&&[...Array(n)].every((_,i)=>i==!!i||n%i)))

```

```
f=n=>[...Array(-~n).keys()].filter(n=>n>!!n&&[...Array(n)].every((_,i)=>i==!!i||n%i))
```

```
<input id=i oninput=o.value=f(i.value)><input id=o>
```
> 3 votes

# Answer
# Ruby, 53

```
$..upto(gets.to_i){|i|($....i).one?{|f|i%f<$.}&&p(i)}

```

This uses the `$.` magic variable in place of numeric literals, since it starts off as `0` and is incremented when we call `gets` to read from standard input. We can then define a prime number as a number that has exactly one factor less than it (`$....i` means the range from `1` to `i` excluding `i`) to avoid erroneously printing 0 and 1.
> 3 votes

# Answer
# Retina, ~~29~~ 27 bytes

```
!&`(?!.$|(?<k>..+)\<k>+$).+

```

Try it online!

Input/output in unary.

## How it works:

It matches, with overlapping (`&`), the substrings of the input that are not 1 (`(?!.$`) and are not composite numbers (`(?<k>..+)\<k>+$`), then output all matches linefeed-separatedly (`!`)
> 2 votes

# Answer
# Pyth, 13 bytes

```
fqh!Z/%LTSTZS

```

Try it here!

## Explanation

Using the shortest (but most inefficient) way to check for primes.

```
fqh!Z/%LTSTZSQ    # implicit: Q = input

f           SQ    # Filter [1...Q] with T
       L ST       # Map over [1...T]
      % T         # T module the lambda var
     /     Z      # Count number of zeroes
 qh!Z             # If ^ is 2, it's a prime

```
> 2 votes

# Answer
# MATL, 10 bytes

```
:t!\~sqq~f

```

Try it online!

It could be shortened to **9 bytes** using `H` (which produces predefined literal `2`). But it feels like cheating:

```
:t!\~sH=f

```

Try it online!

### Explanation

```
:     % Implicitly take input N. Generate row vector [1 2 ... N]
t!    % Duplicate and transform into column vector
\     % Modulo operation, element-wise with broadcast
~     % Logical negate. Transform zeros to 1, non-zeros to 0
s     % Sum of each column
qq    % Decrement by 1, twice. Zeros correspond to primes
~f    % Indices of zeros. Implicitly display

```
> 2 votes

# Answer
# JavaScript (ES6), 110 bytes

```
f=n=>{p=true;q=[];for(i=p+p;i<=n;i++){for(j=i/i;++j<i;p=i%j?p:p>p);p?q.push(i):i;p=true}alert(q)};f(+prompt())
```

Thanks to @LeakyNun for helping me shorten my solution.
> 1 votes

# Answer
# Brachylog, 6 bytes

```
$!$pd.

```

Saved a crapload of bytes thanks to @LeakyNun, who pointed out that you can use prime factorization built-ins.
> 1 votes

# Answer
# Perl 6,  ~~51 48~~  47 bytes

```
~~.say for grep {!first $_%%*,[*]^.. .sqrt},[*]^..get~~
~~.say for grep {!first $_%%*,[*]^..^$_},[*]^..get~~
.say for grep {!grep $_%%*,[*]^..^$_},[*]^..get
```

### Explanation:

`[*]` / `[*] ()` multiply all of the elements of an empty list, which results in `1`.

`$_ %% *` is a WhateverCode that returns True if `$_` is divisible by its only argument.

```
.say   # call the .say method on:
for    # every value from:
  grep # only those that match:

    {  # bare block with $_ for parameter
       # ( this block returns True when the value is prime )
      !          # negate: ( True for Nil, False for a number )

      first      # return the first value that is
        $_ %% *, # divisible by one of the following

        # ｢2 .. $_.sqrt.floor｣

        [*]      # 1
        ^..      # Range that ignores the first value
        .sqrt    # the square root of the value we are checking for primality
    },

    # ｢2 .. get｣

    [*]         # 1
    ^..         # Range that ignores the first value
    get         # read a line from $*IN

```

The 48 byte example tests against a Range that is from 1 up to the value to check for primality, excluding both end points.

---

That will run slower as the prime numbers increase, as it checks against all values up to the square root of the number it is testing. It will be more performant if you cache the primes as you go, and only test against them.
( There may be a point where the previous code will be more performant if you run out of memory, and it has to page the cache out to disk )

```
my @p;.say for grep {push @p,$_ if !first $_%%*,@p},([*])^..get

```

---

The normal way to write something that prints out primes would be:

```
.say for grep *.is-prime, 2..get

```

( I would probably use `@*ARGS[0]` instead of `get` so that it gets input from the command line instead of STDIN )
> 1 votes

# Answer
# J, 22 bytes

```
([:>:@I.>:|*:@!)@i.@x:

```

Also uses Wilson's theorem.

## Usage

```
   f =: ([:>:@I.>:|*:@!)@i.@x:
   f 9
2 3 5 7
   f 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

```
> 1 votes

# Answer
# Python 2, 74 bytes

```
lambda n:[-p for p in range(-n,n/-n)if all(p%i for i in range(-~True,-p))]

```
> 1 votes

# Answer
# Python 2, ~~59~~ 58 bytes

```
n=input();k=p=n/n
while k<n:
 p*=k*k;k=-~k
 if p%k:print k

```

Test it on Ideone.
> 0 votes

# Answer
# Python 2, 102 bytes

```
p=input()
q=p/p
print[i if min([i%l for l in range(q+q,i)]+[q])>q-q else None for i in range(q+q,p+q)]

```
> 0 votes

# Answer
# Perl 5, 37 bytes

36, plus 1 for `-nE` instead of `-e`

```
{/^.?$|^(..+?)\1+$/||say;s/.//;redo}

```

Input and output are in unary.
> 0 votes

# Answer
## Mathematica, 43 bytes

```
Select[Range@Input[],Tr@Rest@Divisors@#==#&]

```

Selects from a range of integers between 1 and `Input[]` those, the sum of whose divisors, except the first one (in ascending order) is equal to the number itself.
> 0 votes

# Answer
# Dyalog APL, 14 bytes

```
((⊢~∘.×⍨)≢↓⍳)⎕

```

Fully parenthesised:

```
(⊢ ~ ((∘.×)⍨)) (≢ ↓ ⍳)

```

Every triple of functions applies the right and left monadic functions separately to whatever is outside of the parenthesis, and then the two results become the arguments of the middle function, thus `(f g h)A` is `(f A) g (h A)`. This repeat itself until the following tree structure:

```
    ┌──────┴──────┐
 ┌──┼────┐     ┌──┼──┐
┌┴┐┌┴┐┌──┴──┐ ┌┴┐┌┴┐┌┴┐
│⊢││~││∘.× ⍨│ │≢││↓││⍳│
└─┘└─┘└─────┘ └─┘└─┘└─┘

```

prompt for numeric input

Let's assume the user inputs `6`:

tally the input (giving `1`) and  indices until the input (giving `1 2 3 4 5 6`)

`1 ↓ 1 2 3 4 5 6` drop 1 from the list (giving `2 3 4 5 6`)

pass through (`2 3 4 5 6`) and `∘.×⍨` multiplication table:

```
 4  6  8 10 12
 6  9 12 15 18
 8 12 16 20 24
10 15 20 25 30
12 18 24 30 36

```

`2 3 4 5 6 ~ 4 6 8 10 12 6 9`… "without" (i.e. set difference), yielding `2 3 5`

TryAPL!
> 0 votes

# Answer
# J, 7 bytes

```
~.@q:@!

```

`~.` unique `@` of `q:` prime factors `@` of `!` factorial
> 0 votes

---
Tags: code-golf, restricted-source, primes
---


title: Derivative at the Edge

text:
# Question
Title: Derivative at the Edge
My preferred way to approximate a derivative is the central difference, its more accurate than forward difference or backward difference, and I'm too lazy to go higher-order. But the central difference requires a data point on either side of point you are evaluating. Normally this means you end up not having a derivative at either endpoint. To solve it, I want you to switch to forward and backward difference at the edges:

Specifically, I want you to use a forward difference for the first point, a backward difference for the last point, and a central difference for all the points in the middle. Also, you can assume x values are evenly spaced, and focus only on y. Use these formulas:

Good luck, I'm looking forward to seeing if someone comes up with a simple rule which reproduces all 3 derivatives in the right places!

EX INPUT:

```
0.034  9.62    8.885   3.477   2.38

```

I will use FD, CD, and BD to denote which algorithm to use in which spot, so above 5 points are used to approximate derivatives using

```
FD     CD      CD      CD     BD

```

And then the calculated values would be:

```
9.586  4.4255 -3.0715 -3.2525 -1.097

```

You can assume that there will always be at least 3 input points, and you can calculate using single or double precision.

And as always, shortest answer wins.

# Answer
> 4 votes
# Jelly, ~~13~~ 10 bytes

```
I.ịṚjI+2\H

```

Try it online!

### How it works

```
I.ịṚjI+2\H  Main link. Argument: A (array)

I           Increments; compute the deltas of consecutive values.
            For [a, b, c, d, e], this yields [b-a, c-b, d-c, e-d].
 .ị         At-index 0.5; get the the last and first element.
            This yields [e-d, b-a].
   Ṛ        Reverse the pair.
            This yields [b-a, e-d].
    jI      Join, separating by the increments.
            This yields [b-a, b-a, c-b, d-c, e-d, e-d].
      +2\   Add the values of all overlapping pairs.
            This yields [2(b-a), c-a, d-b, e-c, 2(e-d)].
         H  Halve all resulting numbers.
            This yields [b-a, (c-a)/2, (d-b)/2, (e-c)/2, e-d].

```

# Answer
> 3 votes
# MATL, ~~21~~ 15 bytes

```
2/d1)6Mh8Mt0)h+

```

TryItOnline

Halves the input vector, and takes successive differences, to give `d=[i(2)-i(1) i(3)-i(2) ... i(end)-i(end-1)]/2` and then makes two modified vectors, `[d(1) d]` and `[d d(end)]`, and adds them.

The older version was better (because convolution), but 21 bytes

```
d1j)6M1)6MTT2/H3$Y+bv

```

# Answer
> 3 votes
## Python with NumPy, 29 bytes

```
import numpy;numpy.gradient

```

This happens to be the default behaviour of NumPy's `gradient` function. The bytes were counted according to this consensus.

# Answer
> 1 votes
## 05AB1E, ~~20~~ ~~19~~ ~~17~~ 14 bytes

```
¥Ð¦øO;s¤s0èŠ)˜

```

**Explained**

```
¥Ð              # triplicate deltas of list
                  [9.585999999999999, -0.7349999999999994, -5.4079999999999995, -1.097]
  ¦øO;          # get central difference (fold addition over deltas and divide by 2)
                  [4.4254999999999995, -3.0714999999999995, -3.2524999999999995]
      s¤        # get backwards difference
                  -1.097
        s0è     # get forwards difference
                  9.585999999999999
           Š)˜  # reorder differences, merge to list and flatten
                  [9.585999999999999, 4.4254999999999995, -3.0714999999999995, -3.2524999999999995, -1.097]

```

Try it online

Saved 2 bytes thanks to @Adnan

# Answer
> 1 votes
# Julia, 8 bytes

```
gradient

```

Inspired by @MartinEnder's Python answer. Try it online!

# Answer
> 1 votes
# Pyth, 14 bytes

```
.OM>L2._seB-Vt

```

Try it online: Demonstration

### Explanation:

```
.OM>L2._seB-VtQQ   implicitly add two Qs (input arrays) at the end
           -VtQQ   get all neighbored differences
        seB        get the last element of ^ and append it to ^
      ._           compute all prefixes
   >L2             reduce all prefixes to the last two elements
.OM                compute the average of each ^

```

# Answer
> 1 votes
# J, 21 bytes

```
[:((,{:)+{.,])2-~/\-:

```

Similar to the approach used in @David's solution.

## Usage

```
   f =: [:((,{:)+{.,])2-~/\-:
   f 0.034 9.62 8.885 3.477 2.38
9.586 4.4255 _3.0715 _3.2525 _1.097

```

## Explanation

```
[:((,{:)+{.,])2-~/\-:  Input: list A
                   -:  Halve each value in A
              2   \    Select each overlapping sublist of size 2 in A
               -~/     Reduce it using subtraction to get the difference
[:(          )         Operate on the list of differences, call it D
            ]          Identity function, returns D
         {.            Get the head of D
           ,           Join them to get [head(D), D]
   ( {:)               Get the tail of D
    ,                  Join them to get [D, tail(D)]
        +              Add them together elementwise to get the derivatives and return

```

# Answer
> 0 votes
# Pyth - 29 bytes

Stupid simple approach.

```
s[_-F<Q2mc-@Qhd@Qtd2tUtQ_-F>2

```

Try it online here.

# Answer
> 0 votes
## JavaScript (ES6), 62 bytes

```
a=>a.map((_,i)=>i&&i--<a.length-2?(a[i+2]-a[i])/2:a[i+1]-a[i])

```

# Answer
> 0 votes
# Pyth, ~~27~~ ~~24~~ ~~23~~ 21 bytes

```
~~.bcF_-VNYK++]hJ,VUQQJ]eJttK~~
~~.bcF-VYN+]hJ,VQUQJ+tJ]eJ~~
~~++hJ-V+tQeQ+hQQcR2PtJeJ~~
~~*V++1*].5ttlQ1-V+tQeQ+h~~
*V++1m.5ttQ1-V+tQeQ+h

```

Try it online!

---
Tags: code-golf, math
---