title: The coin catastrophe

text:
# Question
Title: The coin catastrophe
In Golfenhagen, The people are allowed, and encouraged, to melt down old coins for scrap metal, if the smelter can make a profit off of it. There are 5 coins that make the Golfenhagen mint. The half-penny(0.5)(H), the penny(1)(P), the tea (5)(T), the flag (10)(F), and the driver (25)(D). Golfenhagen also mints bills, in the form of 100(O), 500(E), 1000(N), and 2500(Y). Recently, the price of metals has plumetted to an all time low, and so everybody is trying to give their coins away, as they are worth less than the bills.

A humble software engineer decides to write a program that will guarantee that those who pay with cash will always get at least 9 coins back on any purchase whose net difference is bigger than 3 cents.

## Your challenge:

Take on the role of developer, and write a program that takes one input (the net difference of the money handed out and the purchase total) and outputs the correct change.

## You must:

* Make your program put out a nominal of 9 coins with any decimal, except where the difference is less than 5 cents (5).
* Make your program output a diverse set of coins, all coins MUST be able to be outputted by your program. no giving change in exclusively in halfcents.
* Use the dollar bills where applicable.
* This is a golf, the shortest code wins

## Examples:

> 301
> OODDDTTTTTP

This is a valid output. There are two dollars ("OO"), and 9 coins ("DDDTTTTTP ").

> 5693
> 2Y1E1O2D3F2T3P

This is also valid output, as it specifies the currency type and quantities, and has 10 coins.

> 412
> OOOODPP

This is not valid output, as it only uses 3 coins.

> 20
> 10P20H

This is not valid, see the second rule

Code example of a change counter for the least change possible. (as requested per cold golf)

```
package lookup;

public class Main {

    static void main(String[]s) {

        int changeincents = 53;
        int quartercount  =  0;
        int dimecount     =  0;
        int nickelcount   =  0;
        int pennycount    =  0;
        while(changeincents >= 25){//value of a quarter
            quartercount++;
            changeincents-=25;
        }
        while(changeincents >= 10){
            dimecount++;
            changeincents-=10;
        }
        while(changeincents >= 5){
            nickelcount++;
            changeincents-=5;
        }
        while(changeincents >= 1){
            pennycount++;
            changeincents--;
        }
    }
}

```

Good luck!

# Answer
> 2 votes
## Haskell, ~~177~~ 165 bytes

Thanks to @Lynn.

```
f n|n>2504='Y':f(n-2500)|n>1004='N':f(n-1000)|n>504='E':f(n-500)|n>104='O':f(n-100)|n>29='D':f(n-25)|n>14='F':f(n-10)|n>9='T':f(n-5)|n>6='P':f(n-1)|0<1=[1..2*n]>>"H"

```

In a readable format:

```
f n
  | n > 2504 = "Y" ++ f(n-2500)
  | n > 1004 = "N" ++ f(n-1000)
  | n > 504 = "E" ++ f(n-500)
  | n > 104 = "O" ++ f(n-100)
  | n > 29 = "D" ++ f(n-25)
  | n > 14 = "F" ++ f(n-10)
  | n > 9 = "T" ++ f(n-5)
  | n > 6 = "P" ++ f(n-1)
  | 0 < 1 = replicate (2*n) 'H'

```

Just give out the biggest denomination which still leaves more than 5 cents to fill with halfcoins.

---
Tags: code-golf, arithmetic
---


title: Staggered Starts

text:
# Question
Title: Staggered Starts
In races in which racers go around at least one turn of a curved track, the starting positions for each racer are staggered, so that each racer travels the same distance around the track (otherwise, the racer in the innermost lane would have a huge advantage).

Given the lengths of the major and minor axes (or semi-major and semi-minor, if you'd prefer) of an elliptical track and the number of lanes in the track, output the distances from the innermost lane's starting point that each lane should be staggered.

## Specifications

* Each lane is an ellipse with semi-major axes 5 units longer than the next-shortest lane. For simplicity, assume that the lanes have 0 width.
* The innermost lane always starts at 0, and every other starting point is a positive integer greater than or equal to the previous starting point.
* Input and output may be in any convenient and reasonable format.
* The inputs will always be integers.
* You must calculate the circumference of the track to within 0.01 units of the actual value.
* Outputs are to be rounded down to the nearest integer (floored).
* The finish line is the starting point for the innermost racer. There is only one lap in the race.
* The lengths of the axes are measured using the innermost lane of the track.
* Outputting the 0 for the innermost lane's offset is optional.

## Test Cases

Format: `a, b, n -> <list of offsets, excluding innermost lane>`

```
20, 10, 5 -> 30, 61, 92, 124
5, 5, 2 -> 31
15, 40, 7 -> 29, 60, 91, 121, 152, 183
35, 40, 4 -> 31, 62, 94

```

These test cases were generated with the following Python 3 script, which uses an approximation of the circumference of an ellipse devised by Ramanujan:

```
#!/usr/bin/env python3

import math

a = 35 # semi-major axis
b = 40 # semi-minor axis
n = 4  # number of lanes
w = 5  # spacing between lanes (constant)

h = lambda a,b:(a-b)**2/(a+b)**2
lane_lengths = [math.pi*(a+b+w*i*2)*(1+3*h(a+w*i,b+w*i)/(10+math.sqrt(4-3*h(a+w*i,b+w*i)))) for i in range(n)]

print("{}, {}, {} -> {}".format(a, b, n, ', '.join([str(int(x-lane_lengths[0])) for x in lane_lengths[1:]])))

```

The approximation used is:

Finally, here is a helpful diagram for understanding the calculations of the offsets:

# Answer
# 05AB1E, 43 bytes

```
UVFXY-nXY+WZn/3*©T4®-t+/>Z*žq*5DX+UY+V})¬-ï

```

**Explanation**

```
UV                                           # X = a, Y = b
  F                                   }      # n times do
   XY-n                                      # (a-b)^2
       XY+W                                  # Z = (a + b)
             /                               # divide (a-b)^2
           Zn                                # by (a+b)^2
              3*                             # multiply by 3
                ©                            # C = 3h
                       /                     # 3h divided by
                 T                           # 10
                      +                      # +
                  4®-t                       # sqrt(4-3h)
                        >                    # increment
                         Z*žq*               # times (a + b)*pi
                              5DX+UY+V       # increase a and b by 5
                                       )     # wrap in list of circumferences
                                        ¬-   # divide by inner circumference
                                          ï  # floor
                                             # implicitly display

```

Try it online!
> 1 votes

# Answer
# Haskell, ~~103~~ 98 bytes

```
c!d|h<-3*d*d/c/c=pi*c*(1+h/(10+sqrt(4-h)))
f a b n|x<-a-b=[floor$(a+b+10*w)!x-(a+b)!x|w<-[1..n-1]]

```
> 2 votes

# Answer
# Dyalog APL, 45 bytes

Prompts for *n*, then for *a* *b*. Requires `⎕IO←0` which is default on many systems.

```
⌊1↓(⊢-⊃)(○+×1+h÷10+.5*⍨4-h←3×2*⍨-÷+)⌿⎕∘.+5×⍳⎕

```

`⍳⎕` prompt for *n*, then give {0, 1, 2, ..., *n*−1)

multiply by five to get {0, 5, 10, ..., 5*n*−5}

`⎕∘.+` prompt for *a* and *b*, then make an addition table:
*a*, *a*+5, *a*+10, ... *a*+5*n*−5
*b*, *b*+5, *b*+10, ... *b*+5*n*−5

`(`...`)⌿` apply the parenthesised function to each vertical pair, i.e.
*f*(*a*, *b*), *f*(*a*+5, *b*+5), *f*(*a*+10, *b*+10), ..., *f*(*a*+5*n*−5, *b*+5*n*−5)
where *f*(*x*, *y*) is\*

> pi times
>
> (*x* \+ *y*) times
>
> `1+` one plus
>
> *h*(*x*, *y*) \[the function *h* will be defined later\] divided by
>
> `10+` ten plus
>
> `.5*⍨` the square-root of
>
> `4-` four minus
>
> `h←` *h*(*x*, *y*), which is
>
> three times
>
> `2*⍨` the square of
>
> (*x**y*) divided by
>
> `+` *x* \+ *y*

`(⊢-⊃)` on the result of the function applied to each pair, subtract the value of the first result

`1↓` remove the first (zero)

round down

TryAPL online!

---

\*In procedural language:

`-÷+` find the fraction of the difference between and the sum of *x* and *y*

`2*⍨` square that fraction

multiply that square by three

`h←` assign that product to *h*

`4-` subtract that product from four

`.5*⍨` take the square-root of that difference

`10+` add ten to that square-root

divide *h* by that sum

`1+` add one to that fraction

multiply that sum with the sum of *x* and *y*

multiply that product by pi
> 1 votes

# Answer
# Python 3, ~~168~~ 164 bytes

*Thanks to @Adám and @Mego for -2 bytes each*

```
from math import*
h=lambda a,b:3*(a-b)**2/(a+b)**2;C=lambda a,b:pi*(a+b)*(1+h(a,b)/(10+sqrt(4-h(a,b))))
f=lambda a,b,n:[int(C(a+i*5,b+i*5)-C(a,b))for i in range(n)]

```

A function `f` that takes input via argument and returns a list of lane offsets, including `0` for the innermost lane.

**How it works**

This uses Ramanujan's approxiamtion. We simply define functions `h` and `C` for calculating the parameter and circumference, then subtract the length of the innermost lane from the length of the current lane and floor, for all lanes.

Try it on Ideone
> 1 votes

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


title: Integer square root of integer

text:
# Question
Title: Integer square root of integer
**Problem:**

In your choice of language, write the shortest function that returns the floor of the square root of an unsigned 64-bit integer.

**Test cases:**

Your function must work correctly for all inputs, but here are a few which help illustrate the idea:

```
               INPUT ⟶ OUTPUT

                   0 ⟶  0
                   1 ⟶  1
                   2 ⟶  1
                   3 ⟶  1
                   4 ⟶  2
                   8 ⟶  2
                   9 ⟶  3
                  15 ⟶  3
                  16 ⟶  4
               65535 ⟶ 255
               65536 ⟶ 256
18446744073709551615 ⟶ 4294967295

```

**Rules:**

1. You can name your function anything you like. (Unnamed, anonymous, or lambda functions are fine, as long as they are somehow callable.)
2. Character count is what matters most in this challenge, but runtime is also important. I'm sure you could scan upwards iteratively for the answer in O(√n) time with a very small character count, but O(log(n)) time would really be better (that is, assuming an input value of n, not a bit-length of n).
3. You will probably want to implement the function using purely integer and/or boolean artithmetic. However, if you really want to use floating-point calculations, then that is fine so long as you call no library functions. So, simply saying `return (n>0)?(uint32_t)sqrtl(n):-1;` in C is off limits even though it would produce the correct result. If you're using floating-point arithmetic, you may use `*`, `/`, `+`, `-`, and exponentiation (e.g., `**` or `^` if it's a built-in operator in your language of choice, but *only exponentiation of powers not less than 1*). This restriction is to prevent "cheating" by calling `sqrt()` or a variant or raising a value to the ½ power.
4. If you're using floating-point operations (see #3), you aren't required that the return type be integer; only that that the return value is an integer, e.g., floor(sqrt(n)), and be able to hold any unsigned 32-bit value.
5. If you're using C/C++, you may assume the existence of unsigned 64-bit and 32-bit integer types, e.g., `uint64_t` and `uint32_t` as defined in `stdint.h`. Otherwise, just make sure your integer type is capable of holding any 64-bit unsigned integer.
6. If your langauge does not support 64-bit integers (for example, Brainfuck apparently only has 8-bit integer support), then do your best with that and state the limitation in your answer title. That said, if you can figure out how to encode a 64-bit integer and correctly obtain the square root of it using 8-bit primitive arithmetic, then more power to you!
7. Have fun and get creative!

# Answer
> 14 votes
# CJam, 17 (or 10) bytes

```
{_1.5#\/i}

```

Try it online by verifying the test cases:

```
[0 1 2 3 4 8 9 15 16 65535 65536 18446744073709551615]{_1.5#\/i}%N*

```

