# Question
Title: There's an echo in my array... echo in my array... my array
Help! I seem to have an annoying echo in some of my arrays, and I'd like to get rid of it. When this occurs, the original array repeats itself somewhere in the middle causing the values to be added to each other.

For example, the array `[ 422, 375, 527, 375, 859, 451, 754, 451 ]` contains an echo of itself like so:

```
[ 422, 375, 527, 375, 859, 451, 754, 451 ] <-- array with echo (input)

[ 422, 375, 105,   0, 754, 451           ] <-- original array (output)
[           422, 375, 105,   0, 754, 451 ] <-- echo of original array

```

Example 2:

```
[ 321, 526, 1072, 899, 6563, 798, 7038, 3302, 3032, 3478, 1806, 601 ] <-- input

[ 321, 526,  751, 373, 5812, 425, 1226, 2877, 1806,  601            ] <-- output
[            321, 526,  751, 373, 5812,  425, 1226, 2877, 1806, 601 ]

```

**It's also possible that there is no echo in the array, in which case return the original array:**

Example 3:

```
[ 623, 533, 494, 382 ] <-- input
[ 623, 533, 494, 382 ] <-- output

```

## Challenge:

Given an array that may contain an echo, remove it and return the array without an echo.

### Input:

* An array, list, delimited string, punched cards or your platform-suitable equivalent, containing three or more integers, in the range of \\$0\leq n\lt10000\\$ with at least one element \\$\gt 0\\$.
* The echo cannot begin at the first or after the last element.
* The echo will only occur once or not at all within the input.

### Output:

* An array, list, etc of integers \\$0\leq n\lt10000\\$, with the echo removed.
* If there is no echo, return the original array.

### Rules and scoring:

### Test cases:

**With echo:**

```
[ 422, 375, 527, 375, 859, 451, 754, 451 ]
[ 422, 375, 105, 0, 754, 451 ]

[ 321, 526, 1072, 899, 6563, 798, 7038, 3302, 3032, 3478, 1806, 601 ]
[ 321, 526, 751, 373, 5812, 425, 1226, 2877, 1806, 601 ]

[ 4330, 3748, 363, 135, 2758, 3299, 1674, 1336, 4834, 2486, 4087, 1099, 4098, 4942, 2159, 460, 4400, 4106, 1216, 3257, 1638, 2848, 3616, 3554, 1605, 490, 1308, 2773, 3322, 3284, 4037, 7109, 4171, 5349, 2675, 3056, 4702, 4229, 1726, 5423, 6039, 8076, 6047, 7088, 9437, 4894, 1946, 7501, 5331, 3625, 5810, 6289, 2858, 6610, 4063, 5565, 2200, 3493, 4573, 4906, 3585, 4147, 3748, 3488, 5625, 6173, 3842, 5671, 2555, 390, 589, 3553, 3989, 4948, 2990, 4495, 2735, 1486, 3101, 1225, 2409, 2553, 4651, 10, 2994, 509, 3960, 1710, 2185, 1800, 1584, 301, 110, 969, 3065, 639, 3633, 3544, 4268 ]
[ 4330, 3748, 363, 135, 2758, 3299, 1674, 1336, 4834, 2486, 4087, 1099, 4098, 4942, 2159, 460, 4400, 4106, 1216, 3257, 1638, 2848, 3616, 3554, 1605, 490, 1308, 2773, 3322, 3284, 4037, 2779, 423, 4986, 2540, 298, 1403, 2555, 390, 589, 3553, 3989, 4948, 2990, 4495, 2735, 1486, 3101, 1225, 2409, 2553, 4651, 10, 2994, 509, 3960, 1710, 2185, 1800, 1584, 301, 110, 969, 3065, 639, 3633, 3544, 4268 ]

[ 24, 12, 52, 125, 154, 3, 567, 198, 49, 382, 53, 911, 166, 18, 635, 213, 113, 718, 56, 811, 67, 94, 80, 241, 343, 548, 68, 481, 96, 79, 12, 226, 255, 200, 13, 456, 41 ]
[ 24, 12, 52, 125, 154, 3, 567, 198, 25, 370, 1, 786, 12, 15, 68, 15, 88, 348, 55, 25, 55, 79, 12, 226, 255, 200, 13, 456, 41 ]

[ 1, 3, 2 ]
[ 1, 2 ]

[ 0, 1, 3, 2, 0 ]
[ 0, 1, 2, 0 ]

```

**Without echo:**

```
[ 623, 533, 494, 382 ]
[ 623, 533, 494, 382 ]

[ 1141, 1198, 3106, 538, 3442, 4597, 4380, 3653, 1370, 3987, 1964, 4615, 1844, 5035, 2463, 6345, 4964, 4111, 5192, 8555, 5331, 3331, 4875, 6586, 5728, 4532, 5972, 2305, 3491, 6317, 2256, 2415, 5788, 4873, 6480, 2080, 5319, 4551, 6527, 5267, 4315, 2178, 2615, 5735, 5950, 6220, 7114, 6259, 5000, 4183, 6822, 6927, 7150, 8003, 5603, 3154, 8231, 5005, 5743, 6779, 4530, 4029, 5336, 6105, 4777, 6183, 6838, 5725, 6819, 8584, 3142, 3840, 3291, 4284, 2933, 4859, 2906, 5176, 2853, 2110, 2048, 4389, 4501, 2267, 2704, 431, 1495, 2712, 3008, 187, 3487, 630 ]
[ 1141, 1198, 3106, 538, 3442, 4597, 4380, 3653, 1370, 3987, 1964, 4615, 1844, 5035, 2463, 6345, 4964, 4111, 5192, 8555, 5331, 3331, 4875, 6586, 5728, 4532, 5972, 2305, 3491, 6317, 2256, 2415, 5788, 4873, 6480, 2080, 5319, 4551, 6527, 5267, 4315, 2178, 2615, 5735, 5950, 6220, 7114, 6259, 5000, 4183, 6822, 6927, 7150, 8003, 5603, 3154, 8231, 5005, 5743, 6779, 4530, 4029, 5336, 6105, 4777, 6183, 6838, 5725, 6819, 8584, 3142, 3840, 3291, 4284, 2933, 4859, 2906, 5176, 2853, 2110, 2048, 4389, 4501, 2267, 2704, 431, 1495, 2712, 3008, 187, 3487, 630 ]

[ 4791, 1647, 480, 3994, 1507, 99, 61, 3245, 2932, 8358, 6618, 1083, 5391, 3498, 4865, 1441, 3729, 5322, 5371, 6271, 2392, 1649, 5553, 9126, 3945, 2179, 3672, 2201, 4433, 5473, 4924, 6585, 6407, 3862, 6505, 1530, 5293, 4792, 6419, 6739, 3258, 3839, 3891, 7599, 2576, 5969, 5659, 6077, 5189, 1325, 4490, 5694, 6567, 6367, 5724, 5756, 6450, 5863, 4360, 2697, 3100, 3779, 4040, 4653, 1755, 3109, 2741, 3269 ]
[ 4791, 1647, 480, 3994, 1507, 99, 61, 3245, 2932, 8358, 6618, 1083, 5391, 3498, 4865, 1441, 3729, 5322, 5371, 6271, 2392, 1649, 5553, 9126, 3945, 2179, 3672, 2201, 4433, 5473, 4924, 6585, 6407, 3862, 6505, 1530, 5293, 4792, 6419, 6739, 3258, 3839, 3891, 7599, 2576, 5969, 5659, 6077, 5189, 1325, 4490, 5694, 6567, 6367, 5724, 5756, 6450, 5863, 4360, 2697, 3100, 3779, 4040, 4653, 1755, 3109, 2741, 3269 ]

[ 235, 121, 52, 1249, 154, 26, 5672, 1975, 482, 3817, 532, 9104, 1661, 171, 6347, 2124, 1122, 7175, 558, 8101, 667, 934, 798, 2404, 3424, 5479, 672, 4808, 956, 789, 123, 2255, 2549, 200, 126, 4562, 41 ]
[ 235, 121, 52, 1249, 154, 26, 5672, 1975, 482, 3817, 532, 9104, 1661, 171, 6347, 2124, 1122, 7175, 558, 8101, 667, 934, 798, 2404, 3424, 5479, 672, 4808, 956, 789, 123, 2255, 2549, 200, 126, 4562, 41 ]

[ 1, 1, 1, 1, 1 ]
[ 1, 1, 1, 1, 1 ]

```

# Answer
# MATL, 16 bytes

```
t"GX@WQB&Y-~?w]x

```

Try it online! Or verify all test cases.

### Explanation

Polynomial division for the win!

```
t      % Implicit input. Duplicate
"      % For each (do the following as many times as input length)
  G    %   Push input again. This will be the output if no solution exists
  X@   %   Push current iteration index, k
  WQB  %   2 raised to that, add 1, convert to binary. Gives [1 0 ... 0 1] (k-1 zeros)
  &Y-  %   Two-output polynomial division (deconvolution). Gives quotient and remainder
  ~    %   Logical negate: transforms zeros into 1, nonzeros into 0
  ?    %   If all values are nonzero (i.e. if remainder was all zeros): solution found
    w  %      Swap. This moves the copy of the input to top (to be deleted)
  ]    %   End
  x    %   Delete. This deletes the quotient if it was not a solution, or else deletes
       %   the copy of the input
       % End (implicit). Since it is guaranteed that at most one solution exists, at this
       % point the stack contains either the solution or the input
       % Implicit display

```
> 8 votes

# Answer
# Haskell, 167 bytes

First it is important to notice that if there is an echo present, then the input array is a convolution of another array with some array of the form `[1,1],[1,0,1],[1,0,0,1],...`.

This means we just have to check this for all these arrays. But discrete convolution/deconvolution is the same as polynomial multiplication/long division, so this is just an implementation using polynomials, each time returning the quotient if possible.

One trick that shortened the whole thing a little bit was in addition to the arrays above also checking for `[1]` as a base case, because if no other array works, the deconvolution with `[1]` will work and will return the original polynomial.

```
import Math.Polynomial
import Data.Ratio
p=poly LE
c z=last[polyCoeffs LE q|k<-zipWith const[p(take k(1:repeat 0)++[1])|k<-[0..]]z,(q,r)<-[quotRemPoly(p z)k],r==zero]

```

Try it online!
> 7 votes

# Answer
# JavaScript, ~~211~~ ~~171~~ 145 bytes

```
s=>{for(n=x=0,y=s.length;++x<y/2&!n;)for(n=s.slice(i=0,x);i+x<y-x&&n;)n=(n[i+x]=s[i+x]-n[i++])<0?0:n;return n&&n.slice(1-x)+''==s.slice(1-x)?n:s}

```

Try it online

40 bytes from Kevin Cruijssen

Another 26 bytes from Arnauld

My first code golf answer, invalidates potential offsets, and returns either the original or the new array dependent on what it finds. If anyone knows how to make it shorter pls let me know, seems like a fun game.
> 4 votes

# Answer
## Haskell, ~~112~~ ~~111~~ 110 bytes

```
l=length
(!)=splitAt
f a=last$a:[x|i<-[1..l a],let (h,t)=i!a;o=h++zipWith(-)t o;(x,y)=l t!o,all(>=0)o,sum y<1]

```

Try it online!