It won't pass the last test case because of rounding issues, but since `18446744073709551615` isn't an *Integer* in CJam (it's a *Big Integer*), we're still good, right?

If not, the following (and slightly longer) code will correct those errors:

```
{__1.5#\/i_2#@>-}

```

Not the shortest solution anymore, but *faaast*.

### How it works

```
__    " Duplicate the integer twice. ";
1.5#  " Raise to power 1.5. Note that, since 1.5 > 1, this doesn't break the rules. ";
\     " Swap the result with the original integer. ";
/     " Divide. ";
i     " Cast to integer. ";
_2#   " Push square of a copy. ";
@     " Rotate the orginal integer on top of the stack. ";
>-    " If the square root has been rounded up, subtract 1. ";

```

# Answer
> 10 votes
# Haskell, 28 26

I believe that this is the shortest entry from any language that wasn't designed for golfing.

```
s a=[x-1|x<-[0..],x*x>a]!!0

```

It names a function `s` with parameter `a` and returns one minus the first number whose square is greater than `a`. Runs incredibly slowly (O(sqrt n), maybe?).

# Answer
> 7 votes
### Golfscript, 17 characters

```
{).,{.*1$<},,\;(}

```

I could name my function any way I liked, but I decided not to name it at all. Add two characters to name it, add three to name it and not leave it on the stack, subtract one character if providing a full program is OK.

This abomination runs not in logaritmic time in the value of the input, not in O(sqrt n) time, it takes a whooping linear amount of time to produce the result. It also takes that much space. Absolutely horrendous. But... this is code-golf.

The algorithm is:

```
n => [0..n].filter(x => x*x < n+1).length - 1

```

# Answer
> 7 votes
# Pyth, 14 characters

```
DsbR;fgb*TTL'b

```

Provides a named function, s, which calculates the square root by filtering the list from 0 to n for the square being larger than the input, then prints the last such number. Uses no exponentiation or floats.

```
Dsb       def s(b):
R;        return last element of
f         filter(lambda T:
gb*TT                     b>=T*T,
L'b                       range(b+1))

```

Example usage:

```
python3 pyth.py <<< "DsbR;fgb*TTL'b       \msd[0 1 2 3 4 8 9 15 16 65535 65536"
[0, 1, 1, 1, 2, 2, 3, 3, 4, 255, 256]

```

# Answer
> 7 votes
# Retina (non-competing - Language is newer than the challenge), 43

While working on this answer, it occurred to me that a similar method can be used to calculate integer square roots using retina:

```
.+
$*
^
1:
+`(1+):(11\1)
1 $2:
1+:$|:1+

1+

```

This relies on the fact that perfect squares may be expressed as `1+3+5+7+...`, and by corollary that the number of terms in this expression is the square root.

Try it online. (First line added to allow multiple testcases to be run.)

Obviously due to the decimal to unary conversion, this will only work for relatively small inputs.

# Answer
> 6 votes
## Perl, 133 characters

Not the shortest by far, but uses a digit-by-digit algorithm to handle any size input, and runs in O(log n) time. Converts freely between numbers-as-strings and numbers-as-numbers. Since the largest possible product is the root-so-far with the square of a single digit, it should be able to take the square root of up to 120-bit or so numbers on a 64-bit system.

```
sub{($_)=@_;$_="0$_"if(length)%2;$a=$r="";while(/(..)/g){
$a.=$1;$y=$d=0;$a<($z=$_*(20*$r+$_))or$y=$z,$d=$_ for 1..9;$r.=$d;$a-=$y}$r}

```

Decompressed, that is:

```
sub {
  my ($n) = @_;
  $n = "0$n" if length($n) % 2; # Make an even number of digits
  my ($carry, $root);
  while ($n =~ /(..)/g) { # Take digits of $n two at a time
    $carry .= $1;         # Add them to the carry
    my ($product, $digit) = (0, 0);
    # Find the largest next digit that won't overflow, using the formula
    # (10x+y)^2 = 100x^2 + 20xy + y^2 or
    # (10x+y)^2 = 100x^2 + y(20x + y)
    for my $trial_digit (1..9) {
      my $trial_product = $trial_digit * (20 * $root + $trial_digit);
      if ($trial_product <= $carry) {
        ($product, $digit) = ($trial_product, $trial_digit);
      }
    }
    $root .= $digit;
    $carry -= $product;
  }
  return $root;
}

```

# Answer
> 5 votes
# Matlab (56) / Octave (55)

It works out the square root by using a fixed point method. It converges in maximal 36 steps (for 2^64-1 as argument) and then checks if it is the lower one of the 'possible' integer roots. As it always uses 36 iterations it has a runtime of O(1) =P

The argument is assumed to be uint64.

Matlab:

```
function x=q(s)
x=1
for i = 1:36
    x = (x+s/x)/2
end
if x*x>s
    x=x-1
end

```

Octave:

```
function x=q(s)
x=1
for i = 1:36
    x = (x+s/x)/2
end
if x*x>s
    x-=1
end

```

# Answer
> 5 votes
### Ruby — 36 characters

```
s=->n{g=n;g=(g+n/g)/2 while g*g>n;g}

```

# Answer
> 4 votes
## C99 (58 characters)

This is an example of an answer I would not consider to be a good one, although it's interesting to me from a code golf point of view because it's so perverse, and I just thought it would be fun to throw into the mix:

**Original: 64 characters**

```
uint64_t r(uint64_t n){uint64_t r=1;for(;n/r/r;r++);return r-1;}

```

The reason this one is terrible is that it runs in O(√n) time rather than O(log(n)) time. (Where n is the input value.)

**Edit: 63 characters**

Changing the `r-1` to `--r` and abutting it to `return`:

```
uint64_t r(uint64_t n){uint64_t r=1;for(;n/r/r;r++);return--r;}

```

**Edit: 62 characters**

Moving the loop increment to inside the conditional portion of the loop (note: this has unguaranteed behavior because the order of operations with respect to the preincrement operator is compiler-specific):

```
uint64_t r(uint64_t n){uint64_t r=0;for(;n/++r/r;);return--r;}

```

**Edit: 60 characters**

Adding a `typedef` to hide `uint64_t` (credit to user *technosaurus* for this suggestion).

```
typedef uint64_t Z;Z r(Z n){Z r=0;for(;n/++r/r;);return--r;}

```

**Edit: 58 characters**

Now requiring second parameter being passed as 0 in invocation of the function, e.g., `r(n,0)` instead of just `r(n)`. Ok, for the life of me, at this point I can't see how to compress this any further...anyone?

```
typedef uint64_t Z;Z r(Z n,Z r){for(;n/++r/r;);return--r;}

```

# Answer
> 4 votes
# Python (39)

```
f=lambda n,k=0:k*k>n and k-1or f(n,k+1)

```

The natural recursive approach. Counts up potential square roots until their square is too high, then goes down by 1. Use Stackless Python if you're worried about exceeding the stack depth.

The `and/or` idiom is equivalent to the ternary operator as

```
f=lambda n,k=0:k-1 if k*k>n else f(n,k+1)

```

**Edit:** I can instead get **25 chars** by exploiting the rule "you may use `*`, `/`, `+`, `-`, and exponentiation (e.g., `**` or `^` if it's a built-in operator in your language of choice, but only exponentiation of powers not less than 1)." (Edit: Apparently Dennis already found and exploited this trick.)

```
lambda n:n**1.5//max(n,1)

```

I use the integer division operator `//` of Python 3 to round down. Unfortunately, I spend a lot of characters for the case `n=0` not to give a division by 0 error. If not for it, I could do 18 chars

```
lambda n:n**1.5//n

```

The rules also didn't say the function had to be named (depending how you interpret "You can name your function anything you like."), but if it does, that's two more characters.

# Answer
> 4 votes
# Haskell, 147 138 134 128 bytes

Not the shortest code in the world, but it does run in O(log n), and on arbitrary-sized numbers:

```
h x=div(x+1)2
n%(g,s)|g*g<n=(g+s,h s)|g*g>n=(g-s,h s)|0<1=(g,0)
f(x:r@(y:z:w))|x==z=min x y|0<1=f r
s n=fst$f$iterate(n%)(n,h n)

```

This does a binary search of the range \[0..n\] to find the best lower approximation to sqrt(n). Here is an ungolfed version:

```
-- Perform integer division by 2, rounding up
half x = x `div` 2 + x `rem` 2

-- Given a guess and step size, refine the guess by adding
-- or subtracting the step as needed.  Return the new guess
-- and step size; if we found the square root exactly, set
-- the new step size to 0.
refineGuess n (guess, step)
    | square < n  =  (guess + step, half step)
    | square > n  =  (guess - step, half step)
    | otherwise   =  (guess, 0)
    where square = guess * guess

-- Begin with the guess sqrt(n) = n and step size (half n),
-- then generate the infinite sequence of refined guesses.
--
-- NOTE: The sequence of guesses will do one of two things:
--         - If n has an integral square root m, the guess
--           sequence will eventually be m,m,m,...
--         - If n does not have an exact integral square root,
--           the guess sequence will eventually alternate
--           L,U,L,U,.. between the integral lower and upper
--           bounds of the true square root.
--        In either case, the sequence will reach periodic
--        behavior in O(log n) iterations.
guesses n = map fst $ iterate (refineGuess n) (n, half n)

-- Find the limiting behavior of the guess sequence and pick out
-- the lower bound (either L or m in the comments above)
isqrt n = min2Cycle (guesses n)
    where min2Cycle (x0:rest@(x1:x2:xs))
            | x0 == x2    =   min x0 x1
            | otherwise   =   min2Cycle rest

```

*Edit:* Saved two bytes by replacing the "otherwise" clauses with "0\<1" as a shorter version of "True", and a few more by inlining g\*g.

Also, if you are happy with O(sqrt(n)) you could simply do

```
s n=(head$filter((>n).(^2))[0..])-1

```

for 35 characters, but what fun is that?

*Edit 2:* I just realized that since pairs are sorted by dictionary order, instead of doing min2Cycle . map fst, I can just do fst . min2Cycle. In the golfed code, that translates to replacing f$map fst with fst$f, saving 4 more bytes.

*Edit 3:* Saved six more bytes thanks to proudhaskeller!

# Answer
> 4 votes
# C# ~~64~~ ~~62~~ 55

Since this is a (and I'm terrible with maths), and runtime is merely a suggestion, I've done the naive approach that runs in linear time:

```
decimal f(ulong a){var i=0m;while(++i*i<=a);return--i;}

```

(test on dotnetfiddle)

Of course, it's terribly slow for larger inputs.

# Answer
> 4 votes
# C 95 ~~97~~

**Edit** Typedef, suggested by @Michaelangelo

This should be more or less a straightforward implementation of Heron algorithm. The only quirk is in computing the average avoiding integer overflow: a=(m+n)/2 does not work for biiiig numbers.

```
typedef uint64_t Z;
Z q(Z x)
{
   Z n=1,a=x,m=0;
   for(;a-m&&a-n;) n=a,m=x/n,a=m/2+n/2+(m&n&1);
   return a;
}

```

# Answer
> 4 votes
## Golfscript - 14 character

```
{.,\{\.*<}+?(}

```

Find the smallest number `i` less than the input `n` for which `n < i*i`. Return `i - 1`.

I.e. `[0..n-1].first(i => n < i*i) - 1`

Explanation for those who don't know Golfscript as well, for sample call with input `5`:

```
.        //Duplicate input.  Stack: 5 5
,        //Get array less than top of stack.  Stack: 5 [0 1 2 3 4]
\        //Switch top two elements of stack.  Stack: [0 1 2 3 4] 5
{\.*<}+  //Create a block (to be explained), and prepend the top of the stack.
         //Stack: [0 1 2 3 4]{5\.*<}
?        //Find the first element of the array for which the block is true.
         //So, find the first element of [0 1 2 3 4] for which {5\.*<} evaluates to true.
         //The inner block squares a number and returns true if it is greater than the input.
(        //Decrement by 1

```

# Answer
> 4 votes
**JavaScript ~~91~~ ~~88~~ 86:** Optimized for speed

```
function s(n){var a=1,b=n;while(Math.abs(a-b)>1){b=n/a;a=(a+b)/2}return Math.floor(a)}

```

**JavaScript 46:** Non optimized for speed

```
function s(n){a=1;while(a*a<=n)a++;return a-1}

```

Here is a JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/

# Answer
> 3 votes
## Clojure - 51 or 55 bytes

Checks all numbers from n to 0, giving the first one where `x^2 <= n`. Runtime is `O(n - sqrt n)`

Unnamed:

```
(fn[x](first(filter #(<=(* % %)x)(range x -1 -1))))

```

Named:

```
(defn f[x](first(filter #(<=(* % %)x)(range x -1 -1))))

```

Example:

```
(map (fn[x](first(filter #(<=(* % %)x)(range x -1 -1)))) (range 50))
=> (0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7)

```

# Answer
> 3 votes
# Befunge 93 - 48 Bytes or 38 Characters

```
101p&02p>02g01g:*`#v_01g1-.@
        ^  p10+1g10<

```

Try it over here.

# Answer
> 3 votes
# Cobra - 62

```
do(n as uint64)as uint64
    o=n-n
    while o*o<n,o+=1
    return o

```

# Batch - 74

```
set a=0
:1
set /ab=%a%*%a%
if %b% LSS %1 set /aa=%a%+1&goto 1
echo %a%

```

# Answer
> 3 votes
**Haskell, 53 50 49 characters, O(log n)**

```
s n=until((<=n).(^2))(\g->g-1-div(g^2-n-1)(2*g))n

```

this solution implements the newton-raphson method, although it searches integers instead of floats. wiki: http://en.wikipedia.org/wiki/Newton%27s\_method

the complexity seems to be about O(log n), but is there a proof of it? please answer in the comments.

# Answer
> 3 votes
# J (10)

Very, very, very inspired by the answer of @Dennis:

```
<.@%~^&1.5

```

And a slightly longer, but with better performance (I suspect):

```
<.@(-:&.^.)

```

`floor(halve under log)`

To execute, indented parts are input:

```
   f=:<.@%~^&1.5
   f 0 8 12 16
0 2 3 4
   g=:<.@(-:&.^.)
   g 0 8 12 16
0 2 3 4

```

# Answer
> 3 votes
# APL - 12 chars, 19 bytes

```
{⌊(⍵*1.5)÷⍵}

```

example use:

```
{⌊(⍵*1.5)÷⍵}17

```

returns 4

## Test vector

```
{⌊(⍵*1.5)÷⍵}¨0 1 2 3 4 8 9 15 16 65535 65536 18446744073709551615

```

returns

1 1 1 1 2 2 3 3 4 255 256 4294967296

Try Online

**Big thanks to**: user "ssdecontrol" for algorithm

# Answer
> 2 votes
## C99 (108 characters)

Here is my own solution in C99, which is adapted from an algorithm in an article on Wikipedia. I'm sure it must be possible to do much better than this in other languages.

Golfed:

```
uint64_t s(uint64_t n){uint64_t b=1,r=0;while(n/b/4)b*=4;for(;b;b/=4,r/=2)n>=r+b?r+=b,n-=r,r+=b:0;return r;}

```

Partially golfed:

```
uint64 uint64_sqrt(uint64 n)
{
  uint64 b = 1, r = 0;
  while (b <= n / 4)
    b *= 4;
  for (; b; b /= 4, r /= 2)
    if (n >= r + b)
      { r += b; n -= r; r+= b; }
  return r;
}

```

Ungolfed:

```
uint64_t uint64_sqrt(uint64_t const n)
{
  uint64_t a, b, r;

  for (b = 1; ((b << 2) != 0) && ((b << 2) <= n); b <<= 2)
    ;

  a = n;
  r = 0;
  for (; b != 0; b >>= 2)
  {
    if (a >= r + b)
    {
      a -= r + b;
      r = (r >> 1) + b;
    }
    else
    {
      r >>= 1;
    }
  }

  // Validate that r² <= n < (r+1)², being careful to avoid integer overflow,
  // which would occur in the case where n==2⁶⁴-1, r==2³²-1, and could also
  // occur in the event that r is incorrect.
  assert(n>0? r<=n/r : r==0);  // Safe way of saying r*r <= n
  assert(n/(r+1) < (r+1));     // Safe way of saying n < (r+1)*(r+1)

  return r;
}

```

# Answer
> 2 votes
# JavaScript 73 81 (to comply with 64-bit numbers requirement)

`n=prompt();g=n/3;do{G=g,g=(n/g+g)/2}while(1E-9<Math.abs(G-g))alert(Math.floor(g))`

Implementing *Heron of Alexandria's* algorithm...

# Answer
> 2 votes
## Powershell (52) Limited to Int32 (-2,147,483,648 to 2,147,483,647)

```
function f($n){($n/2)..0|%{if($_*$_-le$n){$_;exit}}}

```

I'm screaming at Powershell right now trying to make the last test case work but no matter what I do Powershell winds up using the pipeline variable $\_ as an Int32, and I can't find a way around it right now.

So I'll just limit my answer for now. If I can find a better way to handle uint64s I will edit. (The last test case is too big for Powershell's normal Int64 type, by the way!)

Here are a few test cases (with a bit of extra output I used to track the time)

```
f 17
4
Elapsed Time: 0.0060006 seconds

f 65
8
Elapsed Time: 0.0050005 seconds

f 65540
256
Elapsed Time: 1.7931793 seconds

f 256554
506
Elapsed Time: 14.7395391 seconds

```

I don't know my O()s, but this seems like a pretty dramatic jump.

# Answer
> 2 votes
Caveat: as of 2011, R had no built-in support for 64 bit integers as I had assumed it did. These answers might be invalid on that technicality, but then again R has changed a lot in the last 3 years.

---

## R, 85

Using Newton's method:

```
function(n){s=F
x=n
y=(1/2)*(x+n/x)
while(abs(x-y)>=1){x=y
y=(1/2)*(x+n/x)}
trunc(y)}

```

which converges quadratically. +2 characters to assign the function to a variable for benchmarking:

```
microbenchmark(q(113424534523616))
# Unit: microseconds
#                expr    min      lq median      uq    max neval
#  q(113424534523616) 24.489 25.9935 28.162 29.5755 46.192   100

```

---

## R, 37

Brute force:

```
function(n){t=0
while(t^2<n) t=t+1
t}

```

And the same check:

```
microbenchmark::microbenchmark(q(113424534523616),times=1)
# Unit: seconds
#                 expr      min       lq   median       uq      max neval
#   q(113424534523616) 4.578494 4.578494 4.578494 4.578494 4.578494     1

```

---

## R, 30

The cheap/brilliant exponentiation trick:

```
function(n) trunc(n^(1.5)/n)

```

which also happens to be very fast (although not as fast as the built-in):

```
microbenchmark(q(113424534523616),sqrt(113424534523616))
# Unit: nanoseconds
#                   expr min    lq median    uq  max neval
#     z(113424534523616) 468 622.5  676.5 714.5 4067   100
#  sqrt(113424534523616)  93 101.0  119.0 160.5 2863   100

```

# Answer
> 2 votes
# C, 38

```
f(n){int m;while(++m*m<=n);return--m;}

```

Translation of my Forth submission. Slow but correct. O(√n). Tested on OS X (64 bit).

# Answer
> 2 votes
# dc, 50 bytes

```
dc -e"?dsist[lt2/dstd*li<B]dsBx[lt1+dstd*li!<A]dsAxlt1-f"

```

Spaced out and explained:

```
               # The idea here is to start with the input and reduce it quickly until it is
               # less than what we want, then increment it until it's just right
?              # Take input from stdin
d si st        # Duplicate input, store in `i' and in `t'
[              # Begin macro definition (when I write in dc, "macro"=="function")
 lt            # Load t, our test term
 2/            # Divide t by two
 d st          # Store a copy of this new term in `t'
 d*            # Duplicate and multiply (square)
 li<B          # Load i; if i<(t^2), execute B
] d sB x       # Duplicate, store function as `B', and execute
               # Loop ends when t^2 is less than i
[              # Begin macro definition
 lt            # Load t, our test term
 1+            # Increment
 d st          # Store a copy of this new term in `t'
 d*            # Duplicate and multiply (square)
 li!<A         # Load i; if i>=(t^2), execute A
] d sA x       # Duplicate, store function as `A', and execute
               # Loop ends when t^2 == i+1
lt 1- f        # Load t, decrement, and dump stack

```

# Answer
> 2 votes
# C, ~~139~~ ~~137~~ 136 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in `O(log n)` time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the `a=32` part is changed to `a=NUMBITS/2`.

```
typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;t++<r?y++,r-=t++:t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}

```

# Answer
> 1 votes
**C - 50 (61 without global)**

```
typedef uint64_t T;T n,i;f(){while(++i*i<=n);--i;}

```

It use global variables as parameter and return value to save space.

No global version :

```
typedef uint64_t T;T f(T n){T i=0;while(++i*i<=n);return--i;}

```

# Answer
> 1 votes
## C++ 125

```
int main()
{
uint64_t y;cin>>y;
double x=y/2,d,z;
while((d=(x*x-y))>0.5)
{
d<0?x+=0.5:x-=0.5;
}
cout<<(uint64_t)x;
}

```

# Answer
> 1 votes
# Forth, 43

```
: f -1 begin 1+ 2dup dup * - 0< until 1- ;

```

O(√n)

# Answer
> 1 votes
## GolfScript (15 chars)

Pick any one of

```
{):x,{.*x<},,(}
{:x,{).*x>!},,}
{.,\{1$)/<}+,,}
{,.,{1$)/<}+,,}

```

I've followed the other GolfScript answers in interpreting "*You can name your function anything you like*" as meaning "*You may leave a block which does the job on the stack*". These are currently the shortest GolfScript answers which correctly handle inputs `0` and `1`.

Online demo

# Answer
> 1 votes
# JavaScript (ES6) 61 bytes

```
n=>n&&eval('g=n;while(Math.abs(g-(g=(n/g+g)/2))>1e-9);g-g%1')

```

## Tests:

```
f=n=>n&&eval('g=n;while(Math.abs(g-(g=(n/g+g)/2))>1e-9);g-g%1')

console.log(f(0) == 0);
console.log(f(1) == 1);
console.log(f(2) == 1);
console.log(f(3) == 1);
console.log(f(4) == 2);
console.log(f(8) == 2);
console.log(f(9) == 3);
console.log(f(15) == 3);
console.log(f(16) == 4);
console.log(f(65535) == 255);
console.log(f(65536) == 256);
console.log(f(18446744073709551615) == 4294967296);
```

I hope you can excuse the last test, since JavaScript interprets the literal value `18446744073709551615` as `18446744073709552000`. This is because JavaScript uses the IEEE 754 standard, which can only store every consecutive positive integer up to `9007199254740992` (2^53).

An alternative method that's even shorter is below. However, it does not meet the speed optimization requirements:

### JavaScript (ES6) 30 bytes (non-competing)

```
n=>eval('for(a=0;a*a<=n;)a++')

```

## Tests:

```
f=n=>eval('for(a=0;a*a<=n;)a++')

console.log(f(0) == 0);
console.log(f(1) == 1);
console.log(f(2) == 1);
console.log(f(3) == 1);
console.log(f(4) == 2);
console.log(f(8) == 2);
console.log(f(9) == 3);
console.log(f(15) == 3);
console.log(f(16) == 4);
console.log(f(65535) == 255);
console.log(f(65536) == 256);
// console.log(f(18446744073709551615) == 4294967296)

f=n=>eval('for(a=4294967290;a*a<=n;)a++')

console.log(f(18446744073709551615) == 4294967296);
```

The last test case hypothetically evaluates to true, but would take around a month to execute.

# Answer
> 1 votes
# Dyalog APL, 8 bytes

```
⌊*∘1.5÷⊢

```

<sup>*n*<sup>³⁄₂</sup></sup><sub>*n*</sub>⌋ as follows:
`*∘1.5` the power-1.5 function
the pass-through function
`(*∘1.5) ÷ ⊢` is the power-1.5 divided by the number itself
floor

Uses `⎕DIV←1` which often is default.

For the fun of it, here is a generalized solution that lets you calculate any root without raising to any power \< 1:

```
⌊⊣(*÷⊣)(1+(÷⊢))