```
f a=
      i<-[1..l a]                -- for all indices 'i' of the input array 'a'
      (h,t)=i!a                  -- split 'a' at 'i' into 'h' and 't'
                                 -- e.g. a: [1,2,3,4], i: 1 -> h: [1], t:[2,3,4]
      o=                         -- calculate the original array by
        h++                      --   prepended 'h' to
        zipWith(-)t o            --   the (element-wise) difference of
                                 --   't' and itself
      (x,y)=l t!o                -- split 'o' at position <length of t>
                                 --
                                 -- example:
                                 --      a: [0,1,3,2,0]
                                 --      h: [0]
                                 --      t: [1,3,2,0]
                                 --   now
                                 --      o: [0,1,2,0,0]
                                 --      x: [0,1,2,0]
                                 --      y: [0]
                                 --
    ,                            -- 'o' is valid, if
     all(>=0)o                   --   all elements of 'o' are not negative
    ,sum y<1                     --   and 'y' is all zeros
  [x|         ]                  -- keep 'x' (a valid echo array) if 'o' is valid

 last $ a :[  ]                  -- if there's no echo, the list of 'x's is empty
                                 -- and 'a' is picked, else the last of the 'x's

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~131~~ ~~129~~ ~~120~~ ~~119~~ ~~102~~ ~~98~~ ~~97~~ ~~96~~ 95 bytes

```
(w=#;Do[(w=v/.#)&/@Thread[#==PadLeft[v=Array[x,L-d],L]+v~PadRight~L]~Solve~v,{d,L=Tr[1^#]}];w)&

```

Try it online!

−1 byte thanks to attinat: we can write `L=Tr[1^#]` instead of `L=Length@#` when the argument is a list of numbers.

**Code explanation:** Iterate through the shrinkage `d` (difference between input and output lengths). For each output list length, construct a list of unknowns `v={x[1],x[2],...,x[L-d]}` and add it to itself left-padded and right-padded to length `L` (`PadLeft[v,L]+PadRight[v,L]`), then set this sum equal to the input list and solve for the unknowns `x[1]...x[L-d]`. Pick the shortest solution, which is the last one generated: just keep overwriting the variable `w` every time a solution is found.

Un-golfed version:

```
F = Function[A,                                  (* A is the input list *)
  Module[{L = Length[A],                         (* length of A *)
          v,                                     (* list of unknowns *)
          x,                                     (* unknowns in v *)
          w = A},                                (* variable for solution, defaults to A *)
    Do[                                          (* loop over shrinkage: d = Length[A]-Length[output] *)
      v = Array[x, L - d];                       (* list of unknowns to be determined *)
      (w = v /. #) & /@                          (* overwrite w with every... *)
        Solve[                                   (* ...solution of... *)
          Thread[PadLeft[v,L]+PadRight[v,L]==A], (* ...v added to itself, left-padded and right-padded, equals A *)
          v],                                    (* solve for elements of v *)
    {d, L}];                                     (* loop for shrinkage from 1 to L (the last case d=L is trivial) *)
    w]];                                         (* return the last solution found *)

```
> 3 votes

# Answer
# Python 2, ~~113~~ ~~123~~ ~~128~~ ~~127~~ ~~123~~ 122 bytes

```
def f(a,i=1):
 e=a[:i]
 for v in a[i:-i]:e+=v-e[-i],
 return i<=len(a)/2and(min(e)>=0<e[-i:]==a[-i:]and e or f(a,i+1))or a

```

Try it online!

1 byte thx to TFeld; and 1 byte thx to Sebastian Kreft.

On each call to `f`, we construct a potential echo of length `len(a)-i`. The first part is just the first `i` bytes of a; the remainder is calculated so that the 'echoed sum' will be correct for the 'overlapped' section of the echo sum (i.e., the echo-sum is correct up to `a[:-i]`).

Then the very short-cutted comparison, un-golfed, gives:

```
if i>=len(a)/2+1:
    return a # because it can't be that short, so there is no echo
else:
    if min(e)>=0                       # all elements are non-negative
                 and e[-i:]==a[-i:]:   # and the tails are the same
        return e                       # it's a match!
    else:
        return f(a,i+1)                # recurse

```
> 2 votes

# Answer
# Jelly, ~~25~~ 24 bytes

```
ðsạ\FḣL_¥,+¥Ż⁹¡$µⱮLṪ⁼¥Ƈȯ

```

Try it online!

A monadic link that takes and returns a list of integers. Technically, the successful results are nested in two further lists, but when run as a full program the implicit output to stdout ignores the redundant lists.
> 2 votes

# Answer
# PHP, 124 bytes

```
function($a){while(!$z&&++$y<$c=count($b=$a))for($x=0;$x<$c&$z=0<=$b[$x+$y]-=$b[$x++];);return array_slice($b,0,$c-$y)?:$a;}

```

Try it online!

**Explanation:**

Create a copy of the input array and loop through each possible offset of the echo. For each column, subtract the value in the offset position from the corresponding value in the original position to determine the value necessary to add up to the input. If it is valid (\\$\gt 0\\$), replace the contents of that column with that value. Continue to the end and if no values are invalid, it is a correct answer.

```
function( $a ) {
  // iterate through all possible offsets of echo
  while( ! $b && ++$y < $c = count( $b = $a ) ) {
    // create a copy of input array, iterate through all elements
    for( $x = 0; $b && $x < $c; ) {
      // if difference between the elements in the offset copy of
      // the array is positive, subtract the value in the input array
      // from the offset array in the same column
      if ( ( $b[ $x+$y ] -= $b[ $x++ ] ) < 0 ) {
        // result is not valid, erase array and break out of loop
        $b = 0;
      }
    }
  }
  // truncate output array to correct size. if still contains values,
  // it is a valid result. otherwise return the original array
  return array_slice( $b, 0, $c-$y ) ?: $a;
}

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), 93 bytes

```
(b=#;Do[a=#;Do[a[[i+j]]-=a[[j]],{j,2k}];a/.{__?(#>=0&),0}:>(b=a~Drop~-i),{i,k=Tr[1^#]/2}];b)&

```

Try it online!

Returns the shortest echo present in the list.
> 2 votes

# Answer
# Python 3, 111 bytes

```
def f(r,l=1):o=r[:l];o+=(v-o[-l]for v in r[l:]);return l<len(r)and(min(o)<any(o[-l:])and f(r,l+1)or o[:-l])or r

```

Try it online!

The solution takes some ideas from @Chas Brown's solution such as the recursive structure and the construction of the output array. Meanwhile, it also makes some changes in the judging criteria as well as putting the for loop into a generator expression to allow a single-line solution. The ungolfed version is shown in the following. Here, the array `out` is computed all the way to the end of the input array and then we check whether the last `l` elements of it are all zero. If so, the first `len(arr)-l` elements are returned as the answer if all of them are non-negative.

# Ungolfed, non-recursive version

```
def remove_echo(arr):
    l = 1
    while l < len(arr):
        out = arr[:l]
        out += (v - out[-l] for v in arr[l:])
        if min(out) >= 0 and out[-l:] == [0] * l:
            return out[:-l]
        l += 1
    return arr

```

Try it online!
> 2 votes

# Answer
# Charcoal, 62 bytes

```
≔⁰ζＦ⊘Ｌθ«≔Ｅ⊕ι⁰ηＦＬθ§≔ηκ⁻§θκ§ηκ¿⬤η¬κ≔⊕ιζ»Ｆ⁻Ｌθζ⊞υ⁻§θι∧ζ∧¬‹ιζ§υ±ζＩυ

```

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

```
≔⁰ζ

```

Assume there's no echo.

```
Ｆ⊘Ｌθ«

```

Try all possible start points of echo. Note: I may have misread the question and might not be trying enough sizes of echo, in which case the  would not be necessary.

```
≔Ｅ⊕ι⁰η

```

Start with an array of zeros the same size as the start point of the echo.

```
ＦＬθ§≔ηκ⁻§θκ§ηκ

```

For each element in the original array, subtract the element in the echo array cyclically from it. Each element in the echo array thus builds up the alternating sum of the elements that distance apart.

```
¿⬤η¬κ≔⊕ιζ»

```

If all of the alternating sums are zero then save this as a possible start point. (So if there is more than one possibility then the largest possible start point is used.)

```
Ｆ⁻Ｌθζ⊞υ⁻§θι∧ζ∧¬‹ιζ§υ±ζ

```

Build up the echoing array by subtracting elements after the start point from the appropriate previously calculated element.

```
Ｉυ

```

Cast to string for implicit output on separate lines.
> 1 votes

---
Tags: code-golf, array, algorithm
---


title: Road painting ahead

text:
# Question
Title: Road painting ahead
Given two parameters *lane pattern* and *road length*, print an ASCII representation of the lane markings for Roads and Traffic Service to paint the roads.

## Example input/output

**Input:** `BTHMLRPHU`, 21

I don't care if you take two parameters or concatenate the number onto the end of the string, it's unambiguous.

Input may be taken from STDIN, as a function argument, environment variables, whatever makes sense in your language.

**Output:**

```
!   |      x      ##      |      |      x      x      !
! B |  /\  x HOV3 ##  <-  |  ->  |  ^^  x HOV3 x      !
! B |  \/  x HOV3 ##   |  |  |   |  ^^  x HOV3 x      !
!   |      x      ##      |      |      x      x      !
!   |      x      ##      |      |      x      x      !
!   |      |      ##      |      |      |      |      !
!   |      |      ##      |      |      |      |      !
!   |      |      ##      |      |      |      |      !
! B |  /\  | HOV3 ##  <-  |  ->  |  ^^  | HOV3 |      !
! B |  \/  | HOV3 ##   |  |  |   |  ^^  | HOV3 |      !
!   |      x      ##      |      |      x      x      !
! B |  /\  x HOV3 ##  <-  |  ->  |  ^^  x HOV3 x      !
! B |  \/  x HOV3 ##   |  |  |   |  ^^  x HOV3 x      !
!   |      x      ##      |      |      x      x      !
!   |      x      ##      |      |      x      x      !
!   |      |      ##      |      |      |      |      !
!   |      |      ##      |      |      |      |      !
!   |      |      ##      |      |      |      |      !
! B |  /\  | HOV3 ##  <-  |  ->  |  ^^  | HOV3 |      !
! B |  \/  | HOV3 ##   |  |  |   |  ^^  | HOV3 |      !
!   |      x      ##      |      |      x      x      !

```

Each character denotes 0.5 metres in width and one kilometre in length.

# Specification

## Lane markings

For every 10 km stretch of road, markings are painted at kilometres 2, 3, 9 and 10 (from the "top" of the output). Markings are centred in the lane. With the exception of the bike lane and median, all lanes are 3 metres (6 characters) wide.

ASCII diamond and arrow characters are *not* permitted in lieu of the markings as indicated in the example output.

* `B`: Bike lane. `B` marking. 1.5 metres (3 characters) wide.
* `T`: Transit. Diamond marking
* `H`: High-occupancy vehicle lane. `HOV3` marking
* `L` and `R`: Turning lane. Arrow marking
* `P`: Passing lane. Caret markings
* `U`: Unrestricted lane. No markings

## Separators (in order of precedence)

* Median: `##` (denoted by `M` in the input string, replaces any other separator including ditch)
* Ditch (extreme left and extreme right): `!` Exclamation mark
* HOV lanes alternate between `x` and `|` every 5 km
* Normal: `|`

## Constraints

Your function or program must:

* Print to STDOUT (this means equivalents of `System.out.print` for Java, `console.log` for JavaScript, etc.)
* Be able to print 1 - 9 lanes with 0 - 10 medians
* Be able to print up to 50 km of roadway (50 lines of output)
* Not use any standard loopholes
* Trailing white space is not acceptable with the exception of an optional `\n` at the end of the output

Largest possible output: 3700 bytes (74 characters * 50 lines).

Smallest possible output: 5 bytes (with input `B`, 1)

### Assumptions

* No adjacent medians (substring `MM` will not occur)
* The second line of markings might be cut off (for example if the length is 9 or 12 km)
* Lanes may not logically make sense (any order is possible, for example a right turn lane on the left of the road)

This is , so shortest code (in bytes) wins!

# Answer
## Ruby, 245

Print the lane divides if relevant, then print the lane.

I don't expect to win.

```
->(n,i){i.times{|d,t|*e=''
g=e+%w{HOV3 ^^ B}
n.chars{|c|$><<(c==?M?'##':!t ??!:(t+c)[?H]&&d%10<5??x:?|)if(M=t!=?M)
$><<((e+[(%w{/\\ <- ->}+g)[v='TLRUHPB'.index(c)],(%w{\\/ \ | |\ }+g)[v]]+e*4)*2)[d%10].center(v>5?3:6)if(t=c)!=?M}
puts M ? e:?!}}

```

### Changelog

**245** choke stderr and split arrays effectively.

**263** better way to index array

**268** just print each line, don't calculate a canonical version.

**330** initial commit
> 4 votes

# Answer
## JavaScript (ES6), 316 bytes

```
f=(x,n)=>{for(i=0;n>i++;){b=!(r=i%10)|r==3;y=[...`! ${[...x].join` | `} !`[o='replace'](/[\W] ?M [\W]?/g,'##')].map(c=>~(q='LPRTU'.indexOf(c))?` ${'<- |^^^^->| /\\\\/    '.substr(4*q+2*b,2)} `:c=='H'?'HOV3':c).join``;y=r&&r<6?y[o](/\| H/g,'x H')[o](/3 \|/g,'3 x'):y;console.log(b|r==2|r==9?y:y[o](/[^!\|x#]/g,' '))}}

```

### Demo

It should work in Firefox and Edge at time of writing, Chrome/Opera require experimental features to be enabled.

```
console.log = x => O.innerHTML += x + '\n';

f = (x, n) => {
  for (i = 0; n > i++;) {
    b = !(r = i % 10) | r == 3;
    y = [...
      `! ${[...x].join` | `} !` [o = 'replace'](/[\W] ?M [\W]?/g, '##')
    ].map(c => ~(q = 'LPRTU'.indexOf(c)) ? ` ${'<- |^^^^->| /\\\\/    '.substr(4*q+2*b,2)} ` : c == 'H' ? 'HOV3' : c).join ``;
    y = r && r < 6 ? y[o](/\| H/g, 'x H')[o](/3 \|/g, '3 x') : y;
    console.log(b | r == 2 | r == 9 ? y : y[o](/[^!\|x#]/g, ' '))
  }
}

// Snippet stuff
var demo = () => {
  O.innerHTML = '';
  document.forms[0].checkValidity() && f(document.getElementById('P').value, document.getElementById('N').valueAsNumber);
};

document.getElementById('P').addEventListener('change', demo);
document.getElementById('N').addEventListener('change', demo);

demo();
```

```
<form action='#'>
  <p>
    <label>Lane pattern:
      <input type=text pattern=^M?([BHLPRTU]M?)+$ maxlength=19 required id=P value=MLTPUMHUTBR>
    </label>
  </p>
  <p>
    <label>Kilometres:
      <input type=number id=N min=1 value=21 max=50 step=1 required>
    </label>
  </p>
  <pre><output id=O></output></pre>
</form>
```
> 2 votes

# Answer
# 05AB1E, ~~175~~ ~~174~~ 175 bytes

```
ðTиDU'|TиX'BŽ5ES©ǝX„\/TbSDVè®ǝ€ºX4×"HOV3"®ǝX'<18SǝX„|-Yè®ǝøJDí'<'>:X'^®ǝ2×'#Tи2×'x5и'|5и«'!Tи)I.•o¤[‹‡•uŽDýSтì€ûŽe1ª904ûª8ª₄Â«ª‡•δ~¬]•2ôDí«Ž
ÿT∍S:ð.ø8ðìÂ‚8:1ðìÂ‚ð:SðT:èεI∍}øJ»

```

Pretty bad approach, but it works and was fun to make. Can definitely be golfed some more, though.

+1 byte as bug-fix for two adjacent `HH` lanes.

Try it online.

**Explanation:**

Step 1: Create all possible lanes with size 10:

```
ðTи               # Push a space character, repeated 10 times as list
   DU             # And store a copy in variable `X`
'|Tи             '# Push "|", repeated 10 times as list
X                 # Push the list of spaces of variable `X`
 'B              '# Push a "B"
   Ž5E            # Push compressed integer 1289
      S           # Converted to a list of digits: [1,2,8,9]
       ©          # Store it in variable `®` (without popping)
        ǝ         # Replace the spaces in the pushed `X` with the "B" at these (0-based)
                  # indices
X                 # Push `X` again
 „\/              # Push string "\/"
    TbS           # Push 10, converted to binary, as list: [1,0,1,0]
       DV         # Store a copy in variable `Y`
         è        # Index each into this string: ["/","\","/","\"]
          ®       # Push list `®` again ([1,2,8,9])
           ǝ      # And replace the spaces with these characters
            €º    # And then mirror each line (" "→"  "; "/"→"/\"; "\"→"\/")
X                 # Push `X` again
 4×               # Extend each space to four spaces
   "HOV3"         # Push string "HOV3"
         ®ǝ       # And replace the spaces with this string at the indices of `®` again
X                 # Push `X` again
 '<              '# Push string "<"
   18S            # Push 18 as list: [1,8]
      ǝ           # Replace the spaces with "<" at those indices
       X          # Push `X` yet again
        „-|       # Push string "-|"
           Yè     # Use list `Y` ([1,0,1,0]) to index into this string: ["-","|","-","|"]
             ®ǝ   # And replace the spaces at the indices of `®` again
               ø  # Then zip-pair the two lists together
                J # And join each pair of characters to a string
Dí                # Create a copy and reverse each string
  '<'>:           # And replace all "<" with ">"
X'^®ǝ            '# Push `X` with the spaces at indices `®` replaced with "^"
     2×           # Extend each character to size 2
'#Tи             '# Push "#", repeated 10 times as list
    2×            # And extend each character to size 2
'x5и             '# Push "x" repeated 5 times as list
    '|5и         '# Push "|" repeated 5 times as list
        «         # And merge the lists together
'!Tи             '# Push "!", repeated 10 times as list
)                 # And finally wrap all lists of the stack into one big list of lanes

```

Step 2: Convert the input-string to indices (which we're going to use to index into the list we created in step 1):

```
I                 # Push the input-string
 .•o¤[‹‡•         # Push compressed string "tlrpbhmu"
         u        # And uppercase it
ŽDý               # Push compressed integer 3567
   S              # Converted to a list of digits: [3,5,6,7]
    тì            # Prepend each with "100": ["1003","1005","1006","1007"]
      €û          # And palindromize each: ["1003001","1005001","1006001","1007001"]
Že1               # Push compressed integer 10201
   ª              # And append it to the list
904ûª             # Push 904 palindromized to "90409", and also append it to the list
8ª                # Append 8 to the list
₄Â                # Push 1000, and bifurcate it (short for Duplicate & Reverse copy)
  «               # Merge them together: "10000001"
   ª              # And also append it to the list
‡                 # Now transliterate all uppercase characters in the input to these numbers
•δ~¬]•            # Push compressed integer 1119188999
      2ô          # Split into parts of size 2: [11,19,18,89,99]
        Dí        # Create a copy, and reverse each item: [11,91,81,98,99]
          «       # And merge the lists together: [11,19,18,89,99,11,91,81,98,99]
Ž\nÿ              # Push compressed integer 19889
    T∍            # Extended to size 10: 1988919889
      S           # As a list of digits: [1,9,8,8,9,1,9,8,8,9]
:                 # Replace all [11,19,18,89,99,11,91,81,98,99] with [1,9,8,8,9,1,9,8,8,9]
                  # in the converted string
ð.ø               # Surround the string with spaces
8ðì               # Push 8 with a prepended space: " 8"
   Â‚             # Bifurcate and pair: [" 8","8 "]
     8:           # And replace all those for 8 in the string
1ðìÂ‚ð:           # Do the same for [" 1","1 "] → " "
S                 # Convert the string to a list of characters (digits and space)
 ðT:              # Replace the spaces for 10

```

Step 3: we use those indices to index into the list of lanes. And then we convert those list of lanes to the correct output, including extending/shortening them to the size of the integer-input:

```
è                 # Index the indices in the integer-list into the lanes-list
 ε                # Map over each lane
  I               #  Push the second integer-input
   ∍              #  Extend/shorten each 10-sized lane to this input-size
 }ø               # After the map: zip/transpose; swapping rows/columns
   J              # Join inner list together to a single string
    »             # And then join each string by newlines
                  # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (sections *How to compress strings not part of the dictionary?* and *How to compress large integers?*) to understand why `Ž5E` is `1289`; `.•o¤[‹‡•` is `"tlrpbhmu"`; `ŽDý` is `10201`; `•δ~¬]•` is `1119188999`; `Ž\nÿ` is `19889`.
> 1 votes

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


title: Count the number of shortest paths to n

text:
# Question
Title: Count the number of shortest paths to n
This code challenge will have you compute the number of ways to reach \\$n\\$ starting from \\$2\\$ using maps of the form \\$x \mapsto x + x^j\\$ (with \\$j\\$ a non-negative integer), and doing so in the minimum number of steps.

(Note, this is related to OEIS sequence A307092.)

## Example

So for example, \\$f(13) = 2\\$ because three maps are required, and there are two distinct sequences of three maps that will send \\$2\\$ to \\$13\\$:

$$\begin{array}{c} x \mapsto x + x^0 \\ x \mapsto x + x^2 \\ x \mapsto x + x^0\end{array} \qquad \textrm{or} \qquad \begin{array}{c}x \mapsto x + x^2 \\ x \mapsto x + x^1 \\ x \mapsto x + x^0\end{array}$$

Resulting in \\$2 \to 3 \to 12 \to 13\\$ or \\$2 \to 6 \to 12 \to 13\\$.

## Example values

```
f(2)   = 1 (via [])
f(3)   = 1 (via [0])
f(4)   = 1 (via [1])
f(5)   = 1 (via [1,0])
f(12)  = 2 (via [0,2] or [2,1])
f(13)  = 2 (via [0,2,0] or [2,1,0], shown above)
f(19)  = 1 (via [4,0])
f(20)  = 2 (via [1,2] or [3,1])
f(226) = 3 (via [2,0,2,1,0,1], [3,2,0,0,0,1], or [2,3,0,0,0,0])
f(372) = 4 (via [3,0,1,0,1,1,0,1,1], [1,1,0,2,0,0,0,1,1], [0,2,0,2,0,0,0,0,1], or [2,1,0,2,0,0,0,0,1])

```

# Challenge

The challenge is to produce a program which takes an integer \\$n \ge 2\\$ as an input, and outputs the number of distinct paths from \\$2\\$ to \\$n\\$ via a minimal number of maps of the form \\$x \mapsto x + x^j\\$.

This is , so fewest bytes wins.

# Answer
> 2 votes
# Jelly, 16 bytes

```
2+*¥þ³Ḷ¤F$n³Ạ$¿ċ

```

Try it online!

A full program taking as its argument \\$n\\$ and returning the number of ways to reach \\$n\\$ using the minimal path length. Inefficient for larger \\$n\\$.

# Answer
> 5 votes
# JavaScript (ES6),  ~~111 ... 84~~  80 bytes

Returns true rather than \\$1\\$ for \\$n=2\\$.

```
f=(n,j)=>(g=(i,x,e=1)=>i?e>n?g(i-1,x):g(i-1,x+e)+g(i,x,e*x):x==n)(j,2)||f(n,-~j)

```

Try it online!

### Commented

```
f = (                     // f is the main recursive function taking:
  n,                      //   n = input
  j                       //   j = maximum number of steps
) => (                    //
  g = (                   // g is another recursive function taking:
    i,                    //   i = number of remaining steps
    x,                    //   x = current sum
    e = 1                 //   e = current exponentiated part
  ) =>                    //
    i ?                   // if there's still at least one step to go:
      e > n ?             //   if e is greater than n:
                          //     add the result of a recursive call with:
        g(i - 1, x)       //       i - 1, x unchanged and e = 1
      :                   //   else:
                          //     add the sum of recursive calls with:
        g(i - 1, x + e) + //       i - 1, x + e and e = 1
        g(i, x, e * x)    //       i unchanged, x unchanged and e = e * x
    :                     // else:
      x == n              //   stop recursion; return 1 if x = n
)(j, 2)                   // initial call to g with i = j and x = 2
|| f(n, -~j)              // if it fails, try again with j + 1

```

# Answer
> 4 votes
# Haskell, ~~78~~ 75 bytes

This implementation uses a breath-first-search in the "tree" of iteratively all necessary mappings `x -> x + x^j`.

```
j#x=x+x^j
f n=[sum[1|x<-l,x==n]|l<-iterate((#)<$>[0..n]<*>)[2],n`elem`l]!!0

```

Try it online!

### Explanation

```
-- computes the mapping x -> x + x^j
j#x=x+x^j
--iteratively apply this function for all exponents [0,1,...,n] (for all previous values, starting with the only value [2])
                            iterate((#)<$>[0..n]<*>)[2]
-- find each iteration where our target number occurs
    [                   |l<-...........................,n`elem`l]
-- find how many times it occurs
     sum   [1|x<-l,x==n]
-- pick the first entry
f n=.............................................................!!0

```

# Answer
> 3 votes
# 05AB1E, 17 bytes

```
2¸[˜DIå#εIÝmy+]I¢

```

Try it online!

# Answer
> 3 votes
# Python 2, 72 bytes

```
f=lambda n,l=[2]:l.count(n)or f(n,[x+x**j for x in l for j in range(n)])

```

Try it online!

# Answer
> 1 votes
# Perl 5 (`-lp`), 79 bytes

```
$e=$_;@,=(2);@,=map{$x=$_;map$x+$x**$_,0..log($e)/log$x}@,until$_=grep$_==$e,@,

```

TIO

# Answer
> 1 votes
## CJam (27 bytes)

```
qi2a{{_W$,f#f+~2}%_W$&!}ge=

```

Online demo

Warning: this gets very memory-intensive very fast.

### Dissection:

```
qi            e# Read input and parse to int n (accessed from the bottom of the stack as W$)
2a            e# Start with [2]
{             e# Loop
  {           e#   Map each integer x in the current list
    _W$,f#f+~ e#     to x+x^i for 0 <= i < n
    2         e#   and add a bonus 2 for the special case
  }%          e#   Gather these in the new list
  _W$&!       e#   Until the list contains an n
}g
e=            e# Count occurrences

```

The bonus `2`s (to handle the special case of input `2`, because `while` loops are more expensive than `do-while` loops) mean that the size of the list grows very fast, and the use of exponents up to `n-1` means that the values of the larger numbers in the list grow very fast.

# Answer
> 1 votes
# Haskell, 65 bytes

```
([2]%)
l%n|elem n l=sum[1|x<-l,x==n]|1>0=[x+x^k|x<-l,k<-[0..n]]%n

```

Try it online!

Golfing flawr's breadth-first-search. I also tried going backwards from `n`, but it was longer:

**73 bytes**

```
q.pure
q l|elem 2l=sum[1|2<-l]|1>0=q[x|n<-l,x<-[0..n],i<-[0..n],x+x^i==n]

```

Try it online!

# Answer
> 1 votes
# , ~~78~~ 77 bytes

```
function(n,x=2){while(!{a=sum(x==n)})x=rep(D<-x[x<n],n+1)+outer(D,0:n,'^')
a}

```

Try it online!

Using a simplified Breadth-first Search

Unrolled code with explanation :

```
function(n){                              # function taking the target value n

  x=2                                     # initialize vector of x's with 2

  while(!(a<-sum(x==n))) {                # count how many x's are equal to n and store in a
                                          # loop while a == 0

    x=rep(D<-x[x<n],n+1)+outer(D,0:n,'^') # recreate the vector of x's
                                          # with the next values: x + x^0:n
  }
a                                         # return a
}

```

---

Shorter version with huge memory allocation (failing for bigger cases) :

# , ~~70~~ 69 bytes

```
function(n,x=2){while(!{a=sum(x==n)})x=rep(x,n+1)+outer(x,0:n,'^')
a}

```

Try it online!

-1 byte thanks to @RobinRyder

# Answer
> 0 votes
# Pyth, 24 bytes

```
VQIJ/mu+G^GHd2^U.lQ2NQJB

```

Try it online!

This should produce the correct output, but is very slow (the 372 test case times out on TIO). I could make it shorter by replacing `.lQ2` with `Q`, but this would make the runtime horrendous.

Note: Produces no output for unreachable numbers \\$(n \leq 1)\\$

### Explanation

```
VQ                        # for N in range(Q (=input)):
   J                      #   J =
     m                    #     map(lambda d:
      u                   #       reduce(lambda G,H:
       +G^GH              #         G + G^H,
            d2            #         d (list), 2 (starting value) ),
              ^U.lQ2N     #       cartesian_product(range(log(Q, 2)), N)
    /                Q    #     .count(Q)
  IJ                  JB  #   if J: print(J); break

```

---
Tags: code-golf, sequence, combinatorics
---


title: Implement a Stopwatch

text:
# Question
Title: Implement a Stopwatch
Implement a simple digital Stopwatch, which will display the time elapsed in seconds and minutes, as described below.

> **Important**
>
> Please read both *Display* and *Controls* sections !

**Display**

Time elapsed, should be displayed in the `MM:SS` format, by replacing the previously displayed time string "in-place" (clearing the whole or a part of the screen is also allowed).

The stopwatch must be updated at least every second.

*Examples:*

0 minutes, 0 seconds

```
00:00

```

0 minutes, 33 seconds

```
00:33

```

1 minute, 50 seconds

```
01:50

```

Initially, you can start with '00:00' or with any other value in range \[00:00-59:59\].

Once your Stopwatch reaches `59:59`, it should reset to `00:00` and continue afresh.

You can use a different base (instead of decimal) or even a different numeral system if you wish, as long as you follow the general pattern.

For example `13:03` can be displayed as:

Decimal

```
13:03

```

Hexadecimal

```
0D:03

```

Base64

```
N:D

```

Quater-imaginary base

```
10101:3

```

Roman Numerals

```
XIII:III

```

Beware that if you use a non-decimal numeral system/base, it must be encoded using printable ASCII (or Unicode) characters, e.g. using two binary (unprintable) bytes for minutes and seconds is not allowed.

You must also left-pad your output with zeroes as appropriate, if your numerical system allows for that.

Replacing the separator character `:` with any other printable character (including digits) is also acceptable.

**Controls**

The stopwatch should start *paused*, and stay in this state, until user explicitly *starts* it, by pressing the *'control'* key (see below).

If, while stopwatch is counting, user presses the *'control'* key again, the stopwatch should *pause* (keeping the current time), until the *'control'* key is pressed a one more time.

The *'control'* key can be a single keystroke, e.g. `s`, or any combination of keys, e.g. `Ctrl+Shift+X`, but it must be 'atomic', pressing multiple keys in sequence, e.g. `s` then `Enter`, is *not allowed*.

The same *'control'* key (or combination) must be used to *pause* and *resume* the stopwatch.

You must use a specific *'control'* key, i.e. 'any key' is not allowed.

Alternatively, you can use a single or double mouse-click, instead of a keypress for 'control'.

---

**Rules**

* This is , the shortest answer in bytes wins;
* Standard code-golf loopholes apply;
* Your program must (theoretically) be capable of running forever.

# Answer
> 8 votes
# SmileBASIC, ~~86~~ ~~77~~ 71 bytes

```
@L
N=N!=DIALOG(FORMAT$("%02D:%02D",F/60MOD 60,F MOD 60),,,N)F=F+1GOTO@L

```

`DIALOG` displays a textbox on the touch screen. `N` is the number of seconds the text box will stay on screen before it disappears. If `N` is `0`, it stays until the user presses the button on the touch screen.

`DIALOG` Returns `1` if the user pressed the button, and `0` if it closed automatically. So when the user pushes the pause button, it returns `1`, and the display time is set to `0`, pausing the stopwatch. After the user presses the button again, we set the display time back to `1`, resuming the timer. Basically, every time `DIALOG` returns `1`, the display time is switched between `1` and `0` using `!=`, which is eqivilant to a logical XOR as long as both inputs are 1 or 0.

# Answer
> 9 votes
# Python 2, ~~167~~ 129 bytes

-36 bytes mostly\* from using Maltysen's idea of catching `ctrl-c` using an exception - go give credit!
-4 bytes thanks to DLosc (init `n` and `b` to 0 rather than `f()`)
-1 byte thanks to FlipTack (use `p^=1` rather than `p=1-p`)
-2 bytes thanks to Felipe Nardi Batista (remove precision specifiers)

```
import time
f=time.time
n=b=p=0
while 1:
 try:n=[n,f()][p];t=n-b;print'\r%02d:%02d'%(t/60%60,t%60),
 except:b=[b-n+f(),b][p];p^=1

```

Works the same as my original, below, but with the control key sequence of `ctrl+c`.
(Tested by me with Python 2.7.8 on Windows 7, 64bit;
Tested by Brian Minton with Python 2.7.13 on linux, 64bit)

* also collapsed `if` statement to a list lookup in order to get the `try` as a one-liner.

My original:

```
import time,msvcrt as m
f=time.time
n=b=p=0
while 1:
 if m.kbhit()and m.getch()==b'p':b=[b-n+f(),b][p];p^=1
 if p:n=f()
 t=n-b;print'\r%0.2d:%0.2d'%(t/60%60,t%60),

```

(Tested by me with Python 2.7.8 on Windows 7, 64bit - this code, however, is Windows specific due to the use of the `msvcrt` library)

The control key is 'p'.

`n` and `b` are initialised to the same value at start-up, giving an "offset" of 0; `p` is initialised to 0, indicating a paused state.

Whenever the control key is pressed the value of `p` is switched. When switching from a paused state to an active state `b` is updated to a new value keeping any current offset from the previous active state(s) with `b-n`.

During an active state `n` is repeatedly updated to the current time by calling `time.time()`.

The difference between `n` and `b`, `t`, is then the total number of seconds (including a fractional part) elapsed during active state(s).

The minutes elapsed are then `t/60` and each of the minutes and seconds are displayed mod 60 with `(t/60%60,t%60)`. Leading zeros are prepended for each using string formatting of the integer part with `'...%0.2d...'`. Printing a tuple (the trailing `,`) where the first item has a leading carriage return (the `\r`) causes the previously printed text to be overwritten.

# Answer
> 6 votes
# Python - ~~160~~ ~~159~~ 143 bytes

*Thanks to @JonathanAllan for saving me 18 bytes!*

Only uses builtin libraries, so the control key is `ctrl-c`, catching it with an `except keyboardInterrupt`.

```
import time
Z=0
print'00:00'
while 1:exec"try:\n while 1:\n  %s\nexcept:1\n"*2%(1,"print'\033c%02d:%02d'%divmod(Z%3600,60);Z+=1;time.sleep(1)")

```

# Answer
> 5 votes
# QBasic, ~~213~~ 211 bytes

Control key is tab. Leaving this running may cause laptop fires. You have been warned.

```
DO
WHILE k$<>CHR$(9)
k$=INKEY$
LOCATE 1
?CHR$(48+m\10);CHR$(48+(m MOD 10));":";CHR$(48+(d MOD 60)\10);CHR$(48+(d MOD 10))
IF r THEN
n=TIMER
d=v+n-b+86400
m=d\60MOD 60
END IF
WEND
k$=""
v=v+n-b
r=1-r
b=TIMER
LOOP

```

Here it is in action, pausing at 10, 15, and 20 seconds:

### Ungolfed and commented

```
' Outer loop runs forever
DO
  ' The WHILE-WEND loop runs until tab is pressed
  WHILE key$ <> CHR$(9)
    key$ = INKEY$
    ' Output the stopwatch value at top left of screen
    LOCATE 1
    ' Unfortunately, QBasic's PRINT USING doesn't have a format for printing
    ' with leading zeros, so we have to do it manually by printing the
    ' 10s digit and the 1s digit
    PRINT CHR$(48 + minute \ 10); CHR$(48 + (minute MOD 10));
    PRINT ":";
    PRINT CHR$(48 + second \ 10); CHR$(48 + (second MOD 10))
    ' Update the current time if the running flag is set
    IF running THEN now = TIMER
    ' Take the difference between now and the last time we started the
    ' stopwatch, plus the amount of saved time from previous runs,
    ' plus 86400 to account for the possibility of running over midnight
    ' (since TIMER is the number of seconds since midnight, and QBasic's
    ' MOD doesn't handle negative values like we would need it to)
    diff = saved + now - lastStarted + 86400
    second = diff MOD 60
    minute = diff \ 60 MOD 60
  WEND
  ' If we're outside the WHILE loop, the user pressed tab
  key$ = ""
  ' Add the previous run's time to the saved amount
  saved = saved + now - lastStarted
  ' Toggle running between 0 and 1
  running = 1 - running
  ' If we're starting, we want to put the current time in lastStarted;
  ' if we're stopping, it doesn't matter
  lastStarted = TIMER
LOOP

```

Note that values of `TIMER` are floating-point. This doesn't affect the output, since `MOD` and `\` truncate to integers. But it does add accuracy to the amount of saved time: if you pause the timer right before a tick, you'll see when you start it up again that the number changes in less than a second.

# Answer
> 5 votes
# bash + Unix utilities, 90 or 93 bytes

**90-byte version:**

```
trap d=\$[!d] 2;for((n=0;;)){((d|!n))&&dc<<<DP60dod*d$n\r%+n|colrm 1 4&&: $[n++];sleep 1;}

```

**93-byte version:**

```
trap d=\$[!d] 2;for((n=0;;)){((d|!n))&&dc<<<DP60dod*$n+n|colrm 1 4&&n=$[(n+1)%3600];sleep 1;}

```

Ctrl-C is the resume/pause character. A space is the delimiter between minutes and seconds.

The difference between the two versions is that the 90-byte program will work for 2^63 seconds (at which point, bash will give me an integer overflow).

The 93-byte version will truly work forever.

The original problem included the requirement: "Your program must (theoretically) be capable of running forever."

If running for 2^63 seconds is sufficient to meet that requirement, then the 90-byte solution works. That duration is more than 20 times the age of the universe!

If the program needs to be able to run for longer than that, I'll have to go with the 93-byte solution.

---

I should probably point out that this solution, as well as at least some of the others posted, will *very* slowly fall behind the true elapsed time. This slippage is because the program is sleeping for one second between each execution of the body of the loop, but the body of the loop does take some tiny amount of time to execute. This will be inconsequential in practice.

# Answer
> 4 votes
## Batch, 132 bytes

```
set/ar=0,m=s=100
:l
cls
@choice/t 1 /d y /m %m:~1%:%s:~1% /n
set/as+=r,m+=c=s/160,s-=c*60,m-=m/160*60,r^^=%errorlevel%-1
goto l

```

Pressing `n` will (un)pause the timer. The output flicker can be reduced at a cost of three (or four) bytes.

# Answer
> 4 votes
# Pure bash, 141 bytes

```
set -m
while ! read -t 1;do printf '\r%02i:%02i' $[s=s>3598?0:s+1,s/60] $[s%60];done&trap 'fg>/dev/null' TSTP
printf '00:00'
kill -STOP $!
read

```

This uses nothing but Bash builtins (no external tools). The control character is `Ctrl-Z`, so that standard `SIGTSTP` handling pauses the stopwatch.

If `Ctrl-Z` is pressed while the subshell is foregrounded, it will pause execution and return the outer script to the foreground, where it will wait silently. If the outer script is foregrounded, the trap handler will resume the subshell's execution, and it will count up again.

# Answer
> 3 votes
# HTML + JavaScript (ES6), ~~191 192 187 183~~ 174 bytes

```
<b onclick='b=b?clearInterval(b):setInterval("a.innerHTML=`${(d=(((c=a.innerHTML.split`:`)[1]>58)+c[0])%60)>9?d:`0`+d}:${(e=++c[1]%60)>9?e:`0`+e}",1e3)'onload='b=0'id=a>00:00

```

### Explanation

Click the timer to start or pause the stopwatch. As such, a single click is the *control* key. The separator between the two values is a colon.

Whenever the user clicks the click, the value of `b` is checked. It is initialised to `0` which evaluates to `false`, so a string of code is evaluated every 1000 milliseconds. This sets the variable to the id of the interval, so it can be stopped later. If `b` contains a number, it evaluates to `true`, so the interval is stopped. This returns the value `undefined`, so the cycle continues.

The string of code changes the html of the element with id `a` (the stopwatch). First the minutes are parsed by taking the previous stopwatch value, splitting it by the colon, and getting the minutes value, which is increased by 0 if the value of the seconds is not 59 (greater than 58), and 1 otherwise, modulo 60. Then this value is padded. Then comes the colon, and lastly, the seconds. The code simply gets the old value, increases it by 1, takes modulo 60 and optionally pads it.

# Answer
> 3 votes
## C ~~309~~ 179 bytes

```
f(){m=0,s=0;A: while(getchar()^'\n'){if(s++==59){if(m++==59)m=0;s=0;}printf("\r%02d:%02d",m,s);sleep(1);system("clear");if(getchar()=='\n'){break;}}while(getchar()^'\n'){}goto A;}

```

Ungolfed version:

```
void f()
{
   int m=0,s=0;

   A: while(getchar()^'\n')
      {
       if(s++==59)
       {
         if(m++==59)
           m=0;

         s=0;
       }
       printf("\r%02d:%02d",m,s);
       sleep(1);
       system("clear");

        if(getchar()=='\n')
        {
          break;
        }
      }

       while(getchar()^'\n')
       {}
       goto A ;
}

```

Usage: Press `Enter` to *Pause* and *Resume* the Stopwatch.

Explanation:

* Wait for `Enter` keystroke, `break` the first `while` loop and wait until next `Enter` comes.
* Upon next `Enter` keystroke, `goto` first `while` loop and resume counting.

Now, I know `goto` is a bad coding practice in C, but I could not figure out another way.

# Answer
> 3 votes
# Javascript in Chrome console, 143 bytes

```
f=document,m=s=g=i=0;setInterval(()=>{if(g%2){m=(i/60|0)%60;s=i++%60}f.write((m>9?m:'0'+m)+':'+(s>9?s:'0'+s));f.close();f.onclick=()=>g++},1e3)

```

When entered in console it inits the counter to 00:00 and then enables the control which is keypress on the document.

Not much magic going on, notably the `(i/60)|0` floors the number

Done and tested in Chrome console

# Answer
> 3 votes
# Javascript, 124 bytes

```
s=i=1,setInterval("s&&(d=document).close(d.write(`0${i/60%60|0}:`.slice(-3)+`0${i++%60}`.slice(-2))),d.onclick=_=>s=!s",1e3)

```

The 'control key' is a click on the document. To test this, paste the code in the console or in a html file inside the `<script>` tag.

*Explanation:*

```
let s = 1
let i = 1
setInterval(() => {
    //If s = true then check after the "&&" operator else false
    s && (d = document).close( //put the document variable inside the d variable, so now i don't need to use anymore the long word 'document, then i close the document
            d.write( //Write into the document the next string
                `0${i/60%60|0}:`.slice(-3) + `0${i++%60}`.slice(-2) //Here is the magic, here I update the 'i' variable and convert the 'i' value to minutes and seconds
            )
        ),
        d.onclick = _ => s = !s //Add onclick event to the document, if s = true then s = false, if s = false then s = true
}, 1e3) //1e3 = 1000

```

Tested in Chrome

# Answer
> 2 votes
**C# 220 Bytes**

```
using static System.Console;
using static System.DateTime;
class P
{
    static void Main()
    {
        var l = Now;
        var d = l-l;
        for( var r = 1<0;;Write($"\r{d:mm\\:ss}"))
        {
            if (KeyAvailable&&ReadKey(1<2).KeyChar == 's')
            {
                l = Now;
                r = !r;
            }
            if (r)
                d -= l - (l = Now);
        }

    }
}

```

Golfed

```
using static System.Console;using static System.DateTime;class P{static void Main(){var l=Now;var d=l-l;for(var r=1<0;;Write($"\r{d:mm\\:ss}")){(KeyAvailable&&ReadKey(1<2).KeyChar=='s'){l=Now;r=!r;}if(r)d-=l-(l=Now);}}}

```

Using the `s` key to start/stop. Whole program works by remembering the TimeDelta using `DateTime.Now`

Most C#-Magic here comes from the C# 7.0 feature `using static`.

# Answer
> 2 votes
# PHP, ~~94~~ 91 bytes

I assume that 32 is the key code for the space bar (which it probably is not);
I currently have no way to test ncurses. But the rest of the code works fine.

```
for($s=[STDIN];;)echo date("\ri:s",$t+=$r^=stream_select($s,$n,$n,1)&&32==ncurses_getch());

```

starts at `00:00`, but increments immediately when pause ends

If You (like me) don´t have ncurses, You can test by replacing the second `date` parameter with `$t+=$r^=!rand(sleep(1),19);` or `$t+=$r^=++$x%20<1+sleep(1);`. (`sleep` always returns `0`.)

**breakdown**

```
for($s=[STDIN];                     // set pointer for stream_select
    ;                               // infinite loop:
)
    echo date("\ri:s",                  // 5. print CR + time
        $t+=                            // 4. increment $t if watch is running
        $r^=                            // 3. then toggle pause
            stream_select($s,$n,$n,1)   // 1. wait 1 second for a keystroke
            &&32==ncurses_getch()       // 2. if keystroke, and key==space bar
    ;

```

# Answer
> 2 votes
Bash, 65 bytes

`trap d=\$[!d] 2;for((;;)){ printf "\r%(%M:%S)T" $[n+=d];sleep 1;}`

Note that it must be written to a file script to work correctly, or else, try:

`bash -c 'trap d=\$[!d] 2;for((;;)){ printf "\r%(%M:%S)T" $[n+=d];sleep 1;}'`

Extended version to explain it:

```
trap d=\$[!d] 2                     # flip d for each INT (ctrl-c) signal.
for((n=0;;)){                       # repeat forever the code inside the {...}
                                    # The n=0 is not strictly needed.
    printf "\r%(%M:%S)T" "$[n+=d]"  # Print Minute:Second string calculated from
                                    # the n value, increment by the value of d.
                                    # If IFS is not numeric (0-9), then, the
                                    # quotes around "$[n+=d]" could be removed.
    sleep 1                         # wait for 1 second.
}

```

The `%(...)T` format to printf is valid in bash 5+.

# Answer
> 1 votes
# Commodore BASIC (C64/TheC64 Mini, VIC-20, PET, C16/+4) - 147 tokenized and BASIC bytes

```
 0?"{clear}":geta$:ifa$<>" "thengoto
 1ti$="000000"
 2fori=.to1:?"{home}"mid$(ti$,3,2)":"mid$(ti$,5,2):geta$:b$=ti$:i=-(a$=" "):nE:pO198,.
 3geta$:ifa$<>" "then3
 4ti$=b$:goto2

```

`{clear}` in the listing is `SHIFT+CLR/HOME` which outputs as one PETSCII character when following an opening quotation mark, whereas `{home}` is the `CLR/HOME` key without the shift on the same condition of following an opening quotation mark.

Use the space bar as the control key.

To work with the Commodore 128 in BASIC 7, change the listing in the following lines:

```
 0?"{clear}":geta$:ifa$<>" "thengoto0
 2fori=.to1:?"{home}"mid$(ti$,3,2)":"mid$(ti$,5,2):geta$:b$=ti$:i=-(a$=" "):nE:poK198,.

```

Adds an extra seven tokens to the count (as all numbers are stored in BASIC as 7 bytes, so `goto10` is 8 tokenized bytes whereas `goto` is only 1).

# Answer
> 1 votes
# C (gcc), ~~121~~ 115 bytes

```
p,r;g(){r^=1;}main(t,b){for(b=time(signal(2,g));;r?p=t:(b+=t!=p))t=time(0)-b,printf("\r%02d:%02d  ",t/60%60,t%60);}

```

Try it online!

Sets a signal handler for SIGINT, which is triggered by pressing control-C. We keep a time offset in `b`, and display the wall clock time minus the time offset. If we are paused, increment the time base everytime the wall clock ticks to freeze the displayed time.

Thanks to @ceilingcat for shaving off 6 bytes!

# Answer
> 0 votes
# Zsh + Gnu date, 242 bytes

Featuring 1/100ths of a second! It requires an interactive terminal, but here's a TIO link anyway.
Hit `Enter` to start/stop the timer; `Ctrl-C` to exit.

```
u(){p=`gdate +%s`;q=`gdate +%N`;}
f(){read -t0.01&&{read;break};unset REPLY}
g(){while :;{u;t=$[p-a];s=$[t%60];m=$[(t%3600-s)/60]
echo "\r`printf %02d:%02d $m $s`.$q[1,2]\c";f;}}
<<<ready;read;u;a=$p
while :;{f;echo "\r\e[2A\c";u;a=$[p-t];g;}

```

Comments (a bit out of date):

```
u()echo $[`gdate +%s%N`/1000]       # fn:unix timestamp extended to µs
v()gdate +%s                        # fn:unix time, in s
f(){read -t0.01 -r&&{read -r;break;} # fn:listens for "Enter"
                      ;unset REPLY;}

g(){while :;                        # fn:rolling stopwatch
    {q=`u`;t=$[`v`-a]               #    t=time diff from baseline (s)
    ;echo "\r`printf %02d:%02d      #    format output
    $[(t%3600-s)/60] $s`            #    minutes:seconds
    .${q:10:2}\c";                  #    .xx = partial seconds
    f;}}                            #    listen for "Enter"

                                    # Execution starts here!
<<<ready;read;u;a=$p                # Wait for "Enter"; get baseline $a

while :;{                           # Main program loop
         f;                         # listen for an "Enter"
           echo "\r\e[2A\c"         # go up 1 line of the console
a=$[`v`-t]                          # reset the baseline
                ;g;}                # begin the stopwatch

```

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


title: Compute height of Bowl Pile

text:
# Question
Title: Compute height of Bowl Pile
# Bowl Pile Height

The goal of this puzzle is to compute the height of a stack of bowls.

A bowl is defined to be a radially symmetric device without thickness. Its silhouette shape is an even polynomial. The stack is described by a list of radii, each associated with an even polynomial, given as input as a list of coefficients (e.g. the list `3.1 4.2` represents the polynomial \\$3.1x^2+4.2x^4\\$).

The polynomial may have arbitrary degree. For simplicity, the height of the pile is defined as the altitude of the center of the top-most bowl (see plot of Example 3 for an illustration).

Test cases are in the format `radius:coeff1 coeff2 ...`: each line starts with a float number representing the radius of the bowl, followed by a colon and a space-separated list containing the coefficients for the even powers, starting with power 2 (zero constant part is implied). For example, the line `2.3:3.1 4.2` describes a bowl of radius `2.3` and the shape-polynomial `3.1 * x^2 + 4.2 * x^4`.

## Example 1

```
42:3.141

```

describes a pile of zero height since a single bowl has no height.

## Example 2

```
1:1 2
1.2:5
1:3

```

describes a pile of height `2.0` (see plot).

## Example 3

```
1:1.0
0.6:0.2
0.6:0.4
1.4:0.2
0.4:0 10

```

describes a pile of height 0.8 (see green arrow in the plot).

This is code golf, so the shortest code wins.

I have reference code.

# Edit:

The reference implementation relies on a library to compute the roots of polynomials. You may do that as well but you don't need to. Since the reference implementation is only a (quite good) numerical approximation, I will accept any code which produces correct results within common floating-point tolerances.

The idea counts. I don't care if there are small erros \\$\<\varepsilon\\$.

<sup> Another variant of this puzzle is to minimize the height by reordering the bowls. I'm not sure if there's a fast solution (I guess it's NP-hard). If anyone has a better idea (or can prove NP-completeness), please tell me! </sup>

# Answer
# Jelly, ~~54~~ 53 bytes

```
J×$ÆrAƑƇ«⁹;⁹*€J{ḋ⁸ŻṀ
Œcz€0ḢṂç@I0;ⱮFƲƲ€ṚṁL’R€Ɗ;+Ṁ¥¥ƒ0Ṁ

```

Try it online!

A monadic link that takes as its argument the list of bowls from top to bottom in the format `[[b1_radius, b1_coef1, ...], [b2_radius, b2_coef1, ...]]` and returns the y position of the bottom of the top bowl.

Now correctly handles bowls which meet at places other than the minimal radius.

## Explanation

### Helper link: takes as left argument `l` the differences in coefficients of the polynomials representing the bowls from 1 upwards, and its right argument `r` the minimum radius; returns the maximum y value where the two bowls meet

```
  $                   | Following as a monad:
J                     | - Sequence from 1..<len(l)>
 ×                    | - Multiply (by l)
   Ær                 | Roots of polynomial
     AƑƇ              | Keep only those invariant when passed through absolute function (excludes negative, imaginary and complex numbers)
        «⁹            | Min of these filtered roots and r
          ;⁹          | Concatenate r to the list
            *€        | Each root/radius to the power of:
              J{      | - Sequence from 1..<len(l)>
                ḋ⁸    | Dot product with l
                  Ż   | Prepend zero
                   Ṁ  | Maximum

```

### Main link, takes a bowl pile as its argument and returns y value of base of top bowl

```
Œc                               | Combinations length 2
  z€0                            | Transpose each using 0 as a filler
               Ʋ€                | For each one, do the following as a monad:
     Ḣ                           | - Take the head (the radii)
      Ṃ                          | - Minimum
       ç@     Ʋ                  | - Call the helper link with this (min radius) as right argument and the following as left argument:
         I                       |   - Increments (difference between second and first polynomial for each coefficient)
          0;Ɱ                    |   - Prepend each with a zero (odd coefficients are all zero)
             F                   |   - Flatten
                 Ṛ               | Reverse
                  ṁ    Ɗ         | Mould to the following as a monad:
                   L             | Length
                    ’            | Decrease by 1
                     R€          | Range of each (e.g. [1],[1,2],[1,2,3],[1,2,3,4]
                            ¥ƒ0  | Reduce using the following as a dyad and starting with 0
                        ;  ¥     | - Concatenate the following as a dyad
                         +       |   - Add
                          Ṁ      |   - Take the maximum
                               Ṁ | Finally take the overall maximum

```

### Python reference

Finally, here’s a TIO version of the Python reference that @pasbi included for the main problem. It reads from stdin.
> 6 votes

# Answer
# Python 3 \+ numpy + scipy, ~~248~~ 240 bytes

```
from scipy.optimize import*
from numpy import*
def f(b,i=0):
 for r,c in b:p=zeros(2*len(c)+1);p[-3::-2]=c;p[-1]=h=max([0,*(-fminbound(lambda x:polyval(polysub(p,d),x),0,min(s,r),full_output=1)[1]for s,d in b[:i])]);b[i][1]=p;i+=1
 return h

```

Try it online!

*-8 bytes thanks to @xnor*

The function takes a list of `[radius, polynomial]` pairs as input and returns the pile height.

This solution uses more or less the same algorithm as the reference code except that it does not compute the maximum using derivatives. Meanwhile, it is written using built-in `numpy` and `scipy` functions in Python. The ungolfed version is shown in the following. This serves as an alternative version of the reference code for those who wants a shorter version to capture the idea quickly.

```
from scipy.optimize import fminbound
import numpy as np

def compute_pile_height(bowl_data):
    for i, (r, curve) in enumerate(bowl_data):
        distances = [0]  # Initialize the distances array with 0 as the lower bound for max
        # Construct a complete polynominal coefficient array
        curve_poly = np.zeros(2 * len(curve) + 1)
        curve_poly[-3::-2] = curve

        # Iterate over all bowls under the current bowl
        for j in range(i):
            b_r, b_curve_poly = bowl_data[j]

            # Calculate the difference polynominal between the current bowl and bowl j
            diff = np.polysub(curve_poly, b_curve_poly)

            # Find the maximum height difference between bowl j and the current bowl in the range [0, min(b_r, r)]
            max_height_diff = -fminbound(lambda x:np.polyval(diff, x), 0, min(b_r, r), full_output=True)[1]
            distances.append(max_height_diff)

        # Compute the maximum distance as the height for the current bowl,
        # update the polynominal using the height as the constant coefficient
        curve_poly[-1] = height = max(distances)

        # Update stored data for the current bowl
        bowl_data[i][1] = curve_poly
    return height

```

Try it online!
> 2 votes

# Answer
# , ~~451~~ 436 bytes

```
function(x){x=c(x[1],x);a=rev(pmax(0,c(combn(x,2,function(y,z=sapply(y,"length<-",max(lengths(y)))){z[is.na(z)]=0
b=rep(0,2*(n=nrow(z)-1))
b[2*1:n]=e=z[-1,2]-z[-1,1]
b=b*1:(2*n)
while(!c(b,1)[1])b=b[-1]
b=rev(b)
s=`if`(length(b)>1,eigen(rbind(-(b/b[1])[-1],cbind(diag(length(b)-2),0)))$va,0)
max(outer(c(pmin(abs(s[s==abs(s)]),r<-min(z[1,])),r),2*1:n,`^`)%*%e)}))))
o={}
for(i in seq(a=x[-1])){o=c(o,max(c(0,o)+a[1:i+F]));F=F+i}
max(o)}

```

Try it online!

Try it online!

Broadly speaking an R port of my Jelly answer, though since base R has no function to find the roots of polynomials this is implemented using the method found in `polynom::solve.polynomial`.

A function taking a list of numeric vectors from top to bottom of pile.

Thanks to @RobinRyder for golfing off 15 bytes!
> 1 votes

# Answer
# Wolfram Language (Mathematica), ~~104~~ 93 bytes

```
FoldPair[{(R=#;F=#2)&@@#2;H=Max[0,{#2-F,0<x<#~Min~R}~MaxValue~x&@@@#],#~Join~{R|H+F}}&,{},#]&

```

Try it online!

Takes input as a List of `{radius, polynomial}` pairs representing bowls, with polynomials in terms of \\$x\\$.

For decimal instead of symbolic output, use `NMaxValue` instead (or just call `N` on the result).

```
(* Step through a list of bowls: *)
(* At each step, calls a function taking {previous-bowls-list},current-bowl *)
(*  which returns {height,{bowls-list}} *)
(* and returns the final height *)
FoldPair[
  (R=#;F=#2)&@@#2;          (*  extract Radius and Function*)
  {
    H=Max[0,                (*  Height - at least zero; the greatest of *)
      MaxValue[{#2-F,       (*   the required heights *)
          0<x<#~Min~R},x]   (*     within the relevant domain *)
      &@@@#]                (*   given all previous bowls *)
  ,
    #~Join~{R|H+F}          (*   append to list of bowls *)
  }&,
  {},                       (* initial list of bowls (empty) *)
  #                         (* list of bowls *)
]&

```
> 1 votes

---
Tags: code-golf, math, arithmetic, polynomials
---


# Question
Title: Write a "hello world" program that can be compiled/interpreted as two different languages simultaneously
Rules:

1. Your program must print "hello world" when executed
2. Your program must be interpretable or compilable into 2 or more languages
3. Your program must require no input or arguments
4. Languages with identical syntax are too easy, and will be shunned. We all know you can write `echo hello world` in Bash and Batch, so let's make it more interesting.

I'll add my example as an answer.

# Answer
> 0 votes
**Python 2.7 and Bash, 45 bytes**

```
x="hello world"
''''echo $x;exit #'''
print x

```

Adding 1 byte can make it Python 3 compatible as well -- `print(x)`

Explanation by line:

1. Variable assignment valid in both languages
2. Python comment `'''` with an extra `'` will be interpreted as 0-length string concatenation in bash, followed by echo and exit. The `#'''` closes the python comment block, but is preceded by a bash comment, so it will be ignored
3. Python print (bash will exit before getting here, so it won't complain)

# Answer
> 0 votes
## Ruby and Foo, 17 bytes

```
puts"hello world"

```

Foo prints everything in the quotes, and Ruby uses a built-in function to output to stdout.

---
Tags: code-golf, code-challenge, polyglot, hello-world
---


# Question
Title: Normalized Malbolge to Malbolge translator
In this task, you will write a program/function that takes a Normalized Malbolge program and outputs the resulting Malbolge program. (This is a secret tool that all Malbolge programmers are using!)

## Input

A data structure that (somehow) represents a Normalized Malbolge program.

## Output

A data structure that represents the resulting Malbolge program.

## Examples

```
jpoo*pjoooop*ojoopoo*ojoooooppjoivvvo/i<ivivi<vvvvvvvvvvvvvoji
(=BA#9"=<;:3y7x54-21q/p-,+*)"!h%B0/.~P<<:(8&66#"!~}|{zyxwvugJ%

jjjj*<jjjj*<v
('&%#^"!~}{XE

jjjjjjjjjjjjjjjjjjjjjjj*<jjjjjjjjjjjjjjjjjjjjjjjj*<v
('&%$#"!~}|{zyxwvutsrqpnKmlkjihgfedcba`_^]\[ZYXWVT1|

```

## How to convert

Iterate over the normalized Malbolge program, performing the following steps for each character:

1. Replace the characters in the string `*jpovi</` with the corresponding character in `'(>DQbcu`. (That is, map `*` to `'`, `j` to `(`, and so on.)
2. Then subtract the current position of the program counter (i.e. the number of characters before the current one) from the character's ASCII code.
3. If the resulting ASCII code is less than 33, increment it by 94 and repeat until it is at least 33.
4. Append the resulting character to the output.

## Rules

* This is a contest; the shortest answer wins.
* No standard loopholes please.
* The default I/O methods are allowed.
* Input will only contain the characters `*jpovi</`.

# Answer
> 4 votes
# Jelly, ~~29~~ 22 bytes

```
Oị“%þV DCµ2®  ‘_JịØṖḊ¤

```

Try it online!

A monadic link taking a Jelly string as its argument and returning a Jelly string.

Thanks to @JonathanAllan for saving 2 bytes!

## Explanation

```
O                      | Convert to Unicode code points
 ị“%þV DCµ2®  ‘        | Index into compressed integer list [37, 31, 86, 32, 68, 67, 9, 50, 8, 32, 32] (note the 32s are never actually used because the input mod 11 will be one of 1,2,3,5,6,7,8,9)
               _J      | Subtract position of character in original string
                 ị   ¤ | Index into the following as a nilad:
                  ØṖ   | - Printable ASCII characters
                    Ḋ  | - With the first character (space) removed

```

# Answer
> 9 votes
# Malbolge Unshackled (20-trit rotation variant), 7,784e6 bytes

Size of this answer exceeds maximum postable program size (eh), so the code is located in my GitHub repository.

## How to run this?

This might be a tricky part, because naive Haskell interpreter will take ages upon ages to run this. TIO has decent Malbogle Unshackled interpreter, but sadly I won't be able to use it (limitations).

The best one I could find is the fixed 20-trit rotation width variant, that performs very well, **converting 0,5 characters per second**.

To make the interpreter a bit faster, I've removed all the checks from Matthias Lutter's Malbolge Unshackled interpreter.

My modified version can run around 6,3% faster.

```
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const char* translation = "5z]&gqtyfr$(we4{WP)H-Zn,[%\\3dL+Q;>U!pJS72Fh"
        "OA1CB6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G\"i@";

typedef struct Word {
    unsigned int area;
    unsigned int high;
    unsigned int low;
} Word;

void word2string(Word w, char* s, int min_length) {
    if (!s) return;
    if (min_length < 1) min_length = 1;
    if (min_length > 20) min_length = 20;
    s[0] = (w.area%3) + '0';
    s[1] = 't';
    char tmp[20];
    int i;
    for (i=0;i<10;i++) {
        tmp[19-i] = (w.low % 3) + '0';
        w.low /= 3;
    }
    for (i=0;i<10;i++) {
        tmp[9-i] = (w.high % 3) + '0';
        w.high /= 3;
    }
    i = 0;
    while (tmp[i] == s[0] && i < 20 - min_length) i++;
    int j = 2;
    while (i < 20) {
        s[j] = tmp[i];
        i++;
        j++;
    }
    s[j] = 0;
}

unsigned int crazy_low(unsigned int a, unsigned int d){
    unsigned int crz[] = {1,0,0,1,0,2,2,2,1};
    int position = 0;
    unsigned int output = 0;
    while (position < 10){
        unsigned int i = a%3;
        unsigned int j = d%3;
        unsigned int out = crz[i+3*j];
        unsigned int multiple = 1;
        int k;
        for (k=0;k<position;k++)
            multiple *= 3;
        output += multiple*out;
        a /= 3;
        d /= 3;
        position++;
    }
    return output;
}

Word zero() {
    Word result = {0, 0, 0};
    return result;
}

Word increment(Word d) {
    d.low++;
    if (d.low >= 59049) {
        d.low = 0;
        d.high++;
        if (d.high >= 59049) {
            fprintf(stderr,"error: overflow\n");
            exit(1);
        }
    }
    return d;
}

Word decrement(Word d) {
    if (d.low == 0) {
        d.low = 59048;
        d.high--;
    }else{
        d.low--;
    }
    return d;
}

Word crazy(Word a, Word d){
    Word output;
    unsigned int crz[] = {1,0,0,1,0,2,2,2,1};
    output.area = crz[a.area+3*d.area];
    output.high = crazy_low(a.high, d.high);
    output.low = crazy_low(a.low, d.low);
    return output;
}

Word rotate_r(Word d){
    unsigned int carry_h = d.high%3;
    unsigned int carry_l = d.low%3;
    d.high = 19683 * carry_l + d.high / 3;
    d.low = 19683 * carry_h + d.low / 3;
    return d;
}

// last_initialized: if set, use to fill newly generated memory with preinitial values...
Word* ptr_to(Word** mem[], Word d, unsigned int last_initialized) {
    if ((mem[d.area])[d.high]) {
        return &(((mem[d.area])[d.high])[d.low]);
    }
    (mem[d.area])[d.high] = (Word*)malloc(59049 * sizeof(Word));
    if (!(mem[d.area])[d.high]) {
        fprintf(stderr,"error: out of memory.\n");
        exit(1);
    }
    if (last_initialized) {
        Word repitition[6];
        repitition[(last_initialized-1) % 6] =
                ((mem[0])[(last_initialized-1) / 59049])
                    [(last_initialized-1) % 59049];
        repitition[(last_initialized) % 6] =
                ((mem[0])[last_initialized / 59049])
                    [last_initialized % 59049];
        unsigned int i;
        for (i=0;i<6;i++) {
            repitition[(last_initialized+1+i) % 6] =
                    crazy(repitition[(last_initialized+i) % 6],
                        repitition[(last_initialized-1+i) % 6]);
        }
        unsigned int offset = (59049*d.high) % 6;
        i = 0;
        while (1){
            ((mem[d.area])[d.high])[i] = repitition[(i+offset)%6];
            if (i == 59048) {
                break;
            }
            i++;
        }
    }
    return &(((mem[d.area])[d.high])[d.low]);
}

unsigned int get_instruction(Word** mem[], Word c,
        unsigned int last_initialized,
        int ignore_invalid) {
    Word* instr = ptr_to(mem, c, last_initialized);
    unsigned int instruction = instr->low;
    instruction = (instruction+c.low + 59049 * c.high
            + (c.area==1?52:(c.area==2?10:0)))%94;
    return instruction;
}

int main(int argc, char* argv[]) {
    Word** memory[3];
    int i,j;
    for (i=0; i<3; i++) {
        memory[i] = (Word**)malloc(59049 * sizeof(Word*));
        if (!memory) {
            fprintf(stderr,"not enough memory.\n");
            return 1;
        }
        for (j=0; j<59049; j++) {
            (memory[i])[j] = 0;
        }
    }
    Word a, c, d;
    unsigned int result;
    FILE* file;
    if (argc < 2) {
        // read program code from STDIN
        file = stdin;
    }else{
        file = fopen(argv[1],"rb");
    }
    if (file == NULL) {
        fprintf(stderr, "File not found: %s\n",argv[1]);
        return 1;
    }
    a = zero();
    c = zero();
    d = zero();
    result = 0;
    while (!feof(file)){
        unsigned int instr;
        Word* cell = ptr_to(memory, d, 0);
        (*cell) = zero();
        result = fread(&cell->low,1,1,file);
        if (result > 1)
            return 1;
        if (result == 0 || cell->low == 0x1a || cell->low == 0x04)
            break;
        instr = (cell->low + d.low + 59049*d.high)%94;
        if (cell->low == ' ' || cell->low == '\t' || cell->low == '\r'
                || cell->low == '\n');
        else if (cell->low >= 33 && cell->low < 127 &&
                (instr == 4 || instr == 5 || instr == 23 || instr == 39
                    || instr == 40 || instr == 62 || instr == 68
                    || instr == 81)) {
            d = increment(d);
        }
    }
    if (file != stdin) {
        fclose(file);
    }
    unsigned int last_initialized = 0;
    while (1){
        *ptr_to(memory, d, 0) = crazy(*ptr_to(memory, decrement(d), 0),
                *ptr_to(memory, decrement(decrement(d)), 0));
        last_initialized = d.low + 59049*d.high;
        if (d.low == 59048) {
            break;
        }
        d = increment(d);
    }
    d = zero();

    unsigned int step = 0;
    while (1) {
        unsigned int instruction = get_instruction(memory, c,
                last_initialized, 0);
        step++;
        switch (instruction){
            case 4:
                c = *ptr_to(memory,d,last_initialized);
                break;
            case 5:
                if (!a.area) {
                    printf("%c",(char)(a.low + 59049*a.high));
                }else if (a.area == 2 && a.low == 59047
                        && a.high == 59048) {
                    printf("\n");
                }
                break;
            case 23:
                a = zero();
                a.low = getchar();
                if (a.low == EOF) {
                    a.low = 59048;
                    a.high = 59048;
                    a.area = 2;
                }else if (a.low == '\n'){
                    a.low = 59047;
                    a.high = 59048;
                    a.area = 2;
                }
                break;
            case 39:
                a = (*ptr_to(memory,d,last_initialized)
                        = rotate_r(*ptr_to(memory,d,last_initialized)));
                break;
            case 40:
                d = *ptr_to(memory,d,last_initialized);
                break;
            case 62:
                a = (*ptr_to(memory,d,last_initialized)
                        = crazy(a, *ptr_to(memory,d,last_initialized)));
                break;
            case 81:
                return 0;
            case 68:
            default:
                break;
        }

        Word* mem_c = ptr_to(memory, c, last_initialized);
        mem_c->low = translation[mem_c->low - 33];

        c = increment(c);
        d = increment(d);
    }
    return 0;
}

```

## It's working!

# Answer
> 6 votes
# Python 3, 82 bytes

```
p=0
for c in input():print(end=chr((b"de{#0ABT"["*jpovi<".find(c)]-p)%94+33));p+=1

```

Try it online!

Thanks to @Joel for replacing the ugly unprintable characters in the bytestring with printable ones.

I'm looking for a mod-chain to replace `"*jpovi<".find(c)`, but I don't think there is one that's shorter, and a non-exhaustive brute-force search hasn't found anything so far.

**82 bytes**

```
f=lambda s,p=0:s and chr((b"de{#0ABT"["*jpovi<".find(s[0])]-p)%94+33)+f(s[1:],p+1)

```

Try it online!

# Answer
> 5 votes
# Python 3, ~~84~~ 83 bytes

```
f=lambda p,i=0:p and chr(126-(i+b"WV@:-zyg"["*jpovi<".find(p[0])])%94)+f(p[1:],i+1)

```

Try it online!

This is mostly a math problem about simplifying the computation, plus some golfing after getting the math done. The ungolfed version of code is shown below.

# Ungolfed, non-recursive version

```
def convert(prog):
    offsets = dict(zip("*jpovi</", [87, 86, 64, 58, 45, 122, 121, 103]))  # ASCII encoded to "WV@:-zyg"
    output = ""
    for pos, c in enumerate(prog):
        output += chr(126-(offsets[c]+pos)%94)
    return output

```

Try it online!

# Answer
> 5 votes
# JavaScript (Node.js), 69 bytes

```
s=>(B=Buffer)(s).map((c,i)=>33+(B(" #{T BAe0d")[c%11]+94-i%94)%94)+''

```

Try it online!

### How?

Conveniently, Malbolge commands can easily be turned into a value in \\$\[1..9\]\\$ by just taking their ASCII code modulo \\$11\\$.

```
 char. | ASCII code | mod 11
-------+------------+--------
  '*'  |      42    |   9
  'j'  |     106    |   7
  'p'  |     112    |   2
  'o'  |     111    |   1
  'v'  |     118    |   8
  'i'  |     105    |   6
  '<'  |      60    |   5
  '/'  |      47    |   3

```

# Answer
> 3 votes
# Perl 6, ~~65 55~~ 53 bytes

```
*.ords>>.&{(' #{T BAe0d'.ords[$_%11]-$++)%94+33}.chrs

```

Try it online!

Uses the mod 11 trick from Arnaud's answer

# Answer
> 3 votes
# 05AB1E, ~~32~~ ~~31~~ ~~23~~ 22 bytes

```
žQ¦•4¡ˆ¶ü]₁η₃•₃вIÇèā-è

```

-8 bytes creating a port of *NickKennedy*'s Jelly answer, so make sure to upvote him!!
-1 byte thanks to @Grimy.

Outputs as a list of characters.

Try it online or verify all test cases.

**Explanation:**

```
   •4¡ˆ¶ü]₁η₃•          # Push compressed integer 82767635194143615015
              ₃в        # Converted to base-95 as list: [1,36,30,85,0,67,66,8,49,7,0]
                IÇ      # Push the input and convert each character to its unicode value
                  è     # Index each into the list we created
                   ā    # Push an integer list in the range [0, length]
                        # (without popping the list itself)
                    -   # Subtract it from the previous list
žQ                      # Push builtin with all printable ASCII characters,
  ¦                     # and remove the leading space
                     è  # Index the values of the list into the ASCII characters
                        # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?* and *How to compress integer lists?*) to understand why `•4¡ˆ¶ü]₁η₃•` is `82767635194143615015` and `•4¡ˆ¶ü]₁η₃•₃в` is `[1,36,30,85,0,67,66,8,49,7,0]`.

# Answer
> 2 votes
# Perl 5 (`-p`), ~~53~~, 51 bytes

saving 2 bytes, using `de{#0ABT` instead of `'(>DQbcu` so that `61` no longer needed

```
y;*jpovi</;de{#0ABT;;s/./chr 33+(-"@-"+ord$&)%94/ge

```

TIO

first answer was

```
y;*jpovi</;'(>DQbcu;;s/./chr 33+(61-"@-"+ord$&)%94/ge

```

TIO

# Answer
> 2 votes
# Japt, ~~24~~ 23 bytes

Port of Nick's Jelly solution

```
;£EÅgYn" #T BA0 "cXc

```

Try it

```
;£EÅgYn"..."cXc     :Implicit input of string
 £                  :Map each character X at 0-based index Y
; E                 :ASCII
   Å                :Slice of the first character (space)
    g               :Get character at index
     Y              :  Increment Y
      n             :  Subtract from
       "..."        :    Literal string (Codepoints: 32,35,29,84,32,66,65,7,48,6,32)
            c       :    Codepoint at index
             Xc     :      Codepoint of X

```

# Answer
> 1 votes
# Retina 0.8.2, 50 bytes

```
T`*j\p\ovi</`'(>DQbcu
.
$.`$* $&¶
+T`!p`~_p` .¶
¶

```

Try it online! Link includes test cases. Explanation:

```
T`*j\p\ovi</`'(>DQbcu

```

Make the transliteration as described in the question. `p` (described below) and `o` have special meaning to `T`ransliterate so they need to be quoted.

```
.
$.`$* $&¶

```

List each character on its own line, preceded by a number of spaces according to its index i.e. what the program counter would be.

```
+T`!p`~_p` .¶

```

Repeatedly cyclically decrement the last character on each line, deleting the preceding space each time, until all of the spaces have been deleted. The `p` stands for printable ASCII i.e.  `-~`, however we want the `!` to map to `~` so that is transliterated first, and then the `_` causes the space in the match  to be deleted, while the remaining characters get transliterated one character code at a time.

Join all of the characters back together.

# Answer
> 1 votes
# Charcoal, 23 bytes

```
⭆Ｓ§Φγμ⁻℅§ #{T BAe0d ℅ικ

```

Try it online! Link is to verbose version of code. Port of @Arnauld's JavaScript answer. Explanation:

```
 Ｓ                      Input string
⭆                       Map over characters and join
                     ι  Current character
                    ℅   ASCII code
        §               Cyclically indexed into
          #{T BAe0d     Literal string ` #{T BAe0d `
       ℅                ASCII code
      ⁻                 Subtract
                      κ Current index
  §                     Cyclically indexed into
    γ                   Printable ASCII
   Φ                    Filtered on
     μ                  Inner index (i.e. skip initial space)
                        Implicitly print

```

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 59 bytes

```
s=>s.Select((c,i)=>(char)(33+(" #{T BAe0d"[c%11]+94-i)%94))

```

Try it online!

Port of @Arnaulds JavaScript answer. One if the rare instances where C# is shorter!

-3 bytes thanks to @ceilingcat!

# Answer
> 1 votes
# Haskell, 135 bytes

```
t=h"*jpovi</"(fromEnum<$>"'(>DQbcu")
h(x:m)(y:n)i|i==x=y|1<2=h m n i
a n|n<33=a(n+94)|1<2=n
f=(toEnum.a<$>).(zipWith(+)[0,-1..]).(t<$>)

```

Try it online!

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


# Question
Title: Triangular Lattice Points close to the Origin
# Background

A **triangular grid** is a grid formed by tiling the plane regularly with equilateral triangles of side length 1. The picture below is an example of a triangular grid.

A **triangular lattice point** is a vertex of a triangle forming the triangular grid.

The **origin** is a fixed point on the plane, which is one of the triangular lattice points.

# Challenge

Given a non-negative integer `n`, find the number of triangular lattice points whose Euclidean distance from the origin is less than or equal to `n`.

# Example

The following figure is an example for `n = 7` (showing only 60-degree area for convenience, with point A being the origin):

# Test Cases

```
Input | Output
---------------
    0 |       1
    1 |       7
    2 |      19
    3 |      37
    4 |      61
    5 |      91
    6 |     127
    7 |     187
    8 |     241
    9 |     301
   10 |     367
   11 |     439
   12 |     517
   13 |     613
   14 |     721
   15 |     823
   16 |     931
   17 |    1045
   18 |    1165
   19 |    1303
   20 |    1459
   40 |    5815
   60 |   13057
   80 |   23233
  100 |   36295
  200 |  145051
  500 |  906901
 1000 | 3627559

```

**Hint**: This sequence is *not* OEIS A003215.

# Rules

Standard rules for apply. The shortest submission wins.

Please include how you solved the challenge in your submission.

# Answer
> 57 votes
# Python 2, 43 bytes

```
f=lambda n,a=1:n*n<a/3or n*n/a*6-f(n,a+a%3)

```

Try it online!

This is black magic.

**Offering 250 rep for a written-up proof.** See Lynn's answer for a proof and explanation.

# Answer
> 34 votes
# Haskell, 48 bytes

```
f n=1+6*sum[(mod(i+1)3-1)*div(n^2)i|i<-[1..n^2]]

```

Try it online!

Uses xnor's "black magic" formula:

$$f(n)=1+6\sum\_{a=0}^\infty \left\lfloor \frac{n^2}{3a+1}\right\rfloor - \left\lfloor \frac{n^2}{3a+2}\right\rfloor$$

A proof of its correctness, and an explanation of how xnor managed to express it in 43 bytes of Python, can be found **here**.

> Long story short: we count Eisenstein integers of norm \\$1 \le N \le n^2\\$, by factoring \\$N = (x+y\omega)(x+y\omega^\*)\\$ into Eisenstein primes and counting how many solutions for \\$(x,y)\\$ come out of the factorization. We recognize the number of solutions as being equal to
>
> $$6 \times ((\text{# of divisors of }N \equiv 1\space(\text{mod }3)) - (\text{# of divisors of }N \equiv 2\space(\text{mod }3)))$$
>
> and apply a clever trick to make that really easy to compute for all integers between \\$1\\$ and \\$n^2\\$ at once. This yields the formula above. Finally, we apply some Python golf magic to end up with the really tiny solution xnor found.

# Answer
> 30 votes
# Wolfram Language (Mathematica), ~~53~~ ~~51~~ 50 bytes

-1 byte thanks to @miles

```
Sum[Boole[x(x+y)+y^2<=#^2],{x,-2#,2#},{y,-2#,2#}]&

```

Try it online!

## How?

Instead of thinking in this:

Think of it like this:

So we apply the tranformation matrix `[[sqrt(3)/2, 0], [1/2, 1]]` to transform the second figure to the first one.

Then, we must find the circle in the triangular grid in terms of Cartesian coordinates.

```
(sqrt(3)/2 x)^2 + (1/2 x + y)^2 = x^2 + x y + y^2

```

So we find lattice points `x, y` such that `x^2 + x y + y^2 <= r^2`

For example, with `r = 3`:

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

Based on OEIS A004016.

```
1+6Sum[DivisorSum[i,#~JacobiSymbol~3&],{i,#^2}]&

```

Try it online!

# Answer
> 7 votes
### CJam (24 bytes)

```
{_*_,f{)_)3%(@@/*}1b6*)}

```

This is an anonymous block (function) which takes one argument on the stack and leaves the result on the stack. Online test suite. Note that the two largest cases are too slow.

### Explanation

alephalpha noted in a comment on the question that

> It is the sum of the first n^2+1 terms of OEIS A004016

and xnor's answer implements this sum (although I'm not sure whether their unposted proof uses it explicitly) as $$f(n) = 1 + 6 \sum\_{a=0}^\infty \left\lfloor\frac{n^2}{3a+1}\right\rfloor - \left\lfloor\frac{n^2}{3a+2}\right\rfloor$$

My proof of correctness of that formula is based on some information gleaned from alephalpha's OEIS link:

> G.f.: 1 + 6\*Sum\_{n\>=1} x^(3\*n-2)/(1-x^(3\*n-2)) - x^(3\*n-1)/(1-x^(3\*n-1)). - Paul D. Hanna, Jul 03 2011

for which the relevant reference is the paper by Hirschhorn. An elementary proof is possible using nothing more than a basic understanding of complex numbers (cube roots of unity, magnitude), the concept of generating functions, the derivative of \\$x^a\\$, and the chain rule of differentiation. In summary, we first prove from first principles the Jacobi triple-product identity $$\prod\_{k=0}^\infty (1-q^{k+1})(1 + xq^{k+1})(1 + x^{-1}q^k) = \sum\_{k\in \mathbb{Z}} q^{k(k+1)/2}x^k$$ That then bootstraps a proof that $$\sum\_{m,n \in \mathbb{Z}} \omega^{m-n} q^{m^2+mn+n^2} = \prod\_{k=1}^\infty \frac{(1-q^k)^3}{1-q^{3k}}$$ where \\$\omega\\$ is a primitive cube root of unity. The final big step is to use this to show that $$\sum\_{m,n \in \mathbb{Z}} q^{m^2+mn+n^2} = 1 + 6 \sum\_{k \ge 0} \left(\frac{q^{3k+1}}{1-q^{3k+1}} - \frac{q^{3k+2}}{1-q^{3k+2}} \right)$$

### Code dissection

```
{          e# Define a block. Stack: ... r
  _*       e#   Square it
  _,f{     e#   Map with parameter: invokes block for (r^2, 0), (r^2, 1), ... (r^2, r^2-1)
    )      e#     Increment second parameter. Stack: ... r^2 x with 1 <= x <= r^2
    _)3%(  e#     Duplicate x and map to whichever of 0, 1, -1 is equal to it (mod 3)
    @@/*   e#     Evaluate (r^2 / x) * (x mod 3)
  }
  1b6*     e#   Sum and multiply by 6
  )        e#   Increment to count the point at the origin
}

```

# Answer
> 5 votes
# APL (Dyalog Classic), 23 bytes

```
{1+6×+/-/⌊⍵÷1+3⊥¨⍳⍵2}×⍨

```

Try it online!

tribute to xnor's and lynn's answers

the last test is commented because it needs more memory, e.g. `MAXWS=200M` in the env

# Answer
> 4 votes
# , 27 bytes

```
[:+/@,*:>:(*++&*:)"{~@i:@+:

```

Try it online!

Based on JungHwan Min's method.

## Explanation

```
[:+/@,*:>:(*++&*:)"{~@i:@+:  Input: n
                         +:  Double
                      i:     Range [-2n .. 2n]
                  "{~        For each pair (x, y)
                *:             Square both x and y
              +                Add x^2 and y^2
             +                 Plus
            *                  Product of x and y
        >:                   Less than or equal to
      *:                     Square of n
     ,                       Flatten
  +/                         Reduce by addition

```

# Answer
> 3 votes
# Jelly,  ~~15~~  13 bytes

-2 thanks to Dennis (just increment the square to avoid concatenation of a zero; avoid head by using a post-difference modulo-slice rather than a pre-difference slice)

Uses the "black magic" method of honing in on the answer that was exposed by xnor in their Python answer, but uses iteration rather than recursion (and a little less calculation)

```
²:Ð€‘$Im3S×6C

```

A monadic link accepting a non-negative integer and returning a positive integer.

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

### How?

```
²:Ð€‘$Im3S×6C - Main Link: non-negative integer, n     e.g. 7
²             - square                                     49
     $        - last two links as a monad:
    ‘         -   increment                                50
  Ð€          -   map across (implicit range of) right with:
 :            -     integer division                       [49,24,16,12,9,8,7,6,5,4,4,4,3,3,3,3,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0]
      I       - incremental differences                    [-25,-8,-4,-3,-1,-1,-1,-1,-1,0,0,-1,0,0,0,-1,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1]
       m3     - every third element                        [-25,-3,-1,0,0,-1,0,0,0,0,0,0,0,0,0,0,-1]
         S    - sum (vectorises)                           -31
          ×6  - multiply by six                           -186
            C - complement (1-X)                           187

```

# Answer
> 3 votes
# Jelly, 14 bytes

```
ḤŒR+²_×ʋþ`F½»ċ

```

Uses @JungHwanMin's method.

Try it online!

# Answer
> 3 votes
# 05AB1E, ~~15~~ 14 bytes

```
nD>L÷¥3ιнO6*±Ì

```

Port of *@JonathanAllan*s Jelly answer, which in turn is a derivative from @xnor's 'black magic' formula.

Try it online or verify all test cases.

**Explanation:**

```
n               # Square the (implicit) input-integer
 D>             # Duplicate it, and increase the copy by 1
   L            # Create a list in the range [1, input²+1]
    ÷           # Integer divide input² by each of these integers
     ¥          # Take the deltas / forward differences
      3ι        # Uninterleave this list into 3 parts
                #  i.e. [a,b,c,d,e] → [[a,d],[b,e],[c]]
        н       # Pop and leave the first inner list
         O      # Take the sum of this list
          6*    # Multiply it by 6
            ±   # Take the bitwise NOT (-n-1)
             Ì  # And increase it by 2
                # (after which the result is output implicitly)

```

# Answer
> 2 votes
# JavaScript (ES6), 65 bytes

This is a port of @JungHwanMin's solution.

```
f=(n,y=x=w=n*2)=>y-~w&&(x*x+x*y+y*y<=n*n)+f(n,y-=--x<-w&&(x=w,1))

```

Try it online!

---

# Original answer (ES7), 70 bytes

Simply walks through the grid and counts the matching points.

```
f=(n,y=x=n*=2)=>y+n+2&&(x*x*3+(y-x%2)**2<=n*n)+f(n,y-=--x<-n&&(x=n,2))

```

Try it online!

# Answer
> 2 votes
# Wolfram Language (Mathematica), 39 bytes

```
Length@Solve[x(x+y)+y^2<=#^2,Integers]&

```

Try it online!

Using JungHwan Min's coordinate transformation and simply counting the solutions over the integers.

# Answer
> 1 votes
# Java 8, 65 bytes

```
n->f(n,1)int f(int n,int a){return n*n<a/3?1:n*n/a*6-f(n,a+a%3);}

```

Port of *@xnor*'s Python 2 answer.

Try it online.

# Answer
> 1 votes
# Pari/GP, 42 bytes

Using the built-in `qfrep`.

```
n->1+2*vecsum(Vec(qfrep([2,1;1,2],n^2,1)))

```

> qfrep(q,B,{flag=0}): vector of (half) the number of vectors of norms from 1 to B for the integral and definite quadratic form q. If flag is 1, count vectors of even norm from 1 to 2B.

Try it online!

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

```
n=>{int g(int x,int y)=>x*x<y/3?1:x*x/y*6-g(x,y+y%3);return g(n,1);}

```

Try it online!

Same as everyone else, unfortunately. I know there's probably a better way of writing this, but declaring and calling a lambda at the same time in c# is not exactly something I do, well, ever. Though in my defense, I can't think of a good reason (outside code golf, of course) to do so. Still, if someone knows how you can do this, let me know and/or steal the credit, I guess.

---
Tags: code-golf, math, geometry, hexagonal-grid
---