```

# Answer
> 1 votes
## Swift 2, 43 bytes

```
let f={a in (0..<a).filter{$0*$0<=a}.last!}

```

Try here. There is a caveat - it won't compile unless the function is called, ie `f(255)`, as type inference is unable to infer the return type.

# Answer
> 1 votes
## Mathematica, 20

```
⌊#^1.5/1~Max~#⌋&

```

# Answer
> 1 votes
## Pyke, 7 bytes (noncompeting)

```
#Xt)ltt

```

Try it here!

Finds the first number where `i*i>=n` and takes 2 from the number of numbers it had to check to get there

# Answer
> 1 votes
# C++17, 80 bytes

```
auto f(auto n){auto x=1ul<<32,a=x-x;for(;x/=2;)a+=(a+x)*(a+x)<=n?x:0;return a;};

```

## Explanation

This computes one bit per iteration, accumulating the result in `a`.

## Tests

```
int main()
{
    return
        + (f(0) != 0)
        + (f(1) != 1)
        + (f(1) != 1)
        + (f(2) !=  1)
        + (f(3) !=  1)
        + (f(4) !=  2)
        + (f(8) !=  2)
        + (f(9) !=  3)
        + (f(15) !=  3)
        + (f(16) !=  4)
        + (f(65535) != 255)
        + (f(65536) != 256)
        + (f(18446744073709551615ul) != 4294967295)
        ;
}

```

# Answer
> 0 votes
# Tellurium(non-competing), 8 bytes

```
@s|Iqg^`

```

This defines a function named `s` that converts input to an integer (`I`), calculates the square root (`q`) and rounds it to the floor (`g`)

The function can be called using `=s.`

# Alternatively, 7 bytes

```
{Iqg^}f

```

This one defines an anonymous function that can be called using `ä`.

# Answer
> 0 votes
# Lua, 74 bytes

```
n=io.read() if n==0 then print(0) os.exit() end print(math.floor(n^1.5/n))

```

Try it online!

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


title: Implement this key cipher

text:
# Question
Title: Implement this key cipher
# Implement this key cipher

## Goal

Use the algorithm (explained in the Algorithm section) to implement a certain cipher.

The program must read input from STDIN or the closest available equivalent, use the algorithm to generate the ciphertext and a key.

The ciphertext and the key will be written to STDOUT or the closest available equivalent. Any format is allowed, as long as it outputs the ciphertext and the key.

## Algorithm

Convert the characters in the string into the respective ASCII values. For example:

`Hello -> 72 101 108 108 111`

Next, you will need to generate a key as long as the string with random numbers in the range of 0-9.

`Hello -> 62841`

Add the integers in the random number sequence to the ASCII values of the string. In the above examples, 72 would become 78, and 101 would become 104.

`72 + 6 = 78, 101 + 2 = 103, 108 + 8 = 116, etc`

Next, convert the new values back to characters. In the above examples, the text `Hello` has become `Ngtpp`.

## Examples

(These are simply examples of what the output *might* look like. The output can and will vary.)

```
Hello World

Lfrlu)_supg
41606984343

```

---

```
This will be encoded

Zhjs$~koo gj$iuhofgj
60104723305544750226

```

## Rules

* You can assume that the input will only contain characters in the range a-z, A-Z, and spaces.
* Submissions must be full programs or functions.
* Submissions will be scored in bytes.
* Standard loopholes are forbidden.
* This is code-golf, so the shortest code wins.

---

(This is one of my first challenges, if there's something wrong with it, feel free to tell me how I could improve it.)

# Answer
# Jelly, ~~12~~ 9 bytes

```
⁵ṁX€’Ṅ+OỌ

```

Try it online!

### How it works

```
⁵ṁX€’Ṅ+OỌ  Main link. Argument: s (string)

⁵             Set the return value to 10.
 ṁ            Mold; create an array of 10's with the length of s.
  X€          Pseudo-randomly pick a integer between 1 and 10, for each 10.
    ’         Decrement, so the integers fall in the range [0, ..., 9].
     Ṅ        Print the key, as an array, followed by a linefeed.
      +O      Add the integers to the ordinals (code points) of s.
        Ọ     Unordinal; convert back to characters.

```
> 5 votes

# Answer
# Python 3, 130 bytes

*Thanks to @Rod for pointing out a bug*

```
from random import*
def f(x):l=10**len(x);k=str(randint(0,l-1)+l)[1:];print(''.join(chr(ord(i)+int(j))for i,j in zip(x,k))+'\n'+k)

```

A function that takes input via argument as a string and prints to STDOUT.

**How it works**

```
from random import*  Import everything from the random module
def f(x):            Function with input string x
l=10**len(x)         Define l for later use as 10^length(x)
randint(0,l-1)+l     Generate a random integer in the range [0, l-1] and add l, giving a
                     number with l+1 digits...
k=str(...)[1:]       ...convert to a string and remove the first character, giving a key of
                     length l that can include leading zeroes, and store in k
for i,j in zip(x,k)  For each character pair i,j in x and k:
chr(ord(i)+int(j))    Find the UTF-8 code-point (same as ASCII for the ASCII characters),
                      add the relevant key digit and convert back to character
''.join(...)         Concatenate the characters of the ciphertext
print(...+'\n'+k)    Add newline and key, then print to STDOUT

```

Try it on Ideone
> 5 votes

# Answer
# Pyth - 16 bytes

Waiting for decision by OP on the output formats.

```
sCM+VCMQKmOTQjkK

```

Test Suite.
> 3 votes

# Answer
## Actually, 17 bytes

```
;`X9J`M;(O¥♂cΣ@εj

```

Try it online!

Explanation:

```
;`X9J`M;(O¥♂cΣ@εj
;                  dupe input
 `X9J`M            for each character in input copy:
  X9J                discard the character, push a random integer in [0, 9]
       ;           duplicate the offset array
        (O         bring input to top of stack, ordinal array
          ¥♂c      pairwise addition with offset array, turn each ordinal into a character
             Σ     concatenate
              @εj  concatenate the copy of the offset array

```
> 3 votes

# Answer
## PowerShell v2+, ~~79~~ 77 bytes

```
param($n)-join(($x=[char[]]$n|%{0..9|Random})|%{[char]($_+$n[$i++])});-join$x

```

Takes input `$n`, loops over every character and gets a `Random` element from `0..9` each iteration. Stores those numbers (as an array) into `$x`. Pipes that array into another loop. Each iteration, takes the current element `$_`, adds it to the positional char sliced out of `$n` (implicit char-to-int cast), then re-casts as `[char]`. Leaves that on the pipeline. That's encapsulated in parens and `-join`ed together to form the word. That's left on the pipeline. Additionally, the number `$x` is also `-join`ed together and left on the pipeline. Those are implicitly printed with a `Write-Output` at the end of execution, which results in them being printed with a newline by default.

### Example

```
PS C:\Tools\Scripts\golfing> .\implement-this-key-cipher.ps1 'Hello World!'
Lhoot(Yt{mf"
433358259121

```
> 2 votes

# Answer
# CJam - 14 bytes

When I saw the ascii code math, I knew I had to write a CJam answer.

```
q_{;Amr}%_@.+p

```

Try it online here.
> 2 votes

# Answer
# MATL, 13 bytes

```
"10r*]v!kGy+c

```

The output looks like this:

```
9 5 8 2 1
Qjtnp

```

Try it online!

Explanation:

```
"    ]          % For each character:
 10             % Push a 10 onto the stack
   r            % Push a random float in [O, 1)
    *           % Multiply. This essentially the same thing as pushing a number in [0, 10)
      v!k       % Join all of these together, and take the floor
         G      % Push the input again
          y     % Duplicate the array of random numbers
           +    % And add these together. Since MATL treats strings as an array of chars, we don't need to explicitly convert types
            c   % Display as string

```
> 2 votes

# Answer
## 05AB1E, ~~18~~ 17 bytes

```
vžh.RDyÇ+ç`?}J¶?,

```

**Explanation**

```
v           }      # for each char in input
 žh.RD             # push 2 copies of a random number in [0..9]
      yÇ+          # add 1 copy to the current chars ascii value
         ç`?       # convert to char, flatten and print
             J     # join stack (which contain the digits of the key)
              ¶?,  # print a newline followed by the key

```

Try it online
> 2 votes

# Answer
## C#, ~~252~~ ~~247~~ ~~245~~ ~~232~~ 216 Bytes

The size is pretty bad compared to the other solutions but nevertheless...

```
using System;using System.Linq;class p{static void Main(){var c="";var i=Console.ReadLine();var r=new Random();for(int b=0;b++<i.Count();){int d=r.Next(10);Console.Write((char)(i[b]+d));c+=d;}Console.Write("\n"+c);}}

```

This is my second ever answer to a codegolf and I'm quite a beginner considering C# so I'd appreciate to hear how to get it shorter :)

Ungolfed:

```
using System;
using System.Linq;

class p
{
    static void Main()
    {
        var c = "";
        var i = Console.ReadLine();
        var r = new Random();
        for (int b = 0; b++ < i.Count();)
        {
            int d = r.Next(10);
            Console.Write((char)(i[b] + d));
            c += d;
        }
        Console.Write("\n" + c);
    }
}

```
* Saved 5 Bytes thanks to @FryAmTheEggman
* Saved 2 Bytes thanks to @theLambGoat
* Saved 7 Bytes by removing `static` from class p
* Saved 24 Bytes thanks to @milk
> 2 votes

# Answer
# CJam, 11 bytes

```
Nq{Amr_o+}/

```

Try it online!

### How it works

```
N            Push a linefeed on the stack.
 q           Read all input from STDIN and push it on the stack.
  {      }/  For each character in the input:
   Amr       Pseudo-randomly pick an integer in [0 ... 9].
      _o     Print a copy.
        +    Add the integer to the character.
             (implicit) Print the linefeed, followed by the modified characters.

```
> 2 votes

# Answer
# Python 3, 112 bytes

c is a function that returns the encrypted text and the key

```
from random import*
c=lambda t:map(''.join,zip(*[(chr(a+b),str(b))for a,b in((ord(i),randint(0,9))for i in t)]))

```

Here is a code that does the same thing and is a bit more readable

```
def encrypt(text):
    # keep the codes of the letters in the input and a random key
    # that will be used later to encrypt this letter
    letter_and_key = ((ord(letter),randint(0,9)) for letter in text)

    # encrypt the letter and keep the key used as a string
    output_and_key = [(chr(letter_code+key), str(key))
                      for letter_code, key in letter_and_key]

    # At this point the values are kept in the format:
    # [(firstletter, firstkey), (secondletter, secondkey), ...]

    # to reorder the list to be able to output in the format "text key"
    text, key = map(''.join, zip(*output_and_key))

    # same as print(*output_and_key)
    return text, key

```

Output:

```
>>> text, key = c('Hello World')
>>> print(text, key, sep='\n')
Liuot#`oylk
44935390707

```
> 2 votes

# Answer
## PHP, ~~63~~ ~~86~~ 82 bytes

Edit: forgot to print the key...

*Thanks to Alex Howansky for saving me 4 bytes.*

```
for(;$i<strlen($a=$argv[1]);$s.=$r)echo chr(ord($a[$i++])+$r=rand(0,9));echo"
$s";

```

Input is given through a command line argument. Takes each character in the string and adds a random int from 0-9 to its ASCII code, then converts the code back to ASCII. Every random number is appended to `$s`, which is printed at the end.
> 1 votes

# Answer
# J, 32 bytes

```
<@:e,:~[:<[:u:3&u:+e=.[:?[:$&10#

```

python equivalent:

```
from random import randint
def encrypt(message):
    rand_list = list(map(lambda x: randint(0, 9), range(len(message))))
    return (''.join(list(map(lambda x,y: chr(x+y), rand_list, map(ord, message)))), rand_list)

```
> 1 votes

# Answer
# Perl, 34 bytes

Includes +1 for `-p`

```
#!/usr/bin/perl -p
s%.%$\.=$==rand 10;chr$=+ord$&%eg

```
> 1 votes

# Answer
# Perl, 65 bytes

```
for(split'',$ARGV[0]){$;.=$a=int rand 9;$b.=chr$a+ord}say"$b\n$;"

```

Took me awhile to figure out how to get the input without a new line at the end. Takes it as a command line arg
> 0 votes

# Answer
# Python 2, ~~84~~ 99 bytes

```
def f(x):y=`id(x)**len(x)`[1:len(x)+1];return''.join(map(chr,[ord(a)+int(b)for a,b in zip(x,y)])),y

```

Uses the `id()` value of the string to generate random numbers.

Try it
> 0 votes

# Answer
# Senva, 74 bytes

Here is the shortest program I've made :

```
2'(`>0.>{@}0'{v}2-2'0,{@}1'{v}0'{+}{'}9%+{^}{1-}1'"{+}{~}>$10.~0'2+"0,-:>$

```

A little explanation ? (Note: **BM** means *Back-Memory*) :

```
// === Input and informations storing ===

2'  // Go to the 3rd cell (the two first will be used to store informations)
(   // Ask the user for a string (it will be stored as a suite of ASCII codes)
`   // Go the end of the string
>   // Make a new cell
0.  // Put a 0 to mark the end of the string
>   // Make a new cell, here will be stored the first random number
{@} // Store its adress in BM
0'  // Go to the 1st cell
{v} // Paste the adress, now the 1st cell contains the adress of the first random number
2-  // Subtract 2 because the string starts at adress 2 (the 3rd cell)
2'  // Go to the 3rd cell (where the string begins)

// === String encryption and displaying ===

0,  // While the current cell doesn't contain 0 (while we didn't reach the string's end)
  {@}  // Store the character's adress into the memory
  1'   // Go to the 2nd cell
  {v}  // Paste the value, now the 1st cell contains the adress of the current char
  0'   // Go to the 1st cell
  {+}  // Add the adress of the first random number to the current char adress
  {'}  // Go to this adrses
  9%+  // A random number between 0 and 10
  {^}  // Store this number in BM
  {1-} // Decrease BM (random number between 0 and 9)
  1'   // Go to the 1st cell
  "    // Go to the adress pointed by the cell (the adress of the current char)
  {+}  // Add it to the random number value
  {~}  // Display it as an ASCII character
  >    // Go to the next cell (the next character)
$   // End of the loop
10. // Set the new line's ASCII code into the current cell (which is now useless, so it can be overwritten)
~   // Display the new line
0'  // Go to the first cell
2+  // Add 2 to the adress, because we are not in the string loop : we cancel the 2 substraction
"   // Go to the pointed adress (the first random number's one)

// === Display the random numbers ===

0,  // While we didn't reach the end of the random numbers suite
    // That was why I stored numbers between 1 and 10, the first equal to 0 will be the end of the suite
  - // Decrease it (number between 0 and 9)
  : // Display the current random number as an integer
  > // Go to the next cell (the next number)
$ // End of the loop

```

That appears bigger now, true :p ? Maybe it's possible to optimize this code, but for the moment that's the shortest I've found.
> 0 votes

# Answer
# C#, 174 bytes

```
using static System.Console;class b{static void Main(){var c=new System.Random();var d="\n";foreach(var e in ReadLine()){var f=c.Next(10);Write((char)(e+f));d+=f;}Write(d);}}

```

Ungolfed:

```
using static System.Console;

class b
{
    static void Main()
    {
        var c = new System.Random();
        var d = "\n";

        foreach (var e in ReadLine())
        {
            var f = c.Next(10);
            Write((char)(e + f));
            d += f;
        }

        Write(d);
    }
}

```

Pretty straightforward, really.
> 0 votes

# Answer
# Perl 6: 55 or 70 bytes

As an anonymous function that takes a string parameter, and returns a list of two strings *(54 characters, 55 bytes)*:

```
{my @n=^9 .roll(.ords);(.ords Z+@n)».chr.join,@n.join}

```

As a program that reads from STDIN and writes to STDOUT *(69 characters, 70 bytes)*:

```
my @a=get.ords;my @n=^9 .roll(@a);say (@a Z+@n)».chr.join;say @n.join

```
> 0 votes

---
Tags: code-golf, random, encryption
---


title: How secure are my locks?

text:
# Question
Title: How secure are my locks?
You have been assigned the task of installing new locks to the company's building. However, the locks you use are quite unusual: they require some combination of keys to open. Now, you want to figure out which locks are the most secure, so you can prioritize the most important locations.

The keys you use are numbered by security: key 1 is the weakest and could be given to the cat, key 2 is a bit better, and so on.

The locks are defined by AND and OR expressions between the keys. For example, a lock might open with just key 1, so it's defined by the string `1`; another one might require key 3 and either key 1 or 2, so it's defined by `3 & (1 | 2)`. A lock opens if the expression is truthy when all key numbers are substituted for true/false depending on if the user possessed the respective keys. XOR and NOT are not needed, since possessing extra keys doesn't matter.

The security of a lock is defined by the weakest key combination required to open the lock. One way to compute this is the following algorithm:

1. Find all the subsets of the keys that open the lock.
2. Sort each combination descending (from the strongest key to the weakest).
3. Sort the combinations lexicographically ascending.
4. The **security value** of the lock is now the first item in the list.

In order to compare two locks, one just has to compare their security values lexicographically: the larger one is more secure.

## Challenge

You are given a list of expressions that define locks. Your task is to sort the locks based on security in **descending order**.

Standard rules apply.

## Input

You will receive a list of locks as input.

* The list may be taken as lines or in the list representation of your choice.
* Each lock can be given either as a string like `1 & ((2 | 3) & 4)` or a nested list like `[1, "&", [[2, "|", 3], "&", 4]]`.
    + Any whitespace in the string is optional, and all operations except for the outermost one will be wrapped in parentheses.
    + You are free to choose the list format that suits your needs.
* Each operator will have two operands.
* Key numbers will range from 1 to 99 and there will not be unused keys between 1 and the maximum used key.

## Output

You will output the same list you got as input, sorted by security in descending order. All formats listed above are valid. If two locks are equally secure, their order does not matter.

## Test cases

The test cases are in the "list" format. The outputs include the security values of each lock for reference; you should **not** output them.

**Input:**

```
[1]
[2]
[3]
[1, "&", 2]
[1, "&", 3]
[3, "&", 2]
[1, "|", 2]
[2, "|", 3]
[[1, "&", 2], "|", 3]
[[2, "|", 3], "&", 3]

```

**Result:**

```
[3, "&", 2]            # (3, 2)
[1, "&", 3]            # (3, 1)
[[2, "|", 3], "&", 3]  # (3)
[3]                    # (3)
[1, "&", 2]            # (2, 1)
[[1, "&", 2], "|", 3]  # (2, 1)
[2]                    # (2)
[2, "|", 3]            # (2)
[1]                    # (1)
[1, "|", 2]            # (1)

```

**Input:**

```
[[[6, '|', [[10, '|', 1], '&', [3, '&', 3]]], '|', 10], '&', [[12, '&', [9, '|', 7]], '|', [[3, '|', 8], '&', [[10, '|', [[1, '&', 3], '&', 9]], '|', [[2, '|', 1], '&', 1]]]]]
[[7, '|', 9], '&', [[5, '|', 10], '&', [[12, '|', 3], '&', 4]]]
[7, '|', 7]
[[[5, '|', [1, '|', 9]], '&', [[7, '&', [[6, '&', [1, '|', 7]], '|', 2]], '|', 5]], '&', [[[[8, '&', 6], '&', 1], '&', 5], '&', [10, '|', [11, '&', [3, '&', 6]]]]]
[[[[2, '&', [6, '&', 8]], '|', [[4, '|', 4], '|', [[5, '&', 4], '|', [[[1, '|', 5], '|', 1], '&', 7]]]], '&', [[[9, '|', [3, '&', 7]], '|', [9, '|', 5]], '&', [[[[8, '|', 11], '|', 8], '|', 2], '|', 2]]], '&', [[3, '|', 6], '&', 9]]
[[12, '|', [5, '&', [[12, '&', 3], '|', [9, '&', 1]]]], '|', [10, '&', [[8, '|', 9], '&', [[[8, '|', 3], '|', 8], '|', 11]]]]
[[9, '|', 11], '&', [[[11, '&', 12], '|', 10], '&', [3, '&', 12]]]
[[[5, '&', 9], '&', [10, '&', 2]], '|', [10, '|', 10]]
[[6, '&', 4], '&', [4, '|', 11]]
[[[[11, '&', [[[[5, '|', 11], '&', [10, '|', 7]], '&', 2], '|', 2]], '|', 12], '|', 5], '&', [[[2, '&', [5, '|', 9]], '&', 4], '&', [6, '|', [3, '&', 2]]]]

```

**Result:**

```
[[9, '|', 11], '&', [[[11, '&', 12], '|', 10], '&', [3, '&', 12]]] # (12, 10, 9, 3)
[[[5, '|', [1, '|', 9]], '&', [[7, '&', [[6, '&', [1, '|', 7]], '|', 2]], '|', 5]], '&', [[[[8, '&', 6], '&', 1], '&', 5], '&', [10, '|', [11, '&', [3, '&', 6]]]]] # (10, 8, 6, 5, 1)
[[[5, '&', 9], '&', [10, '&', 2]], '|', [10, '|', 10]] # (10)
[[12, '|', [5, '&', [[12, '&', 3], '|', [9, '&', 1]]]], '|', [10, '&', [[8, '|', 9], '&', [[[8, '|', 3], '|', 8], '|', 11]]]] # (9, 5, 1)
[[[[2, '&', [6, '&', 8]], '|', [[4, '|', 4], '|', [[5, '&', 4], '|', [[[1, '|', 5], '|', 1], '&', 7]]]], '&', [[[9, '|', [3, '&', 7]], '|', [9, '|', 5]], '&', [[[[8, '|', 11], '|', 8], '|', 2], '|', 2]]], '&', [[3, '|', 6], '&', 9]] # (9, 4, 3, 2)
[[7, '|', 9], '&', [[5, '|', 10], '&', [[12, '|', 3], '&', 4]]] # (7, 5, 4, 3)
[7, '|', 7] # (7)
[[6, '&', 4], '&', [4, '|', 11]] # (6, 4)
[[[[11, '&', [[[[5, '|', 11], '&', [10, '|', 7]], '&', 2], '|', 2]], '|', 12], '|', 5], '&', [[[2, '&', [5, '|', 9]], '&', 4], '&', [6, '|', [3, '&', 2]]]] # (5, 4, 3, 2)
[[[6, '|', [[10, '|', 1], '&', [3, '&', 3]]], '|', 10], '&', [[12, '&', [9, '|', 7]], '|', [[3, '|', 8], '&', [[10, '|', [[1, '&', 3], '&', 9]], '|', [[2, '|', 1], '&', 1]]]]] # (3, 1)

```

This program can be used to generate additional test cases. It also outputs the security values of each lock generated.

# Answer
# Perl 6: ~~132~~ 124 bytes

```
{reverse .sort: {use MONKEY-SEE-NO-EVAL;my &infix:<|>={|$^a,|$^b}
min map *.flat.sort.squish.reverse,EVAL .trans('&'=>'X')}}

```

A lambda that takes a list of lines as input.

It generates the sort key for each line as follows:

* Declare `|` as a list concatenation operator within the lexical scope.
* Replace `&` in the string with `X`, the Perl 6 cartesian product operator.
* Eval the string *(which unfortunately requires the ghastly `MONKEY-SEE-NO-EVAL` pragma)*, yielding all possible combinations of keys that open the door.
* Post-process the lists and pick the "least secure" combination.
> 2 votes

# Answer
# Python, ~~253~~ 246 bytes

```
m=lambda a,b:min(sorted(a),sorted(b))
def w(s):
    if type(s)!=list:return[s]
    if len(s)==1:return s
    k=w(s[0])
    z=w(s[2])
    if s[1]=="|":return m(k,z)
    return k+z
r=[]
for i in n:r+=[(i,sorted(w(i),reverse=1))]
sorted(r,reverse=1,key=lambda x:x[1])

```
> 2 votes

---
Tags: code-golf, array, logic
---


title: Exploring 10-Rep Questions

text:
# Question
Title: Exploring 10-Rep Questions
**Related**

## Introduction

As it happens, someone put forward the idea that, since PPCG has graduated, up votes on questions should be worth 10 rep. As a result, I started wondering how much rep I would have if it had always been 10 rep.

## Challenge

Given **a PPCG user's id as input**, output how much total rep the user would have if question up votes were worth +10.

## Example Calculation

I, Beta Decay (user id 30525), have **6744** rep. **3488** of that was earned by posting questions (calculated by subtracting the total rep lost from downvotes from the total rep gained from upvotes).

Firstly, we subtract 3488 from 6744, giving us 3256 rep, the amount earned from posting answers.

Next, we find out how much I would have earned from 10 rep questions by simply multiplying 3488 by 2, giving us 6976.

Finally, we add 3256 and 6976 together to get a final answer of 10232 rep.

A simplified method is to take the total, 6744 and add the rep from questions, 3488, giving is 10232 rep.

***For continuity, you must use the method described above***

## Examples

Note that these examples are subject to change and are unlikely to stay current.

### Helka Homba (UID 26997)

```
71398

```

### Martin Ender (UID 8478)

```
121077

```

### Downgoat (UID 40695)

```
21894

```

## Rules

Internet access is allowed. Similarly, access to the Stack Exchange API is allowed. However, URL shorteners are disallowed.

T-SQL entrants using the Stack Exchange Data Explorer are allowed.

You also **do not** have to take into account the daily rep cap of 200.

## Winning

Shortest code in bytes wins.

# Answer
> 1 votes
# Python, 336 Bytes

Anonymous lambda function, takes a string.

Should work, but couldn't test it, because I drained my api quota.

(**Warning! Will drain your api quota!)**

```
import requests,re
lambda x,u="http://api.stackexchange.com/2.2/users/%s%s?site=codegolf&page=%d":int(re.search('n":\d+',requests.get(u%(x,"",1)).text).group()[3:])+sum([5*len(re.findall(':5,',requests.get(u%(x,"/reputation-history",i)).text))-2*len(re.findall('-2',requests.get(u%(x,"/reputation-history",i)).text))for i in range(99)])

```

a bit quota-friendlier:

```
import requests,re
f=lambda x,u="https://api.stackexchange.com/2.2/users/%s%s?site=codegolf&pagesize=100&page=%d":int(re.search('n":\d+',requests.get(u%(x,"",1)).text).group()[3:])+sum([5*len(re.findall(':5,',requests.get(u%(x,"/reputation-history",i)).text))-2*len(re.findall('-2',requests.get(u%(x,"/reputation-history",i)).text))for i in range(30)])

```

---
Tags: code-golf, internet
---


title: Thwart Lepton compression

text:
# Question
Title: Thwart Lepton compression
Dropbox recently released Lepton (GitHub), a method that **losslessly** compresses JPEG images round-trip, saving an average of 22%.

Because of the pigeonhole principle, any *general* compression algorithm cannot be *guaranteed* to result in a smaller file (*general* because it doesn't apply to inputs constrained to a specific format). Lepton exploits common characteristics about JPEGs, which if subverted, might pigeonhole it to produce a file larger than the source.

# Requirements

Write a program that generates:

* A valid JPEG/JFIF image,
* with a size between 0.5 MB and 1 MB,
* no smaller than 256 × 256 px,
* no larger than 4096 × 4096 px,
* recognizable by Lepton (it can successfully "compress" to a `.lep` image), and
* decompresses to an *identical* `.jpg` (as the input).
* `APPx`, `COM`, and other metadata, non-graphical marker sections are restricted in the JPEG (injecting arbitrary amounts of random bytes into the image to asymptotically approach 1:1 compression is lame.)
    + an `APP0` JFIF marker is permitted but no thumbnail is allowed (should be exactly 16 bytes)
    + **tl;dr** If you're not intentionally shoving metadata into an EXIF segment and you disable any sort of thumbnail your language library of choice wants to put into the image, that should be OK.

Post the code and image.

If you want to write a program that produces a *Lepton* image that when converted yields a JPEG meeting the criteria, that's fine. It must remain identical across arbitrarily many JPEG → Lepton → JPEG → ... cycles.

# Scoring

The byte size of the Lepton image divided by the source JPEG image. Higher (worse Lepton compression) is better. Run Lepton with default flags and switches.

---

# Getting Lepton

A 5-second crash-course to build Lepton:

```
git clone https://github.com/dropbox/lepton.git
cd lepton
./autogen.sh && ./configure && make

# fish shell: ./autogen.sh ;and ./configure ;and make

```

Then `./lepton --help` should tell you things.

# Answer
> 5 votes
# Python 3 + mozjpeg + /dev/urandom, 720×720: avg. score 102%

Depends on the `mozjpeg` package, the code assumes it's installed into `/usr/local/opt/mozjpeg`. (on OS X it's trivial to install, just run `brew install mozjpeg`)

Also it depends on `/dev/urandom` special file, it's used for generating random data.

The code simply feeds random data to `mozjpeg` compressor (in TGA format, because cjpeg understands it and it has very simple header), and lets it create an optimized jpeg file. Quality is set to the maximum because it makes DCT coefficients the least compressable, and it doesn't matter much what algorithm is used to compress uncompressable data.

I checked that the jpeg-\>lepton-\>jpeg cycle is lossless — it is true.

```
import subprocess
from subprocess import PIPE

c_mozjpeg_path = '/usr/local/opt/mozjpeg/bin/cjpeg'
cjpeg_params = '-quality 100 -dc-scan-opt 2 -dct float -targa'
image_size = 720

def write_random_tga_image(w, h, of, rf):
    def wb(value, size):
        of.write(int.to_bytes(value, size, 'little'))

    wb(0, 2)
    wb(3, 1)
    wb(0, 9)
    wb(w, 2)
    wb(h, 2)
    wb(8, 1)
    wb(0, 1)

    data_size = w * h
    while data_size > 0:
        data_size -= of.write(rf.read(data_size))

def main():
    with open('/dev/urandom', 'rb') as rf:
        with open('oops.jpg', 'wb') as f:
            p = subprocess.Popen((c_mozjpeg_path,) + tuple(cjpeg_params.split(' ')), stdin=PIPE, stdout=f)
            write_random_tga_image(image_size, image_size, p.stdin, rf)
            p.communicate()

if __name__ == '__main__':
    main()

```

Code is not golfed, obviously.

Example image:

Fun fact: generated JPEG file is larger than the source uncompressed TGA image, even though JPEG uses lossy compression.

Fun fact 2: Imgur (the default image hosting for SO) does very bad job at this file — for some reason it recompresses it to lower quality, even though it's less than 1MB. So I used Github to upload the example image.

Fun fact 3: In general, mozjpeg indeed does better JPEG compression while staying compatible with existing JPEG decoders. And it also has tool to losslessly optimize JPEG files, too — `jpegtran`.

# Answer
> 1 votes
# Naive Noise, 1024 × 1024: score 85.55%

A compliant example in Python to get the ball rolling. Not optimized in any way; probable shortcomings:

* No idea what the default quality setting is.
* Each 8x8 block has practically the exact same average value (~50%) to the one adjacent to it: Lepton says that they use that information to save space.
* Totally default quantization and Huffman tables (whatever the library decides to use).

---

```
import numpy as np
from PIL import Image

np.random.seed(0) # make sure it's repeatable.

size = 1024

imgr = np.random.randint(0, 0xFF, (size, size, 3)).astype('uint8')
pimg = Image.fromarray(imgr)
pimg.save('noise.jpg')

```

Then some bash to do the thing:

```
./lepton noise.jpg noise.lep 2>\dev\null # vomits out a lot of technobabble
./lepton noise.lep noise-out.jpg 2>\dev\null

diff -qs noise.jpg noise-out.jpg

SIZE1=$(stat -f "%z" noise.jpg) # http://superuser.com/a/570920/18931
SIZE2=$(stat -f "%z" noise.lep)
RATIO=$(bc <<< "scale=4; $SIZE2/$SIZE1")
echo "$SIZE2/$SIZE1 = $RATIO"

# Files noise.jpg and noise-out.jpg are identical
# 538817/629769 = .8555

```

---
Tags: code-challenge, image-processing, compression
---


title: Pokemon GO Evolution Cost Calculator

text:
# Question
Title: Pokemon GO Evolution Cost Calculator
Tired of always wondering how many more Pokémon you need to catch to get those high-tier evolutions? Wonder no more! Now you will write a complete program or function to calculate it for you!

## The Challenge:

As input, your program will receive a list of the costs in candy to evolve a Pokémon to the next tier. (This list may be separated by any delimiter of your choosing, or as function arguments). Your program will then return or print the number of Pokémon that must be caught, including the one that will be evolved, to evolve through all the tiers given.

How do you calculate this? Like so:
1. Add up all the candy costs: `12 + 50 = 62`
2. Subtract 3 candies from the total, this being from the one Pokémon you keep for evolving: `62 - 3 = 59`
3. Divide this number by 4 (3 for catching, 1 for giving it to the Professor), always taking the `ceil()` of the result: `ceil(59/4) = 15`
4. Finally, add 1 to this total to get the total number of Pokémon you must catch, 16!

Example `Input -> Output`:

```
[4] -> 2
[50] -> 13
[12, 50] -> 16
[25, 100] -> 32
[19, 35, 5, 200] -> 65

```

## Winning:

The app has already taken up most of the space on your phone, so your program needs to be as short as possible. The complete program or function with the smallest byte count will be accepted in two weeks! (with any ties being settled by the earliest submitted entry!)

# Answer
# Jelly, ~~5~~ 4 bytes

```
S:4‘

```

Try it online!

`S`um, integer divide `:` by `4` and increment .
> 9 votes

# Answer
# 05AB1E, 4 bytes

```
O4÷>

```

**Explanation**

```
O    # sum
 4÷  # integer division by 4
   > # increment

```

Try it online
> 9 votes

# Answer
# C# REPL, 15 bytes

```
n=>n.Sum()/4+1;

```

Casts to `Func<IEnumerable<int>, int>`.
> 3 votes

# Answer
## Actually, 4 bytes

```
Σ¼≈u

```

Try it online!

Explanation:

```
Σ¼≈u
Σ     sum
 ¼    divide by 4
  ≈   floor
   u  add 1

```
> 3 votes

# Answer
# Brachylog, 5 bytes

```
+:4/+

```

Try it online!

### Explanation

A very original answer…

```
+        Sum
 :4/     Integer division by 4
    +    Increment

```
> 3 votes

# Answer
# BASH (sed + bc) 19

```
sed 's~)~+4)/4~'|bc

```

Input is a `+` separate list on stdin
E.g.:
`echo '(19+35+5+200)'| sed 's~)~+4)/4~'|bc`
> 2 votes

# Answer
# S.I.L.O.S ~~100 99~~ 103 characters + 22 for sample input

Code with testing harness.

```
set 512 52
set 513 10
GOSUB e
GOTO f
funce
a = 0
i = 511
lblE
i + 1
b = get i
a + b
if b E
a / 4
a + 1
return
lblf
printInt a

```

input as a series of set commands to modify the spots of the heap starting at spot 512.
Try it Online!
> 1 votes

# Answer
## Retina, ~~18~~ 17 bytes

Byte count assumes ISO 8859-1 encoding.

```
$
¶4
.+|¶
$*
1111

```

Input is linefeed-separated.

Try it online!
> 1 votes

# Answer
# Haskell, 17 bytes

```
(+1).(`div`4).sum

```
> 1 votes

# Answer
## Pyke, 4 bytes

```
seeh

```

Try it here!

```
((sum(input)/2)/2)+1

```
> 1 votes

# Answer
# Pyth, 5 bytes

```
h/sQ4

```

Try it here!

Sum input with `sQ`, divide by 4 with `/4` and finally increment `h`.
> 1 votes

# Answer
# CJam, 7 bytes

```
{:+4/)}

```

Try it here!

Defines an unnamed block that expects the input on the stack and leaves the result there.
`:+` sums the list, `4/` divides the result by 4 and `)` increments that.
> 1 votes

# Answer
# R, 22 bytes

```
floor(sum(scan())/4+1)

```
> 1 votes

# Answer
# **JavaScript, 29 Bytes**

```
x=>x.reduce((a,b)=>a+b)/4+1|0

```
> 1 votes

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


# Question
Title: Given a list of Tetris moves, return the number of completed lines
# Description

We consider a slightly simplified version of Tetris where each move consists of:

* rotating the piece clockwise, 0 to 3 times
* positioning the piece at a given column
* fast drop

The goal is to determine the number of completed lines, given a list of such Tetris moves.

Completed rows are removed as pieces are dropped, following standard Tetris rules.

**Playfield**

The playfield is 10-column wide. There's no *Game Over* and it is assumed that there's always enough space and time to perform the above actions, no matter the configuration of the playfield. The height of the playfield doesn't really matter here, but you can use the standard 22 rows as an upper limit.

**Shapes of Tetrominoes**

## Input / Output

**Input**

A comma separated list of Tetris moves encoded with 3 characters. The first two character describe the Tetromino shape to use and the last one describes the position where it's dropped.

1. Tetromino: `I`, `O`, `T`, `L`, `J`, `Z` or `S`, in the same order as above.
2. Number of clockwise rotations: `0` to `3`
3. Column: `0` to `9`. This is the column in which the top-left corner of the piece (marked with an `x` on the above picture) is located after the rotation 1

It is assumed that all moves in the provided list are valid. There's no need to check for invalid entries such as `I07` (horizontal `I` shape put too far on the right).

1 *You are free to either implement a real rotation algorithm or to hardcode all the different shapes, as long as the `x` is located in the column given by the third character of the move.*

**Output**

Number of completed lines.

## Example

`O00,T24` will generate the first position and `O00,T24,S02,T01,L00,Z03,O07,L06,I05` will generate the second position.

Therefore, the following sequence will generate a Tetris and should return `4`:

```
O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19

```

## Test cases

```
1) "O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19" -> 4
2) "S00,J03,L27,Z16,Z18,I10,T22,I01,I05,O01,L27,O05,S13" -> 5
3) "I01,T30,J18,L15,J37,I01,S15,L07,O03,O03,L00,Z00,T38,T01,S06,L18,L14" -> 4
4) "S14,T00,I13,I06,I05,I19,L20,J26,O07,Z14,Z10,Z12,O01,L27,L04,I03,S07,I01,T25,J23,J27,O01,
    I10,I10" -> 8
5) "O00,T24,L32,T16,L04,Z11,O06,L03,I18,J30,L23,Z07,I19,T05,T18,L30,I01,I01,I05,T02" -> 8

```

## Test page

You can use **this JSFiddle** to test a move list.

# Answer
> 5 votes
# PHP, ~~405~~ ~~399~~ ~~378~~ ~~372~~ ~~368~~ ~~360~~ ~~354~~ ~~347~~ ~~331~~ ~~330~~ ~~328~~ ~~319~~ ~~309~~ 300 bytes

(with Dave´s block mapping)

```
<?$f=[~0];L:for($y=0;$f[++$d+$y]|$s;$s>>=4)$y-=1022<$f[$d+$y]=$f[$d]|$s%16<<$x;$c-=$y;if(list($p,$r,$x)=$argv[++$z])for($s=I==$p?$r&1?4369:15:hexdec(decoct(O==$p?27:ord(base64_decode('M1ozWjqaF1kemR6ZPJMPyTnSJ0s')[ord($p)/4%5*4+$r])));;$d--)for($y=4;$y--;)if ($f[$d+$y]>>$x&$s>>$y*4&15)goto L;echo$c;

```

program, takes moves as separate arguments, prints result

**breakdown to function:**

takes moves as array, returns result

```
function t($a)
{
    $f=[~$z=0];             // init field $f (no need to init $z in golfed version)
    L:                      // jump label
                            // A: paint previous piece at line $d+1:
#   if($s)paint($f,$s,$d+1,$x);
    for($y=0;               // $y = working line offset and temporary score
        $f[++$d-$y]|$s;$s>>=4)// next field line; while field or piece have pixels ...
        $s>>=4)                 // next piece line
        $y+=1022<               // 3: decrease temp counter if updated line is full
            $f[$d-$y]=$f[$d]    // 2: use $y to copy over dropped lines
                |$s%16<<$x;     // 1: set pixels in working line
    $c+=$y;                         // add temp score to global score
#   paint($f);var_dump($c);
    if(list($p,$r,$x)=$a[$z++])// B: next piece: $p=name; $r=rotation, $x=column
#   {echo"<b>$z:$p$r-$x</b><br>";
        for(                // C: create base 16 value:
            $s=I==$p
                ? $r&1?4369:15  // I shape (rotated:0x1111, not rotated:0xf)
                : hexdec(decoct(    // 5: convert from base 8 to base 16
                    O==$p ? 27  // O shape (rotation irrelevant: 033)
                    : ord(          // 4: cast char to byte
                                    // 0: 4 bytes for each remaining tetromino
                        base64_decode('M1ozWjqaF1kemR6ZPJMPyTnSJ0s')[
                            ord($p)/4%5 // 1: map STZJL to 01234
                            *4      // 2: tetromino offset
                            +$r]    // 3: rotation offset
            )));;$d--
        )
            for($y=4;$y--;) // D: loop $y through piece lines
                if ($f[$d+$y]>>$x & $s>>$y*4 & 15) // if collision ...
                    goto L;         // goto Label: paint piece, tetris, next piece
#   }
    return$c;               // return score
}

```

for reference: the old mapping

```
            hexdec(decoct(          // 3. map from base 8 to base 16
                                    // 0. dword values - from high to low: rotation 3,2,1,0
                [0x991e991e,0xc90f933c,0x4b27d239,0x1b1b1b1b,0,0x5a335a33,0x59179a3a]
                [ord($m[0])/2%9]    // 1. map ZJLO.ST to 0123.56 -> fetch wanted tetromino
                >>8*$m[1]&255       // 2. the $m[1]th byte -> rotated piece
            ))

```

**testing**

see my other PHP answer

**want to watch?**

remove the `#` from the function source and add this:

```
function paint($f,$s=0,$d=0,$x=0){echo'<pre>';for($y=count($f)+5;$y--;$g=0)if(($t=(($z=$y-$d)==$z&3)*($s>>4*$z&15)<<$x)|$r=$f[$y]|0){$z=$t?" $r|$t=<b".(1022<($z=$t|$r)?' style=color:green':'').">$z":" <b>$r";for($b=1;$b<513;$b*=2)$z=($t&$b?'<b>'.($r&$b?2:1).'</b>':($r&$b?1:'.')).$z;printf("%02d $z</b>\n",$y);}echo'</pre>';}

```

**some golfing steps**

Rev. 5: A big leap (399-**21**=378) came by simply moving the column shift
from a separate loop to the two existing loops.

Rev. 8: Switching from array to base 16 for the piece ($s) did not give much,
but made way for some more golfing.

Rev. 17: crunched the values with `base64_encode(pack('V*',<values>))`
and used byte indexing instead of `unpack` to save **16** bytes

Rev. 25 to 29: inspired by Dave´s code: new hashing (-2), new loop design (-9), goto (-10)
no pre-shift though; that would cost 17 bytes.

**more potential**

With `/2%9`, I could save 15 bytes (only 14 bytes with `/4%5`)
by putting binary data into a file `b` and then indexing `file(b)[0]`.
Do I want that?

UTF-8 characters would cost a lot for the transformation.

**on the hashing**

I used `ZJLO.ST /2%9 -> 0123.56`; but `T.ZJLOS /3%7 -> 0.23456` is as good.
one byte longer: `O.STJLZ %13/2 -> 0.23456`
and three more: `OSTZJ.L %17%12%9 -> 01234.6`

I could not find a short hash (max. 5 bytes) that leaves no gap;
but Dave found `STZJL /4%5 -> 01234`, dropping the O from the list. wtg!

btw: `TIJSL.ZO (%12%8) -> 01234.67` leaves room for the `I` shape
(and a fictional `A`, `M` or `Y` shape). `%28%8` and `%84%8`, do the same (but with `E` instead of `A`).

# Answer
> 16 votes
# C, ~~401~~ ~~392~~ ~~383~~ ~~378~~ ~~374~~ ~~351~~ ~~335~~ ~~324~~ ~~320~~ ~~318~~ ~~316~~ 305 bytes

```
d[99]={'3Z3Z',983177049,513351321,1016270793,970073931,~0},*L=d+5,V,s;char c;main(x){B:for(c=0;c[++L]|V;V>>=4)c-=(L[c]=*L|(V&15)<<x)>1022;s-=c;if(scanf("%c%1d%d,",&c,&V,&x)>2)for(V=c^79?d[c/4%5]>>24-V*8:27,V=c^73?V/64%4<<8|V/8%8<<4|V%8:V&32?15:4369;;--L)for(c=4;c--;)if(L[c]>>x&V>>c*4&15)goto B;return s;}

```

Takes comma-separated input on stdin, returns the score in the exit status.

Requires `char` to be signed (which is the default for GCC) and requires `'3Z3Z'` to be interpreted as 861549402 (which is the case for GCC on little endian machines, at least).

---

### Usage example:

```
echo "O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19" | ./tetris; echo "$?";

```

---

### High-level explanation:

All shapes except the line can fit in a 3x3 grid with one corner missing:

```
6 7 -
3 4 5
0 1 2

```

That means it's easy to store them in a byte each. For example:

```
- - -         0 0 -
- # -   -->   0 1 0   -->   0b00010111
# # #         1 1 1

```

(we align each piece to the bottom-left of the box to make dropping it easier)

Since we get at least 4 bytes to an int, this means we can store all 4 rotations of each piece in a single integer, with a special case for the line. We can also fit each row of the game grid into an int (only needs 10 bits), and the currently falling piece into a long (4 lines = 40 bits).

---

### Breakdown:

```
d[99]={             // General memory
  '3Z3Z',           //  Shape of "S" piece (multi-char literal, value = 861549402)
  983177049,        //  Shape of "T" piece
  513351321,        //  Shape of "Z" piece
  1016270793,       //  Shape of "J" piece
  970073931,        //  Shape of "L" piece
  ~0                //  Bottom of game grid (solid row)
},                  //  Rest of array stores lines in the game
*L=d+5,             // Working line pointer (start >= base of grid)
V,                  // Current piece after expansion (also stores rotation)
s;                  // Current score (global to initialise as 0)
char c;             // Input shape identifier (also counts deleted lines)
main(x){            // "x" used to store x location
  B:                                // Loop label; jumps here when piece hits floor
  for(c=0;c[++L]|V;V>>=4)           // Paint latest piece & delete completed lines
    c-=(L[c]=*L|(V&15)<<x)>1022;
  s-=c;                             // Increment score
  if(scanf("%c%1d%d,",&c,&V,&x)>2)  // Load next command
    for(V=c^79?                     // Identify piece & rotation
          d[c/4%5]>>24-V*8          //  Not "O": load from data
        :27,                        //  Else "O": always 27
        V=c^73?                     // If not "I" (line):
          V/64%4<<8|V/8%8<<4|V%8    //  expand shape to 16-bits
        :                           // Else we are a line:
          V&32?                     //  "I" coincides with "J"; use this to check
               15:4369;             //  horizontal/vertical
        ;--L)                       // Loop from top-to-bottom of grid
      for(c=4;c--;)                 //  Loop through rows of piece
        if(L[c]>>x&V>>c*4&15)       //   If collides with existing piece:
          goto B;                   //    Exit loops
  return s;                         // Return score in exit status
}

```

---

-4, -1 thanks to @Titus, and -23, -11 with inspiration from their answer

# Answer
> 2 votes
# Ruby, ~~474~~ ~~443~~ ~~428~~ 379 + 48 = 427 bytes

-1 thanks to @Titus

This can definitely be golfed more.

Reads a binary dictionary of pieces (see below) from STDIN or a filename and takes a move list as an argument, e.g. `$ cat pieces | ruby script.rb O00,T24,S02,...`.

```
q=$*.pop
z=$<.read.unpack('S*')
b=c=g=i=0
x=10
u=1023
r=->n{n&2**x-1>0?n:r[n>>x]}
y=->n{n>0?[n&u]+y[n>>x]:[]}
l=->c,n{z.find{|m|m>>x==c<<2|n.to_i}||l[c,n-2]}
q.scan(/(\w)(\d)(\d)/){n=l["IOTLJSZ".index($1),$2.to_i]
v=(n&1|(n&6)<<9|(n&56)<<17|(n&960)<<24)<<$3.to_i
(y[b].size+1).times{t=b<<40
t&v>0&&break
g=t|v
v<<=x}
b=0
a=y[r[g]]
a.grep_v(u){|o|b|=o<<x*i
i+=1}
c+=a.count u}
p c

```

Binary piece data (xxd format)

```
0000000: c003 4b04 d810 d814 b820 9c24 d029 5a2c  ..K...... .$.)Z,
0000010: 7830 9634 e039 ca3c 3841 d444 c849 4e4c  x0.4.9.<8A.D.INL
0000020: 9861 9869 5c64 5c6c f050 f058 9a54 9a5c  .a.i\d\l.P.X.T.\

```

See it on repl.it (with hard-coded arguments, dictionary): https://repl.it/Cqft/2

## Ungolfed & explanation

```
# Move list from ARGV
q = $*.pop

# Read piece dictionary; pieces are 16-bit integers: 3 for letter,
# 2 for rotation, 10 for shape (and 1 wasted)
z = $<.read.unpack('S*')

# Empty board and various counters
b = c = g = i = 0
x = 10 # Magic numbers
u = 1023

# A function to remove empty lines
r = ->n{ n & 2**x - 1 > 0 ? n : r[n >> x] }

# A function to split the board into lines
y = ->n{ n > 0 ? [n & u] + y[n >> x] : [] }

# A function to lookup a piece by letter and rotation index
l = ->c,n{ z.find {|m| m >> x == c << 2 | n.to_i } || l[c, n-2] }

# Read the move list
q.scan(/(\w)(\d)(\d)/) {
  # Look up the piece
  n = l["IOTLJSZ".index($1), $2.to_i]

  # Convert the 10-bit piece to a 40-bit piece (4 rows of 10 columns)
  v = (n & 1 |
        (n & 6) << 9 |
        (n & 56) << 17 |
        (n & 960) << 24
      ) << $3.to_i # Shift by the appropriate number of columns

  # Drop the piece onto the board
  (y[b].size + 1).times {
    t = b << 40
    t & v > 0 && break
    g = t | v
    v <<= x
  }

  # Clear completed rows
  b = 0
  a = y[r[g]]
  a.grep_v(u) {|o|
    b |= o << x * i
    i += 1
  }

  c += a.count u # Count cleared rows
}
p c

```

# Answer
> 2 votes
# PHP, ~~454~~ ~~435~~ ~~427~~ ~~420~~ 414 bytes

bit fields for pieces and map; but no special case for the `I` shape as Dave´s golfing.

```
<?$t=[I=>[15,4369],O=>[51],T=>[114,562,39,305],L=>[113,802,71,275],J=>[116,547,23,785],Z=>[54,561],S=>[99,306]];foreach($argv as$z=>$m)if($z){$s=$t[$m[0]][$m[1]%count($t[$m[0]])];for($d=$i=0;$i<4;$i++)for($k=0;$k<4;$k++)if($s>>4*$k&1<<$i){for($y=0;$y++<count($f);)if($f[$y-1]&1<<$m[2]+$i)$d=max($d,$y-$k);$k=3;}for($k=$d;$s;$k++,$s>>=4)if(1022<$f[$k]|=$s%16<<$m[2]){$c++;unset($f[$k]);}$f=array_values($f);}echo$c;

```

takes arguments from command line, prints result

**ungolfed as function**

takes arguments as array, returns result

```
function t($a)
{
    // bitwise description of the stones and rotations
    $t=[I=>[15,4369],O=>[51],T=>[114,562,39,305],L=>[113,802,71,275],J=>[116,547,23,785],Z=>[54,561],S=>[99,306]];
    foreach($a as$m)
    {
        $s=$t[$m[0]][$m[1]%count($t[$m[0]])];   // $s=stone
        // find dropping space
        for($d=$i=0;$i<4;$i++)
            // a) lowest pixel of stone in column i
            for($k=0;$k<4;$k++)
                if($s>>4*$k&1<<$i)
                {
                    // b) top pixel of field in column x+i
                    for($y=0;$y++<count($f);)
                        if($f[$y-1]&1<<$m[2]+$i)$d=max($d,$y-$k);
                    $k=3; // one byte shorter than `break;`
                }
        // do drop
        for($k=$d;$s;$k++,$s>>=4)
            if(1022<$f[$k]|=$s%16<<$m[2])   // add block pixels to line pixels ... if full,
            {$c++;unset($f[$k]);}           // tetris
        $f=array_values($f);
    }
    return$c;
}

```

**tests** (on function)

```
$data=[
    "O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19"=>4,
    "S00,J03,L27,Z16,Z18,I10,T22,I01,I05,O01,L27,O05,S13" => 5,
    "I01,T30,J18,L15,J37,I01,S15,L07,O03,O03,L00,Z00,T38,T01,S06,L18,L14" => 4,
    "S14,T00,I13,I06,I05,I19,L20,J26,O07,Z14,Z10,Z12,O01,L27,L04,I03,S07,I01,T25,J23,J27,O01,I10,I10" => 8,
    // additional example for the two last tetrominoes:
    'O00,T24,L32,T16,L04,Z11,O06,L03,I18,J30,L23,Z07,I19,T05,T18,L30,I01,I01,I05,T02' => 8,
];
function out($a){if(is_object($a)){foreach($a as$v)$r[]=$v;return'{'.implode(',',$r).'}';}if(!is_array($a))return$a;$r=[];foreach($a as$v)$r[]=out($v);return'['.join(',',$r).']';}
function cmp($a,$b){if(is_numeric($a)&&is_numeric($b))return 1e-2<abs($a-$b);if(is_array($a)&&is_array($b)&&count($a)==count($b)){foreach($a as $v){$w = array_shift($b);if(cmp($v,$w))return true;}return false;}return strcmp($a,$b);}
function test($x,$e,$y){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>",out($x),'</td><td>',out($y),'</td><td>',out($e),'</td><td>',cmp($e,$y)?'N':'Y',"</td></tr>";$h='';}
foreach($data as $v=>$e)
{
    $x=explode(',',$v);
    test($x,$e,t($x));
}

```

---
Tags: code-golf, tetris
---


title: Build a marginal tax calculator

text:
# Question
Title: Build a marginal tax calculator
There have been some tax rate calculator problems here that depend on defined rates (specifically US federal rates), but none that have done it for arbitrary lists.

Your task is to build a program or function that will take an arbitrary list of marginal tax brackets and calculate the effective amount of tax paid on a given amount of taxable income.

Your program will take as input:

* `N` pairs of numbers in the form `(amt, rate)`, each representing a tax bracket.

+ `amt` is the amount of taxable income above which at which the tax rate starts to apply. These amounts will all be integers, and appear in increasing order.
    + `rate` is the tax rate, expressed as a decimal percentage from 0 to 100 inclusive.
* The amount of taxable income, as a nonnegative integer.

If no rate is specified for $0, the rate is assumed to be 0%.

Alternatively, your program can also take as input two lists `(amt1, amt2, ...)` and `(rate1, rate2, ...)`, containing the amounts and rates in the same order.

Your program will then output the payable tax, either to two decimal places, or rounded *down* to the nearest whole currency unit.

---

An example input (the most recent Canadian tax brackets, from 2016, with the basic personal tax credit applied and nothing else):

```
11474 15
45282 20.5
90563 26
140388 29
200000 33

393216

```

And its corresponding output:

```
108357.07  or  108357

```

---

The shortest program in any language to do this wins.

# Answer
## 05AB1E, ~~35~~ 24 bytes

```
vy³ï‚{0è)˜}³ï‚˜¥²ø€PTn/O

```

**Explanation**

```
vy                         # for each amount
  ³ï‚                      # pair with taxable income
     {0è                   # get min
        )˜}                # add to list
           ³ï‚˜            # add income to the end of the list
               ¥           # get deltas
                ²ø         # zip with tax rates
                  €P       # map product on each pair of [amount in tax bracket,rate]
                    Tn/    # divide by 100
                       O   # sum
                           # implicitly display result

```

Try it online
> 2 votes

# Answer
# Haskell, ~~67~~ 66 bytes

Thanks Damien for -1 byte.

This solution is in the form of an infix function, `?`, of type `(Integral b, RealFrac r) => [(r, r)] -> r -> b`. The helper function, `#`, does the required calculations while `?` serves to handle the IO specifications.

```
a?b=floor$reverse a#b
((m,p):r)#i|v<-min i m=p/100*(i-v)+r#v
_#_=0

```
> 3 votes

# Answer
# Mathematica ~~85~~ 82 bytes

Derived from Josh O'Brien's code in R.

```
d_~f~i_:=Tr@Thread[Differences@((i~Min~#&/@d[[All,1]]~Append~∞))d[[All,2]]/100.]

```

---

## Usage

```
f[{{11474, 15}, {45282, 20.5}, {90563, 26}, {140388, 29}, {200000, 33}}, 393216]

```

108357.
> 2 votes

# Answer
## JavaScript (ES6), 60 bytes

```
(a,n)=>a.map(([b,r])=>{t+=n>b&&(n-b)*(r-p);p=r},p=t=0)|t/100

```

`a` is an array of arrays of band and rate, which would be `[[11474, 15], [45282, 20.5], [90563, 26], [140388, 29], [200000, 33]]` for the given example, and `n` is the income (`393216`).
> 1 votes

# Answer
## Matlab, 79 bytes

Assuming we can take `amt` and `rate` as separate column vectors:

```
function[]=f(a,b,c)
t=sort([0;a;c]);fix(sum(diff(t).*[0;b/100].*(t(2:end)<=c)))

```

If we can't (then `a` is a two-column matrix of `amt` and `rate`) it's 87 bytes.

```
function[]=f(a,c)
t=sort([0;a(:,1);c]);fix(sum(diff(t).*[0;a(:,2)/100].*(t(2:end)<=c)))

```

**Explanation:**

```
f(a,b,c)           -- takes amt, rate and income
[0;a;c]            -- gives a vector of amounts with 0 and the income amount
t=sort(...)        -- sort this vector
diff(t)            -- gives us amounts to be taxed in every bracket
diff(t).*[0;b/100] -- tax in every bracket
.*(t(2:end)<=c)    -- take only entries lower than the income
sum(...)           -- sum everything
fix(...)           -- round towards 0

```
> 1 votes

# Answer
# Swift, 61 bytes

```
zip(zip(m+[i],[0]+m).map{$0-$1},[0]+r).map{$0*$1}.reduce(0,+)

```

Ungolfed, with test cases:

```
struct TaxContext {
    let marginLowerBound: [Double]
    let rates: [Double]
}

// ungolfed
extension TaxContext {
    func calcAfterTaxIncome(_ income: Double) -> Double {
        //drop first element (0), append income
        let upper = marginLowerBound + [income]
        let lower = [0] + marginLowerBound

        let incomeInEachMargin = zip(upper, lower)
            .map{ upperBound, lowerBound in upperBound - lowerBound }

        let taxInEachMargin = zip(incomeInEachMargin, [0]+rates)
            .map{ incomeInMargin, rate in incomeInMargin * rate }

        let totalTax = taxInEachMargin.reduce(0, +)

        print(upper)
        print(lower)
        print(incomeInEachMargin)
        print(rates)
        print(taxInEachMargin)

        return totalTax
    }
}

// golfed
extension TaxContext {
    // computed properties to serve as aliases for the golfed version
    var m: [Double] { return self.marginLowerBound }
    var r: [Double] { return self.rates }

    func f(_ i: Double) -> Double {
        return zip(zip(m+[i],[0]+m).map{$0-$1},[0]+r).map{$0*$1}.reduce(0,+)
    }
}

let testCase1 = TaxContext(
    marginLowerBound: [10_000, 20_000, 30_000],
    rates: [0.1, 0.2, 0.3, 0.4]
)
let result1 = testCase1.calcAfterTaxIncome(70_000)
print(result1)

let testCase2 = TaxContext(
    marginLowerBound: [11474 , 45282, 90563, 140388, 200000],
    rates: [0.15, 0.205, 0.26, 0.29, 0.33]
)
let result2 = testCase2.calcAfterTaxIncome(393216)
print(result2)

```
> 0 votes

---
Tags: code-golf
---